2020-01-02

一致性HASH的原理和实现

1. HASH Function & HASH Table
2. 一致性HASH
参考

一致性HASH的概念在我们的工作中经常会用到，例如对于集群中一些有状态的服务，我们希望对于同一个玩家的请求总是由固定的服务器来处理，且不会因为该服务的扩缩容而导致请求失效，即转发到了其他服务器处理。那么为什么一致性HASH可以保证被映射到某个服务的请求持久有效呢？

一致性HASH(Consistent Hashing)(维基)定义：一种特殊的HASH，在HASH表大小发生变化时，只有$K/n$个key需要进行重新映射(K是总key的个数，n是节点个数)。在介绍一致性HASH之前先回顾一下HASH的相关知识。

1. HASH Function & HASH Table

HASH函数是指可以将任意长度数据映射到固定长度的值的函数的统称。HASH函数需要具有以下三个功能：

将可变长度的key转换成固定长度的value，例如按word进行奇偶校验来对key进行折叠，像ADD/XOR操作。
对输入的key进行置乱来使计算的value结果能够均匀分布。
将产生的HASH value映射到固定的table中。这是HASH table的要求。

HASH函数有以下几点基本特性：

相同的key，生成的HASH value一定是相同的；
不同的key，生成的HASH value有可能是相同的；
不同的HASH value，对应的key一定是不同的；

一个好的HASH函数应该保证以下基本两点：

HASH value的计算过程要很快；
HASH value冲突的概率要小；

这两点在实际应用过程中是很重要的，就像平时看到的口号:”又快又好！”。

HASH表是通过HASH函数的返回值用来进行索引一个固定大小的table。它是HASH函数的一个主要应用。C++中提供的unordered_map就是HASH表的一个实现。

通过HASH函数来索引HASH表的过程称之为hashing即哈希法或散列法。hashing的目的就是通过HASH表将key/value对进行分散存储，以提高检索效率。对于一个给定的key，计算其索引的方式可以表示如下：

index = f(key, array_size)
//经常分为如下两步
hash_value = hashfunc(key)
index = hash_value % array_size

由上述HASH index的计算过程可以知道，在某个节点故障或者添加节点的时候，由于array_size发生变化，可能会导致所有key最终生成的index全部都发生变化，导致节点的映射发生变化。这对于一些分布式的服务中缓存的cache会失效，因为之前的请求可能会被转发到其他server，这会使系统的性能带来急剧的下降，这是我们不希望看到的。如下图所示ServerN的故障就会导致之前的key的映射关系发生变化：

ServerN故障后：

那有没有一个好的映射方法，能够保证在某个节点发生故障时，只会影响当前节点的映射关系，而不会影响到其他的节点的映射呢？

2. 一致性HASH

那就是一致性哈希(consistent hashing)，这个算法是MIT的Karger在1997年发表的论文(Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web )中为了解决分布式缓存而设计的。一致性哈希的核心思想就是将每个服务节点与一个HASH值区间关联起来。然后一致性哈希会将每个请求对象通过同样的HASH将其映射到某个HASH值区间上，从而关联到对应的服务节点。当添加或删除节点时，变动的只有对应节点HASH值区间的对象需要变动，即只有$K/n$个key需要进行重新映射(K是总key的个数，n是节点个数)。

一致性HASH的四个重要特性如下：

Balance：平衡性，hash函数对于输入items能够均匀的映射到每个bucket。
Monotonicity：单调性，某个item映射到bucket A1，此时如果新加入了一个bucket A3，那么此item的映射关系可能从bucket A映射到bucket A3，但绝不会映射到旧的bucket A2中。
Spread：分散性，分布式的系统中，每个终端可能看到的bucket集群是不一致的，所以最终会导致相同的items被映射到不同的bucket中。这种情况是要避免，分散性要越低越好。
Load：负载，和Spread概念相似，只不过是用来描述bucket中被不同的用户映射为不同的item。负载也是越低越好。

2.1 单调性

Karger提出的一致性HASH算法的思想前面也说了就是：将每个服务节点与一个HASH值区间关联起来，为了能够让所有请求都能映射到一个服务节点，这就要求所有服务节点生成的HASH值区间必须是连续且是收尾相连的，其实就是一个环。Karger在其后的一片论文(Web Caching with Consistent Hashing)中阐述了一致性HASH的一种简单实现：采用的HASH函数将string的输入映射到一个数字区间[0, M]，可以把该区间认为是一个单位圆，然后将所有服务节点都映射到圆上的某个点，然后将每个请求通过同样的HASH映射到该圆上的某个点，该请求item映射到圆上的点，以顺时针找到与之最近的服务节点。

如下图：三个服务节点S1，S2，S3通过HASH映射到圆上的三个点：

三个请求K1，K2，K3通过同样的HASH函数映射到圆上的三个点，然后通过逆时针找到最近的服务节点，如下所示：

上述两步一般的HASH算法都可以做到，那一致性hash的是为了解决什么呢？就是为了解决在HASH表大小发生变化时，只有$K/n$个key需要进行重新映射，即保证在某个节点发生故障时，只会影响当前节点的映射关系，而不会影响到其他的节点的映射！如下图，当S3服务节点出现故障时，请求K3会被转发到S2上：

同样对于新加入的服务节点S4让原有映射到S3的请求K3重新映射到了S4，对于新加入的节点只影响到了原有映射到S3部分区间，这就是一致性HASH的核心：单调性。

2.2 平衡性(数据倾斜问题)

我们知道在HASH函数的应用中，对于HASH函数好坏判断的一个重要指标就是平衡性。很多比较常见的HASH函数：BKDR， DJB，FNV，CRC32其实都相对好的平衡性，同样一致性HASH平衡性也至关重要，既然很多HASH函数能够提供很好的平衡性，那么是不是一致性HASH就直接按上述的实现就可以了呢？

我们看上图中只有三个服务节点的情况下：假设三个请求被均匀的映射到了三个服务节点，在S3挂了之后，K3就会被映射到S2，你会发现有什么问题？本来三个服务节点各分担了33%的流量，但当S3挂了后，S1还是分担了33%的流量，而S2则分担了66%的流量。

一致性HASH为了解决在服务节点少的情况下且遇到故障时不能平衡性的问题，作者Karger在论文中提出了:一致性HASH需要将C个服务节点拷贝k份，也就是大家说的构建虚拟节点。将每个节点拷贝100份，生成的HASH圆环简要信息如下：此时如果S3挂了，基本上可以保证S1和S2各承担50%的流量，保证了平衡性。

此时如果S3挂了，S3所有的虚拟节点都会失效，但是可以保证S1和S2各承担50%的流量，保证了平衡性。这在分布式系统设计中是很关键的，这样可以最大程度的减少由于部分节点失效所带来的系统不稳定性。

但这里拷贝多少份呢？当建立的虚拟节点过多时就会影响一致性HASH的查找性能。

2.3 实现

下面一致性HASH的实现，主要有三个接口：

AddNode：添加服务节点；添加服务节点时都自动进行虚拟节点的创建；
DelNode：删除服务节点；
GetNode：根据请求数据获取映射的服务节点；

#include <string>
#include <map>
#include <cstdint>
#include <sstream>
#include <iostream>

template<typename T>
std::string ToString(const T & t) 
{
    std::ostringstream os;
    os<<t;
    return os.str();
}

template<typename Node, typename Data, typename Hash>
class ConsistentHash
{
public:
    ConsistentHash(uint32_t _virtual_nodes = 100) 
        : hash_(Hash()), virtual_nodes_(_virtual_nodes)
    {}

    void AddNode(const Node & node)
    {
        std::string str_node = ToString(node);
        for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
        {
            std::string key = str_node + "_" + ToString(loop_i);
            uint64_t hash_value = hash_(key);
            unit_circle_.insert(std::make_pair(hash_value, node));
        }
    }

    void DelNode(const Node & node)
    {
        std::string str_node = ToString(node);
        for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
        {
            std::string key = str_node + "_" + ToString(loop_i);
            uint64_t hash_value = hash_(key);
            unit_circle_.erase(hash_value);
        }
    }

    const Node * GetNode(const Data & data) const
    {
        if(unit_circle_.empty())
            return nullptr;

        uint64_t hash_value = hash_(ToString(data));
        auto itr = unit_circle_.lower_bound(hash_value);
        if(itr == unit_circle_.end())
            return &unit_circle_.begin()->second;
        return &itr->second;
    }

private:
    std::map<uint64_t, Node> unit_circle_;
    uint32_t virtual_nodes_;
    Hash hash_;
};

在添加完所以节点后，可以通过计算每个节点对应区域在单位圆上的占比来统计一致性HASH的分布均匀性，如下计算方式：

void PrintBalacne() const
   {
       std::map<uint64_t, uint64_t> distribute_map;

       uint64_t last_val = 0;
       for(auto & val : unit_circle_)
       {
           auto itr = unit_circle_.upper_bound(val.first);
           if(itr == unit_circle_.end())
               distribute_map[val.second] += uint64_t(-1) - val.first + unit_circle_.begin()->first;

           distribute_map[val.second] += itr->first - val.first;
       }

       for(auto & val : distribute_map)
           std::cout<<val.first<<":"<<val.second<<":"<<val.second * 1.0 / uint64_t(-1)<<std::endl;
   }

下面是通过CityHash进行的测试，主要是为了测试服务节点在某个节点下线后，数据映射均衡性问题：

int main()
{
    ConsistentHash<uint32_t, uint32_t, CityHasher> consistent_hash;
    for(uint32_t loop_i = 1; loop_i <= 5; ++loop_i)
        consistent_hash.AddNode(loop_i);

    consistent_hash.PrintBalacne();

    consistent_hash.DelNode(3);

    consistent_hash.PrintBalacne();
}