⚒️

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

2022/02/08に公開

tech

概要

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

わかったこと

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

内容

各ノードに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を割り振ればノードをスケールさせる際のキャッシュヒット率の減少を押さえることができるのでしょうか。
この問題を解決するためにコンシステントハッシュ法と呼ばれるアルゴリズムが使用されています。