聊聊分布式散列表（DHT）的原理——以 Kademlia（Kad） 和 Chord 为例

★引子——为啥要聊这个话题？

　　这是一篇比较深入地谈技术的博文，而且还牵涉到一点算法（俺很久没有写这种类型的博文啦）。
　　今天发这篇，主要是因为如下几点：
　　1
　　在“对抗 GFW、对抗政府审查”的过程中，【彻底无中心】的分布式系统是非常有用滴！
　　（关于这点，请参见前几年的博文：《“对抗专制、捍卫自由”的 N 种技术力量》）
　　2
　　DHT 是这类分布式系统的【关键基础设施】，俺希望追求自由的网民能多了解这方面的知识
　　3
　　俺也希望有更多程序员能参与这方面的【开源社区】。
　　在对抗政府审查的时候，商业公司是靠不住滴；只能指望开源社区。
　　4
　　虽然 GFW 已经在封杀 BT sync／Resilio Sync；但是，启用了 DHT 功能的 BTsync（必须是老版本），在墙内依然是【免翻墙】可用，让俺很受鼓舞 :)
　　（感兴趣的同学可以参见上个月的博文：《聊聊 GFW 如何封杀 Resilio Sync（BTSync）？以及如何【免翻墙】继续使用？》）

★预备知识

　　（如果你自认为是一个熟练的程序员，请直接略过“预备知识”这个章节，看下一章节）

◇什么是“散列/哈希（hash）”？

　　（注：在本文中，凡是提及“散列”或“哈希”或“hash”，均表示相同含义）
　　关于 hash 的概念，俺曾经写过一篇相关的扫盲教程《扫盲文件完整性校验——关于散列值和数字签名》，不了解此概念的同学，可以先看看。
　　老实说，如果你还没有搞明白 hash 的概念，就不要浪费时间看本文的后续部分啦。

◇什么是“散列表/哈希表（hash table）”？

　　“散列表/哈希表”是用来存储“键值对”的一种容器。“键值对”洋文称之为“key/value pairs”，简称“K/V”。有了“散列表”，你可以很方便快速地通过 key 来获得 value。
　　举个例子：
　　手机通讯簿可以通俗理解成一个“散列表”。里面的每一条记录都包含“姓名”和“电话号码”。“姓名”相当于“键值对”中的 key，电话号码相当于 value。你可以通过姓名方便地查找出电话号码。

◇如何实现散列表？

　　（考虑到本文的完整性，【简单介绍】一下散列表的实现）
　　在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。
　　“桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。
　　下面这张图是从维基百科上剽窃来的。它展示了散列表的【查找】原理。当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散列值对 N（桶数）进行“取模”运算（除法求余数），就可以算出对应的桶编号。
　　（注：取模运算是最常用的做法，但不是唯一的做法）


（使用散列表存储电话簿的示意图，剽窃自维基百科）

◇什么是“散列表”的【碰撞/冲突】（Collision）？

　　在俺那篇扫盲教程中，已经介绍了“散列碰撞”（也称为“散列冲突”）的概念。
　　当两个不同的 key 进行哈希计算却得到【相同的散列值】，就是所谓的【散列函数碰撞】。一旦出现这种情况，这两个 key 对应的两个键值对就会被存储在【同一个】桶（bucket）里面。
　　另一种情况是：虽然计算出来的散列值【不同】，但经过“取模运算”之后却得到【相同】的桶编号。这时候也会出现：两个键值对存储在一个桶里面。


（出现“散列碰撞”的示意图，剽窃自维基百科）
　　如果某个哈希表在存储数据时【完全没有碰撞】，那么每个桶里面都只有 0个 或 1个 键值对。查找起来就非常快。
　　反之，如果某个哈希表在存储数据时出现【严重碰撞】，就会导致某些桶里面存储了一大坨的键值对。将来查找 key 的时候，如果定位到的是这种“大桶”，就需要在这个桶里面逐一比对 key 是否相同——查找效率就会变得很差。

◇“散列表”有哪些优点？

　　主要优点是：（当数据量很大时）散列表可以提供快速且稳定的查找速度。
　　当然，这里有个前提就是：散列函数要【足够好】——
1、计算出的散列值要足够离散（从而使得不同的键值对可以比较【均匀】地分配到各个桶里面）
2、要尽可能降低碰撞（碰撞会降低性能）
　　另一个前提是：桶的数量也有一定的讲究——
1、桶数要足够大。否则的话，【必定会】导致某些桶里面的键值对太多（这点很明显，没想明白的同学，可参见“抽屉原理”）
2、（如果用常见的“取模”映射到桶）桶的总数最好是【质数/素数】（这个不解释，爱思考的同学自己想一下）

★分布式散列表（DHT）概述

◇啥是 DHT？

　　“分布式散列表”也称为“分布式哈希表”，洋文是“distributed hash table”，简称 DHT。
　　“分布式散列表”在概念上类似与传统的“散列表”，差异在于——
“传统的散列表”主要是用于单机上的某个软件中；
“分布式散列表”主要是用于分布式系统（此时，分布式系统的节点可以通俗理解为散列表中的 bucket）

　　“分布式散列表”主要是用来存储大量的（甚至是海量的）数据。在实际使用场景中，直接对所存储的“每一个业务数据”计算散列值，然后用散列值作为 key，业务数据本身是 value。


（分布式散列表的示意图，此图剽窃自维基百科）
　　（为了偷懒，本文以下部分均使用 DHT 来表示“分布式散列表”）

◇为啥会出现 DHT？

　　在 P2P 文件共享的发展史上，出现过3种不同的技术路线（三代）。

　　第1代
　　采用【中央服务器】的模式——每个节点都需要先连接到中央服务器，然后才能查找到自己想要的文件在哪里。
　　这种技术的最大缺点是——中央服务器成为整个 P2P 网络的【单点故障】。
　　（关于“单点故障”这个概念，可以看另一篇介绍：《聊聊“单点故障”——关于“德国空难”和“李光耀”的随想》）
　　这类 p2p 的典型代表是 Napster。

　　第2代
　　采用【广播】的模式——要找文件的时候，每个节点都向自己相连的【所有节点】进行询问；被询问的节点如果不知道这个文件在哪里，就再次进行“广播”......如此往复，直至找到所需文件。
　　这种技术的最大缺点是——会引发“广播风暴”并严重占用网络带宽，也会严重消耗节点的系统资源。即使在协议层面通过设置 TTL（time to live），限制查询过程只递归 N 轮，依然【无法】彻底解决此弊端。
　　因为这种手法太吓人，获得“Query Flooding”的绰号。下面放一张示意图。


（示意图：第2代 P2P 的 Query Flooding）
　　这类 p2p 的典型代表是 Gnutella 的早期版本。

　　第3代
　　这一代采用的技术就是今天要聊的 DHT。
　　通过 DHT 这个玩意儿，不但避免了第一代技术的【单点故障】，也避免了第二代技术的【广播风暴】。

◇DHT 有哪些应用场景？

　　DHT 最早用于 P2P 文件共享和文件下载（比如：BT、电驴、电骡），之后也被广泛用于某些分布式系统中，比如：

分布式文件系统
分布式缓存
暗网（比如：I2P、Freenet）
无中心的聊天工具/IM（比如：TOX）
无中心的微博客/microblogging（比如：Twister）
无中心的社交网络/SNS

　　正是因为【无中心】的分布式系统普遍使用 DHT，所以本文开头称之为：分布式系统的【基础设施】。

★分布式散列表（DHT）的难点

◇“无中心”导致的难点

　　前面提到了 DHT 的诞生，是为了解决前面两代 P2P 技术的缺陷。其中一个缺陷是“中央服务器”导致的【单点故障】。
　　因此 DHT 就【不能】再依靠中央服务器。而没有了中央服务器，就需要提供一系列机制来实现节点之间的通讯。

◇“海量数据”导致的难点

　　DHT 的很多使用场景是为了承载海量数据（PB 或更高级别）。
　　由于数据是海量的，每个节点只能存储（整个系统的）一小部分数据。需要把数据【均匀分摊】到每个节点。

◇“节点动态变化”导致的难点

　　很多 DHT 的使用场景是在公网（互联网）上，参与 DHT 的节点（主机）会出现【频繁变化】——每时每刻都有新的节点上线，也会有旧的节点下线。在这种情况下，需要确保数据依然是【均匀分摊】到所有节点。

　　（俺特别强调一下：传统的散列表在这种情况下的困难）
　　前面提到：传统散列表所含的【桶数】是固定不变滴。为啥捏？
　　因为传统散列表在针对 key 计算出散列值之后，需要用“散列值”和“桶数”进行某种运算（比如：取模运算），从而得到桶的编号。
　　如果桶的数量出现变化，就会影响到上述“取模运算”的结果，然后导致数据错乱。

◇“高效查询”导致的难点

　　对于节点数很多的分布式系统，如何快速定位节点，同时又不消耗太多网络资源，这也是一个挑战。
　　比如前面提到第二代 P2P 技术，在查找所需文件时会导致【广播风暴】。这就成为其致命弱点。
　　DHT 必须有更高效的查找机制。而且这种查找机制要能适应“节点动态变化”这个特点。

★分布式散列表（DHT）如何解决上述难点？

　　DHT 采用如下一些机制来解决上述问题，并满足分布式系统比较苛刻的需求。

◇“散列算法”的选择

　　前面提到：DHT 通常是直接拿业务数据的散列值作为 key，业务数据本身作为 value。
　　考虑到 DHT 需要承载的数据量通常比较大，散列函数产生的“散列值范围”（keyspace）要足够大，以防止太多的碰撞。更进一步，如果 keyspace【大到一定程度】，使得“随机碰撞”的概率小到忽略不计，就有助于简化 DHT 的系统设计。
　　通常的 DHT 都会采用大于等于 128 比特的散列值（2¹²⁸ 比 “地球上所有电子文档总数” 还要大【很多数量级】）。

◇同构的“node ID”与“data key”

　　DHT 属于分布式系统的一种。既然是分布式系统，意味着存在【多个】节点（电脑主机）。在设计分布式系统的时候，一种常见的做法是：给每一个节点（node）分配【唯一的】ID。有了这个节点 ID（node ID），在系统设计上的好处是——对分布式系统所依赖的物理网络的【解耦】。
　　很多 DHT 的设计会让“node ID”采用跟“data key”【同构】的散列值。这么搞的好处是：
1、当散列值空间足够大的时候，随机碰撞忽略不计，因此也就确保了 node ID 的唯一性
2、可以简化系统设计——比如简化路由算法（下面会提及）

◇“拓扑结构”的设计

　　作为分布式系统，DHT 必然要定义某种拓扑结构；有了拓扑结构，自然就要设计某种“路由算法”。
　　如果某个 DHT 采用前面所说的——“node ID”与“data key”【同构】——那么很自然的就会引入“Key-based routing”。
　　请注意，这【不是】某个具体的路由算法，而只是某种【风格】。采用这种风格来设计路由机制，好处是：key 本身已经提供了足够多的路由信息。

　　当某个分布式系统具有自己的拓扑结构，它本身成为一个“覆盖网络”（洋文叫“Overlay Network”）。所谓的“覆盖网络”，通俗地说就是“网络之上的网络”。对于大部分 DHT 而言，它们是基于互联网之上的“覆盖网络”，它们的数据通讯是依赖下层的互联网来实现的。
　　前面提到的“node ID”，其【解耦】的作用就体现在——分布式系统在设计拓扑结构和路由算法时，只需要考虑 node ID，而不用考虑其下层网络的属性（比如：协议类型、IP 地址、端口号）。

◇“路由算法”的权衡

　　由于 DHT 中的节点数可能非常多（比如：几十万、几百万），而且这些节点是动态变化的。因此就【不可能】让每一个节点都记录所有其它节点的信息。实际情况是：每个节点通常只知道少数一些节点的信息。
　　这时候就需要设计某种路由算法，尽可能利用已知的节点来转发数据。“路由算法”这玩意儿很重要，直接决定了 DHT 的速度和资源消耗。
　　在确定了路由算法之后，还需要做一个两难的权衡——“路由表的大小”。
路由表越大，可以实现越短（跳数越少）的路由；缺点是：（由于节点动态变化）路由表的维护成本也就越高。
路由表数越小，其维护成本越小；缺点是：路由就会变长（跳数变多）。

◇距离算法

　　某些 DHT 系统还会定义一种“距离算法”，用来计算：“节点之间的距离”、“数据之间的距离”、“节点与数据的距离”。
　　请注意：此处所说的“距离”属于【逻辑层面】，对应的是 DHT 自己的拓扑结构；它与地理位置【无关】，也与互联网的拓扑结构【无关】。
　　写到这里，某些聪明的读者就会明白：为啥前面要强调——“node ID”与“data key”【同构】。当这两者【同构】，就可以使用【同一种“距离算法”】；反之，如果这两者不同构，多半要引入几种不同的“距离算法”。

◇数据定位

　　有了前面这一大砣东西作为铺垫，现在就可以来谈谈“数据定位”啦。对 DHT 而言，这是最关键的东东。
　　DHT 与传统的散列表在【功能】上是类似的。说白了，他们最关键的功能只有两个——“保存数据”和“获取数据”。如果用 C 语言来表示的话，函数原型大致如下：

void put(KEY k, VALUE v);  // 保存“键值对”
VALUE get(KEY k);  // 根据“键”获取“值”

　　保存数据
　　（以下只是大致原理，具体的协议实现可能会有差异）
　　当某个节点得到了新加入的数据（K/V），它会先计算自己与新数据的 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。
　　如果计算下来，自己与 key 的距离最小，那么这个数据就保持在自己这里。
　　否则的话，把这个数据转发给距离最小的节点。
　　收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

　　获取数据
　　（以下只是大致原理，具体的协议实现可能会有差异）
　　当某个节点接收到查询数据的请求（key），它会先计算自己与 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。
　　如果计算下来，自己与 key 的距离最小，那么就在自己这里找有没有 key 对应的 value。有的话就返回 value，没有的话就报错。
　　否则的话，把这个数据转发给距离最小的节点。
　　收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

★Chord 协议简介

◇概述

　　Chord 诞生于2001年。第一批 DHT 协议都是在那年涌现的，另外几个是：CAN、Tapestry、Pastry。
　　俺之所以选取 Chord 来介绍，主要是因为 Chord 的原理比较简单（概念好理解），而且相关的资料也很多。

　　（请允许俺稍微跑题，聊一下 IT 八卦）
　　Chord 是 MIT 的几个技术牛人一起搞出来的，这几个牛人中包括世界级的黑客：罗伯特·莫里斯（Robert Morris）。
　　此人以“莫里斯蠕虫”而享誉信息安全界。这是 IT 史上【第一个】蠕虫（注：蠕虫可以利用网络【实时】传播），这个蠕虫对当时（1988年）的互联网造成毁灭性打击（一天之内，约十分之一的互联网主机中招并下线）。
　　他不仅是编程高手兼顶级黑客，而且是创业者兼投资人。他与同样大名鼎鼎的保罗·格雷汉姆（Paul Graham）以及 Trevor Blackwell，3人在1995年共同创立了 Viaweb，并在1998年把公司以5千万美元卖给 Yahoo。然后他们拿这笔钱创办了 Y Combinator（如今世界闻名的风投机构）。

◇拓扑结构——环形

　　要聊 Chord 的拓扑，必然要提到“Consistent Hashing”（译作：“一致散列”或“稳定散列”）。搞明白“一致散列”也就知道 Chord 的拓扑设计了。
　　提出“一致散列”这个概念主要是为了解决“节点动态变化”的难点（前面有提及）。为了解决这个难点，“一致散列”把散列值空间（keyspace）构成一个【环】。对于 m 比特的散列值，其范围是 [0, 2m-1]。你把这个区间头尾相接就变成一个环，其周长是 2m。然后对这个环规定了一个移动方向（比如顺时针）。
　　如果 node ID 和 data key 是同构的，那么这两者都可以映射到这个环上（对应于环上的某点）。


（示意图：环形的 keyspace）
　　假设有某个“节点A”，距离它最近的是“节点B”（以顺时针方向衡量距离）。那么称 B 是 A 的【继任】（successor），A 是 B 的【前任】（predecessor）。

　　数据隶属于【距离最小】的节点。以 m = 6 的环形空间为例：
数据区间 [5,8] 隶属于“节点8”
数据区间 [9,15] 隶属于“节点15”
......
数据区间 [59,4] 隶属于“节点4”（注：“6比特”的环形空间，63之后是0）


（示意图：“数据”与“节点”对应关系）
　　以上就是“一致性散列”的拓扑结构，同时也是 Chord 的拓扑结构。

◇路由机制

　　接下来简单说一下路由的玩法。

　　基本路由（简单遍历）
　　当收到请求（key），先看 key 是否在自己这里。如果在自己这里，就直接返回信息；否则就把 key 转发给自己的继任者。以此类推。
　　这种玩法的时间复杂度是：O(N)。对于一个节点数很多的 DHT 网络，这种做法显然【非常低效】。

　　高级路由（Finger Table）
　　由于“基本路由”非常低效，自然就引入更高级的玩法——基于“Finger Table”的路由。
　　“Finger Table”是一个列表，最多包含 m 项（m 就是散列值的比特数），每一项都是节点 ID。
　　假设当前节点的 ID 是 n，那么表中第 i 项的值是：successor( (n + 2i) mod 2m )
　　当收到请求（key），就到“Finger Table”中找到【最大的且不超过 key】的那一项，然后把 key 转发给这一项对应的节点。
　　有了“Finger Table”之后，时间复杂度可以优化为：O(log N)。


（示意图：Finger Table）

◇节点的加入

　　1
　　任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
　　2
　　A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
　　3
　　A 通过跟 B 进行查询，找到自己这个 ID 在环上的接头人。也就是——找到自己这个 ID 对应的“继任”（假设叫 C）与“前任”（假设叫 D）
　　4
　　接下来，A 需要跟 C 和 D 进行一系列互动，使得自己成为 C 的前任，以及 D 的继任。
　　这个互动过程，大致类似于在双向链表当中插入元素（考虑到篇幅，此处省略 XXX 字）。

◇节点的【正常】退出

　　如果某个节点想要主动离开这个 DHT 网络，按照约定需要作一些善后的处理工作。比如说，通知自己的前任去更新其继任者......
　　这些善后处理，大致类似于：在双向链表中删除元素（考虑到篇幅，此处省略 XXX 字）。

◇节点的【异常】退出

　　作为一个分布式系统，任何节点都有可能意外下线（也就是说，来不及进行善后就挂掉了）
　　假设 节点A 的继任者【异常】下线了，那么 节点A 就抓瞎了。咋办捏？
　　为了保险起见，Chord 引入了一个“继任者候选列表”的概念。每个节点都用这个列表来包含：距离自己最近的 N 个节点的信息，顺序是【由近到远】。一旦自己的继任者下线了，就在列表中找到一个【距离最近且在线】的节点，作为新的继任者。然后 节点A 更新该列表，确保依然有 N 个候选。更新完“继任者候选列表”后，节点A 也会通知自己的前任，那么 A 的前任也就能更新自己的“继任者候选列表”。

◇引申阅读

　　Chord 就介绍到这里。想要进一步了解的同学，可以参考其原创论文：
《Chord——A Scalable Peer-to-peer Lookup Service for Internet Applications 》

★Kademlia（Kad）协议简介

　　（注：“Kademlia”这个词太长了；为了打字省力，以下都采用“Kad”这个简写）

◇概述

　　Kad 诞生于2002年，由纽约大学的两个牛人（Petar Maymounkov ＆ David Mazières）共同设计（他俩的论文，在本章节末尾附有链接）。
　　Kad 的原理比 Chord 稍微晦涩一些（涉及一点点数据结构的知识，如果你是程序猿，不用怕）。俺之所以选 Kad 来介绍，是因为——实际应用的 DHT 大部分都采用 Kad 及其变种。比如几种知名的 P2P 下载（BT、eDonkey/电驴、eMule/电骡）的 DHT 都是基于 Kad；知名的 I2P 暗网也依赖 Kad（说到 I2P，俺博客写过一篇扫盲教程，在“这里”）。

◇拓扑结构——二叉树

　　散列值的预处理
　　Kad 也采用了“node ID 与 data key 同构”的设计思路。然后 Kad 采用某种算法把 key 映射到一个二叉树，每一个 key 都是这个二叉树的【叶子】。
　　在映射之前，先做一下预处理。
　　1. 先把 key 以二进制形式表示。
　　2. 把每一个 key 缩短为它的【最短唯一前缀】。

　　为啥要搞“最短唯一前缀”？
　　Kad 使用 160比特 的散列算法（比如 SHA1），完整的 key 用二进制表示有 160 个数位（bit）。
　　首先，实际运行的 Kad 网络，即使有几百万个节点，相比 keyspace（2¹⁶⁰）也只是很小很小很小的一个子集。
　　其次，由于散列函数的特点，key 的分布是【高度随机】的。因此也是【高度离散】的——任何两个 key 都【不会】非常临近。
　　所以，使用“最短唯一前缀”来处理 key 的二进制形式，得到的结果就会很短（比特数远远小于 160）。

　　散列值的映射
　　完成上述的预处理后，接下来的映射规则是：
　　1. 先把 key 以二进制形式表示，然后从高位到低位依次处理。
　　2. 二进制的第 n 个 bit 就对应了二叉树的第 n 层
　　3. 如果该位是 1，进入左子树，是 0 则进入右子树（这只是人为约定，反过来处理也可以）
　　4. 全部数位都处理完后，这个 key 就对应了二叉树上的某个【叶子】


（示意图：“最短唯一前缀”映射到二叉树的叶子）

◇距离算法——异或（XOR）

　　接下来要聊的是 Kad【最精妙之处】——采用 XOR（按位异或操作）算法计算 key 之间的“距离”。
　　这种搞法使得它具备了类似于“几何距离”的某些特性（下面用 ⊕ 表示 XOR）

(A ⊕ B) == (B ⊕ A)	XOR 符合“交换律”，具备对称性。相比之下，Chord 的距离算法不对称
(A ⊕ A) == 0	反身性，自身距离为零
(A ⊕ B) > 0	【不同】的两个 key 之间的距离必大于零
(A ⊕ B) + (B ⊕ C) >= (A ⊕ C)	三角不等式

◇路由机制

　　二叉树的拆分
　　对每一个节点，都可以【按照自己的视角】对整个二叉树进行拆分。
　　拆分的规则是：先从根节点开始，把【不包含】自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。
　　Kad 默认的散列值空间是 m = 160（散列值有 160 bits），因此拆分出来的子树【最多】有 160 个（考虑到实际的节点数【远远小于】2160，子树的个数会明显小于 160）。
　　对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到 n 个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这 n 个节点进行递归路由，从而到达整个二叉树的【任何一个】节点（考虑到篇幅，具体的数学证明就不贴出来了）


（示意图：二叉树的拆分。注：图中的“第三”与“第四”应对调。非常感谢热心读者在评论区指正！）
　　K-桶（K-bucket）
　　前面说了，每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（请始终牢记：分布式系统的节点是动态变化滴），光知道【一个】显然是不够滴，需要知道【多个】才比较保险。
　　所以 Kad 论文中给出了一个“K-桶（K-bucket）”的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个【系统级】的常量。由使用 Kad 的软件系统自己设定（比如 BT 下载使用的 Kad 网络，K 设定为 8）。
　　这个“K-桶”其实就是【路由表】。对于某个节点而言，如果【以它自己为视角】拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的【上限】是 K。
　　说 K 只是一个【上限】，是因为有两种情况使得 K 桶的尺寸会小于 K。
1. 距离越近的子树就越小。如果整个子树【可能存在的】节点数小于 K，那么该子树的 K 桶尺寸永远也不可能达到 K。
2. 有些子树虽然实际上线的节点数超过 K，但是因为种种原因，没有收集到该子树足够多的节点，这也会使得该子树的 K 桶尺寸小于 K。


（示意图：K = 2 的路由表）

（示意图：路由过程）
　　K-桶（K-bucket）的刷新机制
　　刷新机制大致有如下几种：
　　1. 主动收集节点
　　任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新 K 桶中的节点信息（下面聊“节点的加入”时，会提及这种）
　　2. 被动收集节点
　　如果收到其它节点发来的请求（协议类型 FIND_NODE 或 FIND_VALUE），会把对方的 ID 加入自己的某个 K 桶中。
　　3. 探测失效节点
　　Kad 还是支持一种探测机制（协议类型 PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。

　　“并发请求”与“α 参数”
　　“K桶”的这个设计思路【天生支持并发】。因为【同一个】“K桶”中的每个节点都是平等的，没有哪个更特殊；而且对【同一个】“K桶”中的节点发起请求，互相之间没有影响（无耦合）。
　　所以 Kad 协议还引入了一个“α参数/α因子”，默认设置为 3，使用 Kad 的软件可以在具体使用场景中调整这个“α因子”。
　　当需要路由到某个“子树”，会从该子树对应的“K桶”中挑选【α个节点】，然后对这几个节点【同时】发出请求。
　　这么做有啥好处捏？俺在本文末尾聊“性能”和“安全性”时会具体介绍。

◇节点的加入

　　1
　　任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
　　2
　　A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
　　3
　　A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）
　　4
　　B 收到该请求之后，（如前面所说）会先把 A 的 ID 加入自己的某个 K 桶中。
　　然后，根据 FIND_NODE 协议的约定，B 会找到【K个】最接近 A 的节点，并返回给 A。
　　（B 怎么知道哪些节点接近 A 捏？这时候，【用 XOR 表示距离】的算法就发挥作用啦）
　　5
　　A 收到这 K 个节点的 ID 之后，（仅仅根据这批 ID 的值）就可以开始初始化自己的 K 桶。
　　6
　　然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型 FIND_NODE），如此往复（递归），直至 A 建立了足够详细的路由表。

◇节点的退出

　　与 Chord 不同，Kad 对于节点退出没有额外的要求（没有“主动退出”的说法）。
　　所以，Kad 的节点想离开 DHT 网络【不】需要任何操作（套用徐志摩的名言：悄悄的我走了，正如我悄悄的来）

◇引申阅读

　　Kad 就介绍到这里。想要进一步了解的同学，可以参考其原创论文：
《Kademlia——A Peer-to-peer Information System Based on the XOR Metric》

★为啥 Kad 成为 DHT 的主流？

　　Kad 成为 DHT 的主流实现方式，这已经是很明显的事实。问题在于：为啥会是它？
　　这是一个比较发散的问题，以下是俺个人观点，供参考。

◇简单性

　　在“简单性”方面，Kad 和 Chord 都属于很简单的。所以俺要拿一个【反面教程】作为对比。
　　下面俺来说说 CAN（Content Addressable Network）——它是最早出现的四个 DHT 协议之一（2001年），在学术界也算很有名气。
　　介绍 CAN 的资料，通常会在开篇提到：CAN 的拓扑结构是基于【多维笛卡尔环面】。俺相信很多程序员看到这个词汇，心里会咯噔一下，脑袋会大一圈。
　　和 CAN 的【多维环面】比起来，Kad 基于【二叉树】的拓扑结构，就显得异常简单、非常亲切。假如要让程序员在 “二叉树” 和 “多维笛卡尔环面” 二选一，都不用调查问卷，俺就敢打保票——超过 99% 的程序员会选择“二叉树”。
　　Kad 除了拓扑结构很简单，它的距离算法也很简单——只不过是节点 ID 的异或运算（XOR）。

　　（稍微跑题一下）
　　有很多充满学院派气息的系统设计，最终成为空中楼阁，就是因为：这些系统的【设计太复杂】了。当程序员对设计望而生畏，更有可能的情况是：要么没人愿意动手写，要么是有人动手写了，但是迟迟做不出来。

◇灵活性

　　以 Kad 和 Chord 的路由表来作对比。
　　Kad 的“K-bucket”是可以根据使用场景来调整 K 值，而且对 K 值的调整完全不影响代码实现。这就是所谓的“适应需求的灵活性”（有时也称之为“设计的弹性”）。
　　相比之下，Chord 的“Finger Table”就没有这种灵活性。

◇性能

　　Kad 的路由算法天生就支持【并发】（参见前面介绍的“α 参数”）。
　　而很多 DHT 协议（包括 Chord）没有这种优势。
　　由于公网上的线路具有很大的不确定性（极不稳定），哪怕是同样两个节点，之间的传输速率也可能时快时慢。由于 Kad 路由请求支持并发，发出请求的节点总是可以获得最快的那个 peer 的响应。

◇安全性

　　考虑到本文只介绍了 Chord 和 Kad，还是拿它俩做对比。
　　假设某个攻击者想要搞 Chord 网络的某个节点（假设叫 A），他/她可以先获得此 节点A 的 ID（这并不难）。知道 节点A 的 ID 后，攻击者就可以运行若干个受控的 Chord 节点（恶意节点），并且精心设置这批恶意节点的 ID；当这批恶意节点加入 Chord 网络后，就可以顺利被添加到 节点A 的路由表中（具体的原理，参见前面对“Finger Table”的介绍）。一旦 节点A 的路由表加入【足够多】的恶意节点，那么 节点A 的路由就有【足够大】的概率会经过这批恶意节点。攻击者作为这批恶意节点的控制人，就可以对 节点A 做很多手脚。

　　从理论上讲，类似的手法也可以用来针对 Kad。但是攻击难度会显著变大。原因如下：
　　1
　　Kad 协议缺省约定——在线时间越长的节点越可能被加入“K桶”。所以攻击者哪怕构造了一批恶意节点，这些恶意节点要想被正常节点加入自己的“K桶”，难度也很大。
　　2
　　就算某个恶意节点（比如叫 X）被正常节点（比如叫 A）加入“K-桶”。由于一个“K-桶”只对应【一个子树】。所以，只有当 节点A 在针对某个【特定子树】进行路由的时候，才【有可能】会碰上这个恶意节点。
　　（唠叨一下：Kad 的路由算法中，对每个子树都维护一个“K-桶”作为路由表）
　　3
　　即便正好对这个子树路由，也【不一定】会碰上恶意节点——碰上的【概率】取决于：“K 的大小” 以及 “从桶中选取节点的策略”。
　　4
　　前面提到：Kad 协议支持【并发查询】——每次都会从同一个“K-桶”中取出【α个】节点，发出查询请求（参数 α 默认设为 3,可以调大）
　　所以，这【α 个节点】中，如果只有一个是恶意的，这个恶意节点也很难捣乱；除非这【α 个节点】全部都是恶意的，而这个概率又很小。

　　（注：俺并【没有】说 Kad 是最安全的。这段介绍只能让你体会一下“K-桶”的设计思路——除了增加性能，还顺便增加了攻击者的难度）

◇小结

　　刚才聊的这几个方面，对每一个方面，Kad 未必能排第一，但至少它都能排进前几名。
　　几个方面综合起来，它就成为最有竞争力和活力的 DHT 技术方案。

★结尾

　　刚才聊到了“安全性”，本来还想再写一个章节，谈谈“针对 DHT 网络的攻击手法”。不过捏，本文已经写了很长，为了照顾某些患有“阅读障碍症”的读者，就先到此为止吧。今后另外找时间谈“攻击 DHT”这个话题。
　　由于本文的某些内容，俺也是现学现卖。如有错漏之处，还望懂行的同学不吝赐教 :)


俺博客上，和本文相关的帖子（需翻墙）：
《计算机网络通讯的【系统性】扫盲——从“基本概念”到“OSI 模型”》
《扫盲文件完整性校验——关于散列值和数字签名》
《聊聊 GFW 如何封杀 Resilio Sync（BTSync）？以及如何【免翻墙】继续使用？》
《“如何翻墙”系列：关于 Tor 的常见问题解答》
《“如何翻墙”系列：简单扫盲 I2P 的使用》
《“对抗专制、捍卫自由”的 N 种技术力量》
《聊聊“单点故障”——关于“德国空难”和“李光耀”的随想》

版权声明
本博客所有的原创文章，作者皆保留版权。转载必须包含本声明，保持本文完整，并以超链接形式注明作者编程随想和本文原始地址：
https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html?m=0