原文: The Twitter Engineering Blog: Introducing Gizzard, a framework for creating distributed datastores
This article is translated by @ono_matope. Please contact me if any problem.
多くのモダンなWebサイトは、１台のコンピューターに納まりきらないほどの大量のデータに高速にアクセスする必要があります。そのため、複数のコンピューターに情報を分けて格納する「シャード」という手法が使われます。
シャーディング戦略はパーティショニングとレプリケーションという二つのテクニックに関係します。 パーティショニングでは、データは小さいチャンクに分割され、多数のコンピューターに横断してストアされます。これらのチャンクひとつひとつは小さいので、それをストアするコンピューターは効率的にデータの操作や照会ができます。もう一方のテクニックであるレプリケーションは、複数のデータ複製をいくつかのマシンにわたって格納するものです。各コピーはそのマシン上で利用され、クエリに応答できるので、システムはレプリケーションを追加することで同じデータへの多量のクエリに効率的に応答することができるようになります。レプリケーションはまた、いずれかの複製が壊れても他のコピーが同じタスクを行えるので、システムの回復力を高めます。
問題は、シャーディングは難しい、ということです。適切なパーティショニング手法を決定することは難しく、信頼性の低いネットワークやサーバで全てのデータ複製の間で一貫性を保つことはさらに困難です。 残念なことに、今流行のOSS分散データベースのほとんどは現時点ではWebにおける様々な問題を扱うにはまだ未熟であるか制限が多すぎであり、非常に有望ではあるものの独自のソリューションを構築するほうが実践的なこともあります。
Twitterが幾つか作った分散データストアのうち、共通的に必要とされた部分をメンテナンス性と再利用性のために抽出したものがGizzardです。耐障害性のあるカスタム分散データベースの作成を簡単にするためのScalaフレームワークです。
Gizzardは特定の種類の問題を解決するための基本的なテンプレートを提供するフレームワークです。万能ではないものの、様々なデータストレージの問題に便利です。高い水準では、Gizzardは任意のバックエンドストレージ(SQL Database、Luceneなど)のデータパーティショニングを管理するネットワークサービスミドルウェアです。パーティショニングのルールはキーレンジをパーティションにマップする転送テーブルに格納されます。各パーティションは宣言的なレプリケーションツリーを通じて自身のレプリケーションを管理します。Gizzardは"マイグレーション"をサポート（例えば、クラスターにマシンをElasticに追加）し、障害に優雅に対処します。全てのwriteオペレーションは冪等(Idempotent)かつ可換(Commutative)であることを要求され、オペレーションが失敗するとあとでリトライされるため、このシステムはEventually Consistentになっています。
分散キーバリューストアのRowzはGizzardを使ったとてもシンプルなサンプルです。Gizzardをすばやく立ち上げ動作させるために、Rowsを起動してカスタマイズしてみましょう！
でもその前に、Gizzardのはたらきを説明します。
Gizzardはネットワーキングサービスのミドルウェアとして動作します。クライアント(主にPHPやRoRでかかれたフロントエンド)と、大量のデータレプリケーション及びレプリカの真ん中に陣取ります。全てのデータクエリと操作はGizzardを経由されます。Gizzardインスタンスはステートレスなのでスループットを維持したりTCPコネクションを維持するのに必要なだけのGizzardを実行できます。GizzardはJVM上で動作していることもありたいへん効率的です。あなたの使い方によりますが、TwitterのGizzardアプリケーションの一つ(Flock DB、分散グラフデータベース)はコモデティマシンにつき秒間10,000クエリを受け付けます。
Gizzardはどのようなネットワークデータストレージサービス間でもデータを複製するように設計されています。Lucene, Redis, その他なんでも。原則的に、Gizzardは全てのWriteオペレーションが idempotent(冪等) かつ commulative(可換) であることを要求するので、これはバックエンドストアの使い方をいくらか制約するかもしれません。特に、GizzardはWriteオペレーションが順序どおりに適用されることを保証しません。そのため、システムはWriteの実行順序にかかわらず一貫した状態に到達するように設計される必要があります。
Gizzardはデータの 範囲 を特定のシャードにマッピングすることでパーティショニング（i.e., 排他的なデータの範囲をたくさんのホストにわたって分割する）を扱います。これらのマッピングは数的範囲の下限と、その範囲のデータがどのシャードに属するかを指定する転送テーブルに格納されます。
正確には、Gizzardはカスタム"ハッシング"関数を提供しており、それはデータのキー(アプリケーション特有)を受け取り、転送テーブル中のレンジのひとつに所属する数字を生成します。これらの関数はプログラマブルなのでローカリティかバランスか、あなたのニーズに合わせて最適化できます。
この表的な手法は他の分散データストアで広く使われる"Consistent Hasing"とは異なる。これはヘテロジニアスなサイズのパーティションを許すので、簡単に ホットスポット (非常に人気のあるデータセグメント)を管理できます。実際、Gizzardであなたはコンシステントハッシングのように完全にカスタムな転送ストラテジを実装することができますが、推奨できないアプローチです。
フォワーディングテーブル内の各シャードは、物理シャードか論理シャードのいずれかです。物理シャードは、SQL databaseのような特定のデータストレージバックエンドへの参照です。逆に、論理シャードは単に他のシャードのツリーで、ツリーの各 ブランチ はデータのいくつかの論理的な変形を表現し、 各 ノード はデータストレージバックエンドです。ブランチでのこれらの論理的変形は通常、read/writeオペレーションがどのようにそのブランチの子供に伝播するかのルールです。例えば、ここに2レベルレプリケーションツリーがあります。この表現は単に(後述のテーブルで参照するように) ONE パーティションであることに気をつけてください。
図中の"Replicate"ブランチはWriteオペレーション全ての子供達に繰り返し、健康状態や重み付け関数にそって子供間でreadをバランスするシンプルなストラテジです。 あなたは追加のトランザクション/コーディネーションプリミティブやQuorum戦略を追加するようなあなたの特定のデータストレージのニーズに合わせたカスタムなバランシング/論理シャードを作成することができます。 しかしGizzardはReplicating, Write-Only, Read-Only, Blocked(ReadもWriteも不許可)といった広く便利ないくつかのストラテジを同梱しています。 より曖昧なシャードタイプのいくつかの有用性については Migrations の章で論じます。
そのレプリケーショントポロジの性質はパーティションごとに変わります。つまり、あなたは "よりホットな" パーティションには高いレプリケーションレベルを、 "よりクールな" ものには低いレプリケーションレベルを割り当てられます。 これはシステムを高度にコンフィギュラブルにします。例えば、あなたはプライマリ-セカンダリ-ターシャリー-etcにお互いにミラーしあうように設定することもできます。 ほかには、よりよい耐障害性のために(複雑にはなりますが)、あなたはマシン間でパーティションを"ストライプ"してどのマシンも他のマシンをミラーしないようにもできます。
耐障害性は分散システムの最大の不安の種のひとつです。このようなシステムはたくさんのコンピューターが関与するので、いつもひとつまたは複数のそれが機能不全に陥っている可能性が高いです。 Gizzardはいかなる単一障害点ももたないよう設計されました。 もしパーティション中の特定のレプリカが壊れたら、Gizzardはリクエストを重み付け関数を考慮しつつ残った健康なレプリカにルーティングします。もしパーティション中の全てのレプリカが使用不能になったら、Gizzardはそのシャードへのreadリクエストを提供できなりますが、他のシャードは影響を受けません。 使用不能なシャードへのWriteは、シャードがまた利用可能になるまでバッファされます。
実際は、もしシャード内の任意の数のレプリカが使用不能だったら、Gizardはできるだけ早く全ての健康なレプリカに書き込んで使用不能なシャードへの更新をバッファして、不健康なシャードが復帰したらあとでまた書こうとします。基本的な戦略は、全ての書き込みは耐久性のある、トランザクショナルなジャーナルに具現化されるということです。書き込みはそのとき非同期に(とはいえ扱いやすい低レイテンシ)でシャード内の全てのレプリカに書かれます。もしシャードが使用不能だったら、Writeオペレーションはエラーキューに入り、あとでリトライされます。
"結果整合性"を得るために、この"あとでリトライ"戦略はあなたのWriteオペレーションが冪等(idempotent) かつ commutative(可換)であることを要求します。これは、"あとでリトライ"はオペレーションをばらばらに適用される可能性があるからです(例えば、新しいジョブが古い失敗したジョブのリトライの前に適用される)。ほとんどの場合、これは簡単な要求です。可換かつ冪等な書き込みの例はGizzard デモアプリのRwozに含まれています。
シャードのデータをあるコンピューターから他のコンピューターに複製や移動できたら便利なこともあります。マシンが多かれ少なかれこれは負荷をバランスするために行われるかもしれませんし、ハードウェア障害対応のためかもしれません。 あまり知られない論理シャードのタイプの幾つかを説明するために、マイグレーションがどのように行われるか説明するのは興味深いことです。 Datastore AからDatastore A'にマイグレーションするとき、レプリケート中のシャードはそれらの間に設置されていますが、WriteOnlyシャードがDatastore A'の前に設定されています。このときデータは古いシャードから新しいシャードにコピーされます。WriteOnlyシャードは新しいシャードがbootstrapしている間、そこから誰もreadしないことを保証します(なぜならそれは不完全な状態だからです)。
Writeはばらばらに実行されるので(新しいwriteは古いものより前に実行されたり、いくつかのwriteは二回実行されるかもしれない)、全てのWriteはデータ一貫性を保証するために冪等である必要があります。
The source-code to Gizzard is available on GitHub. A sample application that uses Gizzard, called Rowz, is also available. The best way to get started with Gizzard is to clone Rowz and customize.
com.twittergizzard
1.0
The Github issue tracker is here.
Robey Pointer Nick Kallen Ed Ceaser John Kalucki If you'd like to learn more about the technologies that power Twitter, join us at Chirp, the Twitter Developer Conference, where you will party, hack, chat with and learn from Twitter Engineers and other developers!
—@nk, @robey, @asdf, @jkalucki