哈希
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 和区块链的设计上是没有核心节点的，也不会有节点可能晓得所有网络中的节点信息，因而无核心节点的哈希算法在此能够大放异彩。