document

Transaction Puzzlers
appengine ja night #4
あらかわ (@ashigeru)
講演者について

名前
 あらかわ

(@ashigeru)
所属
 株式会社グルージェント

開発部
普段の業務
 研究開発
(コンパイラ系)
 教育 (Computer Aided Education)
 ブログ書き (Song of Cloud Blog)
2010/01/22
appengine ja night #4 - @ashigeru
2
Song of Cloud Blog

会社ブログ



http://songofcloud.gluegent.com
App Engineのポータルサイトをコンセプトに
By arakawa (App Engine関連)








Slim3 Datastoreに乗り換える
テキスト部分一致検索
送金のトランザクション処理パターン
分散トランザクション処理の最適化
SDK 1.2.8 Release Notesで語られなかったこと
App Engine SDK 1.3.0 (overview)
App Engine JDP Tips
グローバルトランザクション処理のパターン
2010/01/22
appengine ja night #4 - @ashigeru
3
今日の内容
トランザクション処理の考え方
 トランザクション処理のパターン

2010/01/22
appengine ja night #4 - @ashigeru
4
トランザクション処理の考え方

リソースを一時的に独占できる技術
 同時に変更して不整合が起こる、などを回避

今回は悲観的/楽観的をあまり気にしない
 App
Engineは楽観的並行性制御
 いずれも一時的にリソースを独占できる
 設計/実装時には考慮する必要がある
2010/01/22
appengine ja night #4 - @ashigeru
5
App Engineのトランザクション

トランザクションはEntity Group (EG)単位
 同一EG内のエンティティに対する操作はACID
 複数EGにまたがる操作は対応していない
2010/01/22
appengine ja night #4 - @ashigeru
6
Entity Groupの構成

同じルートキーを持つエンティティ群
 データストア上で近くに配置される

例
 Foo(A)
 Foo(A)/Hoge(B)
EG: Foo(B)
 Foo(B)
 Bar(A)/Foo(A)
 Bar(A)/Foo(B)/Hoge(D)
2010/01/22
EG: Foo(A)
EG: Bar(A)
appengine ja night #4 - @ashigeru
7
Entity Groupの特徴

ポイント
 トランザクションの範囲はエンティティ作成
時に決まり、変更できない
 EGを大きくするとトランザクションで独占す
るエンティティが多くなる

EGの設計が非常に重要に
 間違えると並列性が極端に低下する
 うまくやればスケールアウトする
2010/01/22
appengine ja night #4 - @ashigeru
8
ここまでのまとめ (1)

App EngineのトランザクションはEG単位
 EG内ではACIDトランザクション
 EGをまたぐトランザクションは未サポート

EGの設計によっては並列性が落ちる
 EGを大きくすると独占範囲が広がる
 EGを分断すると整合性を保つのが困難
2010/01/22
appengine ja night #4 - @ashigeru
9
トランザクション処理のパターン

App Engineのトランザクションはやや特殊
 パターンで対応したほうがよさそう

本日紹介するもの
 Read-modify-write
 トランザクションの合成
 ユニーク制約
 冪(べき)等な処理
 Exactly
Once
 BASE Transaction
2010/01/22
appengine ja night #4 - @ashigeru
10
注意点

プログラムの説明に擬似コードを多用
 言語はJavascriptライク
 APIはJavaのLow-Level

APIライク
見慣れない言語要素
 キーリテラル

– KEY:…
KEY:Foo(A), KEY:Foo(A)/Bar(B), など
 データストア

get(tx, key), put(tx, entity), beginTransaction()
 タスクキュー

enqueue([tx,] statement)
2010/01/22
appengine ja night #4 - @ashigeru
11
パターン: read-modify-write
エンティティのプロパティを変更する
 例:

 カウンタの増加
 ショッピングカートに商品を追加

現在の値をもとに次の値が決まる
 読む、変更、書き戻す、の3ステップが必要
 途中で割り込まれると不整合が起こる
2010/01/22
appengine ja night #4 - @ashigeru
12
read-modify-write (1)

考え方
 読んでから書き戻すまでエンティティを独占
100 + 1
100
2010/01/22
101
appengine ja night #4 - @ashigeru
13
read-modify-write (2)
var tx = beginTransaction()
try {
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
tx.commit()
}
finally {
if (tx.isActive()) tx.rollback()
}
2010/01/22
appengine ja night #4 - @ashigeru
14
read-modify-write (3)
var tx = beginTransaction()
try {
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
読んでから書き戻す
tx.commit()
までをACIDに行う
}
finally {
if (tx.isActive()) tx.rollback()
}
2010/01/22
appengine ja night #4 - @ashigeru
15
DSL: atomic (tx) { … }

以後は下記のように省略
 トランザクションの開始と終了を簡略化
atomic(tx) {
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
2010/01/22
appengine ja night #4 - @ashigeru
16
パターン: トランザクションの合成
同じEGに対する複数のトランザクション
処理を合成
 例:

 2つのカウンタを同時に変更
(恣意的)
 非正規化した2つの情報を同時に更新

注意点
 分断したトランザクションでは、途中で失敗
した際に修復が大変
2010/01/22
appengine ja night #4 - @ashigeru
17
トランザクションの合成 (1)

考え方
 同じEGのトランザクションが2つあったら、
一度に処理してしまう
15
30
2010/01/22
16
31
appengine ja night #4 - @ashigeru
18
トランザクションの合成 (2)
atomic(tx) {
var a = get(tx, KEY:Eg(C)/Counter(A))
a.value++
put(tx, a)
var b = get(tx, KEY:Eg(C)/Counter(B))
b.value++
put(tx, b)
}
2010/01/22
appengine ja night #4 - @ashigeru
19
トランザクションの合成 (3)
atomic(tx) {
var a = get(tx, KEY:Eg(C)/Counter(A))
a.value++
put(tx, a)
var b = get(tx, KEY:Eg(C)/Counter(B))
b.value++
put(tx, b)
同じEGのエンティティ
}
に対する操作
2010/01/22
appengine ja night #4 - @ashigeru
20
トランザクションの合成 (4)
atomic(tx) {
var a = get(tx, KEY:Eg(C)/Counter(A))
a.value++
put(tx, a)
var b = get(tx, KEY:Eg(C)/Counter(B))
b.value++
put(tx, b)
複数のトランザクション
}
を合成, 全体がACIDに
2010/01/22
appengine ja night #4 - @ashigeru
21
パターン: ユニーク制約
重複するエンティティの登録を防止する
 例:

 同じIDを持つユーザの登録を防ぐ
 ダブルブッキングを防ぐ

注意点
 データストアは制約機能を組み込んでいない
 クエリはトランザクションに参加できない
2010/01/22
appengine ja night #4 - @ashigeru
22
ユニーク制約 (1)

考え方
 エンティティの入れ物ごと独占
 入れ物が空なら追加するエンティティは一意
@hoge
2010/01/22
@hoge
@hoge
appengine ja night #4 - @ashigeru
23
ユニーク制約 (2)
var key = KEY:User([email protected])
atomic(tx) {
var user = get(tx, key)
if (user != null) {
throw new NotUniqueException()
}
user = new User(key, ...)
put(tx, user)
}
2010/01/22
appengine ja night #4 - @ashigeru
24
ユニーク制約 (3)
var key = KEY:User([email protected])
atomic(tx) {
var user = get(tx, key)
if (user != null)
{
ユニーク制約をキーで
throw new NotUniqueException()
表す(メールアドレス)
}
user = new User(key, ...)
put(tx, user)
}
2010/01/22
appengine ja night #4 - @ashigeru
25
ユニーク制約 (4)
var key = KEY:User([email protected])
atomic(tx) {
var user = get(tx, key)
if (user != null) {
throw new NotUniqueException()
}
user = new User(key, ...)
そのエンティティが
put(tx, user)
すでにあれば制約違反
}
2010/01/22
appengine ja night #4 - @ashigeru
26
ユニーク制約 (5)
var key = KEY:User([email protected])
atomic(tx) {
var user = get(tx, key)
if (user != null) { 存在しなければ
throw new NotUniqueException()
ユニークなので追加
}
user = new User(key, ...)
put(tx, user)
}
2010/01/22
appengine ja night #4 - @ashigeru
27
ユニーク制約 (6)
var key = KEY:User([email protected])
atomic(tx) {
var user = get(tx, key)
if (user != null) {
throw new NotUniqueException()
}
user = new User(key, ...)
put(tx, user)
getからputまでを独占
}
2010/01/22
appengine ja night #4 - @ashigeru
28
ここまでのまとめ (2)

read-modify-write
 最初に読んでから書き戻すまで独占

トランザクションの合成
 同一EGに対する操作をまとめる

ユニーク制約
 入れ物を独占してからエンティティを作成
 すでにあったらユニークじゃないので失敗
2010/01/22
appengine ja night #4 - @ashigeru
29
パターン: 冪(べき)等な処理

1回分しか効果を出さない処理
 2回以上成功しても、1回分しか反映しない

例:
 フォームの多重送信を防止
 お一人様一点限り。

注意点
 英語でidempotentだけど覚えにくい
2010/01/22
appengine ja night #4 - @ashigeru
30
冪等な処理 (1)

考え方
 「処理がユニークに成功する」ということ
 まだ成功していなかったら成功させる
 一度成功していたら何もしない
成功
成功
成功
結果
2010/01/22
appengine ja night #4 - @ashigeru
31
冪等な処理 (2)
var key = KEY:Counter(C)/Flag(unique)
atomic(tx) {
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
2010/01/22
appengine ja night #4 - @ashigeru
32
冪等な処理 (3)
var key = KEY:Counter(C)/Flag(unique)
atomic(tx) {
var flag = get(tx, key)
「ユニークなキー」を表す
if (flag
!= null) {
→ db.allocate_ids()
return
} → DatastoreService.allocateIds()
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
2010/01/22
appengine ja night #4 - @ashigeru
33
冪等な処理 (4)
var key = KEY:Counter(C)/Flag(unique)
atomic(tx) {
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
ユニーク制約をユニークなキーで。
put(tx, counter)
1回目は確実に成功、
}
キーを使いまわせば2回目は失敗
2010/01/22
appengine ja night #4 - @ashigeru
34
冪等な処理 (5)
var key = KEY:Counter(C)/Flag(unique)
atomic(tx) {
var flag = get(tx, key)
if (flag != null)それ以降の処理は
{
return
一度だけしか行われない
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
2010/01/22
appengine ja night #4 - @ashigeru
35
冪等な処理 (6)
var key = KEY:Counter(C)/Flag(unique)
atomic(tx) {
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
全体を合成してACIDに
}
2010/01/22
appengine ja night #4 - @ashigeru
36
冪等な処理 (まとめ)

冪等な処理
 「1回分しか効果を出さない」パターン

やりかた
 「成功」済みかどうかについてユニーク制約
 トランザクションを合成
ユニーク制約で成功フラグを立てる
 OKなら続きの処理を行う


注意点
 ごみ(Flag)が残るが、これを消すのは一手間
2010/01/22
appengine ja night #4 - @ashigeru
37
パターン: Exactly Once

確実にぴったり1回成功する処理
 冪等な処理では0回の場合もある

(最大1回)
例:
 カウンタの値を正確に更新する(恣意的)

注意点
 「確実に失敗する」処理には適用できない
2010/01/22
appengine ja night #4 - @ashigeru
38
Exactly Once (1)

考え方
 1度しか反映されない操作を執拗に繰り返す
 いつかは成功するはず
 間違えて2回以上成功しても効果は1回分
2010/01/22
appengine ja night #4 - @ashigeru
39
Exactly Once (2)
var key = KEY:Counter(C)/Flag(unique)
while (true) {
try {
atomic(tx) {
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
} catch (ignore) {}
}
2010/01/22
appengine ja night #4 - @ashigeru
40
Exactly Once (3)
var key = KEY:Counter(C)/Flag(unique)
while (true) {
try {
atomic(tx) {
var flag = get(tx, key)
冪等な処理の
if (flag != null) {
パターン
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
}
} catch (ignore) {}
}
2010/01/22
appengine ja night #4 - @ashigeru
41
Exactly Once (4)
var key = KEY:Counter(C)/Flag(unique)
while (true) {
try {
冪等な処理を
atomic(tx) {
無限に繰り返す
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
30秒ルールがあるので
}
確実とはいえない
} catch (ignore) {}
}
2010/01/22
appengine ja night #4 - @ashigeru
42
Exactly Once (5)
var key = KEY:Counter(C)/Flag(unique)
enqueue(atomic(tx) {
var flag = get(tx, key)
if (flag != null) {
return
}
put(tx, new Flag(key))
var counter = get(tx, KEY:Counter(C))
counter.value++
put(tx, counter)
代わりにTask Queueで
})
成功するまで繰り返し
2010/01/22
appengine ja night #4 - @ashigeru
43
Exactly Once (まとめ)

Exactly Once
 「確実にぴったり1回成功する」パターン
 ただし、いつ成功するかは不明

やりかた
 冪等な処理を無限に繰り返す
 一度成功したらあとは無駄なので打ち切る

App EngineのTask Queueを使える
 成功するまで無限に繰り返す、という性質
 30秒ルールがあるからwhile(true)は不適切
2010/01/22
appengine ja night #4 - @ashigeru
44
パターン: BASE Transaction

複数のEGにまたがるゆるいトランザク
ション
 ACIDほど強い制約がない

例:
 口座間の送金処理

注意点
 途中の状態が外側に見える
 ACIDよりアプリケーションが複雑
2010/01/22
appengine ja night #4 - @ashigeru
45
BASE Transaction (1)

送金処理で本当にやりたいことは２つ
 Aの口座からX円引く
 Bの口座にX円足す

「トランザクションの合成」は困難
 Aの口座とBの口座を同じEGに配置？
 Aから送金されうるすべての口座を同じEGに？

トランザクションを分断すると危険
 失敗例:「Aの口座からX円引いたけどBに届かない」
 補償トランザクションすら失敗する可能性
2010/01/22
appengine ja night #4 - @ashigeru
46
BASE Transaction (2)

単純に考えてみる
 まずAの口座から5000円引く
 そのあと「一度だけ」Bの口座に5000円足す
atomic (tx1) {
Exactly Once
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
}
atomic (tx2) {
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
}
2010/01/22
appengine ja night #4 - @ashigeru
47
BASE Transaction (3)
var key = KEY:Account(B)/Flag(unique)
atomic (tx1) {
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
enqueue(tx1, atomic(tx2) {
var flag = get(tx2, key)
if (flag != null) {
return
}
put(tx2, new Flag(key))
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
})
}
2010/01/22
appengine ja night #4 - @ashigeru
48
BASE Transaction (4)
var key = KEY:Account(B)/Flag(unique)
atomic (tx1) {
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
enqueue(tx1, atomic(tx2) {
Read-modify-write
var flag = get(tx2, key)
if (flag != null) {
(A -= 5000)
return
}
put(tx2, new Flag(key))
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
})
}
2010/01/22
appengine ja night #4 - @ashigeru
49
BASE Transaction (5)
var key = KEY:Account(B)/Flag(unique)
atomic (tx1) {
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
enqueue(tx1, atomic(tx2) {
Read-modify-write
var flag = get(tx2, key)
if (flag != null) {
(B += 5000)
return
}
put(tx2, new Flag(key))
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
})
}
2010/01/22
appengine ja night #4 - @ashigeru
50
BASE Transaction (6)
var key = KEY:Account(B)/Flag(unique)
atomic (tx1) {
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
enqueue(tx1, atomic(tx2) {
var flag = get(tx2, key)
if (flag != null) {
return
}
put(tx2, new Flag(key))
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
})
}
2010/01/22
appengine ja night #4 - @ashigeru
Exactly Once
(B += 5000)
51
BASE Transaction (7)
var key = KEY:Account(B)/Flag(unique)
atomic (tx1) {
var a = get(tx1, KEY:Account(A))
a.amount -= 5000
put(tx1, a)
enqueue(tx1, atomic(tx2) {
全体を合成
var flag = get(tx2, key)
if (flag != null) {
(A -= 5000, B += 5000)
return
}
put(tx2, new Flag(key))
var b = get(tx2, KEY:Account(B))
b.amount += 5000
put(tx2, b)
})
}
2010/01/22
appengine ja night #4 - @ashigeru
52
BASE Transaction (まとめ)

BASE Transaction
 EGをまたいだゆるいトランザクション
 いつか確実に完了する、という性質

やりかた
 トランザクションを合成
 一つ目のEGに対して操作を行う
 Exactly Onceで二つ目のEGに対して操作を行う

注意点
 操作が行われるまでタイムラグがある
 Eventual Consistency: いずれ整合性が取れる
 二つ目のEGに対する操作は制約をかけられない
 送金先に受け取り拒否されるとすごく困る
2010/01/22
appengine ja night #4 - @ashigeru
53
ここまでのまとめ (3)

パターン: 冪等な処理
 操作自体を最大一回だけ(ユニーク)にする
=

ユニーク制約 + トランザクションの合成
パターン: Exactly Once
 最大一回だけ成功する処理を無限に繰り返す
=

冪等な処理 + Task Queue
パターン: BASE Transaction
 自分を変更後、相手の変更を確実に一度だけ適用
=
read-modify-write + Exactly Once + 合成
2010/01/22
appengine ja night #4 - @ashigeru
54
おわりに

App Engineのトランザクションは「パズ
ル」になりがち
 複雑な制約を考慮しつつ、時間内に解く
 ルールも定石もあるので、積み重ねが大切

「仮説→検証」のサイクルが必要な段階
 みんなで情報共有
 パターンやアンチパターンを持ち寄ろう
2010/01/22
appengine ja night #4 - @ashigeru
55
参考文献

Programming Google App Engine
 Oreilly

& Associates Inc, 2009/11
リレーショナルデータベース入門
 サイエンス社,

トランザクション処理
 日経BP社,

2003/03
2001/10
BASE: An Acid Alternative
 http://queue.acm.org/detail.cfm?id=1394128
2010/01/22
appengine ja night #4 - @ashigeru
56
Question + Discussion

実はあと数枚残ってる
2010/01/22
appengine ja night #4 - @ashigeru
57
Transaction Puzzlers
Advanced Topics
appengine ja night #4
@ashigeru
2種類の並行性制御

悲観的並行性制御

 リソースを独占できな
 リソースを独占し、
他人を待たせる

特徴
楽観的並行性制御
かったら、やり直し

特徴
 他人に迷惑をかける
 他人に迷惑をかけない
 成功確率が高い
 失敗し続ける場合も
 常にオーバーヘッド
 成功すれば速い
誰に迷惑が掛かるか、という点で異なる
2010/01/22
appengine ja night #4 - @ashigeru
59
その他のパターン

Sharding
 エンティティを複数のEGに分散

Long Running Transaction
 リクエストをまたぐ長いトランザクション

Software Global Transaction
 ソフトウェアで2PCプロトコルを実装

Software MVCC
 ソフトウェアでMVCCを実装
2010/01/22
appengine ja night #4 - @ashigeru
60
トランザクション設計のポイント
データの局所性を生かす
 更新頻度を意識する
 本当の制約を見極める

2010/01/22
appengine ja night #4 - @ashigeru
61
ポイント: データの局所性を生かす

ユーザ情報はユーザごとに独立している
 同一ユーザは同時にリクエストしないことが多い
 多くのユーザを同時に捌いても並行稼動

「複数のユーザが共有するリソース」に注意
 カウンタなどは典型例
 チケット予約なども該当する

ユースケース分析は重要
 単一ユースケースの並列性から考える
 いざとなれば非正規化+Eventual
2010/01/22
Consistency
appengine ja night #4 - @ashigeru
62
ポイント: 更新頻度を意識する

更新頻度の観点でエンティティを分類
 稀に更新/常に更新のプロパティを共存させない
 更新しないプロパティはどこに混ぜてもいい

マスタ/トランザクションデータでは不十分
 トランザクションデータも参照系と更新系に
 参照系はトランザクション処理しなくてもよい場合
がある

もちろん、更新に局所性があれば問題ない
 ローカルトランザクションを衝突させない設計
2010/01/22
appengine ja night #4 - @ashigeru
63
ポイント: 本当の制約を見極める


Strong Consistencyはオーバースペック
どの程度の不整合がどの順で許されるか考える
 自動販売機の支払い/商品受け取り
(数秒)
 コンビニの支払い/商品受け取り (数十秒)
 ファーストフードの支払い/食事 (数分)
 レストランの支払い/食事 (▲数十分)

同時にアプリケーション作成コストも考える
 不整合の許容は制御することが増えすぎる
 提供先のビジネス特性を考慮し、合意を得る必要性
 あらゆる観点で「必要十分」に
2010/01/22
appengine ja night #4 - @ashigeru
64

Download Report