在这些系列文章中，我将主要在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）

 // 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(∑, &ceil)
   // Add together
   return idInt.Bytes()
}  

2.节点加入

每当有新节点加入时，都应维护三个不变式（前两个确保正确性，最后一个保持快速查询）：

· 每个节点的后继者正确指向其直接后继者。

· 每个密钥存储在后继者（k）中

· 每个节点的手指表应该正确。

为了满足这些不变性，为每个节点维护一个前置字段。

 type Node struct {
  *internal.Node
  predecessor *internal.Node
  successor *internal.Node
  fingerTable fingerTable
  storage Storage
  transport  transport 
}  

由于后继项是Finger表的第一个条目，因此我们不再需要单独维护此字段。 对于新加入的节点n应该执行以下任务：

· 初始化节点n（前身和手指表）。

· 通知其他节点更新其前身和手指表。

· 新节点从后继节点接管其负责的密钥。

 func (n *Node) join(joinNode *internal.Node) error {
// First check if node already present in the circle
// Join this node to the same chord ring as parent
var foo *internal.Node
// // Ask if our id already exists on the ring.
if joinNode != nil {
remoteNode, err := n.findSuccessorRPC(joinNode, n.Id)
if err != nil {
return err
}
if isEqual(remoteNode.Id, n.Id) {
return ERR_NODE_EXISTS
}
foo = joinNode
} else {
foo = n.Node
}
succ, err := n.findSuccessorRPC(foo, n.Id)
if err != nil {
return err
}
n.succMtx.Lock()
n.successor = succ
n.succMtx.Unlock()
return nil
}
  

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（）：定期检查前任是否还活着

 /*
NewNode creates a new Chord node. Returns error if node already
exists in the chord ring
*/func NewNode(cnf *Config, joinNode *internal.Node) (*Node, error) {
if err := cnf.Validate(); err != nil {
return nil, err
}
node := &Node{
Node:       new(internal.Node),
shutdownCh: make(chan struct{}),
cnf:        cnf,
storage:    NewMapStore(cnf.Hash),
}

var nID string
if cnf.Id != "" {
nID = cnf.Id
} else {
nID = cnf.Addr
}
id, err := node.hashKey(nID)
if err != nil {
return nil, err
}
aInt := (&big.Int{}).SetBytes(id)

fmt.Printf("new node id %d, \n", aInt)

node.Node.Id = id
node.Node.Addr = cnf.Addr

// Populate finger table
node.fingerTable = newFingerTable(node.Node, cnf.HashSize)

// Start RPC server
transport, err := NewGrpcTransport(cnf)
if err != nil {
return nil, err
}

node.transport = transport

internal.RegisterChordServer(transport.server, node)

node.transport.Start()

if err := node.join(joinNode); err != nil {
return nil, err
}

// Peridoically stabilize the node.
go func() {
ticker := time.NewTicker(1 * time.Second)
for {
select {
case <-ticker.C:
node.stabilize()
case <-node.shutdownCh:
ticker.Stop()
return
}
}
}()

// Peridoically fix finger tables.
go func() {
next := 0
ticker := time.NewTicker(100 * time.Millisecond)
for {
select {
case <-ticker.C:
next = node.fixFinger(next)
case <-node.shutdownCh:
ticker.Stop()
return
}
}
}()

// Peridoically checkes whether predecessor has failed.

go func() {
ticker := time.NewTicker(10 * time.Second)
for {
select {
case <-ticker.C:
node.checkPredecessor()
case <-node.shutdownCh:
ticker.Stop()
return
}
}
}()

return node, nil
}  

许多细节可以在论文中找到。 这是一个简单的gif，以演示DHT和弦的工作原理。

如您所见，当一个节点关闭时，该节点的密钥将转移到后继节点。

如需要看代码请私信译者

(本文翻译自Farhan Ali Khan的文章《Chord: Building a DHT (Distributed Hash Table) in Golang》，参考：