⚒️

シャーディングとコンシステントハッシュ法

2022/02/08に公開約2,200字

概要

シャーディングのリクエストの割り振り方を学習する。

わかったこと

コンシステントハッシュ法と呼ばれるアルゴリズムを使用するとうまく割り振ることができる。

内容

各ノードにkeyに対応したキャッシュを持っていてシャーディング(水平分割)したいケースを考えます。 ルートノードはリクエストされたkeyをみてキャッシュを保持しているノードにリクエストを割り振ります。
どのように割り振ればキャッシュヒット率を上げることができるのでしょうか?

リクエスト先をmodで割り振る

まず初めにkeyの値の余りを利用して各ノードがキャッシュを保持し、リクエストを割り振るアルゴリズムを採用してみます。

この方法を使用すると、keyの番号が7のリクエストが来た場合にはノード数3で割った余りが1であるのでキャッシュが存在するノード1にリクエストを正しく割り振ることができます。

次にリクエストが大量に来たのでノードの台数を一台増やして水平にスケールさせてみます。

ノードの台数が増えたことによりルートノードはkeyを4で割った余りで割り振るようになります。
追加直後に各ノードは担当のキャッシュを再度取り直す必要があります。そのため、キャッシュヒット率が一時的に低下します。例えば一つ前の例ではkeyが7のリクエストは7mod3 = 1であり1番のノードに割り振られましたが、ノードが4台になった場合は7mod4 = 3で3番のノードにリクエストを割り振られることになります。
3番のノードは今まで3で割ってあまりが0になるkeyのデータしかキャッシュしていなかったためキャッシュミスになってしまいます。ノードの台数が増えるたびにほぼすべてのkeyのキャッシュを取り直す必要があるため効率的ではありません。

ノードの台数で割ったあまりで割り振る方法は、ノードをスケールさせた際にキャッシュヒット率が落ちてしまうことがわかりました。では、どのようにkeyを割り振ればノードをスケールさせる際のキャッシュヒット率の減少を押さえることができるのでしょうか。
この問題を解決するためにコンシステントハッシュ法と呼ばれるアルゴリズムが使用されています。

コンシステントハッシュ法

スロットとキーにハッシュ値に順序比較可能なものを使用します。
スロットはソート管理し、各キーのハッシュ値はスロットと同じかそれより大きい値の中から一番近いものを選んで同じグループとみなします。各スロットにノードサーバを割り当てます。

先ほどと同様にリクエストの増加に伴いノードサーバを増やしたとします。
それに伴い、スロットの数を増やし各keyのグループを再計算します。

すると今回の例では一つのkeyを別ノードに移すだけでスケールが完了しました。
キーの数をK, スロット数(ノードサーバの数)nとすると平均してK/n個のkeyのマッピングの変更で済むため先程の余りで割り振る方法と比較してキャッシュミスを低減することができました。

まとめ

シャーディングのリクエストの割り振り方を調査し、コンシステントハッシュ法がキャッシュミスを少なくスケールさせられることがわかりました。

参考文献

分散システムデザインパターン

コンシステントハッシュ法 wiki

Discussion

ログインするとコメントできます