分布式协议与算法，你了解多少？( 二 ) _分布式协议

增加了节点后，节点在哈希环上的分布就相对均匀了。这时，如果有访问请求寻址到“Node-A-01”这个虚拟节点，将被重定位到节点 A 。
具体代码实现如下：
/** * 带虚拟节点的一致性Hash算法 */public class ConsistentHashingWithVirtualNode{/*** 待添加入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"};/*** 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好*/private static List<String> realNodes = new LinkedList<String>();/*** 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称*/private static SortedMap<Integer, String> virtualNodes =new TreeMap<Integer, String>();/*** 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点*/private static final int VIRTUAL_NODES = 5;static{// 先把原始的服务器添加到真实结点列表中for (int i = 0; i < servers.length; i++)realNodes.add(servers[i]);// 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高for (String str : realNodes){for (int i = 0; i < VIRTUAL_NODES; i++){String virtualNodeName = str + "&&VN" + String.valueOf(i);int hash = getHash(virtualNodeName);System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);virtualNodes.put(hash, virtualNodeName);}}System.out.println();}/*** 得到应当路由到的结点*/private static String getServer(String node){// 得到带路由的结点的Hash值int hash = getHash(node);// 得到大于该Hash值的所有MapSortedMap<Integer, String> subMap =virtualNodes.tailMap(hash);// 第一个Key就是顺时针过去离node最近的那个结点Integer i = subMap.firstKey();// 返回对应的虚拟节点名称，这里字符串稍微截取一下String virtualNode = subMap.get(i);return virtualNode.substring(0, virtualNode.indexOf("&&"));}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]) + "]");}}Gossip协议Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。Gossip 协议通过上面的特性，可以保证系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。
Gossip数据传播方式Gossip数据传播方式分别有：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering）。
直接邮寄（Direct Mail）：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。也就是说，只采用直接邮寄是无法实现最终一致性的。
反熵（Anti-entropy）：反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。
在实现反熵的时候，主要有推、拉和推拉三种方式。推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵，拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵。
谣言传播（Rumor mongering）：指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。由于谣言传播非常具有传染性，它适合动态变化的分布式系统

文章插图

Quorum NWR算法Quorum NWR 中有三个要素，N、W、R 。
N 表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本，就像下图的样子：

文章插图

在这个三节点的集群中，DATA-1 有 2 个副本，DATA-2 有 3 个副本，DATA-3 有 1 个副本。也就是说，副本数可以不等于节点数，不同的数据可以有不同的副本数。
W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新。
R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本。