抽象一致性 hash 多用于散播式数据存储场景，在集群节点数目发生变化时，擢升集群相宜变化的能力。

大多数网站背后驯服不是只消一台功绩器提供功绩，因为单机的并发量和数据量皆是有限的，是以皆会用多台功绩器组成集群来对外提供功绩。那么这些功绩器需要若何分派客户端的肯求呢，这个其实即是负载平衡。然而一般的负载平衡算法是针对通盘功绩器上的数据皆是通常的，也即是无法应付散播式存储的场景。

当想要提高系统的容量，就会将数据水平切分到不同的节点来存储，也即是将数据散播到了不同的节点。比如一个散播式 KV（key-valu） 缓存系统，某个 key 应该到哪个或者哪些节点上得回，应该是详情的，不是说纵情拜访一个节点皆不错得到缓存限度的。而 hash 算法就不错很好的完成 k-v 对的存储，因为对合并个关键字进行哈希诡计，每次诡计皆是相通的值，这么就不错将某个 key 详情到一个节点了，不错赋闲散播式系统的负载平衡需求。

#Java #每天一个常识点而一致性 hash 是传统 hash 算法的增强版。

传统hash存在的问题hash 算法最约略的作念法即是进行取模运算，比如散播式系统中有 3 个节点，就不错基于 hash(key) % 3 公式对数据进行映射。

然而这么，要是节点数目发生了变化（比如面前节点不成赋闲条件了，需要新增一个节点增多容量），也即是在对系统作念扩得意者缩容时，必须移动更动了映射关联的数据，不然会出现查询不到数据的问题。

显明，要处分这个问题，就需要进行 数据移动 ，比如节点的数目从 3 变化为 4 时，需要基于新的诡计公式 hash(key) % 4 ，从头对数据和节点作念映射。

假定总和据条数为 M，哈希算法在靠近节点数目变化时，最坏情况下所终点据皆需要移动，是以它的数据移动边界是 O(M)，真钱三公棋牌游戏官网这么数据的移动资本太高了。

而一致性 hash 算法例是将这种因节点数目变化所需要破耗的援救资本，降至最低

一致性hash一致性 hash 引入了哈希环的成见，中枢想路：

法例了一个哈希环，环的元素由 [0， 2^32 -1] 范围的整数组成将 key，功绩节点通过诡计映射到哈希环上顺时针标的为 key 寻找相邻的 第一台 功绩节点，完成 key -> node 的关联映射比如，下图中的 key-1 映射的位置，往顺时针的标的找到第一个节点即是节点 A。另外两个节点对应关联为：

Key1 -> Node-AKey2 -> Node-BKey3 -> Node-C假定面前新增一个节点，比如节点数目从3增多到了4，新的节点 D 进程哈希诡计后映射到了下图中的位置：也即是说，key-1、key-3 皆不受影响，只消 key-2的数据 需要被移动节点 D。

因此，在一致哈希算法中，博亚(中国)要是增多或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。这就不错处分传统 hash 算法中多半数据移动的问题。

数据歪斜问题然而一致性哈希算法并 不保证节点省略在哈希环上散播均匀 ，这么就会带来一个问题，会有多半的肯求齐集在一个节点上。

这么通盘的数据皆会肯求到节点 A 上，这就莫得了负载平衡。况兼假定节点 A 故障被移除了，那么通盘的数据也皆需要移动到节点 B 上

因此，一致性 hash 如实省略裁减节点数目变化对集群举座酿成的影响，但存在 数据歪斜 问题。

引入假造节点假造节点的中枢：

将一个物理节点分化成多个假造节点将假造节点映射到哈希环受骗 key 射中假造节点后，通过假造节点找到其所属的物理节点也即是说，不再将实在节点映射到哈希环上，而是将假造节点映射到哈希环上，并将假造节点映射到实际节点，是以这里有 两层 的映射关联。

比如：

对节点 A 加上编号来行为假造节点：A-01、A-02、A-03对节点 B 加上编号来行为假造节点：B-01、B-02、B-03对节点 C 加上编号来行为假造节点：C-01、C-02、C-03不错看到这么使得数据散播愈加平衡。另外要是移除了一个节点 C，也不会发生多半的数据移动情况，况兼能有不同的节点共同摊宗派统的变化，因此涌现性更高：

比如，当某个节点被移除时，对应该节点的多个假造节点均会移除，而这些假造节点按顺时针标的的下一个假造节点， 可能会对应不同的实在节点 ，即这些不同的实在节点共同摊派了节点变化导致的压力。上图是为了简短分解，每个实在节点仅包含 3 个假造节点，这么能起到的平衡效力其实很有限。而在实际的工程中，假造节点的数目会大许多，比如 Nginx 的一致性哈希算法，每个权重为 1 的实在节点就含有160 个假造节点。

况兼，有了假造节点后，还不错为硬件设立更好的节点增多权重，比如对权重更高的节点增多更多的假造机节点即可。

基础完了public class ConsistentHash {

private final int numberOfReplicas; // 假造节点数目

// 哈希环，key为假造节点的哈希值，value为实际节点

private final SortedMap circle = new TreeMap;

/**

* 构造函数

*

* @param numberOfReplicas 假造节点数目

* @param nodes 实际节点列表

*/

public ConsistentHash(int numberOfReplicas， Collection nodes) {

this.numberOfReplicas = numberOfReplicas;

for (String node : nodes) {

addNode(node);

}

}

// 添加节点

public void addNode(String node) {

for (int i = 0; i

String virtualNode = node + "#" + i;

int hash = getHash(virtualNode);

circle.put(hash， node);

}

}

// 移除节点

public void removeNode(String node) {

for (int i = 0; i

String virtualNode = node + "#" + i;

int hash = getHash(virtualNode);

circle.remove(hash);

}

}

// 获取数据应该存储的节点

public String getNode(String key) {

if (circle.isEmpty) {

return null;

}

// 诡计 key 的哈希值 int hash = getHash(key); // 要是莫得大于等于该 hash 值的节点，则复返第一个节点 if (!circle.containsKey(hash)) { SortedMap tailMap = circle.tailMap(hash); hash = tailMap.isEmpty ? circle.firstKey : tailMap.firstKey; } return circle.get(hash); } /** * FNV1_32_HASH 算法 * * @param str 字符串 * @return 哈希值 */ private long getHash(String str) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i > 7; hash += hash > 17; hash += hash

// 要是算出来的值为负数则取其所有值 if (hash

归来领先，hash 算法不错用来处分离播式存储的问题，但要是节点数目发生变化，也将会发生多半的数据移动。

而一致性 hash 算法即是通过一个首尾接续的 hash 环处分传统 hash 算法中多半的数据移动的问题的，要是增多或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

然而一致性哈希算法并 不保证节点省略在哈希环上散播均匀 ，存在 数据歪斜 问题。

因此就引入了假造节点，将一个实在节点映射为多个假造节点。不再将实在节点映射到哈希环上，而是将假造节点映射到哈希环上，从而提高节点的负载平衡度博亚(中国)，和系统的涌现性。