PHP 實現一致性哈希算法：Flexihash 庫深度解析與分佈式路由應用

一致性哈希解決了分佈式系統中節點增減導致的大規模鍵遷移問題。本文深度解析 Flexihash 這個經典 PHP 實現，剖析虛擬節點、環狀哈希空間、查找邏輯、擴展接口，並展示如何在分佈式緩存、數據庫分片、服務路由中落地應用。

🎯 一致性哈希核心原理

1. 哈希環：將哈希值空間（0 ~ 2³²-1）組織為一個環。
2. 節點映射：每個物理節點通過哈希函數映射到環上一個或多個位置。
3. 虛擬節點：每個物理節點對應多個虛擬節點（Replicas），解決物理節點少時分佈不均問題。
4. 鍵定位：鍵哈希後在環上順時針查找最近的虛擬節點，所屬物理節點即為目標節點。
5. 變更影響：節點增減僅影響順時針方向相鄰區間的鍵，避免全量重分佈。

📦 Flexihash 核心類結構

public function addTarget($target) {
    if (isset($this->_targetToPositions[$target])) {
        throw new Exception("Target '$target' already exists.");
    }
    $this->_targetToPositions[$target] = [];
    
    for ($i = 0; $i < $this->_replicas; $i++) {
        $position = $this->_hasher->hash($target . $i); // "node1:0", "node1:1"...
        $this->_positionToTarget[$position] = $target; // 查找用
        $this->_targetToPositions[$target][] = $position; // 刪除用
    }
    $this->_positionToTargetSorted = false;
    $this->_targetCount++;
    return $this;
}

2. 移除節點：精確清理

_targetToPositions[$target] as $position) {
        unset($this->_positionToTarget[$position]);
    }
    unset($this->_targetToPositions[$target]);
    $this->_targetCount--;
    return $this;
}

3. 查找路由：環狀順時針搜索

private function _sortPositionTargets() {
    if (!$this->_positionToTargetSorted) {
        ksort($this->_positionToTarget, SORT_REGULAR); // 按哈希值升序
        $this->_positionToTargetSorted = true;
    }
}

🚀 實戰應用示例

1. 分佈式緩存路由

$shards = ['shard-01', 'shard-02', 'shard-03', 'shard-04'];
$router = (new Flexihash())->addTargets($shards);

// 用戶 ID 路由到固定分片
$userId = 12345;
$shard = $router->lookup("user:{$userId}"); // 同一用戶始終路由到同一分片
// 執行分片查詢...

3. 服務發現與負載均衡

場景推薦配置說明

緩存集群（Memcached/Redis Cluster 客戶端）CRC32 + 128-256 replicasCRC32 極快，虛擬節點多分佈均勻
持久化存儲分片（MySQL/MongoDB）MD5 + 64-128 replicasMD5 分佈更隨機，跨語言一致性好
服務網格路由CRC32 + 32 replicas實例變更頻繁，較少虛擬節點重排快
多副本查找（N 個備選節點）lookupList($key, N)用於寫入多副本、讀取故障轉移



🔧 進階擴展：Ketama 算法兼容
Flexihash 邏輯與業界標準 Ketama（Memcached 客戶端標準算法）一致。若需與 Java/Go/Python 客戶端互通，統一使用 MD5 哈希 + 160 虛擬節點/物理節點 + 節點標識格式「host:port」 即可實現跨語言一致路由。