以Kademlia为例实战DHT（三）

路由表

DHT的路由表存储了远程节点的位置信息。这个路由表是不断更新维护的。其routingTable的结构体如下：

type routingTable struct {
    *nTree
    addresses map[string]*remoteNode    // 地址是UDP地址的map  host:port格式表示一堆remoteNodes。
    // 之所以使用字符串，是因为不可能使用net.UDPAddr创建映射。
    nodeId string                   // 节点自己本身的ID
    boundaryNode *remoteNode        // 跟NodeID距离最远的路由表中的某个节点
    proximity int                   // NodeID跟boundaryNode之间的距离有多少个前缀位
}

围绕路由表存储的有如下方法：

• func newRoutingTable() *routingTable
  • 构建一个路由表，二叉树是空的，路由表中的地址map是空的，自己的NodeId是空的，最远节点是空的，最大前缀位设置为0。
• func (r *routingTable) hostPortToNode(hostPort string,port string) (node *remoteNode,addr string,existed bool,err error)
  • 根据指定的hostPort，port在路由表中找到一个节点，返回这个远程节点，其地址，并且是否存在。
• func (r *routingTable) length() int
  • 统计一下节点路由表中有多少联系的节点。
• func (r *routingTable) reachableNodes() (tbl map[string][]byte)
  • 查询节点路由表中有哪些节点是可触达的，返回一个map。
• func (r *routingTable) numNodes() int
  • 统计一下节点路由表中有多少联系的节点。
• func isValidAddr(addr string) bool
  • 判断一个节点的地址是否合法。
• func (r *routingTable) update(node *remoteNode,proto string) error
  • 输入远程节点，proto作为参数，更新节点的现有路由条目。
• func (r *routingTable) insert(node *remoteNode,proto string) error
  • 将所提供的节点插入到路由表中，如果另一个节点已经存在这个地址，则会出现错误。
• func (r *routingTable) getOrCreateNode(id string,hostPort string,proto string) (node *remoteNode,err error)
  • 创建或返回一个节点。
  • 第一步是根据hostPort和proto直接到路由表中去找。
  • 然后对查找出来的结果进行验证，如果已经存在就直接返回。
  • 如果不存在，就构建一个remoteNode，将新的远程节点插入并返回。
• func (r *routingTable) kill(n *remoteNode,p *peerStore)
  • 从路由表中kill掉一个远程节点，并从peerStore中删除掉这个远程节点。
• func (r *routingTable) resetNeighborhoodBoundary()
  • 如果出现kill远程节点，添加新的远程节点，就需要对最远节点进行重新设置。
  • 因为路由表中，距离最远的节点放在neighbors的最上层，所以r.boundaryNode = neighbors[len(neighbors)-1]。
  • 而NodeId和boundaryNode的前缀位计算是commonBits，r.proximity = commonBits(r.nodeId,r.boundaryNode.id)。
• func (r *routingTable) cleanup(cleanupPeriod time.Duration,p peerStore) (needPing []remoteNode)
  • 对路由表进行一次清理，如果需要ping的远程节点就放到needPing中。
  • 如果判断需不需要ping呢？
  • 对路由表的地址进行遍历，如果远程节点是可触达的，如果pendingQueries还没有元素，直接就需要ping。
  • 如果远程节点上次响应的时间有点旧了，还是kill掉好了。
  • 如果最近才看到，响应时间比较新，就不需要ping，直接跳过好了。
• func (r *routingTable) neighborhoodUpkeep(n *remoteNode,proto string,p *peerStore)
  • 如果远程节点比路由表中已有的8个邻近节点还要更近，这个方法就通过替换那个最不近的节点（boundaryNode），n.id来更新路由表。
  • 如果路由表的boundaryNode为空，直接添加邻近节点。
  • 如果路由表的长度小于kNodes，直接添加邻近节点。
  • 计算nodeId和远程节点id的前缀位cmp，cmp大于路由表的前缀位proximity，添加邻近节点并删除原有路由表中最远节点。
• func (r *routingTable) addNewNeighbor(n *remoteNode, displaceBoundary bool, proto string, p *peerStore)
  • 添加远程节点，同时考虑是否需要替换掉路由表中的最远节点。
  • 如果不需要kill掉最远节点，就可以将添加进去的节点进行重设，重新选出最远的节点。
• func pingSlowly(pingRequest chan remoteNode,needPing []remoteNode,cleanupPeriod time.Duration,stop chan bool)
  • 作用是在整个cleanupPeriod期间，不断ping到远程节点，分发ping信号，避免网络流量的爆发。