常见的分布式协议与算法【转】

我这里将主要列举一致性Hash算法、Gossip协议、QuorumNWR算法、PBFT算法、PoW算法、ZAB协议,Paxos会分开单独讲,Raft算法已经写好了一篇文章,具体可以参考:从JRaft来看Raft协议实现细节。

一致性Hash算法

一致性Hash算法是为了解决Hash算法的迁移成本,以一个10节点的集群为例,如果向集群中添加节点时,如果使用了哈希 算法,需要迁移高达 90.91% 的数据,使用一致哈希的话,只需要迁移 6.48% 的数据。

所以使用一致性Hash算法实现哈希寻址时,可以通过增加节点数降低节点 宕机对整个集群的影响,以及故障恢复时需要迁移的数据量。后续在需要时,你可以通过增 加节点数来提升系统的容灾能力和故障恢复效率。而做数据迁移时,只需要迁移部分数据,就能实现集群的稳定。

不带虚拟节点的一致性Hash算法

我们都知道普通的Hash算法是通过取模来进行路由寻址的,同理一致性Hash用了取模运算,但与哈希算法不同的是,哈希算法是对节点的数量进行取模 运算,而一致哈希算法是对 2^32 进行取模运算。你可以想象下,一致哈希算法,将整个 哈希值空间组织成一个虚拟的圆环,也就是哈希环:

image-20200705171118346

在一致哈希中,你可以通过执行哈希算法,将节点映射到哈希环上,从而每个节点就能确定其在哈希环上的位置了:

image-20200705171554305

然后当要读取指定key的值的时候,通过对key做一个hash,并确定此 key 在环上的位置,从这个位置沿着哈希环顺时针“行走”,遇到的第一节点就是 key 对应的节点。

image-20200705171705097

这个时候,如果节点C宕机了,那么节点B和节点A的数据实际上不会受影响,只有原来在节点C的数据会被重新定位到节点A,从而只要节点C的数据做迁移即可。

如果此时集群不能满足业务的需求,需要扩容一个节点:

image-20200705171946737

你可以看到,key-01、key-02 不受影响,只有 key-03 的寻址被重定位到新节点 D。一般 而言,在一致哈希算法中,如果增加一个节点,受影响的数据仅仅是,会寻址到新节点和前 一节点之间的数据,其它数据也不会受到影响。

实现代码如下:

/** * 不带虚拟节点的一致性Hash算法 */ public class ConsistentHashingWithoutVirtualNode { /** * 待添加入Hash环的服务器列表 */ private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"}; /** * key表示服务器的hash值,value表示服务器的名称 */ private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); /** * 程序初始化,将所有的服务器放入sortedMap中 */ static { for (int i = 0; i < servers.length; i++) { int hash = getHash(servers[i]); System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash); sortedMap.put(hash, servers[i]); } System.out.println(); } /** * 得到应当路由到的结点 */ private static String getServer(String node) { // 得到带路由的结点的Hash值 int hash = getHash(node); // 得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = sortedMap.tailMap(hash); // 第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); // 返回对应的服务器名称 return subMap.get(i); } public static void main(String[] args) { String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; for (int i = 0; i < nodes.length; i++) System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]"); } } 带虚拟节点的一致性Hash算法

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzdyzz.html