一致性哈希初认识

2023-11-20 13:02:12 浏览数 (3)

一致性哈希

一致哈希算法简单得令人难以置信，但却非常强大，但直到我坐下来亲自研究它之前，我都不太明白它到底是什么。在介绍一致性散列之前，你需要先了解我们要解决的问题：

如何确定分布式网络中哪个服务器存储和检索键呢？要求是：所有节点获得相对相等数量的键，能够添加和删除节点，从而使移动的键数量最少。

假设我们有四台服务器：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的集合：

代码语言：javascript复制
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的初始化函数：

代码语言：javascript复制
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方法了：

代码语言：javascript复制
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()），下面我们需要实现它们：

代码语言：javascript复制
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，这一步是重点：

代码语言：javascript复制
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:

代码语言：javascript复制
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:

代码语言：javascript复制
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:

代码语言：javascript复制
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/

func nodes 服务器 数组 网络

1 人点赞