分布式缓存：一致性哈希与虚拟节点

一致性哈希算法

一致性哈希将哈希值空间组织成一个虚拟的环（0到2^32-1），节点和数据都映射到环上。数据沿顺时针方向找到第一个节点存储，当节点增减时只影响相邻节点的数据分布。

import hashlib
from bisect import bisect_right

class ConsistentHash:
    def __init__(self, nodes: list, virtual_nodes: int = 150):
        self.ring = {}
        self.sorted_keys = []
        self.virtual_nodes = virtual_nodes
        
        for node in nodes:
            self.add_node(node)
    
    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_node(self, node: str):
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:v{i}"
            hash_val = self._hash(virtual_key)
            self.ring[hash_val] = node
            self.sorted_keys.append(hash_val)
        self.sorted_keys.sort()
    
    def remove_node(self, node: str):
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:v{i}"
            hash_val = self._hash(virtual_key)
            del self.ring[hash_val]
            self.sorted_keys.remove(hash_val)
    
    def get_node(self, key: str) -> str:
        if not self.ring:
            return None
        hash_val = self._hash(key)
        idx = bisect_right(self.sorted_keys, hash_val) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

虚拟节点解决数据倾斜

物理节点数量较少时，一致性哈希可能导致数据分布不均匀。虚拟节点将每个物理节点映射为多个虚拟节点，使数据分布更均匀。

type ConsistentHash struct {
    ring         map[uint32]string
    sortedKeys   []uint32
    virtualNodes int
    mu           sync.RWMutex
}

func NewConsistentHash(nodes []string, virtualNodes int) *ConsistentHash {
    ch := &ConsistentHash{
        ring:         make(map[uint32]string),
        virtualNodes: virtualNodes,
    }
    for _, node := range nodes {
        ch.AddNode(node)
    }
    return ch
}

func (ch *ConsistentHash) AddNode(node string) {
    ch.mu.Lock()
    defer ch.mu.Unlock()
    
    for i := 0; i < ch.virtualNodes; i++ {
        key := fmt.Sprintf("%s#%d", node, i)
        hash := ch.hash(key)
        ch.ring[hash] = node
        ch.sortedKeys = append(ch.sortedKeys, hash)
    }
    sort.Slice(ch.sortedKeys, func(i, j int) bool {
        return ch.sortedKeys[i] < ch.sortedKeys[j]
    })
}

func (ch *ConsistentHash) GetNode(key string) string {
    ch.mu.RLock()
    defer ch.mu.RUnlock()
    
    if len(ch.ring) == 0 {
        return ""
    }
    
    hash := ch.hash(key)
    idx := sort.Search(len(ch.sortedKeys), func(i int) bool {
        return ch.sortedKeys[i] >= hash
    })
    
    if idx >= len(ch.sortedKeys) {
        idx = 0
    }
    return ch.ring[ch.sortedKeys[idx]]
}

func (ch *ConsistentHash) hash(key string) uint32 {
    h := fnv.New32a()
    h.Write([]byte(key))
    return h.Sum32()
}

缓存穿透、雪崩、击穿解决方案

// 布隆过滤器防止缓存穿透
public class BloomFilterCache {
    private final BloomFilter<String> bloomFilter;
    private final RedisTemplate<String, Object> redisTemplate;
    
    public BloomFilterCache(int expectedInsertions, double fpp) {
        this.bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(Charset.defaultCharset()),
            expectedInsertions,
            fpp
        );
    }
    
    public Object get(String key, Supplier<Object> dbLoader) {
        // 1. 布隆过滤器检查
        if (!bloomFilter.mightContain(key)) {
            return null; // 一定不存在
        }
        
        // 2. 查询缓存
        Object value = redisTemplate.opsForValue().get(key);
        if (value != null) {
            return value;
        }
        
        // 3. 缓存击穿防护 - 分布式锁
        String lockKey = "lock:" + key;
        try {
            if (redisTemplate.opsForValue().setIfAbsent(lockKey, "1", 10, TimeUnit.SECONDS)) {
                value = dbLoader.get();
                if (value != null) {
                    redisTemplate.opsForValue().set(key, value, 30, TimeUnit.MINUTES);
                }
                return value;
            }
        } finally {
            redisTemplate.delete(lockKey);
        }
        return null;
    }
}

Redis Cluster架构设计

Redis Cluster通过16384个哈希槽分配数据，支持水平扩展和自动故障转移。每个节点负责一部分哈希槽，客户端通过MOVED重定向找到正确的节点。