TiKVトランザクションの深層に潜る。TiKV Prewrite Requestのライフストーリー

TiKV は、Google Spanner、F1、HBaseの設計をベースにした、分散Key-Valueストレージエンジンです。しかし、TiKVは分散ファイルシステムに依存しないため、よりシンプルに管理することができます。

TiKVの深層に潜るとTiKVによる読み取りと書き込みの方法で紹介したように、TiKVはGoogle Percolatorにヒントを得た2-phase commit (2PC) アルゴリズムを適用して、分散トランザクションをサポートしています。この2つのフェーズは、 Prewrite と Commit です。

本稿では、PrewriteフェーズにおけるTiKVリクエストの実行ワークフローを探り、リージョンリーダーの複数のモジュール内で楽観的トランザクションのPrewriteリクエストがどのように実行されるかについてトップダウンで説明します。この情報は、TiKVリクエストのリソース利用を明確にし、TiKVの関連するソースコードについて学ぶのに役立ちます。

ワークモデル

TiKVは初期化されると、設定に基づき様々な種類のワーカースレッドを作成します。これらのワーカースレッドが作成されると、ループ内で継続的にタスクをフェッチして実行します。これらのワーカースレッドは、一般に関連するタスクキューと対になっています。したがって、さまざまなタスクを異なるタスクキューに投入することで、いくつかの処理を非同期で実行することができます。次の図は、このワークモデルを簡単に説明したものです。

gRPC Requestフェーズ

TiKV Prewriteリクエストは、ネットワークからのgRPC prewrite requestがgRPCサーバスレッドに現れることから始まります。下図はこのフェーズのワークフローを表しています。

図を見ただけではわかりにくいかもしれませんので、以下、gRPCスレッドが何をするのか、順を追って説明します。各ステップの番号は、対応するソースコードにリンクしています。

• ステップ 1：Prewrite protobufメッセージをトランザクション層で理解可能なMutationに変換します。MutationはKeyの書き込み操作を意味します。
• ステップ 2：チャネルを作成し、チャネルの送信者を使用してgRPC Notify Callbackを構築します。
• ステップ 3：チャネルの受信者をgRPC respond taskとして構築し、gRPC task queueに投入して通知を待ちます。
• ステップ 4：gRPC notify callbackとMutationsをトランザクションタスクとして結合します。
• ステップ 5：トランザクション層のラッチを取得し、gRPC notify callbackをTransaction task slotに格納します。
• ステップ 6：トランザクション層がラッチの取得に成功すると、gRPCサーバースレッドはgRPC notify callbackのインデックスに使用できる一意なcidを持つタスクの実行を継続します。このcidは、prewriteリクエストの実行プロセスを通じてグローバルに一意なものです。 
• ステップ 7：Raftレイヤーのためのsnapshot callbackを構築します。このコールバックは、cid、Mutations、およびtransaction schedulerから構成されます。
• ステップ 8：Raft Read Indexリクエストを作成し、そのリクエストとsnapshot callbackとを組み合わせてRaftコマンドを形成します。
• ステップ 9：Raftコマンドを所属するピアに送信します。

gRPCスレッドはその役目を終えました。続きはraftstoreスレッドで行います。

Read Proposeフェーズ

このフェーズを紹介する前に、バッチシステムについてお話したいと思います。これはTiKVのmulti-raft実装の基礎となるものです。

TiKVでは、raftstoreスレッドとapplyスレッドがバッチシステムのインスタンスです。この2つのワーカースレッドも固定ループパターンで動作しており、前述のワークモデルと一致しています。

raftstoreスレッドとapplyスレッドは、ループの中で3つのフェーズ：メッセージの収集フェーズ、メッセージの処理フェーズ、およびI/Oの処理フェーズを通過します。次のセクションでは、これらのフェーズについて詳しく説明します。

さて、話を元に戻しましょう。

Raftコマンドが所属するピアに送信されると、そのコマンドはピアのメールボックスに格納されます。メッセージの収集フェーズ(上の円の緑色の部分)で、raftstoreスレッドはメールボックスにメッセージを持つ複数のピアを収集し、メッセージの処理フェーズ(円の紫色の部分)でそれらをまとめて処理します。

このPrewriteリクエストの例では、Raft Read Indexリクエストを持つRaftコマンドがピアのメールボックスに格納されています。raftstoreスレッドがステップ1でピアを収集した後、raftstoreスレッドはメッセージの処理フェーズに入ります。

以下は、raftstoreスレッドがhandle messagesフェーズで実行する対応のステップです。

• ステップ2：ピアのメールボックスからRaftコマンドを読み出します。
• ステップ3：RaftコマンドをRaft Read Indexリクエストとsnapshot callbackに分割します。
• ステップ4：Raft Read Indexリクエストをraft-rsライブラリに渡し、ステップ関数で処理させます。
• ステップ5：raft-rsライブラリは、送信するネットワーク・メッセージを準備し、メッセージ・バッファに保存します。
• ステップ6：スナップショット・コールバックをピアの保留中のリード・キューに保存します。
• ステップ7：このフェーズの最初に戻り、同じワークフローを持つ他のピアを処理します。

raftstoreスレッドがすべてのピアのメッセージを処理した後、単一のループの最後のフェーズであるプロセスI/Oフェーズ(円の青い部分)に至ります。このフェーズでは、raftstoreスレッドは、メッセージバッファに格納されたネットワークメッセージを、ステップ8でネットワークインターフェースを介してクラスタの他のTiKVノードに送信します。

これで、Read Proposeフェーズが終了します。prewrite要求が進展する前に、他のTiKVノードが応答するのを待つ必要があります。

Read Applyフェーズ

「長い」待ち時間(コンピュータにとって数ミリ秒は本当に長い)の後、ネットワークメッセージを送信したTiKVノードはようやく他のフォロワーノードからの応答を受信し、応答メッセージをピアのメールボックスに保存します。ここで、prewriteリクエストはRead Applyのフェーズに入ります。下図は、このフェーズのワークフローを示したものです。

働き者のraftstoreスレッドは、このピアのメールボックスに処理待ちのメッセージがあることに気付くので、このフェーズでのスレッドの動作は次のようになります。

• ステップ1：メッセージの収集フェーズにループバックした際に、再びピアを収集します。
• ステップ2：前のフェーズと同様に、スレッドはピアのメールボックスから返信メッセージを読み出します。
• ステップ3：ステップ関数で処理されるように、メッセージをraft-rsに渡します。
• ステップ4：メッセージが処理された後に適用可能な読み取り操作を特定し、その操作を収集します。
• ステップ5：ピアの保留中の読み取りキューに一時的に格納されているスナップショット・コールバックを呼び出します。
• ステップ6：KVエンジンのスナップショットを構築し、スナップショットコールバックに送信します。
• ステップ7：スナップショットコールバックをトランザクションスケジューラと、スナップショット、cid、およびMutationsからなるタスクに分割します。そして、raftstoreスレッドは、トランザクションスケジューラが記録した情報に従って、トランザクションワーカースレッドにタスクを送信します。

これでRead Applyのフェーズが終了します。次は、トランザクションワーカーの番です。

Write Prepareフェーズ

このフェーズでは、スケジュールワーカープールのトランザクションワーカーがステップ1でraftstoreスレッドから送られたタスクを受信すると、ワーカーはステップ2でタスクをKVスナップショット、Mutations、cidに分割して処理を開始します。

トランザクションレイヤーの主要なロジックがここで登場します。これには、トランザクションワーカースレッドによって実行される以下のステップが含まれます。

• ステップ3：スナップショットを介してKVエンジンを読み込み、トランザクション制約が保持されているかどうかをチェックします。
• ステップ4：チェックに合格した後、prewriteリクエストのために書き込むデータを準備します。
• ステップ5：データを通常のRaftリクエストにラップします。
• ステップ6：cidを持つ新しい書き込みコールバックを準備します。
• ステップ7：コールバックを通常のRaftリクエストと一緒にRaftコマンドに組込みます。
• ステップ8：そのコマンドを所属するピアに提案します。

トランザクション層のロジックはここで終了します。このRaftコマンドは書き込み操作を含みます。コマンドが正常に実行されれば、prewriteリクエストは成功です。

Write Proposeフェーズ

さて、いよいよraftstoreスレッドが書き込み操作を提案するフェーズです。次の図は、このフェーズでraftstoreスレッドがRaftコマンドをどのように処理するかを示しています。

このフェーズの最初の3つのステップは、前のセクションのものと同じです。ここでは繰り返しません。残りのステップを見ていきましょう。

• ステップ4：raft-rsは、ネットメッセージをメッセージバッファに保存します。
• ステップ5：raft-rsはRaftログを書き込みバッチに追加します。
• ステップ6：ピアが書き込みコールバックをプロポーザルに転送し、ピアの内部プロポーザル・キューに格納します。
• ステップ7：raftstoreスレッドは、メールボックスにメッセージを持つ他のピアの処理に戻ります。
• ステップ8：raftstoreスレッドはプロセスI/Oフェーズ(円の青い部分)に来て、書き込みバッチに一時的に格納されたメッセージをRaft Engineに書き込みます。
• ステップ9：Raft Engineは、メッセージの書き込みが成功したことを返します。
• ステップ10：raftstoreスレッドが他のストレージノードにネットメッセージを送信します。

これでWrite Proposeフェーズが終了します。さて、Read Proposeフェーズの終了と同様に、リーダーノードは次のフェーズに移る前に他のTiKVノードからの応答を待つ必要があります。

Write Commitフェーズ

さらに「長い」待ち時間の後、フォロワーノードはリーダーノードに応答し、prewriteリクエストをWrite Commitフェーズに移行させます。

• ステップ2：ピアは、他のTiKVノードからRaft appendレスポンスを受信します。
• ステップ3：ステップ関数が応答メッセージを処理します。
• ステップ4、5、6：raftstoreスレッドは、コミットされたRaftエントリーをRaft Engineから収集します。
• ステップ7：raftstoreスレッドは、コミットされたRaftエントリーに関連するプロポーザルを内部プロポーザル・キューから収集します。
• ステップ8：raftstoreスレッドは、Raftコミットされたエントリーと関連するプロポーザルをapplyタスクに組み入れます。
• ステップ9：raftstoreスレッドはタスクをapplyスレッドに送信します。

Write Commitフェーズが終了すると、raftstoreスレッドはそのすべてのタスクを完了します。次に、applyスレッドにバトンタッチされます。

Write Applyフェーズ

Prewriteリクエストにとって最も重要なフェーズであり、スレッドが実際にKVエンジンに書き込みを行います。

applyスレッドは、ステップ1、2でraftstoreスレッドから送信されたapplyタスクを受信した後、メッセージの処理フェーズ(円の紫色の部分)で次のステップを継続的に行います。

• ステップ3：タスクからコミットされたRaftのエントリーを読み取ります。
• ステップ4：エントリーをKey-Valueペアに転送し、そのKey-Valueペアを書き込みバッチに格納します。
• ステップ5：タスクからプロポーザルを読み取り、コールバックとして格納します。

そして、次のフェーズ(プロセスI/O)で、applyスレッドは以下のステップを行います。

• ステップ6：書き込みバッチ内のKey-ValueペアをKVエンジンに書き込みます。
• ステップ7：KVエンジンが返し、書き込み操作が成功したかどうかの結果を受け取ります。
• ステップ8：全てのコールバックを呼び出します。

コールバックが呼び出されると、トランザクションスケジューラはステップ9でそのcidを持つタスクをトランザクションワーカーに送り、最後の部分に至ります。

Returnフェーズ

これは、prewrite処理の最終フェーズです。TiKVは、prewriteリクエストの実行結果をクライアントに返します。

このフェーズのワークフローは、主にトランザクションワーカーによって実行されます。

• ステップ1：トランザクションスケジューラから送られたcidをトランザクションワーカーが取得します。
• ステップ2：トランザクションワーカーは、cidを使用して相互排他的にトランザクションタスクスロットにアクセスします。
• ステップ3：トランザクションワーカーは、gRPCリクエストフェーズの間にトランザクションタスクスロットに格納されるgRPC notifi callbackをフェッチします。
• ステップ4：トランザクションワーカーは、gRPCタスクキューで待機しているgRPC respond taskに通知を送信します。
• ステップ5：gRPCサーバースレッドは成功結果をクライアントに応答します。

まとめ

この記事では、prewriteリクエストを成功させるための8つのフェーズを紹介し、各フェーズ内のワークフローに焦点を当てました。この記事が、TiKVリクエストのリソース利用を明確にし、TiKVをより深く理解するための一助となれば幸いです。

TiKVの実装の詳細については、TiKVのドキュメントとディープダイブを参照してください。もし質問やアイデアがあれば、お気軽にTiKV Transaction SIGに参加して、私たちとシェアしてください。