一致性哈希初认识
一致性哈希
一致哈希算法简单得令人难以置信，但却非常强大，但直到我坐下来亲自研究它之前，我都不太明白它到底是什么。在介绍一致性散列之前，你需要先了解我们要解决的问题：
如何确定分布式网络中哪个服务器存储和检索键呢？要求是：所有节点获得相对相等数量的键，能够添加和删除节点，从而使移动的键数量最少。
假设我们有四台服务器：S1，S2，S3 和 S4。四台服务器都是相同的，但彼此无法互相了解。
在这个例子中，为了保持简单，键是递增的整数。通常情况下，将键与校验和进行运算后会返回一个数字。有了这个数字后，就可以将这个数字与节点数量（上图中是 4）进行求模。在网络稳定的情况下，即没有节点离开或加入网络时，这种方法会非常有效。
但是，如果有一个节点挂了（S2），那该怎么办？那问题就大了。
请注意，从上图看，我们可以清楚看到，几乎所有节点的键都需要再重新映射。这挺无道理，为什么正常运行的服务器中的键也要重新映射呢？你是不是也有这样的疑惑？OK，现在我们应该知道，需要了解一下一致哈希的必要性。
以下是维基百科[1]中对一致性哈希的定义：
一致哈希是一种特殊的哈希方式，当调整哈希表大小并使用一致哈希时，平均只需重新映射 K/n 个键，其中 K 是键的数量，n 是槽的数量。
如果我们在上面使用了一致哈希，那么只有 S2 节点中的键需要移动。通常，大多数文章都会画一个如下单位圆的草图，并据此进行解释：
我们暂时先不考虑如何将节点放到单位圆上。与其在键的哈希值上应用模函数，不如把哈希值直接映射到单位圆上。(如果要应用模函数，这也是挺简单的，下面我们很快就能实现）。要确定键映射到哪个节点，我们只需顺时针查找，直到找到一个节点。因此，对于键 1，S2 就是它应该被存储和检索的节点。
如果 S2 宕机了怎么办？我们需要从另一个节点获取和检索键 1，但请注意其他键的映射并没有改变。唯一发生变化的是 S2 节点中的键。就是这样！如果添加新节点，这个方法也同样有效。比方说，你把 S5 添加到网络中。我们并不需要改变现有键的节点位置。
一致哈希还包括节点大小不同的情况。我们要做的就是创建虚拟节点，并将它们置于单位圆上。根据所选的哈希函数，虚拟节点可以随机放置在单位圆上。对于容量较大的节点，应添加更多虚拟节点。这样，当一个节点宕机时，键就会平均分配到其他节点上，而不只是下一个节点。
实现一致性哈希
接下来，我们将使用 Go 来实现一致哈希。在我找到一个很好的实现并把打印语句放在各处并修改代码之前，我并不太理解它。这个实现在很大程度上受到了 stathat[2] 实现的启发。原论文要求使用树来实现，但我们还是先使用 stathat 的方法。
我们将使用 crc32[3] 来生成键的校验和。至于 crc32 的作用和原理，不在本博文的讨论范围之内。只需知道给定一个输入，它就会返回一个 32 uint。本例中的输入是节点的 IP 地址。
其要点是，我们使用一个数组来保存节点** id 校验和**的结果。对于每个键，我们都会进行校验和，并确定该键应被添加到的位置，然后返回与之相邻的节点。如果超出数组范围，则返回第一个节点。首先，我们定义 Ring，它是节点 Node的集合：
package consistent
// Ring 由分布式节点组成的网络
type Ring struct {
Nodes Nodes
sync.Mutex
}
// Nodes 节点切片
type Nodes []*Node
// Node Ring中的一个实体
type Node struct {
Id string
HashId uint32
}
接下来，我们来编写Ring和Node的初始化函数：
package consistent
// NewRing 初始化Ring
func NewRing() *Ring {
return &Ring{Nodes: Nodes{}}
}
// NewNode 初始化Node
func NewNode(id string) *Node {
return &Node{
Id: id,
HashId: crc32.ChecksumIEEE([]byte(id)),
}
}
现在，我们就可以来实现添加节点AddNode方法了：
package consistent
// AddNode 往Ring中添加节点
func (r *Ring) AddNode(id string) {
r.Lock()
defer r.Unlock()
node := NewNode(id)
r.Nodes = append(r.Nodes, node)
sort.Sort(r.Nodes)
}
为什么要使用 sort.Sort对Ring中节点进行排序？这又回到了单位圆。究竟如何实现单位圆呢？一种方法是使用一个数组，其中最后一项指向该数组中的第一项。我们也可以使用链表来实现，但很快你就会明白为什么没有必要。
如果你运行我们目前所做的，Go 编译器会报错：Nodes does not implement sort.Interface，因为 Nodes 没有实现 sort.Sort 中的接口（Len()，Less()、Swap()），下面我们需要实现它们：
package consistent
func (n Nodes) Len() int {
return len(n)
}
func (n Nodes) Less(i, j int) bool {
return n[i].HashId < n[j].HashId
}
func (n Nodes) Swap(i, j int) {
n[i], n[j] = n[j], n[i]
}
下来，要实现获取节点的方法 Get，这一步是重点：
package consistent
func (r *Ring) Get(id string) string {
i := r.search(id)
if i >= r.Nodes.Len() {
i = 0
}
return r.Nodes[i].Id
}
func (r *Ring) search(id string) int {
searchFn := func(i int) bool {
return r.Nodes[i].HashId >= crc32.ChecksumIEEE([]byte(id))
}
return sort.Search(r.Nodes.Len(), searchFn)
}
sort.Search使用二分搜索来查找切片中节点是否存在。如果不存在，它会返回我们要添加节点时应添加该节点的位置。如果节点校验和大于最后一个节点，那么我们就把它添加到第一个节点，整个过程就是这样。
接下来，我们还需要实现删除节点的方法RemoveNode:
package consistent
func (r *Ring) RemoveNode(id string) error {
r.Lock()
defer r.Unlock()
i := r.search(id)
if i > r.Nodes.Len() || r.Nodes[i].Id != id {
return ErrNodeNotFound
}
r.Nodes = append(r.Nodes[:i], r.Nodes[i+1:]...)
return nil
}
到此，实现一致性哈希的代码就完成了，完整的代码以及测试用例我将放到文中的最后，可以结合着测试用例再好好理解下。
完整代码
consistent.go:
package consistent
import (
"errors"
"hash/crc32"
"sort"
"sync"
)
var ErrNodeNotFound = errors.New("node not found")
// Ring 由分布式节点组成的网络
type Ring struct {
Nodes Nodes
sync.Mutex
}
// NewRing 初始化Ring
func NewRing() *Ring {
return &Ring{Nodes: Nodes{}}
}
// AddNode 往Ring中添加节点
func (r *Ring) AddNode(id string) {
r.Lock()
defer r.Unlock()
node := NewNode(id)
r.Nodes = append(r.Nodes, node)
sort.Sort(r.Nodes)
}
func (r *Ring) RemoveNode(id string) error {
r.Lock()
defer r.Unlock()
i := r.search(id)
if i > r.Nodes.Len() || r.Nodes[i].Id != id {
return ErrNodeNotFound
}
r.Nodes = append(r.Nodes[:i], r.Nodes[i+1:]...)
return nil
}
func (r *Ring) Get(id string) string {
i := r.search(id)
if i >= r.Nodes.Len() {
i = 0
}
return r.Nodes[i].Id
}
func (r *Ring) search(id string) int {
searchFn := func(i int) bool {
return r.Nodes[i].HashId >= crc32.ChecksumIEEE([]byte(id))
}
return sort.Search(r.Nodes.Len(), searchFn)
}
// Nodes 节点切片
type Nodes []*Node
func (n Nodes) Len() int {
return len(n)
}
func (n Nodes) Less(i, j int) bool {
return n[i].HashId < n[j].HashId
}
func (n Nodes) Swap(i, j int) {
n[i], n[j] = n[j], n[i]
}
// Node 环中的一个实体
type Node struct {
Id string
HashId uint32
}
// NewNode 初始化Node
func NewNode(id string) *Node {
return &Node{
Id: id,
HashId: crc32.ChecksumIEEE([]byte(id)),
}
}
consistent_test.go:
package consistent
import (
"hash/crc32"
"testing"
. "github.com/smartystreets/goconvey/convey"
)
var (
node1id = "node1"
node2id = "node2"
node3id = "node3"
)
func TestAddNode(t *testing.T) {
Convey("Given empty ring", t, func() {
Convey("Then it should add node", func() {
r := NewRing()
r.AddNode(node1id)
So(r.Nodes.Len(), ShouldEqual, 1)
Convey("Then node should've hashed id", func() {
So(r.Nodes[0].HashId, ShouldHaveSameTypeAs, uint32(0))
})
})
Convey("Then it should add node & sort by node id", func() {
r := NewRing()
r.AddNode(node1id)
r.AddNode(node2id)
So(r.Nodes.Len(), ShouldEqual, 2)
node1hash := crc32.ChecksumIEEE([]byte(node1id))
node2hash := crc32.ChecksumIEEE([]byte(node2id))
So(node1hash, ShouldBeGreaterThan, node2hash)
So(r.Nodes[0].Id, ShouldEqual, node2id)
So(r.Nodes[1].Id, ShouldEqual, node1id)
})
})
}
func TestRemoveNode(t *testing.T) {
Convey("Given ring with nodes", t, func() {
r := NewRing()
r.AddNode(node1id)
r.AddNode(node2id)
r.AddNode(node3id)
Convey("When node doesn't exist", func() {
Convey("Then it should return error", func() {
err := r.RemoveNode("nonexistent")
So(err, ShouldEqual, ErrNodeNotFound)
})
})
Convey("When node exists", func() {
Convey("Then it should remove node", func() {
err := r.RemoveNode(node2id)
So(err, ShouldBeNil)
So(r.Nodes.Len(), ShouldEqual, 2)
So(r.Nodes[0].Id, ShouldEqual, node3id)
So(r.Nodes[1].Id, ShouldEqual, node1id)
})
})
})
}
func TestGet(t *testing.T) {
Convey("Given ring with 1 node", t, func() {
r := NewRing()
r.AddNode(node1id)
Convey("Then it should return that node regardless of input", func() {
insertnode := r.Get("id")
So(insertnode, ShouldEqual, node1id)
insertnode = r.Get("anykey")
So(insertnode, ShouldEqual, node1id)
})
})
Convey("Given ring with multiple nodes", t, func() {
insertid := "justa"
r := NewRing()
r.AddNode(node1id)
r.AddNode(node2id)
r.AddNode(node3id)
Convey("Then it should return node closest", func() {
node1hash := crc32.ChecksumIEEE([]byte(node1id))
node3hash := crc32.ChecksumIEEE([]byte(node2id))
inserthash := crc32.ChecksumIEEE([]byte(insertid))
So(inserthash, ShouldBeLessThan, node1hash)
So(inserthash, ShouldBeGreaterThan, node3hash)
insertnode := r.Get(insertid)
So(insertnode, ShouldEqual, node1id)
})
})
}
参考资料
[1]
维基百科: https://en.wikipedia.org/wiki/Consistent_hashing
[2]
stathat: https://github.com/stathat/consistent
[3]
crc32: https://golang.org/pkg/hash/crc32/