文档章节

一致性hash的C++实现

江浸月
 江浸月
发布于 2013/12/29 23:12
字数 1212
阅读 4714
收藏 90

一致性哈希的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; 
}

© 著作权归作者所有

共有 人打赏支持
江浸月

江浸月

粉丝 39
博文 9
码字总数 18652
作品 2
深圳
程序员
加载中

评论(4)

pww71
pww71
https://sourceforge.net/projects/pwwhashmap/?source=navbar
看看这个哈希算法
江浸月
江浸月

引用来自“Sail_鸢”的评论

最近我们也在搞这个。。。

0
Sail_鸢
Sail_鸢
最近我们也在搞这个。。。
Sail_鸢
Sail_鸢
顶~~~高大师
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
0
0
Linux C++、Boost、ACE ......

Linux/UNIX、C++、Boost、ACE、Shell ...... Linux/UNIX C++高级培训---远程班 培养目标:Linux/UNIX C++高级软件工程师 专注Linux/UNIX服务器端的软件开发(后台开发),培养企业所需的专业...

athxy
2010/04/01
0
1
C语言/C++编程学习未来之路

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
03/30
0
0
Effective STL - 容器

STL(standard template library)提供了一组表示容器,迭代器,函数对象和算法的模板。容器是一个与数组类似的单元,可以存若干个值。 STL容器是同质的,即存储的值的类型相同;算法是完成特...

積木leayn
2013/10/07
0
0
C++ STL编程轻松入门 2

1.3.3 STL和GP,GP和OOP   正如前面所提到的,在STL的背后蕴含着泛型化程序设计(GP)的思想,在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的...

暖冰
2015/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

新工作与老项目

新的工作不知不觉的干了一个多月了。怎么说呢,跟想象中的差别不少,本来想的能进来跟大公司的同事能有很多交流,能在团队中跟大牛学习更快。结果公司的这个项目上只有两个程序员,项目是十年...

zypy333
15分钟前
0
0
mysql 在windows的安装

mysql 在windows的安装。 mysql64位的server的下载地址是: https://dev.mysql.com/downloads/mysql/ 使用的是5.7版本。 下载安装包,解压至D:\mysql\mysql-5.7.23-winx64\ 在D:\mysql\mysq...

lxzh504
27分钟前
1
0
云技术、大数据(hadoop)入门常见问题回答

当我们学习一门新技术的时候,我们总是产生各种各样的问题,这些问题整理出来,包括该 1.如何学习hadoop? 2.hadoop常见问题? 3.还有hbase、hive安装使用等? 你知道搭建hadoop平台需要些什...

董黎明
27分钟前
1
0
小程序自定义底部tab

场景 1.tabBar是在内页而非首页,这时就不得不自定义一个tabBar了 2.自定义风格 3.子页数量超过5个,得到更多了tab 4.改变点击tab默认事件,比如出登录界面,或者弹出上拉子菜单等 步骤 1.照...

萤火的萤火
33分钟前
1
0
shell炫技

1.为脚本添加“--help” #!/bin/shif [ ${#@} -ne 0 ] && [ "${@#"--help"}" = "" ]; then printf -- '...help...\n'; exit 0;fi; 2.输出字体添加颜色 https://misc.flogisoft.com......

HJCui
33分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部