P2P 中 DHT 网络介绍

kiki
Jan 1, 0001 blog

分布式哈希表 DHT

  • 分布式哈希表(DHT， Distributed Hash Table)，一种分布式存储方法，一类可由键值来唯一标识的信息按照某种约定/协议被分散地存储在多个节点上
  • 不需要服务器，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现正哥 DHT 网络的寻址和存储
  • 可以有效地避免“中央集权式”的服务器(如 tracker)的单一故障而带来整个网络瘫痪
  • 实现 DHT 的算法常用的有 Chord，Pastry，Kademlia
    • 最直接的目标是以最快的速度定位到期望的节点
    • 计算的是某种逻辑上的距离，因为地理距离的计算很复杂

Kademlia

Kademlia: A Peer-to-Peer Information System Based on the XOR Metric 论文阅读

  • 特点
    • 最小化节点发送的配置消息：可以通过 key lookup 流程展开配置信息
    • 节点通过低延迟的路径来路由查询
    • KAD 使用并行、异步查询来避免离线节点的超时

异或度量

  • 每个 KAD 节点有一个 160 比特长的 ID，节点 ID 是随机值
    • 节点发送的每个消息包含自身的节点 ID，允许接收者记录发送者的存在性
  • 键(Key)也是 160 比特的标识符
  • Kademlia 采用简单的异或计算衡量两节点之间的距离，与地理距离无关：d(x,y)=xor(x,y)
  • 具备几何公式的多数特征
    • 节点和本身的异或距离是 0：d(x,x)=0
    • 异或距离是对称的：d(x,y)=d(y,x)
    • 异或距离符合三角不等式：给定三个顶点 A B C，若 AC 之间的异或距离最大，则 AC 之间的异或必小于等于 AB 异或距离和 BC 异或距离之和
    • d(x,y)+d(y,z)>=d(x,z)
    • 证明：xor(d(x,y), d(y,z))=d(x,z),且 a+b>=xor(a,b)
    • 对于给定的一个距离，距离 A 只存在唯一的一个节点 B，也即单向性，在查找路径上也是单向的，这个和地理距离不同
    • 已知 x 和 dis, 求 y 使得 dis=xor(x,y)：xor(dis,x)=xor(xor(x,y),x)=y

节点状态

  • KAD 节点存储其他节点的信息来路由请求消息
  • 每个节点保存一张三元组<IP_addr, UDP_port, Node_ID>链表，记录距离自身2^i到2^(i+1)的节点，称之为k-bucket(k 桶)
    • k-bucket 存储策略是least-recently seen eviction：最少最近访问的节点放在链表头，最多最近访问的节点放在链表尾
    • 关于 k 值
      • 对于较小的 i，k-bucket 可能为空，即不存在合适的距离较近的节点
      • 对于较大的 i，链表的长度可以增加到 k
      • k 是一个系统范围的参数，是指任意 k 个节点在一个小时内不会全部掉线
    • 关于 k-bucket 的更新
      • 当一个 KAD 节点收到其他节点的消息（请求或者回复）时，节点会更新发送者节点 ID 对应的 k-bucket 信息
      • 如果发送节点已经存在 k-bucket，接收者将其移到链表尾部
      • 如果发送节点不在 k-bucket
      • k-bucket 的元素数目小于 k，接收者将发送节点插入链表尾部
      • k-bucket 已满，接收者将会 ping 最近最少访问的节点决定如何做
        • 如果最近最少访问的节点没有回复，接收者将该节点从 k-bucket 移除，并将之前的发送者节点插入链表尾部
        • 如果收到最近最少访问的节点的回复，接收者将该节点移到链表尾部，并丢弃之前的发送者节点的信息
    • k-bucket 不会将 live 的节点从链表移除
      • 在线时间长的节点更值得信任，即下一段时间保持在线的可能性比新访问的节点更大
      • k-bucket 在某种程度上可以抵制 DOS 攻击，因为节点的路由状态不会被新访问的节点刷新，当旧的节点没有离开系统时，k-bucket 不会插入新的节点

KAD 协议

  • KAD 协议包括四个 RPC
    • ping：探测一个节点是否在线
    • store：指导节点存储一个<key,value>对便于之后的检索
    • find_node：取一个 160 比特的 ID 作为参数，发送给 k-bucket 的节点，接收者返回已知的距离目标 ID 最近的节点的三元组<IP_addr, UDP_port, Node_ID>
    • 三元组可以来自一个 k-bucket
    • 当最近的 k-bucket 不满时，三元组来自多个 k-bucket
    • RPC 接收者必须返回 k 个元素，当接收者所有的 k-bucket 加起来不到 k 个 节点，则返回它知道的所有节点
    • find_value：类似于 find_node，当 RPC 接收者收到一个关于 key 的 store RPC，则返回存储的 value
    • 接收者若存储了 key 对应的 value，则返回 value
    • 否则返回距离 key 最近的 k 个节点的信息
  • node lookup：每个 KAD 的参与者执行的一个最重要的操作就是对于给定的节点 ID，定位 k 个最近的节点
    • KAD 使用递归的算法查找节点
    • 查找的发起者从它最近的非空 k-bucket 中选择 α 个节点(当 bucket 中节点少于 α，则选择已知的最近的 α 个节点)
      • α 是系统范围的并发参数
      • 假设发起者是节点 x，x 先计算距离 d=xor(x, ID)
      • x 从第 log2(d)个 k-bucket 中选择 α 个节点，不足 α 个节点时，从附近多个 bucket 中选择距离最接近 d 的一共 α 个节点
    • 查找的发起者发送并行、异步的 find_node RPC 到这 α 个节点
    • 接收者如果发现自己就是 ID，则回答自己是最接近的，否则计算自己和 ID 的距离，从中自己的 k-bucket 中选择 α 个节点返回
    • 发起者收到接收者回复的 k 个节点，再选择未发送过请求的 α 个节点，再次发送 find_node 请求到这 α 个节点
      • 没有回复的节点直接被移除
    • 当所有的 find_node 不再返回比已知的节点更近的节点，查找的发起者发送重新发送 find_node 给所有最近且未查询过的 k 个节点
    • 当发起者查询并且收到 k 个最近的节点的回复，查询终止
  • 存储<key,value>对
    • 参与者定位距离 key 最近的 k 个节点，并发送 store RPC
    • 每个节点间隔一段时间(如 24h)重新发布<key,value>对来保持 alive
  • 查找一个<key,value>对
    • 一个节点先执行 lookup 找到 k 个距离 key 最近的节点 ID
    • 查找 value 使用 find_value RPC
    • 当任意节点返回此 value 时，此流程终止
    • 当查询成功时，发送请求的节点会存储<key,value>对到已知的距离最近且未返回 value 的节点
    • 由于拓扑的无方向性，查询相同的 key 可能会在找到最近的节点之前找到缓存的条目
    • 为了避免对常查找的 key 的”over-caching”，对于所有节点数据库的<key,value>对设置过期时间，过期时间与当前节点和距离 key 最近的节点之间的节点数成指数反比关系，即越远的节点过期时间越短
    • 数字可以通过当前节点的 bucket 结构推算出来
  • 通常通过请求在节点之间的转发更新 bucket。为了避免某些节点范围不被查询，每个在一小时之内未执行查询节点的节点会更新其所有的 bucket。
    • 刷新意味着从 bucket 中随机选择一个 ID，并且对该 ID 执行一次节点查询
  • 新加入的节点 u 更新自己的 k-bucket
    • u 选择一个已经加入网络的节点 w 到自己的对应 k-bucket
    • u 对自己的节点 ID 执行一次节点查询
    • 最终，u 更新自己所有的 k-bucket，同时插入自身到其他的一些节点的 k-bucket

路由表

  • KAD 的路由表是一个二叉树，叶子节点是 k-bucket
    • 每个 k-bucket 包含和 ID 有一些共同前缀的节点，前缀是 k-bucket 在二叉树中的位置
    • 每个 k-bucket 覆盖了 ID 空间的某个范围，所有的 k-bucket 刚好覆盖了整个 160 比特的 ID 空间
  • 路由树的节点根据需要动态分布
    • 一开始，一个节点 u 的路由表有一个节点，一个 k-bucket 覆盖整个 ID 空间
    • 当 u 得到新的联系信息，尝试插入到适合的 k-bucket
    • 当该 bucket 不满，则插入新的联系信息
    • 否则，如果 k-bucket 范围包含节点自身，则将 bucket 分为两个 bucket，再尝试插入适合的 bucket
    • 如果不同范围的 k-bucket 已满，则丢弃新的联系信息

有效的 key re-publishing

  • 之前缓存了<key,value>对的节点可能会掉线，新加入的节点可能比缓存了<key,value>的节点距离 key 更近，因此持有<key,value>的节点需要重复发布
  • KAD 每隔一个小时会重复发布所有的<key,value>对，以避免缓存过的节点掉线
    • re-publishing 过程的优化：
    • 每个收到 store RPC 的节点会假定消息已经发送到另外 k-1 个最近的节点，所以接收者不会发布这个消息。因此，当 re-publication 的间隔没有完全同步，每个小时，只有一个节点会 republish 指定的<key,value>对
    • 在 republish 之前避免查找节点。这样，一个节点对所有 k-bucket 的刷新可以分摊到许多的节点的重复发布过程中
    • 每个节点只会在自己的 ID 比其他节点距离 key 更近的情况下发布 store RPC

优化

  • 采用 LRU 策略维持 k-bucket 的联系信息时，为了避免发送过多的 ping 请求阻塞网络， KAD 增加一个替换缓存(Replacement cache)保存新得到的联系信息，当持有有用的信息才会发送 ping 信息给链表中的节点，如果节点没有回复，则从链表中删除该节点，并从替换缓存中找一个最近最多访问的节点插入链表头
  • 因为 KAD 使用 UDP，当网络阻塞的时候，网卡会丢掉一些包。 KAD 会锁住没有回复的联系信息，并不会再给这些联系节点发送 RPC
  • 当一个联系节点连续 5 次没有回复 RPC，其他节点会认为此联系节点是 stale（过时，失去时效），当节点的 k-bucket 不满或者替换缓存为空的时候， KAD 不会从 k-bucket 移除这个联系节点，而是将其置为 stale。这样保证了一个节点自身的网络连接暂时断掉的时候，不会将自身所有的 k-bucket 置为无效。（什么时候再置为有效呢？？？）
  • 减少查找节点的跳跃数：增加路由表的 size，即每次根据 b 个比特位来查找临近节点发送请求。但是这样会增加维护难度

DHT 中 KAD 的应用

  • 每个节点的 ID 和种子文件的 info_hash 采用 sha-1 算法，节点和种子(<key,value>)的距离就是节点 ID 和 info_hash 的异或距离
  • 每个节点按照距离自己的异或远近将所有的节点划分成 160 棵子树，表示其他节点 ID 和自身 ID 的共同前缀的比特数的范围 0-159
    • 每个节点的各个 k-bucket 记录了每个子树中的 k 个节点信息
  • 每个新加入 DHT 网络的节点更新路由表的步骤
    • 如本节点曾经启动过，则从保存的“路由表”文件中直接读取然后刷新“路由表”
    • 如果节点第一次启动，且节点有“超级节点”，则通过这些“超级节点”来间接地生成自己的“路由表”
    • 如果节点第一次启动且没有“超级节点”，则路由表生成过程需要推迟到 download 文件过程。节点从获取到的种子文件提取 nodes 字段，通过这些 nodes 字段中的节点来间接生成自己的路由表
    • 该 nodes 字段是做种子（支持 DHt 网络的种子）的时候生成的
    • 一般 nodes 字段设置为原始种子的 ip 和 port，或者是做种子的节点离该种子的 info-hash 最近的 k 个节点
    • 动态建立过程：节点经过初始化后，在下载、上传或无任务过程中收到任何节点发送的消息，都会检查当前的“路由表”并尝试按照一定的规则去建立/刷新路由表
  • tracker：对每一个分享文件（种子）维护一个 peers 列表，告诉需要下载的询问者 client
  • DHT 查找类型包括
    • find_nodes：是为了建立路由表。节点 x 查找节点 y 的过程
    • x 从 xor(x,y) 对应的本地 k-bucket 中得到 k 个比较近的节点
    • x 向上面找到的 k 个节点发送消息查找节点 y
    • 收到请求的节点从自己的 k-bucket 中找到更近的 k 个节点返回给 x
    • x 从收到的回复中选择 k 个最近的节点再次发送请求
    • 当 x 收到的回复的节点中没有更近的节点停止查找
      • x 最后得到 k 个距离 y 最近的节点
      • 在此过程中，x 会尝试将得到的节点插到自己的路由表中
    • get_peers：与 find_nodes 类似，但是查找的参数不是节点 ID，而是 info_hash
    • 在查找过程中，收到任意<info_hash, peers_list>回复就停止查找
    • 得到 peers_list之后，节点会试图给每个 peer 主动发起 TCP 的连接，之后开始下载，同时会把自己的 peer 信息发送给 k 个距离自己最近的节点存储 <info_hash, peers_list>信息
      • k 个节点保存该信息 24 小时，期间没有收到 x 的更新消息则信息失效
p2p

相关