第九部分：一致性哈希 —— 解决分布式缓存扩缩容问题

在分布式缓存（如 Redis Cluster）或负载均衡中，当节点数量变化时，传统的哈希取模会导致大量 key 的映射位置改变，引发缓存雪崩。一致性哈希算法可以在节点增减时只影响少量 key。

9.1 基本原理
将哈希值空间组织成一个大小为 2^32 的圆环。将节点（如 Redis 实例）的 IP 哈希到环上，将 key 也哈希到环上，然后顺时针找到第一个节点。

虚拟节点：每个物理节点在环上映射多个虚拟节点，使数据分布更均匀，且节点变化时影响范围更平均。

9.2 代码实现简化版

import java.util.*;

public class ConsistentHash {
    private final SortedMap<Integer, String> circle = new TreeMap<>();
    private final int virtualNodesNum = 150;

    public void addNode(String node) {
        for (int i = 0; i < virtualNodesNum; i++) {
            int hash = (node + "#" + i).hashCode();
            circle.put(hash, node);
        }
    }

    public void removeNode(String node) {
        for (int i = 0; i < virtualNodesNum; i++) {
            int hash = (node + "#" + i).hashCode();
            circle.remove(hash);
        }
    }

    public String getNode(String key) {
        if (circle.isEmpty()) return null;
        int hash = key.hashCode();
        SortedMap<Integer, String> tailMap = circle.tailMap(hash);
        Integer nodeHash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        return circle.get(nodeHash);
    }
}

实际应用：Redis Cluster 使用哈希槽（16384 个槽）而不是一致性哈希，但原理类似。分布式数据存储（如 Cassandra、Amazon DynamoDB）广泛使用一致性哈希。

第十部分：分布式 ID 生成 —— 确保全局唯一且趋势递增

在分库分表环境下，数据库自增 ID 无法保证全局唯一。需要一种分布式 ID 生成器。

10.1 常见方案对比

10.2 雪花算法详解
雪花算法生成 64 位 Long 型 ID，结构如下：

0 | 41位时间戳 | 10位机器ID | 12位序列号

1 位符号位，固定 0。

41 位时间戳（毫秒级），可支持 69 年。

10 位机器 ID（最多 1024 个节点）。

12 位序列号，同一毫秒内可生成 4096 个不同 ID。

Java 实现片段：

public class SnowflakeIdGenerator {
    private final long twepoch = 1288834974657L; // 起始时间戳
    private final long workerIdBits = 10L;
    private final long sequenceBits = 12L;
    private final long maxWorkerId = ~(-1L << workerIdBits);
    private final long workerId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) throw new IllegalArgumentException();
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        if (timestamp < lastTimestamp) {
            // 时钟回拨处理：等待或抛出异常
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try { Thread.sleep(offset << 1); } catch (Exception e) {}
                timestamp = System.currentTimeMillis();
            } else throw new RuntimeException("Clock moved backwards");
        }
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & ((1 << sequenceBits) - 1);
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }
        lastTimestamp = timestamp;
        return ((timestamp - twepoch) << (workerIdBits + sequenceBits))
                | (workerId << sequenceBits)
                | sequence;
    }

    private long tilNextMillis(long lastTs) {
        long ts = System.currentTimeMillis();
        while (ts <= lastTs) ts = System.currentTimeMillis();
        return ts;
    }
}

拓展：百度开源的 UidGenerator、美团 Leaf 提供了更健壮的方案，支持时钟回拨自动补偿。
https://htnus.cn/