以太坊和libp2p的dht源码概述(一)

以太坊

对应代码位置
github.comethereumgo-ethereump2pdiscover

概述

以太坊实现了udpv4和udpv6两种节点发现。
他们都包含一个table结构体来存储node信息。

会从table 、discovery两个方面叙述。

table

以太坊的定义是 a Kademlia-like index of neighbor nodes
是一个table但不是哈希table
同样有n个buckets
将网络部分抽象成一个名为transport的接口。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d2TmC6LV-1667273896916)(/tfl/pictures/202210/tapd_47654106_1666333931_51.png)]
每个节点存到哪个bucket:
距离=len-cpl,距离决定了bucket的index,距离小的在0个桶,距离越远,index越大
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OjcEAr4S-1667273896918)(/tfl/pictures/202210/tapd_47654106_1666942953_37.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xHvP1u25-1667273896918)(/tfl/pictures/202210/tapd_47654106_1666942970_74.png)]

本地节点查询

查询节点函数findnodeByID
会返回所有buckets中所有entries节点。
(没有libp2p那种计算距离每次找最近的)

bucket

type bucket struct {
   entries      []*node // live entries, sorted by time of last contact
   replacements []*node // recently seen nodes to be used if revalidation fails
   ips          netutil.DistinctNetSet
}

entries存储节点,每次顺序添加,并记录节点的添加时间。
add节点时,如果entries的长度超过bucketSize,则写入replacements,(不记录写入时间)

节点验证

默认10秒验证一次,每次随机选择一个bucket验证entries中的最后一个节点。只验证entries不验证replacements。
验证方式就是ping/pong
验证成功则移动到队首,且livenessChecks++。验证失败则从replacements中选一个代替这个验证失败的节点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-py8DqvyZ-1667273896918)(/tfl/pictures/202210/tapd_47654106_1666593649_3.png)]

lookup(即discovery)

doRefresh函数包含了向其他节点查询的功能lookupRandom
每次随机选择3个节点,3是写死的,默认30分钟执行一次。刚启动时会执行一次。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wmIWdbgU-1667273896919)(/tfl/pictures/202210/tapd_47654106_1666593515_78.png)]

每次执行时new一个lookup,并调用run()方法,lookup方法优先从table里找到邻居,这个找邻居的函数就是findnodeByID,然后再向这些邻居发发送find请求,邻居们再调用自己的findnodeByID把结果返回。

入口(如何启动这一切的)

udpv4合udpv5有个new函数,new一个udpv4实例的时候再new一个tab并启动这个tab不断更新。
提供一个函数Resolve来返回查询到的节点。

libp2p的k桶

本文内容源自下面源码版本
go-libp2p-kbucket@v0.4.7
#高频名词解释
cpl:common prefix length两个ID的公共前缀长度。

功能简介

go-libp2p-kbucket实际是实现了一个路由表,他的结构体命名也是RoutingTable
除了正常增删节点之外,主要功能是查找距离一个节点最近的n个节点的peerID
NearestPeers(id ID, count int) []peer.ID
简单来讲是靠计算他们的前缀来实现的。

bucket

bucket是k桶的基础组成,一个k桶包含n个bucket,每个bucket通过一个链表*list.List来维护节点。
bucket提供最基本从增删改查之外,还有一个计算最大公共前缀的函数,
该函数会遍历list中的每个节点,然后找到公共前缀最大的结果并返回。

RoutRoutingTable 路由表(哈希表)

函数NewRoutingTable会初始化一个路由表,强制需要一个localID,并生成一个bucket放入buckets

add节点

add一个节点时,会计算该节点和localID的公共长度,该长度和len(buckets) 取最小值,该最小值就是bucket的index(bucketID)。
用index从buckets拿出对应的bucket,先判断节点是否已经存在,存在则返回false。
如果这个bucket的长度< rt.bucketsize,则正常插入该bucket,并返回true。
如果这是最后一个bucket(也就是最后一个bucket也满了),则扩展bucket个数,然后重新执行获得index,如果bucket的长度< rt.bucketsize则正常插入该bucket,并返回true。
如果这不是最后一个bucket,会从当前bucket踢出一个replaceable==true的节点然后查询这个新节点。
如果没有能replace的,则返回false,插入失败。

获得最近的节点NearestPeers

先计算target和local的cpl,这个cpl作为index,将对应的bucket的全部节点写入结果数组。
如果数量不够,从cpl后面的bucket开始写入结果集。
如果数量还不够,从cpl前面的bucket依次写入结果集。
然后结果集排序并返回。

go-libp2p-kad-dht

IpfsDHT这个结构体实现了很多interface
文本只关心PeerRouting

// 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)
}

FindPeer函数会调用dht的runLookupWithFollowup去执行一个lookup操作,
runLookupWithFollowup的参数里有一个回调函数queryFn

具体流程是:
dht.host.Network().Connectedness(id)里找是否已经包含,有就直接返回,没有会启动一个runLookupWithFollowup
runLookupWithFollowup先从自己的routingTable里找到最近的节点(dht.routingTable.NearestPeers
如果结果为空则返回失败。
不为空则run一个query,这个query的结果就是最终结果。这个query包含了哈希表全部的最近节点,对每个节点依次遍历。
遍历的过程是先q.dht.dialPeer,失败则返回,成功则调用回调函数queryFn,通过queryFn拿到新的节点就写入自己的哈希表。无论失败返回还是成功拿到新节点,都会把结果写入一个chan,run出来的query函数里创建的这个chan并一直等待读这个chan,读到则这个节点状态为PeerQueried且将这个节点加入结果集:q.queryPeers.TryAdd(p, up.cause)。最后返回就是读这个结果集q.queryPeers.GetState(p)

queryFn里面的逻辑是
发送一个类型为Message_FIND_NODE的消息
对方收到消息会调用函数 handleFindPeer,该函数会执行dht.routingTable.NearestPeers拿到最近的节点,通过pstore.PeerInfos拿到这些节点的地址并封装成返回值。返回值最终写入一个addrsCh ,从addrsCh中收到的地址写入数组 newAddrs
FullRTdht.h.Connect这些地址
IpfsDHT结构体会返回这些节点的信息