シャーディング
Sharding ・ しゃーでぃんぐ
データをシャードキーで分けて複数ノードに置き、1台の容量と書き込み性能の限界を超える手法。
✦ 30秒で試す — 航海台数で割るだけの振り分けが、増設の日に大惨事を招く6台にすると、人気の1人を持つサーバの負荷は？予想してみる概要
シャーディング（sharding）は、1つの大きなデータの集まりを「分割キー」に従っていくつかの塊（シャード）に切り分け、それぞれを別々のノード（サーバ）に分けて格納する手法です。「割れた破片（shard）」という語のとおり、たとえばユーザー情報を「ユーザーIDの範囲」や「IDのハッシュ値」で分け、AさんのデータはノードA、BさんのデータはノードBへ、というように振り分けます。こうすると、1台では収まりきらない量のデータを複数台に分散して持て、読み書きの負荷も台数に応じて分散します。
これはスケーリングの中でも、サーバの性能を上げる「垂直スケール（スケールアップ）」ではなく、台数を増やして負荷を分ける「水平スケール（スケールアウト）」をデータ層で実現する代表的な方法です。行を分割キーごとに別のノードへ振り分けるので、「水平分割（horizontal partitioning）」とも呼ばれます。サービスが成長し、1台の RDBMS ではディスクもメモリも CPU も足りなくなったとき、最後に検討される選択肢の一つです。
似た言葉に「パーティショニング」があります。PostgreSQL の宣言的パーティショニングのように、1台のデータベースの中で大きな表を月ごとなどの子表に分ける機能もパーティショニングと呼ばれます。こちらは古いデータを丸ごと消しやすくしたり、検索で不要な子表を読み飛ばしたりするための工夫で、台数は増えません。シャーディングは、分けた塊を別々のマシンに置くところが違います（分散データベースの文献では、シャードのことをパーティションと呼ぶこともあります）。
なぜ生まれたか
サービスが小さいうちは、データベースは1台で足ります。足りなくなってきたら、まずはより高性能なマシンに載せ替える「スケールアップ」で凌げます。しかしこの手には天井があります。世界最速のサーバでも積めるメモリやディスクには上限があり、値段も性能の限界に近づくほど急激に跳ね上がります。データが数十テラバイト、書き込みが毎秒数万件という規模になると、どんな1台をもってしても物理的に処理しきれなくなります。
そこで「1台を強くする」のではなく「多数の平凡なマシンに分けて載せる」という方向に発想を変えたのがシャーディングです。データを分割キーで割り振れば、各ノードは全体の一部だけを担当すればよく、台数を増やすほど容量も処理能力も伸びます。もともとは大規模Webサービスが巨大RDBMSの限界を回避するために手作業で編み出した工夫でしたが、後のNoSQL系データストアはこの分散を最初から仕組みとして内蔵し、シャーディングを「設計時の前提」に格上げしました。
詳細
シャードキーで振り分ける
シャーディングの成否は「何をキーに分けるか（シャードキー）」にほぼ集約されます。代表的な戦略は3つです。範囲分割（レンジ）は「ID 1〜1000万はノード1、1000万〜2000万はノード2」のようにキーの範囲で分けます。範囲検索が得意な反面、連番の ID や時刻をキーにすると、新しい書き込みがすべて最後のシャードに集中します。ハッシュ分割は、キーをハッシュ化した値（暗号用である必要はなく、散らばり方が均一な関数なら十分です）でノードを決めます。分布は均等になりますが、隣り合うキーがばらばらのノードに散るので、範囲検索は全ノードへの問い合わせになります。ディレクトリ方式は「どのキーがどのノードにあるか」を別の対応表で管理し、柔軟に配置できる代わりに、対応表そのものが要（かなめ）になります。
クライアントの読み書きは、まず「そのキーがどのシャードにあるか」を判定するルータ（プロキシやドライバ）を通り、担当ノードへ振り分けられます。キーを指定した1件の読み書きは1ノードで完結するので速いのですが、シャードキーを含まない検索や集計は全ノードへ問い合わせて結果を束ねる（スキャッター・ギャザー）必要があり、ノードが増えるほど遅く、1台の遅れに全体が引きずられるようになります。
なぜ hash mod N ではだめなのか
ハッシュ分割のいちばん素朴な実装は、「ハッシュ値を台数 N で割った余り」でノードを決める hash(key) mod N です。均等に散らばり、計算も一瞬です。ところが、台数を変えた瞬間に破綻します。3台から4台に増やすと、割る数が 3 から 4 に変わるので、ほとんどのキーの余りが変わります。余りが変わらずに済むのは、平均して4個に1個だけです。つまり1台足しただけで、全データの約4分の3が別のノードへ引っ越すことになります。引っ越しの間、データの移動が回線とディスクを埋め、キャッシュなら一斉にヒットしなくなります。
コンシステントハッシュ法（1997年に Karger らが Web キャッシュの分散のために提案した方法）は、この引っ越しを最小にします。ハッシュ値の範囲を円（リング）に見立て、キーだけでなくノードもハッシュしてリング上に置きます。各キーは、リングを時計回りに進んで最初に出会うノードが担当します。ノードを1台足すと、そのノードがリングに割り込んだ位置の手前の区間のキーだけが新しいノードへ移り、ほかのキーは1つも動きません。N 台から N+1 台にしたときに動くのは、平均して全体の 1/(N+1) です。
ノードをリングに1点ずつ置くだけでは、置かれた位置の偶然で区間の長さがばらつき、負荷が偏ります。そこで実際の実装（Amazon Dynamo や Cassandra など）では、1台のノードをリング上の多数の点に分けて置く「仮想ノード」を使い、区間を細かく混ぜて均します。別の解き方として、最初からノード数よりずっと多い固定数のパーティション（たとえば1000個）に分けておき、台数が増えたらパーティションを丸ごと新しいノードへ渡す方式（Elasticsearch のシャード数、Couchbase の vBucket など）や、大きくなった範囲を二つに割って移す方式（Bigtable や HBase のリージョン分割、MongoDB のチャンク）もあります。
下の部品で確かめてください。リングに載ったキーの色が、それを持つノードです。「＋ノード」をリングへドラッグして1台足すと、右の箱の間をキーが引っ越します。hash mod N とコンシステントハッシュで、動くキーの数を比べてください。アクセスを1つのキーに集中させると、ノードを足しても解けない偏り（ホットスポット）も見えます。
リングの上の40個の点がキー、色はそれを持つノード（右の箱）です。まず「＋ノード」をリングへドラッグして、4台目を足してください。
レプリケーションとの違い
混同しやすいのがレプリケーションとの違いです。どちらも「複数のノードにデータを置く」ものですが、目的も置き方も正反対です。レプリケーションは同じデータの複製を各ノードに丸ごと持たせ、可用性と読み取り性能を高めます。1台が落ちても他が同じデータを持っているので生き残れますが、全体の容量は1台ぶんのままです。シャーディングは各ノードに異なる一部だけを持たせ、容量と書き込み性能を伸ばします。その代わり、あるシャードが落ちると、その範囲のデータだけがまるごと読めなくなります。
このため実務では両者を組み合わせます。データをシャードに分けたうえで、各シャードをさらにレプリケーションで複製する。こうして容量・性能・可用性を同時に確保するのが、大規模データストアの標準的な構成です。
落とし穴と設計のトレードオフ
シャーディングは強力ですが、導入した瞬間に多くの前提が崩れます。まず、複数のシャードにまたがるトランザクションが極端に難しくなります。1台の RDBMS なら当たり前だった「複数の行をまとめて原子的に更新する」が、ノードをまたぐと二相コミットのような分散トランザクション（分散システムの中でも難しい部類の問題）になり、性能も設計の手間も跳ね上がります。JOIN や一意制約も、関係する行が別のシャードに散っていると効かせにくくなります。だからこそ、「一緒に読み書きするものは同じシャードに入る」ようにシャードキーを選ぶ（たとえば、テナントごと・ユーザーごとに分ける）ことが設計の中心になります。
さらに厄介なのが、シャードキー選びの後戻りの難しさです。偏ったキーを選ぶと、特定のシャードだけに負荷が集中するホットスポットが生まれます。フォロワーが数千万人いる有名人の投稿のように、1つのキーにアクセスが集中する場合は、ハッシュでどう散らしてもそのキーを持つ1台に負荷が乗ります。キーの末尾に乱数を付けて複数のシャードに分け、読むときに束ねる、といったアプリケーション側の工夫が必要です。運用開始後にキーを変えたり、シャードを増減させてデータを再配置（リシャーディング）したりするのは、大量のデータ移動を伴う一大作業です。鉄則は「必要になるまでシャーディングしない」こと。まずインデックスとクエリの見直し、スケールアップ、読み取りレプリカで粘り、それでも書き込みや容量が1台の限界を超えるときに初めて手を出すのが、複雑さに見合った判断です。
試問
リングの上に40個のキー（データの見出し）が並び、色はそれを持つノード（サーバ）です。いまは3台で、キーの持ち主を hash mod N（キーのハッシュ値を台数で割った余り）で決めています。「＋ノード」をリングへドラッグすると1台増え、別のノードへ引っ越したキーが金の縁で光ります。置き方はコンシステントハッシュにも切り替えられます。
リングの上の40個の点がキー、色はそれを持つノード（右の箱）です。いまは hash mod N でキーを置いています。「＋ノード」をリングへドラッグすると1台増えます。