初心者に向けるTiDBの学習メニュー

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

スケジューリングをする理由

初心者に向けるTiDBの学習～ストレージ編～では、TiKVクラスタがTiDBデータベースの分散KVストレージエンジンであることが紹介されています。データはリージョンに複製された上で管理されます。各リージョンには異なるTiKVノードに分散した複数のレプリカがあります。これらのレプリカのうち、リーダーは読み取り／書き込みを担当し、フォロワーはリーダーから送られてきたRaftログを同期します。では、以下の質問について考えてみてください。

同じリージョンの複数のレプリカが異なるノードに分散していることを保証するには、どうしたらよいでしょうか？また、1台のマシンで複数のTiKVインスタンスを起動すると、どうなるでしょうか？
TiKVクラスタがディザスタリカバリに備えて複数の場所に展開されている場合、1つのデータセンターに障害が発生しても、Raftグループの複数のレプリカが失われないようにするには、どうしたらよいでしょうか？
TiKVクラスタの他のノードのデータを新しく追加されたノードに移動するには、どうしたらよいでしょうか？
ノードが故障したらどうしますか？クラスタ全体で何をする必要がありますか？ノードに一時的な障害が発生した場合（例：サービスの再起動）、どのように対処したらよいですか？長時間の障害（例：ディスク障害やデータの損失）の場合はどうですか？
各RaftグループがN個のレプリカを持つ必要があるとします。1つのRaftグループで、レプリカが足りない可能性（例：ノードが故障してレプリカが消失した場合）や、レプリカが多すぎる可能性（例：一度故障したノードが再稼働して自動的にクラスタに加わった場合）があります。どのようにして複製数を設定するのですか？
読み取り／書き込みはリーダーが行いますが、すべてのリーダーが数台のノードに集まった場合、クラスタはどうなるのでしょうか？
すべてのリージョンにアクセスする必要はなく、ホットスポットはいくつかのリージョンに存在していると思われます。この場合、どうすればいいのでしょうか？
クラスタは、ロードバランシングの過程でデータを移行する必要があります。このようなデータ移行は、ネットワーク帯域、ディスクIO、CPUをかなり消費しますが、オンラインサービスに影響を与えるのではありませんか？

上記の問題の1つ1つを解くのは簡単ですが、組み合わさると難しくなります。例えば、レプリカを追加するかどうかは数が足りているかどうかで判断するなど、1つのRaftグループの内部状況を考えればよい問題もあるようです。しかし、実際には、このレプリカをどこに追加するかには、包括的な視点が必要です。システム全体はダイナミックに変化しています。リージョンの分割、ノードの結合、ノードの故障、ホットスポットへのアクセスの変更などが常に発生しています。スケジューリングシステムもまた、最良の状態に向けて調整され続ける必要があります。全体的な情報を把握し、スケジューリングし、設定できるコンポーネントがなければ、これらのニーズを満たすのは難しいでしょう。そのため、システム全体の状況を制御・調整する中央ノードが必要となります。そこで登場したのがPlacement Driver（PD）モジュールです。

スケジューリングの要件

先に挙げた質問を分類して整理したいと思います。大きく分けて、2種類あります。

分散型で可用性の高いストレージシステムは、以下の要件を満たす必要があります。

適切な数のレプリカの作成
レプリカの別のマシンへの分散
他のノードのレプリカを、ノードを追加した後に移行可能
ノードのオフライン時の、そのノード上のデータ移行

優れた分散システムには、以下のような最適化が必要です。

クラスタ内のリーダーのバランスのとれた配置
各ノードのストレージ容量のバランスのとれた配置
ホットスポットへのアクセスのバランスがとれた配分
オンラインサービスに影響を与えないようなバランシングの速度の制御
手動でノードのオンライン／オフラインを切り替えたり、障害のあるノードを自動的にオフラインにするといったノード状態の管理

第1の要件を満たす場合、システムは複数のレプリカのディザスタリカバリ、ダイナミックスケーラビリティ、ノード障害の耐性、自動ディザスタリカバリをサポートしています。また、第2の要件を満たせば、システムの負荷のバランスがよくなり、管理が容易になります。

これらの要件を満たすためには、まず、各ノードの状態、各Raftグループの情報、ビジネスへのアクセスやオペレーションの統計といった情報を十分に収集する必要があります。そして、PDがこれらの情報やスケジューリングポリシーに基づいて、上記の要求を満たすスケジューリング計画を立てるよう、ポリシーを設定する必要があります。

スケジューリングの基本的なオペレーション

スケジューリングの基本的なオペレーションはとてもシンプルです。言い換えれば、スケジューリングポリシーに沿ってできることです。これがスケジューラ全体の本質です。

上述のスケジューラの要求は複雑に見えますが、3つのオペレーションに大別できます。

レプリカの追加
レプリカの削除
Raftグループの異なるレプリカ間でのリーダーの役割の移行

Raftプロトコルは、偶然これらの要件を満たしており、AddReplica、RemoveReplica、TransferLeaderの各コマンドは、これら3つの基本的なオペレーションをサポートしています。

情報収集

スケジューリングは、クラスタ全体の情報収集に依存します。簡単に言えば、各TiKVノードと各リージョンの状態を知る必要があるのです。TiKVクラスタは、2種類の情報をPDに報告します。

各TiKVノードは、ノード全体の情報をPDに定期的に報告します。

TiKVストアとPDの間にはハートビートがあります。PDはハートビートで各データストアがアクティブかどうか、また新しく追加されたデータストアがあるかどうかを確認します。一方、ハートビートには、そのデータストアの状態情報が含まれています。主に以下のようなものです。

総ディスク容量
空きディスクの容量
リージョンの数
データの書き込み速度
送受信したスナップショットの数（レプリカはスナップショットでデータを同期します）
オーバーロードしていないか
ラベル情報（ラベルとは、上下関係のある一連のタグです）

各RaftグループのリーダーのPDへの定期的な報告

各RaftグループのリーダーとPDはハートビートで結ばれており、このリージョンの状態を以下のように報告します。

リーダーの地位
フォロワーの位置
オフラインのレプリカの数
データの読み取り／書き込み速度

この2種類のハートビートを通じて、PDはクラスタ全体の情報を収集し、判断します。さらに、PDは管理インターフェースを介して追加情報を得ることで、より正確な判断を下します。例えば、データストアのハートビートが中断された場合、PDにはそれが一時的なものなのか恒久的なものなのかがわかりません。PDは一定時間（デフォルトでは30分）しか待つことができません。それでもハートビートがない場合、PDはそのデータストアがオフラインになったと判断し、そのデータストア上のすべてのリージョンを移動させる必要があります。しかし、オペレーションスタッフが手動でマシンをオフラインにした場合は、そのスタッフが管理インターフェースを通じてPDにデータストアが利用できないことを伝える必要があります。この場合、PDはデータストア上のすべてのリージョンを直ちに移動させます。

スケジューリングポリシー

情報を集めた後、具体的なスケジューリング計画を描くためには、PDにはいくつかのポリシーが必要です。

1. リージョン内のレプリカの数が正しい

PDは、リージョンリーダーのハートビートを通じて、あるリージョンのレプリカの数が必要条件を満たしていないことを発見すると、レプリカの追加／削除の操作によってレプリカの数を修正します。これは次のような場合に起こります。

ノードが故障してすべてのデータを失い、一部のリージョンでレプリカが存在しない状態になる。
故障したノードが再び機能し、自動的にクラスタに参加する。この場合、冗長なレプリカが存在することになるため、削除する必要があります。
管理者がレプリカポリシーと最大レプリカ数の設定を変更した。

2. 1つのRaftグループの複数のレプリカが同じ場所に存在してはならない

同じ場所であって、同じノードではないことに注意してください。一般的にPDが保証できるのは、ノードが故障した際に多くのレプリカが失われるという問題を避けるよう、複数のレプリカが同じノードに存在しないということだけです。実際の導入時には、次のような要件が出てくることがあります。

同一の物理マシン上に複数のノードが配置されている。
TiKVノードが複数のサーバーに分散している。サーバーの電源が落ちても、システムが利用できることを想定しています。
TiKVノードが複数のIDCに分散している。データセンターの電源が落ちても、システムはそのまま利用できます。

基本的には、共通のロケーション属性を持ち、最小の耐障害ユニットを構成するノードが必要となります。このユニットの中では、複数のリージョンレプリカが共存しないのが望ましいです。このとき、ノードにラベルを設定し、PD内のロケーションラベルを設定して、どのラベルを場所の識別子にするかを指定します。レプリカを配置する際に、複数のレプリカを格納しているノードが同じ位置識別子を持つことはありません。

3. レプリカが各データストアに均等に分散

各レプリカのデータ記憶容量は固定されているので、各ノードのレプリカ数のバランスを維持すれば、全体の負荷はよりバランスのとれたものになります。

4. リーダーの数が各データストアに均等に分散

Raftプロトコルはリーダーを介して読み取り／書き込みを行うため、計算負荷は主にリーダーにかかります。そのため、PDはリーダーを異なるデータストアに分散させて管理します。

5. ホットスポットの数が各データストアに均等に分布

情報を送る際、各データストアとリージョンリーダーは、キーの読み取り／書き込みのスピードなど、その時点のアクセス負荷の情報を伝えます。PDはホットスポットをチェックし、複数のノードに分散させます。

6. 各データストアのストレージスペースの占有率がほぼ同じ

各データストアは起動時に容量パラメータを指定しますが、これはこのデータストアのストレージスペースの限界を示します。PDはスケジューリング時にノードの残りのスペースを考慮します。

7. オンラインサービスに影響を与えないようにスケジューリングの速度を制御

スケジューリング動作は、CPU、メモリ、ディスクI/O、ネットワーク帯域を消費するため、オンラインサービスに影響を与えないようにしなければなりません。PDは進行中のオペレーションの数を制御しており、デフォルトのスピードは保守的なものになっています。スケジューリングを高速化したい場合（サービスアップグレードの停止、新しいノードの追加、できるだけ早くスケジューリングしたいなど）は、pd-ctlで、手動で高速化することができます。

8. オフラインのノードを手動でサポート

pd-ctlで、手動でノードをオフラインにする場合、PDは一定のレート制御の範囲内でノード上のデータを遠ざけます。その後、そのノードをオフラインにします。

スケジューリングの実装

では、スケジュールリングの流れを見てみましょう。

PDは、データストアやリーダーのハートビートを通して常に情報を収集することで、クラスタの詳細データを取得します。PDはこの情報とスケジューリングポリシーに基づいて動作シーケンスを作成し、リージョンリーダーから送られてくるハートビートを受信すると、このリージョンに実行すべきオペレーションがないかをチェックします。PDは、ハートビートの返信メッセージを通じて、今後実行するオペレーションをリージョンリーダーに返し、次のハートビートでその実行結果を監視します。これらのオペレーションはリージョンリーダーへの提案に過ぎず、実行が保証されているわけではありません。実行するかどうか、いつ実行するかは、リージョンリーダーがその時の状態に応じて判断します。

まとめ

このブログでは、他では得られないような情報をご紹介しました。スケジューリングのための分散型ストレージシステムを構築するために何を考慮すべきか、また、より柔軟にポリシーを拡張できるようポリシーと実装を切り離す方法について、ご理解いただけたでしょうか？
3つのブログ（ストレージ編、コンピューティング編、スケジューリング編）が、TiDBの基本的なコンセプトや実装原理を理解するのに役立つことを願っています。今後は、コードからアーキテクチャに至るまで、TiDBに関するブログをさらに増やしていきます。