TiDBストレージ

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

キーと値のペア

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

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

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

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

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

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

いかだプロトコル

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

簡単な方法は、データを複数のマシンに複製することです。これにより、1つのマシンに障害が発生した場合でも、他のマシンのレプリカを引き続き使用できます。つまり、信頼性が高く、効率的で、失敗したレプリカの状況を処理できるデータレプリケーションスキームが必要です。これらはすべて、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つの重要なタスクを実行します。

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

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

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

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

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

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

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

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
……

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

分散ACIDトランザクション

TiKVのトランザクションは、BigTableでGoogleが使用するモデルを採用しています： パーコレーター 。 TiKVの実装は、多くの最適化を加えたこのペーパーに触発されています。詳細については、 取引概要を参照してください。