网关高可用协议：HSRP、VRRP、GLBP、CASP

网络中网关设备负责完成大部分的高级处理，因此网关设备的高可用十分重要。常见的高可用协议包括 HSRP、VRRP、GLBP、CASP。基本原理都是在一个组里面选出一个主节点，拿到虚的网关 IP 和 虚 MAC。这些协议也可以提供 IP 节点的高可用保护。

HSRP

全称是 Hot Standby Routing Protocol，Cisco 家 98 年公开的专利协议，在 RFC 2281 中给出。

一主一从，其它为监听状态。组内多播到 224.0.0.2（v1）或 224.0.0.102（v2），虚地址不能跟物理地址重复，虚 MAC 地址为00-00-0c-07-AC-XX。

基本只有 Cisco 家设备支持。

VRRP

全称是 Virtual Route Rendundancy Protocol，IETF 的标准协议，在 RFC 3768 和 RFC 5798 中给出。设计思路是基于 HSRP，所以两者之间在概念上有很多相似之处，但并不兼容。

一主多从。组内 IP 多播到 224.0.0.18，IP 协议号为 112。虚地址可以复用物理地址，虚 MAC 为 00-00-5E-00-01-XX。

除了 Cisco，别家硬件支持的较多，另外有开源软件实现，Linux 上的 VRRPd。

用 VRRPd 配置的话很简单，指定网卡，本机的优先级，所属的组号和虚 IP 即可，例如

$ vrrp –i eth0 –p 24 –v 1 192.168.1.1

GLBP

GLBP 也是 Cisco 家的私有协议，基于 HSRP，最大的改进是考虑了负载均衡。特别之处的设计在于通过激活的虚网关（Active Virtual Gateway）来负责响应网络中的 ARP 请求，虚网关会根据权重来答复不同的成员的虚 MAC 地址。

组内多播到 224.0.0.2（v1）或 224.0.0.102（v2），协议基于 UDP，目标和源端口都是 3222。

最多同时可有 4 个转发网关。

CASP

全称是 Common Address Redundancy Protocol，非标准协议，最初是为了避免 HSRP 的专利风险，由 OpenBSD 在 2003 年完成的全新的设计，加强了安全性，带有负载均衡功能。

分布式系统中的算法设计（一） -- 一致性 Hash

Hash 大家都知道，把某个要存储的内容的索引 key 通过某个规则计算一下，算出来一个值，这个值往往范围比原来小，且概率意义上不会冲突。

由于 Hash 计算复杂度往往比查找要快，被大量应用到各种大规模的系统中，特别是分布式系统。具体实践中有几个典型的问题。

问题来源

一致性 Hash 讨论地已经很多，基本故事就是分布式存储系统中，通过 Hash 来决定内容存到哪个节点上。

典型的比如 cache 系统，后面放若干节点，查找某个 key，hash 到某个节点，再进一步检索。

最简单的自然是按照节点数量取个模，理想状态下不会有啥问题。

但是如果发生如下情况，就无法正常工作了。 加节点（一般是有计划的） 减节点（可能突然故障，无法预知）

所以提出了一致性 hash，即考虑如下四个方面的算法： 平衡性(Balance)：哈希结果尽可能分布到所有的节点，这样可以使得所有的节点都得到利用； 单调性(Monotonicity)：加入新的节点后，已经分配节点的 hash 结果 被映射到原有的或者新的节点上去，而不会被映射到其他节点； 分散性(Spread)：同样内容尽量避免 hash 到不同节点； 负载(Load)：不同内容避免 hash 到同样节点。

简单的说，就是有一个算法，首先分配尽量均匀，其次，当节点个数变化的时候，尽量维持原来内容的映射，并进行局部调整。

能满足的算法有很多，这里介绍两个比较经典的。

基于环的实现

该算法最初于 1997 年在论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web 中提出。算法复杂度为 O(log(n))。

主要设计思想为：构造一个环（顺序标上编号比如 0 ~ 2^32-1），将已有节点编号并分配到这个环上，分割环为不同的段。

对每个内容，hash 后是一个独一无二的数字，这个数字肯定会落入某个段上，按照固定方向往前找到的第一个节点编号即为要分配到的节点。

考虑两个相邻的节点 A 和 C，如果要在中间添加一个节点 B，那么 AB 段上内容会从 C 节点重新分配到 B 节点。反之，如果删除掉 B 节点，那么 AB 段上内容会再次分配到 C 节点上。

这种算法很好的满足性质 2-4，唯独平衡性没有解决。即当节点个数不多的时候，内容可能会集中在某些段，划分到部分节点上。要解决这个问题也很简单，把一个节点虚拟为多个虚节点，提高整体节点个数，然后再分散放到环上。这样就提高了平衡性。

基于概率转移的实现

该算法最初于 2014 年在论文 A Fast, Minimal Memory, Consistent Hash Algorithm 中由 Google 工程师 John Lamping 和 Eric Veach 提出。算法复杂度为 O(log(n))。

主要设计思想为：假设原先有 n 个节点，新加上一个节点后，每个 key 都有 1/n+1 的概率转移到新的节点上，n/n+1 的概率留在原先分配的节点。

举个例子，原先有 1 个节点，再加一个节点，那么已有内容有 1/2 的概率跳转到到第二个节点。原先有 2 个节点（每个里面有 1/2 的内容），再加一个节点，则已分配内容应该有 1/3 的概率转移到新的节点。

一个简单的实现代码为：

int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; // This will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j++) {
        if (random.next() < 1.0/(j+1)) b = j ;
    }
    return b;
}

即根据 key 生成 num_buckets-1 个（0~1.0）的伪随机数，依次检查随机数序列：

• 第一个随机数 <1/2，则放第二个节点；
• 第二个随机数 <1/3，则放第三个节点；
• ...

注意伪装随机数序列由 key 唯一确定。意味着同样的内容在多次分配中，分配结果将是一致的。

另外，可以计算出如果当前分配为 b，下一个结果 j >= i 的概率（即 b+1 到 i-1 的过程都不发生跳变）

P(j>=i) = (b+1)/i

最终优化为如下代码：

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

这个算法依赖于伪随机算法的输出，特点有： 分布均匀性由伪随机算法决定，而跟 key 自身均匀性无关，实践均匀性远好于基于环的算法； 不需要对 key 进行计算，复杂度低，实践计算时间也比基于环的算法好。

算法没解决的问题：当中间减掉节点的时候，序号会发生变化，变为 0...n-1。因此需要在外面维护一个映射关系，动态映射到原先的节点上。