初心者に向けるTiDBの学習 ～コンピューティング編 第1回～

## 初心者に向けるTiDBの学習メニュー
[初心者に向けるTiDBの学習 ～ストレージ編 第1回～] (https://qiita.com/it2911/items/a676bb6a63b07e865558)
[初心者に向けるTiDBの学習 ～ストレージ編 第2回～](https://qiita.com/it2911/items/8050f76eba36f6dc7a25)
[初心者に向けるTiDBの学習 ～ストレージ編 第3回～](https://qiita.com/it2911/items/054e7a05764753964059)
[初心者に向けるTiDBの学習 ～コンピューティング編 第1回～](https://qiita.com/it2911/items/0dc6ef5e351b4e7379c5)  <- 今ここ
[初心者に向けるTiDBの学習 ～コンピューティング編 第2回～](
https://qiita.com/it2911/items/0819844669fe12b3d6b2)
[初心者に向けるTiDBの学習 ～スケジューリング編～](
https://qiita.com/it2911/items/0a5e9b4c4f0eee846ba7)

![shutterstock_652948648.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/197234/912e493b-6727-728d-26f6-3d1254eb3a87.jpeg)

前回の[初心者に向けるTiDBの学習 ストレージ編](https://qiita.com/it2911/items/a676bb6a63b07e865558)では、TiDBがデータを保存する方法を紹介しました。（これはTiKVの基本概念でもあります。）今回は、TiDBがどのようにボトムレイヤーのKey-Valueにデータを格納し、リレーショナルモデルをKey-Valueモデルにマッピングし、SQLを行うのか、について詳しく説明します。

リレーショナルモデルとKey-Valueモデルのマッピング
---

リレーショナルモデルを単純化して、単純なテーブルとSQL文だけについて考えてみましょう。考えなければならないのは、テーブルデータの格納とSQL文の実行をKey-Value上でどのように行っているかです。以下のようなテーブルを考えます。

```
CREATE TABLE User {...
    ID int,
    Name varchar(20),
    Role varchar(20),
    Age int,
    PRIMARY KEY (ID),
    Key idxAge (age)
};
```

通常のSQLデータベースとKey-Valueの構造には大きな違いがあるため、いかにしてSQLデータベースをKey-Valueにマッピングするかが重要になります。この記事ではまず、どのマッピングソリューションが良いかどうかを判断するために、データ保存の仕方の特徴について説明します。

テーブルには、3つのデータが含まれています。（ただし、この記事ではメタデータについては触れません。）

  1. テーブルに関するメタデータ
  2. テーブルの行数
  3. インデックスデータ

データは、行単位でも列単位でも保存することができ、どちらにも利点と欠点があります。TiDBの主な目的はオンライントランザクション処理（OLTP）であり、データの行の読み取り、保存、更新、削除を迅速に行うことを目標としているため、行ストアの方が良いと思われます。

TiDBは、Primary IndexとSecondary Indexの両方をサポートしています。インデックスの機能は、クエリの高速化、高いクエリ性能、および制約のためのものです。クエリには2つの形式があります。

- ポイントクエリ：`select name from user where id=1;` のように、主キーやユニークキーなどの同等の条件を用いて、インデックスを介してデータの特定の行を探します。
- レンジクエリ：例えば `select name from user where age > 30 and age < 35;`のように、`idxAge`を使用して年齢が 30 から 35 の間にあるデータを照会します。インデックスには Unique Index と Non-unique Index の 2 種類ありますが、TiDBではその両方ともサポートしています。

保存するデータの特徴を分析した後は、Insert/Update/Delete/Select文など、データを操作するために必要なことに移りましょう。

- **Insert**ステートメント: 行データをKey-Valueに書き込み、インデックスデータを作成します。
- **Update**ステートメント: 必要に応じて行データとインデックスのデータを更新します。
- **Delete**ステートメント: 行データとインデックスの両方を削除します。
- **Select**ステートメント: この4つの中で最も複雑な状況を扱います。
  - データの行を簡単かつ迅速に読み取ります。（この場合、各行にはID（明示的または暗黙的に）が必要です。）
  - `Select * from user;`というように、複数の行のデータを連続して読み取ります。
  - インデックスを使ってデータを読み込み、PointクエリやRangeクエリでインデックスを活用します。

**グローバルに分散され、並び変えられたKey-Valueエンジン**は、上記の操作の要件を満たします。グローバルで並び変えられているという特徴は、かなり多くの問題を解決するのに役立ちます。以下を2つの例として考えてみましょう。

- データの行の素早い取得: 単一または複数のキーを作成できると仮定して、この行を探すときには、TiKVが提供するSeekメソッドを使って、このデータの行を素早く探し出すことができます。
- テーブル全体のスキャン: テーブルをKeyのRangeにマッピングできる場合は、StartKeyからEndKeyまでスキャンすることで、すべてのデータを取得することができます。インデックスデータを操作する方法も同様です。

それでは、これがTiDBでどのように機能するかを見てみましょう。

TiDBは、各テーブルに`TableID`を、各インデックスに`IndexID`を、各行に`RowID`を割り当てます。テーブルに整数の主キーがある場合には、その値が`RowID`として使用されます。`TableID`はクラスタ全体で一意であり、`IndexID/RowID`はテーブル内で一意です。これらのIDはすべて int64 です。

各行のデータは、以下のルールに従ってKey-Valueペアにエンコードされます。

```
Key: tablePrefix{tableID}_recordPrefixSep{rowID}
Value: [col1, col2, col3, col4]
```

Keyの`tablePrefix/recordPrefixSep`は、特定の文字列定数であり、Key-Value空間で他のデータを区別するために使用されます。インデックスデータは、以下のルールに従って、Key-Valueペアにエンコードされます。

```
Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: rowID
```

上記のエンコーディングルールは、Unique Indexには適用されますが、Non-Unique IndexではUnique Keyを作成することはできません。その理由は、インデックスの`tablePrefix{tableID}_indexPrefixSep{indexID}`が同じであるためです。また、複数の行の`ColumnsValue`も同じである可能性があります。そこで、Non-unique Indexをエンコードするために、いくつかの変更を行いました。

```
Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID
Value: null
```

このようにして、各行のデータに一意のキーを作成することができます。

上記のルールでは、キーの`xxPrefix`はすべて文字列定数であり、異なるタイプのデータ間の衝突を避けるために、名前空間を区別する機能を持っています。

```
var(
    tablePrefix     = []byte{'t'}
    recordPrefixSep = []byte("_r")
    indexPrefixSep  = []byte("_i")
)
```

行とインデックスのどちらのキーエンコードソリューションも同じ接頭辞を持つことに注意してください。具体的には、テーブルのすべての行は同じ接頭辞を持ち、インデックスのデータも同じ接頭辞を持ちます。これらの同じ接頭辞を持つデータは、TiKVのキー空間にまとめて配置されます。言い換えれば、接尾辞の符号化方法を慎重に設計し、比較関係が変化しないようにすれば、行やインデックスのデータが整然とTiKVに格納されることになります。このように、エンコードの前後で比較関係が変化しないことを**Memcomparable**といいます。どのような値であっても、エンコード前の2つのオブジェクトの比較結果は、エンコード後のバイト配列の比較結果と一致します（注：TiKVのキーとバリューは共にプリミティブなバイト配列です）。より詳細な情報は、TiDBのコーデックパッケージを参照してください。このエンコード方法を採用した場合、テーブルのすべての行データは、RowIDの順序に従ってTiKVのキー空間に配置されます。また、特定のインデックスのデータも、インデックスのColumnValue順に配置されます。

ここで、これまでの要件とTiDBのマッピングソリューションを考慮し、ソリューションの実現性を検証します。

1. まず、マッピングソリューションを介して行とインデックスのデータをKey-Valueデータに変換し、各行と各インデックスデータがユニークなキーを持っていることを確認します。
2. 次に、PointクエリとRangeクエリの両方に対応しているため、このマッピングソリューションを使用して、ある行やインデックスの一部に対応するキーを簡単に作成することができます。
3. 最後に、テーブルにいくつかの制約を確保する場合、対応する制約が満たされているかどうかを判断するために、特定のキーを作成し、そのキーの存在を確認することができます。

ここまでで、テーブルをKey-Valueにマッピングする方法を説明しました。

次に、同じテーブル構造を持つもうひとつのケースを紹介します。テーブルには3行のデータがあるとします。

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

まず、データの各行がKey-Valueのペアとしてマッピングされます。このテーブルにはIntの主キーがあるので、RowIDの値はこの主キーの値となります。このテーブルのTableIDが10で、その行データが以下であるとします: 

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

このテーブルには、主キーの他にインデックスがあります。インデックスのIDは1で、そのデータは以下であるとします:

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

前述のエンコーディングルールは、上記の例を理解するのに役立ちます。私たちがこのマッピングソリューションを選んだ理由とその目的を理解していただければ幸いです。

---

今回はコンピューティングのリレーショナルモデルとKey-Valueモデルのマッピングを紹介しました。次回、[初心者に向けるTiDBの学習 ～コンピューティング編 第2回～](https://qiita.com/it2911/items/0819844669fe12b3d6b2)**メタデータ管理**及び**SQLの実現方法**を紹介させていただきます。