Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
June 19, 2021各サーバーがネットワーク全体の情報を保持しない分散キャッシュネットワークにホットスポットを生まないためのキャッシュプロトコルを開発した。 表題のconsistent hashingは、プロトコルの基礎になるハッシュ関数で、関数の写像が値域の違いに影響されにくい。 この影響しにくさは、クライアントから見えるアクティブなサーバが入れ替わる可能性に対して機能する。 また、クライアントは一部のキャッシュサーバーにアクセスできればよく、クライアントごとにアクセス可能なキャッシュサーバーの集合は違ってよい。
キャッシュサーバーが複数ある場合、クライアントは、オブジェクトのキャッシュをホストするサーバを特定しなければならない。 サーバーとクライントでハッシュ関数を共有し、オブジェクトをキャッシュすべきサーバーをハッシュ値で決めれば、クライアントはサーバーに問い合わせることなく対象のサーバーを特定できる。 ただし、ネットワークの状況やキャッシュサーバーの動的な入れ替え次第で、クライアントから見えるキャッシュサーバーの集合は変わる。 クライアントから見えるサーバーの集合に特定方法が依存するほど、集合が変化したときに無効になるキャッシュデータの数が増える。 consistent hashingは、クライアントから見えるキャッシュサーバーの集合をviewと称し、viewに一貫性がなくても、オブジェクトできるかぎり同じキャッシュサーバーにキャッシュできるように、値域の変化に写像が影響されにくように設計されている。
一貫性を定義するために、balance, monotonicity, spread, loadの4つの指標を導入する。 \(\mathcal{I}\)をキャッシュするオブジェクトの集合、\(\mathcal{B}\)をキャッシュサーバーの集合とする。 このときview \(\mathcal{V}\)は\(\mathcal{B}\)の部分集合にあたる。 求めるハッシュ関数は\(f: 2^{\mathcal{B}}\times\mathcal{I}\rightarrow \mathcal{B}\)の形で、ranged hash functionという。 各\(\mathcal{V}\)について\(f_{\mathcal{V}}(\mathcal{I}) \subseteq \mathcal{V}\)でなければならない。 \(f\)の集合をranged hash familyといい、\(\mathcal{F}\)と略記する。
balanceは、キャッシュサーバーにオブジェクトが均等に分配される程度を意味する。 あるview \(\mathcal{V}\)が与えられたとき、\(\mathcal{F}\)から無作為に\(f\)を選んでも、どんなキャッシューサーバについてもオブジェクトが写像される確率がある確信度以上で\(O(1/\mid V \mid)\)になるとき、\(\mathcal{F}\)はbalancedであるという。 確信度は、ユーザーがパラメタ\(N\)で\(1-1/N\)と定義できる。
monotonicityは、viewに新しいキャッシュサーバーを追加したときに、オブジェクトが新しいキャッシュサーバーに移ることはあっても、昔からある別のキャッシュサーバーに移らないことを保証する。 すべてのviewについて、\(\mathcal{V}_1 \subseteq \mathcal{V}_2 \subseteq \mathcal{B}, f_{\mathcal{V}_2}(i)\in \mathcal{V}_1\)であれば\(f_{\mathcal{V}_1(i)}=f_{\mathcal{V}_2(i)}\)であれば、\(f\)はmonotoneであるという。 すべての\(f\)がmonotoneであれば、\(\mathcal{F}\)はmonotoneである。
viewの集合があり、各viewについて\(f_{\mathcal{V}}(\mathcal{I}) \subseteq \mathcal{V}\)になる割り当て方であれば、あるオブジェクトを格納しているキャッシュサーバーの数が少ないほうがサーバーの使用効率がよい。この指標をspreadという。 \(\mathcal{V}_1\dots \mathcal{V}_V\)をviewの集合、各viewは少なくとも\(C/t\)のキャッシュサーバーをもち、集合全体で\(C\)個の個別のキャッシュサーバーがあるとする。 このとき、オブジェクト\(i\)のspread \(\sigma(i)\)を\(\mid \{f_{\mathcal{V}_j}(i)\}^{V}_{j=1}\mid\)と定義し、 \(\sigma(f)\)を\(\sigma(i)\)の最大値とする。 ある確信度以上でランダムに選んだ\(f\)のspreadが\(\sigma\)になるとき、\(\mathcal{F}\)のspreadを\(\sigma\)とする。
loadは、spreadと同様にキャッシュサーバーの負荷の指標であり、キャッシュサーバーがホストするオブジェクトの数を評価する。 キャッシュサーバー\(b\)のload \(\lambda(b)\)を\(\mid\cup_{\mathcal{V}}f^{-1}_{\mathcal{V}}(b)\mid\)と定義する。 ただし、\(f^{-1}_{\mathcal{V}}(b)\)はview \(\mathcal{V}\)にあるキャッシュサーバー\(b\)に割り当てられたオブジェクトの集合を示す。 loadが最大のキャッシュサーバーのloadを\(f\)のloadとする。 また、ランダムに選んだ\(f\)がある確信度以上でloadの値が\(\lambda\)であれば、その値を\(\mathcal{F}\)のloadとする。
キャッシューサーバを単位区間のある値にランダムに写像する関数を\(r_{\mathcal{B}}\), オブジェクトを同区間にランダムに写像する関数を\(r_{\mathcal{I}}\)とおく。 このとき、\(f_\mathcal{V}(i)\)を\(\mid r_{\mathcal{B}}-r_{\mathcal{I}}(i)\mid\)を最小にする\(\mathcal{b}\in \mathcal{V}\)とする。 いいかえると、\(f\)は\(i\)を最も近い\(b\)に割りあてる。 当該範囲のキャッシュサーバーの数が常に\(C\)より少ないとすると、\(\kappa\)を定数として、各キャッシュサーバーごとに\(\kappa\log(C)\)個のコピーをつくり、コピーを無作為に写像するように\(r_{\mathcal{B}}\)を定義する。 以上の\(f\)の\(\mathcal{F}\)は次の性質を満たす。
- \(\mathcal{F}\)はmonotone.
- Balance: ある固定した\(\mathcal{V}\)について、\(i\in \mathcal{I}\), \(b\in \mathcal{V}\)とすると\(r_{\mathcal{B}}\)によらず\(\text{Pr}[f_{\mathcal{V}}(i)= b]\le \frac{\mathcal{O}(1)}{\mid\mathcal{V}\mid}\)
- Spread: \(\rho\)を定数、viewの数を\(V=\rho C\), オブジェクトの数を\(I=C\)とすると、\(i\in \mathcal{I}\)について、\(1-1/C^{\Omega(1)}\)より大きい確率で\(\sigma(i)\)は\(O(t\log(C))\)になる。
- load: \(b\in\mathcal{B}\)について、\(1-1/C^{\Omega(1)}\)より大きい確率で\(\lambda(b)\)は\(O(t\log(C))\)になる。
論文をこちらからダウンロードできます。