歴史で振り返るv19.2で実装されたParallel Commits　最短処理を実現する処理タイミングの変化

Parallel Commits未実装、初期の実行の流れ

kota2and3kan氏：ここまでが基本的なCOMMITとそれらのデータを読み込む際の動作になります。ここからはParallel Commitsについて話をします。これはどちらかというと最適化の部分の話になってきます。

まず、少し歴史の話をします。まだParallel Commitsが実装されていない、初期の頃の話です。最初の頃のCockroachDBでは、トランザクションの中のStatementはすべて順番に実行される作りになっていました。

どういうことかというと、最初に1つ目のWriteが実行され、このタイミングでTransaction Recordも作成されます。

この書き込みが完了した後に、2つ目のWriteが実行されます。

そしてこの2つ目の書き込みが完了した後に、さらに3つ目の書き込みが実行され、最後にTransaction RecordをCOMMITTEDに書き換えるというCOMMITの処理が実行されます。

つまり、トランザクション内のStatementに対して、処理時間が比例して延びてしまう。トランザクション内のStatementがnだった場合、O(n+1)という処理時間がかかってしまうのが初期の頃の作りになっていました。

v2.1〜v19.1までの実装

そして、少し前のバージョンで新しい機能が実装されました。Pipeliningと呼ばれる機能で、このPipeliningという機能を使うと、トランザクション内のStatementを並列で実行できます。

（スライドを示して）この例だと、ここの3つのWriteはすべてが並列で実行されます。1つ前のStatementが終わるのを待たず、並列で書き込みを開始できます。

そしてすべての書き込みが完了した後に、Transaction RecordをCOMMITに書き換える処理をします。

つまり、Coordinatorから他のNodeに対する処理がStatementの数に比例するのではなく、最短2往復で済むことになります。

ただし、少し制限があります。例えば、トランザクションの中のStatementに依存関係がある場合です。今自分が書き込んだKey1に対して、その後に同じKeyをReadするトランザクションがあったとします。

この時、直接関係がないKey1とKey3に対するWriteは並列で実行されます。

ただ、Readの処理は自分が書き込んだKey1の値を正しく読み込まないといけないので、Key1に対する書き込みが終わった後にReadを実行します。

そして最後に、トランザクションをCOMMITする処理が実行されます。つまり、Pipeliningを使ってもあくまで理論上の最短が2往復の処理になるだけで、トランザクション内のStatementに依存関係がある場合は、必ずしも最短2往復になるわけではないことになります。

最新の実装

いよいよParallel Commitsについて話します。このParallel Commitsではどのような処理をするかというと、先ほど最短2往復になっていた原因であるCOMMITの処理すらも、他のStatementと並列して実行することになります。

つまり、COMMITを含めたすべての処理が最短1往復で完了できるという、理論上の最短を実現する機能になっています。

（スライドを示して）また特徴として、今までは最初のWriteと一緒にTransaction Recordが作成されていたのですが、Parallel Commitsの場合、COMMITの処理をするタイミングでTransaction Recordが作成されます。

書き込み完了前にCOMMITする処理を開始して大丈夫なのかが気になると思うので、その話をしていきたいと思います。

Parallel Commits、COMMIT（Write）の動作

Parallel CommitsのCOMMIT、まずWriteの動作について話します。今回はNode1がCoordinatorでクライアントからBEGINしてKey1にWrite、Key2にWrite、COMMITというトランザクションが実行される場合を考えます。また、Key1とKey2はそれぞれ別のRangeに別のNodeにデータが格納されていると仮定します。

ここでクライアントからまずトランザクションを受け取って処理を開始するのですが、COMMITする手前まで、Writeを受け取ったタイミングでは、まだTransaction Recordを作成せずに、Key1とKey2に対するWriteをそれぞれ並列で実行します。

そしてクライアントからCOMMITを受け取ったタイミングで、Key1やKey2への書き込みと並列でTransaction Recordを作成します。この時、StateはSTARGINGという、Parallel Commitsの処理中であることを示す値がStateとして書き込まれます。ここには「このトランザクションで処理しているKey1とKey2の値、どのKeyに書き込んでいますよ」という情報が入っています。これは障害発生時に使う情報になるので、後で説明します。

そしてこのTransaction RecordとKey1とKey2に対する書き込みに対して、すべてWrite OKが返ってきた場合は、Coordinatorはクライアントに対してCOMMIT完了を返します。

このタイミングでクライアントは次の処理に移行できるわけですが、そのCOMMITを返した後、非同期で最後のCOMMITする処理をCockroachDBで実行します。

（スライドを示して）先にStatementをCOMMITTEDに書き換えます。COMMITTEDに書き換えた後はWrite Intentが要らなくなるので、削除する処理をします。この時、他のトランザクションが読み込んできたりする可能性があるので、非同期にはなっているのですが、この処理はできるだけ早く実行されます。

Write Intentが削除されて最終的にトランザクションが完了すると、不要になったTransaction Recordが削除される動きになります。これがParallel CommitsでのWriteの動作です。

Parallel Commits、Readの動作

次にReadの動作について話します。先ほどと同じように、Node1がCoordinatorでKey1とKey2に対してWriteを実行して、STAGINGのTransaction Recordが作成されている状態を考えます。この時、他のNode2がTransaction2の中でKey1に対するReadを実行します。

ここでNode2がKey1に対するReadを実行するとWrite Intentの印が付いていることがわかるので、「これはまだ処理中の可能性がある」と判断できます。

そのため、Transaction Recordの値を確認しにいくと、StateがSTAGINGになっている。つまり、Parallel Commitsで処理中であることが判断できます。

また、この時Node1は正常に動作しているので、CoordinatorであるNode1からTransaction Recordに対してHeartbeatが実行されています。

つまり、Heartbeatが生きている間はトランザクションを処理しているCoordinatorが生きていることも判断できるので、このNode2のトランザクションは「このWriteをしているNode1の処理が完了するまで待つ」という動作をします。

そして、待っている状態で、裏でTransaction Recordと各Keyに対する書き込みが完了します。Coordinator Node側でCOMMITを返して「Transaction RecordがCOMMITですよ」となるタイミングで「ここのWrite IntentはCOMMITした」という扱いにしてよいので、待っていたReadのトランザクション、Node2はx1という値をReadすることになります。

つまり、Parallel CommitsであってもReadが特殊なことをしているわけではなく、「単純に書き込みをしているトランザクションの処理が終わるのを待つ」という動作をします。これが正常時の動作です。

（次回に続く）