以太坊

对应代码位置
github.com\ethereum\go-ethereum\p2p\discover

概述

以太坊实现了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。
FullRT会dht.h.Connect这些地址
IpfsDHT结构体会返回这些节点的信息