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

来源：编程随想

编辑：IPFS.斐克社区-Seven

文章目录

★预备知识

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

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

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

★Chord 协议简介

★Kademlia（Kad）协议 简介

★为啥 Kad 成为 DHT 的主流？

★结尾

本文仅写至 ★分布式散列表（DHT）如何解决上述难点？下一篇继续写完。。。

★预备知识

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

◇什么是“散列/哈希（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，没有的话就报错。

否则的话，把这个数据转发给距离最小的节点。

收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

THE END.

想了解本文剩余部分，请留意明天的推送。

最后

别忘了

关注我们的公众号：

IPFS.斐克社区