Golang实现高性能跳转一致性哈希算法插件库doublejump的使用

概述

Doublejump是对Google跳转一致性哈希算法的改进版本。它克服了原始设计无法删除节点的缺点。

性能基准

Doublejump/10-nodes               49276861       22.3 ns/op        0 B/op      0 allocs/op
Doublejump/100-nodes              33304191       34.9 ns/op        0 B/op      0 allocs/op
Doublejump/1000-nodes             25261296       46.3 ns/op        0 B/op      0 allocs/op

StathatConsistent/10-nodes         4780832      273.5 ns/op       80 B/op      2 allocs/op
StathatConsistent/100-nodes        4059537      291.8 ns/op       80 B/op      2 allocs/op
StathatConsistent/1000-nodes       3132294      367.6 ns/op       80 B/op      2 allocs/op

SerialxHashring/10-nodes           2766384      455.7 ns/op      152 B/op      5 allocs/op
SerialxHashring/100-nodes          2500936      487.6 ns/op      152 B/op      5 allocs/op
SerialxHashring/1000-nodes         2254138      560.0 ns/op      152 B/op      5 allocs/op

安装

V1版本 (Go <= 1.17)

go get -u github.com/edwingeng/doublejump

V2版本 (Go >= 1.18)

go get -u github.com/edwingeng/doublejump/v2

使用示例

V1版本示例 (Go <= 1.17)

import "github.com/edwingeng/doublejump"

func Example() {
    // 创建新的哈希环
    h := NewHash()
    
    // 添加10个节点
    for i := 0; i < 10; i++ {
        h.Add(fmt.Sprintf("node%d", i))
    }

    // 获取节点数量
    fmt.Println(h.Len())      // 当前有效节点数
    fmt.Println(h.LooseLen()) // 总节点数(包括已删除的)

    // 根据key获取节点
    fmt.Println(h.Get(1000))  // 获取key=1000对应的节点
    fmt.Println(h.Get(2000))  // 获取key=2000对应的节点
    fmt.Println(h.Get(3000))  // 获取key=3000对应的节点

    // 移除一个节点
    h.Remove("node3")
    
    // 再次获取节点数量
    fmt.Println(h.Len())      // 当前有效节点数
    fmt.Println(h.LooseLen()) // 总节点数(包括已删除的)

    // 再次根据key获取节点
    fmt.Println(h.Get(1000))  // 获取key=1000对应的节点
    fmt.Println(h.Get(2000))  // 获取key=2000对应的节点
    fmt.Println(h.Get(3000))  // 获取key=3000对应的节点

    // 输出:
    // 10
    // 10
    // node9
    // node2
    // node3
    // 9
    // 10
    // node9
    // node2
    // node0
}

V2版本示例 (Go >= 1.18)

import "github.com/edwingeng/doublejump/v2"

func Example() {
    // 创建新的哈希环(泛型版本)
    h := NewHash[string]()
    
    // 添加10个节点
    for i := 0; i < 10; i++ {
        h.Add(fmt.Sprintf("node%d", i))
    }

    // 获取节点数量
    fmt.Println(h.Len())      // 当前有效节点数
    fmt.Println(h.LooseLen()) // 总节点数(包括已删除的)

    // 根据key获取节点(返回节点和是否找到的标志)
    fmt.Println(h.Get(1000))  // 获取key=1000对应的节点
    fmt.Println(h.Get(2000))  // 获取key=2000对应的节点
    fmt.Println(h.Get(3000))  // 获取key=3000对应的节点

    // 移除一个节点
    h.Remove("node3")
    
    // 再次获取节点数量
    fmt.Println(h.Len())      // 当前有效节点数
    fmt.Println(h.LooseLen()) // 总节点数(包括已删除的)

    // 再次根据key获取节点
    fmt.Println(h.Get(1000))  // 获取key=1000对应的节点
    fmt.Println(h.Get(2000))  // 获取key=2000对应的节点
    fmt.Println(h.Get(3000))  // 获取key=3000对应的节点

    // 输出:
    // 10
    // 10
    // node9 true
    // node2 true
    // node3 true
    // 9
    // 10
    // node9 true
    // node2 true
    // node0 true
}

致谢

原始算法的实现归功于dgryski。