Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
March 18, 2025コンシステントハッシュ法は、Content Delivery Network (CDN) 規模のキャッシュシステムの負荷分散に使われている。 コンシステントハッシュ法を提案したConsistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Webは、特定のキャッシュサーバーへのリクエストの集中を避けることを目的にする。
Random Treeはd分木であり、ノードはコンシステントハッシュ法でキャッシュサーバーに写像される。 ルートノードのキャッシュサーバーにはすべてのページのキャッシュがある仮定の上で、リクエストに応じて、キャッシュは親ノードのキャッシュサーバーから子ノードのキャッシュサーバーにコピーされる。 ページのリクエストがあると、葉がランダムに選ばれる。 リクエストは葉のキャッシューサーバーにルーティングされ、キャッシューサーバーにページのキャッシュがあれば、キャッシュをリクエスト元に返す。 ページがなければ、親ノードにページを問い合わせ、その応答をリクエスト元に返す。 同様にページがなければ、親ノードはさらに親ノードに問い合わせる。 ノードはページごとにキャッシュミスの回数を数え、しきい値以上キャッシュミスがあればそのページをキャッシュする。
Random Treeの構造はハードウェアと直接関係しないので不変にできるが、アクティブなキャッシュサーバーの集合の変化は避けられない。 また、各キャッシュサーバーがほかのすべてのキャッシューサーバーと通信できるとは限らない。 キャッシュサーバーやノードの集合の変わればハッシュ関数も変わるが、ハッシュ関数の変化は小さいほどのぞましい。 変化が大きいほど、変更すべき写像関係が増えるだけでなく、Random Treeによるキャッシュの分散の効果が失われる。
コンシステントハッシュ法は、写像されるノード数をキャッシュサーバー間で均等にするだけでなく、キャッシュサーバーの増減時に移動するノードの数を減らすこともできる。 値域が単位区間 () のハッシュ関数でキャッシュサーバーとノードの実数を計算する。 ノードはその実数と最も近い実数のキャッシュサーバーに割り当てられる。 キャッシュサーバーを追加したら、隣接するキャッシュサーバーにあるノードの実数を調べ、追加したキャッシュサーバーがよりノードと近ければ、ノードを追加したキャッシュサーバーに移す。 キャッシュサーバーを削除するときは、キャッシュサーバーの実数よりも大きい実数のノードを後続のキャッシュサーバーに、小さい実数のノードを前のキャッシュサーバーに移す。 より大きい実数がなければ、かわりに最小の実数のキャッシュサーバーを参照する。
より具体的には、各キャッシュサーバーに複数の実数を割り当てる。 キャッシュサーバーを追加、削除すると、隣接するキャッシュサーバーのみノードの数が増減する。 キャッシューサーバーに複数の実数を割当てることで、分配されるキャッシュサーバーの数が増やし、キャッシュサーバーの負荷をより均等に保たせる。
リクエストは、リクエスト元、求めるページのID, Random Treeの葉からルートへの経路、経路上のノードに対応するキャッシュサーバーのシーケンスの4組の要素からなる。 最後のシーケンスは、ルートへの経路上のノードにコンシステントハッシュ法を適用して特定したキャッシュサーバーからなる。
文献には2分木で実数に対応するキャッシュサーバーやノードの探索を実装するアルゴリズムが説明されているが、A Fast, Minimal Memory, Consistent Hash AlgorithmやMulti-probe consistent hashingなどの方法もある。