データモデル

etcdは、更新頻度の低いデータを確実に保存し、信頼できる監視クエリーを提供するように設計されています。etcdはキー・バリューペアの過去のバージョンを公開し、低コストのスナップショットと過去のイベントの監視（「タイムトラベルクエリー」）を実現します。永続的な多版型同時実行制御のデータモデルは、このような用途に適しています。

etcdは、多版型の永続的な キー・バリューストアにデータを保存します。永続的なキー・バリューストアは、値が新しいデータで置き換えられても、キー・バリューペアの以前のバージョンを保持します。このキー・バリューストアは実質的に不変です。操作は既存の構造をその場で更新せず、更新を反映した新しい構造を常に生成します。変更後も、キーの過去のすべてのバージョンにアクセスし、監視できます。データストアが時間とともに無制限に増大し、古いバージョンを保持し続けるのを防ぐため、ストアをコンパクションして、更新によって古くなったデータの最も古いバージョンを取り除くことができます。

論理的な構造

ストアの論理的な構造は、平坦なバイナリーキー空間です。キー空間には、バイト列のキーを辞書順に並べたインデックスがあるため、範囲クエリーを低コストで実行できます。

キー空間は複数のリビジョンを保持します。ストアを作成した時点のリビジョンは1です。アトミックな変更操作（たとえば、トランザクション操作には複数の操作が含まれることがあります）のたびに、キー空間に新しいリビジョンが作成されます。過去のリビジョンが保持するすべてのデータは変更されません。キーの古いバージョンには、過去のリビジョンを通じて引き続きアクセスできます。同様に、リビジョンにもインデックスが付けられるため、ウォッチャーでリビジョンの範囲を効率的に扱えます。領域を節約するためにストアをコンパクションすると、コンパクションリビジョンより前のリビジョンが削除されます。リビジョンは、クラスターの存続期間を通じて単調に増加します。

キーの作成から削除までを1つの世代とします。各キーは1つ以上の世代を持つことがあります。キーを作成すると、そのキーのバージョンが増加します。現在のリビジョンにキーが存在しなければ、1から始まります。キーを削除すると、そのキーのトゥームストーンが生成され、バージョンが0にリセットされて現在の世代が終了します。キーを変更するたびにバージョンが増加するため、バージョンはキーの世代内で単調に増加します。コンパクションを行うと、そのリビジョンより前に終了したすべての世代が削除されます。また、コンパクションリビジョンより前に設定された値は、最新のものを除いて削除されます。

物理的な構造

etcdは、永続的なb+tree にキー・バリューペアとして物理データを保存します。効率のため、ストアの状態の各リビジョンは、直前のリビジョンとの差分だけを保持します。1つのリビジョンが、ツリー内の複数のキーに対応することもあります。

キー・バリューペアのキーは、3つの要素からなるタプル（major, sub, type）です。majorは、そのキーを保持するストアのリビジョンです。subは、同じリビジョン内のキーを区別します。typeは、特殊な値に使う省略可能な接尾辞です（値がトゥームストーンを含む場合のtなど）。キー・バリューペアの値は、直前のリビジョンからの変更、つまり1つの差分を保持します。b+treeは、キーのバイト列の辞書順で並びます。リビジョン間の差分に対する範囲検索は高速で、あるリビジョンから別のリビジョンまでの変更をすばやく見つけられます。コンパクションは、古くなったキー・バリューペアを削除します。

etcdは、キーに対する範囲クエリーを高速化するため、メモリー内に補助的なbtree インデックスも保持します。btreeインデックスのキーは、ユーザーに公開されるストアのキーです。値は、永続的なb+tree内の変更へのポインターです。コンパクションは、無効になったポインターを削除します。

全体として、etcdはbtreeからリビジョン情報を取得し、そのリビジョンをキーにしてb+treeから値を取得します（下図）。