MAC多原链之技能进阶：MAC的NDPOS共同机制与共同性哈希算法
一．散布式算法
在做效劳器负载均衡时分可供挑选的负载均衡的算法有许多，包含： 轮循算法(Round Robin)、哈希算法(HASH)、最少衔接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其间哈希算法是最为常用的算法.
典型的运用场景是： 有N台效劳器供给缓存效劳，需求对效劳器进行负载均衡，将恳求均匀分发到每台效劳器上，每台机器担任1/N的效劳。
常用的算法是对hash成果取余数 (hash() mod N )：对机器编号从0到N-1，依照自定义的 hash()算法，对每个恳求的hash()值按N取模，得到余数i，然后将恳求分发到编号为i的机器。但这样的算法办法存在丧命问题，假如某一台机器宕机，那么应该落在该机器的恳求就无法得到正确的处理，这时需求将当掉的效劳器从算法从去除，此刻分会有(N-1)/N的效劳器的缓存数据需求从头进行核算;假如新增一台机器，会有N /(N+1)的效劳器的缓存数据需求进行从头核算。关于体系而言，这一般是不行承受的波动(因为这意味着许多缓存的失效或许数据需求搬运)。那么，怎么规划一个负载均衡战略，使得受到影响的恳求尽可能的少呢?
在Memcached、Key-Value Store 、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，能够说Consistent Hashing 是散布式体系负载均衡的首选算法。
二．共同性哈希算法的了解
1、算法简述
共同性哈希算法(Consistent Hashing Algorithm)是一种散布式算法，常用于负载均衡。Memcached client也挑选这种算法，处理将key-value均匀分配到许多Memcached server上的问题。它能够替代传统的取模操作，处理了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真实存储的server，命中率会急剧下降)。
简略来说，共同性哈希将整个哈希值空间安排成一个虚拟的圆环，如假定某哈希函数H的值空间为0 - (2^32)-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：
整个空间按顺时针方向安排。0和(2^32)-1在零点中方向重合。
下一步将各个效劳器运用H进行一个哈希，详细能够挑选效劳器的ip或主机名作为关键字进行哈希，这样每台机器就能断定其在哈希环上的方位，这儿假定将上文中三台效劳器运用ip地址哈希后在环空间的方位如下：
接下来运用如下算法定位数据访问到相应效劳器：将数据key运用相同的函数H核算出哈希值h，通依据h断定此数据在环上的方位，从此方位沿环顺时针“行走”，第一台遇到的效劳器就是其应该定位到的效劳器。
例如咱们有A、B、C、D四个数据目标，经过哈希核算后，在环空间上的方位如下：
依据共同性哈希算法，数据A会被定为到Server 1上，D被定为到Server 3上，而B、C别离被定为到Server 2上。
2、容错性与可扩展性剖析
下面剖析共同性哈希算法的容错性和可扩展性。现假定Server 3宕机了：
能够看到此刻A、C、B不会受到影响，只要D节点被重定位到Server 2。一般的，在共同性哈希算法中，假如一台效劳器不行用，则受影响的数据仅仅是此效劳器到其环空间中前一台效劳器（即顺着逆时针方向行走遇到的第一台效劳器）之间数据，其它不会受到影响。
下面考虑别的一种状况，假如咱们在体系中添加一台效劳器Memcached Server 4：
此刻A、D、C不受影响，只要B需求重定位到新的Server 4。一般的，在共同性哈希算法中，假如添加一台效劳器，则受影响的数据仅仅是新效劳器到其环空间中前一台效劳器（即顺着逆时针方向行走遇到的第一台效劳器）之间数据，其它不会受到影响。
综上所述，共同性哈希算法关于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
3、虚拟节点
共同性哈希算法在效劳节点太少时，简单因为节点分部不均匀而构成数据歪斜问题。例如咱们的体系中有两台效劳器，其环散布如下：
此刻必定构成很大都据会集到Server 1上，而只要极少量会定位到Server 2上。为了处理这种数据歪斜问题，共同性哈希算法引入了虚拟节点机制，即对每一个效劳节点核算多个哈希，每个核算成果方位都放置一个此效劳节点，称为虚拟节点。详细做法能够在效劳器ip或主机名的后边添加编号来完成。例如上面的状况，咱们决定为每台效劳器核算三个虚拟节点，所以能够别离核算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，所以构成六个虚拟节点：
4.JAVA完成
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash
HashFunc hashFunc;
private final int numberOfReplicas;
private final SortedMap
public ConsistentHash(int numberOfReplicas, Collection
this.numberOfReplicas = numberOfReplicas;
this.hashFunc = new HashFunc() {
@Override
public Long hash(Object key) {// return fnv1HashingAlg(key.toString());
return md5HashingAlg(key.toString());
}
};
//初始化节点
for (T node : nodes) {
add(node);
}
}
Consistent Hashing最大极限地按捺了hash键的从头散布。别的要获得比较好的负载均衡的作用，往往在效劳器数量比较少的时分需求添加虚拟节点来确保效劳器能均匀的散布在圆环上。因为运用一般的hash办法，效劳器的映射地址的散布十分不均匀。运用虚拟节点的思维，为每个物理节点（效劳器）在圆上分配100～200个点。这样就能按捺散布不均匀，最大极限地减小效劳器增减时的缓存从头散布。用户数据映射在虚拟节点上，就表明用户数据真实存储方位是在该虚拟节点代表的实践物理效劳器上。
三．MAC 的共同机制与传统散布式共同算法的差异
1. 传统散布式共同性算法和区块链共同进程的异同点
相同点：
· Append only
· 着重序列化
· 少量服从大都准则
· 别离掩盖的问题：即长链掩盖短链区块，多节点掩盖少量节点
不同点：
· 传统散布式共同性算法大多不考虑拜占庭容错(Byzanetine Paxos在外)，即假定一切节点只发作宕机、网络故障等非人为问题，并不考虑歹意节点篡改数据的问题；
· 传统散布式共同性算法是面向日志（数据库）的，即更通用的状况，而区块链共同模型面向买卖的，所以严格来说，传统散布式共同性算法应该处于区块链共同模型的下面一层。
2. 区块链共同模型与传统共同性算法的联系
考虑上面的不同点，结合私有链和职业链的性质，咱们有：
私有链：关闭生态的存储网络，一切节点都是可信任的，如某大型集团内部大都公司。
职业链：半关闭生态的买卖网络，存在对等的不信任节点，如房地产职业A、B、C、D公司。
公有链：敞开生态的买卖网络，这层主要是为职业链和私有链供给全球买卖网络。
因为私有链是关闭生态的存储网络，也就是说运用传统散布式共同性模型应该是最优的；因为联盟职业链其半关闭半敞开特性，运用Delegated Proof of XXX 是最优的，能够考虑以传统共同性算法作为基础参加拜占庭容错/安全防护机制进行改善。公有链PoW应该仍然是最优的挑选。
四．MAC的NDPOS 进化于DPOS,POS.
嵌套股份授权证明机制（NDPOS）
(1) NDPoS的中心机制行将多个链之间的原子操作
(2) 在NDPoS结构中，每一条链中的账本分为署理节点与跟从节点两种人物
(3) 当网络存在三层或更多层嵌套架构时，每个账本节点可能一起具有若干种人物。
以一个三方买卖为例，假定存在于三个分片链的X、Y、Z记载之间进行转账买卖，其间记载X来自分片A；记载Y来自分片B；记载Z来自分片C。
能够看到，分片链A、B、C之间彻底独立，而每个分片的投票节点内存在一个或多个署理节点，构成分片链之间的一个虚拟链。在这个虚拟链中一切节点相同运用DPoS机制进行共同。能够看到，NDPoS的中心思维在于先在顶层虚拟链中达到共同，然后将成果传达给底层分片链。当存在超越两层虚拟链时，该形式以递归的方法由顶层向下传递。
工作量证明（Proof of Work, POW）
(1) 工作量证明机制，使得区块的发生具有核算性难度，以添加进犯的本钱;
(2) 从统计学视点，1笔买卖在6个区块后被以为是清晰承认且不行逆的。中心开发者以为，需求120个区块才干充沛维护网络不受来自潜在更长的已将新发生的币花掉的进犯区块链的要挟;
(3) 虽然呈现更长的区块链会变得不太可能，但任何具有巨大经济资源的人仍有可能制作一个更长的区块链来假造买卖（51%进犯）。
股权证明机制（Proof of Stake,POS）
(1) 股权证明机制有许多不同变种，但基本概念是发生区块的难度与在网络里所占的股权(一切权占比)成份额;
(2) 处理POW的资源耗费问题。
瑞波共同机制(Ripple Consensus)
(1) 瑞波共同算法，使一组中心化的特别节点列表达到共同;
(2) 初始特别节点列表就像一个沙龙，要接收一个新成员，必须由51%的该沙龙会员投票经过;
(3) 共同遵从这中心成员的51%权利，外部人员则没有影响力。因为该沙龙由“中心化”开端，它将一直是“中心化的”;
(4) 瑞波体系将股东们与其投票权离隔，并因而比其他体系更中心化。
授权股权证明机制(DPOS)
(1) 每个股东按其持股份额具有影响力，51%股东投票的成果将是不行逆且有约束力的，这点相似POS;
(2) 每个股东将其投票权颁发一名代表，获票数最多的前100位代表按既定时间表轮番发生区块。每名代表分配一个时间段来生产区块;
(3) 一切代表将收到等同于一个均匀水平的区块所含买卖费的10%作为酬劳;
(4) 该形式每30秒钟发生一个区块。
根据买卖的股权证明机制(TaPOS)
(1) 一般POS代表是短时间的；
(2) TaPOS为股东们供给了一个长效机制来直接同意他们的代表的行为;
(3) 均匀而言，51%的股东在6个月内能够直接承认每个区块;
(4) 而买卖活泼流转的股份所占的份额，则均匀10%的股东在几天内能够直接承认区块链。
