一致性hash的C++實現

一致性哈希的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的設計和實現變得非常的簡單，同時留給用戶以極大的靈活性和可定制 性。

後面的例子中將介紹如何實現虛擬節點。

模板參數

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(); 
返回對應的反向迭代器 

虛擬節點的例子

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

在這個例子中，我們首先定義虛擬節點類型，和其對應的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; 
}; 

為每個主機生成100個虛擬節點，然後加入consistent_hash_map中。

typedef consistent_hash_map<vnode_t,crc32_hasher> consistent_hash_t; 
consistent_hash_t consistent_hash_; 
 
for(std::size_t i=0;i<5;++i) { 
    for(std::size_t j=0;j<100;j++) { 
        consistent_hash_.insert(vnode_t(i,j)); 
    } 
} 

查找某個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 = consistent_hash_.begin(); //第一個節點 
consistent_hash_t::reverse_iterator j = consistent_hash_.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 = consistent_hash_.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;