CockroachDB アーキテクチャ設計

これは、https://github.com/cockroachdb/cockroach/blob/master/docs/design.md の、２０１７年３月時点の、kanda.motohiro@gmail.com による抄訳です。Apache License, Version 2.0 の下で公開します。

CockroachDB READMEの訳と違って、こっちは長いので、md ファイルを訳して html に変換するのでなくて、じかにこのページに書いていきます。なので、体裁は原文と異なります。

この文書について

この文書は、Spencer Kimball による２０１４年はじめのオリジナルな設計文書の更新版です。

概要

CockroachDB は、分散 SQL データベースです。その主な設計ゴールは、スケーラビリティ、強一貫性、そしてサバイバル可能性です(なので、この名前です)。CockroachDBは、ディスク、マシン、ラック、そしてデータセンタの障害にさえ耐えられることを目指しています。遅延への影響は最小限に、そして人手による介入はありません。CockroachDBノードは対称的です。設計ゴールは、均質な配備(単一バイナリ)で最小限の設定、外部への依存が必要ないことです。

データベースクライアントへのエントリポイントは SQL インタフェースです。CockroachDB クラスタの全てのノードはクライアントSQLゲートウェイとしてはたらくことができます。SQLゲートウェイは、クライアントSQL文をキーバリュー(KV)操作に変換して実行します。それをゲートウェイは必要に応じてクラスタ全体に分配して、クライアントに結果を返します。CockroachDB は、キーから値への単一のモノリシックなソート済みマップを提供します。キーと値の両方はバイト文字列です。

KVマップは、論理的には、レンジと呼ばれるキー空間の小さいセグメントから構成されます。それぞれのレンジはローカルKVストレージエンジン(私たちは RocksDB 、LevelDB の変種、を使います）に格納されたデータに対応します。レンジのデータは設定可能な数の追加の CockroachDB ノードに複製されます。レンジは目的サイズ、デフォルトで６４M、を維持するようにマージとスプリットされます。比較的小さなサイズは、ノード障害に対処するための素早い修復と再バランス、容量の追加、そして読み書きの負荷への対処を容易とします。しかし、この長さは、システムがより多くのレンジを管理しないといけない負荷とバランスして決めなくてはいけません。

CockroachDB は水平スケーラビリティを達成します：

- ノードを追加すれば、クラスタの容量は、それぞれのノードにあるストレージの量だけ、増加します（設定可能な複製ファクタで割ります）。理論的には、4 exabytes (4E) の論理的データが可能です。

- クライアントの問い合わせはクラスタのどのノードに送ってもかまいません。そして問い合わせは独立に（競合なしに）動作することができます。これは、全体のスループットはクラスタのノードの数に線形に比例するということです。

- 問い合わせは分散されます（分散SQL）なので、単一の問い合わせの全体のスループットはノードを追加することで増加することができます。

CockroachDB は強一貫性を達成します：

- キーバリューのそれぞれのレンジのデータを同期複製するために、分散コンセンサスプロトコルを使います。私達は Raft コンセンサスアルゴリズムを使うことを選びました。全てのコンセンサス状態は、RocksDB に格納されます。

- 一つのレンジへの一つのあるいはバッチされた変更は、そのレンジの Raft インスタンスによって調停されます。Raft は ACID セマンティクスを保証します。

- 複数のレンジに影響する論理的変更は、ACID セマンティクスのために、分散トランザクションを使います。CockroachDB は、効率の良い、ノンロッキング分散コミットプロトコルを使います。

CockroachDB は、サバイバル可能性を達成します：

- レンジの複数の複製は、一つのデータセンタ内に同居できます。それは低遅延な複製をもたらし、ディスクあるいはマシンの障害に耐えます。ラックをまたがって分散させれば、ある種のネットワークスイッチ障害に耐えます。

- レンジの複製を、地理的により離れたデータセンタに置くことができます。それは、データセンタの電源障害あるいはネットワーク損失から、その地域の電源障害までの、より大きな障害シナリオに耐えます。

  (例えば、`{ US-East-1a, US-East-1b, US-East-1c }`, `{ US-East, US-West, Japan }`, `{ Ireland, US-East, US-West}`, `{ Ireland, US-East,  US-West, Japan, Australia }`).。

CockroachDB は、snapshot isolation (SI) と serializable snapshot isolation (SSI) セマンティクスを提供します。それは、externally consistent なロックフリーのリードとライトを提供します。どちらも、歴史的スナップショットタイムスタンプから、そして現在の壁時計の時刻からです。SI はロックフリーのリードとライトを提供しますが、ライトスキューが起きることがあります。SSI はライトスキューを除きますが、競合の多いシステムで性能問題を起こします。SSI が、デフォルトのアイソレーションです。クライアントは注意して、正しさと性能をトレードオフしなければいけません。CockroachDB は限定された形の linearalizability を実装します。それは、任意の観測者あるいは観測者の連鎖にオーダリングを提供します。

Spanner ディレクトリと同様に、CockroachDB はデータの任意のゾーンの構成が可能です。これは、複製ファクター、ストレージデバイスタイプ、そして／あるいは、データセンタの場所を選んで、性能と／あるいは、可用性を最適化することを可能とします。Spanner とは違って、ゾーンはモノリシックであり、エンティティグループのレベルにおいて、細粒度のデータの移動を許しません。

アーキテクチャ

CockroachDB は層をなしたアーキテクチャを実装します。最も上の抽象化のレベルは SQL 層（この文書では今、述べられていません）です。訳注。アプリケーション層、と言いたいのかも。

それは直接、SQL 層に依存します。後者はスキーマ、テーブル、カラム、そしてインデックスなどのなじみのあるリレーショナルの概念を提供します。次に SQL 層は、分散キーバリューストアに依存します。それは、レンジのアドレッシングの詳細を処理して、単一のモノリシックなキーバリューストアという抽象化を提供します。分散 KV ストアは任意の数の物理 Cockroach ノードと通信します。それぞれのノードは一つ以上のストアを持ち、ストアは物理デバイスに一つあります。

それぞれのストアは、潜在的に多くのレンジを持ちます。レンジは、キーバリューデータの最低レベルの単位です。レンジは、Raft コンセンサスプロトコルを使って複製されます。以下の図は、前の図の５つのノードから４つのノードのストアを拡大したバージョンです。それぞれのレンジは raft を使って３多重に複製されます。色は、対応するレンジの複製を示します。

それぞれの物理ノードは、二つの RPC ベースのキーバリュー API を公開します。一つは外部クライアントのため、そしてもうひとつは内部のクライアントのため（センシティブな運用的機能を公開します）。どちらのサービスも、まとめた要求を受け付け、まとめた応答を返します。ノードは能力と公開するインタフェースにおいて対称です。それぞれは同じバイナリを持ち、どの役割りでもできます。

ノードと、それがアクセスを提供するレンジは、信頼性と性能の間のトレードオフをするために、いろいろな物理ネットワークトポロジーを使って配置できます。例えば、三多重のレンジはそのそれぞれの複製を、異なる：

- 一つのサーバ内のディスクに置いて、ディスク障害に耐えることができます。

- 一つのラック内のサーバに置いて、サーバ障害に耐えることができます。

- 一つのデータセンタ内の異なるラックに置いて、ラックの電源あるいはネットワーク障害に耐えることができます。

- 異なるデータセンタのサーバに置いて、大規模なネットワークあるいは電源喪失に耐えることができます。

複製の総数が `N = 2F + 1` なら、`F` までの障害に耐えられます（例えば、3x 複製なら、一つの障害に耐えられます。5x 複製なら、２つの障害です。など）。

キー

Cockroach キーは、任意のバイト配列です。キーは二つのフレーバーがあります。システムキーとテーブルデータキーです。システムキーは、Cockroach によって、内部データ構造とメタデータのために使われます。テーブルデータキーは SQL テーブルデータ(インデックスデータも)を持ちます。システムとテーブルデータキーは、全てのシステムキーが、どのテーブルデータキーよりも前にソートされるようにプレフィックスされます。

システムキーは、いくつかのサブタイプがあります。

・グローバルキーは、"meta1" と "meta2" キーのような、クラスタワイドなデータを格納します。また、ノードとストアの ID アロケータのような、いろいろな他のシステムワイドなキーも格納します。

・ストアローカルキーは、複製されないストアメタデータ（例えば、`StoreIdent` 構造体）のために使われます。「複製されない」とは、これらの値は複数のストアにわたって複製されないことを示します。それらが持つデータが、それが存在するストアの生存期間に結びついているためです。

・レンジローカルキーは、あるグローバルキーに関連したレンジメタデータを格納します。レンジローカルキーは特別なプレフィックスを持ち、その後にグローバルキーと特別のサフィックスを持ちます。例えば、トランザクションレコードは、このようなレンジローカルキーです。

`\x01k<global-key>txn-<txnID>`

・複製されたレンジ ID ローカルキーは、あるレンジの全ての複製に存在するレンジメタデータを格納します。これらのキーは Raft 操作を経由して更新されます。例としては、レンジリース状態と、アボートキャッシュエントリがあります。

・複製されないレンジ ID ローカルキーは、ある複製にローカルなレンジメタデータを格納します。そのようなキーの主な例は、Raft 状態と Raft ログです。

テーブルデータキーは全ての SQL データを格納するために使われます。テーブルデータキーは、SQL モデルと KV の間のデータのマッピングの節で述べられている内部的なデータ構造を含みます。

バージョン付きの値

Cockroach は、値を、対応するコミットタイムスタンプと一緒に格納することで、歴史的バージョンを維持します。リードと走査は、スナップショット時刻を指定して、そのスナップショットタイムスタンプより前の最新のライトを返すようにできます。値のより古いバージョンは、利用者の指定する満了期間に従って、コンパクションの間にシステムによってガーベッジコレクトされます。長く走る走査(たとえば、MapReduce のため)をサポートするために、全てのバージョンは最小の満了期間を持ちます。

バージョン付きの値は、キーごとにコミットタイムスタンプと GC 満了期間を記録するという RocksDB への変更によってサポートされます。

ロックフリー分散トランザクション

Cockroach は、ロック無しの分散トランザクションを提供します。Cockroach トランザクションは、二つのアイソレーションレベルをサポートします。

- snapshot isolation (SI) と

- serializable snapshot isolation (SSI) です。

SI は実装が単純で、とても高性能で、いくつかの異常な条件（例えばライトスキュー）を除いてほとんど、正しいです。SSI は少し複雑さを必要とし、それでも十分に高性能で、（競合があると、あまりそうではありませんが）そして、異常な条件は何も持ちません。Cockroach のSSI 実装は論文からのアイディアに基づき、いくらかの新規な洞察を加えます。

SSI がデフォルトのレベルです。SI は、性能に対する必要性と、ライトスキュー条件が無いことを十分に確信できるアプリケーション開発者が、意識的にそれを使うために提供されます。競合が軽いシステムでは、私達の SSI 実装は、SI と同じくらいに高性能です。それは、ロックも、追加のライトも必要としません。競合があると、私達の SSI実装は、ロックを同様に必要としませんが、より多くのトランザクションをアボートすることになります。Cockroach の SI と SSI 実装は任意の長さのトランザクションに対しても、飢餓シナリオを防ぎます。

SSI の一つの可能な実装については、Cahill 論文https://drive.google.com/file/d/0B9GCVTp_FHJIcEVyZVdDWEpYYXVVbFVDWElrYUV0NHFhU2Fv/edit?usp=sharing を参照下さい。これはもうひとつの優れた論文 http://cs.yale.edu/homes/thomson/publications/calvin-sigmod12.pdfです。リードライトの競合を防ぐことによる（それを検出するのではなく、ライトスナップショットアイソレーションと呼ばれます） SSI 実装についての議論は、Yabandeh 論文 https://drive.google.com/file/d/0B9GCVTp_FHJIMjJ2U2t6aGpHLTFUVHFnMTRUbnBwc2pLa1RN/edit?usp=sharing を参照下さい。それは、Cockroach の SSI の多くのインスピレーションの源です。

SI も SSI も、リードの結果は、保存されることを要求します。つまり、以前のリードよりも小さいタイムスタンプにおけるキーへのライトは成功してはいけません。そのために、それぞれのレンジは、それが読まれた最新のタイムスタンプまでのキー範囲を有限のメモリ上キャッシュに維持します。

このタイムスタンプキャッシュへの更新のほとんどは、読まれるキーに対応します。しかし、タイムスタンプキャッシュは、結果的にそのキャッシュにエントリを挿入することになるある種のライト（特に、レンジ削除）の結果も保護します。キャッシュのエントリは、最も古いタイムスタンプから最初に破棄され、キャッシュの低ウォーターマークを適切に更新します。

Cockroach トランザクションのそれぞれは開始時に、ランダムな優先度と「タイムスタンプの候補」を与えられます。タイムスタンプの候補は、そのトランザクションがコミットすると思われるタイムスタンプであり、そのトランザクションを調停しているノードの現在クロック時刻が選択されます。これは、競合のないトランザクションは普通は、絶対時刻で、そのトランザクションが行う実際の仕事より前のタイムスタンプでコミットすることを意味します。

一つ以上の分散ノードの間でトランザクションを調停する間に、タイムスタンプの候補は加算されることがあります。しかし、減算されることは決してありません。SI と SSI の二つのアイソレーションレベルの核となる違いは、前者はトランザクションのタイムスタンプの候補が加算するのを許し、後者は許さないことです。

トランザクション実行フロー

トランザクションは、二相にわたって実行されます。

１. そのトランザクションが大きく関連するだろうレンジを選んで、トランザクションを始めます。そのレンジの予約された領域に”PENDING” 状態の新しいトランザクションレコードを書きます。それと並行して、そのトランザクションの一部として書かれるそれぞれのデータに、「インテント」値を書きます。これらは通常の MVCC 値ですが、特別なフラグ(つまり「インテント」)を持っていて、トランザクション自身がコミットした後にその値がコミットすることを示します。さらに、インテント値と一緒に、トランザクション ID (一意で、トランザクション開始時にクライアントによって選ばれます)も格納されます。この txn id は、競合がある時に、そのトランザクションレコードを参照するために使われ、また、同じタイムスタンプの間で、オーダリングについてのタイブレーキング判定をするために使われます。それぞれのノードはそのライトで使われたタイムスタンプ(それは、読み書きの競合がなければ、元の候補のタイムスタンプです)を返します。クライアントは、全てのライトタイムスタンプの中で最大のものを、最終的なコミットタイムスタンプとして選びます。

２. トランザクションを、そのトランザクションレコードを更新することでコミットします。コミットエントリの値は、候補のタイムスタンプ(最新のリードタイムスタンプがあればそれに応じて必要ならば加算されます)を持ちます。トランザクションはこの時点で完全にコミットしたと考えることができ、制御をクライアントに返すことができることに注意下さい。

SI トランザクションの場合、並行するリーダーのために加算されたコミットタイムスタンプは完全に許容され、コミットは続行できます。SSI トランザクションの場合、コミットタイムスタンプの候補との差はトランザクション再開始を必要とします(注意。再開始は、アボートと違います。以下を参照)。

トランザクションがコミットした後、全てのライトインテントは、並列に、「インテント」フラグを除くことでアップグレードされます。このステップの前に、トランザクションは完全にコミットしたと考えることができ、これを待つことなくトランザクションコーディネータに制御を返します。

競合がなければ、これで終わりです。システムの正しさを保証するために必要なものはもう何もありません。

競合解決

ものごとは、リーダーあるいはライターが、それが読み書きする必要のあるところに、インテントレコードあるいは新しくコミットされた値を見つけると、より面白いことになります。これは競合です。普通は、トランザクションのどちらかがアボートあるいは再開始することになります。どちらになるかは競合の型によります。

トランザクション再開始

これが普通(そしてより効率的)なふるまいの型です。それは、そのトランザクションがアボート(例えば他のトランザクションによって)された時以外に使われます。ようするに、それは二つの場合に起きます。最初の場合は、前述されたとおりです。SSI トランザクションが、コミットしようとした時に、自分のコミットタイムスタンプが進められているのを見つけた時です。二つめの場合は、アクティブに競合に会うトランザクションに関連します。つまり、そのリーダーあるいはライターの一つが、競合解決を必要とする(以下の、トランザクション相互作用を参照下さい)データを見つけた時です。

トランザクションが再開始すると、それは自分の優先度を変更し、そして／あるいは、競合に結びついているデータに従って自分のタイムスタンプを前に進めます。そして、同じ txn id を使って新しく始めます。そのトランザクションの以前の実行はライトインテントをいくつか書いてきたかもしれません。それらは、トランザクションの一部に含まれないように、トランザクションがコミットする前に削除する必要があります。この無効なライトインテントを削除するのはトランザクションの再実行の時に、そのトランザクションの再実行の一部として、同じキーに新しいライトインテントを書くことにより暗黙的に行われるか 、そのトランザクションの再実行の一部ではない無効なインテントを明示的にクリーンアップするかのどちらかで行われます。ほとんどのトランザクションは同じキーに書くことになりますから、そのトランザクションをコミットする前に走る明示的なクリーンアップは、普通は NOOP です。

トランザクションアボート

これは、トランザクションが、自分のトランザクションレコードを読んだ時に、自分がアボートされたと見つける場合です。この場合、そのトランザクションはインテントを再使用できません。それをクリーンアップする前に、クライアントに制御を戻します(他のリーダーとライターは、未解決インテントに当たった時に、クリーンアップします)。しかし、アボートされたトランザクションは、その後、クリーンアップを試みます。次の試みは、(あるならば)新しい txn id を持つ新しいトランザクションとして走ります。

トランザクション相互作用

トランザクションが相互作用するシナリオがいくつかあります。

・リーダーが、はるか未来のより新しいタイムスタンプを持つライトインテントあるいは値に会う

これは競合ではありません。リーダーは自由に進めます。リーダーは結局、その値のより古いバージョンを読むことになるでしょう。なので競合しません。ライトインテントは、その候補よりも後のタイムスタンプでコミットされることがあるのを思い出してください。それは決して前のではコミットしません。

脚注。もし SI トランザクションリーダーがそのリーダー自身のトランザクションが書いた、より新しいタイムスタンプを持つライトインテントを見つけたら、リーダーは常にそのインテントの値を返します。

・リーダーが、近い未来のより新しいタイムスタンプを持つライトインテントあるいは値に会う

この場合、注意が必要です。このより新しい値は、厳密に言うと、ライターのクロックがその値を提供しているノードよりも進んでいる時に、私たちのリーダーの過去において、起きたのかもしれません。そうならば、私たちはこの値を考慮しなければいけないでしょう。しかしそれは全くわかりません。なので、トランザクションは再開始します。なお、未来のタイムスタンプを使います(ただし、不確定のウィンドウを最大のクロックスキューに制限するために、使ったタイムスタンプの最大値を覚えておきます)。実際、これはさらに最適化できます。詳細は、以下の、「タイムスタンプを選ぶ」のところを見てください。

・リーダーが、より古いタイムスタンプを持つライトインテントに会う

リーダーは、そのインテントのトランザクション id をトランザクションレコードで追う必要があります。もしそのトランザクションがすでにコミットしていれば、リーダーは単純にその値を読むことができます。ライトトランザクションがまだコミットしていないときは、リーダーは二つの選択肢があります。もしそのライト競合が SI トランザクションのものなら、リーダーはそのトランザクションのコミットタイムスタンプを未来に進めることができます(その結果、それを読む必要はありません)。これは簡単にできます。リーダーはそのトランザクションのタイムスタンプを更新して、いつ/本当に、そのトランザクションがコミットするのかを指定します。タイムスタンプは少なくても同じくらい大きいものを使うべきです。しかし、そのライト競合が SSI トランザクションによるなら、リーダーは優先度を比べなくてはいけません。もしリーダーがより高い優先度を持つなら、それはそのトランザクションのコミットタイムスタンプを進めます（そのトランザクションは後に、自分のタイムスタンプが進められたことに気が付き、再開始するでしょう）。もしそれが、低いか同じ優先度なら、新しい優先度 `max(新しいランダムな優先度, 競合するトランザクションの優先度 - 1)` を使って自分で再開始します。

・ライターが、コミットされないライトインテントに会う

もし、より低い優先度を持つトランザクションによって他のライトインテントが書かれていたら、そのライトは競合するトランザクションをアボートします。もしそのライトインテントがより高いか等しい優先度を持っていたら、トランザクションは新しい優先度 `max(新しいランダムな優先度, 競合するトランザクションの優先度 - 1)` を使って再開始します。再開始は、短いランダム化されたバックオフインターバルの後行われます。

・ライターがより新しいコミット済みの値と会う

そのコミット済みの値は、既にコミットしたトランザクションが作ったライトインテントであり、解決してないだけかもしれません。トランザクションは再開始します。再開始の時、同じ優先度が再使用されます。しかし、タイムスタンプの候補は、見つかった値のタイムスタンプにまで進められます。

・ライターが、より新しいリードキーに会う

ノードにおいて、それぞれのライトで、リードタイムスタンプキャッシュが調べられます。もしそのライトのタイムスタンプの候補が、キャッシュ自身の低ウォーターマーク(つまり、その最後に破棄されたタイムスタンプ)よりも古い場合、あるいは、書かれるキーが、そのライトのタイムスタンプの候補よりも新しいリードタイムスタンプを持っている場合、この新しいタイムスタンプ値が、ライトにおいて戻されます。新しいタイムスタンプは、serializable のときに限り、トランザクションの再開始を強制します。

トランザクション管理

トランザクションは、クライアントプロキシ（あるいは、SQL Azure 用語では、ゲートウェイ）によって管理されます。Spanner とは違って、ライトはバッファされずに、直接関連するレンジに送られます。これによって、ライト競合があった時にトランザクションを早くアボートできます。クライアントプロキシは、トランザクション完了時に非同期にライトインテントを解決するために、全ての書かれたキーを追跡します。もしトランザクションがコミットに成功したら、全てのインテントはコミット済みにアップグレードされます。トランザクションがアボートした場合は、全ての書かれたインテントは削除されます。クライアントプロキシは、それがインテントを解決することを保証しません。

もし、ペンディングトランザクションがコミットする前にクライアントプロキシが再開始した場合、未解決トランザクションは他のトランザクションによってアボートされるまで「生き」続けます。トランザクションは、定期的に自分のトランザクションレコードをハートビートして、ライブネスを維持します。

リーダーやライターが出会った、未解決インテントを持つトランザクションで、必要な期間内にハートビートされていないものは、アボートされます。トランザクションがコミットしたが、非同期の解決が終わる前に、プロキシが再開始した場合、未解決インテントは将来のリーダーやライターがそれに出会った時にアップグレードされます。そして、システムの正しさはそれらのタイムリーな解決に依存しません。

競合とアボート回数、そして破棄されたトランザクションについての再開始の研究は、ここ https://docs.google.com/document/d/1kBCu4sdGAnvLqpT-_2vaTbomNmX3_saayWEGYu1j7mQ/edit?usp=sharing にあります。

トランザクションレコード

最新の構造体は、pkg/roachpb/data.proto を見て下さい。最良のエントリポイントは、`message Transaction` です。

利点

- 失敗する二相コミットプロトコルを防ぐために、安定したコード実行をする必要がありません。

- SI セマンティクスの場合、リーダーは決してブロックしません。SSI セマンティクスの場合、それはアボートすることがあります。

- 伝統的二相コミットプロトコルよりも低遅延です(競合のない時)。二相目は、トランザクションレコードへの一つのライトを必要とするだけで、全てのトランザクション参加者への同期のラウンドトリップは要らないからです。

- 優先度は任意の長さのトランザクションに対して、飢餓を防ぎます。そして、競合するトランザクションの中から、常に勝者を選びます(両方アボートすることはありません)。

- ライトはクライアントでバッファされません。ライトは失敗する時は早いです。

- serializable SI に対して、リードロックのオーバーヘッドがありません(他の SSI 実装と比べて)。

- 優先度を正しく選ぶと(つまり、ランダム度を少なく)、任意のトランザクションに遅延の確率的保証を柔軟に与えられます(例えば、OLTP トランザクションは、非同期にスケジュールされるジョブのような低優先度のトランザクションと比べて、１０倍、アボートしにくくすることができます)。

欠点

- リース保持者でない複製からのリードは、それでもやはり、リードタイムスタンプキャッシュを更新するために、リース保持者への ping を必要とします。

- 放棄されたトランザクションは、最大ハートビート間隔だけ、競合するライターをブロックすることがあります。しかし、平均的待ち時間は、ずっと短いでしょう(リンクにあるグラフを参照下さい)。これは、リードとライトロックを放すために検出をして二相コミットを再開始するよりもずっと高性能と思われます。

- 他の SI 実装とのふるまいの違い。最初のライターが勝つわけではありません。短いトランザクションが常に素早く終わるわけではありません。OLTP システムにとって驚きとなる点は、問題となるでしょう。

- 二相ロッキングと比べて、競合するシステムにおいてはアボートがスループットを下げることが多いでしょう。アボートと再開始はリードとライトのトラフィックを増し、遅延を増し、スループットを減らします。

タイムスタンプを選ぶ

クロックスキューのある分散システムでデータを読む時の、鍵となる挑戦は、全てのコミット済みトランザクションの最新のタイムスタンプよりも(絶対時刻で)大きいことが保証されるタイムスタンプを選ぶことです。既にコミットされたデータを読むことのできないシステムは一貫性を主張できません。

一つのノードをアクセスするトランザクション(あるいは一つの操作だけ)について一貫性を達成するのは簡単です。タイムスタンプはそのノード自身がアサインするので、そのノードにある全ての既存のタイムスタンプを持つデータよりも大きいタイムスタンプであることが保証されます。

複数のノードの場合、そのトランザクション t を調停するノードのタイムスタンプが使われます。さらに、既にコミットされたデータのタイムスタンプの上限を与えるために t + ε が提供されます(ε は、最大クロックスキューです)。トランザクションが進むにつれて、t より大きく、t + ε より小さいタイムスタンプを持つデータが読まれると、そのトランザクションはアボートし、競合したタイムスタンプ tc を使って再開始することになります。tc > t です。最大のタイムスタンプ t + ε は同じです。これは、クロックが不確実なために起きるトランザクション再開始は長さ ε の時間間隔の間だけ起きるということです。

私たちは、不確実のために起きる再開始を減らすために別の最適化をします。再開始の時に、トランザクションは tc だけでなく、不確実なリードが起きた時刻のそのノードのタイムスタンプ tnode も考慮します。この二つのタイムスタンプ tc と tnode の大きい方(後者であることが多いでしょう)が、リードタイムスタンプを加算するために使われます。さらに、競合しているノードは、 “certain” とマークされます。そしてそのトランザクションのそのノードへの将来のリードは、`MaxTimestamp = Read Timestamp`にして、これ以上の不確実のための再開始を防ぎます。

リードの時には、そのノードには tnode より大きなタイムスタンプを持つキーのいかなるバージョンもないことを私たちは知っているという事実の結果、正しさが保証されます。そのノードによって起きた再開始では、もしトランザクションがより大きいタイムスタンプを持つキーを見たら、その値は、絶対時刻で、 tnode が得られた、つまり、不確実なリードの後に、書かれたことがわかります。なので、トランザクションは、そのデータの古いバージョン(そのトランザクションのタイムスタンプの時の)を読んで進むことができます。これは、あるノードに起因する時刻不確実のための再開始を最大一度に制限します。私たちが、最適なもの(> 競合するタイムスタンプの最大値)より大きなタイムスタンプを選ぶことがあるというトレードオフがあります。その結果、競合の確率は少し高くなります。

私たちは、再開始はまれだと期待します。しかしこの仮定は、再開始が問題となった時には再検討が必要でしょう。この問題は、歴史的リードには起きないことに注意ください。再開始を必要としない別のアプローチは、全てのノードにあらかじめひとつのラウンド問い合わせて、報告されたノードの壁時計の最大値をタイムスタンプとして使うことです。しかし、あらかじめアクセスされるノードがどれか知るのは困難で、潜在的に限界があります。Cockroach は、グローバル時計を使うこともできます（Google  は、Percolator でこれをしました）。しかしそれは地理的に近いクラスタで適切でしょう。

厳格な Serializability (Linearizability)

大まかに言って、厳格な serializability （この文書では、linearizability と言うこともあります）と、CockroachDB のデフォルトのアイソレーションレベル（serializable）との違いは、linearizable トランザクションにおいては、因果律が保たれることです。つまり、もしあるトランザクション（例えば利用者の投稿を作成する）が、その前のもの（まずはその利用者を作成する）が完了するのを待っているとしたら、前者にアサインされる論理的タイムスタンプは後者のそれよりも大きいことが期待されるでしょう。

現実では、分散データベースにおいて、これは成立しないことがあります。典型的には、分散システム全体ではクロックが完全に同期していないためで、「後者」のトランザクションが、最初のトランザクションが走った部分とは分断された部分を触ったために、コミットタイムスタンプを決めるためのクロックが分断された情報を持つことになったためです。

現実では、Cockroach では、多くのトランザクショナルなワークロードは実際に linearizable です。しかし、正確な条件は、ここで概説するには複雑過ぎます。

典型的には、因果律は多くのトランザクションで必要ではありません。なので、本当にそれが必要なときにだけ、対価を払うのが有利です。Cockroach はこれを、causality token によって実装します。トランザクションがコミットするとき、causality token を取得して、次のトランザクションに渡すことができます。それは、この二つのトランザクションが、増加する論理的タイムスタンプをアサインされることを保証します。

さらに、より優れた同期がとれたクロックが、クラウド提供者によって提供される標準的コモディティとなるにつれて、Cockroach は、グーグルの Spanner が行なったのとほぼ同じことをすることによって、グローバルな linearizability を提供できるでしょう。つまり、コミットの後、クライアントに戻る前に、最大クロックオフセットだけ、待つという。

よりずっと深い情報は、以下のブログ投稿を参照下さい。

https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

論理的マップの内容

論理的には、このマップは、専用のシステムキー／値の対の連続と、その後に続く実際のユーザデータ（SQL サブシステムが管理します）を含みます。

- `\x02<key1>`: `\x03<key1>` までのレンジのためにレンジメタデータ。これは "meta1" キーです。

- ...

- `\x02<keyN>`: `\x03<keyN>`までのレンジのためにレンジメタデータ。これは "meta1" キーです。

- `\x03<key1>`: `<key1>`までのレンジのためにレンジメタデータ。これは "meta2" キーです。

- ...

- `\x03<keyN>`: `<keyN>`までのレンジのためにレンジメタデータ。これは "meta2" キーです。

- `\x04{desc,node,range,store}-idegen`: いろいろなコンポーネントタイプのための ID 生成オラクル。

- `\x04status-node-<varint encoded Store ID>`: ランタイムメタデータを格納します。

- `\x04tsd<key>`: Time-series data キー。

- `<key>`: ユーザキー。実際は、これらのキーは SQL サブシステムが管理します。それが、自分自身のキーの内容を決めます。

ストアとストレージ

ノードは一つ以上のストアを持ちます。それぞれのストアは、独立したディスクに置くべきです。内部的に、それぞれのストアは、RocksDB の一つのインスタンスを持ちます。それは、一つのノードに格納される全てのストアの間で共用されるブロックキャッシュを持ちます。そして次に、これらのストアはレンジ複製の集まりを持ちます。一つのレンジのための複製は、同じストア、あるは同じノードにさえ、一つ以上は決して置かれません。

クラスタが最初に初期化された時、一番最初には、いくつかのデフォルトのスターティングレンジは一つの複製しか持ちません。しかし、他のノードが使用可能になるにつれて、複製はそこに複製されます。それは、望ましい複製ファクター、デフォルトは3、に達するまで続きます。

自己修復

もし、あるストアからしばらくの間、便りが(自分のディスクリプタをゴシップする)なければ、デフォルト設定は五分です、クラスタはこのストアを落ちたと考えます。これが起きたら、そのストアにある全ての複製は使用不可能と判断され、除かれます。

訳注。レンジが使用不可能と原文にあるのは誤りでしょう。

そのストアに複製を持つレンジは、他の使用可能なストアに、自分を複製します。これは、望ましい複製ファクターがまた満たされるまで続きます。もし、同時に５０％以上の複製が使用不可能になると、クォーラムがなくなるので、レンジ全体は、少なくても５０％以上の複製が再び使用可能となるまで、使用不可能とされます。

再バランス

システムにより多くのデータが加わるにつれて、あるストアは他よりも早く増加するかもしれません。これに対処し、負荷全体をクラスタ全体にばらまくために、複製は、目的の複製ファクターを維持しながら、ストアの間を移動します。この再バランスを行う時に使われるヒューリスティックには、以下があります。

・ストアあたりの複製数

・ストアで使われているデータの大きさの合計

・ストアの空き容量

将来は、以下のファクターも考慮されるでしょう。

・ストアの、CPUとネットワーク負荷

・問い合わせで、しばしば一緒に使われるレンジ

・ストアのアクティブなレンジの数

・ストアが持っているレンジリースの数

レンジメタデータ

レンジのデフォルトの大きさはほぼ64M(2^26 B)です。1P(2^50 B)の論理的データをサポートするためには、ほぼ、 2^(50 - 26) = 2^24 個のレンジのためのメタデータが必要です。合理的なレンジメタデータの大きさの最大値は、ほぼ256バイトです(三段階になったノード位置のために、3*12 バイト、レンジキー自身のために、220バイト)。2^24 レンジ * 2^8 B はほぼ、格納するために4G (2^32 B) 必要です。これは、マシンの間で複製するには大きすぎます。私たちの結論は、レンジメタデータは大規模構成の場合分散されなくてはいけないということです。

分散メタデータでもキー検索を比較的速く保つために、私たちは、全てのトップレベルのメタデータを単一のレンジ(最初のレンジ)に格納します。これらのトップレベルのメタデータキーは、meta1 キーと呼ばれ、キー空間の先頭にソートされるようにプレフィックスされます。前述のように、メタデータの大きさを256バイトとすると、単一の64Mレンジは 64M/256B = 2^18 レンジをサポートできます。それは全体で、64M * 2^18 = 16T のストレージを提供します。前述のように、1P をサポートするには、二段階の間接が必要です。最初のレベルは二つ目をアドレスし、二つ目がユーザデータをアドレスします。二段階の間接で、2^(18 + 18) = 2^32 レンジをアドレスできます。それぞれのレンジは 2^26 B をアドレスするので、全体で、2^(36 + 26) B = 2^62 B = 4 E のユーザデータをアドレスできます。

ユーザがアクセス可能な key1 に対して、対応する meta1 レコードが、meta1 空間の key1 の後のキーの位置に見つかります。meta1 空間は疎ですから、続くキーは、存在する次のキーとして定義されます。meta1 レコードは、 meta2 レコードを含むレンジを指定します。それは同じプロセスを使って見つかります。meta2 レコードは key1 を含むレンジを指定します。それはまた、同じ方法で見つかります（以下の例を参照下さい）。

具体的には、メタデータキーは、\x02 (meta1) そして \x03 (meta2) プレフィックスされます。プレフィックス \x02 と \x03 は、望ましいソート時のふるまいをします。こうして、key1 の meta1 レコードは、\x02<key1> の次のキーの位置にあります。

注意：私たちは、meta{1,2} レコードに、それぞれのレンジの終了キーを加えます。これは、RocksDB のイテレータが Ceil() のようにふるまう Seek()  しかサポートしないためです。あるレンジの開始キーを使うと、Seek()  は探しているメタインデックスレコードの後のキーを見つけることになります。それは、イテレータをバックアップすることを必要とし、それは効率的ではなく、常に可能ではない選択肢です。

以下の例は、レンジ三つ分のデータを持つマップのディレクトリ構造を示します。てんてんは、データのレンジ全体を満たす、追加のキー／値対を示します。わかりやすくするために、例では、 meta1 と meta2 を、プレフィックス \x02 と \x03 を指すために使います。レンジを分割するためには、メタデータレイアウトを知っていてレンジメタデータを更新する必要が有るという事実を除けば、レンジメタデータ自身は、特別の扱いや、ブートストラップは必要ありません。

Range 0 (サーバ dcrama1:8000, dcrama2:8000, dcrama3:8000 にあります)

・meta1\xff: dcrama1:8000, dcrama2:8000, dcrama3:8000

・meta2<lastkey0>: dcrama1:8000, dcrama2:8000, dcrama3:8000

・meta2<lastkey1>: dcrama4:8000, dcrama5:8000, dcrama6:8000

・meta2\xff: dcrama7:8000, dcrama8:8000, dcrama9:8000

・...

・<lastkey0>: <lastvalue0>

Range 1 (サーバ dcrama4:8000, dcrama5:8000, dcrama6:8000 にあります)

・...

・<lastkey1>: <lastvalue1>

Range 2 (サーバ dcrama7:8000, dcrama8:8000, dcrama9:8000 にあります)

・...

・<lastkey2>: <lastvalue2>

より単純なマップを考えましょう。それは、一つのレンジより少ないデータしか持ちません。この場合、全てのレンジメタデータと全てのデータは同じレンジにあります。

Range 0 (サーバ dcrama1:8000, dcrama2:8000, dcrama3:8000 にあります)*

・meta1\xff: dcrama1:8000, dcrama2:8000, dcrama3:8000

・meta2\xff: dcrama1:8000, dcrama2:8000, dcrama3:8000

・<key0>: <value0>

・...

最後は、二つの間接レベルを必要とするほどに大きなマップです（レンジ複製を示す代わりに、この例はレンジインデックスだけを示すように簡単化されているのに注意下さい）。

Range 0

・meta1<lastkeyN-1>: Range 0

・meta1\xff: Range 1

・meta2<lastkey1>: Range 1

・meta2<lastkey2>: Range 2

・meta2<lastkey3>: Range 3

・...

・meta2<lastkeyN-1>: Range 262143

Range 1

・meta2<lastkeyN>: Range 262144

・meta2<lastkeyN+1>: Range 262145

・...

・meta2\xff: Range 500,000

・...

・<lastkey1>: <lastvalue1>

Range 2

・...

・<lastkey2>: <lastvalue2>

Range 3

・...

・<lastkey3>: <lastvalue3>

Range 262144

・...

・<lastkeyN>: <lastvalueN>

Range 262145

・...

・<lastkeyN+1>: <lastvalueN+1>

range 262144 を選んだのは、単に近似であることに注意下さい。一つのメタデータレンジでアドレス可能なレンジの実際の数は、キーの長さに依存します。キー長を小さくしようと努力がされるなら、アドレス可能なレンジの総数は、増えるでしょうし、逆も真です。

前記の例では、キー位置の検索は、<key> の値を得るためには、最大でも三回のリードを必要とすることが明らかです。

1. meta1<key> の最小値

2. meta2<key> の最小値

3. <key>

小さいマップならば、検索全体は、レンジ０への一つの RPC だけで満足できます。１６T 以下のデータを持つマップは二つの検索を必要とするでしょう。クライアントは、レンジメタデータの両方のレベルをキャッシュします。そして、個々のクライアントのデータ局所性は高いことが期待されます。クライアントは古いキャッシュエントリを使うことになるかもしれません。検索時に、参照されたレンジがクライアントの期待とマッチしない場合、クライアントはその古いエントリを取り除いて、きっと新しい検索をするでしょう。

Raft - レンジ複製の一貫性

それぞれのレンジは、三つ以上の複製からなるように構成されています。それは、その ZoneConfig で指定されます。レンジ内のそれぞれの複製は、自分自身の分散コンセンサスアルゴリズムのインスタンスを維持します。私達は、Raft コンセンサスアルゴリズムを選びました。それは推論するのにより単純で、重要な詳細をカバーするレファレンス実装があるためです。

ePaxos は、WAN 分散された複製に対して素晴らしい性能特性を持ちますが、複製間の一貫したオーダリングを保証しません。

Raft は比較的長寿命のリーダーを選出し、それがコマンドをプロポーズするためには必須です。それは定期的にフォロワーにハートビートして、それらのログを複製された状態に維持します。ハートビートがなくなると、フォロワーはランダム化された選出タイムアウトの後に候補者となり、新しいリーダー選出をします。Cockroach は、ランダムなタイムアウトに重みをつけて、他ノードへのより短いラウンドトリップ時間を持つ複製が、最初に選出を始めやすいようにします（まだ実装されていません）。Raft リーダーだけがコマンドをプロポーズできます。フォロワーは単純にコマンドを最近既知であるリーダーに転送します。

私達の Raft 実装は CoreOS と一緒になって開発されました。しかし、一つのノードが数百万のコンセンサスグループ（レンジあたり一つ）を持つことがあるという事実を考慮した最適化の層を追加しました。最適化の領域は、主に、ハートビートの集約化（ノードの数が、ハートビートの数を決めます。より大きな、レンジの数ではなく）と、要求のバッチ処理です。将来の最適化は、二相の選出と、quiescent 静かなレンジ（つまり，インアクティブなレンジに対してはトラフィックを完全に止めます）です。

レンジリース

Raft の節で概説したとおり、レンジの複製は Raft グループとして組織され、コマンドをそれらの共用されたコミットログから実行します。しかし、Raft を通すのは高価な操作です。そして、一度に一つの複製においてしか実行できない（全ての複製においてでなく）処理があります。特に、権威あるリードを一つの複製から（理想的には一つ以上から。でもそれはずっとむつかしいです）提供できることが望ましいです。

これらのために、Cockroach はレンジリースの概念を導入します。これは、(database, i.e. hybrid logical) 時間のスライスの間、保持されるリースです。複製は、raft を通して特別なリース確保ログエントリをコミットすることによって自分をあるレンジに対するリースの所有者として確立します。そのログエントリはその複製ノードの node liveness table （それぞれのノードごとのエポックと満了時刻を持つシステムテーブル）から得たエポックを含みます。ノードは、liveness table の自分のエントリの満了時刻を連続して更新する責任があります。リースが raft を通してコミットされたら、その複製はそのリース確保コマンドをアプライしたらすぐにリース保持者になります。これは、その複製がそのリースを使うときには、それは既にその複製に対する全ての以前のライトをアプライしており、その結果をローカルに見ることができることを保証します。

二つのノードがリースを取ることを防ぐために、要求者は自分がそのリースを要求するときに有効であると自分が信じるリースのコピーを含めます。新しいリースが適用される時にそのリースがまだ有効ならば、それは許可されます。あるいは、その間に他のリースが許可され、要求されたリースは無視されます。リースは、ノードA のliveness レコードが満了して、そのエポックが加算された後に限って、ノードAからノードBに移動することができます。

注意：node liveness table キー空間にあるレンジのためのレンジと、それより前にある全てのレンジ、それには、 meta1, meta2 を含みます、のためのレンジリースは、上記機構を使っては管理されません。循環依存を防ぐためです。

あるエポックにおいて、リースを持っている複製は、ノードエポックが変わり、満了時刻になるまではずっと、そのリースを使うことができます。リースを持っている複製は、Raft を経由するオーバヘッドを起こすことなく、リードをローカルに処理できます。また、その複製は、分割、マージ、そして再バランスのような、レンジ固有のメンテナンス作業の責任があるか、またはそれに関わることがあります。

通常は、全てのリードとライトはリースを持っている複製に送られます。誰も持っていなければ、任意の複製に送られます。それは、その複製が同期でリースを取るようにします。リースを持ってない（要求のヘッダにある HLC タイムスタンプの間）人が受けた要求は、失敗し、応答はその複製の最後の既知のリース所有者を指す情報を含みます。この要求は、更新されたリースとともに、ゲートウェイノードによって透過的にリトライされ、クライアントには決して届きません。

リードは Raft をバイパスするので、新しいリース所有者は、何より先に、自分のタイムスタンプキャッシュが前回のリース所有者のよりも小さいタイムスタンプを報告しないことを確認します（前回のリース所有者において起きたかもしれないリードと互換となるためです）。これは、リースが実際に満了する前に、それを、stasis period （それは、単に、満了時間マイナス最大クロックオフセットです）に置くことで実現されます。そうすれば、次の全てのリース所有者がしなくてはいけないことは、タイムスタンプキャッシュの低ウォーターマークをその新しいリースの開始時刻に設定することだけです。

リースが stasis period に入ると、それ以上はリードもライトも処理されません。それは望ましくありません。しかし、これは現実的には、ノードが使用不可能になった時にしか起きません。現実的なほぼ全ての状況では、使用不可能になることはありません。リースは通常は長い寿命ですから（そして／あるいは積極的に伸ばされます。それは stasis period を避けることになります）。あるいはリースはそれが起きる前にリース所有者から他に転送されます。それもやはり、stasis period を避けることになります。次のリースが有効になるまではそれ以上のリードを処理しないことを約束することになるからです。

Raft リーダーシップとの同居

レンジリースと Raft リーダーシップとは完全に分離しています。それは特に何もしなくてもそうなります。Raft リーダーシップとレンジリースは同じ複製が持っていないことがあります。この二つの役割が同居しないのは高価ですから(リース保持者はそれぞれのプロポーザルをリーダーに転送しなくてはならず、高価な RPC ラウンドトリップを加えます)。リースの更新や受け渡しをするときも、それらを同居させようと試みます。現実的にはこれは、ミスマッチはまれで、自分で素早く修正されることを意味します。

コマンド実行フロー

この節は、リースを保持する複製が読み書きコマンドをどのように処理するかを詳しく説明します。それぞれのコマンドは、(１)そのコマンドがアクセスするキー(あるいはキーの範囲)と、(２)そのキーが属するレンジの ID を指定します。コマンドを受けた時、ノードは指定されたレンジ ID のレンジを検索し、そのレンジがまだ、指定されたキーの責任を持っているかチェックします。もしキーのどれかがそのレンジに属していないなら、そのノードはエラーを返し、クライアントがリトライして正しいレンジに要求を送るようにします。

キーの全てがそのレンジに属するなら、そのノードはそのコマンドを処理しようとします。そのコマンドが不整合を許すリードオンリーのコマンドなら、すぐに処理されます。そのコマンドが整合が必要なリードあるいはライトならコマンドは以下の両方の条件が満たされた時に実行されます。

・そのレンジ複製がリースを持っている。

・サブミットされたこのコマンドとキーがオーバーラップし、読み書きの競合を起こすコマンドが他に走っていない。

最初の条件が満たされない場合、複製はリースを得ようと試みるか、エラーを返してクライアントがそのコマンドを現在のリース所有者にリダイレクトするようにします。二つ目の条件は、あるキーに対する一貫した読み書きがシーケンシャルに実行されることを保証します。

上記の二つの条件が満たされたら、リース所有者の複製はそのコマンドを処理します。一貫したリードはリース所有者において直ちに処理されます。ライトコマンドは、Raft ログにコミットされるため、全ての複製は同じコマンドを実行します。全てのコマンドは決定論的な結果を生成します。このため、レンジの複製はお互いに一貫した状態を維持します。

ライトコマンドが完了したら、全ての複製は自分の応答キャッシュを更新して、べき等性を保証します。リードコマンドが完了したら、リース所有者である複製は自分のタイムスタンプキャッシュを更新して、あるキーに対する最新のリードを追跡できるようにします。

コマンドが実行される間に、レンジリースが満了する可能性があります。コマンドを実行する前に、それぞれの複製は、コマンドを提案している複製がまだリースを持っているかをチェックします。リースが満了している場合、そのコマンドはその複製によって拒否されます。

レンジの分割とマージ

ノードは、レンジが、容量あるいは負荷のしきい値の最大値あるいは最小値を超えたかどうかに基づいて、レンジを分割あるいはマージします。容量あるいは負荷の最大値を超えたレンジは分割され、容量と負荷の両方の最小値より小さいレンジはマージされます。

レンジは、キープレフィックスと同じ使用統計を維持します。これは、結局、分の粒度のデータ点の時系列です。バイト数から、読み書きのキュー長までの全てがあります。統計の任意の蒸留結果は、分割／マージの基本として使うことができます。分割／マージで使われる二つの適切なメトリックは、レンジのバイト数と、IO／秒です。複製をあるノードから他へ再バランスするための良いメトリックは読み書きキューの合計待ち時間でしょう。これらメトリックはゴシップされます。それぞれのレンジあるいはノードは、自分自身が、知っている範囲の最小あるいは最大であるならば、関連するメトリックを受け渡します。

容量あるいは負荷のしきい値を超えたレンジは分割します。そのために、そのレンジのリース保持者は、適切なスプリットキーの候補を計算して、Raft を経由して分割を発行します。分割とは違って、マージはレンジが、容量と負荷の両方において、最小しきい値より小さい必要があります。マージされるレンジは、そのすぐ前あるいはすぐ後のレンジのうち小さい方を選びます。

分割、マージ、再バランス、そして回復は、データをノード間で移動するための、同じ基本的なアルゴリズムに従います。新しい複製ターゲットは、作成され、ソースレンジの複製セットに加わります。次に、新しいそれぞれの複製は、ログを完全にリプレイするかそれとも、ソース複製データのスナップショットを複写し、次にそのスナップショットのタイムスタンプからのログをリプレイして完全にキャッチアップするかのいずれかの方法でアップトゥーデートにされます。新しい複製が完全にアップトゥーデートになったら、レンジメタデータが更新され、古いソース複製は可能なら消されます。

コーディネータ (リース所有者の複製)

if splitting

  SplitRange(split_key):  分割は、レンジ複製において、ローカルに起きます。そして、ローカルに完了した後で、新しい目的の複製に移動されます。

else if merging

  目的のレンジ複製と同じサーバで、新しい複製を選びます。複製セットに加えます。

else if rebalancing || recovering

  負荷が最も少ないサーバにおいて複製を選びます。複製セットに加えます。

新しい複製

複製を最新にする：

if 複製されたログから全ての情報を読むことができるならば

  複製されたログを複写します。

else

  ソース複製をスナップショットします。

  スナップショットを参照しているソース複製に、連続する ReadRange 要求を送ります。

if merging

  全ての複製のレンジを結合します。

else if rebalancing || recovering

  古いレンジ複製を削除します。

ノードは、あるレンジにあるデータ総量が設定可能な最大しきい値を超えた時にレンジを分割します。同様に、データ総量が設定可能な最小しきい値より小さくなるとレンジはマージされます。

TBD:説明を増やすこと：

特に、マージでは（なお、再バランスでも）ローカルノードから消えるレンジがあります。そのレンジは、そのデータの新しい所有者に操作をスムーズに受け渡して優雅に消える必要があります。

レンジは、あるノードが自分の負荷あるいは容量がクラスタ内で最悪であると、ゴシップされた負荷統計に基づいて判断した時に再バランスされます。同じデータセンタにある、予備の容量を持つノードが選ばれ、特別ケースの分割が行われます。それは、単純にデータを１：１で複製し、レンジ構成メタデータをリセットします。

ノードアロケーション(ゴシップによる)

レンジがスプリットした時は、新しいノードをアロケートしなくてはいけません。それぞれのノードが、全ての、あるいは多数の仲間のノードの状態を知っていることを要求したり、あるいは、十分なグローバルな知識を持つキュレーターあるいはマスターを専用に必要とする代わりに、私たちはゴシッププロトコルを使って、クラスタ内の全てのノードの間で、面白い情報だけを効率的に通信します。面白い情報とは何でしょう？一つの例は、あるノードがたくさんの予備の容量を持っていることです。ゴシップする時、それぞれのノードはゴシップのそれぞれの話題を自分自身の状態と比べます。もし自分の状態が、最近見た話題中の最も面白くないものより何らかの意味で「より面白い」なら、それは、仲間のノードとの次回のゴシップセッションの一部として、自分の状態を含めます。このようにして、平均よりかなり大きな容量を持っているノードは、クラスタ全体から素早く見つけられます。

ゴシッププロトコル自身には、二つの主なコンポーネントがあります。

・相手の選択: それぞれのノードは、常時通信する N 個の相手を維持します。それは、ファンアウトを最大にする意図のもとで相手を選びます。あるノードが知っているノードと、大きくオーバラップするノードのセットと通信しているノードと、あるノードにとって未知のノードのいくつもと通信しているノードでは、後者が相手として選ばれます。ゴシップが始まる時に毎回、それぞれのノードの相手のセットが交換されます。それぞれのノードは自由に、他の人の相手で適切なものを取り込むことができます。あるノードに多すぎる入力要求が来て問題を起こすのを避けるために、ノードはゴシップ交換に答えるのを拒否できます。それぞれのノードは、あまりオーバラップのないノードからの要求に答え、そうでないものは拒否する傾向にあります。

相手は、  Agarwal & Trachtenberg (2006) に書かれているように、ヒューリスティックスを使って効率よく選ばれます。

TBD: 分割を避けるにはどうしますか？プロトコルのシミュレーションを作って、ふるまいをチューニングし、それがどのくらいうまくいくか経験的に調べる必要があります。

・ゴシップ選択: 何を通信するか。ゴシップは、トピックに分かれています。負荷特性(ディスクごとの容量、CPU負荷、そして状態[例えば、ドレイン中、OK、障害]) などが、ノードのアロケーションを駆動するために使われます。レンジ統計(レンジの読み書き負荷、無くなった複製、使用不可能なレンジ)そしてネットワークトポロジー(ラックの間のバンド幅／遅延、データセンター間のバンド幅／遅延、サブネット障害)を使って、いつレンジを分割するのが良いか、複製を回復するのとネットワーク接続が回復するのを待つのとどちらが良いかを決めます。デバッグやシステム管理にも使います。いずれの場合も、最小値のセットと最大値のセットが伝搬されます。それぞれのノードは、自分自身の世界観を適用して、それらの値を補強します。最小値と最大値のそれぞれには、それを報告したノードがタグ付けされています。その他の関連する文脈情報もあります。ゴシップのそれぞれのトピックは、構造化データを保持するための専用の protobuf を持ちます。それぞれのトピックのゴシップのアイテムの数は、設定可能な最大値で制限されます。

効率のために、ノードは、ゴシップの新しいアイテムのそれぞれにシーケンス番号を与えます。そして、相手ノードのそれぞれが今までに見た最大のシーケンス番号を維持します。毎回のゴシップのラウンドでは、新しいアイテムを含む差分だけを通信します。

ノードとクラスタのメトリック

システムの全てのコンポーネントは自分に関する興味深いメトリックを公開する責任があります。それは、ヒストグラムであったり、スループットカウンタであったり、測定ゲージであったりします。

これらのメトリックは、外部のモニタリングシステム(Prometheus のような)に対して、HTTP エンドポイント経由で公開されます。しかし、CockroachDB は内部的な時系列データベースも持っています。それは複製されたキーバリューマップに格納されます。

時系列データベースはストアごとの粒度で格納され、管理者ダッシュボードを使って、クラスタ、ノード、あるいはストアのレベルでの情報宇宙の中で効率的に可視化できます。

定期的なバックグラウンド処理が、古い時系列データを選り分け、ダウンサンプリングし、最終的にはそれを捨てます。

キープレフィックス統計とゾーン

キープレフィックスに関して、任意の細粒度の統計を指定できます。キープレフィックスはオーバーラップできます。それは、階層的関係をとらえるために必要だからです。例を示すために、データベースのセットにある行を指定するキーが、以下の形式を持つとしましょう。

この場合、以下のキープレフィックスについて統計を取ることができます。

デフォルトで、統計はマップ全体に対して保持されます。

統計

ーーここから

ーーここまで

SQL

クラスタのそれぞれのノードは、SQL クライアント接続を受けることができます。CockroachDB は PostgreSQL ワイアプロトコルをサポートし、ネイティブ PostgreSQL クライアントドライバを再使用できます。SSL を使い、クライアント証明書を使って認証されるコネクションは、サポートされ、暗号化されない(セキュアでない)パスワードを基とするコネクションよりも推奨されます。

それぞれのコネクションは SQL セッションと関連づけられ、それがサーバ側のコネクションの状態を持ちます。セッションが有効な間、クライアントは SQL を使ってトランザクションをオープン、クローズし、文と問い合わせを発行し、セッションパラメータを設定できます。これは他の SQL データベースと全く同じです。

言語サポート

CockroachDB はまた、PostgreSQL がサポートする SQL のフレーバーをエミュレートしようと試みますが、重要ないくつかの点で異なりもします。

・CockroachDB は、トランザクションの MVCC ベースの一貫性だけを実装します。なので、SQL のアイソレーションレベル SNAPSHOT と SERIALIZABLE だけをサポートします。他の伝統的な SQL アイソレーションレベルは、内部的に、SNAPSHOT あるいは SERIALIZABLE のどちらかにマップされます。

・CockroachDB は、独自の SQL 型システムを実装します。それは、PostgreSQL に比べて、型の間の暗黙的な変換をより限られた形でしかサポートしません。その理由は、実装を単純で効率的に保つためです。それは、１) クライアントのほとんどの SQL コードは対応する型で自動的に生成されることと、２) 他のデータベースのための既存の SQL コードはどちらにせよ、CockroachDB のために修正する必要があるだろうという観測に基づきます。

SQL アーキテクチャ

ネットワークを通るクライアントコネクションは、それぞれのノードにおいて、 pgwire サーバプロセス(goroutine)によって処理されます。これは、入力コマンドのストリームを処理し、問い合わせ／文の結果を含む応答を送り返します。

ーーここから

pgwire サーバはまた、pgwire レベルのコンパイル済み文を処理します。引数をコンパイル済み文にバインドし、実行のためにコンパイル済み文を探します。

SQLコネクションの状態は、セッションオブジェクトと、モノリチックな planner オブジェクトが維持します。planner はコネクションに一つあり、セッション、現在の SQL トランザクション状態、そして背後にある KV ストアの間で、実行を

します。

文あるいは問い合わせを受けた時(直接あるいは以前にコンパイルされた文の実行により)、pgwire サーバはその SQL テキストをそのコネクションに関連する planner に転送します。SQL コードは次に、 SQL 問い合わせプランに変換されます。問い合わせプランは、その問い合わせを解決するために必要な、

のような高レベルデータ操作を記述するオブジェクト木として実装されます。問い合わせプランオブジェクトは、現在、その問い合わせプランの実行に必要なランタイム状態も含みます。SQL 問い合わせプランが準備できたら、次はそれらのオブジェクトに対するメソッドが、他のプログラミング言語で言う、「ジェネレータ」のように、実行を行います。それぞれのノードは子ノードを開始し、それ以降、それぞれの子ノードは結果の行のストリームのジェネレータとしてはたらきます。親ノードはその結果を消費し、累積的に変換し、自分もまたジェネレータとして、その親ノードに提供します。

最上位の plannerは、問い合わせプランの上位のノードの生成したデータを消費し、それを pgwire 経由でクライアントに返します。

SQL モデルと KV の間のデータマッピング

ーーここまで

ーーここから

ーーここまで