一致性哈希的C++實現

一致性哈希是分布式計算領域被廣泛應用的一個算法。在許多分布式系統包括 Amazon Dynamo, memcached, Riak 等中都有使用。
一致性哈希的原理比較簡單，網上有很多介紹的比較好的文章，也有一些相關的代碼，但是都不太令人滿意，因此自己實現了一個。代碼很簡單，放在了 github 上面。

consistent_hash_map

一致性哈希的功能被封裝在模板類consistent_hash_map中：

template <typename T,
        typename Hash,
        typename Alloc = std::allocator<std::pair<const typename Hash::result_type,T > > >
class consistent_hash_map

consistent_hash_map 使用了stl map風格的接口。實際上其內部也使用了std::map 來管理和維護所有節點。

consistent_hash_map只提供最基本的一致性hash的功能，并不直接支持虛擬節點的概念，但是虛擬節點的概念可以很容易的通過定制的T 和 Hash類型來實現。這樣設計的好處在于可以使consitent_hash_map的設計和實現變得非常的簡單，同時留給用戶以極大的靈活性和可定制性。
后面的例子中將介紹如何實現虛擬節點。

模板參數

1. T: consistent hash的節點類型。
2. Hash: 一元函數對象。接收T類型對象作為參數，返回一個整形作為其hash值，該hash值將被用于內部的排序。Hash需在其內部定義result_type 指明返回整形的類型。
3. Alloc: 內存分配器，默認為std::allocator
</ol>

member type

size_type           Hash::reslut_type               hash函數返回值的類型
value_type          std::pair<const size_type,T>    first為節點的哈希值，second為節點
iterator            a bidirectional iterator to value_type  雙向迭代器
reverse_iterator    reverse_iterator<iterator>      反向迭代器

member function

std::size_t size() const;
返回consistent_hash_map內的節點數量。

bool empty() const;
判斷consistent_hash_map是否為空
std::pair<iterator,bool> insert(const T& node);
插入一個節點，如果返回值中bool變量為真，iterator則為指向插入節點的迭代器。如果bool為假，表示插入失敗。
插入失敗因為節點已經存在或者是節點的hash值與其他節點發生沖突。
void erase(iterator it);
通過迭代器刪除指定節點。
std::size_t erase(const T& node);
通過節點值刪除指定節點。
iterator find(size_type hash);
通過傳入的hash值找對其在consistent_hash中對應的節點的迭代器。
iterator begin();
iterator end();
返回對應迭代器
reverse_iterator rbegin();
reverse_iterator rend();
返回對應的反向迭代器</pre> 
虛擬節點的例子

整個例子的完整代碼在這。 

在這個例子中，我們首先定義虛擬節點類型，和其對應的hasher。

#include <stdint.h>

include <boost/format.hpp>
include <boost/crc.hpp>
include "consistent_hash_map.hpp"
//所有主機的列表
const char* nodes[] = {
    "192.168.1.100",
    "192.168.1.101",
    "192.168.1.102",
    "192.168.1.103",
    "192.168.1.104"
};
//虛擬節點
struct vnode_t {
    vnode_t() {}
    vnode_t(std::size_t n,std::size_t v):node_id(n),vnode_id(v) {}

std::string to_str() const {
    return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id);
}

std::size_t node_id; //主機ID,主機在主機列表中的索引
std::size_t vnode_id; //虛擬節點ID


};
//hasher,使用CRC32作為hash算法，注意需要定義result_type
struct crc32_hasher {
    uint32_t operator()(const vnode_t& node) {
        boost::crc_32_type ret;
        std::string vnode = node.to_str();
        ret.process_bytes(vnode.c_str(),vnode.size());
        return ret.checksum();
    }
    typedef uint32_t result_type;
};</pre> 
為每個主機生成100個虛擬節點，然后加入consistent_hash_map中。

typedef consistent_hash_map<vnode_t,crc32_hasher> consistent_hash_t;
consistent_hash_t consistenthash;

for(std::size_t i=0;i<5;++i) {
    for(std::size_t j=0;j<100;j++) {
        consistenthash.insert(vnode_t(i,j));
    }
}</pre> 
查找某個hash值對應的vnode 和 主機：

consistent_hash_t::iterator it;
it = consistent_hash_.find(290235110);
//it -> first是該節點的hash值，it -> second是該虛擬節點。
std::cout<<boost::format("node:%1%,vnode:%2%,hash:%3%") 
            % nodes[it->second.node_id] % it->second.vnode_id % it->first << std::endl;
 
遍歷consistent_hash中的所有的vnode,統計每個虛擬節點的key的數量和每個主機包含key的數量：

std::size_t sums[] = {0,0,0,0,0};
consistent_hash_t::iterator i = consistenthash.begin(); //第一個節點
consistent_hash_t::reverse_iterator j = consistenthash.rbegin(); //最后一個節點
std::size_t n = i->first + UINT32_MAX - j->first; //計算第一個節點包含的key的數量
std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%") 
        % i->second.to_str() % i->first % n << std::endl;
sums[i->second.node_id] += n; //更新主機包含的key數量。

//計算剩余所有節點包含的key的數量,并更新主機包括的key的數量。
uint32_t priv = i->first;
uint32_t cur;
consistent_hash_t::iterator end = consistenthash.end();
while(++i != end) {
    cur = i->first;
    n = cur - priv;
    std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%") 
        % i->second.to_str() % cur % n << std::endl;
    sums[i->second.node_id] += n;
    priv = cur;
}
for(std::size_t i=0;i<5;++i) {
    std::cout<<boost::format("node:%1% contains:%2%") % nodes[i] % sums[i] <<std::endl; 
}</pre>來自：http://my.oschina.net/u/90679/blog/188750