3.7. 实现一致性hash算法

1.0

1.0

这一篇是比较重要的，如果实现不了那么你也就无法实现分布式存储！也就无法实现分布式权限验证的功能！想学就请重视！实在不懂请加qq:495681586

前边我们说过了一致性hash算法的理解，今天就用golang来实现一致性hash
代码当中包括了如何向hash环上添加节点
以及
如何通过一个key获取到离着这个key对应的hash值最近的节点的value
以及
如何删除hash环上的节点
其中用到了二分法算法，
上一篇讲过的！
上代码吧：
//实现一致性hash算法

package common

import (
   "errors"
 "hash/crc32" "sort" "strconv" "sync")

//声明新切片类型
type units []uint32

//返回切片长度  因为是切片类型内部就是指针指向 所以不用 func (x *units) len() {}func (x units) Len() int {
   return len(x)
}

//比较两个数大小
func (x units) Less(i,j int) bool {
   return x[i] < x[j]
}

//切片中两个值的交换
func (x units) Swap(i,j int) {
   x[i],x[j] = x[j],x[i]
}

//当hash环上没有数据时提示错误
var errEmpty = errors.New("Hash 环没有数据")

//创建结构体保存一致性hash信息
type Consistent struct {
   //hash环 key为哈希值 值为存放节点的信息
  circle map[uint32]string
  //已经排序的节点hash切片
  sortedHashes units
  //虚拟节点个数，用来增加hash的平衡性
  VirtualNode int
  //map 读写锁   稍后解释 可以保证在高并发下读取的数据不会错误
  sync.RWMutex
}

//创建一致性hash算法结构体  设置默认节点数量
func NewConsistent() *Consistent {
   return &Consistent{
      //初始化变量
  circle:       make(map[uint32]string),
      //设置虚拟节点个数
  VirtualNode:  20,
   }
}

//自动生成key值
//根据服务器相关信息加上index 生成服务器相关的key
func (c *Consistent) generateKey(element string,index int) string {
   //副本key生成逻辑
  return element+strconv.Itoa(index)
}

//获取hash位置  根据传入的key获取对应的hash值
func (c *Consistent) hashKey(key string) uint32 {
   if len(key) < 64 {
      //声明一个数组长度为64
  var srcatch [64]byte
  //拷贝数据到数组当中
  copy(srcatch[:],key)
      //使用IEEE 多项式返回数据的CRC-32校验和   是一个标准 能帮助我们通过算法算出key对应的hash值
  return crc32.ChecksumIEEE(srcatch[:len(key)])
   }
   return crc32.ChecksumIEEE([]byte(key))
}

//更新排序 方便查找
func (c *Consistent) updateSortedHashes() {
   //相当于清空切片里面的内容
  hashes := c.sortedHashes[:0]
   //判断切片容量，是否过大，如果过大则重置
  //这个用于排序的切片的容量除以虚拟节点个数的4倍  大于 hash环上的节点数  则清空里面的值
  if cap(c.sortedHashes)/(c.VirtualNode*4) > len(c.circle) {
      hashes = nil
  }
   //添加hashs
  for k := range c.circle {
      hashes = append(hashes,k)
   }
   //对所有节点hash值进行排序
  //方便之后进行二分法查找
  sort.Sort(hashes)
   //重新赋值
  c.sortedHashes = hashes
}

//动态添加节点  需要加锁
//向hash环中添加节点
func (c *Consistent) Add(element string){
   //加锁  分布式存储当中这个锁是非常关键的  后边会讲到
  c.Lock()
   //解锁
  defer c.Unlock()
   c.add(element)
}

//添加节点
//向hash环里面添加服务器信息
func (c *Consistent) add(element string) {
   //循环虚拟节点 设置副本
  //虚拟节点加上generateKey()里面的规则 生成虚拟节点的信息  根据虚拟节点的信息进行hash
  for i:=0;i<c.VirtualNode;i++ {
      //根据生成的虚拟节点添加到hash环中
  c.circle[c.hashKey(c.generateKey(element,i))] = element
  }
   //下面对生成以后的虚拟节点进行排序
  c.updateSortedHashes()
}

//动态删除节点
func (c *Consistent) Remove(element string){
   c.Lock()
   defer c.Unlock()
   c.remove(element)
}

//删除节点
//需要传入服务器的信息比如是ip
func (c *Consistent) remove(element string){
   //根据传入的服务器的信息删除所欲的副节点
  for i:=0;i<c.VirtualNode;i++{
      delete(c.circle,c.hashKey(c.generateKey(element,i)))
   }
   //然后更新排序 方便二分法查找hash环上的节点
  c.updateSortedHashes()
}

//顺时针查找最近的节点
func (c *Consistent) search(key uint32) int {
   //查找算法
  f := func(x int) bool {
      return c.sortedHashes[x] > key
  }
   //使用“二分查找”算法来搜索指定切片满足条件的最小值
  i := sort.Search(len(c.sortedHashes), f)
   //如果超出范围则设置i=0
  if i >= len(c.sortedHashes) {
      i = 0
  }
   return i
}

//根据数据标识获取最近服务器节点信息 其实是返回的ip地址
func (c *Consistent) Get(name string)(string,error){
   //添加锁
  c.RLock()
   //解锁
  defer c.RUnlock()
   //如果为零则返回错误
  if len(c.circle) == 0 {
      return "",errEmpty
  }
   //计算hash值
  key := c.hashKey(name)
   //在hash环上查找我们最近的节点
  i := c.search(key)
   return c.circle[c.sortedHashes[i]],nil
}

代码当中提到的添加锁解除锁，我们会在接下来的博文当中具体讲解，分布式存储是一定要有锁的机制的！敬请期待！