在這些系列文章中，我將主要在Golang中實現一些與分佈式系統相關的著名論文。 （請閱讀以前關於使用紅黑樹的一致性哈希的文章）
本文是Golang中CHORD DHT論文的簡單實現。
DHT簡介
Distributed Hash Table
分佈式哈希表（DHT）是分散式分佈式系統的一類，它提供類似於哈希表的查找服務：（鍵，值）對存儲在DHT中，並且任何參與節點都可以有效地檢索與哈希表關聯的值。 給定密鑰。 維護從鍵到值的映射的責任以這樣的方式分佈在節點之間，即，參與者集合中的更改導致最小程度的中斷。 這允許DHT擴展到極大數量的節點，並處理連續的節點到達，離開和故障。
DHT形成了可用於構建更復雜的服務的基礎結構，例如任播，協作Web緩存，分佈式文件系統，域名服務，即時消息傳遞，多播以及對等文件共享和內容分發系統。 使用DHT的著名分佈式網絡包括BitTorrent的分佈式跟蹤器，Coral內容分發網絡，Kad網絡，Storm殭屍網絡，Tox即時通訊程序，Freenet，YaCy搜索引擎和行星際文件系統。
DHT的屬性
DHT特有強調以下特性：
· 自治和分散：節點在沒有任何中央協調的情況下共同形成系統。
· 容錯能力：即使節點不斷加入，離開和出現故障，系統也應該可靠（在某種意義上）。
· 可擴展性：即使有成千上萬個節點，系統也應有效運行。
DHT協議和實現的示例：Apache Cassandra，BATON覆蓋，CAN（內容可尋址網絡），Pastry，Riak，Voldemort
什麼是CHORD？
在計算中，Chord是用於點對點分佈式哈希表的協議和算法。 分佈式哈希表通過將鍵分配給不同的計算機（稱為"節點"）來存儲鍵值對； 節點將存儲它負責的所有鍵的值。 Chord指定如何將密鑰分配給節點，以及節點如何通過首先找到負責該密鑰的節點來發現給定密鑰的值。
Chord與CAN，Tapestry和Pastry一起，是四種原始的分佈式哈希表協議之一。 它是由Ion Stoica，Robert Morris，David Karger，Frans Kaashoek和Hari Balakrishnan於2001年提出的，並由MIT開發。 有關更多信息，可以參考原始論文。
Chord基於一致的哈希，這是我在上一篇文章中實現的。
實施細節
Chord協議僅支持一種操作：給定密鑰，它將確定負責存儲密鑰值的節點。 Chord本身並不存儲鍵和值，但提供了允許較上層軟件構建各種存儲系統的原語； CFS就是Chord原語的一種用法。
我將嘗試使用Wiki文章解釋基本實現。
1.基本查詢
Chord協議的核心用法是從客戶端（通常也是節點）查詢密鑰，即查找後繼者（k）。 如果無法在本地找到密鑰，則基本方法是將查詢傳遞給節點的後繼者。 這將導致O（N）查詢時間，其中N是環網中的計算機數。 為了避免上面的線性搜索，Chord通過要求每個節點保留一個手指表最多包含m個條目來實現一種更快的搜索方法，回想一下m是哈希鍵中的位數。
節點n的第i個條目將包含後繼者（（n + 2 ^ {i-1}）mod 2 ^ m）。 手指表的第一個條目實際上是節點的直接後繼者（因此不需要額外的後繼者字段）。 節點每次要查找鍵k時，都會將查詢傳遞給其手指表（ID小於ID的圓圈中"最大"的手指）中k的最接近的後繼者或前任者（取決於手指表） k），直到節點發現密鑰存儲在其直接後繼中。 使用這種手指表，在N節點網絡中查找後繼節點必須聯繫的節點數為O（log N）
<code>// fingerEntry represents a single finger table entry
type fingerEntry struct {
Id []byte // ID hash of (n + 2^i) mod (2^m)
Node *internal.Node
}
func newFingerTable(node *internal.Node, m int) fingerTable {
ft := make([]*fingerEntry, m)
for i := range ft {
ft[i] = newFingerEntry(fingerID(node.Id, i, m), node)
}
return ft
}
// newFingerEntry returns an allocated new finger entry with the attributes set
func newFingerEntry(id []byte, node *internal.Node) *fingerEntry {
return &fingerEntry{
Id: id,
Node: node,
}
}
// Computes the offset by (n + 2^i) mod (2^m)
func fingerID(n []byte, i int, m int) []byte {
// Convert the ID to a bigint
idInt := (&big.Int{}).SetBytes(n)
// Get the offset
two := big.NewInt(2)
offset := big.Int{}
offset.Exp(two, big.NewInt(int64(i)), nil)
// Sum
sum := big.Int{}
sum.Add(idInt, &offset)
// Get the ceiling
ceil := big.Int{}
ceil.Exp(two, big.NewInt(int64(m)), nil)
// Apply the mod
idInt.Mod(&sum, &ceil)
// Add together
return idInt.Bytes()
}/<code>
2.節點加入
每當有新節點加入時，都應維護三個不變式（前兩個確保正確性，最後一個保持快速查詢）：
· 每個節點的後繼者正確指向其直接後繼者。
· 每個密鑰存儲在後繼者（k）中
· 每個節點的手指表應該正確。
為了滿足這些不變性，為每個節點維護一個前置字段。
<code>type Node struct {
*internal.Node
predecessor *internal.Node
successor *internal.Node
fingerTable fingerTable
storage Storage
transport Transport
}/<code>由於後繼項是Finger表的第一個條目，因此我們不再需要單獨維護此字段。 對於新加入的節點n應該執行以下任務：
· 初始化節點n（前身和手指表）。
· 通知其他節點更新其前身和手指表。
· 新節點從後繼節點接管其負責的密鑰。
<code>func (n *Node) join(joinNode *internal.Node) error {
\t// First check if node already present in the circle
\t// Join this node to the same chord ring as parent
\tvar foo *internal.Node
\t// // Ask if our id already exists on the ring.
\tif joinNode != nil {
\t\tremoteNode, err := n.findSuccessorRPC(joinNode, n.Id)
\t\tif err != nil {
\t\t\treturn err
\t\t}
\t\tif isEqual(remoteNode.Id, n.Id) {
\t\t\treturn ERR_NODE_EXISTS
\t\t}
\t\tfoo = joinNode
\t} else {
\t\tfoo = n.Node
\t}
\tsucc, err := n.findSuccessorRPC(foo, n.Id)
\tif err != nil {
\t\treturn err
\t}
\tn.succMtx.Lock()
\tn.successor = succ
\tn.succMtx.Unlock()
\treturn nil
}
/<code>n的前任可以很容易地從後繼（n）的前任（在前一個圓中）獲得。 至於其手指表，有各種初始化方法。 最簡單的方法是對所有m個條目執行查找後繼查詢，從而導致O（M \\ log N）初始化時間。 更好的方法是檢查手指表中的第i個條目對於第（i + 1）個條目是否仍然正確。 這將導致O（log²N）。
3.穩定
為確保正確查找，所有後續指針都必須是最新的。 因此，穩定協議在後臺定期運行，該協議更新了指針表和後繼指針。
穩定協議的工作方式如下：
· Stabilize（）：n向其後繼者要求其前任p，並決定p是否應為n的後繼者（如果p最近加入了系統，就是這種情況）。
· Notify（）：通知n的後繼者存在，因此可以將其前任更改為n
· Fix_fingers（）：更新手指表/ *
· check_predecessor（）：定期檢查前任是否還活著
<code>/*
\tNewNode creates a new Chord node. Returns error if node already
\texists in the chord ring
*/
func NewNode(cnf *Config, joinNode *internal.Node) (*Node, error) {
\tif err := cnf.Validate(); err != nil {
\t\treturn nil, err
\t}
\tnode := &Node{
\t\tNode: new(internal.Node),
\t\tshutdownCh: make(chan struct{}),
\t\tcnf: cnf,
\t\tstorage: NewMapStore(cnf.Hash),
\t}
\tvar nID string
\tif cnf.Id != "" {
\t\tnID = cnf.Id
\t} else {
\t\tnID = cnf.Addr
\t}
\tid, err := node.hashKey(nID)
\tif err != nil {
\t\treturn nil, err
\t}
\taInt := (&big.Int{}).SetBytes(id)
\tfmt.Printf("new node id %d, \\n", aInt)
\tnode.Node.Id = id
\tnode.Node.Addr = cnf.Addr
\t// Populate finger table
\tnode.fingerTable = newFingerTable(node.Node, cnf.HashSize)
\t// Start RPC server
\ttransport, err := NewGrpcTransport(cnf)
\tif err != nil {
\t\treturn nil, err
\t}
\tnode.transport = transport
\tinternal.RegisterChordServer(transport.server, node)
\tnode.transport.Start()
\tif err := node.join(joinNode); err != nil {
\t\treturn nil, err
\t}
\t// Peridoically stabilize the node.
\tgo func() {
\t\tticker := time.NewTicker(1 * time.Second)
\t\tfor {
\t\t\tselect {
\t\t\tcase \t\t\t\tnode.stabilize()
\t\t\tcase \t\t\t\tticker.Stop()
\t\t\t\treturn
\t\t\t}
\t\t}
\t}()
\t// Peridoically fix finger tables.
\tgo func() {
\t\tnext := 0
\t\tticker := time.NewTicker(100 * time.Millisecond)
\t\tfor {
\t\t\tselect {
\t\t\tcase \t\t\t\tnext = node.fixFinger(next)
\t\t\tcase \t\t\t\tticker.Stop()
\t\t\t\treturn
\t\t\t}
\t\t}
\t}()
\t// Peridoically checkes whether predecessor has failed.
\tgo func() {
\t\tticker := time.NewTicker(10 * time.Second)
\t\tfor {
\t\t\tselect {
\t\t\tcase \t\t\t\tnode.checkPredecessor()
\t\t\tcase \t\t\t\tticker.Stop()
\t\t\t\treturn
\t\t\t}
\t\t}
\t}()
\treturn node, nil
}/<code>
許多細節可以在論文中找到。 這是一個簡單的gif，以演示DHT和絃的工作原理。
如您所見，當一個節點關閉時，該節點的密鑰將轉移到後繼節點。
如需要看代碼請私信譯者
(本文翻譯自Farhan Ali Khan的文章《Chord: Building a DHT (Distributed Hash Table) in Golang》，參考：https://medium.com/techlog/chord-building-a-dht-distributed-hash-table-in-golang-67c3ce17417b)
閱讀更多 聞數起舞 的文章
