天天看点
返回

的一致性哈希_经典算法之一致性哈希

一、前言

背景

在分布式系统中，为了避免对系统中的某一台服务器进行集中地访问而导致该服务器出现被流量压垮的现象，一般都会采用相关的负载均衡算法来对流量进行分散，对于数据分布式采用分布式存储算法来实现数据的拆解。单机系统与分布式系统的最大的区别在于问题的规模，即计算、存储的数据量的区别。将一个单机问题使用分布式解决，首先要解决的就是如何将问题拆解为可以使用多机分布式解决，使得分布式系统中的每台机器负责原问题的一个子集。由于无论是计算还是存储，其问题输入对象都是数据，所以如何拆解分布式系统的输入数据成为分布式系统的基本问题。不管是流量还是数据的分布式最终的通用解决方案都是采用哈希算法，也是我们着重探讨的哈希算法。

负载均衡算法

  • 轮询算法：通过轮询的方式将流量绝对平均的分发给每一台服务器。
  • 随机算法：通过随机的方式将流量进行分发。
  • 加权轮询：Nginx 的默认负载均衡算法，比如对于性能较低的机器我们可以将其权值设置的小一点，从而在轮询时少分给它一些流量，而对于性能较高的机器我们可以调大其权值，从而在轮询时多分发给它一些流量。
  • 哈希算法

分布式存储算法

  • 哈希算法

二、哈希算法

什么是哈希

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出，该输出就是散列值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

传统哈希(加密型哈希)与分布式系统中的哈希

在Golang官方包中我们可以找到对应一些hash算法包，加密类型的哈希属于加密包，而一致性哈希则在hash包中。

  1. 加密型哈希，哈希函数应该对抗碰撞性和抗篡改性要求很高，而会牺牲查找效率。
  2. 查找型哈希，哈希函数更追求查找的效率和良好的抗碰撞性。
  • 加密型哈希，数据安全，用于加密签名等。
    • MD5
    • SHA1
    • SHA256
的一致性哈希_经典算法之一致性哈希
  • 查找型哈希，速度更快，用于分布式系统的一致性哈希。
    • CRC(Cyclic-Redundancy-Check)：循环冗余校验。它是一类重要的，编码和解码方法简单，检错和纠错能力强的哈希算法，在通信领域广泛地用于实现差错控制。
    • FNV(Fowler-Noll-Vo)：能快速 hash 大量数据并保持较小的冲突率，它的高度分散使它适用于 hash 一些非常相近的字符串。
    • Murmur：高运算性能，低碰撞率，优于FNV。
    • Ketama：一致性哈希算法的实现之一，其他的哈希算法有通用的一致性哈希算法实现，只不过是替换了哈希映射函数而已
的一致性哈希_经典算法之一致性哈希

一致性哈希是一种策略

加密型哈希主要应用于文件校验、数字签名、鉴权协议等场景，想必大家都已经用的炉火纯青了，我们主要讨论的是分布式系统中应用的哈希。后面我们探讨的重点也在于一致性哈希与哈希槽这两个方面。一致性哈希与哈希槽是分布式系统中的一种分片分流策略，并非实际意义上的，或者说狭义上说的某一种哈希算法。

三、哈希在分布式中的应用

数据分片

数据分片的路由策略一般有三种，依次弥补上一个策略而衍生出下一个策略，官方Redis集群使用虚拟槽的方式实现数据分片：

策略 简述 短板
哈希取模算法 以元素被某个整数M整除后所得到的余数找对其对应处理的节点( H(K) = K % M，M等于节点的个数) 当增加或减少节点时，数据的路由将发生变化，伸缩性很差
一致性哈希 以元素通过某个散列函数H(K)所得到的散列值坐落在Hash环上的位置，找到其对应处理的节点。 使用此方式很难保证客户端的请求平均分配到各个节点中，不能很好的实现负载均衡
哈希槽 以元素通过某个散列函数H(K)所得到的槽位，找到其对应处理的节点。 -

hash取模算法

简单的分流分片方式，分库分表方案最主要就是路由算法，把路由的key按照指定的算法进行路由存放。

中大型项目中，一旦遇到数据量比较大，小伙伴应该都知道就应该对数据进行拆分了。有垂直和水平两种。

  • 垂直拆分比较简单，业务角度进行拆分多个库，主要是分割字段。
  • 水平拆分的概念，是同一个业务数据量大之后，进行水平拆分，主要是分割数据，也就是我们这里讨论的hash取模算法。

    H(K) = K % M
代码样例 
// id当前id号，count实例总数(一共分了几张表)// 返回表id号(第几张表)func GetShard(id, count int64) int64 {    return id % count}
应用场景
  1. 数据库分表分库
  2. 分流负载
缺点

将来的数据迁移和扩容，会很难。

一致性Hash

哈希环，比较经典的策略。一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形)。

  • Data

     =>数据,带有一个用于hash计算的key,或者本身就是key

  • Shard01

     =>实例,具体实例,如mysql,redis

  • Shard01|1

     =>节点,虚拟节点,使得实例均匀分布在哈希环上

  • Hash()

     =>哈希函数,计算出在[0,2^32-1]中的值
  • Data数据会存储在最接近自己下一个哈希值所对应的实例上
的一致性哈希_经典算法之一致性哈希
// 一致性哈希type Consistent struct {    circle           map[uint32]string // 哈希环    members          map[string]bool // 数据分片(实例)登记 (shard01,true),(shard02,true)    sortedHashes     uints // 有序的虚拟节点哈希计算值数组 Hash(shard01|1),Hash(shard01|2)，……    NumberOfReplicas int // (每个实例)虚拟节点数 shard01|1，shard01|2，……    count            int64 // 数据分片(实例)总数 shard01，shard02    scratch          [64]byte // crc算法需要    UseFnv           bool // 是否使用FNV算法    sync.RWMutex // 读写锁}

在一致性哈希算法中，如果

shard01|2

不可用或者迁移时，则受影响的数据仅仅是

shard01|2

到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)

shard01|1

之间数据，其它不会受到影响，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。一致性哈希算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题 ，为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

代码样例 
package consistentimport (    "errors"    "hash/crc32"    "hash/fnv"    "sort"    "strconv"    "sync")type uints []uint32// Len returns the length of the uints array.func (x uints) Len() int { return len(x) }// Less returns true if element i is less than element j.func (x uints) Less(i, j int) bool { return x[i] < x[j] }// Swap exchanges elements i and j.func (x uints) Swap(i, j int) { x[i], x[j] = x[j], x[i] }// ErrEmptyCircle is the error returned when trying to get an element when nothing has been added to hash.var ErrEmptyCircle = errors.New("empty circle")// Consistent holds the information about the members of the consistent hash circle.type Consistent struct {    circle           map[uint32]string    members          map[string]bool    sortedHashes     uints    NumberOfReplicas int    count            int64    scratch          [64]byte    UseFnv           bool    sync.RWMutex}// New creates a new Consistent object with a default setting of 20 replicas for each entry.//// To change the number of replicas, set NumberOfReplicas before adding entries.func New() *Consistent {    c := new(Consistent)    c.NumberOfReplicas = 20    c.circle = make(map[uint32]string)    c.members = make(map[string]bool)    return c}// eltKey generates a string key for an element with an index.func (c *Consistent) eltKey(elt string, idx int) string {    // return elt + "|" + strconv.Itoa(idx)    return strconv.Itoa(idx) + elt}// Add inserts a string element in the consistent hash.func (c *Consistent) Add(elt string) {    c.Lock()    defer c.Unlock()    c.add(elt)}// need c.Lock() before callingfunc (c *Consistent) add(elt string) {    for i := 0; i < c.NumberOfReplicas; i++ {        c.circle[c.hashKey(c.eltKey(elt, i))] = elt}    c.members[elt] = true    c.updateSortedHashes()    c.count++}// Remove removes an element from the hash.func (c *Consistent) Remove(elt string) {    c.Lock()    defer c.Unlock()    c.remove(elt)}// need c.Lock() before callingfunc (c *Consistent) remove(elt string) {    for i := 0; i < c.NumberOfReplicas; i++ {        delete(c.circle, c.hashKey(c.eltKey(elt, i)))}    delete(c.members, elt)    c.updateSortedHashes()    c.count--}// Set sets all the elements in the hash.  If there are existing elements not// present in elts, they will be removed.func (c *Consistent) Set(elts []string) {    c.Lock()    defer c.Unlock()    for k := range c.members {        found := false        for _, v := range elts {            if k == v {                found = true                break            }        }        if !found {            c.remove(k)        }}    for _, v := range elts {        _, exists := c.members[v]        if exists {            continue        }        c.add(v)}}func (c *Consistent) Members() []string {    c.RLock()    defer c.RUnlock()    var m []string    for k := range c.members {        m = append(m, k)}    return m}// Get returns an element close to where name hashes to in the circle.func (c *Consistent) Get(name string) (string, error) {    c.RLock()    defer c.RUnlock()    if len(c.circle) == 0 {        return "", ErrEmptyCircle}    key := c.hashKey(name)    i := c.search(key)    return c.circle[c.sortedHashes[i]], nil}func (c *Consistent) search(key uint32) (i int) {    f := func(x int) bool {        return c.sortedHashes[x] > key}    i = sort.Search(len(c.sortedHashes), f)    if i >= len(c.sortedHashes) {        i = 0}    return}// GetTwo returns the two closest distinct elements to the name input in the circle.func (c *Consistent) GetTwo(name string) (string, string, error) {    c.RLock()    defer c.RUnlock()    if len(c.circle) == 0 {        return "", "", ErrEmptyCircle}    key := c.hashKey(name)    i := c.search(key)    a := c.circle[c.sortedHashes[i]]    if c.count == 1 {        return a, "", nil}    start := i    var b string    for i = start + 1; i != start; i++ {        if i >= len(c.sortedHashes) {            i = 0        }        b = c.circle[c.sortedHashes[i]]        if b != a {            break        }}    return a, b, nil}// GetN returns the N closest distinct elements to the name input in the circle.func (c *Consistent) GetN(name string, n int) ([]string, error) {    c.RLock()    defer c.RUnlock()    if len(c.circle) == 0 {        return nil, ErrEmptyCircle}    if c.count < int64(n) {        n = int(c.count)}    var (        key   = c.hashKey(name)        i     = c.search(key)        start = i        res   = make([]string, 0, n)        elem  = c.circle[c.sortedHashes[i]])    res = append(res, elem)    if len(res) == n {        return res, nil}    for i = start + 1; i != start; i++ {        if i >= len(c.sortedHashes) {            i = 0        }        elem = c.circle[c.sortedHashes[i]]        if !sliceContainsMember(res, elem) {            res = append(res, elem)        }        if len(res) == n {            break        }}    return res, nil}func (c *Consistent) hashKey(key string) uint32 {    if c.UseFnv {        return c.hashKeyFnv(key)}    return c.hashKeyCRC32(key)}func (c *Consistent) hashKeyCRC32(key string) uint32 {    if len(key) < 64 {        var scratch [64]byte        copy(scratch[:], key)        return crc32.ChecksumIEEE(scratch[:len(key)])}    return crc32.ChecksumIEEE([]byte(key))}func (c *Consistent) hashKeyFnv(key string) uint32 {    h := fnv.New32a()    h.Write([]byte(key))    return h.Sum32()}func (c *Consistent) updateSortedHashes() {    hashes := c.sortedHashes[:0]    //reallocate if we're holding on to too much (1/4th)    if cap(c.sortedHashes)/(c.NumberOfReplicas*4) > len(c.circle) {        hashes = nil}    for k := range c.circle {        hashes = append(hashes, k)}    sort.Sort(hashes)    c.sortedHashes = hashes}func sliceContainsMember(set []string, member string) bool {    for _, m := range set {        if m == member {            return true        }}    return false}

哈希槽

哈希槽组由16384 个哈希槽(hash slot)，数据库中的每个

Data

都属于这16384个哈希槽中的一个。集群使用公式 CRC16(key) % 16384 来计算

Data

的键 key 属于哪个槽。集群中的每一个节点负责处理一部分哈希槽。经典的Redis集群模式【三主三从】就是由该哈希算法策略实现。redis cluster是采用master节点有多个slave节点机制来保证数据的完整性的,master节点写入数据，slave节点同步数据。当master节点挂机后，slave节点会通过选举机制选举出一个节点变成master节点，实现高可用，以后在讲Redis时，我们会做详细介绍。

的一致性哈希_经典算法之一致性哈希
的一致性哈希
上一篇: 分库分表注意
下一篇: 你们项目的核心战略是什么关于作者

继续阅读