区块链技术入门 | 分布式哈希表（上篇）

DHT 即分布式哈希表，是实现分布式存储和下载的关键技术，现已广泛应用在P2P网络中。想要了解分布式哈希表的技术实现，首先需要知道什么是哈希算法和哈希表。

哈希算法简单来说就是一个函数，这个函数有一些特殊的性质：

1. 无论输入有多复杂，输出的长度都是固定的。

2. 无论输入发生多么微小的变化时，输出都会与之前完全不同。

3. 无法通过哈希值倒推原信息，也就是不可逆。

哈希表，又称为散列表，这个表是用来存放键值对的。当给文件加密时，不仅仅需要存储文件的哈希，也需要存储文件本身。这样就需要将文件和哈希成对存储以方便查找。

对于普通的哈希表而言，扩容的代价是很大的。因为普通的 Hash 计算地址方式如下： Hash(Key)%M ，扩容之后，元素的位置全变了。有数学证明，扩容成两倍大小，使得再哈希的元素个数最少，这也是为什么为了减少扩容时元素的移动，总是将哈希表扩容成原来大小的两倍的原因。

所以哈希表的本质，就是当你寻找某个信息时，最终都是一个将哈希值取余去寻找某个位置的一个过程，但我们也看到了，当有新的节点加入或者旧节点退出时，都需要重新存放键值对，当信息量较大的时候就容易导致网络阻塞。

为了解决节点变动的问题，1997 年麻省理工的 Karger 等人发明了一致性哈希，这才真正让分布式存储进入到了一个真正可以规模化应用的阶段。

什么是一致性哈希呢？

首先，将哈希值空间组织成一个虚拟的圆环，我们以 SHA256 来举例。SHA256 有 2^256 个哈希值，将所有可能的哈希值组成一个圆环，从 0 到 2^256−1，按顺时针进行排序，并且在 12 点处 0 与 2^256−1 重合。

然后，将各个节点用于存储的服务器进行一次哈希计算，可以选择服务器的 IP 地址或者主机名进行哈希计算（为防止主机名重叠一般使用 IP地址，这里很重要），并且按照计算所得哈希将节点服务器按照顺序放在圆环的相应位置

最后，将数据的 key（键，即数据的关键词）使用相同的哈希算法计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

这样，当某一节点因为某种原因而停止运作时，只会影响到其逆时针方向上到上一个节点之间的数据，同样，当新加入了一个节点的时候，也只影响到其逆时针方向上到前一个节点之间的数据。

普通的一致性哈希有没有缺点呢？当然是有的。总结一下就是：没有考虑到每台机器的情况，不能实现很好的负载均衡。

有没有解决办法？有，就是虚拟机技术。例如当一个哈希环中只有两个节点存在：

可以看到，很有可能出现上图这种分配不均匀的情况，为了能在不加入物理设备的前提下实现负载均衡，我们将两个节点的IP后加入一些别的内容（例如#1、#2）再次计算哈希，得到 Node 1.1，Node 1.2，Node 2.1，Node 2.2，使其实现下图中的情况：

当这些虚拟节点加入，数据的分配自然要发生变化，当然，这些虚拟机的物理实体只有一个，自然会存到真正的物理实体中，自然就可以让负载尽量均衡。

IPFS的底层技术中，DHT是非常重要的一环，而之所以IPFS会更加偏好公网固定IP，就是因为固定IP不会改变在哈希环中的位置，进而不会造成因节点变动而产生的额外网络负载。这也是矿场收益会更高且更加稳定的原因之一。

到此，分布式哈希表DHT的基本技术已经介绍完毕。

（作者：区小白）