TiDB論文からNoSQLとの違いを読み解いてみる

# はじめに

- 特に深い意味のないポエムです
- 内容に誤りや偏りが含まれている可能性があるので、内容を鵜呑みにしないようお願いします

# 次の論文から見るTiDB(NewSQL)の特徴について

次の論文を読んで個人的にTiDBの特徴だと感じたところを列挙し、DynamoDBと比較してみます。

[TiDB: A Raft-based HTAP Database](https://www.vldb.org/pvldb/vol13/p3072-huang.pdf)

## 思っていたよりもRDBである

NoSQLDB(DynamoDB)ではレイテンシーやコスト削減、あるいは可用性向上のために非同期化、並列化、ネットワークのRTTの削減、単純化が行われているような処理に関しても、複数ノードを跨ぐもののなるべくRDBとの互換性を維持するように実装されているようです。

### プロトコル

TiDBはMySQLプロトコルとの互換性を維持しており、BEGIN -> ReadやWriteの自由な実行 -> COMMIT/ROLLBACKと通常のMySQLと同じようにトランザクションを実行可能です。
悲観的ロック、楽観的ロックの双方をサポートしていますが、デフォルトでは悲観的ロックのようです。
[TiDB Pessimistic Transaction Mode
](https://docs.pingcap.com/tidb/stable/pessimistic-transaction)

一方でDynamoDBはRDBとの互換性はなく、トランザクション処理は1回のリクエストでWrite/Readを実行することでネットワークのRTTを削減し、レイテンシー削減のために各更新、取得は並列化をおこないます。加えて楽観的ロックのみとしていることがわかります。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
| クライアントの互換性 | MySQLクライアントとの互換性あり  | 既存のDBMSのクライアントとの互換性なし(AWS SDK) |
| トランザクションの扱い | 通常のRDBと同じようにシーケンシャルに BEGIN -> Read/Write -> COMMIT/ROLLBACKを実施、悲観的ロック、楽観的ロックの双方をサポート  | Red/Writeが1ショット(1ネットワークのRT)で実行、各更新、取得処理が並列に実行され、楽観的ロックのみ |

### クエリ・モデル、データ・モデル

TiDBはMySQLのクエリ・モデル、データ・モデルと互換性があり、複数のノードを跨ぐジョインや集計も実施可能です。
RDBと同じようにクエリの実行時にRBOとCBOにより最適な実行計画を生成しているようです。
スキーマについても従来RDBのように維持管理する仕組みが実装されています。

一方でDynamoDBではKVSのAPIと実行される操作が一対一で対応していることからそもそも実行計画の概念が登場しません。
また、スケーラビリティを優先してジョインや集計処理はスコープの対象外とし各操作はバッチやトランザクション、Scanなどを除き、1パーティションで閉じる操作に制限しています。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
| 対応しているクエリ・モデル | MySQL互換のSQL | 独自KVS API, PartiQL(ジョインや集計をサポートしないSQLのサブセット) |
| クエリの実行方式 | RBO + CBOにより実行計画を生成  | APIと実行される操作が一対一で対応、PartiQLも従来操作への1:1のマッピング |
| スキーマ | RDBと同じようにスキーマを定義、維持 | プライマリー・キー以外のスキーマは存在しない |

### データの整合性

はじめに、どちらも単一リージョン(パーティション)に対する更新や取得処理では強整合性をサポートしています。

TiDBの場合、インデックスの更新やFollowerの参照時にも強整合性を維持し、MVCCをサポートしています。
また、組み込みでOLAPのためのTiFlashをサポートしており、また読み取り時にTiKVとの整合性を維持します。

一方でDynamoDBのインデックスおよびFollowerからの参照時はミリ秒単位の遅延を許容する代わりにネットワークのRTTの削減、可用性の向上を優先しています。
MVCCについてもストレージのコスト削減を優先しサポートしていません。
分析クエリの実行のスコープの対象外とし、他のサービスに任せています。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
|  インデックスの扱い | インデックスはrow idを保存し、通常のRDBのようにrow id -> 行データの二回の参照を実施、同期更新  |  実質別テーブル扱い(元のテーブルは参照にいかない)、非同期更新 |
| トランザクションIDの採番方法 | Timestamp Oracle経由で一貫性のある採番 | Transaction Coordinator、もしくはSNがローカル・クロックで採番 ※採用しているプロトコルは時刻のズレの発生を許容 |
| 読み取り時の一貫性 | MVCCをサポートし、snapshot-isolation, Repeatable Readをサポート、non-blocking read | MVCCをサポートしない、複数アイテムを跨ぐ一貫性のある読み取り操作はTransactGetItemsのみ(Serializableかつ書き込みと競合) |
| 単一ノードに対する処理の整合性 | 強整合性をサポート | 強整合性をサポート |
| 同一リージョン(パーティション)に対する読み取り処理のスケーリング(Followerからの参照) | Follower Read(read indexのみをLeaderで確認し読み取り処理はFollowerで実施、強整合性を維持) | Eventual Consistent Read(ミリ秒単位の遅延を許容して最新でないデータを返す) |
| 分析クエリの実行 | TiFlashをLearnerとしてraft groupへ追加、TiSparkの提供。TiFlashは特に意識せずとも実行計画次第で自動的に参照、TiFlashは読み取り時にTiKVとの強整合性を維持 | ネイティブでサポートせず、Zero-ETL、S3へのエクスポート等で外部サービスで対応、OLTPからOLAPへの反映の遅延が発生 |

### ノードの冗長化

TiDBのリージョン(他のDBで言うところのパーティションやシャード等)は3ノードで構築され、Raftアルゴリズムで合意形成が行われます。

DynamoDBの場合、パーティション内のノード数は3つで固定であり、Paxosアルゴリズムで合意形成が行われます。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
| 合意形成アルゴリズム  | Raft  | Paxos |
| 1パーティション内のノード数 | デフォルトで3、変更可能 | 3 |

### 物理配置

TiDBでは恐らくおそらくレンジ・スキャンのためにrange partitionを採用しています。
一方でDynamoDBは負荷の分散を優先してハッシュで分散しています。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
|パーティショニングのストラテジー| おそらくレンジ・スキャンのためにrange partition strategyを採用 | ハッシュで分散※同一パーティション内のデータはソートキーでソート可能 |

## TiFlashはなるべくOLTPに影響を与えないように、かつ透過的に利用される

これはNewSQLというよりもTiDBの特徴だと思われますが、TiFlashにてcolumnar形式のストレージを作成可能です。
更新は非同期かつ読み取り時にはmerge on read方式でなるべくOLTP処理に影響をあたえず、かつOLTPの更新量に追いつけるように意図しているようです。
また、OLTP用のTiKVとの強整合性が維持され、実行計画次第で透過的な利用が行われるようです。

## 論文中の検証でのスループットはOLTPで数千QPS程度

論文中の検証でのスループットはOLTPで数千QPS程度のようです。
ただし、2023年にはこういった事例が発表されているようなので、100万QPS超のスループットは実績として存在するようです。
[Scaling TiDB To 1 Million QPS](https://blog.flipkart.tech/scaling-tidb-to-1-million-qps-d556aa6a16ef)

## 考察

両者の違いは、以下のような設計目標、設計思想に基づくものだと考えられます。
どちらが良い、悪いというものではなく目標としているものが根本的に異なると考えられます。

|  | TiDB | DynamoDB |
|:-:|:-:|:-:|
|  設計目標 | MySQLの振る舞い、プロトコルを維持しながら、その範囲でスケーラビリティを改善する、他のサービスへの連携なしに分析処理もサポートする | できる限り低レイテンシー、低コスト化しつつ、スケーラビリティを阻害する要素（ジョインや集計のサポート等）は極力排除する、RDBとの互換性は求めない |
| 適していると思われるユースケース | MySQLを利用しているシステムをそのまま移行して水平スケーラビリティを向上させたい | 成長し続ける水平分散可能なワークロードを安定したレイテンシーで捌きたい |

また、機能比較より一部界隈ではNewSQLの特徴とされる分散合意形成アルゴリズムの採用や更新やデータ取得時の強整合性の提供、分散トランザクションの実行などもNoSQLの製品によってはサポートされていることもわかります。

## 最後に

思っていた以上に違いが大きいことから両製品は異なるユースケースを想定して開発されており、あまり直接比較するような対象ではないのではないでしょうか。
また、どうしてもネットワークのRTが複数回発生しクエリのレイテンシーが増加することから、通常のMySQLをあらゆるユースケースで直接置き換えることを想定しているわけでもないように思えました。

## 参考文献

- [TiDB: A Raft-based HTAP Database](https://www.vldb.org/pvldb/vol13/p3072-huang.pdf)
- [Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service](https://www.usenix.org/system/files/atc22-elhemali.pdf)
- [Distributed Transactions at Scale in Amazon DynamoDB](https://www.usenix.org/system/files/atc23-idziorek.pdf)