TiDB ストレージ

この文書では、いくつかの設計アイデアとTiKVの重要な概念を紹介します。

storage-architecture

キーと値のペア

データstorageシステムについて最初に決定することは、データstorageモデル、つまりデータをどのような形式で保存するかです。 TiKV が選択したのは Key-Value モデルで、順序付けられた走査方法を提供します。 TiKV データstorageモデルには 2 つの重要なポイントがあります。

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

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

ローカルstorage(RocksDB)

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

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

Raftプロトコル

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

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

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

Leader選挙
メンバーシップの変更 (レプリカの追加、レプリカの削除、リーダーの転送など)
ログのレプリケーション

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

Raft in TiDB

要約すると、TiKV はスタンドアロンマシン RocksDB を介してデータをディスクに迅速に保存し、マシンに障害が発生した場合にはRaftを介して複数のマシンにデータを複製できます。データは、RocksDB ではなくRaftのインターフェイスを通じて書き込まれます。 Raftの実装により、TiKV は分散型 Key-Valuestorageになります。いくつかのマシン障害があっても、TiKV はネイティブRaftプロトコルのおかげで自動的にレプリカを完成させることができ、アプリケーションには影響を与えません。

リージョン

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

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

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

Region in TiDB

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

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

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

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

TiDB Storage

データをリージョンに分散および複製するため、ある程度の災害復旧機能を備えた分散 Key-Value システムが得られます。容量やディスク障害、データ損失について心配する必要はもうありません。

MVCC

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

同じキーの複数のバージョンの場合、番号が大きいバージョンが最初に配置されることに注意してください (キーの順序についてのセクションキーと値を参照)。そのため、キー + バージョンを通じて値を取得する場合、MVCC のキーはキーで構築できます。バージョンはKey_Versionです。次に、RocksDB のSeekPrefix(Key_Version) API を使用して、このKey_Version以上の最初の位置を直接見つけることができます。

分散ACIDトランザクション

TiKV のトランザクションは、 Google がパーコレーターで使用しているモデルを採用しています。 TiKV の実装はこの論文からインスピレーションを受けており、多くの最適化が施されています。詳細は取引概要参照してください。