doublejump - 又快又简洁的一致性哈希库,Google Jump 算法的改进版

edwingeng · 2018-11-17 17:34:05 · 3191 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2018-11-17 17:34:05 的主题,其中的信息可能已经有所发展或是发生改变。

Overview

doublejump 的核心是 Google Jump 一致性哈希算法,这个实现弥补了该算法的最大缺点:不能删除节点。

Benchmark

BenchmarkDoubleJumpWithoutLock/10-nodes      50000000     27.6 ns/op
BenchmarkDoubleJumpWithoutLock/100-nodes     30000000     42.7 ns/op
BenchmarkDoubleJumpWithoutLock/1000-nodes    30000000     54.1 ns/op

BenchmarkDoubleJump/10-nodes                 20000000     72.9 ns/op
BenchmarkDoubleJump/100-nodes                20000000     86.1 ns/op
BenchmarkDoubleJump/1000-nodes               20000000     97.9 ns/op

BenchmarkStathatConsistent/10-nodes           5000000    301 ns/op
BenchmarkStathatConsistent/100-nodes          5000000    334 ns/op
BenchmarkStathatConsistent/1000-nodes         3000000    444 ns/op

BenchmarkSerialxHashring/10-nodes             5000000    280 ns/op
BenchmarkSerialxHashring/100-nodes            5000000    340 ns/op
BenchmarkSerialxHashring/1000-nodes           3000000    427 ns/op

Example

h := NewHash()
for i := 0; i < 10; i++ {
    h.Add(fmt.Sprintf("node%d", i))
}

fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

h.Remove("node3")
fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

// Output:
// 10
// 10
// node9
// node2
// node3
// 9
// 10
// node9
// node2
// node0

有疑问加站长微信联系(非本文作者)

第 1 条附言  ·  2018-11-18 09:28:14

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3191 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传