预备知识
(如果你自认为是一个熟练的程序员,请直接略过“预备知识”这个章节,看下一章节)
什么是“散列/哈希(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 比特的散列值(2128 比 “地球上所有电子文档总数” 还要大【很多数量级】)。
同构的“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 都是这个二叉树的【叶子】。
在映射之前,先做一下预处理。
- 先把 key 以二进制形式表示。
- 把每一个 key 缩短为它的【最短唯一前缀】。
为啥要搞“最短唯一前缀”?
Kad 使用 160比特
的散列算法(比如 SHA1),完整的 key 用二进制表示有 160
个数位(bit)。
首先,实际运行的 Kad 网络,即使有几百万个节点,相比 keyspace(2160)也只是很小很小很小的一个子集。
其次,由于散列函数的特点,key 的分布是【高度随机】的。因此也是【高度离散】的——任何两个 key 都【不会】非常临近。
所以,使用“最短唯一前缀”来处理 key 的二进制形式,得到的结果就会很短(比特数远远小于 160)。
散列值的映射
完成上述的预处理后,接下来的映射规则是:
- 先把 key 以二进制形式表示,然后从高位到低位依次处理。
- 二进制的第
n
个 bit 就对应了二叉树的第n
层 - 如果该位是
1
,进入左子树,是0
则进入右子树(这只是人为约定,反过来处理也可以) - 全部数位都处理完后,这个 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。
- 距离越近的子树就越小。如果整个子树【可能存在的】节点数小于 K,那么该子树的 K 桶尺寸永远也不可能达到 K。
- 有些子树虽然实际上线的节点数超过 K,但是因为种种原因,没有收集到该子树足够多的节点,这也会使得该子树的 K 桶尺寸小于 K。
(示意图:K = 2 的路由表)
(示意图:路由过程)
K-桶(K-bucket)的刷新机制
刷新机制大致有如下几种:
- 主动收集节点
任何节点都可以主动发起“查询节点”的请求(对应于协议类型 FIND_NODE),从而刷新 K 桶中的节点信息(下面聊“节点的加入”时,会提及这种) - 被动收集节点
如果收到其它节点发来的请求(协议类型 FIND_NODE 或 FIND_VALUE),会把对方的 ID 加入自己的某个 K 桶中。 - 探测失效节点
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”这个话题。
由于本文的某些内容,俺也是现学现卖。如有错漏之处,还望懂行的同学不吝赐教 :)