注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

google的工程师搞可以一个不需要额外空间一致性哈希算法A Fast, Minimal Memory, Consistent Hash Algorithm  

2015-03-20 00:00:57|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
直接是一个hash 函数,根据key 计算得到 num_buckets.   不过有个缺点是要求 bucket(server) 是数字连续的。也就是说一台挂了得有另外一台补上,不能不出现不连续的bucket号码

http://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf
A Fast, Minimal Memory, Consistent Hash Algorithm 
         John Lamping, Eric Veach
         Google 

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets)
{
int64_t b = -1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
}


  评论这张
 
阅读(300)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017