算法–一致性哈希

背景

随着时代的发展，数据量日俱增，相比纵向扩展单机的性能，人们更倾向于横向扩展，将多台一般的廉价机器组成集群来充当超级计算机，节省了大量的成本，代价是极大地增加了系统的复杂性。为了应对这些复杂性，一批又一批分布式领域的技术相继诞生，其中不乏一些看过之后令人拍案叫绝的精彩的想法。

从存储来说，数据量大的时候，一台机器不能胜任时，那么通常的做法是将数据分片，存储到多台机器上，通过集群的方式完成数据存储的需求，举个例子，你有大量的数据需要缓存，比如100G，一般的机器显然没有这么大的内存，于是不得不把这100G分布到比如10台机器上，每台存储10G的数据。数据分配的算法有很多种，一种比较容易想到的就是hash，通过将数据对10取模，hash到各个机器上。看似很美好，但是有两点因素是不得不考虑的:

1. 组成集群的机器都是廉价的小型计算机，机器故障是在正常不过的事情了。
2. 随着数据量的持续增加，你发现10台机器不够用了，想增加1台上去，过一段时间，又需要加一台。

以上两种情况有一个共同点：机器数量的变动。而机器数量变动之后，对数据重新取模时，会造成大量的缓存失效。举个例子：

• 本来10台机器，有个key是100，通过key % 10将数据均匀分布到各个机器上，这时100 % 10 = 0，这个key被分配到地0号机器上存储了，然后一台机器挂了，这时，去获取刚才存储的key，100 % 9 = 1，重新hash后，变成了去第1号机器上获取key，自然获取不到，缓存未命中，于是不得不把key重新存储到第1号机器上。

于是乎，人们感叹，如果有什么办法，能在增减机器节点的时候，不需要或者尽可能少的需要为各个key重新分配机器就好了。然后聪明绝顶的 程序员 们想出了一致性hash的办法。

一致性hash

什么是一致性hash呢？看看wiki百科上的定义：

翻译一下：

– 一致性hash是一种特殊的hash，当hash表的大小发生变化时，平均只有K/N个key需要重新计算映射关系(rehash)，这里K是hash表中key的数目，N是hash表中槽位的数目。相比之下，大多数传统的hash表实现，当hash表的大小发生变化时，几乎所有的key都需要重新映射，这是因为key和hash表槽位之间的映射是通过取模预算实现的。

现在来看看传说中的一致性hash是怎样巧妙解决rehash的问题的,借用一张图：

图中所示就是一致性hash的全貌了。下面我们来详细解释图中的细节：

1. 和一般hash表使用数组表示不太一样，一致性hash使用一个hash环来实现，因为一般的hash函数都可以返回一个int型的整数，所以将hash环平均分成2的32次方份，然后key的hashcode对2的32次方取模，一定会落到环上的一点。
2. 各个节点（比如机器名称或者ip）的hashcode经过对2的32次方取模后，也一定会落到环上的一点
3. 如果key和机器落到同一个位置，那么key存储到这个节点上，如果key没有落到某个机器节点上，那么沿着环顺时针寻找，将key存储到遇到的第一个节点上。
4. 当删除一个节点（比如机器故障）时，获取被删除的节点上存储的key时，因为节点不存在了，所以沿着环继续顺时针走，会遇到下一个节点，这样就将原属于被删除节点的key移动到了下一个节点上，而所有属于其他节点的key并不受影响，无需重新分配。

缺点

当hash环中的机器节点较少或者节点位置比较靠近时容易造成数据分布不均匀的情况，就向下面这样：

大多数key都被分配到节点A上，只有很少一部分key会被分配到节点B上，造成分布的极度不均衡。

解决办法

为了解决数据分布不均匀的缺点，我们可以在hash环中添加一些虚拟节点，使得key尽可能的均匀分布到虚拟节点上，然后把虚拟节点存储的数据映射到真实节点上即可。如下图所示：

添加虚拟节点后，key1被分配到Node B存储，key2被存储到NodeB的虚拟节点Virtual B1上存储，这样最终key1、key2被分配到了Node B上，key3、key4、key5被分配到了Node A上，比之前的分布均匀多了。

Show me the code

可以认为节点在环上是有序的，节点编号顺时针递增，C++ 中可以用map来记录机器节点在hash环中的顺序和虚拟节点到真实节点的映射，代码实现如下：

头文件：consistent_hash.h

#include <map>
#include <string>
using namespace std;

class ConsistentHash {
public:
    ConsistentHash(int node_num, int vnode_num);
    ~ConsistentHash();

    size_t GetServerIndex(const string& key);

    void DeleteNode(int index);
    void AddNode(int index);

private:
    map<size_t, size_t> server_nodes_;
    int node_num_;
    int vnode_num_;
};

实现文件：consistent_hash.cpp

#include "consistent_hash.h"
#include <sstream>
#include <functional>

ConsistentHash::ConsistentHash(int node_num, int vnode_num)
    : node_num_(node_num), vnode_num_(vnode_num) {

    for (int i = 0; i < node_num_; ++i) {
        for (int j = 0; j < vnode_num_; ++j) {
            stringstream node_key;
            node_key << "SHARD-" << i << "-NODE-" << j;
            size_t partition = hash<string>{}(node_key.str());
            server_nodes_.insert(pair<size_t, size_t>(partition, i));
        }
    }
}

ConsistentHash::~ConsistentHash() {
    server_nodes_.clear();
}

size_t ConsistentHash::GetServerIndex(const string &key) {
    size_t partition = hash<string>{}(key);
    auto it = server_nodes_.lower_bound(partition);
    if (it == server_nodes_.end()) {
        // 未找到，则返回第一个，这样就构成了一个hash环
        return server_nodes_.begin()->second;
    }
    return it->second;
}

void ConsistentHash::DeleteNode(int index) {
    for (int j = 0; j < vnode_num_; ++j){
        stringstream node_key;
        node_key << "SHARD-" << index << "-NODE-" << j;
        size_t partition = hash<string>{}(node_key.str());
        auto it = server_nodes_.find(partition);
        if (it != server_nodes_.end())
            server_nodes_.erase(it);
    }
}

void ConsistentHash::AddNode(int index) {
    for (int j = 0; j < vnode_num_; ++j) {
        stringstream node_key;
        node_key << "SHARD-" << index << "-NODE-" << j;
        size_t partition = hash<string>{}(node_key.str());
        server_nodes_.insert(pair<size_t, size_t>(partition, index));
    }
    stringstream node_key;
}

测试：main.cpp

#include "consistent_hash.h"
#include <unistd.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

int main(int argc, char* argv[]) {
    if (argc != 3) {
        cout << "usage: " << argv[0] << " sample_count data_count" << endl;
        return 0;
    }

    int sample_count = atoi(argv[1]);
    int data_count = atoi(argv[2]);

    int node_num = 5;
    int vnode_num = 100;

    auto consistent_hash = new ConsistentHash(node_num, vnode_num);

    vector<int> result(node_num, 0);   // 节点存放数据数目统计
    vector<int> data_index(data_count, -1); //数据存放节点位置， 下标是数据值i，它存放在data_index[i]上

    srand(time(nullptr));
    for (int i = 0; i < sample_count; ++i) {
        int value = (rand() + getpid()) % data_count;
        stringstream ss;
        ss << value;
        string key = ss.str();
        size_t index = consistent_hash->GetServerIndex(key);
        result[index]++;
        if (data_index[value] < 0 || int(index) != data_index[value]) {
            cout << "key = " << key << " index = " << index << endl;
        }
        data_index[value] = (int)index;
    }

    int error_index = 3;
    consistent_hash->DeleteNode(error_index);
    cout << "\nremove error node: " << error_index << endl << endl;
    for (int i = 0; i < sample_count; ++i) {
        int value = (rand() + getpid()) % data_count;
        stringstream ss;
        ss << value;
        string key = ss.str();
        size_t index = consistent_hash->GetServerIndex(key);
        result[index]++;
        if (data_index[value] < 0 || int(index) != data_index[value]) {
            cout << "key = " << key << " index = " << index << endl;
        }
        data_index[value] = (int)index;
    }


    consistent_hash->AddNode(error_index);
    cout << "\nadd new node: " << error_index << endl << endl;
    for (int i = 0; i < sample_count; ++i) {
        int value = (rand() + getpid()) % data_count;
        stringstream ss;
        ss << value;
        string key = ss.str();
        size_t index = consistent_hash->GetServerIndex(key);
        result[index]++;
        if (data_index[value] < 0 || int(index) != data_index[value]) {
            cout << "key = " << key << " index = " << index << endl;
        }
        data_index[value] = (int)index;
    }

    for(int i=0;i<node_num; ++i)
    {
        printf("index = %d, data_count = %d\n", i, result[i]);
    }

    return 0;
}

修改自：http://blog.lanjingdejia.com/articles/2018/07/13/1531479442032.html#b3_solo_h1_0