分布式散列表(DHT)的原理

这个是干嘛的

去中心化服务的基础组件

分布式散列表在概念上类似与传统的散列表,差异在于一个存在于分布式系统中,一个存在于单机中。

分布式主要是做为当规模很大时的解决方案。
比如大黄某篇文章上说

一匹马拉不动马车,可以找一匹更壮的马,或者是多找几匹马

单匹马无论多壮,总是有上限的。但多找几匹马,上限可能只受限于调度系统。

为啥会出现DHT?

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

第1代-中央服务器的模式

每个节点都需要先连接到中央服务器,然后才能查找到自己想要的文件在哪里。
这种技术的最大缺点是——中央服务器成为整个 P2P 网络的单点故障。这类 p2p 的典型代表是 Napster

第2代-采用广播的模式

要找文件的时候,每个节点都向自己相连的所有节点进行询问;被询问的节点如果不知道这个文件在哪里,就再次进行广播……如此往复,直至找到所需文件。
这种技术的最大缺点是——会引发“广播风暴”并严重占用网络带宽,也会严重消耗节点的系统资源。这类 p2p 的典型代表是 Gnutella 的早期版本。

第3代-采用DHT技术

找文件时,根据文件信息,在DHT中找到文件,通过路由算法,可以避免之前的广播。

DHT 有哪些应用场景

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

  • 分布式文件系统
  • 分布式缓存
  • 暗网
  • 无中心的聊天工具/IM
  • 无中心的微博客/microblogging
  • 无中心的社交网络/SNS

分布式散列表(DHT)的能解决什么问题

“无中心”导致的难点

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

“海量数据”导致的难点

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

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

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

“高效查询”导致的难点

对于节点数很多的分布式系统,如何快速定位节点,同时又不消耗太多网络资源,这也是一个挑战。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是采取基于key的路由方式,这不是具体的算法,而是指导思路,是种风格。用这种思路来设计路由机制让key本身提供足够多的路由信息。
当某个分布式系统具有自己的拓扑结构,它本身成为一个Overlay Network。所谓的覆盖网络,就是应用层的抽象,通俗地说就是“网络之上的网络”。对于大部分 DHT 而言,它们是基于互联网之上的“覆盖网络”,它们的数据通讯是依赖下层的互联网来实现的。
这种分层思想在网络协议中非常常见。每一层只解决这一层的问题,把复杂的问题分解到每一层来简化问题。

“路由算法”的权衡

由于 DHT 中的节点数可能非常多(比如:几十万、几百万),而且这些节点是动态变化的。因此就不可能让每一个节点都记录所有其它节点的信息。实际情况是:每个节点通常只知道少数一些节点的信息。

这时候就需要设计某种路由算法,尽可能利用已知的节点来转发数据。“路由算法”这玩意儿很重要,直接决定了 DHT 的速度和资源消耗。
在确定了路由算法之后,还需要做一个两难的权衡——“路由表的大小”。
路由表越大,可以实现越短(跳数越少)的路由;缺点是:(由于节点动态变化)路由表的维护成本也就越高。
路由表数越小,其维护成本越小;缺点是:路由就会变长(跳数变多)。

这里的设计与tcp/ip的网络层路由方式类似。

距离算法

某些 DHT 系统还会定义一种“距离算法”,用来计算:“节点之间的距离”、“数据之间的距离”、“节点与数据的距离”。
此处所说的“距离”属于逻辑层面,对应的是 DHT 自己的拓扑结构,网络之上的网络结点之间的距离;它与地理位置无关,也与互联网的拓扑结构无关。
前面要强调“node ID”与“data key”同构。当这两者同构,就可以使用同一种“距离算法”;反之,如果这两者不同构,多半要引入几种不同的“距离算法”。

数据定位

DHT 与传统的散列表在功能上是类似的。说白了,他们最关键的功能只有两个:“保存数据”和“获取数据”。

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

保存数据

  • 当某个节点得到了新加入的数据(K/V),它会先计算自己与新数据的 key 之间的“距离”;然后再计算它所知道的其它节点与这个 key 的距离。
  • 如果计算下来,自己与 key 的距离最小,那么这个数据就保持在自己这里。
  • 否则的话,把这个数据转发给距离最小的节点。
  • 收到数据的另一个节点,也采用上述过程进行处理(递归处理)。

获取数据

  • 当某个节点接收到查询数据的请求(key),它会先计算自己与 key 之间的“距离”;然后再计算它所知道的其它节点与这个 key 的距离。
  • 如果计算下来,自己与 key 的距离最小,那么就在自己这里找有没有 key 对应的 value。有的话就返回 value,没有的话就报错。
  • 否则的话,把这个数据转发给距离最小的节点。
  • 收到数据的另一个节点,也采用上述过程进行处理(递归处理)。

Kademlia(Kad)协议 简介

概述

拓扑结构——二叉树

总结

这篇文章是参考别的的文章写的。
但这个写作思路也值得学习的。

  • 简单介绍这东西是什么
  • 能解决什么实际问题
  • 解决这个问题会遇到什么难
  • 这些难点是怎么解决的
  • 现在工程上实际的方案是怎么样的

这是种顺应人思维方式的讲述方法。还有就是类比原理,通过熟悉的例子或原理类比出新的知识。