一致性哈希解決分散式快取擴縮容時的「雪崩效應」：傳統取模 hash(key) % N 會導致節點變動時所有鍵值重新分佈。Ketama 算法（Memcached 客戶端標準）在哈希環上為每個物理節點建立多個虛擬節點，僅影響鄰近虛擬節點的鍵值。本文提供生產級 PHP 實作。
<?php
namespace App\Cache;
class ConsistentHash {
/** @var array 虛擬節點哈希值 => 節點標識 "host:port" */
private array $ring = [];
/** @var array 節點標識 => 虛擬節點數 */
private array $nodeVirtualCount = [];
/** @var int 每物理節點虛擬節點數（建議 100-200） */
private int $virtualNodes = 160;
/** @var callable 哈希函數（預設 crc32，速度快、分佈均勻） */
private callable $hasher;
public function __construct(array $nodes = [], int $virtualNodes = 160, ?callable $hasher = null) {
$this->virtualNodes = $virtualNodes;
$this->hasher = $hasher ?? static fn($data) => sprintf('%u', crc32($data));
foreach ($nodes as $node) {
$this->addNode($node);
}
}
/** 新增物理節點 */
public function addNode(string $node): void {
if (isset($this->nodeVirtualCount[$node])) {
return; // 已存在
}
for ($i = 0; $i < $this->virtualNodes; $i++) {
$key = $this->hasher("{$node}#{$i}");
$this->ring[$key] = $node;
}
$this->nodeVirtualCount[$node] = $this->virtualNodes;
ksort($this->ring); // 維護有序環
}
/** 移除物理節點 */
public function removeNode(string $node): void {
if (!isset($this->nodeVirtualCount[$node])) return;
foreach ($this->ring as $hash => $n) {
if ($n === $node) {
unset($this->ring[$hash]);
}
}
unset($this->nodeVirtualCount[$node]);
}
/** 獲取鍵對應的節點 */
public function getNode(string $key): ?string {
if (empty($this->ring)) return null;
$hash = $this->hasher($key);
// 二分查找：找到第一個 >= hash 的虛擬節點
$hashes = array_keys($this->ring);
$idx = $this->binarySearch($hashes, $hash);
// 環狀：若超過最大值，回到第一個
if ($idx === count($hashes)) $idx = 0;
return $this->ring[$hashes[$idx]];
}
/** 二分查找：返回第一個 >= target 的索引 */
private function binarySearch(array $sorted, int|string $target): int {
$low = 0;
$high = count($sorted) - 1;
while ($low <= $high) {
$mid = (($low + $high) >> 1);
if ($sorted[$mid] < $target) {
$low = $mid + 1;
} else {
$high = $mid - 1;
}
}
return $low; // 插入位置 = 第一個 >= target
}
/** 獲取所有物理節點 */
public function getNodes(): array {
return array_keys($this->nodeVirtualCount);
}
/** 除錯：列印環分佈 */
public function debugRing(): void {
foreach ($this->ring as $hash => $node) {
echo "{$hash} => {$node}\n";
}
}
}
?><?php
namespace App\Cache;
class MemcacheCluster {
private ConsistentHash $hashRing;
/** @var array 連線池 */
private array $connections = [];
public function __construct(array $servers, int $virtualNodes = 160) {
$this->hashRing = new ConsistentHash($servers, $virtualNodes);
// 建立連線池（延遲連線）
foreach ($servers as $server) {
$this->connections[$server] = null;
}
}
private function getConnection(string $server): Memcached {
if (!isset($this->connections[$server]) || $this->connections[$server] === null) {
[$host, $port] = explode(':', $server);
$mc = new Memcached();
$mc->addServer($host, (int)$port);
// 設定選項
$mc->setOption(Memcached::OPT_CONNECT_TIMEOUT, 1000); // 1ms
$mc->setOption(Memcached::OPT_RETRY_TIMEOUT, 1);
$mc->setOption(Memcached::OPT_DISTRIBUTION, Memcached::DISTRIBUTION_CONSISTENT);
$mc->setOption(Memcached::OPT_LIBKETAMA_COMPATIBLE, true); // 關鍵：啟用 libketama 相容
$this->connections[$server] = $mc;
}
return $this->connections[$server];
}
public function get(string $key): mixed {
$server = $this->hashRing->getNode($key);
if (!$server) throw new \RuntimeException('無可用節點');
return $this->getConnection($server)->get($key);
}
public function set(string $key, mixed $value, int $expire = 0): bool {
$server = $this->hashRing->getNode($key);
if (!$server) throw new \RuntimeException('無可用節點');
return $this->getConnection($server)->set($key, $value, $expire);
}
public function delete(string $key): bool {
$server = $this->hashRing->getNode($key);
if (!$server) return false;
return $this->getConnection($server)->delete($key);
}
/** 動態增減節點（運維介面調用） */
public function addServer(string $server): void {
$this->hashRing->addNode($server);
$this->connections[$server] = null;
}
public function removeServer(string $server): void {
$this->hashRing->removeNode($server);
// 關閉連線
if (isset($this->connections[$server]) && $this->connections[$server] !== null) {
$this->connections[$server]->quit();
}
unset($this->connections[$server]);
}
}
?> | 優化 | 說明 | 效果 |
|---|---|---|
| 虛擬節點數 160 | 經驗值：100-200 平衡分佈均勻度與記憶體/查找速度 | 節點 10 個時，鍵分佈標準差 < 5% |
| 哈希函數 crc32 | PHP 內建、極快、32 位無符號整數空間足夠 | 比 md5/sha1 快 10 倍以上 |
| 二分查找 O(log N) | 虛擬節點 1600 個時，查找約 11 步 | 比線性查找快 100 倍 |
| 連線池複用 | 避免每請求新建 Memcached 物件 | 減少 TCP 握手、記憶體分配 |
OPT_LIBKETAMA_COMPATIBLE | 讓 PHP Memcached 擴展內建一致性哈希與客戶端算法一致 | 可直接用擴展原生分佈，無需 PHP 層實作 |
<?php
$servers = ['127.0.0.1:11211', '127.0.0.1:11212', '127.0.0.1:11213', '127.0.0.1:11214', '127.0.0.1:11215'];
$cluster = new MemcacheCluster($servers, 160);
// 測試分佈均勻度
$dist = [];
for ($i = 0; $i < 100000; $i++) {
$key = "key_{$i}";
$node = $cluster->getNode($key);
$dist[$node] = ($dist[$node] ?? 0) + 1;
}
echo "分佈統計:\n";
foreach ($dist as $node => $count) {
echo "{$node}: {$count} (" . round($count/1000, 2) . "%)\n";
}
// 測試 set/get 效能
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
$key = "perf_{$i}";
$cluster->set($key, "value_{$i}", 3600);
}
echo "Set 10000: " . round(microtime(true) - $start, 4) . "s\n";
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
$cluster->get("perf_{$i}");
}
echo "Get 10000: " . round(microtime(true) - $start, 4) . "s\n";
?>PHP Memcached 擴展 (libmemcached) 內建 Ketama 一致性哈希，**無需 PHP 層實作**：
<?php
$mc = new Memcached();
$mc->addServers([
['127.0.0.1', 11211, 20], // 權重 20
['127.0.0.1', 11212, 20],
['127.0.0.1', 11213, 20],
]);
// 關鍵選項
$mc->setOption(Memcached::OPT_DISTRIBUTION, Memcached::DISTRIBUTION_CONSISTENT);
$mc->setOption(Memcached::OPT_LIBKETAMA_COMPATIBLE, true); // 必須開啟
$mc->setOption(Memcached::OPT_HASH, Memcached::HASH_CRC); // 或 HASH_MD5
// 直接使用，擴展自動處理一致性哈希分佈
$mc->set('key', 'value');
$val = $mc->get('key');
?>優勢：C 層實作、效能最高、支援權重、自動處理節點失效移除。建議生產環境直接用此方式，PHP 層實作僅供教學或特殊需求（如自定義哈希、跨語言一致性）。
一致性哈希是分散式快取的核心演算法。PHP 實作關鍵在於：
crc32 高效哈希OPT_LIBKETAMA_COMPATIBLE避免自造輪子，除非有跨語言一致性、特定哈希函數、或需在無擴展環境運行的特殊需求。
