TiDBコンピューティング

TiKVが提供する分散storageをベースに、TiDBは優れたトランザクション処理能力とデータ分析能力を兼ね備えたコンピューティングエンジンを構築します。このドキュメントでは、まずTiDBデータベーステーブルのデータをTiKVの(キー、値)キーバリューペアにマッピングするデータマッピングアルゴリズムを紹介し、次にTiDBがメタデータを管理する仕組みを紹介し、最後にTiDB SQLレイヤーのアーキテクチャを説明します。

コンピューティングレイヤーが依存するstorageソリューションについては、本ドキュメントではTiKVの行ベースのstorage構造のみを紹介します。OLAPサービスについては、TiDBはTiKVの拡張機能として列ベースのstorageソリューションTiFlash導入しています。

テーブルデータをキー値にマッピングする

このセクションでは、TiDBにおけるキーと値のペア（キー、値）へのデータのマッピング方法について説明します。ここでマッピングされるデータには、以下の2つの種類が含まれます。

テーブル内の各行のデータ（以下、テーブルデータと呼びます）。
テーブル内のすべてのインデックスのデータ（以下、インデックスデータと呼びます）。

テーブルデータとキー値とのマッピング

リレーショナルデータベースでは、テーブルに多数の列が含まれる場合があります。行内の各列のデータを（キー、値）キーと値のペアにマッピングするには、キーの構築方法を検討する必要があります。まず、OLTPシナリオでは、単一行または複数行のデータの追加、削除、変更、検索などの操作が多数発生するため、データベースはデータ行を迅速に読み取る必要があります。そのため、各キーには、キーを迅速に見つけられるように、明示的または暗黙的な一意のIDが必要です。また、多くのOLAPクエリでは、テーブル全体のスキャンが必要です。テーブル内のすべての行のキーを範囲にエンコードできれば、範囲クエリによってテーブル全体を効率的にスキャンできます。

上記の考慮事項に基づいて、TiDB のテーブルデータと Key-Value のマッピングは次のように設計されます。

同じテーブルのデータがまとめて保存され、簡単に検索できるように、TiDB は各テーブルにテーブル ID を割り当てます。テーブル ID はTableIDで表されます。テーブル ID はクラスター全体で一意の整数です。
TiDBは、テーブル内の各データ行に行ID（ RowIDで表されます）を割り当てます。行IDも整数で、テーブル内で一意です。行IDに関しては、TiDBは小さな最適化を行っています。テーブルに整数型の主キーがある場合、TiDBはこの主キーの値を行IDとして使用します。

各データ行は、次の規則に従って (キー、値) キーと値のペアとしてエンコードされます。

Key:   tablePrefix{TableID}_recordPrefixSep{RowID}
Value: [col1, col2, col3, col4]

tablePrefixとrecordPrefixSepどちらも、キー空間内の他のデータを区別するために使用される特別な文字列定数です。これらの文字列定数の正確な値はマッピング関係の概要で紹介されています。

インデックスデータのキー値へのマッピング

TiDBは、主キーとセカンダリインデックス（一意のインデックスと一意でないインデックスの両方）の両方をサポートしています。テーブルデータのマッピングスキームと同様に、TiDBはテーブルの各インデックスにインデックスID（ IndexIDを割り当てます。

主キーと一意のインデックスの場合、キーと値のペアに基づいて対応するRowIDすばやく見つける必要があるため、このようなキーと値のペアは次のようにエンコードされます。

Key:   tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: RowID

一意性制約を満たす必要のない通常のセカンダリインデックスでは、1つのキーが複数の行に対応する場合があります。キーの範囲に応じて対応する行をRowIDクエリする必要があります。したがって、キーと値のペアは以下の規則に従ってエンコードする必要があります。

Key:   tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}
Value: null

マッピング関係の概要

上記のすべてのエンコード規則のtablePrefix 、 recordPrefixSep 、およびindexPrefixSep 、KV をキー空間内の他のデータと区別するために使用される文字列定数であり、次のように定義されます。

tablePrefix     = []byte{'t'}
recordPrefixSep = []byte{'r'}
indexPrefixSep  = []byte{'i'}

また、上記のエンコード方式では、テーブルデータやインデックスデータのキーエンコード方式に関係なく、テーブル内のすべての行は同じキープレフィックスを持ち、インデックスのすべてのデータも同じプレフィックスを持つことに注意してください。同じプレフィックスを持つデータは、TiKVのキー空間に一緒に配置されます。したがって、サフィックス部分のエンコード方式を注意深く設計し、エンコード前とエンコード後の比較が同じになるようにすることで、テーブルデータまたはインデックスデータをTiKVに順序どおりに格納できます。このエンコード方式を使用すると、テーブル内のすべての行データはTiKVのキー空間でRowIDずつ整然と並べられ、特定のインデックスのデータもインデックスデータの特定の値に従ってキー空間に順番に配置されます（ indexedColumnsValue ）。

キーと値のマッピング関係の例

このセクションでは、TiDBのキーと値のマッピング関係を理解するための簡単な例を示します。TiDBに次のテーブルが存在するとします。

CREATE TABLE User (
     ID int,
     Name varchar(20),
     Role varchar(20),
     Age int,
     PRIMARY KEY (ID),
     KEY idxAge (Age)
);

テーブルに 3 行のデータがあるとします。

1, "TiDB", "SQL Layer", 10
2, "TiKV", "KV Engine", 20
3, "PD", "Manager", 30

各データ行は (Key, Value) のキーと値のペアにマッピングされており、テーブルにはint型の主キーがあるため、値RowIDはこの主キーの値です。テーブルのTableID 10であるとすると、TiKV に保存されているテーブルデータは次のようになります。

t10_r1 --> ["TiDB", "SQL  Layer", 10]
t10_r2 --> ["TiKV", "KV  Engine", 20]
t10_r3 --> ["PD", " Manager", 30]

このテーブルには、主キーに加えて、一意ではない通常のセカンダリインデックスidxAgeあります。3 IndexID 1であるとすると、TiKV に保存されるインデックスデータは次のようになります。

t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

上記の例は、TiDB のリレーショナルモデルからキー値モデルへのマッピングルールと、このマッピングスキームの背後にある考慮事項を示しています。

メタデータ管理

TiDBの各データベースとテーブルには、その定義と様々な属性を示すメタデータが保持されます。この情報も永続化する必要があり、TiDBはTiKVにもこの情報を保存します。

各データベースまたはテーブルには、一意のIDが割り当てられます。テーブルデータがKey-Valueにエンコードされる際、このIDは一意の識別子として、Keyにm_プレフィックスを付けてエンコードされます。これにより、シリアル化されたメタデータが格納されたKey-Valueペアが構築されます。

さらに、TiDB は専用の (Key, Value) キーと値のペアを使用して、すべてのテーブルの構造情報の最新のバージョン番号を保存します。このキーと値のペアはグローバルであり、DDL 操作の状態が変化するたびにバージョン番号が1ずつ増加します。TiDB は、このキーと値のペアをキー/tidb/ddl/global_schema_versionで PDサーバーに永続的に保存し、値はint64型のバージョン番号値です。一方、TiDB はスキーマ変更をオンラインで適用するため、PDサーバーに保存されているテーブル構造情報のバージョン番号が変更されるかどうかを常にチェックするバックグラウンドスレッドを維持します。このスレッドにより、バージョンの変更が一定期間内に取得されることも保証されます。

SQLレイヤーの概要

TiDB の SQLレイヤーTiDB サーバーは、SQL ステートメントをキー値操作に変換し、その操作を分散キー値storageレイヤーである TiKV に転送し、TiKV によって返された結果を組み立てて、最終的にクエリ結果をクライアントに返します。

このレイヤーのノードはステートレスです。これらのノード自体はデータを保存せず、完全に同等です。

SQLコンピューティング

SQL コンピューティングの最もシンプルなソリューションは、前のセクションで説明したテーブルデータとキー値とのマッピングです。これは、SQL クエリを KV クエリにマッピングし、KV インターフェイスを介して対応するデータを取得し、さまざまな計算を実行します。

例えば、SQL文select count(*) from user where name = "TiDB"を実行するには、TiDBはテーブル内のすべてのデータを読み取り、フィールドnameがTiDBかどうかを確認し、5であればその行を返します。このプロセスは以下のとおりです。

キー範囲を構築します。表内のすべてのRowID [0, MaxInt64)範囲に含まれます。行データのKeyエンコード規則に従って、 0とMaxInt64使用すると、左閉じ、右開きの[StartKey, EndKey)範囲を構築できます。
キー範囲のスキャン: 上記で構築されたキー範囲に従って TiKV 内のデータを読み取ります。
データのフィルタリング：読み込んだデータ行ごとに、式name = "TiDB"を計算します。結果がtrue場合は、この行に戻ります。そうでない場合は、この行をスキップします。
Count(*)計算します。要件を満たす行ごとに、 Count(*)の結果を合計します。

全体のプロセスは次のように示されます。

naive sql flow

このソリューションは直感的で実現可能ですが、分散データベースのシナリオでは明らかな問題がいくつかあります。

データがスキャンされる際、各行は少なくとも 1 つの RPC オーバーヘッドを伴う KV 操作を介して TiKV から読み取られます。スキャンするデータの量が多い場合、このオーバーヘッドは非常に高くなる可能性があります。
すべての行に適用されるわけではありません。条件を満たさないデータは読み取る必要はありません。
このクエリの返された結果では、要件に一致する行の数だけが必要であり、それらの行の値は必要ではありません。

分散SQL操作

上記の問題を解決するには、RPC呼び出しの大量発生を回避するため、計算処理をstorageノードにできるだけ近づける必要があります。まず、SQL述語条件name = "TiDB"計算処理のためにstorageノードにプッシュダウンし、有効な行のみを返すようにすることで、無駄なネットワーク転送を回避します。次に、集計関数Count(*)もstorageノードにプッシュダウンして事前集計を行い、各ノードはCount(*)の結果のみを返すようにすれば済みます。SQLレイヤーは、各ノードから返されたCount(*)結果を合計します。

次の画像は、データがレイヤーレイヤーに返される様子を示しています。

dist sql flow

SQLレイヤーのアーキテクチャ

前のセクションではSQLレイヤーのいくつかの関数を紹介しました。SQL文がどのように処理されるかについては、基本的な理解が得られたかと思います。実際には、TiDBのSQLレイヤーは多くのモジュールと層で構成されており、はるかに複雑です。次の図は、重要なモジュールと呼び出し関係を示しています。

tidb sql layer

ユーザーのSQLリクエストは、直接またはLoad Balancerを介してTiDBサーバーに送信されます。TiDBサーバーはMySQL Protocol Packet解析し、リクエストの内容を取得し、SQLリクエストを構文的および意味的に解析し、クエリプランを開発・最適化し、クエリプランを実行し、データを取得して処理します。すべてのデータはTiKVクラスターに保存されるため、このプロセスではTiDBサーバーはTiKVと対話してデータを取得する必要があります。最後に、TiDBサーバーはクエリ結果をユーザーに返す必要があります。