LASSIC Media らしくメディア
コンシステントハッシュ法｜分散データ配置の仕組み
大量のアクセスをさばく大規模なサービスでは、データを一台にまとめて置くのではなく、複数のサーバへ分けて預ける「分散」がよく採られます。その際に悩ましいのが、「あるデータをどのサーバに置くか」という割り当ての決め方です。ここで素朴なやり方を選ぶと、サーバを一台増やしたり減らしたりするたびに、大量のデータを置き直す羽目になりかねません。
この置き直しをできるだけ小さく抑える工夫が、コンシステントハッシュ法です。分散型のデータベースやキャッシュ、CDNなど、規模を伸ばしながら止めずに動かし続ける基盤の土台として、長く使われてきました。この記事では、発注者やプロジェクトマネージャー、これから分散システムの設計に関わる方に向けて、その仕組みと使い分けの勘所をかみくだいて整理していきます。
コンシステントハッシュ法とは
コンシステントハッシュ法とは、データをどのサーバに置くかを決める割り当てのやり方の一つで、サーバの増減があっても、置き直すデータをできるだけ少なく抑えることを狙った仕組みです。「一貫性のあるハッシュ法」とも訳され、分散システムでデータやアクセスをならして配る場面で用いられます。
基本の発想はこうです。サーバとデータの両方を、同じ計算（ハッシュ）で数値に変え、その数値を大きな円環（リング）の上に並べます。そして、あるデータは、自分の位置から円環を時計回りにたどり、最初に出会ったサーバに預けられる、という決め方をとります。置き場所を円環に見立てて考えるのが、この手法の目印といえるでしょう。
この置き方のうれしいところは、サーバが一台増減しても、その影響が円環上でとなり合う一部の区間だけにとどまる点にあります。全体を割り当て直すのではなく、ずれるのはごく一部分だけ——この「変化の波及を小さく閉じ込める」ふるまいこそが、コンシステントハッシュ法の値打ちなのです。
この記事のポイント
- コンシステントハッシュ法は、サーバの増減時に置き直すデータを小さく抑える割り当ての仕組みです。
- サーバとデータを円環（ハッシュリング）上に並べ、時計回りでたどって最初のサーバに預けます。
- 仮想ノードを併用して偏りをならし、分散データベースやキャッシュ、CDNで広く使われています。
単純なハッシュ分散の限界
コンシステントハッシュ法のありがたみは、いちばん素朴な分け方と比べると際立ちます。まずは、その単純なやり方から見ていきましょう。
よくあるのは、データの番号をサーバの台数で割った余りで置き場所を決めるやり方です。三台あれば余りは0・1・2のいずれかになり、それぞれのサーバに対応させます。台数が変わらないうちは、これで手早くデータをならせるでしょう。
ところが、サーバを一台足して四台にしたとたん、割る数そのものが変わってしまうため、ほとんどのデータで余りが変わります。結果として、大半のデータを別のサーバへ移し替えることになり、移動の負荷が一気に跳ね上がるのです。キャッシュであれば、置き場所がずれた分だけ元データへの問い合わせが集中し、一時的に応答が重くなることもあります。この「増減のたびに全部を組み替える」つらさを避けたい、という動機から生まれたのが、次に見る円環の考え方でした。
| 観点 | 剰余（mod）方式 | コンシステントハッシュ法 |
|---|---|---|
| 割り当ての決め方 | 台数で割った余り | 円環上で時計回りに最初のサーバ |
| サーバ増減時の影響 | ほぼ全データが移動 | となり合う一部の区間だけ |
| 向く場面 | 台数が変わらない用途 | 増減しながら動かし続ける用途 |
ハッシュリングの仕組み
円環（ハッシュリング）を使った置き方を、もう少していねいに追ってみましょう。手順そのものは、意外なほど素直です。
はじめに、それぞれのサーバをハッシュで数値に変え、円環上の点として配置します。続いて、預けたいデータも同じハッシュで数値に変え、同じ円環上に置きます。そのうえで、データの点から時計回りに進み、最初にぶつかったサーバがそのデータの預け先になる、というわけです。下の図は、その関係を表したものになります。
この置き方の要は、サーバを増減させたときのふるまいにあります。サーバを一台加えると、その新しい点の手前にあった区間のデータだけが、新しいサーバへ移ります。ほかの区間はそのままです。逆にサーバが一台抜けたときは、その区間が受け持っていたデータが、円環上で次に控えるサーバへ引き継がれます。動くのはとなり合う範囲に限られ、全体をかき混ぜずに済むところが、この仕組みの持ち味でしょう。
仮想ノードで偏りをならす
円環に点を置くだけでは、実は困りごとが一つ残ります。サーバの点が円環上でかたよって並ぶと、担当する区間の広さに差が生まれ、特定のサーバばかりにデータが集中してしまうのです。とくに台数が少ないうちは、この偏りが目立ちやすくなります。
そこで使われるのが、仮想ノードという工夫です。一台のサーバを、円環上の複数の点として登録するやり方を指します。たとえば一台につき百個の点をばらまいておけば、担当する区間が細かく分かれて円環全体に散らばり、結果として偏りがならされていきます。
仮想ノードには、もう一つの利点があります。サーバごとの性能差に合わせて点の数を変えれば、力のあるサーバには多めに、そうでないサーバには少なめに、と担当量を調整できるのです。ただ均等に配るだけでなく、重みをつけて配れる柔らかさが加わる、と捉えるとよいでしょう。多くの分散型データベースやキャッシュでは、この仮想ノードが最初から組み込まれています。
どこで使われているか
コンシステントハッシュ法は、規模を伸ばしながら止めずに動かすことが問われる、さまざまな基盤で採り入れられてきました。代表的な使いどころを見てみましょう。
| 使われる場面 | 役割の例 |
|---|---|
| 分散型データベース | キーごとにどのサーバへ置くかを決める（DynamoやCassandraの設計に影響） |
| 分散キャッシュ | memcachedなどで、どのサーバに問い合わせるかを振り分ける |
| CDN | コンテンツをどのエッジサーバに載せるかを割り当てる |
| ロードバランサ | 同じ利用者を同じ処理先へ寄せる、といった振り分けに使う |
いずれの用途にも共通するのは、「サーバの数がしばしば変わる」という前提です。故障で抜けたり、混雑に合わせて足したりが日常的に起きる環境では、増減のたびに全体を組み替えずに済むことが、そのまま止まりにくさへつながります。だからこそ、この手法が土台として選ばれてきたのでしょう。名前を表に出さずとも、身近なサービスの裏側で静かに働いている場面は少なくありません。
発注・設計でおさえる点
コンシステントハッシュ法そのものを一から作り込む場面は、実のところ多くありません。ほとんどは、それを内部で使っている製品を選び、正しく設定して活かすことになるのです。発注や設計の段階で意識しておきたい点を挙げます。
製品まかせで済む部分を見極める
分散データベースやキャッシュの多くは、この割り当てを内部で受け持ってくれます。まずは、採用する製品がキーの分散をどう扱うのかを資料で押さえ、自前で組み立てる必要が本当にあるのかを見極めるとよいでしょう。既存の仕組みに任せられるなら、それがいちばん手堅い選び方になります。
偏りと再配置の挙動を確かめる
仮想ノードの数や設定しだいで、データの散らばり方や、サーバ増減時にどれだけ移動が起きるかは変わってきます。導入する前に、想定する台数での偏りぐあいや、増減させたときの移動量を試しておくと、運用に入ってからの驚きを減らせるはずです。あわせて、移動中に一時的な応答の重さが出ないかも見ておきたいところです。
データの守り方とあわせて考える
割り当ての仕組みだけを切り離して見るのではなく、複製をどう持つか、故障時にどう引き継ぐか、といったデータの守り方とあわせて設計することが欠かせません。置き場所の決め方は土台の一部にすぎず、それ単体で止まりにくさが決まるわけではないのです。全体像のなかに位置づけて考える姿勢が、後々の作り直しを抑えます。
まとめ
- コンシステントハッシュ法は、サーバ増減時に置き直すデータを小さく抑える割り当ての仕組みである。
- サーバとデータを円環（ハッシュリング）上に並べ、時計回りにたどって最初のサーバへ預ける。
- 素朴な剰余方式と違い、影響がとなり合う区間だけにとどまるため、増減にくり返し耐えられる。
- 仮想ノードを併用すると偏りがならされ、性能差に応じた重みづけの配分もしやすくなる。
- 分散DB・キャッシュ・CDNなどで広く使われ、製品を選んで正しく設定して活かすのが基本となる。
よくある質問
単純な剰余（mod）による分散と、何が違いますか。
いちばんの違いは、サーバを増減させたときに動くデータの量です。台数で割った余りで置き場所を決める剰余方式では、台数が変わると割る数そのものが変わるため、ほとんどのデータで置き場所がずれてしまいます。一方コンシステントハッシュ法では、円環上でとなり合う一部の区間だけが影響を受け、残りは元のままにとどまるのです。サーバの増減が日常的に起きる環境ほど、この差が大きく響いてきます。
仮想ノードは、何のために使いますか。
おもに、データの偏りをならすために使います。サーバを円環上の一点だけで表すと、点の並びかたによって担当区間の広さに差が生まれ、特定のサーバにデータが集中しがちです。一台を複数の点として登録する仮想ノードを使えば、担当区間が細かく分かれて円環全体に散らばり、偏りがやわらぎます。あわせて、性能の高いサーバには点を多めに割り当てるなど、重みをつけた配分もしやすくなるのが利点でしょう。
どんなシステムで使われていますか。
分散型のデータベースやキャッシュ、CDN、ロードバランサなど、規模を伸ばしながら動かし続ける基盤で広く使われています。たとえば、キーごとに置き場所を決める分散データベースや、コンテンツをどのエッジサーバに載せるかを決めるCDNなどが代表例です。いずれもサーバの数が状況に応じて変わりやすく、増減のたびに全体を組み替えずに済むことが、そのまま止まりにくさへつながっています。
導入すれば、データの偏りはなくなりますか。
偏りをゼロにできるわけではありません。仮想ノードを使うことで散らばりはかなりならされますが、あくまで確率的にならすものなので、いくらかのむらは残ります。仮想ノードの数を増やすほど偏りは小さくなっていく傾向がありますが、そのぶん管理する点の数は増えていくのです。どの程度のむらまで許すのかを見すえて、点の数を選ぶのが現実的な進め方になります。
著者：テレリモ総研編集部 鈴木 亮佑
LASSICでは、国内ニアショア開発体制を活かし、分散システムのアーキテクチャ方針づくりやデータベースの選定から実装、公開済みシステムの見直しまでを一貫して支援する体制です。要件定義の段階から実装、テスト、リリース後の運用・保守まで、工程を分けずに任せられる点も強みでしょう。データの分散設計やスケール構成でお困りの際も、ご相談いただけます。
ご不明な点はお問い合わせフォームからもご連絡いただけます。
出典
- ACM「Consistent hashing and random trees」（Karger 他, STOC 1997）
- Amazon「Dynamo: Amazon’s Highly Available Key-value Store」（SOSP 2007）
