2010年1月6日水曜日

グローバルトランザクション処理のパターン

送金のトランザクション処理パターンでは、Google App Engine (GAE)のEntity Groupにまたがるトランザクション処理を行う方法について紹介しました。また、それに少しだけ最適化を施した結果、下図のような処理になりました。

しかし、このトランザクション処理はいくつかの制約があります。

  • (a) 送金中に合計金額がずれる
  • (b) 送金先の口座に制約をかけられない

このトランザクションはEventual Consistency (結果整合性)というレベルの整合性保証しかしないため、2つのEntity Groupの値にずれが発生する場合があります(a)。たとえば、口座(A)から口座(B)に1000円だけ送金する場合、(1)と(2)の間は「口座(A)から出金したが、口座(B)に入金されていない」という状態になります。

また、送金元の口座に制約はかけられますが、送金先の口座に制約をかけられません(b)。たとえば「残高不足で送金できない」といった処理は可能ですが、「残高が限界を超えたために入金できない」といったケースに対応できません。もしそこに制約をかけてしまうと、出金したけど入金できないという状況になってしまいます。

今回は、上記のような問題を解決したApp Engine上のトランザクション処理のパターンについて考えてみたいと思います。例によってドラフトなので、ご指摘等いただけると助かります。

なお、「グローバルトランザクション」という名前は、GAEの「ローカルトランザクション」に対して付けた語で、このエントリでは「Entity Groupにまたがるトランザクション」の意味で使います。GAEのEntity Groupのように、局所的にトランザクション処理を実行することをローカルトランザクションと呼ぶようです。

エンティティの書き込み

前回同様に、口座Aから口座Bに5000円送金する例について紹介します。スタートは下図のような感じです。

それぞれの口座を別のEntity Group上に配置し、さらに中央にもう一つ空のEntity Groupを用意しました。これについては次で。

トランザクションの開始 (begin)

まず、グローバルトランザクションを開始します。 このとき、グローバルトランザクションを管理するためのエンティティを一つ作ります。

これには、トランザクションID、開始時刻、状態、などのプロパティを持たせます。トランザクションIDはユニークな値なら何でも構いません。

ジャーナルの作成 (prepare)

次に、変更対象のエンティティを取得し、変更後にジャーナルとして書き込みます。エンティティに直接上書きしないのは、どこかで失敗した際に正しく復元するためです。 ジャーナルには、どのトランザクションで作成されたものかがわかるように、先ほど作成したトランザクションエンティティのIDを付与しておきます。

同様に、残りのエンティティに対しても変更してジャーナルを作成します。これらのエンティティに対する変更は同時に行ってもかまいません、 このため、前回の「(b) 送金先の口座に制約をかけられない」という制約を回避することができます。

なお、上記の2つのエンティティの取得にはtransactional readを使っていません。 もし、同時刻のスナップショットがほしければ口座エンティティにバージョン情報を振っておき、「口座(A) -> 口座(B) -> 口座(A)」の順に読みだして、口座(A)のバージョン整合性を確認すればよさそうです。バージョンが一致した場合、口座(B)を取得した時刻の口座(A)と、読みだした口座(A)の内容が完全に一致します。

トランザクションの完了/中止 (commit/abort)

全てのジャーナルの書き込みが成功したら、トランザクションエンティティの状態を「開始」から「完了」に変更します (「開始」以外を「完了」に変更すると不整合が起こります)。

ここでのポイントは、この状態が「完了」になると全てのジャーナルの情報が有効になる、という点です。 逆に、それまではジャーナルの情報は有効になりませんので、トランザクション全体の状態をここで管理することで、全体の変更をトランザクショナルに行っているように見せかけています。

ジャーナルの書き出しが一つでも失敗したら、トランザクションエンティティの状態を「開始」から「失敗」に変更します。これは「完了」と逆の処理で、全てのジャーナルを無効化します。 この「失敗」の情報を書き出せなかった場合の補償については、後の「トランザクションのタイムアウト」で紹介しています。

ジャーナルの適用 (roll forward)

トランザクションエンティティの状態が「完了」になったら、先ほど書きこんだジャーナルの情報を有効にできます。ジャーナルの情報をエンティティに上書きして、残高を10000円から5000円に変更(5000円出金)します。 ジャーナルの反映が終わったら、同一のローカルトランザクション内でジャーナルの情報を削除します。このため、ジャーナルの情報がエンティティに反映されるのはこの1回だけです。

同様に、残りのエンティティについてもジャーナルの反映を行います。こちらでは残高を10000円から15000円に変更(5000円入金)します

なお、上記の処理も「べき等 (idempotent)」に行うことができます。つまり、何回実行してもジャーナルが反映されるのはちょうど一度だけです。 このため、トランザクションエンティティの状態が「完了」になれば、あとは成功するまでジャーナルの反映を繰り返せば、グローバルトランザクションはいつか成功します(するはずです)。

このべき等性を利用して、App Engineではジャーナルの適用にTask Queueを使うこともできます。 トランザクションエンティティを「完了」にする際に、ジャーナルの適用を行うためのタスクを登録すれば、これらのジャーナルはいつか必ず適用されます。 ローカルトランザクションの中でタスクの登録を行う方法は、「DBオペレーションに応じてメール送信したい - Kays daddy」などでも紹介されています。GAE for Javaの場合は、トランザクションオブジェクトを引数にとるQueue.add()メソッドを利用します。

このときに注意すべき点として、適用するジャーナルは現在のトランザクションに関するものでなくてはなりません。何らかの理由でジャーナルの適用が2回行われ、2回目には別のトランザクションのジャーナルが作成されていた場合、勝手に適用すると大変なことになります。

トランザクションのタイムアウト (timeout)

今回は、トランザクションのタイムアウトについても考えておく必要があります。トランザクションエンティティの状態が「完了」になった以降はタイムアウトしなくてもよいのですが、「ジャーナルを作成してから、トランザクションエンティティの状態が「完了」になるまで」の間にエラーが起こった場合、ジャーナルがゴミとして残ってしまいます。

以降で詳しく説明しますが、ジャーナルが作成されて反映されるまでの間、それぞれのエンティティへの書き込みはできません。書きこんでしまった場合、そのあとに行われるジャーナルの反映で、その書き込みは上書きされてしまいます。 つまり、ゴミとして残ったジャーナルをそのままにしておくと、エンティティを利用できなくなる可能性があります。

そこで、状態が「開始」のまま一定以上時間がたったトランザクションについては失敗したものとみなすようにします。

なお、GAEでは1回のリクエストに30秒以上掛かるものは強制的に終了させられるため、「開始から30秒たっても完了しないトランザクション」を対象にするのがよさそうです。

確実にタイムアウトの処理を行いたい場合には、トランザクションの開始時に「30秒後にトランザクションをタイムアウトにするタスク」を(トランザクショナルに)登録しておけばいつか必ず実現できます。

ジャーナルの破棄 (rollback)

トランザクションエンティティの状態が「失敗」になったら、それぞれのジャーナルの情報は破棄します。

つまり、トランザクションが「完了」になったら全てのジャーナルを反映、トランザクションが「失敗」になったら全てのジャーナルを破棄、といった形になります。 このような形で、トランザクション処理の特性である「アトミック性」について実現できました。

なお、このロールバックの処理についてもジャーナルの適用と同様にTask Queueを利用して実現することもできます。 トランザクションの状態を「失敗」にすると同時にタスクを登録しておけば、いつか必ずロールバックが成功します。 ロールフォワード時の注意点と同様に、、破棄するジャーナルは現在のトランザクションに関するものでなくてはなりません。

エンティティの読み出し

今回はジャーナルという仕組みを使ったため、読み出しについてもいくらか複雑になっています。 トランザクションの状態を4種類に場合分けして、それぞれについて読み出し方を考えてみます。

ここで、適切な分離を選択すれば、前回の「(a) 送金中に合計金額がずれる」という問題を解決できます、が、それなりに大変そうです。

説明が複雑になるのを避けるため、以下すべてローカルトランザクションで、口座エンティティとジャーナル情報を読みに行ったものとしてください。

ジャーナルが存在し、トランザクションが「開始」

トランザクションの状態が「開始」である場合、そのトランザクションはその後に「完了」か「失敗」かのいずれかになります。 「完了」と「失敗」のどちらになるかによってジャーナルの意味が変わってしまうため、現時点でそのエンティティを使うのは危険です。

分離レベルによってはこのエンティティをリードオンリーで利用してもいいかもしれません(トランザクションエンティティをtransactional readしていないので少し怪しいです)。 いずれにせよここでエンティティを変更した場合、その後にジャーナルで上書きされてしまう恐れがあります。

ジャーナルが存在し、トランザクションが「完了」

先ほどの「開始」状態と異なり、「完了」の状態ではジャーナルの情報が有効になっています。 次に必要な操作はジャーナルの適用となるため、読み出し時にはエンティティの情報を無視して、ジャーナルの情報を利用します。

読みだしたエンティティを書き戻す場合は、同時にジャーナルを削除しておきます。これを忘れると、次に読み出す際にもジャーナルから情報を復元してしまい、いつまでたっても書き込みが反映されません。

ジャーナルが存在し、トランザクションが「失敗」

トランザクションの状態が「失敗」の場合は、ジャーナルの情報が無効になっています。 次に必要な操作はジャーナルの破棄となるため、読み出し時にはジャーナルの情報を無視してエンティティの情報を利用します。

このエンティティを書き戻す場合は、先ほどと同様に同時にジャーナルも削除します。

ジャーナルが存在しない場合

ジャーナルが存在しない場合、そのエンティティはグローバルトランザクションに参加していないか、グローバルトランザクションに参加しているもののジャーナルの作成が行われていない状態です。

このケースでは、普通にエンティティを利用できます。

ジャーナルが存在しないエンティティを読み出した後に、そのローカルトランザクション内で変更して書き戻すこともできます。 そこでの整合性については、ローカルトランザクションの機能(楽観的並行性制御)を利用して保障します。 たとえば、別のグローバルトランザクションにおけるジャーナルの作成とこの書き戻しが競合し、先にこの書き戻し処理が成功した場合には、同時に進んでいたグローバルトランザクション全体が失敗します。

なお、ジャーナルが存在する場合には常にトランザクションが「開始」の状態であるとみなす、という別の戦略をとることもできます。 ただし、その方法ではジャーナルによるブロッキングの時間が長くなってしまいますが、トランザクションエンティティの状態を確認しに行かなくてもよくなるために、読み出し処理のパフォーマンスを向上させることができます。この辺りはトレードオフになると思います。

その他

最適化について

今回のエントリで紹介したやり方は、理解しやすさを優先したためかなり無駄が多いです。 トランザクションエンティティが個別のEntity Group上に作成されていますが、これを変更対象のエンティティがいるEntity Group上に作成してやると、ローカルトランザクションの回数を数回削減できます。 また、トランザクションエンティティの「開始」や「失敗」は、ジャーナルエンティティにタイムスタンプを埋めておくことで代用できそうです。

上記のやり方では、Entity Groupがn個のグローバルトランザクションを実現するために、2n - 1回のローカルトランザクションが最低でも必要になりそうです。 送金のトランザクション処理パターンおよびその最適化によって実現したトランザクションは、ちょうどn回のローカルトランザクションで済みますので、状況によって使い分けるのがよさそうです。

まとめ

今回は「送金のトランザクション処理パターン」で紹介した方法よりも、より細かい制御が可能なグローバルトランザクションの手法について考察してみました。 これをアプリケーション側で書くとなると非常に大変そうなので、公式のSDKやフレームワークなどで同じようなことができるようになれば、Google App Engineでもう少し無茶ができそうです。

いずれの場合にせよ、整合性を保障する方策や、許される整合性のレベルなどは、常にACIDトランザクションを利用していた設計よりも多くのことを考えなければなりません。 このエントリで紹介した方法は、パフォーマンスに悪影響を及ぼす可能性が考えられますので、必要な整合性や設計および実装の手間を考慮しながら、注意深く選択することが必要になります。

1 件のコメント:

  1. この記事についてですが、slim3 gtxを使った場合のコードがあると大変わかりやすいと思うのですが。

    返信削除