转：
分布式系统中的哈希算法
哈希
Hash也称散列、哈希，原理是把任意长度的字符串当作输入，然后通过Hash算法变成固定长度输出。Hash是一个映射的过程，因此是一定会产生冲突的，一般使用链地址法，开放寻址法等方法来解决hash冲突。
分布式下的哈希
在分布式的情景下，为了解决数据和请求的定向问题，我们也会常常使用到哈希算法。接下来，就会介绍几种常常在分布式环境下运用的hash算法。
普通哈希
哪怕是在分布式的环境下，我们也可以使用最简单的hash算法，通过设定好每台服务器对应的结果值，在请求或者数据进来时进行计算，将数据分别映射到相应的服务器上，由于计算规则是一致的，因此无论进行多少次的计算，数据的映射是不会进行变化的。
这种普通的哈希的方式优缺点分明，优点是实现简单，清晰明了。缺点是由于分布式系统中的节点充满了不确定性，可能会缩容或者扩容或者节点宕机，如果在这些情况下，意味着哈希的映射将会发生变化，同时之前的那些映射的数据需要进行迁移，以便之后能够正确的访问。而这种方式的哈希在这种情况下产生的数据迁移量将会是非常巨大的。
上图是一个普通的分布式系统的哈希映射关系，3台服务器分别接受哈希值为0，1，2的请求（一般为计算%2的值）。
于是当我们新增一台服务器之后，原本3台服务器变成了4台，哈希映射需要随之修改，大量的数据需要迁移。
一致性哈希
一致性哈希是为了解决之前说到的哈希造成的大量数据迁移的问题。
一致性哈希和普通哈希相比，同样是有一定的映射关系的，但是不同的是，我们会在开始创建一个哈希环，在环上分布着大量的节点值，一般的范围为0 ~ 2^32-1
之后我们会根据一定的规则，将服务器节点落在环上，如下图
之后的逻辑就比较简单了，当请求发往服务器后，经过计算找到其在环上的对应位置，然后检查该位置上是否有对应服务器节点，如果有就将请求转发过去，如果没有就沿着哈希环顺时针寻找，直到找到节点位置。
这样设计的好处是显而易见的，如果我们需要新增或者删除节点的时候，每次只会影响至多2个节点的数据，相比较之前的普通哈希，消耗显然是更少的。并且当某些服务器因故障突然宕机的时候，请求也可以顺延到下个节点进行处理。
节点分布不均问题
一致性哈希的特点决定了如果节点分布的不够均匀会导致其中部分节点压力过大，而部分节点有很多资源的空闲。如下图
图中的A，B节点显然是不均衡的，请求会更多地发往A节点而B节点只能获取A节点约1/3的请求。
于是一致性哈希往往会引入这么一个概念：虚拟节点。尽管我们的服务器分布不够均匀，但是我们可以认为的创建一些虚拟节点，并且创建相应的映射，帮助虚拟节点把请求转发到实际节点。
如图，我们可以创建对应的虚拟节点A'，B'，然后把发往B'的请求转发到B，A'的请求转发到A，这样就不会存在失衡的问题了。
哈希槽
哈希槽的典型是redis的分布式实现。
redis的分布式实现中，会在启动集群的时候确认所有的服务器数量，然后将数量为16384的哈希槽平均分配给所有的master服务器，然后所有的数据都会存放在指定的节点之中。
redis的哈希槽的实现和一致性哈希有相同之处，也有不同之处。最主要的原因是redis采用了不同的高可用策略。一致性哈希在服务器宕机时会把流量转到下一个服务器，但是redis不同，redis的集群模式会保证服务器节点拥有的主备模式。备份节点不会直接参与到哈希槽的分配中，但是当主节点宕机后，从节点会顶替主节点处理任务。
分布式哈希表
分布式哈希表（DHT）是一种分布式的哈希手段。和一致性哈希不同的是，DHT不需要中心节点来分配数据的流向。他有自己的一套机制保证无论数据刚开始走的是哪一个服务器，都可以找到自己需要前往的正确服务器。
Kademlia算法
Kademlia算法是一种典型的分布式的哈希表算法，多用于p2p网络的构建，由Petar Maymounkov 和 David Mazieres共同创造。Kademlia论文源地址：Kademlia
分布式环境下的哈希表的难点在于以下几点：
- 分布式环境下每个服务器不可能掌握所有服务器的情况，因此如何保证你的请求能在没有*节点定位的情况下找到对应的服务器是一大难点。
- 同样由于分布式环境的服务器的掌握信息有限，那么服务器的加入和退出如何能够被集群知晓也是一大难点。
那么我们来看Kademlia算法是如何解决这些问题的吧。
异或运算
Kademlia使用到了异或来进行距离的计算。我们先来看看异或的定义。
异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）
然后我们来看看为什么用异或来计算距离。
a⊕b = b⊕a // 异或符合交换律，a节点到b节点的距离和b节点到a结点的距离相同
a⊕b = 0 // 自己和自己的距离为0
a⊕b >= 0 // 两个节点之间的距离大于0
a⊕b + b⊕c >= a⊕c // a到b再到c的距离大于等于直接到c的距离根据上述的一些异或的规则，我们可以发现异或和距离的一些特性可以说是绝配，真的很佩服算法的作者能够想到如此精巧的设计。
二叉树的构建
确定了用异或来计算距离后，那么具体集群是如何构建并存储信息使得可以查找到正确的信息呢？
Kademlia算法理论中每个集群的节点都会存储一部分节点的信息（不可能存储所有节点的信息，因为效率会低，并且无法保证实时性）。
所有的节点会构建成一棵独特的二叉树如下图：
首先把每个节点的id经过一定的哈希计算得到该节点的一串01字符串以表示其在树中的位置，从高位开始，1则往左子树走，0往右子树走，直到结束。可以看出图中的黑色节点的哈希值为0011
二叉树的拆分
Kademlia的二叉树中的每一个节点都可以根据自己的视角进行二叉树的拆分
拆分规则是从根节点开始依次把不包含自己的子树拆分出来，以此类推，最后只剩下自己。之前的二叉树拆分如之前的图。对于黑色节点来说，外部有拆分出了四个不包含自己的子树。
K-bucket机制
在二叉树拆分之后每一个拆分过后的子树实际上对应的就是一个一个bucket，每个bucket对于当前节点的距离是不同的范围，距离越远，高位不同，因此异或结果差距越大（距离越远）：
| K-bucket | 距离区间 |
|---|---|
| 0 | [2^0, 2^1) |
| 1 | [2^1, 2^2) |
| 2 | [2^2, 2^3) |
| 3 | [2^3, 2^4) |
| 4 | [2^4, 2^5) |
所以实际上每一个节点再进行拆分后只需要在对应的每个bucket中存储一份该bucket的节点就可以遍历整个二叉树（集群）。当然为了容错，一般来说每个bucket的节点都会保留几个，而不仅仅是一个。
节点查询
大致了解了原理之后，我们回过头来看每次请求是如何定位节点的。
首先一个请求进入集群中的某个服务器。然后我们将请求带着的目的地服务器的id和当前服务器的id计算两者的距离。然后计算出了一个值，之后从服务器的bucket列表中寻找对应的bucket（即这个距离范围对应的bucket）。我们的目标服务器就可以锁定在了那个bucket的范围之内，之后，在bucket中寻找距离该节点最近的K个服务节点（此参数可以自行设定大小），将请求重定向到这几个节点。之后重复上述的步骤，如果该集群中真的有目标节点，那么就可以成功的返回。
基本的机制如此，当然在实际的环境中我们考虑到现实情况会对请求做超时处理，避免大量的节点间的查询造成不必要的负载。
节点变动
一个新节点是想加入网络，首先有一个前提条件：他需要有一个处于网络中的节点的信息，然后才能开启加入流程。
加入流程：
- 新节点A以之前就有的节点T为起点，将其加入自己的K-bucket中，并且生成一个自己的节点id
- 节点A项节点B进行请求，以自己的id为参数请求节点定位自己的位置
- 之后就是查询结点的流程了，每一个路经的节点都会找到自己节点中存储的距离节点最近的节点，然后A把这些节点放入自己的bucket中以完善自己的路由表。同时，这些路经节点也会把A节点放入自己的路由表中，以待后用。
- 等到大部分节点返回后，A的路由表建立完成，一些节点也已经将A节点加入自己的路由表。至此A节点加入网络成功。
算法的参数
算法中我们用到的一些参数其实是可以自己定义的：
- k-bucket中的k：定义了每一层bucket会存储k个节点信息
- 每一次请求会向s个节点发送信息
- id的长度也是可以自定义的，注意id的长度会决定二叉树的高度
总结
分布式系统中的哈希算法有很多种，实现不同，功能也不尽相同。对于一般的企业应用中，带有中心节点的哈希算法是更为理想的选择，因为意味着服务的可控可监测。而在类似于p2p和区块链的环境下，具备中心节点的分布式哈希算法是没法接受的，因为p2p和区块链的设计上是没有中心节点的，也不会有节点能够知道所有网络中的节点信息，因此无中心节点的哈希算法在此可以大放异彩。
转：