【编程随想】聊聊分布式散表（DHT）的原——以 Kademlia（Kad）
和 Chord 为
聊聊分布式散表（DHT）的原——以 Kademlia（Kad） 和 Chord 为
Posted: 21 Sep 2017 09:37 AM PDT
★引——为啥要聊这个话题？
这是篇较深地谈技术的博（且还牵涉到点算法）。俺很久没有写这种类型的博。
今天发这篇，主要是因为如下点：
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
128
“地球上所有电档总数” 还要【很多数级】）。
◇同构的“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, 2
m
-1]。你把这个区间头尾相接就变成个环，其周是 2
m
。
然后对这个环规定个移动向（如顺时针）。
如果 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 + 2
i
) mod 2
m
)
当收到请求（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 个数位。
先，实际运的 Kad 络，即使有百万个节点，相 keyspace（2
160
）也只是很很很的个集。
其次，由于散函数的特点，key 的分布是【度随机】的。因此也是【度离散】的——任何两个 key 都【会】常临近。
所以，使“最短唯前缀”来处 key 的进制形式，得到的结果就会很短（远远于 160 个数位）。
散值的映射
完成上述的预处后，接下来的映射规则是：
1. 先把 key 以进制形式表示，然后从位到低位依次处。
2. 进制的第 n 个数位就对应叉树的第 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 特），因此拆分出来的树【最多】有 160 个（考虑到实际的节点数【远远
于】2
160
，树的个数会明显于 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）。它是最早出现的（2001）四个 DHT 协议之，在学术界也算很有名
。
介绍 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”这个话题。
由于本的某些内容，俺也是现学现卖。如果错之处，还望懂的同学吝赐教 :)
俺博客上，和本相关的帖（需翻墙）：
扫盲件完整性校验——关于散值和数字签名
聊聊 GFW 如何封杀 Resilio Sync（BTSync）？以及如何【免翻墙】继续使？
“如何翻墙”系：简单扫盲 I2P 的使
“对抗专制、捍卫由”的 N 种技术
聊聊“单点故障”——关于“德国空难”和“光耀”的随想
版权声明
本博客所有的原创章，作者皆保版权。转载必须包含本声明，保持本完整，并以超链接形式注明作者"编程随想"和本原始地址。
翻墙具
使 BT sync 动同步各种翻墙具（BT sync 免翻墙可）， 同步密钥是 BTLZ4A4UD3PEWKPLLWEOKH3W7OQJKFPLG 如有
其它问题，program.think@gmail.com联系俺
You are subscribed to email updates from 编程随想的博客.
To stop receiving these emails, you may unsubscribe now.
Email delivery powered by Google
Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States
