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

IPFS基于分布式哈希表,实现了3套接口,PeerRouting、ContentRouting、ValueStore。并基于这些接口实现了节点路由、内容寻址、发布订阅、AutoRelay、IPNS等功能。

前言

分布式哈希表(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打洞目前还没有实现,希望后续版本能够更完善。

公众号:

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-01-18 11:25
  • 阅读 ( 985 )
  • 学分 ( 18 )
  • 分类:IPFS

2 条评论

请先 登录 后评论
stirlingx
stirlingx

去中心化搬砖工

8 篇文章, 524 学分