CockroachDBにどのようにデータを記録するのか？　COMMIT、ABORT、Readの仕組みと動作

用語説明

kota2and3kan氏：ここからは、実際のCockroachDBの動作について話していきます。最初に用語について少し話します。

（スライドを示して）まずTransaction Recordです。これはトランザクションの状態を管理するためのデータで、最初にトランザクションがWriteされたKeyと同じRangeに書き込まれます。

Transaction Recordにはいくつかの状態があります。1つ目がPENDINGで、これはトランザクションが処理中であることを示します。次にCOMMITTEDで、トランザクションはCOMMIT済みです。

次にSTAGINGで、これは後半で話すParallel Commitsという処理で使われるものです。そしてABORTEDで、これはトランザクションがABORTしたことを示します。また、Transaction Recordそのものが存在していない状態も発生します。

次にWrite Intentについて話します。（スライドを示して）Write Intentは、トランザクションのCOMMITもしくはABORTという状態が確定していないレコードに付けられる印です。このWrite Intentには、レコードを書き込んだトランザクションのIDの情報や、Write Intentが書き込まれた時間の情報を持っています。

次に、Transaction Liveness Thresholdです。これはトランザクション、もう少し厳密に言うと、Coordinator Nodeの死活監視をする場合に必要な閾値です。Gateway Nodeで障害が発生した時に、それをチェックする場合に使われます。

COMMITの仕組みと動き

ここから、具体的な動きについて見ていきます。（スライドを示して）まず少し説明をしますが、真ん中にあるのが、Rangeと呼ばれるKey−Valueのデータの塊です。そして今ここにKey1、Key2、Key3と3つデータが入っていて、それぞれx0、y0、z0と値が入っています。

そしてもう1つ特徴的なのが、今はt0となっていますが、Keyの中にタイムスタンプの情報も持っています。このようなデータが格納されているところに、タイムスタンプ1で実行されたTransaction1がBEGINして、Key1にWriteしてCOMMITする処理をする時の流れを見ていきます。

最初にトランザクションを開始します。

次にKey1に対するWriteが実行されます。この時、既存のKey1の値を上書きするのではなく、別のWrite Intent付きのKey1という値が追記されます。

その後、Transaction Recordが作成されます。作成されたTransaction RecordはStateがPENDINGになっています。Write IntentからはTransaction1のTransaction Recordが参照できるようになっているので、「これはまだPENDINGのTransactionだよ」ということがわかるようになっています。

最後に、COMMITを実行するとStateの値がCOMMITTEDに書き換えられます。クライアントに対しては、StateをCOMMITTEDに書き換えたタイミングでCOMMIT完了のレスポンスが返ります。

そして、クライアントにCOMMITを返した後に、非同期でWrite Intentを削除する処理が行われます。

Write Intentの削除の処理が終わると、不要になったTransaction Recordが削除されて、「この追記されたKey1は、t1という時間で書き込まれました」というかたちで値が確定することになります。

ABORTの仕組みと動き

次に、ABORTの仕組みを見ていきます。これは先ほどのCOMMITとほぼ同じ流れです。

（スライドを示して）まずトランザクションを開始して、次にKey1に対するWriteを実行します。

ここでWriteを実行すると、Write Intent付きのKey1のデータが追記されます。

そして、同じようにTransaction RecordがPENDINGの状態で作成されます。

この状態でトランザクションがABORTすると、今度はStateの値がABORTEDに書き換えられます。そうすると「このトランザクションはすでにABORTした」と扱えます。

ABORTした場合は、要らなくなったWrite IntentとKeyの値、Transaction Recordを削除する動きをします。これがCockroachDBにおけるCOMMIT、Writeする時の動作です。

Readの仕組みと動作

それでは、Readの動作について見ていきます。トランザクションはどのような値を読み込むのか。先ほどのように、Transaction1がBEGINしてKey1にWriteしてCOMMITもしくはABORTする状況かつ、隣でTransaction2がKey1に対するReadを実行する場合を考えます。

まず、Key1に対するReadが先に実行された場合です。この場合、タイムスタンプの値を見てどの値を読み込むのかを判断するので、Readが先に実行されている場合は、Write Intentが仮にあったとしても、t0の値であるx0という値を読み込みます。

逆にWriteが先に実行されていた場合は、トランザクションのタイムスタンプと実際のKeyのタイムスタンプを比較して最新の値を拾ってきます。最新の値を拾ってきた時に、key1の値はx1ですが、これにはまだIntentが付いています。つまり、トランザクションがCOMMITしたかABORTしたか、確定していないことが確認できます。

そのため、Write Intentを見つけたRead TransactionはTransaction Recordの値を確認しにいきます。

確認しにいったTransaction Recordの値がCOMMITTEDだった場合、Write Intentを書き込んだトランザクションはすでにCOMMITしていると扱えるので、Intentが付いている場合でも、x1という値をそのままReadできます。

逆にStateがABORTEDになっていた場合、トランザクションはもうABORTしていて、書き込みはABORTしたトランザクションによる書き込みとなるためなかったことになり、1つ前のバージョンであるx0という値を読み込むことになります。

さらにStateがPENDIDNGだった場合は、Transaction1側でまだ処理を実行していて、COMMITもABORTも確定していない状況になるので、Read Transactionはトランザクションが完了するまで「待つ」という動作になります。

最後に、Transaction Recordが存在していないパターンがあります。これはトランザクションが単純に処理中である場合や、Gateway Node、いわゆるCoordinator Nodeに障害が発生して書き込まれていない可能性があります。

Transaction Recordがない時にどう判断するのか

Transaction Recordがない時に、いったいどうやって判断するのかという話をしていきます。

これは、Write Intent、書き込まれた値のタイムスタンプの値と、Transaction Liveness Thresholdの値を使って判断をします。このあたりを説明するために、少し補足をしていきます。

（スライドを示して）まず先ほどから話しているように、CockroachDBではクエリを受け取ったNodeがCoordinatorとして動きます。そして、Coordinatorが実際にKeyに対するWriteや、Transaction Recordの作成を実行します。

この時、Transaction Recordを書き込んだCoordinatorに障害が発生したとします。例えば、今のTransaction RecordはState PENDINGのままですが、この状態でCoordinatorに障害が発生してしまうと、Transaction Recordの値を書き換える人が誰もいなくなってしまいます。

この状態で他のNode2で実行されたトランザクションに、例えばReadの処理が実行されると、ReadはKey1の値を見てWrite Intentの印が付いていることが確認できるので、このKey1の状態を判断するために、Transaction Recordを見にいきます。

しかし、Transaction Recordを見にいくとStateはPENDINGなので、Node2は単純にトランザクションが終わるまで待つような動作をします。しかし、実際にはCoordinator Nodeが死んでしまっていて永遠にトランザクションの状態がPENDINGのままになってしまうので、ずっと待ち続ける動きをしてしまいます。

これを解消するためにどういう仕組みがあるかというと、CockroachDBのCoordinator Nodeでは、Transaction Recordに対してHeartbeatが定期的に実行されています。

Heartbeatを実行することで、トランザクションが生きているか死んでいるかを判断できるようになっています。例えば、トランザクションを実行中のCoordinatorが死んだ場合、Heartbeatが途切れるので、「もうここのTransaction Recordは期限切れですよ」と扱えるようになります。この期限切れか否かを判断するのが、Transaction Liveness Thresholdという閾値になっています。

Transaction Liveness Thresholdによって、Transaction1が期限切れになっている状態かを確定できるので、先ほどと同じように、Node2がKey1をReadしてWrite Intentを見つけて、そのWrite Intentに紐付くTransaction Recordを確認した時にすでに期限切れであるため、Transaction1を実行していたCoordinatorに、何らかの問題が起きたことが判断できるようになります。

（スライドを示して）Transaction Recordの値を見て、期限切れになっていることが確認できるので、Node2は「すでにCoordinatorが死んだものである」と判断して、Transaction Recordの値をABORTEDに書き換えます。そしてRead処理自体は、1つ前のバージョンであるx0の値を読み込んでくれることになります。

Transaction Recordが作成される条件

Transaction Recordが作成される条件についても話をします。Transaction Recordが作成される条件は、主に3つあります。

1つ目がCOMMITが実行されたタイミングです。これはParallel Commitsの処理に関連してくる部分なので、後で詳しく話します。

2つ目は、トランザクションを管理しているCoordinatorがHeartbeatを実行したタイミングです。つまり、トランザクション内の最初のWriteから1秒経ってHeartbeatが実行されると、PENDINGの状態でTransaction Recordが作成されます。

3つ目の条件は、障害が発生した時の動作に絡んできます。例えば、あるCoordinatorがKey1をWriteしたものの、Transaction Recordを作成する前に障害が発生してしまったパターンを考えます。

この時、Key1は書き込まれたものの、Transaction Recordは存在していないので、他のNodeがこのKey1の値を読み込んでWrite Intentが付いていることを見つけます。Write IntentがあるのでTransaction Recordを確認しにいこうとすると、Transaction Recordが存在していない状態になります。

ただし、この段階では単純に処理が遅れてたり、タイミングによって作成されていないだけなのか、Coordinatorに障害が起きてるのかをNode2からは判断できません。

では、Node2がTransaction Recordがない状態で判断できなくなった場合はどのようにするかというと、Write Intentのタイムスタンプの値を見にいきます。そして、このタイムスタンプが先ほど話したTransaction Liveness Thresholdという閾値以内か、それとも範囲外かを確認します。

Write IntentのタイムスタンプがTransaction Liveness Thresholdの閾値以内だった場合は、まだ処理中である可能性があるとして、PENDINGとして単純に「待つ」という動作をします。

逆にT1の値がTransaction Liveness Thresholdの範囲外、要するにWrite Intentが古いタイムスタンプで書かれていた場合は、「ここのWrite Intentを書き込むトランザクションには何か問題が発生した」という判断をして、StateをABORTEDに書き換えた上で、1つ前の古いバージョンをきちんと読み込む動作をします。

障害が発生している可能性があることを検知した、Coordinator Nodeではない他のNodeが、ABORTEDでTransaction Record作成することが、Transaction Recordが作成される3つ目の条件になります。

Readの動作

ということで、話を元に戻します。先ほど、WriteとReadが実行されている状態で、ReadがWrite Intentが付いているKeyの値を読み込みました。しかし、Transaction Recordが存在していないという状況が発生し得ます。この時どうやってトランザクションの状態を判断するかというと、Transaction Liveness Thresholdの値を確認します。

Write IntentのスタンプがTransaction Liveness Thresholdの閾値以内だった場合は、処理中の可能性があるとして「待つ」動作をします。

逆に、Write IntentのタイムスタンプがTransaction Liveness Thresholdの範囲外、古いデータだった場合は、Transaction1のCoordinator Nodeに何か問題が発生したと判断をして、このトランザクションは強制的にABORTEDという扱いにされ、古いデータを読み込むことになります。

（次回に続く）