2013-05-12
全IT関係者が知っておくべき「1-copy-snapshot isolation」
snapshot isolationを分散環境に適用する場合の「基本」の内容のまとめになります。（基本自分用のメモなので、間違っていたらすみません）
まずワーディングの整理
・snapshot isolation
TXの分離レベルとしてのsnapshot isolation（以下SI）は、現在のRDBMSのTX管理では、ほぼ実装的にはデファクトと見ていいと思います。ただしANSIの規定のISOLATION_LEVELには定義がないので、どのあたりに位置づけるのかは、DB実装のそれぞれの取り扱いにより異なります。とはいえ、どのDBでもほぼSERIALIZABLEに近い位置づけにしているところが多いですね、というか、SI（特にSerializable SI）ぐらいでないとserializableに現実的には近づけないというのが実態かと思います。（勿論理論上はS2PLで実装は可能ですが、まぁパフォーマンスがアレすぎるので）
この上で・・・
・snapshot isolationと分散環境の親和性
ちょっと考えればすぐにわかりますが、めちゃめちゃ高いわけです。基本的にsnapshotの実行先＝別ノード（別プロセス）と見ればよいわけです。read-onlyなTXであれば、そのまま別プロセスで実行することで、単ノードであろうと、分散ノードであろうと、ほぼ透過的な扱いにすることが可能です。要するに、snapshotをとることとreplicationの実行することが、まぁ基本的に同じ（厳密には全然違いますが）と見なすことで、なんとなく同じようなことができそうだ、という匂いはするわけです。んで、まぁ実際、この分散環境下でのsnapshot-isolationは、割と応用範囲が広い感じで受け止められているので、一応、ほぼ今後の分散トランザクションのデファクトとして見てよいでしょう。基本として押さえておくべきです。・・当然、更新が問題になるわけですが。
ここで、1-copy-snapshot isolationに入る前にですね・・・
・1-copy-hogehoge
一般に1-copy-hogehogeという場合は、「単ノードで実現できていたhogeghogeが分散環境でも透過的に達成できる」ことを意味します。たとえば 1-copy-serializableということであれば、単ノードでの処理がserializableな実行を、そのまま“同じように”分散環境で実行できる、ということを意味します。それでよくあるのが、単ノード環境でのACID特性をそのまま分散環境でも実行できます、という概念で、1-copy-atomicityとか1-copy-isolationという言い方をします。1-copy-durabilityというのもありますね。例えば、1-copy-okachimachiというと単ノードのokachimachi属性が分散環境でも透過的に実現できているという感じです。
よってここでいう 1-copy-snapshot isolationということであれば、これは単ノードで実行できていたsnapshot isolationを分散ノードでも実行できるということを意味します。そもそも「同じ」ってのはどういうことかっていう議論はあるのですが、まぁ端(client)から見ていて同じに見えるという意味でここでは逃げましょう。尚、Txの世界では、「同じ」っていうことは、より厳密にいうとTxを構成する一連の手続きの意味論が同じある種の系に属する、という事になります。
・1-copy-snapshot isolation詳説
というわけで、個人的に、ほぼ世界の常識として「全人類が知っておくべき1-copy-snapshot isolation」を順を追って解説しておきます。というか、割と簡単なんですけど、transaction系のお話は、忘れる時は忘れるので、メモっておきます。（以下はある程度replicationの常識がわかっている前提もありますが、面倒な人は下の方のバリエーションを読めばわかると思います。）
1) eagerかlazyか
基本eagerです。というかlazyはそもそも本来的に一貫性が取りにくいです。lazyだとupdateのconflictがcommit後に検出されるので、そもそもserializableとかそういう議論にはなり難いです。一回commitしたやつをひっくり返すとかアレ過ぎますからね。
propagationは、基本的に非対称(要するにSQLコピー丸投げじゃなくて、差分binary的なアレ)でwrite-setを取得して、取得各replicaへ転送します。commitのタイミングは通常、write-setを取得した段階で行われます。・・・そしてここが話題になります。
2) primary-backupとupdate-anywhere
両者あります。現行の運用レベルでみれば、妥当なものはprimaryだと思いますが、今後のマルチDCとかgeo-replicationとか考えると、ある程度update-anywhereも想定した方がよいと思われます。とはいえ基本的にROWAをベースに敷いています。まぁfull-replicationが基本ですね。部分replicationにすると、後述のvalidationのタイミングで結論が一致しないという可能性も出てきます。（なので、そのときどうするか、ということで対応策が別にあります。）
尚、full-replicationは、write-intensiveになるとスケールアウトがしづらいので、モデルとしてのROWAはわかりやすく優秀だとは思いますが、現実路線を見たときに部分replicationを考える必要があると思っています。ただし、これはデータのパーティショニングがベースになるはずなので、むしろ業務的なデザインの問題になるはずです。（必要なデータのすべての一斉更新とか、ROWAだとほぼ最悪の処理に近いはずですが、しかし至極普通にあるわけですよ。）
3) centralizedとde-centralized
snapshot isolationは基本的にoptimistic concurrency controlです。従ってcommit validationをどこでやるか？ということが問題になります。centralizedは一カ所で、de-centralizedは複数箇所で行います。可用性を考えればたぶんde-centralizedだと思いますが、とはいえ、実装や品質を考えるとcentralizedも検討の範囲ではあると思います。ただし、これもマルチDCとかgeo-replicationとかを考えるとde-centralizedが必要になります。
ということを踏まえた上で・・・基本となるパターンを順番に列挙していきます。
■ベースプロトコル：
まず前提として、Txをパースした時点でread onlyかwriteを含むかを判断します。
read only Tx：Tx開始時点にアサインされた、各replicaローカルの最新のversionを読みます。readがwriteにブロックされません。
write を含むTx：書き込みはすべて一度ローカルに書き出します。ただしコミットされるまでは、書き出したTx以外は触れることはできません。
commit：optimistic concurrency controlです。write操作を含むTxについてはcommit時点でTxの成否を判断します。基本的にTx開始時点のtimestamp(tx_begin)とcommit時点の最新のversionのtimestamp(current_version)を比較して、後者が前者よりもあと（timestamp(tx_begin)<
timestamp(current_version))の場合はabortする、いわゆるfirst-commit-winルールを適用します。
validationに成功した場合は、書きこまれたその値を最新versionにし、各replicaにばらまきます。
尚、仕組みとしては、全順序が分かればいいというレベルの要求になります。順番がわからないとアウトです。
■バリエーション:
まず共通のケースモデル：
Tx1 w1(x)c1
Tx2 r2(y)w2(x)c2→a2
Tx3 r3(y)r3(x)c3
Tx4 r4(x)r4(y)c4
history:w1(x)r2(y)r3(y)c1r4(x)w2(x)c2→a2r3(x)c3r4(y)c4
Tx1からTx4まですべてconcurrentになりますがTx1とTx4はオーバーラップしません。
Tx2ではxを書きにいきますが、c1が先になっているので、first-commit-winで負けてabortになります。
Tx3/Tx4はread onlyなので、replicaで処理されます。
1) Primary-backup & Central
もっとも単純でわかりやすい。これ以降はこのバリエーションになります。
Txはすべてcentral middlewareで一回ハンドリングします。read-only Txと判断できるときは、指定したローカルreplicaに処理を飛ばします。ここではTx3→secondary1 Tx4→secondary2にアサインします。writeを含む、read-only Tx以外のTxについては、writeをprimaryで処理します。commitリクエストが来たタイミングで、primaryからwriteの内容（write set）を取得して、validationを行います。成功した場合はコミットをprimaryに書き込んで、write setを各replicaに配布します。各replicaはコミット順に配布されたwrite setを自分のローカルでupdateしていきます。・・・以下具体的に
・w1(x) Tx begin。primaryに書きだす。
・r2(y) Tx begin。writeもあるTx。まずはreadをsecondary2へ飛ばして、y0を取得。
・r3(y) Tx begin。read-onlyで、処理はsecondary1へ飛ばす。
・c1 Tx1 commit。書き込まれたwrite set(以下ws) を取得、xの最新versionはx0なので、validationはOK。新しいversionを生成(x1)。その直後に、wsを各secondaryに配布し、各secondaryはそのwsを更新し、versionを生成。
・r4(x) Tx begin。read-onlyで、処理はsecondary2へ飛ばす。ただし、既に最新versionは更新されているので、読む値はx1になる。
・w2(x) primaryに書きだす。
・c2→a2 Tx2 commit。書き込まれたwrite setを取得、xの最新versionはx1なので、すでに更新済み。Tx開始時点のversionはx0なので、validationはNG。よってabort
・r3(x) secondary1でread。ただし、Tx3のbeginがc1よりも前なので、取得するxはx0
・c3 Tx3 commit。
・r4(y) secondary2でread。y0を取得。
・c4 Tx4 commit。
2) Update-anywhere & Central
Update-anywhereではprimaryが存在せず、すべてreplicaになります。従って、writeは一義的に、各replicaに書き込まれ、他のreplicaに伝播します。ただしvalidationの制御はcentral middlewareで行います。
Txのvalidation：
Txの成功条件は、「そのTxが開始した時点でのデータセットについての、書き込みについてコミット競合が発生していない。」です。
繰り返しになりますが、書き込みが競合するTx開始時点のtimestamp(tx_begin)とcommit時点の最新のversionのtimestamp(current_version)を比較して、timestamp(tx_begin)<timestamp(current_version)の場合はabortし、それ以外はcommitする、ということになります。んで、さらに「重要なのは順序であり、時間そのものではない」ということです。
仕組みとしては、それぞれのコミットのカウンターを利用します。コミットが成功するタイミングで、カウンターをインクリメントして、timestampの比較の代わりに利用します。
central middlewareが保持するもの
・成功したTxのカウンター (lastValidated)
・各replica R(j)でコミットされた更新Txの数 (lastCommitted[j])
・直前に成功したTxのSet (validatedSet)（どこかでGCするという前提）
Txが開始する時：
各TxにstartTsとして、開始時点の更新するreplicaのlastCommitted[j]をセットする
Commitリクエスト時：
・concurrentなTxで、wsが競合し、startTs<commitTsであるものがある場合はabortし、それ以外はcommitする。（判定するTxはvalidatedSetを逆から見ていく）
・成功した場合、lastValidatedのカウンターをインクリメントする。
・ローカルのlastCommitted[j]をインクリメント。
・TxのcommitTsとして、lastValidatedの値をセットする。
・当該TxをvalidatedSetにappendする。
・wsをreplicaの更新queueに積む。
値のPropagation：
・各replicaに積まれたqueueから順序を保って、ローカルの値を更新する。
・lastCommitted[j]++
以下具体的に・・・尚Tx1/Tx3はreplica Aで、Tx2/Tx4はreplica Bでそれぞれ分散処理をします。トランザクション単位でconcurrentに分散処理を行い、かつ全体で一貫性を担保する形になります。分散snapshot isolationの本領発揮になります。
initialization:
・lastValidated=0
・lastCommitted[A]=0
・lastCommitted[B]=0
・validatedSet=φ
・w1(x) Tx begin。startTs:=0 その上で、replica Aに値を書きます。
・r2(y) Tx begin。startTs:=0 readをreplica Bへ飛ばして、y0を取得。
・r3(y) Tx begin。startTs:=0 read-onlyで、処理はreplica Aへ飛ばす。
・c1 Tx1 commit。書き込まれたws1をreplica Aから取得。validatedSet に何もないので、従ってvalidationはOK。よって、commit versionを生成。
lastValidated=1
Tx1.commitTs:= lastValidated
validatedSet.append(Tx1)
それから、該当するws1を各replicaに飛ばします。まずreplica Aではコミット処理。んで、その他の各replicaはそのws1を更新し、versionを生成。加えて、lastCommitted[]++を処理。（ここではlastCommitted[A]=1 lastCommitted[B]=1)
・r4(x) Tx begin。startTs:=1(lastCommitted[B]) read-onlyで、処理はreplica Bへ飛ばす。既にversionは更新されているので、読む値はx1になる。
・w2(x) replica Bに書きだす。
・c2→a2 Tx2 commit。書き込まれたws2をreplica Bから取得。ここでvalidationする。
ws2∪ws1 でかつ、Tx2.startTS=0 < validatedSet.Tx1.commitTs=1なので、abort
・r3(x) replica Aでread。ただし、Tx3のbeginがc1よりも前なので、取得するxはx0
・c3 Tx3 commit。
・r4(y) replica Bでread。y0を取得。
・c4 Tx4 commit。
3) Update-anywhere & De-Central
2)と同様に、primaryが存在せず、すべてreplicaになります。同じくwriteは各replicaに書き込まれ、他のreplicaに伝播します。これに加えて論理的なvalidation制御のmiddlewareも分散させます。通常は、replicaとペアにして、制御ミドルをばら撒く形になるので、middle+replicaの形でノードをガシガシ足していく形のクラスターになります。文字通りの分散クラスターです。
middleware間の仕組みは、基本的に2)と同じです。順序保証ができていれば、validationが可能になります。つまり、「順序保証を前提にできれば、同じ種類のノードを足すことでスケールアウト可能な分散クラスター上で、一貫性を保証したsnapshot isolationのトランザクション管理ができる」というアーキテクチャになります。要するに（本当にうまく行けば）無敵です。
分散クラスター上でのトランザクション処理として、このアーキテクチャが有力視されていることは、なんとなくわかると思います。（ただし、write setを各replicaで飛ばしっぱなしになるので、障害発生時の復旧は、それなりに考えないといけません。ということでここが話題）
基本的な仕組みは2)と同じですが、各replicaがmiddleware機能を持っています。
各middlewareが保持するもの
・自身のreplicaでコミットされた更新Txの数 (lastCommitted)
・直前に成功したTxのSet (validatedSet)（どこかでGCするという前提）
Txが開始する時：
各TxにstartTsとして、開始時点の更新するreplicaのlastCommittedをセットする
Commitリクエスト時：
・wsを取得して、validationのためにマルチキャストする。ローカルな場合は手元で処理します。
・各replicaで、wsが競合し、startTs<commitTsであるものがある場合はabortし、それ以外はcommitする。（判定するTxはvalidatedSetを逆から見ていく）
・成功した場合、lastCommittedをインクリメント。
・replicaを更新
・TxのcommitTsとして、lastCommittedの値をセットする。
・当該TxをvalidatedSetにappendする。
以下具体的に・・・尚Tx1/Tx3はmiddleA-replica Aで、Tx2/Tx4はmiddelB-replica Bでそれぞれ分散処理をします。
initialization:各replicaのセットアップ
・replicaA.lastCommitted=0
・replicaA.validatedSet=φ
・replicaB.lastCommitted=0
・replicaB.validatedSet=φ
・replicaA w1(x) Tx begin。startTs:=0 その上で値を書きます。
・replicaB r2(y) Tx begin。startTs:=0 y0を取得。
・replicaA r3(y) Tx begin。startTs:=0 y0を取得。
・replicaA c1 Tx1 commit。書き込まれたws1をreplica Aから取得。ブロードキャスト。
ローカルでは、validatedSet に何もないので、従ってvalidationはOK。よって、commit version(replicaA.x1)を生成。
replicaA.lastCommitted=1
Tx1.commitTs:= replicaA.lastCommitted
replicaA .validatedSet.append(Tx1)
ブロードキャスト先（replicaB)でも、validatedSet に何もないので、従ってvalidationはOK。よって、commit version(replicaB.x1)を生成。
replicaB.lastCommitted=1
Tx1.commitTs:= replicaB.lastCommitted
replicaB .validatedSet.append(Tx1)
・replicaB r4(x) Tx begin。startTs:=1(replicaB.lastCommitted) readで読む値はx1になる。
・replicaB w2(x) replica Bに書きだす。
・replicaB c2→a2 Tx2 commit。書き込まれたws2をreplica Bから取得。ブロードキャスト。
ローカルでは、ws2∪ws1 でかつ、Tx2.startTS=0 < replicaB.validatedSet.Tx1.commitTs=1なので、abort
ブロードキャスト先（replicaA)でも、ws2∪ws1 でかつ、Tx2.startTS=0 < replicaA.validatedSet.Tx1.commitTs=1なので、abort
・replicaA r3(x) read。ただし、Tx3のbeginがc1よりも前なので、取得するxはx0
・replicaA c3 Tx3 commit。
・replicaB r4(y) replica Bでread。y0を取得。
・replicaB c4 Tx4 commit。
以上になります。
一応、よくわからん人向けに3行で説明します。
・一応分散環境で特に制御の頭とかいない
・readは好き勝手どこでも読んでよい。writeも好き勝手どこに書いても良い。
・writeはどこかで同時に起きているTxで先にコミットされたら負け。
たったこれだけで、Txの一貫性が担保される仕組みです。
あとは補足的な感じで
・正常系は申し分ないが、障害対策はちゃんと考えないとまずい。
特にコミットの耐障害性をあげる必要があります。validationの結果の同期が障害でずれた時にはちょっとまずいことになります。今までの方針では2PCが有力でしたが、これもPaxosを利用する方針が広く検討されつつあります。このあたりのアレヤコレヤがWalterだったり、MDCCだったりします。この手のものは、勿論、どれもナイーブなSIではありません。が、達成すべきクライテリアとしては、明確に1-copy-SIが言われることが多いです。
・SSIに拡張できる。
とはいえ、この基本になるプロトコルはwrite skewは排除できません。なので、SSIを導入することになります。基本的にr-wのanti-dependencyのグラフ構造が抽出できればいいので、問題は、分散環境でこのグラフをどう作るか？ということになります。あとでまた、まとめますが、一応できてます。えっと、当然write-setの持ち回りにanti-dependencyの情報を持たせて、一斉に飛ばす形になるのですが、read-setも一緒に配ると崩壊するので、工夫します。えっと、さらに判定基準をちょっと工夫しないとまずいので、replicated serializable snapshot isolation(RSSI)という形でちょっと拡張してます。・・・ぶっちゃけ、この手の論文は、デフォルトで分散SIとSSIがわかっていないとまじめにダルマさん状態になります。
・書き込みのフルバッチには弱い、とはいえある程度のwriteの負荷には強い。
読む方はほぼ無敵でしょう。分散クエリーの実行基盤としては申し分ないでしょう。ただし一般的にこの手の分散トランザクション処理は、特に書き込みフルバッチには、極端に弱いという宿命を持っているので、まー実務上はわけて考えるべきでしょうね。とはいえ、ベンチマークでもwriteに強いのはそこそこ立証されていますので、普通の負荷の読み書き程度であればほぼ問題ないでしょう。
・結局Transactionは要るのか？
そもそもNoSQLの世界でTXとかいるのか？という議論ですが、今のところ要りますね、という結論のようですね。たとえばよく言われるのは、wallへの書き込みの順序性の確保ですね。順序がばらばらになると会話が成立しません。んで、これは一種のconstraintになるので、TX制御の話になります。（今はなんか手書き実装とかしているという話もあるようですね。）まぁ、某石割り先生のように「No ACID is No Interest」と言い切るのアレすぎるとは思いますが、似たような人は多いかと。
・個人的見解
いずれにしろ、分散であろうと単ノードであろうcorrectのコンセプトは維持していかないとそもそも議論の土台にものりません。特にconstraintについては追加的にいろいろ議論は発生すると個人的には思っています。SSIでカタがついた、という見解もあるとは思いますが、果たしてそうなのかという気もしています。そもそも、SSIにしても制限的にしているので、serializable全体の集合をカバーしているわけではないですからね。我々の知らない抜け道がまだある、と考える方が妥当でしょう。・・・なんかこう数学的な話にはなりますが、そういうものかと。いずれにしても基本は変わらないでしょう。
それはさておき、もう普通にハイパフォーマンスな分散Txがserializableに近い形で利用できる状況になりつつあります。基本になっていた全順序問題は、Googleのspannerが地獄の釜を開けてしまった感もあり、たぶん怒濤の開発競争になっていると思います。某東洋の島国の立ち後れ感は、ぱない感じですが、皆さん頑張りましょう。
Permalink | トラックバック(0) | 16:38
2013-04-28
IT系サッカーファンはどのチームに注目すべきか
勿論ネタだ。たまにはいいでしょう。
まず、IT系の人間で、スポーツ好きはサッカーファンがおおいような気がします。いや、単に主観なだけという説もありますが。これは、サッカーの特長が「戦略」だったりすることも多少は影響していると思います。まぁ要するにIT屋さんはシステマティックなスポーツが好きだったりするわけで、よって隠れバスケ・隠れアメフトファンも実はそれなりにいらっしゃいますが、やはりサッカーファンが多いでしょう。
さて、どうでもいいですが、ひいきのチームごとに、その性格がカテゴライズできるので、ちょっとまとめておきますよ。
サッカーといえばスペインなわけです。いや、プレミアだろうとか、日本人ならブンデスだろうとか、基本はセリエでしょとか、いやいやリーグ・アンは捨てがたいとか、どうでもいいです。ユーロ・ワールドカップ・ユーロと事実上の世界選手権３連覇している国が最強ですよ。何言っているんですか。（代表とクラブは違うだろうという意見はもっともなのですが、面倒なので一方的に却下します）
ここで、超主観の「IT屋的分類とスペインリーグのひいきのクラブチームの相関」です。
断っておきますが、完全にネタですよ。いいですね？
・・・・・
バルサ：真のアジャイラー
レアル：ミーハーなアジャイラー
ビルバオ：隠れWFなアジャイラー
アジャイラーしかいないのか？という事ですが、一応アジャイラーしかいないと仮定します。だって皆さん好きでしょう？アジャイル。話題だし。やるやらないのは別として。（正直アジャイルかどうかなどは、このレベルのネタでしかないですよ。そこ問題じゃないし）さて順番に・・・
バルサ：
現時点世界最強。70％のボールポゼッションがあれば、8割は勝てるという理論の実践と、他がまったくまねできないパス回しは、完全に別格です。あれはもうエスパーの世界です。ほぼSFです。メッシの得点数とか、サッカーの得点ではないです。もう野球か、バスケの範疇。大体、マークついているのに、マーカーなんぞいないも同然とか意味分かんないし。
ということで、真のアジャイラーはバルサを目指すべきでしょう。プロジェクトコントロール率は常にリアルタイムで70%強を目指す。チケット回し・連絡・連携・報告・相談・進捗管理・情報共有のショートパスはセンチメートルの精度でお願いしたい。完全にできれば、ほぼメッシ並みのゴールゲッターが生成できます。多少の障害があっても、サクッと躱せます。ただし、カンテラよろしく、人材育成が鍵になります。一撃でエスパーなみの連携は不可能なので、そこが課題ですが、乗り切れば世界最強。まぁ雰囲気的にはそんな感じです。
レアル：
目標はバルサ。これは間違いない。しかし、あのパス回しははっきり言って完コピはマジで無理。やはり、最後の力技を外すわけにはいきません。サッカーは最後はガタイで勝負ですよ。微妙にチーム熟成に時間がかかっていますが、プラクティカルという意味では、バルサ以上かもです。
ミーハーアジャイラーはここを目指すべき。理想は理想で距離をおいて、まずはできるところから始めましょう。真のアジャイルの劣化コピー？多いに結構。劣化コピーで何が悪い。多少の精度はおちても最後の最後はヘッドで押し込むスタイルは、有無言わさない。最後は納期通りに出来たもん勝ちですよ、システム構築とはそーゆーものです。「それは正統派アジャイルではない。」何言ってるんですか、うるさいですよ。できればいいのです。まぁ雰囲気的にはそんな感じです。
ビルバオ：
さて、勿論、マニアックなIT屋なら選択の余地はありません。一択です。ビルバオです。つまりビエルサです。ご存知、元チリの代表監督、サッカー戦術ヲタクを通り越して、サッカー界のマッド・サイエンティストとまで言われるビエルサです。趣味はサッカーの試合のビデオ収集ですが、なにか？的なアレです。ビッククラブのオファーを断って、自分のこだわり優先とかプロです。んで、こいつがまた、超ウルトラ・スーパー・システマティック・サッカーなわけです。ぶっちゃけ、あの通りにやるとサイドバックが超人的な負荷で死ぬはずなんですが、なぜ死なないのかわかりません。誰か教えてください。（尚、サッカーヲタクという意味では、ビエルサに比肩するような人材も日本に来てましたけど、・・）
アジャイル的な進め方や試合運びは好きだけど、やっぱり形式的なカタチや決めごとはそれなりに大事だよね、というtype safeな貴方にぴったりなスタイル。是非、ビエルサを目指すべきでしょう。動的なスタイルなかに、約束事を決めて行く。それをそれこそマニアックに追求して行く姿こそ望ましい。プラクティカルかつ必要な要素を切り出し当てはめていきましょう。アジャイルと言いつつWFのいいとこ取りをしつつ、やりすぎちゃって、気づいたら周りから冷たい目線「それなんてWF？」。なんてのもOKです。まぁ雰囲気的にはそんな感じです。
・・・まぁどうでもいいわけです。
というわけで皆さん額にしわ寄せて、クラウドがどうだとか、ビッグデータが金にならんとか、アレだコレだとか議論するんじゃなくて、もっとお気楽に構えましょうよ、とか思うわけですよ。（遠い目
Permalink | トラックバック(0) | 14:28
2013-04-14
「オンプレミス・システムの終わり」の始まり〜AWSでのミッションクリティカルシステムの稼働
個人的には割と大変だったので、その辺をまとめておきます。
ニュースリリースはこちら。
http://www.nautilus-technologies.com/topics/20130409.html
要するに本部系バックエンド基幹システムの「一式」のクラウド移行です。完全なミッションクリティカルシステムで、止まった段階で業務に確実に影響が出ます。
システムの機能概要
1.売上の確定処理と債権管理
POSデータの直結です。売上確定処理を行います。同時に債権管理も行い、F/Bからの入金データをそのままつなぎ込み、入金処理・債権の消し込み処理を実行します。マッチングは自動処理できるものは処理を行い、ヒューリスティックなものはユーザー判断に従います。
2.仕入・費用の計上と確定処理、および支払いデータの作成
費用・在庫の計上確定処理です。当時に支払データの確定処理を行います。EDI（BMS）との連携を行っているため、支払については電子データで照合マッチングを「伝票明細単位」で行います。明細単位で処理を行うため、オープン・インボイスは全部取り込みます。結果として一度の処理では三千万件程度のマッチング・バッチが走ります。ミス・マッチ処理の結果は、アンマッチの原因単位でグループ化したあとでユーザー判断を促します。
3.テナント管理、特にフィー計算
テナントマスターの管理と、売上・仕入・経費の計上を確定した上で、契約に合致したテナントフィーの計算を行います。テナント管理は、販売実績を確定させたあとで、費用計上分をネットし、必要な契約スキームを適用することでコミッション金額を確定させます。つまり最長のバッチフローとしては、売上確定->費用確定->テナント・コミッション確定->確定後の費用確定のロングバッチフローになります。これを日次で行います。
4.管理会計一式
上記の管理会計の一式を行い店舗別のSKU単品を論理在庫計算から、粗利を算出し、カテゴリー・店舗・組織別の全部の積み上げ計算を行い、日別・週別・月別・年度別の利益をデイリーで確定します。
（以上の仕組みは、すでに一部はパッケージとして販売・商談を開始しているので、どこかで中身はもっと詳細にでると思います。）
オンラインとバッチシステムの構成です。外部接続のインターフェイス数は600本強、主要画面数で600画面程度、一晩で走るジョブグループ数で200でバッチ本数で3000本弱、この間に処理されるデータ件数は最大で20億件弱に渡ります。開発期間は2年強。投入人月で600~700人月クラス。（最初の企画は3年前ぐらいからスタートで、結局、最後のC/Oまでかかわったのは、自分とSIサイドのPMさんの二人だけでした。のべ人数で200人以上は関わったと思いますが、出入りも激しいプロジェクトでした。）
バッチ処理は全てHadoopで処理しています。Hadoopでの業務バッチ処理では、おそらく現時点で日本に存在するものの中で、もっとも複雑なものの一つだと思います。ピーク時点では一晩で20億件のデータを業務処理する化け物のようなバッチのカタマリのシステムです。RDBMSだと現実的な時間で終わる事はないと思います。開発はAsakusaなのでできたというシロモノで、Hiveや素のMapReduceでやったら絶対無理です。
フロント画面はJavaScript。バッチ系はかなりサクッといったのですが、画面系は大苦戦でした。jsはもう少しなんかとしないと、まじでこの世から消えてほしいと関係各者全員が思ったと思います。（jsでの業務画面はどこもうまくは行ってないようですね。・・個別のフレームワークはそれなりにあるのですが、どれも品質やVupやトータルでの仕組みという意味では不十分なようです。）まぁとにかくSIも含めてかなりの大規模な仕組みです。
当たり前ですが、当初の想定はインフラはオンプレミス・システムです。一応形式上は某社の"クラウド"ですが、実態は専用空間をもらっているので、インフラとしては、ほぼオンプレと見なして構わないと思います。ハードとか丸見えだし。Elasticでもなんでもないし。なお、これだけの規模の仕組みなので、リリースは段階移行です。最初のリリースから9ヶ月経過で、全面C/Oという運びでした。
コイツを一式全部すべて、AWSに上げました。
これだけの複雑かつミッション・クリティカルな仕組みがAWSにあがっているのは、日本では間違いなく初めてでしょう。さらに業務系バックエンドを全面的にHadoopで行ったという例では、現時点では世界でも数が少ないと思います。
正直に白状しますが、個人的には絶対に「クラウドにあげることは、ない」と思っていました。これだけの大規模かつ複雑にして、ミッションクリティカルなシステムが万が一にもクラウドに、しかもパブリッククラウドに上がるようであれば、オンプレミスの存在価値は、個人的にはゼロです。10数年前であれば、汎用機かオフコンの化け物で動かす仕組みです。オープン系ですらバッチ・パフォーマンスが出ないので躊躇するレベルです。
なんでクラウドなんですか？オンプレじゃ駄目なんですか？
なんども言うとおり、開発当初はオンプレを想定していました。ところが、最初の段階リリースから、オンプレでのHadoopクラスターの運用（前述の通り某社の国内“クラウド”の一部を利用）がトラブル続き+サーバーのパフォーマンスがあまりに悪すぎました。これをどうにか解決するために、AWSに上げざるを得なかったというところです。順に解説します。
コスト・パフォーマンス
まずコスト・パフォーマンスですが、少なくとも、今回のシステムについて言えば、オンプレとAWSではほぼ2倍程度の開きがあります。世の中、いろいろなコスト・ベンチマークがありますが、その辺りに転がっているベンチマークは残念ながら、大抵はWeb系のread-intensiveなベンチになっている（またはTPC-CのようなものでもWrite-Readはバランスが取れているもの）ので、今回のようなバッチ処理を阿呆みたいに回すハード・コアなシステムでは参考になりません。この辺の重いシステムであれば、それなりにオンプレも善戦するのでは？というもくろみもあったのですが、蓋を開けてみればオンプレ側には残念な結果になってしまいました。正直、基幹系のバッチ中心のシステムでも確実に2倍〜3倍の開きはあります。これはオンプレ側にしてみると痛い。
運用周り
それでも、国内のクラウドベンダーがしっかり（クラウド的に）Hadoopを運用して、AWS並の可用性を出していれば、AWSには移行しなかったでしょう。（これはユーザーさんも同意見です。）やはり、Hadoopの運用はなかなか骨が折れます。しかも、このシステムは基幹処理用ですので、処理件数・プログラムともになかなかに強烈です。毎晩かなりの負荷がクラスターにかかります。稼働が一年近くになってくると、さすがにいろいろイカレてくるのですが、どうにも国内の某ベンダーさんは対応できませんでした。
一番やっかいなのは、ハード・OS系のバグや障害にHadoopの障害が重なるというケースでかつ、なかなか再現しない場合です。これはちょっとどうしようもない感じでした。自分たちはこのシステムとは別にクラウド上で既に業務処理をHadoopを連続で動かしているのですが、彼我の差はイカンともしがたいレベルにまで拡大していることを実感させられました。
現在、ビッグデータのブームもあり、各地でHadoopをオンプレでやってみるという動きが出ています。Hadoopは確かに導入しやすいので、その流れもあるでしょう。ただし、ミッションクリティカルで運用するには、相当な経験とノウハウが必要です。つまり直裁に言えば、普通は無理です。一部の例外を除き、全然お勧めしません。どうしてもやるなら、最低でも、いろいろと人的なコストが青天井になることは覚悟すべきです。
すなわち、コスト・パフォーマンスと可用性の両者でオンプレミスはほぼ完全に敗北でした。これでは移行するな、という方に合理的な理由が見つかりません。ユーザーさんとも相当協議をした上での移行です。（ユーザーさんサイドでも相当いろいろと社内調整をして頂きました。かなり大変だったようです。感謝しております。）
もともと開発はAWS上でずっと行っていたので、システム的な移行は別に作り替えのような大事ではないです。ただし、インフラ周りの整備は全部準備するという感じになっています。当然ですが、ストレートにAWSを全面的に信頼する、というナイーブな作りではありません。AWSのDCが一個丸ごとすっ飛ぶぐらいの障害は織り込んでの検討・構成にしてあります。そーゆー想定がそもそもどーなのよ？という意見はあると思いますが、クラウドで基幹やるならこの程度は想定しないと駄目だと思います。
ちょっと遠目で見ると・・
Hadoopに限らず今後の分散処理は普通にどこでも使われるようになるでしょう。この場合、オンプレでは日本の国内ベンダーの「現在」の技術力では、残念ながら運用が難しいです。出来たように見えても、結局人依存に加えて、長期運用になれば必ず破綻します。そもそもVupですら大事になってしまいますし、実際そうなっている案件も散見されます。少なくともHadoopのような分散系処理基盤はVupは鬼門だともっと知られてしかるべきです。特にリスク管理という側面からですが。・・ツールがあれば大丈夫だ、という意見も聞きますが、ちょっと考えが甘いと思います。
また、同時にハードウェアの寿命とソフトウェアの寿命の乖離に最初から手を打っておきたいところでもあります。オンプレの場合はもう5年後を待つ前にハードは間違いなく時代遅れになるでしょう。基幹系のシステムはソフトウェアは間違いなく10年はもちます。この辺りのバックエンドの業務自体は20年ぐらい変わっていないです。さすがにハード更新に合わせて、同じ物は二度と作りたくないのが人情です。正直、やっとこさ周りの改修やらその他いろいろ終わった段階で早速ハードがイカレ始めました、というのが容易に想像できるところです。これは避けたい。特に分散系になった場合に、5年単位でクラスターの入れ替えとか悪夢以外のなにものでもないです。
本部系の基幹システムは、種々にあるシステムの中でも、もっとも重いシステムの一つです。最後までクラウド化が無理だろうと個人的には思っていました。変な話ですが、いまでも思っています。基本はオンプレで、そもそもアウトソーシングのレベルですら躊躇するのが普通です。単純なWeb系のシステムや、バッチの切り出しのみ、または、ある一定のシステムのカタマリの移行ならともかく、今回は、本部系ほぼ一式というシステム群です。しかもバックエンドがHadoopです。こういったものがクラウドに上がる、いや、上げられるというのは今でもちょっと想像を超える感じです。
それがクラウドに上がりました。上がってしまいました。それもAWSです。
もう、オンプレミスのシステムとか要らないですよ。投入コスト・運用コスト・ハード寿命の短縮化等々、まったく割に合いません。ミッションクリティカルなものですらクラウドで動く時代になりつつあります。勿論今回のようなバックエンドの超絶ヘビー級のシステムをすぐにAWSのようなクラウドに上げろとはいいません。（実際問題、「現時点」で出来るベンダーは日本では非常に限られていると思います。基幹系システムというものがよくわかっていて、かつAWSに精通しているところだけでしょう。こんなもんAWSに上げるのは、他のベンダーは、先はともかく現時点では無理だと思います。普通にどうやっていいかわかんないですよ。）ただ、もう普通のサイズのシステムは、普通にAWSで実行できるのが現状です。
とはいえ、そのままAWSに上げられるのか？
コイツは微妙ですね。実際の今回のケースもあの手この手で工夫をした上での移行です。当たりまえですが、クラウド陣営の大本営発表をそのまま受け取るアホなやり方では、玉砕した時に手の打ちようがありません。信頼性の高い部分はどこか？低いところはどこか？最悪のケースをどうするのか？を考えて準備する事が必要です。
クラウドベンダーの“営業的”な矛盾は、「クラウドって本当に大丈夫なの？」の質問に答えるために「大丈夫です！」を連呼せざるを得ないところにあります。この「大丈夫ですよ大本営発表」ために、結果として「駄目だったときの対策」を明示できない形になります。駄目だったら対策を提示した途端に、「なにそれ？最初から駄目なことを想定するの？」と突っ込まれること請け合いだからです。これはあまりフェアとは言いがたいのですが、事実なので仕方がないでしょう。
この辺りは“ミッションクリティカル”の経験があるところのヘルプが必要だと思います。
どのくらいの工数でやったのか？
・・・あとこのインフラ移行をやったのが、うちのエンジニアが約一名です、ってのもちょっと特記すべき事項だと思っています。（当たり前ですが歴年の会社としての経験値が後ろにあるので、一人でやったという言い方はフェアではないですね。あとアプリサイドの移行はSI屋さんがやっています。）正直、個人的にはいくら弊社の守護神とはいえ、普通じゃない感じです。さすがにちょっとハイパーな動き方で、分単位で動きながら同時に五カ所に指示を飛ばすとか、やってました。自分とか周りのヘルプはまぁ逆にいうと指示出す分だけコストになるぐらいの勢いでした。彼の人でないと無理ですね。他の会社（他の人材）でこれができるか？というと、ちょっと厳しいかと。
自分のタスクは、声だしとか、ヤバかったときの切り戻しの交渉と土下座WBSの作成みたいな感じでした。あ、一応大枠のユーザー調整は自分やってます。とほほ。
これは環境がクラウドだからできた、というのは確かにあります。クラウドは腕のよいエンジニアをとんでもない勢いでレバレッジさせるという好例だと思いました。エンタープライズ（社会インフラ系）経験の豊富なウィザード級のインフラ・エンジニアを2年もAWSに専属で突っ込んでおけば、十分化け物にはなります。そんな感じかと。・・・これが普通になるとインフラの指示待ち人材は完全に仕事がなくなりますね・・・
企業のバックエンドの基幹システムが一式クラウドで動いている、というのは、個人的な想定よりも4-5年早いです。想定外ですが、世の中は大抵想定外なので、そーゆーことなのでしょうか。何度も言っても言い足りませんが、最後の最後まで躊躇しました。とはいえ、移行が必須だったというのも現実です。
最後に実際に弊社某エースの作業中の独り言だけ書いておきます。「これは・・・一筋縄ではいかないわ（汗」だそうでございます。いろいろありましたよ。そんな簡単じゃないですよ。まじめに。まぁとはいえ、できているという現実は直視すべきでしょう。
Permalink | トラックバック(3) | 13:33
2013-03-31
Making Snapshot Isolation Serializable 再考
Making Snapshot Isolation Serializable 再考
■2013年的な位置付け
まずちょうど年度の開始なので、今年は自分的にはRDBMS関連の位置付けとか整理しておきます。去年の後半あたりからの匂いですが、NoSQL的な発展と合わせて、本格的なDB回帰が始まっている感じです。NoSQL系のほぼ致命的な弱点の一つがtransaction処理であることは指摘も多いところです。要するにデータが書き込めても不整合が発生しますね、ということになってしまいます。これではなかなか使えない、というのが現状でしょう。
なので、RDBMの最良のノウハウであるtransaction処理とNoSQL的な分散処理をちゃんと整合性とれるようにしましょう、という自然な流れは従前よりもより強い要請が働くでしょう。(できるかどうかは別ですが。) それで、そろそろなんかその手のものがRDBMSサイドや分散処理系から出てくる感じではあります。
また、オンメモリー系にも焦点があたりつつあります。何度目だ？という話はありますが、まぁ不揮発性メモリーでの処理は従前のものとは根本的に違うので別物と見るべきでしょう。（「従来のDBをそのままメモリーに乗っけました」ってのは、普通に「RDBMのキャッシュ増やしました」というものとアーキテクチャ上の違いはあんまりないので、そうでないものが出てくると思います。）
ということで時代的にはRDBMSの技術の再投入が製品として、そろそろ出てくると思います。そんな流れで、次のDBのカタチも模索が始まるのが本年だと思います。RDBMSの、というかDatabase一般の、技術の柱の一つであるTransaction処理は一回復習しておきたい。特に、Transactionの中でもここ10年でもっとも進化した感もあるものの一つが、MVCCですが、これは分散処理との親和性も高いです。そのMVCCで現在もっとも実装されていると言われているSSI(Serializable Snapshot Isolation)は、個人的に再勉強の価値あり、という感じです。
(尚、MVCCと言っただけ「重い」という認識の方は時々いますが、かなり変わってきています。)
■概略
Snapshot Isolation(以下SI)はTransaction(以下TX)のIsolationの達成手法としては、現在では伝家の宝刀に近い技術です。基本的な流れはMultiVersion Concurrency Controlに属し、その実装手法として、商用のRDBMSではかなり実装されてきています。その上に、かなりの論争にもなって来ました。曰く
赤い会社「完全にserializableですよ。」
その他大勢「いや、SIではfull-serializableにはならないし。」
赤い会社「いや、ほぼ同じだし。」
その他大勢「なんだよ、ほぼ同じってww」
赤い会社「だからこのベンチマーク（TPC-C）でちゃんとanomalyなしだし」
その他大勢「いやだから、そのベンチマークがそもそもだな・・・」
あれやこれや・・・
（以上、脚色なし）
過去、そんな論争があったのがSIですね。ま、この辺りのガチンコ勝負は、DBを真面目に取り扱った人なら周知の通りです。最近ではやっとOSS(Postgres)でも実装されるようになって、その意味でも、その界隈ではもはや常識に近いレベルにまで来ていると思います。
SIではTX開始時点で当該TXで必要なデータセット（したがって、どうphantomを除去するかという問題も考慮する必要があります・・）のsnapshotを取ってきてそのデータセット上でread/writeの処理を行います。したがってまずデータが元データから分離されているので、repeatable readになりますし、また自分でwriteしたものは当該TXのライフサイクル内部では、自分で参照できます。その上で、commit時点で、他のTXでも参照することができるように値を書き出します。ただし単純に上書きするのではなく、追加的に別のversionを生成するという書き出しをとります。したがってversionが複数できます。よって、multi-versionになります。
concurrentなTXが走っている場合は、上書きにより前のversionが後続で読めなくなるanomaly(Lost Update)が発生するので、その不整合を防ぐためにいろいろ手を打つ必要があります。通常は先にcommitした方を勝ちにして、後続の書き込みをabortさせる、First-Commit-Winsを適用することが普通です。また、このSIは理論上リードロックが発生しないため、通常のS2PLのロック機構でserializableを保証するconcurrency controlに比べて、圧倒的にパフォーマンスが良いことは、特に異論のないところです。
ただし、データのセマンティクス上では、複数のTXが走っている最中に、同一の値を参照した上で、「別々のページ」にお互いに不整合が発生する書き込み処理を、きれいにisolateして行う事ができてしまうため、常に不整合が発生する可能性があります。これは上記のFirst-Commit-Winsルールを適用しても発生してしまいます。これが一般にwrite skewといわれるanomalyで、特にSIでは厄ネタでした。
上記の赤い会社の論争は実は赤い会社のデフォのSERIALIZABLEのisolationレベルの実装がSIになっていて、（その結果、当然他社のDBのSERIALIZABLEよりも超絶ぶっちぎりで速い、だがしかしanomalyが発生するわけ・・）んで、各社が何そのプロレスみたいな反則w？とお互いに釣りネタ満載の場外乱闘になっていたわけです。
そんなこんなで、まぁ単純なSIではserializableにはなりません。無敵ではないということです。ところが、このSIをSerializableにできますよ、というの理論・実装が普及してきています。コイツはなかなか画期的で、多分この先10年はserializable実装は、よほどの事がない限りこれがデファクトでしょう。
■Serializable Snapshot Isolation
・Serializable Isolation for Snapshot Databases
http://ses.library.usyd.edu.au/bitstream/2123/5353/1/michael-cahill-2009-thesis.pdf
（引用されるのは短いバージョンの方が多いのですが、長いヤツちゃんと張って置きます。こちらのほうが読みやすい。2009年版ですが、こちらにちゃんと書かれていますが・・・）
SIで最も有名な論文はSIGMOD2008でベスト・ペーパーを取ったこの論文なのは論を待たないでしょう。DB界隈では読んでない人はいないと思います。「俺っち、Oracleプロだから！」って人に限って、どうゆうわけだがこの辺読んでない人大杉栄状態なので、まじでそーゆー人は読んだ方がいいです。・・・ところがこの論文は結構難解というか、部外者が読むには敷居が高いというか・・いや、読むには読めるのですが、肝心かなめの部分が、さらっと流れすぎている気がします。
んで、実は元ネタの論文があって、こっちが本星だったりするわけです。実際上記のCahillの論文は以下のFeketeの論文を十カ所以上に渡って引いておりまして、というか・・・そもそもそのCahillの論文指導がFeketeでして、まぁ要するにこっち読んでおかんとなんだかわからん、という話です。んでそのFeketeは某分散系のLynch学派のメンバーでして、・・・要するにそういうことです。
・Making Snapshot Isolation Serializable
http://www.cse.iitb.ac.in/dbms/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
コレを読まないとなんで「r-wのanti-dependencyが2つあるとserializableじゃないriskがあるのか」ということが、分からない。（超頭のいい人は多分、わかるとは思いますが・・自分はあまり頭が良くなかったせいで、分からなかったわけですが、この論文読めばわかります。）
ここに辿り着く人が何人いるかわかんないし、辿り着いている人はもう分かってるのでそんな解説いらんわい、となると思うので、現時点想定読者は全日本的に5人程度なんですが、自分目的でメモっておきます。マニアックすぎて誰も読まねーとか言われるわけですが、自分が忘れるのでメモる感じですよ。
（あ、一応「俺はTXはガチだから」という人は絶対読んでおいた方いいと思いますよ）
前提1
MVCCとSIとではSIの方が制限的である。これがポイントのひとつ。
MVCCはTX発生時点では、そこまでにwriteされたversionを読むことが可能であって、commitの有無は理論上は直接制限されません。(SIが有名になりすぎて、MVCCと混同されている方も居ますが、MVCCはもっと広い概念です。) しかし、SIの方は明確に、「読む込む時点で直前にcommitされたversionを読む」という制限がかかります（強制）。したがって、TX開始時点で、その読む込みversionをwriteしたTXはすでにcommitを終えています。したがって、論理的には、当該開始されるTXと、開始するTXが読み込むversionをwriteするTXはconcurrentになりません。したがって、w-rまたはw-wのconflictは発生しません。つまり、仮に発生するのであれば、そのconflictは必ずr-wに制限されることになります。（この前提はFeketeの論文で詳細に書いてありますが、コレ以降の論文はほぼ全て「そんなこと知ってるだろ条件」になっているので注意しましょう）
前提2
Serializableにならない、ということはcyclicになるということです。
これはserializabilityの基本定理で、証明は背理法で行いますが、まぁ割と前提でいいかと思います。んで、conflictのグラフがcyclicになる可能性がある場合は、少なくともノードで二つエッジで存在しないといけません。そうでないと「輪」にはなりません。ただし、二つあったからといって輪になるわけではありません。したがって、r-wのantidependency二つがグラフでつながると、実はヤバい可能性が発生し、かつ、それはそのときに限ることになります。
以上が前提になります。
■Making Snapshot Isolation Serializableの概要
それで肝心の論文の構成は以下です。
1. Motivation and preliminaries
2. Transactional history theory
3. Program conflicts and static dependencies
4. Analyzing an application
5. Avoiding isolation errors in the application
6. Conclusion
以下、概略と内容です。ポイントも順番に記述していきます。
（一応、論文は片手に持っている前提で書いています）
1. Motivation and preliminaries
基本的なSIの説明をしています。その上で、問題となる二つのSkew(anomaly)を丁寧に説明しています。なので、どの種類のanomalyが発生するのか？をそのために何をするのか、を把握しています。有名なのは、Write Skewですが、MVCC固有のanomalyとして、Read-only Transaction Skewもちゃんと解説します。あとはphantomについてはなんでreadだけで、writeがないの、ということについても言及しています。以下、Skewを二つ解説します。
○Write-Skew
これは別のエントリーでも書いているので、簡単にしておきます。MVCC絡みだとそれこそ、耳タコぐらいに出てくるので、暗記している人も多いかと。
典型は、
・X+Y > 0 という制約条件
・初期値 X= 70 Y=80
・SIでのIsolation
・T1が X0とY0にアクセスして、Xから100だけ引く。
・T2が X0とY0にアクセスして、Yから100だけ引く
・それぞれのTXは成功してしまう。
R1(X0,70) R1(Y0,80) R2(X0,70) R2(Y0,80) W1(X1, -30) C1 W2(Y2,-20) C2
・んでこれは制約条件を満たさない
・First-Commiter-Winsでも検出不能
○Read-Only Transaction Skew
えっとですね。このanomalyは多分Web系の人は知っておいたほうがいい気もします。俺そっちは疎いので良くわかりませんが、普通のB2Bに比べて、readのワークロードが重いはずなんで。
SI下では、すべてのRaed onlyなTXはserializableに実行されると想定されることが多いです。というのは、
1.Read onlyはインスタント
2.TX発生時点でのcommit済みのデータを読み込む
3.commitされていないデータは見えない
・・・なので、これだけ見ると普通にserializableでしょう。ということになります。がそうではないです。
・Read Only Transaction Anomaly
・Xが決済アカウントで Yが貯蓄用のアカウント
・それぞれ初期値はX=0 Y=0
・T1でYに20だけdeposit
・T2でXから10だけ引き出す
・当座借越の金利はX+Yがマイナスになった時点で発生 金利は1とする
・T3でXとYの残高を参照する。（read only）
・さて、T1-T3をSI下でconcurrentに実行する
・R2(X0,0) R2(Y0,0) R1(Y0,0) W1(Y1,20) C1 R3(X0, 0) R3(Y1,20) C3 W2(X2,-11) C2
・T3のアウトプットは X=0 Y=20できれいに完了する。
・T2-T1でserializeすると貸越になるので、金利発生でX=-11 Y=20
・T1-T2でserializeすると貸越なしで、X=10 Y=20
・いずれにしても、T3はfinal stateとは一致しない。また、残高照会でX=0 Y=20だと、なんで金利が発生するのかわからない。・・という散々な結果。
（つまり本来はできてはいけないTXができてしまっているということです。anomalyとして検出しないといけないというわけです。）
・ちなみに、このケースは2PLで除去可能
あとはこのセクションでは、Predicate readでのanomalyの話が書かれています。特にPredicate-Based Write Skewは見ておいた方がいいでしょう。単純なSELECT FOR UPDATEでは除去できないという話です。このあたりは、「あー、やっちまったかも」的なDBAの人もいると思いますが・・・
この後のセクションで、SSIではこれらのanomalyをきっちり検出しますよ、というのが論文の目的になります。
2.Transactional history theory
まず肝心要のDependencyの話が展開されています。主要なTheoremだけコメントします。
Definition 2.1 Transactional Dependencies
インターリーブするSIのhistoryにおいて、以下、
item-write-read dependency ＝ Tm ->(i-wr)-> Tn
（mで値を生成し、nで読む。i-rwはitem read write dependencyの表記）
item-write-write dependency ＝ Tm ->(i-ww)->Tn
（mで値を生成し、immediate successorのnで別バージョン生成）
item-read-write dependencyまたは item-anti-dependency ＝ Tm->(i-rw)->Tn
（mで値を読んでおり、immediate successorのnで別バージョン生成）
predicte-write-read dependency ＝ Tm ->(pr-wr)-> Tn
（mで値を生成し、nのpredicate readで読む。ただし、nの開始前に、mでコミットされていること）
predicate-read-write dependencyまたは predicate-anti-dependency ＝ Tm->(pr-rw)->Tn
（mで値をpredicateで読んでおり、nで別バージョン生成。nのコミットは、mの開始後）
以上のdependencyをまとめて、Tm->Tn dependencyとしています。predicate writeは存在しないので、入っていません。おなじみのconflictを定義し直しただけです。
次にまず、DSGの定義が続きます。
Definition 2.2 DSG(H) Dependency Serialization Graph for history H
・有向グラフ
・マルチバージョンhistory
・頂点(ノード)はTXのコミット
・ラベルつきエッジ（TmからTn）はそれぞれに対応
という定義になります。
その上でサンプルとしてExample 2.1のグラフが提示されます。
W1(X1) W1(Y1)W1(Z1)C1 W3(X3) R2(X1)W2(Y2)C2 R3(Y1) C3
（serializable orderはT1-T2-T3になりますね。ボールドがrw-dependencyになります）
これも問題ないでしょう。グラフの記述上はr-wは重要なので時に記法を変えるということをやっています。留意すべきは、ここでのグラフは基本的にTX間のdependencyであり、このあとでprogram同士のdependencyに”lift”させる方針をとります。
次に、anti-dependencyにフォーカスします。anomalyをふくむSI historyについてSI historyのDSG(H)の非循環を示します。・・というかserializableでない時にはDSG(H)が循環する（割と特徴的な形で）ということ示します。ここからが本命。
Remarks 2.1
・TX開始時点で読めるはコミットされたものだけ
・よって Tm->wr->Tnの場合、Tmはコミットされている
・よってconcurrentではない
・Tm->ww->Tnも同様（こちらはFirst-Committer-Win）
・ただし、仮にTm->rw->Tnがあればconcurrentな場合はある。
・またはTmが完全に先行している場合
・ただし、Tnが完全に先行することはない。そーなるとanti-dependencyが成立しないので。（最も最近のバージョンを読むというルール）
その上で・・・
Lemma 2.2
・仮にTm->Tnのdependencyが存在するのであれば、TmはTnの前にスタートする。そうなると、上記Remarks 2.1より
・w-r w-wであればconcurrentではない
・r-wであればconcurrentまたはrが先行する
よって、
Lemma 2.3
「仮にTm->Tnのdependencyが存在し、かつそれらがconcurrentであれば、それはTm->rw->Tnである」
それはAnti-Dependencyと呼ばれる
要はブログの冒頭での展開です。言われてみれば、なんだ当たり前だろ、という話ですが、この瞬間にTXのSerializable判定の厄介なグラフの依存関係が一気に簡略化されたのがわかります。いわゆるSGT(Serializable Graph Testing)より格段に優れていると言われるところですね。
んで、このあと、ありとあらゆるMVCCの論文で引用されるTheoremにつながります。これも単純です。
Theorem 2.1
・HをSnapshot Isolation下で生成されたマルチバージョンのhistoryとする。かつ、Hはserializableではないとする。この時、
1 少なく一つは循環するDSG(H)が存在する
2 それらの循環の中には、三つの連続するTransactionが存在する
・ただし三つのうち最初のものと最後のもの同一でもよい
・かつ、最初のものと二番目のものはconcurrentであり edgeが存在する
・かつ、二番目ものと最後のものはconcurrentであり edgeが存在する
なお、edgeはanti-dependencyになる
Proof
Serializableでないとすると、dependencyのcycleが存在する。
（cycleがなければトポロジカルソート可能よってserializableで矛盾）
・任意のcycleをとる
・その最初にコミットタイムがくるTXをT3とする
・T2をT3の先行、T1をT2の先行とする
・ここでT2とT3がconcurrentでないとすると
・その場合、T2が最初に終わるので、T3が最初のコミットと矛盾
・または、T2が開始する前にT3が終了する場合はLemma2.2に矛盾
・よってT2とT3はconcurrentである
・したがって、それはanti-dependencyになる
・T2とT1についても同様
以上。
これも言われれば、まぁそりゃそうだになるのですが、いきなりデフォルトで話されるとなかなか辛い、というか理解不能っすよ。
このあと、SI-RW Diagramの話になります。これは、「話をわかり易くするために」今までの考え方はUser-orientedなので、Scheduler-orientedな考え方をしてみる、という流れなのですが、基本的に証明とか好きじゃない人用で、個人的にはそれは混乱するだけだろう、と思うので省略します。敢えて言えば、「実装的には、こーゆー風に考えれば、今までのTheorem理解できるよね？」という助け舟ですが、助け舟の方が難易度高い感じでアレです。いや、人によるんでしょうが、TX系をやっているひとから見ると不要ですよ。
（・・・この辺はTX系の人間の少なさの悲哀ですね。不勉強な人にも説明しないとイカンので、ちょっといろいろやってます的なアレです。わかんねーヤツはほっとけばいいと思うんですが、まーそうも行かないのでしょう。）
それよりも、ここからが真骨頂で・・・んじゃーそのご大層なTheoremで本当にanomaly検出できますか？という話ですね。
まずWrite Skew
・R1(X0,70) R1(Y0,80) R2(X0,70) R2(Y0,80) W1(X1, -30) C1 W2(Y2,-20) C2
・SI下
・TX1-TX2はconcurrent
・ここで、R2(X0)->W1(X1) R1(Y0)->W2(Y2)でanti-dependency検出
・よってDSGは循環（Tx1=Tx3の例ですね）
・よってanomaly に決定。
次にSI Read-Only serialization anomaly
・R2(X0,0) R2(Y0,0) R1(Y0,0) W1(Y1,20) C1 R3(X0, 0) R3(Y1,20) C3 W2(X2,-11) C2
・R2(Y0)->W1(Y1) R3(X0)->W2(X2) concurrentでanti-dependency(r-w)
・W1(Y1)->R3(Y1) dependency
・Tx1->Tx3->Tx2->Tx1でDSGは循環
・よってanomaly
まるで計ったかように見事にanomalyを検出します。素晴らしい。このあたりの美しさがTX理論の魅力ですね。自分でも読んでて「おおっ」と膝を打ちました。
3.Program conflicts and static dependencies
ここでは、いかにして複数のTXなプログラムが静的解析でSI下でanomalyなしである、と信頼できるか、という問題をとりあげています。んで、その実例が、4章になります。えっと、ですね。最初に上げたCahillの論文はこのあたりを批判して乗り越えてますね。要は「静的解析？いやそれ意味ないでしょう。そもそもparameterizedされたプログラムの方が多いし。てか静的解析できるDBAとか何人いるんだよ？」という話です。このあたりは前出のCahillの「俺TUEEEE」論文を読んで頂ければよいです。とはいえ、そもそもその論文での批判対象を理解しないと、なんで「俺TUEEEE」なのかわからない感じなのでアレですが。
余談ですが、Jim Grayもそうですが、TX界隈の人は「俺TUEEEE」な人が多い割には、TUEEE度合いを自分で解説しないといけない感じで、どうなんだそれは論文が多くて、趣き深いですね。
4.Analyzing an application
実際にTPC-Cのベンチマークを例にとりながらSDG(A)を構成していく、という内容です。基本的にはテーブルと取引トランザクションの内容からSDG(A)を作成して、anti-dependencyを検出するという作業を行っています。自動検出については懐疑的です。尚、現在の潮流はむしろ実行時に検出すべき、という方向が主流ですので、この論文の方法はあまり役には立たないかな、という気はしています。なのでパスしていいでしょう。・・・あ、まぁこのベンチマークの改良がこれ以降各所で話題にはなるので、一応時間がある人はサクッと読んでおいてもいいです。
まったく余談ですが、業務屋的などんな実務をモデル化したらこうなるんじゃいという感じがいつもするので、現実知らないにもほどがあるとは思うことはありますが、それなりリサーチはされているという説あるので、その辺はまぁアレで。
5.Avoiding isolation errors in the application
さて、ここからは実装的にどうやってこの手のanomalyを発生させないようにするのか？ということになります。
実は、この中のmaterializationは、結構他でも応用されている技術（例としては、global serializationのconflictを各プロセスで検出するために、「無理矢理」global conflictをlocal conflictとしてmaterializeする手法もこれにあたります。）だったりします。
尚、この辺の理屈とCahillあたりの実装の論文を読んでおかないとPostgresあたりのSSIの実装が読みづらいはずです。ポイントはあの程度の少ないコードベースで、TXの難問中の難問のserializabilityの問題を、制限があるとはいえ解決している点だと思います。
えっと、本論ですが以下
・dangerous structureの有無がわかれば、SI下ではserializableかどうかわかる。
・しかし制約条件が明示されて無くて、実行時にserializableにならないというケースもありうる。
・アプリケーションの機能を変えずに、少しの変更で、dangerous structureを避けることができるということを説明したい。
・まずはDBAはdangerous structureを特定する必要がある。
・これはvulnerableなエッジをみつけて、そのエッジへの頂点のアプリを変更して、vulnerableでなくせばよい。
ということが話の趣旨です。
5.1 Materialize the Conflict
前提として、dangerous structureはふたつのvulnerableなanti-dependencyをもっているということがスタート地点です。このvulnerableを除去するには、conflictをmaterialize(実体化）する新しいデータアイテムを作り出して、そのアイテムの更新処理に、vulnerableなプログラムを関わらせればよい、という戦術です。
例）
・適当にConflict(Id, val)のテーブルをつくる。
・それぞれの実体化したいanti-dependencyなエッジについて(X,0)[Xはエッジに固有の値]をinsertし、最後にanti-dependencyの両端のノードのアプリケーションに以下を追加する。
UPDATE Conflict SET val= val+1 WHERE Id=X ;
・これによりFirst-committer-Winsルールが働く、よってconcurrentではなくなる。これはpredicateなコンフリクトでも有効といえる。
（次のPromotionが使えないようなケース、たとえば、TX間で共通の値がない場合には、materializeが有効な手法になります。）
また、vulnerabilityを除去するのに単一の値を利用する必要はないです。conflictはプログラムそのものというよりも、与えられるパラメーターにより発生することがしばしばあるので。なので、materializeにはパラメーターを利用する方法もあります。例えばPredicateベースなWrite Skewの例では、制約のテーブルを別につくってその制約を破らないようにする方法もこれにあたります。conflict tableのように単一の値を利用しようとすると、論文のWrite Skewの例では、同時に二つのタスクを二つの別々の人間にアサインできなくなります。ただし、その変形を用いることで可能になります。たとえば、TotalHours(eid, day, total)というテーブルと作って、WorkAssignmentを更新する場合に、同時にTotalHoursも更新する方式にします。これにより、単純にvulnerableなconflictの発生をおさえます。
要するに、共有に関わるテーブルを持たせて更新処理を強制して、concurrentのTX同士において、強制的にconflictを実体化させるという手法です。引っかかればconcurrent中止で、引っかからないのであれば、そのまま処理続行ということになります。
5.2 Promotion
もっとも簡単な方法は、要するにSELECT FOR UPDATEにすることで強制writeに変更して、first-commit-winを適用させ、concurrent処理にさせないという戦術です。これをPromotionと言っています。これによりr-wのanti-dependencyが解消します。
（まぁ極論するとやばそうなTXがやばそうな値に処理を行うときは、有無を言わさずFOR UPDATEにしておけ、というなんか意図しない結論になりそうですが、まーそーゆー趣旨っぽい感じですね。）
6.Conclusion
あまりたいしたことは書いてないですね。
■まとめ
上記が、Making Snapshot Isolation Serializableの概要です。これのサマリーが今後のSSIでは頻繁に利用されます。研究の傾向としては、あとはruntimeでの検出をどうするか？という問題と負荷の問題が検討されています。より実装よりの話題が多いですね。特に問題になるのはdangerous structureの検出の仕組みについて、concurrentな3つTXの依存関係のうち、T1→T2 T2→T3のそれぞれのconcurrecyを把握しておく必要があるときに、T3が走り出す前に、T1が完了してしまう可能性があるということです。つまり、「よって、完了したT1についての依存関係をどこかに保持しておく必要」が発生します。これは、冷静に考えるとちょっと（というか場合によっては、かなり）厄介なことになります。そんな感じで実装を工夫する必要があります。
いずれにしても、静的解析ではなくてruntimeでできるだけserializableでないものは検出しましょう、ということが実現されつつあるので、（今までだとSGTなので、要するにpolynomial timeの時間がかかるわけで、大量TXになったときに死ぬ可能性が高い）これは、それなりのTXの理論的・技術的なブレイクスルーになっています。さらに延長線としては、分散環境でのSSIというやつでして、まずはベースとして、1-Copy-Snapshot-Isolationが出発点になることが多いようですが、この辺はまた別の機会にまとめます。
とりあえず、これだけ書いとけば、自分的に後で見直す時には十分なんで。
（あー間違っていたらすみませんです。一応、念のため書いておきますが。）
以上です。
Permalink | トラックバック(1) | 14:50
2013-03-10
クラウド上にEDIを「移行する」ということの意味
ニュースリリースというか記事はこちら。日経の中田さんの記事ですね。
http://itpro.nikkeibp.co.jp/article/NEWS/20130306/461423/
この辺の解説を記録のために書いておきます。個人的にはちょっとしたマイルストーンなので。
まずEDIの定義ですが、これはElectronic Data Interchangeの略で、B2Bでの電子データ交換の仕組み自体をさします。歴史的にはITの歴史と同じくらい古い。当然インターネットよりも古い。昔は（場所によっては今も）電話で”ぴー”とか”がー”とかやっていた代物です。多分50年以上の来歴を誇る仕組みですね。業界ごとにその業界に応じたプロトコルが制定されており、いわゆる標準化がもっとも進んだ分野のひとつです。そして、大抵はミッションクリティカルな業務に属します。エンタープライズ系のITでは最下層に位置するレイヤーのひとつで、ま、聞いた事はあるが中身を知っているひとは皆無に近い。そんなところです。金融決済系のSWIFTなんてのは有名ですね。
EDIは、普通は事故で止まると営業に即刻影響が出ます。受発注や物流システム、在庫管理や決済につながっているので、データが来ないと大事になります。勿論、いろいろ業務的なバッファーが豊富にあってリードタイムに余裕があるところでは問題にならないのですが、そういうところは例外です。現在、多くの企業ではEDI化が進んでいて、その上でSCMの効率化追求も行っているので、EDIが止まると、物は動かないわ、決済はできないわ、という事になり、すぐにトラブルになります。社会インフラの構成要素の一つと思ってもらってかまいません。つまり、止めると IT屋は土下座になります。
要するに仕組みとしては「とても古い」その上「ないと割と困る」そういう仕組みです。
内容としては、これをクラウドに上げました、ということなのですが、割といろいろ示唆される部分があったので記録として残しておきます。
[元々の起こり]
SUNという会社がなくなりまして（笑）。お客さんのEDIはSUNのサーバーで動いていたわけで、サポート切れの上に、ディスクがもう在庫がありません状態になりました。ここがスタート地点です。
ここでお客さんはEDIの仕組みは維持どころか、ただ今拡大中というステータスで、かなり困った状態に追い込まれました。システム的には、間違ってダウンすると営業に影響がでる寸前まで行っている状態です。
この場合取るべき選択肢としては普通は以下二種類になります。
1.再構築
ハードを一新。まぁミドルも変わるので、一応機能を一部追加した上で再投資でSIする方法。言ってみれば従来の方法。
2.SaaSを使う
出来合いの仕組みを従量課金で使える仕組みは割と出ているので、そのサービスを利用する。
対象が枯れたEDIなので実は機能の追加はあまり必要ありません。とはいえ、ちょこちょこと手直しや接続先の増減は発生します。身軽に考えるのであれば、EDIのSaaSを利用するという手もあるのですが、これは一般のSaaSと同様のトリックがあって、実はスケールしてもコストが低減しません。
SaaSはスタートアップにはいいのですが、ある規模を越えるとコストが合わなくなります。正確にいうとユーザーがスケールメリットを享受できなくなります。これは言ってみれば論理的に当然の帰結で、スケールメリットを享受するのがSaaSベンダーの利益の源泉なので、ユーザーがそのメリットを受けるようでは、ベンダーにはSaaSを提供するうまみがなくなってしまいます。（SFDCが規模が増えると割高になる、というのも理屈は一緒です。）これはちょっと辛い。
実際、いろんな領域でSaaSを見送って自社でSIという選択の根拠の一つはこのような理由が非常に多いですね。
[結局どうしたのか]
というわけで、要するに
1) 既にソフトウェアは資産として（簿価はともかく）保持している
2) ハードが老朽化して、供給も不安
3) 投資しているので、スケールメリットはちゃんと取りたい
4) ミッション・クリティカル
そのような状況をどうにかしろという要請でした。
んで結論は、なんとAWSに上げた。
というシナリオです。なにしろミッション・クリティカルなんで、相当ハードルが、特に精神的ハードルが高いです。これ実際の背景としては、既にAWSで基幹バッチ処理を一年超やっているという実績がかなり効いています。とはいえ、そこまでやるかという感覚がEDI屋の普通の神経です。Amazonにも確認はしていますが、予想通りEDIをAWSというのは実は日本では初めてです。（世界では他に例はあるようです）
これは完全にユーザーさん主導です。リスクを検討・評価（実態はほぼ一年間AWSを評価していたわけで）し、ヘッジをかけた上でベネフィットを取りに行ったという形です。
やってる自分が言うのも変ですが、正直言って、こういう時代になったかと、そう思います。
EDI 屋の本分としては、今でもEDIをVPCとはいえクラウドでやるというのは、ちょっとイメージを越えているところはあります。SaaSをエセ・クラウドでやりますよというのはいくらでも聞くのですが、それは実情は単なるアウトソーシングに過ぎません。というかそれは普通のVANサービスですよ。今回は確実にレベルが違います。
[手伝っていて感じたポイント]
1. ソフトウェアとハードウェアの寿命の乖離が激しくなっている。
業務系のシステムは特にソフトウェアの部分は、やはり寿命が長いです。最近はさらに長くなっているような気がします。その一方でハードウェアの、実質的な寿命はどんどん短くなっています。体感的には3年ぐらいでしょう。CPUのメニーコア化はともかく、Diskの高速化やN/Wの高速化も進んでいます。多分、今後はメモリーの大容量化や不揮発性化も進むでしょう。もう別物です。
ベンダーも複数のサポートラインを持つのは維持コストが高いので、サポートをなるべく切ってくるでしょう。そもそもベンダーにしてみれば、現在のクラウド化の推進下では、オンプレミス用のサーバーですら、アプライアンスを除けば利幅が薄いのが実情です。今後、供給もしなくなるかもしれません。
その意味ではミッション・クリティカルなオンプレミスのシステムはかなりの勢いで対応を迫られる可能性もあります。なにしろシステムのソフトウェア自体はまだまだ現役なのにハードが供給されない。いままでは予備機を買ったり、中古を探したりで凌いで来ましたが、それも早晩限界でしょう。自力でハードを調達できる力がある大手ユーザーはともかく、中堅ユーザーには厳しい時代です。クラウド化というのは、選択肢の一つというよりも、必然的な流れになる可能性すらあります。
2. ガバナンスを保持すべきはどこか？という問題
このような背景も見ると、やはりユーザーさんはハードウェアには投資すべきではないです。エンタープライズでのクラウドの現実化は、とるべきガバナンスの位置を確実に変えています。現在の低成長時代では、ある程度ポータビリィティの高い資産、すなわちソフトウェアに投資していくしかないでしょう。ソフトウェアの投資可搬性の確保が非常に重要だと思います。
とはいえ、世の中のオープン系の建前とは別に、実態としての業務システムはハードとソフトは不可分であることが多いです。理屈はともかく分離は手間です。ソフトウェアはハードウェアがあってはじめて走りますから、ある程度のハードウェアの想定は必ず敷いています。そういう状況でシステムへの投資可搬性の向上はやはり一定のコストをかけて行く必要があるでしょう。
さらにいうと、将来のクラウドの勝者が特定のクラウドベンダーだとは限らないわけで。その場合は、クラウドからクラウドに資産をポートする必要も出てくるでしょう。
3. 最後はユーザーが”ベンダー的役割”を自分でまかなってしまう
実はこのケースは、実態としては「お客様の、自力で作った自社専用VANが仮想的に立ち上がっている」という状態です。勿論、我々のサポートがあって出来ているという部分は確かにありますが、接続やらアレンジメント、一定の設定までユーザーさんが相当の作業をしています。これはある意味できて当然のことではあります。ユーザーさんのシステムなので、内容がわかっているということが大きい。（さすがにAWSを裸でユーザーが直接ってのは、ハードルが高いのでこちらでいろいろ準備はしていますが）
極論すると、この手のものはSIがもうイラない状態になりつつあります。特に出来ている資産を維持運営する、という局面においてはそうですね。表面上はEDIをAWSに乗っけただけですが、その裏側の実質として、「システムの投資可搬性を上げるということ」の結果としての、「SI屋の不在」という現実があります。
いや、簡単な仕組みなら別に大きな問題ではありません。今時、ユーザー主導でSI屋抜きでの環境再構築や大幅な移行という話は、いくらでもある話でしょう。しかしこれはEDIです。「ミッションクリティカルなシステムを、ユーザーさん主導でプロダクトベンダーのサポート下でSI屋さん抜きでクラウド化しました。」そういう仕組みです。
[まとめ的な]
新規の大規模システム開発はリスクや投資対効果をみれば、日本全体ではやはり減ってくるでしょう。湯水のようにお金が使えるならともかく、社会的コストの増大と長期的な収益の頭打ちを考えれば当然です。本来はSI的には、多少の赤字は新規開発でかぶっても、継続運用開発で黒字を稼ぐというスタイルもあったわけですが、それすら徐々に厳しい環境になりそうな気配です。ハード老朽化はいい契機ではあったんですがね・・・
ぱっと見はあまり派手は話ではないのですが、自分的にはクラウドでここまできたかという印象を持つ、そんな「事件」ではありました。なので、ちょっと記録としておいておきます。
・・・ しかし、EDIがAWSでとか、ありえないですよ。当のEDI屋本人が言ってんだから間違いないです。しかも4ヶ月で100社接続まで行った上に、24x365で動いてるし。どーすんだよSI屋さん、とは思います。
Permalink | トラックバック(1) | 21:49
