Skip to content

04-consistent-hashing.md

Latest commit

 

History

History
278 lines (206 loc) · 6.19 KB

04-consistent-hashing.md

File metadata and controls

278 lines (206 loc) · 6.19 KB

4.4 一致性哈希算法

📍 导航：返回目录 | 上一节：动态规划 | 下一节：限流算法

问题背景

传统Hash的问题

// 简单取模
serverIndex := hash(key) % serverCount

缺点：

  • 节点数变化时，大量数据需要重新分配
  • 数据迁移成本高

例子：

  • 3台服务器 → 4台服务器
  • 75%的数据需要迁移！

一致性哈希原理

核心思想

  1. Hash环：将Hash值空间组织成环形（0 ~ 2^32-1）
  2. 节点映射：服务器节点映射到环上
  3. 数据定位：数据顺时针找到第一个节点
         0
         |
    Node C (1000)
         |
  2^32 ←—•—→ Key1 (500)
         |
    Node A (15000)
         |
    Node B (20000)

优势

  • 节点增删，只影响相邻节点
  • 数据迁移量：平均 1/n

Go语言实现

package main

import (
    "fmt"
    "hash/crc32"
    "sort"
    "strconv"
)

type ConsistentHash struct {
    circle           map[uint32]string // 环上的节点
    sortedHashes     []uint32          // 排序的hash值
    virtualNodeCount int               // 虚拟节点倍数
}

func NewConsistentHash(virtualNodeCount int) *ConsistentHash {
    return &ConsistentHash{
        circle:           make(map[uint32]string),
        sortedHashes:     []uint32{},
        virtualNodeCount: virtualNodeCount,
    }
}

// AddNode 添加节点
func (ch *ConsistentHash) AddNode(node string) {
    for i := 0; i < ch.virtualNodeCount; i++ {
        virtualNode := node + "#" + strconv.Itoa(i)
        hash := ch.hashKey(virtualNode)
        ch.circle[hash] = node
        ch.sortedHashes = append(ch.sortedHashes, hash)
    }
    sort.Slice(ch.sortedHashes, func(i, j int) bool {
        return ch.sortedHashes[i] < ch.sortedHashes[j]
    })
}

// RemoveNode 删除节点
func (ch *ConsistentHash) RemoveNode(node string) {
    for i := 0; i < ch.virtualNodeCount; i++ {
        virtualNode := node + "#" + strconv.Itoa(i)
        hash := ch.hashKey(virtualNode)
        delete(ch.circle, hash)
        
        // 从排序列表中删除
        idx := ch.search(hash)
        ch.sortedHashes = append(ch.sortedHashes[:idx], ch.sortedHashes[idx+1:]...)
    }
}

// GetNode 获取key对应的节点
func (ch *ConsistentHash) GetNode(key string) string {
    if len(ch.circle) == 0 {
        return ""
    }
    
    hash := ch.hashKey(key)
    
    // 二分查找第一个 >= hash 的位置
    idx := ch.search(hash)
    
    // 如果超出范围，回到环的起点
    if idx >= len(ch.sortedHashes) {
        idx = 0
    }
    
    return ch.circle[ch.sortedHashes[idx]]
}

func (ch *ConsistentHash) search(hash uint32) int {
    idx := sort.Search(len(ch.sortedHashes), func(i int) bool {
        return ch.sortedHashes[i] >= hash
    })
    return idx
}

func (ch *ConsistentHash) hashKey(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

// 使用示例
func main() {
    ch := NewConsistentHash(150) // 每个节点150个虚拟节点
    
    // 添加节点
    ch.AddNode("server1")
    ch.AddNode("server2")
    ch.AddNode("server3")
    
    // 数据分配
    keys := []string{"user:1001", "user:1002", "user:1003", "user:1004", "user:1005"}
    
    fmt.Println("初始分配：")
    for _, key := range keys {
        node := ch.GetNode(key)
        fmt.Printf("%s -> %s\n", key, node)
    }
    
    // 添加新节点
    fmt.Println("\n添加server4后：")
    ch.AddNode("server4")
    
    for _, key := range keys {
        node := ch.GetNode(key)
        fmt.Printf("%s -> %s\n", key, node)
    }
    
    // 删除节点
    fmt.Println("\n删除server2后：")
    ch.RemoveNode("server2")
    
    for _, key := range keys {
        node := ch.GetNode(key)
        fmt.Printf("%s -> %s\n", key, node)
    }
}

虚拟节点

问题

真实节点少时，数据分布不均匀。

解决方案

每个真实节点映射为多个虚拟节点。

// 真实节点A → 虚拟节点A#1, A#2, A#3, ..., A#150

推荐虚拟节点数：100-200

效果：

  • 数据分布更均匀
  • 负载均衡更好

应用场景

1. 分布式缓存

type DistributedCache struct {
    ch     *ConsistentHash
    caches map[string]*Cache
}

func (dc *DistributedCache) Get(key string) (interface{}, error) {
    node := dc.ch.GetNode(key)
    cache := dc.caches[node]
    return cache.Get(key)
}

func (dc *DistributedCache) Set(key string, value interface{}) error {
    node := dc.ch.GetNode(key)
    cache := dc.caches[node]
    return cache.Set(key, value)
}

2. 分布式存储

  • Cassandra
  • DynamoDB
  • Riak

3. 负载均衡

type LoadBalancer struct {
    ch      *ConsistentHash
    servers map[string]*Server
}

func (lb *LoadBalancer) Route(request *Request) *Server {
    // 根据请求ID或IP做一致性哈希
    node := lb.ch.GetNode(request.ID)
    return lb.servers[node]
}

与其他方案对比

方案 数据迁移量 实现复杂度 负载均衡
取模 100% 简单 均匀
一致性哈希 1/n 中等 需虚拟节点
跳跃一致性哈希 1/n 复杂 均匀

本章小结

关键要点：

  • ✅ 一致性哈希解决节点动态增删问题
  • ✅ 虚拟节点保证数据均匀分布
  • ✅ 广泛应用于分布式系统
  • ✅ 平均迁移量：1/n

扩展阅读

💡 思考题：

  1. 为什么一致性哈希比简单取模好？
  2. 虚拟节点的作用是什么？
  3. 如何选择合适的虚拟节点数量？

⏮️ 上一节：动态规划 | ⏭️ 下一节：限流算法