1. 场景：一次扩容引发雪崩

去年双11前夕，我们的缓存集群分16个节点，用 mod(key, 16) 决定存储位置。双11流量预估需要扩展到20个节点。结果扩容刚完成，数据库连接数瞬间打满，大量超时告警。复盘发现：取模哈希扩容后，原有key映射到新节点需要迁移 16/20 = 80% 以上的数据，迁移过程导致缓存击穿，流量直接打到DB。

这次教训让我们必须换用一致性哈希——它能在节点增删时只迁移少量数据（理论上约 1/N）。但理论归理论，工程实现中有很多坑。这篇文章还原我实现一致性哈希分片的全过程，包含可运行的PHP代码、迁移率对比数据、以及踩过的三个大坑。

2. 方案对比：取模 vs 一致性哈希

简单结论：如果节点不会变动，取模足够；但只要计划扩缩容，必须用一致性哈希。

3. 完整代码实现（PHP 8.3）

我们实现一个 ConsistentHash 类，支持节点添加、删除、key查找，使用虚拟节点解决分布不均问题。哈希函数选择 CRC32（快速且均匀）。

 node]
    private array $nodes = [];            // 物理节点列表
    private array $sorted = [];           // 已排序的哈希值（用于二分查找）

    /**
     * @param int $replicas 虚拟节点个数（值越大越均衡，但内存和计算开销增加）
     */
    public function __construct(int $replicas = 64)
    {
        $this->replicas = $replicas;
    }

    /**
     * 添加物理节点
     * @param string $node 节点标识（如 "cache-1"）
     */
    public function addNode(string $node): void
    {
        if (isset($this->nodes[$node])) {
            return;
        }
        $this->nodes[$node] = true;
        for ($i = 0; $i < $this->replicas; $i++) {
            $hash = $this->hash($node . ':' . $i);
            $this->ring[$hash] = $node;
        }
        $this->sortRing();
    }

    /**
     * 删除物理节点
     * @param string $node
     */
    public function removeNode(string $node): void
    {
        if (!isset($this->nodes[$node])) {
            return;
        }
        unset($this->nodes[$node]);
        for ($i = 0; $i < $this->replicas; $i++) {
            $hash = $this->hash($node . ':' . $i);
            unset($this->ring[$hash]);
        }
        $this->sortRing();
    }

    /**
     * 查找key应分配到的物理节点
     * @param string $key
     * @return string
     */
    public function getNode(string $key): string
    {
        if (empty($this->sorted)) {
            throw new RuntimeException("No nodes available");
        }
        $hash = $this->hash($key);
        // 二分查找第一个大于等于hash的位置
        $index = $this->binarySearch($hash);
        // 如果没有找到（hash大于所有环上的值），则取环的第一个节点（顺时针取首）
        if ($index >= count($this->sorted)) {
            $index = 0;
        }
        $targetHash = $this->sorted[$index];
        return $this->ring[$targetHash];
    }

    /**
     * 获取所有物理节点（方便迁移验证）
     * @return array
     */
    public function getNodes(): array
    {
        return array_keys($this->nodes);
    }

    private function hash(string $str): int
    {
        // 使用CRC32，返回无符号32位整数
        return crc32($str) & 0xFFFFFFFF;
    }

    private function sortRing(): void
    {
        $this->sorted = array_keys($this->ring);
        sort($this->sorted, SORT_NUMERIC);
    }

    private function binarySearch(int $needle): int
    {
        // 二分查找返回第一个 >= needle 的索引
        $low = 0;
        $high = count($this->sorted) - 1;
        while ($low <= $high) {
            $mid = intdiv($low + $high, 2);
            if ($this->sorted[$mid] < $needle) {
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        }
        return $low;
    }
}

使用示例：

// test.php
require_once 'ConsistentHash.php';

$ch = new ConsistentHash(64);  // 每个物理节点64个虚拟节点
$ch->addNode('server-1');
$ch->addNode('server-2');
$ch->addNode('server-3');

$key = 'user:10001';
echo $ch->getNode($key); // 输出 server-2 或类似

4. 迁移率对比验证

我们用一段测试代码模拟：初始10个节点，插入1000个随机key，记录每个key的归属节点。然后增加1个节点（10→11），分别用取模和一致性哈希计算迁移的key数。

// migration_test.php
require_once 'ConsistentHash.php';

function simulateMod(int $oldCount, int $newCount, array $keys): array
{
    $migrated = 0;
    $total = count($keys);
    foreach ($keys as $k) {
        $oldNode = crc32($k) % $oldCount;
        $newNode = crc32($k) % $newCount;
        if ($oldNode !== $newNode) {
            $migrated++;
        }
    }
    return ['migrated' => $migrated, 'total' => $total, 'rate' => $migrated / $total];
}

function simulateConsistent(ConsistentHash $chOld, ConsistentHash $chNew, array $keys): array
{
    $migrated = 0;
    $total = count($keys);
    foreach ($keys as $k) {
        $oldNode = $chOld->getNode($k);
        $newNode = $chNew->getNode($k);
        if ($oldNode !== $newNode) {
            $migrated++;
        }
    }
    return ['migrated' => $migrated, 'total' => $total, 'rate' => $migrated / $total];
}

// 生成1000个随机key
$keys = [];
for ($i = 0; $i < 1000; $i++) {
    $keys[] = 'key-' . bin2hex(random_bytes(4));
}

// 取模测试
$modOldResult = simulateMod(10, 11, $keys);
echo "取模哈希 10→11 迁移率: " . round($modOldResult['rate'] * 100, 2) . "%\n";

// 一致性哈希测试
$chOld = new ConsistentHash(64);
for ($i = 1; $i <= 10; $i++) {
    $chOld->addNode("server-$i");
}
$chNew = new ConsistentHash(64);
for ($i = 1; $i <= 11; $i++) {
    $chNew->addNode("server-$i");
}
$chResult = simulateConsistent($chOld, $chNew, $keys);
echo "一致性哈希 10→11 迁移率: " . round($chResult['rate'] * 100, 2) . "%\n";

运行结果（实际输出）：

$ php migration_test.php
取模哈希 10→11 迁移率: 90.87%
一致性哈希 10→11 迁移率: 9.47%

一致性哈希迁移率约9.5%，接近理论值 1/11 ≈ 9.09%。取模达到了90%以上，符合预期。

5. 效果数据：虚拟节点个数对分布均匀性的影响

虚拟节点太少会导致节点在环上分布不均，实际负载有偏差。我们测试不同 replicas 值下，10节点1000key分配到各节点的key数量标准差（越小越均衡）。

建议生产环境选64~256之间，平衡内存和均衡性。

6. 避坑指南（真实踩过的坑）

坑1：哈希函数选择不当

一开始用 md5($key) 然后截取前8位转为int，发现哈希分布严重不均匀——因为md5的二进制后几位有偏斜。改用 crc32 后均匀性显著提升。后来用过 fnv1a32 效果也不错。但注意crc32在PHP返回的是有符号整型，需要 & 0xFFFFFFFF 转无符号。

坑2：虚拟节点过多导致内存和查找变慢

100个物理节点，replicas=1024，环上有102400个元素，每次查找需要二分查找 O(log 102400) ≈ 17次比较，可以接受。但内存占用：每个环元素是一个int键+string值，约50字节，总共约5MB，还可以。但如果你有1000个物理节点，就要考虑缩减replicas到64。另外，添加/删除节点时需要重建整个排序数组，replicas太大会让节点变更变慢。

坑3：删除节点时的数据丢失

一开始我们写removeNode直接删虚拟节点，但此时该节点上还有数据。在缓存场景下，需要先让该节点上的key过期或主动迁移走，再摘掉节点。我的做法：在删除节点前，先遍历该节点上的所有key（需要额外索引），迁移到新节点，再删除。如果做不到，就设置一个过渡期，让旧节点为只读，新节点同时写入，最后再删除。

坑4：环形分布偏斜（热点）

即使有虚拟节点，如果物理节点的权重不同，环仍可能偏斜。我们增加了加权虚拟节点：为高性能节点分配更多虚拟节点（比如普通节点64个，高性能节点128个）。实现上在 addNode 时传入权重。

坑5：二分查找的边界条件

一开始用 array_search 遍历环，O(n) 太慢。改用二分查找后，注意当hash大于环上所有值时，应该取第一个节点（环形闭合）。代码中 if ($index >= count($this->sorted)) $index = 0; 这个条件容易写错成 >。

7. 总结

一致性哈希不是银弹，但在分布式分片场景下极大降低了节点变动带来的数据迁移量。实现时注意哈希函数、虚拟节点数、节点管理流程。上面代码可直接用于小规模分片，生产环境建议使用成熟的库如 flexihash/php-hashring 或直接基于 Redis Cluster 的槽分配。

最后说一句：永远不要在生产环境拿未测试的一致性哈希代码直接上线——我曾因 sort 默认字符串排序导致环上乱序，二分查找全失效。代码必须经过单元测试和迁移比例验证。