- SlideBoom

松尾津邑研究室 M2 熊崎宏樹

大規模サービスを支えるミドルウェアの一つとして
キーバリューストア(KVS)が注目されている
 複数の計算機に分散する事で性能をスケールアウト可能
 計算機故障への耐性も冗長化で実現
 一貫性の問題からKVSを利用できないケース
A
B
1000円 1000円
T1:AからBへ100円送金
T2:BからAへ50円送金
1000 = get(A);
1000 = get(B);
set(A, 900);
set(B, 1100);
1000 = get(A);
1000 = get(B);
set(A, 950);
set(B, 1050);
数が合わない
900円 1050円

キーバリューペアが指定した値の場合のみ新しい
値が保存するCASコマンド
 条件判定と保存をアトミックに行える

キーバリューペアが存在しない場合に限り保存に
成功するaddコマンド
 KVP不在の確認と保存をアトミックに行える
アトミックな操作が利用可能

上手く動きそうに見える
キー
A
B
バリュー
1000
900
1000
1100
lock(A);
lock(B);
set(A, 900);
set(B, 1100);
unlock(A);
unlock(B);

クライアントが離脱すると破綻する
 タイムアウトでアンロックしてもデータが矛盾する
キー
A
B
永久にロッ
バリュー永久にロック
ク
されたまま
1000
900 されたまま
1000
離脱
永久にロッ
データが
ク
矛盾する
されたまま
lock(A);
lock(B);
set(A, 900);
set(B, 1100);
unlock(A);
unlock(B);



通常のKVSの機能を用いてトランザクションを実行可能
なミドルウェアを提案
分散KVS上でも同様に利用可能
スケールアウト性能や対故障性の恩恵を受けられる
一貫性を保証できるため
より多くの場面でスケールアウト性能や
耐故障性を得られる


DynamicSTMを下敷きにKVS上で同様の機能を実現
DynamicSTMとは






CPU上での並行処理を補助するアルゴリズム
CAS命令を用いて実装可能
複数のオブジェクトを一括に更新可能
ロックを用いずデッドロックが発生しない
メモリの間接参照を用いて集約化を行う
GC(GarbageCollection)のある環境を想定している
多くのKVSには間接参照とGCが無い
KVS上でそれらを実現
Software transactional memory for dynamic-sized data structures
2003 Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III

キーは文字列なのでバリューとして保持できる
A
キー
バリュー
A
B
B
C
B
C

通常のキーバリューペア(KVP)をトランザクション
のために拡張したもの
keyA
value
old
keyA
new
value value’ OwnerName
トランザクション
ステータス
active


バリューがcommited、abort、activeの3状態のど
れかを取るキーバリューペア
トランザクションの現在の状態を表す
 commited:完了
 abort:リトライ待ち
 active:実行中
key OwnerName
トランザクション
ステータス
value
active

ownerの状態によって読み出し方を分岐
 commited:Newの値を読み出す
 abort:Oldの値を読み出す
 active:競合を解決する(後述)
key
old new OwnerName
commited
Abort
active

KVSには2つのKVPが保存されるだけ
キー
keyA
Owner:T1
バリュー
Value
Value’
Owner:T1
active
keyA
value value’ owner
commiｔted
commiｔted
省略して表記
トランザクションを用いて口座Aから口座Bへ送金
Transaction {
a = get(A);
b = get(B);
set(A, a – 100);
set(B, b + 100);
}
を実現する

ステータスを初期化
初期化

必要なTKVPを更新
獲得・更新

ステータスをコミットへ
コミット
yes

成功したら後片付け
成功？
後処理
no


自身のステータスをactiveとしてキーバリューストア
に新たに保存する
キーはランダムな文字列を生成する
Transaction{
a = get(A);
b = get(B);
set(A, a – 100);
set(B, b + 100);
}
set(T1，active)
T1
active

ステータスを初期化
初期化

必要なTKVPを更新
獲得・更新

ステータスをコミットへ
コミット
yes

成功したら後片付け
成功？
後処理
no


KVPは通常通り読む
TKVPはStatusの値によって最新の値が変わる
A
最新の値
A
commited
commitedなら new を読む
A
abort
abortなら old を読む



TKVPならば通常のKVPに書き換えてから読む
書き換えにはCASを用いる
不要となったトランザクションステータスは消す
Commitedなのでnew
A
T1
commited
T1
abort
Abortなのでold
A

A, Bを通常のKVPへと書き換えながら読み出す
a
A
B
b
Transaction{
a = get(A);
commited
b = get(B);
set(A, a – 100);
set(B, b + 100);
}
abort


A, BをTKVPへと書き換える
所有者として自分のステータスを指させる
A
a a - 100 T1
active
B
b b + 100 T1
Transaction{
a = get(A);
b = get(B);
set(A, a – 100);
set(B, b + 100);
}

ステータスを初期化
初期化

必要なTKVPを更新
獲得・更新

ステータスをコミットへ
コミット
yes

成功したら後片付け
成功？
後処理
no

ステータスがactiveであることを確認して
commitedへ書き換える
Transaction{
a = get(A);
b = get(B);
set(A, a – 100);
set(B, b + 100);
}
CAS
cas(T1，committed)
T1
commited
active

ステータスをcommittedへCAS
 newの値が一斉に外部から最新の値として観測される
A
B
Transaction{
CAS
a = get(A);
a a - 100 T1
b = get(B);
set(A, a – 100);
commited
active
set(B, b + 100);
}
b b + 100 T1
最新の値

ステータスを初期化
初期化

必要なTKVPを更新
獲得・更新

ステータスをコミットへ
コミット
yes

成功したら後片付け
成功？
後処理
no


ステータスを消すためKVPへ戻す
書き換えはCASを用いて行い、CAS失敗は無視
 失敗したということは他のトランザクションが引き継いだ事
を意味するため問題ない

最終的に不要なKVPが残らない
A
a a - 100 T1
committed
B
b b + 100 T1

全体として送るコマンドの一例が以下
set(hoge，active)
gets(A)
cas(A, a)
gets(B)
cas(A，[a, a-100, T1])
cas(B，[b, b+100, T1])
cas(T1，committed)
cas(A, a-100);
cas(B, b+100);
delete(T1);
初期化
Aの獲得
Bの獲得
準備
Aの更新
Bの更新
コミット
Aの後処理
Bの後処理
ステータス削除
後処理

ステータスを初期化
初期化

必要なTKVPを更新
獲得・更新

ステータスをコミットへ
コミット
yes

成功したら後片付け
成功？
後処理
no


コミット時にステータスがabortに書き換えられていたら
コミット失敗。トランザクションを始めからやり直す
abortに書き変わっているというのはどういう状況か
T1
abort

statusの値によって読み出し方を分岐
 commited:Newの値を読み出す
 abort:Oldの値を読み出す
 active:競合を解決する
競合を解決する際にAbortされる
key
old new status
active
トランザクションT1
Transaction{
a = get(A);
b = get(B);
set(A, a - 100);
set(B, b + 100);
トランザクションT2
Transaction{
set(B, 950);


所有者のstatusをabortへ書き換える
TKVPを奪う
トランザクションT2
 後処理も行う事でゴミを残さない
A
a a - 100 T1
CAS
Bが欲しいけど
Bを獲得できた
使用中だ…
abort
active
最新の値
B
Transaction{
set(b, 950);
+ 100 T2
b b 950
T1
Abort
active

後発のトランザクションが所有権を奪う
 デッドロックも矛盾も発生しない
 ステータスも削除するのでゴミが残らない
 クライアント離脱への耐性がある
A
a a - 100 T1
ロールバックされる active
abort
B
b b + 100 T1
離脱
Abort
active

後発のトランザクションが所有権を奪う
 デッドロックも矛盾も発生しない
 ステータスも削除するのでゴミが残らない
 クライアント離脱への耐性がある
A
a a - 100 T1
離脱
後処理が引き継がれる
committed
B
b b + 100 T1
active
離脱
GET/CASn回
active
成功・失敗の境目→
CAS1回
CASn回
commited




Pythonでクライアントライブラリを実装
KVSとしてmemcachedをConsistentHashingで利用
1000000件の口座からランダムに2つを選びトランザクショ
ンで残高の一部を移動させる
計算機はAmazonEC2のc1.xlargeインスタンスを50台使用
 CPU: 8コア
 MEMORY:7GB
 Network:1GbE


クライアントとして50台使用
そのうち1台～15台をKVSサーバとしても使用
性能が飽和していないため台数を増やして検証したい
EC2内での物理ネットワーク構成が不定なためか性能が安定しない
トランザクションなしでのアクセスと比較したい
トランザクションなしでは12万qpsほどが上限だったので
1サーバでの性能である約600qpsはおよそ1/200ほどの速度低下
これは想定値より遥かに低いので原因の究明が必要


既存のキーバリューストアの上でトランザクショ
ン処理を行う方法を提案し実装・評価した
更なる評価を行う必要がある
トランザクションを利用した範囲検索の実装
 書き換えの遅延化でスループットの向上


Download Report