一致性hash算法
浏览:3394次 出处信息
memcach中一个具体实现算法:
初始化:
已有server m个和各自权重,构建 40*server个数*4个bucket,每个bucket实际上就是一个long值,按照权重分配给各个server,所有的bucket会分布在2的32次方的空间中,用一个TreeMap来存储。
以下是代码片段: double factor = Math .floor(((double) (40 * this.servers.length * thisWeight)) / (double) this.totalWeight); for (long j = 0; j < factor; j++) { //md5结果为16个字节,每4个一组,转成一个long值(在0到2的32次方间) byte[] d = md5.digest((servers[i] + "-" + j).getBytes()); for (int h = 0; h < 4; h++) { Long k = ((long) (d[3 + h * 4] & 0xFF) << 24) | ((long) (d[2 + h * 4] & 0xFF) << 16) | ((long) (d[1 + h * 4] & 0xFF) << 8) | ((long) (d[0 + h * 4] & 0xFF)); consistentBuckets.put(k, servers[i]); } } |
根据key来查找来分配server:
计算key的hash code,从TreeMap中查找大于它的节点,如果有则取第一个,没有则取TreeMap的第一个(相当于一个圆环)
以下是代码片段: SortedMap tmap = this.consistentBuckets.tailMap(hv); return (tmap.isEmpty()) ? this.consistentBuckets.firstKey() : tmap .firstKey(); |
建议继续学习:
- HashMap解决hash冲突的方法 (阅读:11227)
- 关于memcache分布式一致性hash (阅读:10686)
- 一致性哈希算法及其在分布式系统中的应用 (阅读:7911)
- 分布式哈希和一致性哈希 (阅读:7634)
- MinHash原理与应用 (阅读:5840)
- LVS hash size解决4096个并发的问题 (阅读:5418)
- 无锁HashMap的原理与实现 (阅读:5325)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4863)
- Ubuntu 下Hash校验和不符问题的解决 (阅读:4468)
- 分布式系统hash策略 (阅读:3745)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
文章信息
- 作者:phpor 来源: PHPor 的Blog
- 标签: hash 一致性
- 发布时间:2009-11-20 21:01:37
建议继续学习
近3天十大热文
- [67] Go Reflect 性能
- [67] Oracle MTS模式下 进程地址与会话信
- [67] 如何拿下简短的域名
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [60] 图书馆的世界纪录
- [59] android 开发入门
- [59] 【社会化设计】自我(self)部分――欢迎区
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [47] 界面设计速成