TiDB ストレージ

このドキュメントでは、ティクヴの設計アイデアと主要な概念をいくつか紹介します。

storage-architecture

キーと値のペア

データstorageシステムで最初に決めなければならないのは、データstorageモデル、つまり、データをどのような形式で保存するかです。TiKV では、キー値モデルを選択し、順序付けられたトラバーサルメソッドを提供します。TiKV データstorageモデルには、次の 2 つの重要なポイントがあります。

これは、キーと値のペアを格納する巨大なマップ (C++ のstd::Mapに似ています) です。
マップ内のキーと値のペアは、キーのバイナリ順序に従って順序付けられます。つまり、特定のキーの位置を Seek し、次に Next メソッドを呼び出して、このキーよりも大きいキーと値のペアを増分順に取得できます。

このドキュメントで説明されている TiKV の KVstorageモデルは、SQL テーブルとはまったく関係がないことに注意してください。このドキュメントでは、SQL に関連する概念については説明せず、TiKV などの高性能で信頼性の高い分散型キー値storageを実装する方法にのみ焦点を当てています。

ローカルstorage(RocksDB)

どの永続storageエンジンでも、データは最終的にディスクに保存されますが、TiKV も例外ではありません。TiKV はデータをディスクに直接書き込むのではなく、データstorageを担当する RocksDB にデータを格納します。その理由は、スタンドアロンstorageエンジン、特に慎重な最適化を必要とする高性能スタンドアロンエンジンの開発には多大なコストがかかるからです。

RocksDB は、Facebook がオープンソース化した優れたスタンドアロンstorageエンジンです。このエンジンは、単一のエンジンで TiKV のさまざまな要件を満たすことができます。ここでは、RocksDB を単一の永続的なキー値マップとして考えることができます。

Raftプロトコル

さらに、TiKV の実装では、1 台のマシンに障害が発生した場合にデータの安全性を確保するという、より困難な問題に直面します。

簡単な方法は、データを複数のマシンに複製することです。こうすると、1 台のマシンに障害が発生しても、他のマシンのレプリカは引き続き利用できます。つまり、信頼性が高く、効率的で、レプリカに障害が発生した場合でも対処できるデータ複製スキームが必要です。これらはすべて、 Raftアルゴリズムによって可能になります。

Raft はコンセンサスアルゴリズムです。このドキュメントでは、 Raft簡単に説明します。詳細については、理解しやすいコンセンサスアルゴリズムを求めて参照してください。Raftにはいくつかの重要な機能があります。

Leader選挙
メンバーシップの変更（レプリカの追加、レプリカの削除、リーダーの譲渡など）
ログのレプリケーション

TiKV はRaft を使用してデータレプリケーションを実行します。各データの変更はRaftログとして記録されます。Raft ログレプリケーションを通じて、データはRaftグループの複数のノードに安全かつ確実にレプリケートされます。ただし、 Raftプロトコルによると、書き込みが成功するには、データが大多数のノードにレプリケートされている必要があります。

Raft in TiDB

要約すると、TiKV はスタンドアロンマシン RocksDB を介してディスクにデータをすばやく保存し、マシン障害が発生した場合にはRaft を介して複数のマシンにデータを複製できます。データは RocksDB ではなくRaftのインターフェイスを介して書き込まれます。Raft の実装により、TiKV は分散型キー値storageになります。マシンに障害が発生した場合でも、TiKV はネイティブのRaftプロトコルにより自動的にRaftを完了できるため、アプリケーションには影響しません。

リージョン

理解しやすいように、すべてのデータにレプリカが 1 つしかないと仮定しましょう。前述のように、TiKV は大規模で整然とした KV マップと見なすことができるため、水平方向のスケーラビリティを実現するために、データが複数のマシンに分散されます。KV システムの場合、複数のマシンにデータを分散するための一般的なソリューションは 2 つあります。

ハッシュ: キーによってハッシュを作成し、ハッシュ値に応じて対応するstorageノードを選択します。
範囲: 範囲をキーで分割します。シリアルキーのセグメントがノードに保存されます。

TiKV は、キー値空間全体を一連の連続するキーセグメントに分割する 2 番目のソリューションを選択します。各セグメントはリージョンと呼ばれます。各リージョンは、左が閉じ、右が開いている間隔である[StartKey, EndKey)で表すことができます。各リージョンのデフォルトのサイズ制限は 96 MiB で、サイズは構成できます。

Region in TiDB

ここでのリージョンはSQL のテーブルとは関係がないことに注意してください。このドキュメントでは、SQL については忘れて、今のところ KV に焦点を当てます。データをリージョンに分割した後、TiKV は次の 2 つの重要なタスクを実行します。

クラスター内のすべてのノードにデータを分散し、リージョンを基本単位として使用します。各ノードのリージョンの数がほぼ同じになるように最善を尽くします。
リージョンでRaftレプリケーションとメンバーシップ管理を実行します。

これら 2 つのタスクは非常に重要なので、1 つずつ紹介します。

まず、データはキーに応じて多数のリージョンに分割され、各リージョンのデータは 1 つのノードにのみ保存されます (複数のレプリカは無視されます)。TiDB システムには、クラスター内のすべてのノードにリージョンを可能な限り均等に分散する役割を担う PDコンポーネントがあります。このようにして、一方ではstorage容量が水平方向に拡張され (他のノードのリージョンは新しく追加されたノードに自動的にスケジュールされます)、他方では負荷分散が実現されます (1 つのノードに大量のデータがあるのに、他のノードにはほとんどデータがないという状況は発生しません)。
同時に、上位クライアントが必要なデータにアクセスできるようにするために、システムにはノード上のコンポーネントの分布、つまりキーの正確なリージョンと、任意のキーを通じて配置されたそのリージョンのノードを記録するコンポーネント (PD) があります。
2 番目のタスクでは、TiKV はリージョン内のデータを複製します。つまり、1 つのリージョン内のデータには、「レプリカ」という名前のレプリカが複数存在します。リージョンの複数のレプリカは異なるノードに保存され、 Raftグループを形成します。Raft グループでは、 Raftアルゴリズムによって一貫性が保たれます。
レプリカの 1 つはグループのLeaderとして機能し、もう 1 つはFollowerとして機能します。デフォルトでは、すべての読み取りと書き込みはLeaderを介して処理され、読み取りはリーダーで実行され、書き込みはフォロワーに複製されます。次の図は、リージョンとRaftグループの全体像を示しています。

TiDB Storage

リージョン内でデータを分散および複製することで、ある程度の災害復旧機能を備えた分散型キー値システムが実現します。容量やディスク障害、データ損失について心配する必要がなくなります。

MVCC

TiKV は、マルチバージョン同時実行制御 (MVCC) をサポートしています。クライアント A がキーに書き込み、同時にクライアント B が同じキーを読み取るシナリオを考えてみましょう。MVCC メカニズムがなければ、これらの読み取り操作と書き込み操作は相互に排他的になり、分散シナリオでパフォーマンスの問題やデッドロックが発生します。ただし、MVCC を使用すると、クライアント B がクライアント A の書き込み操作よりも論理的に早い時間に読み取り操作を実行する限り、クライアント B はクライアント A が書き込み操作を実行すると同時に元の値を正しく読み取ることができます。キーが複数の書き込み操作によって複数回変更された場合でも、クライアント B は論理時間に従って古い値を読み取ることができます。

TiKV MVCC は、キーにバージョン番号を追加することで実装されます。MVCC がない場合、TiKV のキーと値のペアは次のようになります。

Key1 -> Value
Key2 -> Value
……
KeyN -> Value

MVCC では、TiKV のキーと値のペアは次のようになります。

Key1_Version3 -> Value
Key1_Version2 -> Value
Key1_Version1 -> Value
……
Key2_Version4 -> Value
Key2_Version3 -> Value
Key2_Version2 -> Value
Key2_Version1 -> Value
……
KeyN_Version2 -> Value
KeyN_Version1 -> Value
……

なお、同じ Key の複数のバージョンがある場合、番号が大きいバージョンが最初に配置されます (Key が順番に並べられているセクションキーバリューを参照)。そのため、Key + Version で Value を取得すると、MVCC の Key は Key と Version で構築でき、これはKey_Versionです。その後、RocksDB のSeekPrefix(Key_Version) API を通じて、このKey_Version以上の最初の位置を直接見つけることができます。

分散ACIDトランザクション

TiKV のトランザクションは、 Google が BigTable で使用しているモデルを採用しています: パーコレーター。TiKV の実装はこの論文にヒントを得て、多くの最適化が行われています。詳細については取引の概要参照してください。