一文搞懂IPFS中的分布式哈希表

前言

分布式哈希表（Distributed Hash Table）简称DHT，主要用于分布式网络的路由寻址，目前有两种主流实现方式Chord和Kademlia。IPFS中的分布式哈希表使用Kademlia协议，简称kad。关于DHT和Kad的基本原理，资料很多，这里不再赘述。本文主要讲解HDT在IPFS中的实现和使用。

哈希表ID

IPFS中的节点ID和分布式哈希表中的ID是不一样的，节点ID叫peer.ID，分布式哈希表中的ID叫 kb.ID（K桶ID）。IPFS节点初始化时，会随机成一个私钥，然后对其对应的公钥进行 SHA2_256 哈希，作为peer.ID。

// IDFromPublicKey returns the Peer ID corresponding to the public key pk.
func IDFromPublicKey(pk ic.PubKey) (ID, error) {
   b, err := pk.Bytes()
   if err != nil {
      return "", err
   }
   var alg uint64 = mh.SHA2_256
   if AdvancedEnableInlining && len(b) <= maxInlineKeyLength {
      alg = mh.IDENTITY
   }
   hash, _ := mh.Sum(b, alg, -1)
   return ID(hash), nil
}

再对peer.ID 计算 SHA256 就得到 kb.ID

// ConvertPeerID creates a DHT ID by hashing a Peer ID (Multihash)
func ConvertPeerID(id peer.ID) ID {
   hash := sha256.Sum256([]byte(id))
   return hash[:]
}

因为 kb.ID 是256 bit，所以IPFS 网络最多可以拥有2^256个节点。

节点距离

kb.ID的异或运算结果就是任意两个节点之间的距离，这里的距离指的是逻辑上的，并非空间上的距离。两个节点kb.ID的公共前缀越多，异或值越小，也就是距离越近。

K桶

因为kb.ID是256 bit，所以IPFS的K桶拥有256个桶，每个桶默认最多存放20个活跃节点的信息。第i个桶中存放的是与本节点kb.ID转化成二进制之后公共前缀数量为i的其他节点信息。IPFS节点启动时，通过配置好的引导节点连接到网络，并将发现的活跃节点存到K桶中。随着时间推移，k桶中的节点也会不断变化。这里面有一套更新机制，这里不再赘述。

路由服务接口

IPFS分布式哈希表提供3种类型的路由服务接口，即PeerRouting、ContentRouting、ValueStore。IPFS上层的很多功能都是基于此实现的。

// Routing is the combination of different routing types supported by libp2p.
// It can be satisfied by a single item (such as a DHT) or multiple different
// pieces that are more optimized to each task.
type Routing interface {
   ContentRouting
   PeerRouting
   ValueStore
}

节点路由（PeerRouting）

通过peer.ID获取节点地址，这是作为一个P2P网络最基本的功能。

// PeerRouting is a way to find address information about certain peers.
// This can be implemented by a simple lookup table, a tracking server,
// or even a DHT.
type PeerRouting interface {
   // FindPeer searches for a peer with given ID, returns a peer.AddrInfo
   // with relevant addresses.
   FindPeer(context.Context, peer.ID) (peer.AddrInfo, error)
}

如果当前节点的K桶中存在目标节点，则返回。若不存在，则从当前节点的K桶中找到离目标节点最近的若干个节点，通过网络请求从这些节点继续找，一直递归，直到没有找到更近的节点为止。为什么可以这样找，因为每个桶的最大容量是固定的20个，但是管理的距离半径却是2倍的关系，离目标节点越近的节点的K桶，拥有更多离目标节点近的节点。查询过程中，每一跳都更接近目标节点，最终收敛于目标节点。

内容寻址（ContentRouting）

内容寻址包含两部分，发布内容（Provide）和查找内容所有者的节点地址（FindProviders）。

// ContentRouting is a value provider layer of indirection. It is used to find
// information about who has what content.
//
// Content is identified by CID (content identifier), which encodes a hash
// of the identified content in a future-proof manner.
type ContentRouting interface {
   // Provide adds the given cid to the content routing system. If 'true' is
   // passed, it also announces it, otherwise it is just kept in the local
   // accounting of which objects are being provided.
   Provide(context.Context, cid.Cid, bool) error
   // Search for peers who are able to provide a given key
   //
   // When count is 0, this method will return an unbounded number of
   // results.
   FindProvidersAsync(context.Context, cid.Cid, int) <-chan peer.AddrInfo
}

当一个节点拥有某个数据时，它将数据的cid和当前节点地址，使用Provide方法，按照以下步骤发布到网络。

• 使用 SHA256 将cid转化成DHT中的kb.ID
• 通过DHT中找到全网中离 cid 最近的若干个节点（这里涉及多次网络跳跃）
• 通过网络请求将 cid 和本节点地址发送给上面找到的节点
• 节点收到请求保存收到的信息，有效期24小时

从上面可以看到，只有部分节点知道某个节点拥有某份数据，而且拥有数据的节点需要定时调用Provide告诉其他节点它持续拥有数据。

网络中任何一个节点只要知道cid，可以通过调用FindProvidersAsync方法，通过以下步骤找到持有数据的节点地址

• 使用 SHA256 将cid转化成DHT中的kb.ID
• 通过DHT中找到全网中离cid最近的若干个节点（这里涉及多次网络跳跃）
• 通过这些节点找到持有数据的节点网络地址

IPFS中使用ContentRouting的功能除了上面说的持有文件数据的发布和查找外，还有几个功能也使用到了。比如发布订阅功能和AutoRelay。

发布订阅（PubSub）

发布订阅是IPFS提供的一个很有用的功能。网络中任何一个节点只要订阅了某个主题（topic），其他节点往这个主题发布消息，订阅的节点就能收到。这个功能极大的简化了开发去中心化即时通信软件的难度。事实上，已经有人这么干了，有个开源项目berty，就是基于此原理实现的。那么IPFS是怎么做到的呢。其实前面讲的内容cid不仅可以是数据的cid，也可以是某个topic的字符串hash。跟前面一样的原理，某个节点订阅消息时，会将topic通过SHA256转化的分布式哈希表中的kb.ID，发送这个kb.ID和本节点地址给距离这个kb.ID最近的若干个节点保存。其他节点发布消息时，就可以根据topic找到订阅的节点，然后直接发送过去。当然IPFS实际实现这个复杂得多，假设同一个topic订阅的节点非常多，这种方式需要每个节点都建立连接，是不太明智的。所以IPFS实现了3中发布消息的路由方式，分别是RandomSubRouter、GossipSubRouter、FloodSubRouter，这里面的细节太多，这里就不展开了。

AutoRelay

由于IPFS网络中并不是所有的节点都有公网IP，而IPFS目前还没实现p2p打洞功能，不在同一个网络的节点之间不能直接通信。所以可以将部分拥有公网IP的节点作为中继使用，不能直连的节点间可以通过中继节点转发数据。要开启这个功能需要中继节点和普通节点在启动前做相应的配置。普通节点可以指定固定中继节点作为中继，也可以通过AutoRelay功能。AutoRelay就是让普通节点具备自动发现全网中已存在的中继节点的能力。AutoRelay功能是如果实现的呢？

IPFS中所有的中继节在分布式哈希表中都有一个共同的key，叫RelayRendezvous,同样需要使用SHA256映射到分布式哈希表的kb.ID 。定义如下

const RelayRendezvous = "/libp2p/relay"

与前面的发布订阅功能类似，中继节点启动后，会自动发布自己的地址给距离这个key最近的若干个节点保存。普通节点可以通过这个key从分布式哈希表中拿到全网活跃的中继节点地址。

VK存储（ValueStore）

分布式哈希表还可以作为分布式的ValueStore存储使用。ValueStore实现了两个方法，PutValue和GetValue。

// ValueStore is a basic Put/Get interface.
type ValueStore interface {
   // PutValue adds value corresponding to given Key.
   PutValue(context.Context, string, []byte, ...Option) error
   // GetValue searches for the value corresponding to given Key.
   GetValue(context.Context, string, ...Option) ([]byte, error)
}

• PubValue通过分布式哈希表，找到距离key最近的若干个节点，并保存。
• GetValue通过分布式哈希表，找到距离key最近的若干个节点，找到value。因为P2P网络的不可靠性，可能多个节点返回的value不一致，GetValue内部有一套机制决定哪个才是最优的，并更新其他节点的value。

基于这个接口，IPFS内部实现了一个名字解析系统IPNS (InterPlanetary Name System)。

IPNS

IPNS包含两个功能，发布（publish）和解析（resolve）。发布指的是将一个IPFS资源路径，绑定一个唯一的key发布到全网，其他节点可以通过key获取资源的路径。其他节点拿到资源路径后就可以通过使用前面讲的ContentRouting找到持有资源的节点，然后通过直连方式或者中继节点下载数据。

IPNS发布流程：

• 用户主动生成一个私钥，如果没有指定则使用节点的私钥
• 通过私钥构建节点ID (peerID)
• 通过peerID加上前缀生成RecordKey，它的value是一个结构体叫IpnsEntry，包含资源的路径、公钥、签名等
• 使用上面的PutValue方法保存key/val对。

// RecordKey returns the libp2p record key for a given peer ID.
func RecordKey(pid peer.ID) string {
   return "/ipns/" + string(pid)
}

IPNS解析就使用GetValue方法通过key取IpnsEntry。从上面可以看到，一个私钥只能生成一个唯一的RecordKey。所以当一个节点需要发布多个资源时，不应该使用节点的私钥，而是要为每个资源指定不同的私钥。

公网与内网

IPFS的DHT内部维护了两个DHT实例，一个公网的WAN，一个内网的LAN。寻找节点时，优先从公网中找，更新时两个网络都更新。

// DHT implements the routing interface to provide two concrete DHT implementationts for use
// in IPFS that are used to support both global network users and disjoint LAN usecases.
type DHT struct {
   WAN *dht.IpfsDHT
   LAN *dht.IpfsDHT
}

总结

IPFS基于分布式哈希表，实现了3套接口，PeerRouting、ContentRouting、ValueStore。并基于这些接口实现了节点路由、内容寻址、发布订阅、AutoRelay、IPNS等功能。同时针对公网和内网维护了两个表实例。我们也看到了IPFS目前功能上的不足，比如P2P打洞目前还没有实现，希望后续版本能够更完善。

公众号：