您的位置: 网界网 > 网络学院-技术开发 > 正文

一致性hash的C++实现

2014年06月19日 20:38:39 | 作者:佚名 | 来源:51CTO | 查看本文手机版

摘要:一致性哈希的C 实现 一致性哈希是分布式计算领域被广泛应用的一个算法。在许多分布式系统包括 Amazon Dynamo, memcached, Riak 等中都有使用。 一致性哈希的原理比较简单,网上有很多介绍的比较好的文章,也有一些相关的代码...

标签
hashC++

一致性哈希的C 实现

一致性哈希是分布式计算领域被广泛应用的一个算法。在许多分布式系统包括 Amazon Dynamo, memcached, Riak 等中都有使用。

一致性哈希的原理比较简单,网上有很多介绍的比较好的文章,也有一些相关的代码,但是都不太令人满意,因此自己实现了一个。代码很简单,放在了github上面。

consistent_hash_map

一致性哈希的功能被封装在模板类consistent_hash_map中:

  1. template <typename T, 
  2.         typename Hash, 
  3.         typename Alloc = std::allocatorconst typename Hash::result_type,T > > > 
  4. 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

member type

  1. size_type           Hash::reslut_type               hash函数返回值的类型 
  2. value_type          std::pair<const size_type,T>    first为节点的哈希值,second为节点 
  3. iterator            a bidirectional iterator to value_type  双向迭代器 
  4. reverse_iterator    reverse_iterator      反向迭代器 

member function

  1. std::size_t size() const
  2. 返回consistent_hash_map内的节点数量。 
  3.  
  4. bool empty() const
  5. 判断consistent_hash_map是否为空 
  6.  
  7. std::pairbool> insert(const T& node); 
  8. 插入一个节点,如果返回值中bool变量为真(+本站微信networkworldweixin),iterator则为指向插入节点的迭代器。如果bool为假,表示插入失败。 
  9. 插入失败因为节点已经存在或者是节点的hash值与其他节点发生冲突。 
  10.  
  11. void erase(iterator it); 
  12. 通过迭代器删除指定节点。 
  13.  
  14. std::size_t erase(const T& node); 
  15. 通过节点值删除指定节点。 
  16.  
  17. iterator find(size_type hash); 
  18. 通过传入的hash值找对其在consistent_hash中对应的节点的迭代器。 
  19.  
  20. iterator begin(); 
  21. iterator end(); 
  22. 返回对应迭代器 
  23.  
  24. reverse_iterator rbegin(); 
  25. reverse_iterator rend(); 
  26. 返回对应的反向迭代器 

虚拟节点的例子

整个例子的完整代码在这。

在这个例子中,我们首先定义虚拟节点类型,和其对应的hasher。

  1. #include  
  2. #include  
  3. #include  
  4.  
  5. #include "consistent_hash_map.hpp" 
  6.  
  7. //所有主机的列表 
  8. const char* nodes[] = { 
  9.     "192.168.1.100"
  10.     "192.168.1.101"
  11.     "192.168.1.102"
  12.     "192.168.1.103"
  13.     "192.168.1.104" 
  14. }; 
  15.  
  16. //虚拟节点 
  17. struct vnode_t { 
  18.     vnode_t() {} 
  19.     vnode_t(std::size_t n,std::size_t v):node_id(n),vnode_id(v) {} 
  20.  
  21.     std::string to_str() const { 
  22.         return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id); 
  23.     } 
  24.  
  25.     std::size_t node_id; //主机ID,主机在主机列表中的索引 
  26.     std::size_t vnode_id; //虚拟节点ID 
  27.  
  28. }; 
  29.  
  30. //hasher,使用CRC32作为hash算法,注意需要定义result_type 
  31. struct crc32_hasher { 
  32.     uint32_t operator()(const vnode_t& node) { 
  33.         boost::crc_32_type ret; 
  34.         std::string vnode = node.to_str(); 
  35.         ret.process_bytes(vnode.c_str(),vnode.size()); 
  36.         return ret.checksum(); 
  37.     } 
  38.     typedef uint32_t result_type; 
  39. }; 

为每个主机生成100个虚拟节点,然后加入consistent_hash_map中。

  1. typedef consistent_hash_map consistent_hash_t; 
  2. consistent_hash_t consistent_hash_; 
  3.  
  4. for(std::size_t i=0;i<5; i) { 
  5.     for(std::size_t j=0;j<100;j ) { 
  6.         consistent_hash_.insert(vnode_t(i,j)); 
  7.     } 

查找某个hash值对应的vnode 和 主机:

  1. consistent_hash_t::iterator it; 
  2. it = consistent_hash_.find(290235110); 
  3. //it -> first是该节点的hash值,it -> second是该虚拟节点。 
  4. std::cout<"node:%1%,vnode:%2%,hash:%3%")  
  5.             % nodes[it->second.node_id] % it->second.vnode_id % it->first << std::endl; 

遍历consistent_hash中的所有的vnode,统计每个虚拟节点的key的数量和每个主机包含key的数量:

  1. std::size_t sums[] = {0,0,0,0,0}; 
  2. consistent_hash_t::iterator i = consistent_hash_.begin(); //第一个节点 
  3. consistent_hash_t::reverse_iterator j = consistent_hash_.rbegin(); //最后一个节点 
  4. std::size_t n = i->first   UINT32_MAX - j->first; //计算第一个节点包含的key的数量 
  5. std::cout<"vnode:%1%,hash:%2%,contains:%3%")  
  6.         % i->second.to_str() % i->first % n << std::endl; 
  7. sums[i->second.node_id]  = n; //更新主机包含的key数量。 
  8.  
  9. //计算剩余所有节点包含的key的数量,并更新主机包括的key的数量。 
  10. uint32_t priv = i->first; 
  11. uint32_t cur; 
  12. consistent_hash_t::iterator end = consistent_hash_.end(); 
  13. while( i != end) { 
  14.     cur = i->first; 
  15.     n = cur - priv; 
  16.     std::cout<"vnode:%1%,hash:%2%,contains:%3%")  
  17.         % i->second.to_str() % cur % n << std::endl; 
  18.     sums[i->second.node_id]  = n; 
  19.     priv = cur; 
  20.  
  21. for(std::size_t i=0;i<5; i) { 
  22.     std::cout<"node:%1% contains:%2%") % nodes[i] % sums[i] <

原文链接:http://my.oschina.net/u/90679/blog/188750

[责任编辑:孙可 sun_ke@cnw.com.cn]