2009年11月24日火曜日

分散トランザクション処理の最適化

前回の「送金のトランザクション処理パターン」では、EntityGroupにまたがるトランザクション処理について簡単に紹介しました。

様々なコメントいただきまして(ありがとうございます)、どうやら「Distributed Transactions on App Engine - Nick's Blog」のやり方が非常に優れているようですので、今回は「送金のトランザクション処理パターン」で紹介した手法に最適化を施して、Nickさんのやり方に近付けてみようと思います。

今回紹介する最適化は、前回のような「狭い範囲のACIDトランザクション」と「べき等性による処理の伝搬」を組み合わせた分散トランザクション一般に適用できそうな手法です。そんなに大層なことはしていませんが、例によってまだ構想段階ですので、また至らない点があればご指摘いただければ幸いです。

おさらい

送金のトランザクション処理パターンでは、次のような図でトランザクションの流れを紹介しました。

このうち、実際の処理の部分だけを抜き出してみると、次のようになります。

上図の四角であらわした部分はApp Engineのトランザクション処理を利用する部分で、矢印であらわした部分はべき等性を利用して処理を伝搬しているところです。ここでのポイントは2点でした。

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

なお、前回に書き忘れてしまったのですが、ここでの「べき等性(idempotency)」は数学におけるべき等よりも少しだけ条件を増やしています。

  • (a) 1回成功すると、2回目以降は作用を起こさない
  • (b) 何度失敗しても副作用を起こさない

コンピュータの世界では、頻繁に「操作が失敗する」ということが起こりえます。前回のエントリや今回のエントリで使っている「べき等」という用語は、上記のように失敗した場合の作用についても規定しています。上記2つを組み合わせると「無限回繰り返すと1回だけ作用が起こる」という性質をもつようになりますので、送金処理では「入金レコードを1回だけ反映する」などのトランザクション処理を適用できない重要な個所で使っていました。

最適化の流れ

さて、前置きはこれくらいにして前回のトランザクション処理に、実際に最適化を施してみましょう。

依存関係のグラフを作る

最適化を行う際に、最初にやることは「処理の流れの整理」です。 前掲の処理の流れを「依存関係のグラフ」に書きなおします。

矢印は依存先の処理に対して伸びていて、前の処理に依存する項目を青い字で、それに依存される項目を赤い字で書いています。

先ほどの図では4つの箱(トランザクション処理)が直列に並んでいましたが、新しい図では(2.b)と(3)が兄弟関係になりました。(3)は(2.b)に依存しないため、上図のようになっています。

トランザクション処理を結合する

各トランザクション処理の依存関係を洗い出したら、次にそれらのトランザクション処理のうち結合可能なものをまとめていきます。ここで使う規則は同じEntityGroupに対する処理はトランザクションで処理できるというものです。

結合可能なものを洗い出すため、対象のEntityGroupごとに色分けしてみます。

すると、(1, 2.b), (2.a, 3)というペアができました。このうち、(2.a, 3)のほうは依存グラフ上で隣接しているため続けて実行できます。この二つを合成してみましょう。

(2.a, 3)を組み合わせたことで、トランザクション処理の回数が1回減りました。残りの部分は交互に色分けされて直列に並んだので、これ以上トランザクションの合成はできなさそうです。

これだけでも動きますが、もう少しだけ単純化します。 なお、結合可能なトランザクション処理を、常にまとめるかどうかは難しい問題に思えます。あまり長すぎるトランザクション処理を行うと、楽観的並行性制御によって常にその処理が失敗するようになるかもしれません。 並行して変更される頻度や、トランザクション処理の長さとの兼ね合いで、結合するかどうかを決めるのがよさそうです。

べき等性に関する処理を除去する

トランザクションが分断されていたころ、個々のEntityGroupへの値や処理の伝搬はべき等性を利用して実現していました。先ほどの最適化のプロセスで、(2.a, 3)のトランザクションを結合したため、従来の(3)に関するべき等性の保障が冗長になります。

べき等性の担保に利用した部分を2重線で消してみました。追加した個所は赤字で記述してあります。 入金処理エンティティの情報をほとんど利用しなくなったため、入金処理エンティティのかなりのプロパティを削減できます。送金番号のユニーク性を保証するだけになりそうです。

これらを組み合わせると、次のようになります。なお、利用しなくなったプロパティは取り消し線を引いてあります。

上記の手順で、Nickさんの紹介する分散トランザクションとほぼ同じになったと思います。 このように、分散トランザクション処理を考える上で、初期状態で多少無駄があっても最適化を施すことで様々な部分を簡略化できそうです。

ちなみに、スタート時点では次のような感じでした。

まとめ

今回の流れをまとめると、次のような3ステップでした。

  1. 依存関係のグラフを作る(トランザクションを結合しやすくする)
  2. 同じEntityGroupに対する隣接するトランザクションを結合する(色分けするとわかりやすい)
  3. 結合したトランザクション処理から、べき等性の担保に使っていた無駄な個所を除去する

あるていど機械的な手順で、「ACIDトランザクション+べき等性による情報の伝搬」で作られた分散トランザクションを最適化できました。よくよく考えるとこの送金処理に関するパターンはBASEトランザクションの特性を持っているので、そちらの世界の知見を使うのがよさそうです。

ちょっと長くなりすぎたので、一度ここでエントリを終了します。 次では、コメントでいただいた「eventually consistentの整合性でdirty readをどうやって抑制するか」という点について考察してみます。

0 件のコメント:

コメントを投稿