首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

分布式散列表的原理——以 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.斐克社区

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181205G1AFGB00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券