PHP 實現一致性哈希算法：Flexihash 核心原理與分佈式應用實戰

一、一致性哈希解決什麼問題？

傳統哈希取模 hash(key) % N 在節點增減時會導致大量鍵值重新映射（雪崩效應）。一致性哈希將節點與鍵映射到同一個 2³² 環狀空間，鍵順時針尋找最近節點，新增/移除節點僅影響鄰近鍵，極大降低遷移成本。

二、Flexihash 核心設計

關鍵數據結構

• _positionToTarget：環上位置 → 節點映射（有序陣列，供二分查找）。
• _targetToPositions：節點 → 其虛擬節點位置列表（用於刪除節點）。
• _replicas：虛擬節點數（預設 64），越多分佈越均勻，但查找、排序開銷增大。
• _hasher：哈希策略介面，支援 CRC32（有號 32 位整數）與 MD5（取前 8 字符十六進制）。

核心流程

1. 添加節點：對節點名稱拼接 0~replicas-1，分別哈希得到位置，寫入兩張映射表，標記需重新排序。
2. 查找：資源哈希得位置，在有序 _positionToTarget 中二分查找首個大於資源位置的節點；若遍歷完未找到，回環取第一個節點（環狀特性）。
3. 刪除節點：遍歷其虛擬位置，從 _positionToTarget 移除，清理 _targetToPositions。

三、完整實現代碼（現代化重構）

 target
    private array $targetPositions = []; // target => [positions]
    private int $replicas;
    private Hasher $hasher;
    private bool $sorted = false;

    public function __construct(Hasher $hasher = null, int $replicas = 64) {
        $this->hasher = $hasher ?? new Crc32Hasher();
        $this->replicas = $replicas;
    }

    public function addTarget(string $target): self {
        if (isset($this->targetPositions[$target])) {
            throw new \InvalidArgumentException("Target '$target' already exists");
        }
        $positions = [];
        for ($i = 0; $i < $this->replicas; $i++) {
            $pos = $this->hasher->hash($target . $i);
            $this->ring[$pos] = $target;
            $positions[] = $pos;
        }
        $this->targetPositions[$target] = $positions;
        $this->sorted = false;
        return $this;
    }

    public function removeTarget(string $target): self {
        foreach ($this->targetPositions[$target] ?? [] as $pos) {
            unset($this->ring[$pos]);
        }
        unset($this->targetPositions[$target]);
        return $this;
    }

    public function getTargets(): array {
        return array_keys($this->targetPositions);
    }

    public function lookup(string $resource): string {
        $list = $this->lookupList($resource, 1);
        if (!$list) throw new \RuntimeException('No targets available');
        return $list[0];
    }

    public function lookupList(string $resource, int $count): array {
        if ($count <= 0) throw new \InvalidArgumentException('Count must be > 0');
        if (empty($this->ring)) return [];
        if (count($this->targetPositions) === 1) {
            return array_unique(array_values($this->ring));
        }
        $this->ensureSorted();
        $resourcePos = $this->hasher->hash($resource);
        $results = [];
        $keys = array_keys($this->ring);
        // 二分查找首個 >= resourcePos 的索引
        $idx = $this->binarySearch($keys, $resourcePos);
        $n = count($keys);
        for ($i = 0; $i < $n && count($results) < $count; $i++) {
            $pos = $keys[($idx + $i) % $n];
            $target = $this->ring[$pos];
            if (!in_array($target, $results, true)) {
                $results[] = $target;
            }
        }
        return $results;
    }

    private function ensureSorted(): void {
        if (!$this->sorted) {
            ksort($this->ring, SORT_REGULAR);
            $this->sorted = true;
        }
    }

    private function binarySearch(array $keys, int $value): int {
        $low = 0;
        $high = count($keys) - 1;
        while ($low <= $high) {
            $mid = (($low + $high) >> 1);
            if ($keys[$mid] < $value) {
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        }
        return $low % count($keys); // 環狀回繞
    }
}

四、實戰應用場景

1. 分佈式緩存（Redis Cluster 客戶端路由）

$hash = new ConsistentHash(new Md5Hasher(), 128);
$hash->addTarget('redis-1:6379')
     ->addTarget('redis-2:6379')
     ->addTarget('redis-3:6379');

$key = 'user:10001:profile';
$redisNode = $hash->lookup($key); // 穩定路由到同一節點
// 擴容時只需 addTarget('redis-4:6379')，極少鍵遷移

2. 負載均衡（無狀態服務節點選擇）

$lb = new ConsistentHash(new Crc32Hasher(), 64);
$lb->addTarget('api-1.internal')
   ->addTarget('api-2.internal')
   ->addTarget('api-3.internal');

$requestId = $_SERVER['HTTP_X_REQUEST_ID'] ?? uniqid();
$backend = $lb->lookup($requestId); // 同一請求 ID 固定落點，利於追蹤

3. 分庫分表路由

$shard = new ConsistentHash(new Md5Hasher(), 256);
for ($i = 0; $i < 16; $i++) {
    $shard->addTarget("shard_{$i}");
}
$table = $shard->lookup("user_{$uid}"); // 取代 uid % 16，擴容平滑

五、效能與調優建議

六、總結

一致性哈希通過「環狀空間 + 虛擬節點」優雅解決分佈式系統的動態擴縮容路由問題。Flexihash 以 ~200 行代碼實現了完整功能，生產環境建議：

• 使用無號 32 位整數空間，避免 PHP 有號整數溢出陷阱。
• 引入 SortedArray 或 SplFixedArray 優化環存儲與二分查找。
• 結合健康檢查自動剔除失效節點，實現真正的高可用路由。