TiDBストレージ

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

キーと値のペア

データストレージシステムを最初に決定するのは、データストレージモデル、つまり、データがどのような形式で保存されるかです。 TiKVの選択はキー値モデルであり、順序付きトラバーサル方法を提供します。 TiKVデータストレージモデルには、次の2つの重要なポイントがあります。

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

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

ローカルストレージ（RocksDB）

永続ストレージエンジンの場合、データは最終的にディスクに保存され、TiKVも例外ではありません。 TiKVはディスクに直接データを書き込みませんが、データの保存を担当するRocksDBにデータを保存します。その理由は、スタンドアロンストレージエンジン、特に注意深い最適化を必要とする高性能スタンドアロンエンジンの開発には多くの費用がかかるためです。

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

Raftプロトコル

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

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

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

• リーダー選出
• メンバーシップの変更（レプリカの追加、レプリカの削除、リーダーの転送など）
• ログレプリケーション

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

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

リージョン

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

• ハッシュ：キーでハッシュを作成し、ハッシュ値に従って対応するストレージノードを選択します。
• 範囲：範囲をキーで除算します。ここで、シリアルキーのセグメントがノードに格納されます。

TiKVは、Key-Valueスペース全体を一連の連続するKeyセグメントに分割する2番目のソリューションを選択します。各セグメントはリージョンと呼ばれます。データを保存する各リージョンにはサイズ制限があります（デフォルト値は96 MBで、サイズを構成できます）。各リージョンは、左閉と右開の間隔である[StartKey, EndKey)で表すことができます。

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

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

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

• まず、データはキーに従って多くのリージョンに分割され、各リージョンのデータは1つのノードにのみ保存されます（複数のレプリカは無視されます）。 TiDBシステムには、クラスタのすべてのノードにリージョンをできるだけ均等に分散させるPDコンポーネントがあります。このようにして、一方で、ストレージ容量は水平方向にスケーリングされます（他のノードのリージョンは、新しく追加されたノードに自動的にスケジュールされます）。一方、負荷分散は実現されます（1つのノードに大量のデータがあり、他のノードにはほとんどデータがないという状況は発生しません）。

  同時に、上位クライアントが必要なデータにアクセスできるようにするために、システムには、ノード上のリージョンの分布、つまりキーの正確なリージョンとキーの正確なリージョンを記録するコンポーネント（PD）があります。任意のキーを介して配置されたそのリージョンのノード。

• 2番目のタスクでは、TiKVはリージョン内のデータを複製します。つまり、1つのリージョン内のデータには、「レプリカ」という名前の複数のレプリカがあります。リージョンの複数のレプリカが異なるノードに保存されてRaftグループを形成します。ラフトグループは、Raftアルゴリズムによって一貫性が保たれます。

  レプリカの1つはグループのリーダーとして機能し、もう1つはフォロワーとして機能します。デフォルトでは、すべての読み取りと書き込みはリーダーを介して処理され、読み取りが行われ、書き込みがフォロワーに複製されます。次の図は、 リージョンとRaftグループの全体像を示しています。

リージョンでデータを分散および複製すると、ある程度のディザスタリカバリ機能を備えた分散キーバリューシステムが実現します。容量や、ディスク障害やデータ損失について心配する必要はもうありません。

MVCC

多くのデータベースはマルチバージョン同時実行制御（MVCC）を実装しており、TiKVも例外ではありません。 2つのクライアントが同時にキーの値を変更する状況を想像してみてください。 MVCCがない場合、データをロックする必要があります。分散シナリオでは、パフォーマンスとデッドロックの問題が発生する可能性があります。 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がBigTableで使用しているモデルを採用しています： パーコレーター 。 TiKVの実装は、多くの最適化を行ったこのペーパーに触発されています。詳細については、 取引概要を参照してください。