2009年11月18日水曜日

送金のトランザクション処理パターン

App Engineで現実的な送金処理について考え中です。 ドラフト版なので、怪しい点があればご指摘いただければ幸いです。

コメントで情報いただきました。 Distributed Transactions on App Engineで紹介されてる方法と基本的に同じなので、おそらく問題なく動きそうです。ありがとうございました。

今回はこんな図を使います。

この図の読み方は、矢印の方向にユースケースの一連の処理(またはリクエストの処理)が流れていて、右に行くほど時間が経過しています。そして、矢印がくし刺しにしている四角形は、そのユースケース中で操作するエンティティを表しています。 また、左右の位置が同じ矢印は、基本的には同じ時刻に発生したイベントを表しています。上記の図では、A, B, Cがそれぞれの口座エンティティを同時に操作している感じです。

並行性制御(おさらい)

最初の図のように、それぞれのユーザが別々の口座を操作している場合は問題ないのですが、送金処理のように「自分の口座と別の人の口座を同時に操作する」といった処理には注意が必要です。

上記のようにAがBに送金処理を行っている最中に、Bが自分の口座を変更した場合、Bの口座の情報が壊れてしまう可能性があります。たとえば、Aの送金がなかったことになったり(Aの残高はちゃんと減る)します。

このような問題に対処するには、「並行性制御」という技術を使います。これは、同じエンティティが並行処理で操作されそうになる際に、どちらかを待たせたり、片方の処理を失敗させたりしてエンティティの情報が壊れないように制御します。 下図のようなイメージです。

以上、基本的なおさらいでした。以降では並行性制御を伴うエンティティの操作を「トランザクション処理」と呼ぶことにします。

エンティティグループ

App Engineのトランザクション処理は、エンティティグループ (EntityGroup)というエンティティに対して行われます。このEntityGroupについては公式ドキュメントや「App EngineのEntityGroupを理解しよう - ひがやすおblog」などで詳しく説明されているため、知らない人はまずそちらを読むのがよいと思います。

EntityGroupを絡めたモデリングをする場合、注意しなければならない点は次の3つです。

  1. 各エンティティは複数のEntityGroupに所属することができない
  2. 各エンティティが所属するEntityGroupは、そのエンティティの作成時に決定され、変更できない
  3. EntityGroupに対するトランザクション処理は、常にEntityGroup全体に対して行われる

先ほどの例では、Aの口座とBの口座をトランザクション処理していましたが、App Engineでこのトランザクション処理を実現するにはAとBを同じEntityGroupに所属させるという作業が必要になります。

さて、ここで次の例を考えてみます。

上記は、「CがBの口座に送金する」といった処理です。これもトランザクション処理中に行う必要があるため、BとCは同一のEntityGroupにあらかじめ所属している必要があります。 しかし、すでにBはAと同じEntityGroupに所属しており、「各エンティティは複数のEntityGroupに所属することができない」という規則により、A, B, Cは同一のEntityGroupに所属することになります。図のようにトランザクション処理が必要な個所が重複している場合、それらすべてを含むEntityGroupを一つ用意してやる必要があります。

さらに、口座C, D, E, F, ... と考えていくと、送金処理が必要になる際にすべてのエンティティが同一のEntityGroupに属することになります。 このEntityGroupを動的に変更できれば問題ないのですが、「各エンティティが所属するEntityGroupは、そのエンティティの作成時に決定され、変更できない」という規則によりどうしても巨大なEntityGroupを作らざるを得ない状況になります。

さて、このような巨大なEntityGroupを作成した場合、最後の「EntityGroupに対するトランザクション処理は、常にEntityGroup全体に対して行われる」という規則が非常に厄介なものになります。

上記は全て並行制御されるため、「同時に操作できる口座は常に1つ」という非常に残念なシステムが出来上がります。 せっかくApp Engineというスケールしやすいプラットフォームを利用しているにもかかわらず、口座の操作がボトルネックとなってしまうことが容易に想像できます。 RDBを利用する場合にはトランザクション処理の範囲を動的に(行単位で)決定できるため、このような問題は起こりにくかったと思います。

今回は、こんなケースにApp Engineではどう対処すればいいか、といった点についてちょっと考えてみたいと思います。

補償トランザクション処理の問題点

巨大なEntityGroupを作成するとボトルネックになってしまうため、最初にやらなければならないのはEntityGroupを分割することです。

EntityGroupを分割し、Aの口座とBの口座を別のEntityGroupに分割するケースについて考えてみます。 AからBに5000円送金する場合、疑似コードであらわしてみると次のようなプログラムになります。なお、atomic { ... }というのはトランザクション処理の単位だと考えてください。

atomic { // (a)
  Aの口座から5000円引く
}
atomic { // (b)
  Bの口座に5000円足す
}

多くの場合、上記の処理で正しく動作します。しかし、(b)の処理中にエラーが発生した場合、Aの口座から5000円が無駄に消滅するといった問題が起こってしまいます。 このリスクは「補償トランザクション」という技術を使ってある程度削減することができます。

atomic { // (a)
  Aの口座から5000円引く
}
try {
  atomic { // (b)
    Bの口座に5000円足す
  }
}
catch (...) {
  atomic { // (c)
    Aの口座に5000円足す
  }
  ...
}

上記は補償トランザクション処理を含めたコードで、(b)の失敗時に(a)の処理を取り消すような処理(c)が行われます。

しかし、App Engineではこの処理はあまりうまくありません。 (b)が失敗した後にさらに(c)も失敗する可能性があり、さらにApp Engineのリクエスト30秒ルールによって、(c)が成功する前に処理を打ち切られてしまう可能性があるためです。 つまり、App Engineお金を扱うなどのケースでは、補償トランザクションを適用すべきではありません。

考えたこと

App Engineで送金系の処理が行えないのも寂しいので、少し真面目に考えてみました。 先ほどと同様に「AからBに5000円送金する」という例について解説してみます。

まず、AとBのEntityGroupを分離しておきます。

次に、Aの口座から5000円引きます。このとき同時に、トランザクション処理で「出金処理」というエンティティを同一のEntityGroup上に作成します。これは「AからBに5000円送るつもりだ」ということを表すエンティティで、このエンティティができた瞬間にAの口座からは5000円引いた状態なります。 ここで失敗した場合は送金処理全体が失敗しますので、補償も必要ありません。

出金処理エンティティは、「送金番号(xxx)」「Bに」「5000円」「未処理」という情報を持っています。このうち、「送金番号」はデータストア上でユニークな値である必要があります。

次の処理で、Bの所属するEntityGroup上に「入金処理」というエンティティを作成します。これは先ほどの「出金処理」と対になるエンティティで、「AからBに5000円送られた」ということを表します。この時点ではまだBの口座残高は変更されません。

このとき重要なことは、「同じ送金番号を持つ入金処理エンティティがあれば何もしない」という点です。この規則を導入することによって、「1つの入金処理エンティティに対し、最大1つの出金処理エンティティしか作成できない」ということを保証することができます。 このようにエンティティのユニーク性を保証する場合、「App Engineのユニーク制限を正しく理解しよう - ひがやすおblog

この保証がある限り、図中の(2.a)の処理を何度繰り返してもよいことになります。1度成功したら、それ以降はユニーク制約により常に失敗するため、現在の成功/失敗の状態にかかわらず何度もこの処理を行うことができます。

次に、(2.a)の処理が無事完了したら、出金処理エンティティの「未処理」を「処理済み」に書き換えておきます。ちなみに、(2.a)で既に入金処理エンティティが作成されていた場合でも(2.a)は無事完了したとします。

これをやらなくても動きますが、「この出金を処理する必要があるか?」という情報として有用なので、やっておいたほうがよさそうです。 なお、この(2.a)と(2.b)は連続して繰り返すことができます。 何度も(2.a)を繰り返して、成功したときだけ(2.b)を行うことにしておけば、(2.b)で失敗した場合にも(2.a)からやりなおすことができます。

このように、何度繰り返しても同じ結果になるような処理のことを「べき等(idempotent)な処理」と呼ぶようです。これはApp EngineのTask Queueによる処理にも求められる性質で、逆にこれが守られている処理はTask Queueで処理しやすくなります。 この(2.*)の処理はEntityGroupをまたぐ処理ですので、整合性の保証が必要になります。この個所を「べき等性が保証されたエンティティの移動」という処理にすることで、安全にEntityGroupをまたいだ処理を行うことができます。

最後に、Bの入金処理エンティティをもとに、Bの口座に5000円加算します。このとき、トランザクション処理で入金処理エンティティの「未処理」を「処理済み」に書き換えておきます。これらは同一のEntityGroupになるように頑張ったので、App Engineの普通のトランザクション処理で実現できます。

このとき、かならず入金処理エンティティが「未処理」である場合だけ上記の操作を行うようにする必要があります。これを守らないと1度の送金で複数回の入金が行われてしまい、Bの資産が無駄に増えます。 ちなみにこの処理もべき等性のある処理です。一度入金処理を行ったら「処理済み」扱いになるので、何度(3)の処理を繰り返しても入金は1度だけになります。また、何度失敗しても、(3)の処理を繰り返せばいつかは入金に成功するはずです。

以上で送金処理の一通りの流れは終了です。最終的に、Aの口座からBの口座に5000円を送金することができました。おそらく、(1) ~ (3)のどのタイミングで失敗しても、いずれは送金が成功するはずです。

まとめ

以上が今回考えた「送金のトランザクション処理パターン」です。簡単に説明すると次の3ステップでした。

  1. Aの口座残高を減らし、出金処理情報を作成する (トランザクション処理)
  2. Aの出金処理情報から、Bの入金処理情報を作成する (べき等性のある処理)
  3. Bの口座残高を増やし、入金処理情報を処理済みにする (トランザクション処理+ べき等性のある処理)

ポイントとしては、次の2点です。

  • (a) トランザクション処理で、クリティカルな部分を操作 (口座残高を減らしつつ、出金処理情報の作成など)
  • (b) べき等性のある処理で、EntityGroupから他のEntityGroupに情報を伝搬

今回は、トランザクション処理で「~操作」というエンティティを切り出し、それを再試行可能になるようにべき等性を保証しながら、別のEntityGroupに移し変える作業を行いました。 これは強力なMessage Queueがあれば同様のことを行えますが、App Engineにはそのようなものがないので、ユニーク制約や不可逆な変更とTask Queueを利用して同様の機能を実現させようとしています。 EntityGroupを小さくしたまま、EntityGroup間のデータ移動を安全に行っているため、それなりにスケーラブルで堅牢なシステムになりそうな感じではあります。ただ、SQLで1行で書ける内容にしては非常にめんどうです。

なお、上記処理では「dirty readが発生する」という点に注意が必要です。AからBの送金処理をアトミックに行った場合、その前後でAとBの残高の和は一定額になりますが、「送金してる途中」という状態を挟む関係で残高の和が一定にならないタイミングがあります。 整合性のレベルはEventually Consistentとなりますので、重要なデータが外に漏れないようにうまく設計する必要があります。 また性質上、最初のトランザクション処理以外で制約を含むデータの更新を行うのが困難です。例えば、送金先の口座残高に上限がある場合などは、入金処理エンティティを出金処理エンティティに書き換えて、元の口座に送り返す必要があります(元の口座も上限に達してたりすると大変なことになりますが)。

ちなみに、上記の考え方はApp Engineと別のクラウドサービスを組み合わせるときなどにも利用できそうです。その場合、べき等性のある処理でまたぐのはEntityGroupではなく物理的なサーバになります。

7 件のコメント:

  1. 基本的にGoogleのNickさんが書かれているのと同じだと思いますが,いかがでしょうか。

    http://blog.notdot.net/2009/9/Distributed-Transactions-on-App-Engine

    ダーティ・リードを防ぐには,口座情報を読む前に,毎度「状態」をチェックして,未処理だったら待つようにすれば防げると思っています。性能的にきついですが。いかがでしょう。

    安東@日経SYSTEMS

    返信削除
  2. 情報ありがとうございます。基本的に同じ流れで安心しました。

    ダーティーリードについては、ご指摘の通り状態に対してスピンロックすることで送金元に関する影響を最小にできると思います。
    ただし、(2.a)->(3)->(2.b)の順で進んだ際に、(3)->(2.b)のタイムラグで(Aの残高+Bの残高)が送金前より増えてしまうという全体視点で別のダーティリードが発生します。今回のケースでは、(Aの残高+Bの残高)が「送金前と同じかそれより少ない」という制約で考えてみたので、上記のような流れになりました。

    返信削除
  3. すいません。Nickさんのエントリは元々松尾さんに教えていただいたものだと後で気付きました。。情報の行き違いでしょうか。


    なるほど。(2.a)->(3)->(2.b)というダーティ・リードは,楽観的ロックである限り,防ぎきれないんですね。。頭が悲観的ロックになっていました。

    難しいですね。。

    安東

    返信削除
  4. >安東さま
    ダーティリードは、トランザクション処理を分断していることが原因で発生します。逆に、同一EntityGroupに対する処理では、基本的にはダーティリードは発生しません。
    スピンロック用の情報をどこかに書きこんだとしても、その情報自体がトランザクションから分断されていると、整合性のレベルとしてはStrongly Consistentを実現できません。そのため、上記のように分散トランザクション処理を行う例では、いまのところEventually Consistentが限界になると思っています。
    そのため、先に行ったほうのトランザクション処理の結果は、「全ての処理が完了する」前に読めてしまいます(この文脈でのダーティリードがこれです)。「全ての処理が完了した」という情報を同時に伝えるためにもトランザクション処理が必要なので…といった具合に、Strongly Consistentの実現は難しそうです。

    的外れでしたらすみません。

    返信削除
  5. あらかわさま

    コメントありがとうございます。楽観的ロックとか関係ないと後で気付きました。こちらこそ的外れですいません。


    もう一つ大きな訂正です。お気づきと思いますが,Nickさんのロジックは微妙にあらかわさんのものとは違っていました。

    Nickさんのもトランザクションは三つですが,
    tx1で(1)のみ
    tx2で(2.a)+(3) 状態をいきなり「処理済み」にする
    tx3で(2.b)
    となっています。

    Nickさんの場合,各txにおいて,更新処理がEntityGroupに閉じているため,スピンロックでダーティリードが防げそうに思えます。。

    tx1とtx2の間
     口座Aは読めない,口座Bは古い残高が読める
    tx2とtx3の間
     口座Aは読めない,口座Bは新しい残高が読める
    tx3のあと
     口座A,Bとも新しい残高が読める


    両者の違いや,Strongly Consistentが本当に可能なのか,きちんと検証するのは私の能力を超えています。ぜひご検証を。。。
    (また誤りが含まれていたら,どうかご容赦ください)

    安東

    返信削除
  6. >安東さま
    なるほど。確かにNickさんのやり方のほうがトランザクション処理の効率がよさそうです。私のやり方では、(2.a), (3)でトランザクションを分離していますが、よくよく考えたらこの分離は必要ありませんでした。同じEntityGroupですので一気にやったほうがよさそうですね。

    もう一件こちらの勘違いなのですが、安東さまがおっしゃるようにスピンロックをかけてダーティリードを防ぐ方法が確かに存在します(片方だけ読めない状態もdirtyとして考えてしまっていました)。これは2-phase commitのようなプロトコルをソフトウェアで作るイメージなのですが、ちょっと長くなりそうなので、上記改善も合わせて後日別エントリでご紹介しようと思います。大変失礼いたしました。

    また、ご指摘非常に助かりました。ありがとうございます。

    返信削除
  7. また,間違ってなくて安心しました(^^)

    次のエントリ,期待しています! Nickさんのエントリは,「分かっている人には分かるよね」的な書き方で,理解するのがとても大変でした。「ほら,簡単だろ」とか書いてあるのですが,「あんたには簡単かも知れんけど,わてら凡人には難しい!!」とか,突っ込み入れたくて。。

    > 2-phase commitのようなプロトコルをソフトウェアで作るイメージ
    また丁寧で分かりやすいエントリ,期待しています。勉強させてください!

    安東

    返信削除