一致性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的设计和实现变得非常的简单,同时留给用户以极大的灵活性和可定制性。
后面的例子中将介绍如何实现虚拟节点。

模板参数

  1. T: consistent hash的节点类型。
  2. Hash: 一元函数对象。接收T类型对象作为参数,返回一个整形作为其hash值,该hash值将被用于内部的排序。Hash需在其内部定义result_type 指明返回整形的类型。
  3. Alloc: 内存分配器,默认为std::allocator

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; 
}
来自:http://my.oschina.net/u/90679/blog/188750
昵    称:
验证码:

相关文档:

  • C语言的BASE64处理 b64
    b64 是很很小型的、简单而且搞笑的 Base64 编码和解码的 C 语言库,无需依赖其他第三方的程序库,支持各种操作系统。同时也包含一个灵...
  • C++格式化输出库 FastFormat
    FastFormat 是一个C/C++格式化输出的库,输入的参数是类型安全的/范型的/可扩展的。...
  • C/C++ 代码文档生成器:cldoc
    cldoc 是一个使用 clang 实现的 C/C++ 代码文档生成器。...
  • 底层的 C 程序库 skalibs
    skalibs 是一组用于一般用途的、底层的 C 程序库,可替换标准 C 库的一些方法,主要用于构建很小的静态二进制文件。...
  • C++书籍推荐
    本文内容来自国外著名编程问答网站Stackoverflow评选的C++推荐书单!推荐大家看原版英文,但这些书大部分也都有中文版!...
  • OpenDDS:数据分布式服务(DDS)的C++实现
    OpenDDS 是一个开源的 C++ 实现的 对象管理组织 OMG 的 数据分布式服务 (DDS) 。...
  • C++各大有名库的介绍之C++标准库
    标准库中提供了C++程序的基本设施。虽然C++标准库随着C++标准折腾了许多年,直到标准的出台才正式定型,但是在标准库的实现上却很令...
  • C语言和抽象思维(二)
    上一次我们说到C语言结合抽象思维完成一个非所见即所得的编辑器, 并且我们已经定义了这个编辑器应有的行为, 基本上抽象也已经完...
  • C++模板库 Standard Portable Library
    Standard Portable Library 是一个指针友好的 C/C++ 标准模板库的替代产品,它所提供的 API 跟 Java 或者是 .NET 的语言类似,包括公用的数据结构...
  • C++ Web应用服务器:MYCP
    MYCP是用于开发、集成、部署和管理大型分布式应用、网络应用和数据库应用的C++ Web应用服务器,拥有高性能、高可用性和可扩展性。...
  • C++11语言扩展:常规特性
    本节内容:auto、decltype、基于范围的for语句、初始化列表、统一初始化语法和语义、右值引用和移动语义、Lambdas、noexcept防止抛出异常、...
  • C++ STL set集合容器常用用法
    set集合容器:实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每...
  • C++11 中委派 (Delegates) 的实现
    在 C++ 中通过一个全局函数来绑定到对象的成员函数是很有用的,这个特性也存在于其他语言中,例如 C#的委派。在 C++ 中相当于成员函...
  • C++异常处理
    C++异常处理...
  • vim c/c++智能补全插件
    我很喜欢vim,而且一直用,不过对于c/c++只能补全一直都没有一个很好的解决方案,虽然有个插件(omnicomplete)功能比较强大,跟eclipse等...
  • C++的Twitter开发包 twitlib
    twitlib 是一个 C++ 的 Twitter 客户端开发包,现已改名为 QTwitLib。...
  • C++的IO库 MeteoIO
    MeteoIO 是一个跨平台的 C++ 库,提供数据的格式化和协议无关的数据访问,提供安全可靠的I/O处理。...
  • zip文件C语言解析包 ZZIPlib
    ZZIPlib 是一个轻量级的用来从ZIP文件抽读取文件的C语言包,同时也可以用来将多个文件压缩成zip格式,采用的是 zlib 库开发。...
  • C++二叉查找树实现过程详解
    在数据结构中,有一个奇葩的东西,说它奇葩,那是因为它重要,这就是树。而在树中,二叉树又是当中的贵族。二叉树的一个重要应用...
  • C++ Virtual详解
    Virtual是C++ OO机制中很重要的一个关键字。只要是学过C++的人都知道在类Base中加了Virtual关键字的函数就是虚拟函数(例如函数print),于...