DEIM Forum 2017 H3-1

無改造な計算機資源を用いた One-Copy Serializable ミドルウェアの検討
三島健†† 日本電信電話株式会社 〒 180–8585 東京都武蔵野市緑町 3–9–11
E-mail: †mishima.takeshi@lab.ntt.co.jp
あらまし

複数の単体データベース（レプリカ）で構成されるクラスタに対し，低コストで高性能かつレプリカ間の一貫性維持を実現するため，One-Copy Serializability（1-Copy-SR）を提供するデータベースレプリケーションミド
ルウェアの検討がなされている．このデータベースクラスタにおいて，レプリカでスナップショット分離を行うことが提案されているが，データ破壊を起こすケースがあることが知られており，これを回避するには破壊検出のため，ミドルウェアとレプリカ間に専用のインタフェース，ならびに機能追加を行わなければならない．本論文では標準である SQL インターフェースを用いて 1-Copy-SR を実現するミドルウェア上の SQL 転送ルールを提案する．また，このルールを用いることで 1-Copy-SR を実現するミドルウェアである Libera を提案する．評価の結果，既存の提案がほとんど性能向上できないのに対して，Libera は参照が多い負荷の場合にスケーラブルな性能向上を実現できた．
キーワード

One-Copy Serializability，シリアライザブルスナップショット分離，ミドルウェア

1. は じ め にの代わりに anomalies が発生しコンシステンシを崩してしまう
可能性があるという欠点を持つ．[2]．

従来より，高性能化するためのデータベースクラスタの検討

Bornea らは ローカルには SI を提供しグローバルにはがさかんである．その中でも市中製品を無改造で使うことで1-copy-SR を提供する Serializable Generalized Snapshot Iso-

低コスト化を実現するレプリケーションミドルウェア（ピュアlation (SGSI) アルゴリズム [7] を提案している．しかし，コンミドルウェアと呼ぶ）に注目が集まっている．従って，ミドル

システンシを維持するために，大きなオーバヘッドを生じるグ

ウェアは高性能化と低コスト化の他にレプリカ間でコンシステ

ループコミュニケーション（高信頼化マルチキャストの一種）

ンシを保つことが課題である．単一のレプリカでコンシステンが必要となる．また，SI anomaly を見つけ出すためにミドルシを保つために最も理想的なトランザクション分離レベルはシウェアに検証機能が必要になる．検証機能には検証専用のデーリアライザブルである [1]．その理由は，シリアライザブルではタベースエンジンが必要で，本来のデータベースエンジンのANSI SQL phenomena で知られている様々なデータ一貫性破

データベースと同じスキーマを用意しておく必要がある．彼ら

壊が起きないからである [2]．複数のレプリカからなるデータ

はデータベースエンジンとして Microsoft SQL Server 2008，

ベースクラスタもクライアントにシリアライザブルを提供する

検証専用のデータベースエンジンとして SQLite.NET を使っことが望ましい（One-Copy Serializability: 1-Copy-SR と呼ている．

ぶ）．例えば，Amza らは distributed versioning (DV) と呼ぶ

2008 年には， 新しいシリアライザブルのアルゴリズムとし二相ロックをベースにした 1-Copy-SR を提供するミドルウェて，シリアライザブルの性能改善を狙ったシリアライザブルス

アを提案している [3]．トランザクションの開始時にテーブル

ナップショット分離 (SSI) が提案された [8]. SSI では，トランにアクセスする順序を示すバージョン番号をトランザクション

ザクションは SI で実行するのとともに実行中に SI anomaliesに与え，バージョン番号の順序でロックをかけながらアクセスを検出・回避し，結果としてシリアライザブルを提供する．こする．ロックはテーブルにアクセスする必要がなくなった時点

れは高性能化を実現するとともに anomalies を発生しない．

で解放される．DV はグローバルに 1-Copy-SR を提供しロー

本論文では，SSI を提供するレプリカからなるクラスタがカルにはシリアライザブルを提供する．残念なことにシリアラ

1-Copy-SR を保証するための SQL 転送ルールを提案する．そイザブルは性能が低いという問題点があり，これが 1-Copy-SRのルールを使ってクライアントに 1-Copy-SR を提供する Libera

も性能が低いという欠点を生み出す．

と呼ぶミドルウェアを提案する．本論文の貢献を以下に示す．

1995 年には，新たな分離レベルとして Gray らがスナップ•

我々は SSI を提供するデータベースレプリカを使ってショット分離 (SI) を提案した [4]．参照命令は更新命令をブロッ

1-Copy-SR を保証するための SQL 転送ルールを提案する．こクしないため高い並列性を実現でき，それゆえに高性能化も期のルールはシンプルであるため，ピュアミドルウェアを作るた待できる [2]．従って，SI のレプリカを複数使ったクラスタ構成

めには有益である．

でクライアントに SI を提供する One-Copy Snapshot Isolation(1-Copy-SI) [5] が注目された．例えば，我々はローカルには SI•

我々は上記ルールを使って Libera と呼ぶ 1-Copy-SR を提供するミドルウェアのプロトタイプを提案する．我々の知るを提供しグローバルには 1-Copy-SI を提供する Pangea と呼限りでは SSI を使って 1-Copy-SR を提供する最初のミドルぶミドルウェアを提案した [6]．1-Copy-SI では SI は高性能化

ウェアである．

•

我々は TPC-W ベンチマークを使って評価を行った．そ2. 2 依 存 関 係の結果，参照が多い環境では 1-Copy-SR を従来技術でミドル

トランザクション Ti と Tj が依存関係を持つとは，（１）あウェアを作った場合に比べて Libera は高い性能を示すことがる DBM Si が他の DBMS とは異なる順序でトランザクショ

分かった．

ン Ti と Tj を実行し，（２）かつ，両 DBMS は異なる結果を出力する場合を言う．この二つの DBMS を同期させるには両2. 予 備 知 識

DBMS で全てのディペンデンシを同じ順序で実行する必要が本章では，1-Copy-SR を論理的に議論するために必要な for-ある．データアイテム xj がデータアイテム xi (i < j) の「直mal apparatus を導入する．また，関連する知識として SI と後の更新者」と呼ぶ場合は，（１）データアイテム xi が参照まSSI, Pangea についても概説する．

たは更新されたこと，（２）データアイテム xj は更新によって

2. 1 データベースモデル

生成されたこと，（３）xi と ij との間に他の更新が無いこと，

database はデータアイテムの集合を構成する．各データアを指す．クエリ oi と oj がディペンデンシを持つとは，最低限

イテムは value を持つ．value はある点においてデータベース

一つのクエリが更新であり，実行順序が異なると実行結果が異の state を構成する．データアイテムは x または y ，z と小文なる場合を意味する．以下のように，三つのディペンデンシが字で表記する．DBMS はデータベースにアクセスするコマン存在する．

ドをサポートするハードウェアとソフトウェアのかたまりであ［定義 1］（dependencies） 二つのクエリ間で生じる三つの de-る．このコマンドはクエリと呼ぶ．トランザクション Ti は参pendency は次の通りである．

照クエリ，更新クエリ，終了クエリ（コミットまたはアボート）• （１）クエリ oi はデータアイテム x を更新し，（２）クである．下付き文字 i は i 番目のトランザクションを表し，他

エリ oj はこのバージョンのデータアイテム xi を読む，場合，のトランザクションと区別するために使用する．従って，xi は

クエリ oi と oj は wr-dependency があると言う．

トランザクション Ti によって更新されたデータアイテム x を• （１）クエリ oi は Tk によって更新されたデータアイテ表す．また，wi,p (xi ) はデータアイテム xi を更新したトラン

ム x を参照し，クエリ oj が直後の更新者である場合，クエリ

ザクション Ti の p 番目の更新クエリを表す．同様に，ri,q (xj )oi と oj は rw-dependency があると言う．

はデータアイテム xj に対する q 番目の参照クエリを表す．ciと ai は Ti のそれぞれコミットクエリとアボートクエリを表す．
もしトランザクション Tj がスタートする前にトランザクショ
ン Ti がコミットしたならば Ti と Tj はシリアルである，と• （１）クエリ oi がデータアイテム x に対して更新し xiとした後，クエリ oj が直後の更新者である場合，クエリ oi とoj は ww-dependency があると言う．
2. 3 スナップショット分離言う．もし，トランザクション Tj がスタートする前であって，

SI は強い分離レベルであると同時に高性能である [4]．SI の

トランザクション Ti はスタートしているがコミットしていな

下ではトランザクション Ti はコミットされたデータベースのい状態の時，トランザクション Ti とトランザクション Tj は状態，すなわちスナップショットからデータを読み込む．デー

平行であると言う．もし Rm

タアイテムを更新する場合はそのスナップショットに対して行と xn とを持っていて xm と xn が同じデータを保持するならわれる．トランザクション Ti のスナップショットは最初の参照

ば，Rm

が R と同じデータアイテム xnと R は同値であると言う．もし，複数のトランザク

クエリ ri,1 (xp ) を実行する直前に暗に作成される．SI では参ション集合が平行に実行されていたら，クエリは交互に入り組

照クエリが更新クエリをブロックすることは無い，逆に更新ク

むかもしれない．DBMS がクエリを実行しようとする順序をエリが参照クエリをブロックすることもない．この特徴が平行

スケジュールという．ヒストリは実際にクエリを実行した順序

実行を増やし性能が向上する理由である．

mnを表す．スケジュールはこれからトライする順序であってヒス

2. 4 シリアライザブルスナップショット分離

トリは実際に実行した順序である．

2008 年に Cahill らはシリアライザブルスナップショット分

データアイテムを参照する前に更新するいわゆるブラインド

離 (SSI) と呼ぶ新しくて強い分離レベルを提案した [8]．SSI は

更新はないものと仮定する [9], [10]. Ti のスナップショットは実行中に SI anomaly が起きる可能性がある実行パターンを探

ri,1 (xk ) が実行される直前である．基本的には wi (x) クエリはし，見つけ次第アボートする．このアルゴリズムは楽観的平行

全てのレプリカで実行し，参照クエリ ri (x) は一つのレプリカ

制御に似ているが SI アノマリを見つけ次第即座にアボートすから読むといういわゆる ROWA モデルをベースとする．代表る点が異なる．この提案手法は全てのシリアライザブルでない

レプリカとはアクセスする毎に全レプリカの中からランダム

トランザクションの実行をアボートするが，アボートする必要に一つ決定する．リーダレプリカは，代表レプリカと同様一つの無い実行までアボートする可能性がある．

のレプリカが選定されたものだが，一度決めたら変わらない．
フォロワレプリカとは全てのレプリカからリーダレプリカを除いたレプリカの集合である．グローバルトランザクションとはクライアントが送信したトランザクションを言い，ローカルト
ランザクションはレプリカが実行するトランザクションを言う．

•

アプリケーションが動作中であってもこのアルゴリズム

はシリアライザブルを保証する．

•

このアルゴリズムによって参照クエリが遅延することはない．また，参照クエリは更新クエリの実行を妨げない．

•

様々な環境において，スループットは SI とほぼ同じであり二相ロックよりも良い．

•

SSI のアルゴリズムは SI を提供するシステムを少し改造するだけで実装できる．

行された直前に生成される．従って，参照クエリがいつ実行されようともその実行は最初の参照クエリ ri,1 (xk ) が実行された

2. 5 Pangea [6]場合行われたのと等価である．

2. 5. 1 Same Snapshot Creation プロトコル［補題 2］（論理的な更新クエリ） トランザクション Ti が更新

もし複数のレプリカがそれぞれ異なるスナップショットからクエリ wi,1 (xi ), wi,2 (xi ), ... , wi,n (xi ) を実行する時，コミッ

データアイテムを参照したり更新したりすると，レプリカ間のトクエリ ci (xi ) が実行された時に全ての更新クエリを実行した

コンシステンシは崩れてしまう．従って，（１）最初の参照ク

場合に等価である．

エリを実行する直前の全てのコミットされたデータをスナップ

証明. SSI では全ての更新クエリは同一のスナップショット

ショットは含むこと，（２）スナップショットへの変更がデータに対して行われ更新内容はコミット時に確定される．従って，ベースに反映されるのはコミットクエリを実行した時であるこ

更新クエリがいつ実行されようともその実行はコミットクエリと，を考えると，最初の参照クエリとコミットクエリの相対順

ci (xi ) が実行された場合に行われたのと等価である．

序を全てのレプリカで同じにしなければならない．より具体的にはコミットクエリを実行する時は最初の参照クエリが一つも実行されないようにしなければならない．また，逆に，最初の参照クエリを実行する時はコミットクエリが一つも実行されないようにしなければならない．

2. 5. 2 Leader/follower プロトコル
あらかじめ，Pangea はリーダのレプリカを選出し残りのレプリカをフォロワとする．Pangea は一旦リーダとフォロワを決めると，障害が起きない限りその役割分担を変えることは無い．あるトランザクションのスナップショットを全てのレプリカで同じにするためには Sect.2. 5. 1 節で述べたようにする．

Leader/Follower プロトコルは次に示す通りである．
(1) Pangea クライアントが送信した更新クエリを受信する．
(2) Pangea は leader にだけ更新クエリを送信する．
(3) leader の ww-dependency の勝者を決定する．
(4) Pangea は正解応答を受けとったら，(5) Pangea 正解応答が返ってきた更新クエリを follower へ送信する．

(6) Pangea は follower から正解応答を受信する．
Pangea は参照クエリを一つのレプリカのみに送信する．最初のクエリ（参照クエリも含む）とコミットクエリは全てのレプリカに送信する．

3. シリアライザブルスナップショット分離を使った One Copy Serializability の実現方法
本章では 1-Copy-SR を実現するとともにレプリカ間でコン
システンシ維持を実現する新しいルールを提案する．

3. 1 dependency とクエリの関係
レプリカがクエリを送信し応答を受信した後に新たなクエリを送信する．レプリカが新しいクエリを送信するのは応答を受信した後であることに注意されたい．SSI では参照クエリと更新クエリは論理的にはそれらが送信された時刻に実行されず以下のタイミングで実行される．
［補題 1］（論理的な参照クエリ） トランザクション Ti が参照
クエリ ri,1 (xk ), ri,2 (xk ), ... , ri,n (xk ) を実行する時，最初のクエリ ri,1 (xk ) が実行された時に全ての参照クエリを実行した場合に等価である．
証明. SSI では全ての参照クエリは同一のスナップショット
から読み込む．スナップショットは最初のクエリ ri,1 (xk ) が実

ミドルウェアレベルでクエリからトランザクションの依存関係を取得するためには dependency とクエリ間で次のような関係がある．
［補題 3］（wr-dependency） トランザクション Ti と Tj において，もし Ti が更新トランザクションであり，かつ ci < rj,1 (xi )の関係が成り立つならばトランザクション Ti と Tj は wr-

dependency である．
証明. Ti は更新トランザクションであるから wi,p (xi ) < ciが成り立つ．従って，wi,p (xi ) < ci < rj,1 (xi ) である．定義 1
よりこの関係は wr-dependency である．
［補題 4］（ww-dependency） もし Ti と Tj が更新トランザク
ションであって，更新クエリに wi,p (xi ) < wj,q (xj ) の関係が成り立つならば，トランザクション Ti と Tj は ww-dependency
である.
証明. もし wi,p (xi ) < wj,q (xj ) であるならば，定義 1 より
トランザクション Ti と Tj は ww-dependency であることは明らかである．
［補題 5］（rw-dependency） Ti は更新トランザクションであり rj,1 (xk ) < ci であるならば，トランザクション Ti と Tj は

rw-dependency である．
証明. Ti は更新トランザクションであるから，定義 1 と 2より rj,1 (xk ) < wi,q (xi ) < ci である．これは rw-dependencyに相当する．
［定義 2］（commit abort） もし Ti と Tj ，Tk が dangerous

structure [11] を持っているならば，ci または cj ，ck のうちど
れかはアボートされる．

3. 2 SSI-Schedule
SSI では補題 1 から 5，さらに定義 2 より，次のスケジュー
ルを定義する．
［定義 3］（SSI-schedule） Tと す る ．Tを ト ラ ン ザ ク ション の 集 合に 対 す る SSI-schedule S は ク エ リ o∈{ri,1 (xk ), ri,2 (xk ), ..., ri,m (xk ), wi,1 (xi ), wi,2 (xi ), ...,
wi,n (xi ), ci } のシーケンスである．この時，S は次のような特徴を持つ．

(1) 各トランザクション Ti ∈ T は ri,1 (xk ) < ci である．
(2) もしトランザクション Ti と Tj ，Tk の集合が dangerous
structure を持っていたら，どれか一つのトランザクションはアボートさせる．

SI-schedules と呼ぶ同じような定義が過去に二つあった [5] [6]．

(3) もし，グローバルトランザクション Ti が更新を含むト

SSI-schedule と異なる点は対象が SI であることである．まランザクションであるならば，mapping function F はフォロ

た，[5] の schedule は SQL ではなく writeset を対象としていワレプリカ Rin のために更新クエリを持ったローカルトランザ

る．さらに，[6] の schedule は ww-dependency しか対象としクションを出力する．

ていない．

3. 5 1CS Rule
レプリカ間のコンシステンシ維持を実現すると同時に 1-

3. 3 SSI-Equivalent
レプリカ間のコンシステンシを議論するためには，equivalentの概念は重要である．

Copy-SR を実現するルールを提案する．
［定義 6］（1CS rule） R を ROWA アプローチに従うレプリ［定義 4］（SSI-equvalent） もし SSI-schedule S m と S n が次カの集合とする．T をグローバルトランザクションの集合との特徴を満足するならば，Sする．S をグローバルトランザクション T の集合に対する

m

とS

n

は SSI-equvalent である

という．

(1)

SSI-schedule とする．レプリカ Rm ∈ R のローカルトランザmm
Ti が更新トランザクションであり cm⇔
i < rj,1 ∈ Snncn
i < rj,1 ∈ S である．

下の特徴が成り立つ時 S は 1-Copy-SR を提供する．

mm(2) Ti が更新トランザクションであり rj,1
< cm
⇔
i ∈ S
n
n
rj,1
< cn
i ∈ S である．

(3)(1) ∪k = rmap(T , R) である ROWA mapping function
rmap が存在する．

m
Ti と Tj が更新トランザクションであり， wi,p(xi ) <mnnwj,q(xj ) ∈ S m ⇔ wi,p(xi ) < wj,q(xi ) ∈ S n である．

(4)

クションの集合 T m に対する SSI-schedule を S m とする．以

(2) Ti , Tj ∈ T から変換した Tim , Tjm ∈ T m に対する各 S m
を含む T に対する SSI-schedule S が存在する．

mm
Ti が更新トランザクションであり, cm⇔
i < cj ∈ Sncn
i < cj ∈ S である．

mm(a) Ti は更新トランザクションであり, cm⇔
i < rj,1 ∈ S

ci < rj,1 ∈ Smm⇔(b) Ti は更新トランザクションであり, rj,1
< cm
i ∈ S

［定理 1］（SSI-equvalent） Rm と Rn は同じデータアイテム

x を持っており，かつ，xm と xn は両方とも同じ値である．もrj,1 < ci ∈ S.
m(xi ) <(c) Ti と Tj は更新トランザクションであり, wi,p

し，S m と S n が SSI-equivalent である時 Rm と Rn はコン
システンシを保つ．

m
n
n
wj,q
(xj ) ∈ S m ⇔ wi,p(xi ) < wj,q(xi ) ∈ S

証明. S m と S n が SSI-equivalent であるならば，補題 3 と(1) より S

mand S には同じ wr-dependency を持つ．また，n

補題 4 と (3) から S

m

に S

n

同じ ww-dependency を持つ．

m(d) Ti と Tj は更新トランザクションであり, cm
i < cj ∈Sm⇔ ci < cj ∈ S.

1CS の特徴は以下の通りである．

に同じ rw-dependency［定理 2］（1CS rule） もし，仮想的な一つのノード R のスケを持つ．(4) は SI anomaly を排除する．従って，三つ全てのジュール S が 1CS ルールに従うならば，S は 1-Copy-SR を

dependency が S提供する．

さらに，補題 5 と (2) から S
m

と S

n

m

とS

n

で成り立つため，anomaly は R

m

証明. 最初に更新を含むトランザクションに注目する．(1) よand R に存在しせず consistent である．
n

りリーダ Rm のためのローカルトランザクション Ti が作成さ

3. 4 Mapping Function
グローバルトランザクション（ミドルウェアが受けとるトラれる．もし，リーダトランザクション Ti が 1CR ルールの (2)ンザクション）からローカルトランザクション（ミドルウェア

を満たすならリーダ Rm と仮想ノード R は equivalent である．

から送信するトランザクション）を生成する mapping function

従って，S m が 1-Copy-SR を提供するならば S も 1-Copy-SRを説明する．mapping function は以下に定義する．

を提供する．次に参照のみのトランザクションに注目する．(1)［定義 5］（Mapping Function） T

よりフォロワのためのローカルトランザクション Tj が作成さをグローバルトラン

ザ ク ション と し ，各 ト ラ ン ザ ク ション は ク エ リ oi∈れる．もし，フォロワスケジュール Si が 1CR ルールの (2) を{ri,1 , ri,2 , ..., ri,p , wi,1 , wi,2 , ..., wi,q , ci , ai } を 持 つ ．mapping満たすならば，フォロワ Rn と仮想ノード R は equivalent でfunction F はグローバルトランザクションからローカルト

ある．S n は 1-Copy-SR を保証するので S は 1-Copy-SR を

ランザクション T l , T m , T n を以下のようにして出力する．

提供する．以上より，S は 1-Copy-SR を提供する．

(1) もし，グローバルトランザクション Ti が参照のみのト
ランザクションであるならば，mapping function F は一つの代表レプリカ Ril のために全てのクエリを持ったローカルトラ

4. Libera
本章では，1-Copy-SR を実現する Libera と呼ぶピュアミド

ンザクション Til を出力する．

ルウェアを提案する．我々のアプローチは現実的なミドルウェア(2) もし，グローバルトランザクション Ti が更新を含むトを実現するために市中技術を使って高性能化を実現する．このランザクションであるならば，mapping function F はリーダ

ために，same snapshot creation プロトコル, Leader/Follower

レプリカ Rim のために全てのクエリを持ったローカルトランザ

プロトコル, SSI の certifier を利用する．既存のレプリケーショ

クション Tim を出力する．また，mapping function F はフォ

ンミドルウェア [3], [7] を拡張して 1-Copy-SR を提供可能では

ロワレプリカ Rin のために最初の参照クエリ ri,1 とコミットク

あるが，たくさんの高価な実装に悩まされる．例えば，グルー

エリ ci を持ったローカルトランザクションを出力する．

プコミュニケーションの実現，readset の作成方法，writeset のAlgorithm 1 Read-only transaction

T1

T2

T3

BEGIN;UPDATE table1
SET a=1 WHERE a=0;
COMMIT;

BEGIN;UPDATE table1
SET a=0 WHERE a=1;
COMMIT;

BEGIN;UPDATE table2
SET a=1 WHERE a=0;
COMMIT;

1: receive a query from a client
2: send the query to the representative replica
3: receive an answer from the replica
4: send the answer to the client

ルと (b) Leader/Follower プロトコルを (c) 各レプリカが持っている certifier の機能をミドルウェアで組み合わせることであ

図 1 Sample transactions

る．つまり，
挿入方法，SSI anomaly を検出する certifier の実現，などで(a) Libera は全てのレプリカで同じスナップショットを作ある．本章では，市中技術を無改造で用いて 1-Copy-SR を実成し，(b+c) もし，リーダレプリカの certifier が anomaly を見つけ現する新しいミドルウェアを提案する．

たとすると，Libera は全てのレプリカでその原因のトランザクa
UPDATE table1
SET a=1 WHERE a=0a1
1

COMMIT

0
1

ションをアボートする，もし，なんら anomaly が見つからな

1

かったとすると，全てのフォロワレプリカはコミットクエリを

1

1

1

1

1

0
(2)

1

a

(3)

DBMS へ送信されたクエリを受信するため，Libera はクライアントと DBMS の間に位置する．Libera は市中製品を無改造で使うだけでなく，certifier, group communication, readset
ない．

a4. 4 アルゴリズム00

本節では Libera の動作を詳細に説明する．もしあるレプリ

00

カからアボート応答を受け取ったとすると，Libera は全てのレ

00

プリカにロールバッククエリを送信する．あらかじめ，Libera

00は全てのレプリカからリーダレプリカを選出し，残りをフォロ

(4)

(5)

ワと決めておかなければならない．一旦、役割を決めたら障害a

図2

4. 3 Libera アーキテクチャの抽出機能，writeset の作成機能，など複雑な機能は必要とし

UPDATE table1
SET a=0 WHERE a=1(1)

平行に実行する．

ABORTが起きない限り役割を変えない．Libera は参照のみのトランザ
Problem of commit order

4. 1 問題の提起
SSI ではコミットの順序が変わると最終的な結果が異なるケースがある．例として，図 1 に示す三つのトランザクション

T1 と T2 , T3 と図 2(1) に示すテーブル 1 を考える．また，三つのトランザクションは平行して実行されているとする．図 2(2)に示すように T1 は UPDATE クエリを実行する．また，図2(4) に示すように T2 は UPDATE クエリを実行する．コミッ
トの順序に注意されたい．もし，T1 のコミットクエリが T2 よりも早かったとすると，テーブルは図 2(3) で確定し，T2 は図

2(5) に示すようにアボートされる．反対に T2 のコミットクエ
リが T1 よりも早かったとすると，テーブルは図 2(4) で確定し，

T1 はアボートされる．このアボートは write skew anomaly によるものである．図 1 に示すように三番目のトランザクション

T3 を考える．この場合何の anomaly も発生しないので T1 とT3 のコミットクエリの順序は重要ではない．従って，複数のレプリカでコンシステンシを保つためには anomalies を生じる

COMMIT クエリはシリアルに実行しなければならない．また，
anomalies を生じないコミットクエリは性能を上げるために同時並行に実行すべきである．

4. 2 キーアイデア
我々のキーアイデアは (a) same snapshot creation プロトコ

クションのために全てのトランザクションの中からランダムに
代表レプリカを決める．代表レプリカは参照トランザクション毎に決める．
アルゴリズム 1 は参照のみのトランザクションを受信した時の Libera の動作である．Libera はクライアントと代表レプリカの間にあり，クエリと応答を中継するだけである．
アルゴリズム 2 は更新を含むトランザクションを Libera が受信した時の動作である．もし，Libera が更新クエリを受信したら (line 1)，Libera は Leader/Follower プロトコルを実行す
る； つまり，Libera はクエリをリーダにのみ送信する (line 3)．

Libera はリーダから応答を受信する (line 4)，もし，応答がア
ボートである場合 (line 5)，Libera はロールバッククエリを全てのレプリカに送信する (line 6)．そして，全てのレプリカから応答を受信する (line 7)．もし，応答が成功であった場合，

Libera は全てのフォロワにクエリを送信する (line 9)．そして全てのフォロワから応答を受信したら (line 10)，一つをクライ
アントへ返す (line 12)．
もし，Libera が最初の参照クエリを受信したら (line 13)，ク
リティカルリージョンに入る (line 14)．このリージョンではコ
ミットクエリが一つも実行されていないことを保証する．Libera
が最初の参照クエリを全てのレプリカへ送信したら (line 16)，

Libera は全てのレプリカから応答を受信する (line 17)．クリAlgorithm 2 Update transaction
1: receive a query from a client
2: if the query is a write query then3:
send the query to the leader;4:
receive a response from the leader;5:
if the response is an abort then6:
send a rollback query to all replicas;
7:
receive a response from the all replicas;
8:
else
9:
send the query to all the followers;
10:
receive a response from all the followers;
11:
end if12:
send the response to the client
13: else if the query is the first read query then14:
enter critical region;15:/* there is no commit operation executed */16:
send the operation to all replicas;
17:
receive responses from all the replicas;
18:
leave critical region;
19:
send the response to the client
20: else if the query is a read query (excluded the first read query) then21:
send the query to the leader
22:
receive a response from the leader;23:
send the response to the client;
24: else if the query is a commit operation then25:
enter critical region;
26:/* there is no first read operation executed */27:
send the query to the leader;28:
receive a response from the leader;29:
if the response is an abort then30:
send a rollback query to all replicas;
31:
receive a response from the all replicas;
32:
else
33:
send the query to all the followers;
34:
receive responses from all the followers;
35:
end if36:
leave critical region;37:
send the response to the client
38: end if

SI を実現する他のミドルウェアの性能を比較したい．そこで，SGSI [7] と Distributed Versioning (DV) [3] の二つの候補がある．Libera と違って SGSI は非標準なインターフェースである多くの機能を必要とする．具体的には，readset の抽
出，writeset の挿入，高信頼マルチキャストプロトコルの実
装，certifier の実装，である．特に，高信頼化マルチキャスト
プロトコルは JGroups [13] や Horus [14]，Ensemble [15] など
多数の研究成果が存在するが，どれも複雑で高価である．特に

SGSI については certifier 専用の CertDB と呼ぶ DBMS（彼らの研究では SQLite.NET）が必要であり本末転倒である．対して DV は SQL インターフェースを前提としており certifierのような高価な機能を必要としない．従って，DV を選択し，

1-Copy-SR を SSI を提供するレプリカを使って実現するように改造した（DV-SSI と呼ぶ）．

5. 2 TPC-W ベンチマーク

TPC-W ベンチマーク [12] はオンライン書店にアクセスするお客をモデル化している．データベースは item と country,

author, customer, orders, order line, cc xacts, address を管理している．14 種類のアクセスパターンがあり，そのうち 6個は参照のみのトランザクションから構成されている．このベンチマークはブラウジング，ショッピング，オーダリングの三
つの異なる負荷を試験できる．テーブル 1 は三つの負荷におけるアクセスパターンの比率を表している．

ティカルリージョンを抜ける (line 18)．Libera は一つの応答

表1

Three workloads in TPC-W benchmark

をクライアントへ返す (line 19)．

read-only update

もし，Libera が参照クエリ（最初の参照クエリは除く）を受信したら (line 1)，Libera はリーダに送信し (line 21)，応答をリーダから受信する (line 22).
もし，Libera がコミットクエリを受信したら (line 1)，クリ
ティカルリージョンに入る (line 25)．このリージョンでは最初の参照クエリが実行されていないことを保証する．Libera はリーダにコミットクエリを送信すると (line 27)，リーダは応答を受信する (line 28)．もし，応答がアボートならば (line 29)，

Libera は全てのレプリカへロールバッククエリを送り (line 30)，
応答を受けとる (line 31)．もし，応答が成功ならば，Libera は全てのフォロワへクエリを送信する (line 33)．そして，Libera
は全てのフォロワから応答を受けとる (line 34)．もし，Libera
がアボート応答を受けとったら，全てのトランザクションを
ロールバックする．Libera はクリティカルリージョンを抜ける(line 36)．Libera はクライアントへ応答を返す (line 37).
1.00.7

5. 評

価

Libera の有効性を示すために，プロトタイプを実装し TPCW ベンチマーク [12] を使った性能評価を行った；スループッ
ト、応答時間、拡張性について Libera と 既存技術を使って1-Copy-SSI 提供するミドルウェアとを比較した．
5. 1 性能比較のために基準としたミドルウェア
Libera の有効性を示すためには，Libera の性能と 1-Copy-

browsing mix

95%

5%

shopping mix

80%

20%

ordering mix

50%

50%

ブラウジング負荷は参照が多く，オーダリング負荷は更新が多いという特徴がある．評価基準は スループット（WIPS: web

interactions per second) と応答時間 (ms) である．
5. 3 実 験 環 境

測定には最大で 8 ノードを使い，一つはリーダ，残りがフォロワである．さらに，ミドルウェアを動作させる一つのノード，負荷を発生させるノードを四つ使った．全てのノードは同じスペックである (一つの 3.1 GHz Xeon E3-1220 CPU,

16 GBytes RAM, and one 250 GB SCSI HDD)．全てのノードは一つのギガビットイーサスイッチで相互接続されている．ノードで動作させる DBMS として，バージョン 9.4.9の PostgreSQL を 使った ．設 定 ファイ ル を 変 更 し た 箇 所 はdefault transaction isolation を SERIALIZABLE （注 1） とし
た．TPC-W ベンチマークに与えたパラメータは 100 万 itemと 288 万 customers であり，これは約 6 GBytes の大きさを
占める．

5. 4 結果

本節では，TPC-W ベンチマークを使った場合における Lib-era と DV-SSI のスループットと応答時間を比較した．
（注 1）：PostgreSQL では SERIALIZABLE を指定すると，serializable snap-

shot isolation で動作する．

400

Response time [S]500
Throughput [WIPS]

2

Libera (4 nodes)
Libera (2 nodes)
Libera (1 node)
DV-SSI (4 nodes)
DV-SSI (2 nodes)
DV-SSI (1 node)

300
200

8

Libera (4 nodes)
Libera (2 nodes)
Libera (1 node)
DV-SSI (4 nodes)
DV-SSI (2 nodes)
DV-SSI (1 node)

1.5

7
Normalized throughput

600

1

0.5

100
0
400
600
800
1000
Load [EBs]Throughput underbrowsing mix

Response time [S]

400

400
600
800
1000
[EBs]browsing mix
Response timeLoad
under

図4

200

3
2

300
200

2

0.5

6

8

10

600

800

1000

1000

1200

Libera (b-1 node)
Libera (o-1 node)
PGSQL (b-1 node)
PGSQL (o-1 node)

250

1

4

Load [EBs]
図 5 Scaleout

300

Libera (4 nodes)
Libera (2 nodes)
Libera (1 node)
DV-SSI (4 nodes)
DV-SSI (2 nodes)
DV-SSI (1 node)

1.5

0

100

200
150
100
50

0
0

200

400
600
800
1000
Load [EBs]Throughput underordering mix

2

400
600
800
1000
[EBs]ordering mix
Response timeLoad
under

図7
400

Libera (b-1 node)
Libera (o-1 node)
PGSQL (b-1 node)
PGSQL (o-1 node)

1

0.5

200

300

0

250
200
150
100

200

400

Load with[EBs] 1 node
図 8 Throughput
2

Libera (b-2 nodes)
Libera (o-2 nodes)
PGSQLx2 (b-1 nodex2)
PGSQLx2 (o-1 nodex2)

350
Throughput [WIPS]

1.5

0
0

Response time [WIPS]

0

Throughput [WIPS]

4

0
0

2

Libera (4 nodes)
Libera (2 nodes)
Libera (1 node)
DV-SSI (4 nodes)
DV-SSI (2 nodes)
DV-SSI (1 node)500
Throughput [WIPS]

200

Throughput [WIPS]

0

600

図6

5

1

0

図3

6

Libera (b-2 nodes)
Libera (o-2 nodes)
PGSQLx2 (b-1 nodex2)
PGSQLx2 (o-1 nodex2)

1.5

1

0.5

50
0

0
0

200

400

600

800

Load [EBs]
図 9 Response timewith 1 node

1000

図 10

0
0

200

400

600

800

1000

1200

0

[EBs] ordering mix
Response timeLoad
under

200

図 11

400

600

800

Load [EBs]
Scale
out

5. 4. 1 ブラウジング負荷におけるスループットの最大レスポンス時間になる負荷に変化が現れる．つまり，1,

最初の評価は，ブラウジング負荷における Libera と DV-SSI

2, 4 レプリカでそれぞれ 300 EBs, 500 EBs, 900 EBs となる．

のスループットである．レプリカ数は 1, 2, 4 と変化させた．図他方で，DV-SSI はレプリカ数を変えてもそれほど変化はない．

3 はブラウジング負荷のスループットである．x 軸は負荷（EB5. 4. 3 ブラウジング負荷の拡張性数）であり y 軸はレプリカ数を変化させた時のスループットで第三の評価は，Libera のスループットの拡張性である．第ある．低負荷 (約 100 EBs) の場合，レプリカ数が変わったと

5. 4. 1 と 第 5. 4. 2 ではレプリカ数を増やすとより高いスルー

しても Libera も DV-SSI も約 50 WIPS である．従って，低プットが実現できることが分かった．そこで，レプリカ数を 8

負荷の場合には Libera も DV-SSI もスループットに変化はほまで増やして最大スループットを評価した．図 5 はブラウジン

とんどない．高負荷の場合，Libera の最大スループットに変化

グ負荷において，x 軸はレプリカ数，y 軸は正規化したスルーがあった．1 レプリカ，2 レプリカ，4 レプリカの時にそれぞプットを示す．驚いたことに，スループットは 8 ノードまで線

れ 81.8 WIPS, 164 WIPS, 315 WIPS であった．レプリカ数

形に増加する．8 レプリカのシステムは 621.3 WIPS となりシを増やせば増やすほどスループットは線形に増加した．他方でングルレプリカシステムの 7.60 倍である．SGSI が 8 レプリ

は，DV-SSI はレプリカ数を増やしても約 74 WIPS でありほカで 4 倍しか達成できてないこと，また，理想的な 8 倍に近とんど変わらない．

いこと，などから考えると，Libera はオーバヘッドが少なく高5. 4. 2 ブラウジング負荷における応答時間
第二の評価は，ブラウジング負荷における Libera と DV-SSI

性能化に長けていると言える．

5. 4. 4 オーダリング負荷時のスループットの応答時間である．レプリカ数は 1, 2, 4 と変化させた．図 4

第四の評価は，オーダリング負荷における Libera と DV-SSI

はブラウジング負荷時の応答時間である．x 軸は負荷（EB 数）のスループットである．レプリカ数は 1, 2, 4 と変化させた．

であり y 軸はレプリカ数を変化させた時の応答時間である．

図 6 はオーダリング負荷のスループットである．x 軸は負荷

低負荷 (約 100 EBs) の場合，レプリカ数が変わったとしても（EB 数）であり y 軸はレプリカ数を変化させた時のスループッ

Libera は約 0.06 s である．他方，DV-SSI の応答時間はレプトである．ブラウジング負荷と同様に，低い負荷（約 100 EBs）

リカ数が変わったとしても 0.20 s である．負荷が低い場合ででは Libera も DV-SSI も約 50 WIPS である．負荷を高くすはわずかに Libera が優位である．負荷が大きくなると Libera

ると，Libera では奇妙なことが起きる．レプリカの数を増やすと，スループットが下がる．例えば，500 EBs の時は，Lib-

era のスループットはレプリカ数 1, 2, 4 において 209 WIPS,

6. お わ り に

189 WIPS, 125 WIPS である．更新の負荷が高い場合には

1-Copy-SR を SQL 転送制御で提供する 1CS ルールを提案

Libera は無視できないオーバヘッドが生じることが分かった．

した．また，1CS を使って 1-Copy-SR を提供する Libera と呼このオーバヘッドの詳細は 5. 4. 6 節で議論する．DV-SSI はどぶミドルウェアも提案した．Libera は SSI を使って 1-Copy-SRのような場合でもスループットは低い．

を実現する最初のミドルウェアである．Libera は (1) DBMS

5. 4. 5 オーダリング負荷における応答時間とクライアントに透過であること，(2) 無改造で市中技術の第 5 の評価は，オーダリング負荷における Libera と DV-SSI

ハードウェアとソフトウェアを使っていること，(3) readsetsの応答時間である．レプリカ数は 1, 2, 4 と変化させた．図 7と writesets を処理したり，group communication を実装したはオーダリング負荷時の応答時間である．x 軸は負荷（EB 数）

り，専用の解析機を実装したり，という特殊でコストの高いこであり y 軸はレプリカ数を変化させた時の応答時間である．

とを必要としないピュアミドルウェアである．我々は無改造のLibera はスループットと同様，反対の順序となった．つまり，PostgreSQL を使い Libera を実装した．規模は C 言語で 3000

最も小さい応答時間は 1 レプリカの時であり次に 2 レプリカ

ライン程度である．TPC-W ベンチマークを使って性能評価をの時である．この原因の解析は 5. 4. 6 節で議論する．DV-SSI

行った．Libera は参照クエリが多い環境で従来技術よりも高い

は Libera の 4 レプリカのケースよりもさらに悪い．

スループットを実現できた．驚くことに Libera はほとんどロ5. 4. 6 Overhead

スすることなく線形にスループットを向上できる．8 レプリカ

第六の評価は Libera のオーバヘッドの解析である．一般的のシステムで単一レプリカのパフォーマンスの 7.60 倍である．

にはピュアミドルウェアはデータベースエンジンを改造しない

Libera はシンプルであるばかりでなく，参照クエリが多い場合ことから非効率なレプリケーションを引き起こし大きなオーバ

はレプリカ数が多いシステムを構築可能な現実的なシステムでヘッドを発生させてしまう可能性がある．Libera では次の二つある．

がオーバヘッドを発生させる原因となりうる．

(1) Same Snapshot Creation protocol(2) Leader/Follower protocol
最初に，一つの PostgreSQL ノードを持った Libera と Lib-era を使わない一つの PostgreSQL を比較することによってオーバヘッド (1) を解析した．図 8 は一つの PostgreSQL ノー
ドを持った Libera のスループットと Libera を使わない Post-

greSQL のスループットを示す．オーダリング負荷では，Liberaのスループット曲線は PostgreSQL の曲線のすぐ下に位置す
る．その結果，Libera によるスループット低下率は約 1.5% である．ブラウジング負荷では，Libera のスループット曲線はPostgreSQL の曲線にほとんどオーバラップする．図 9 は一つの PostgreSQL ノードを持った Libera の応答時間と Liberaを使わない PostgreSQL の応答時間を示す．スループットのケースと同じように Libera のカーブと Libera を使わない

PostgreSQL のカーブはほぼ一致する．従って，オーバヘッド(1) は無視できる．
次に，二つの PostgreSQL ノードを持った Libera のスルー
プットと Libera を使わない PostgreSQL のスループットを2 倍した値（PGSQLx2 と表記する）とを比較してオーバヘッ
ド (2) を議論する．図 10 に二つの PostgreSQL ノードを持った Libera のスループットと PGSQLx2 を示す．ブラウジング
負荷の場合，両カーブはほとんど一致する．従って，ブラウジ
ング負荷の場合，Leader/Follower protocol のオーバヘッドは
ほとんど生じないと言える．他方でオーダリング負荷の場合を考える．低負荷の場合は Libera と PGSQLx2 は非常に近い
が，高負荷の場合は Libera と PGSQLx2 は離れていて Liberaの方が高い．以上より，Libera は更新が多く高負荷の場合にLeader/Follower protocol で無視できないオーバヘッドが生じることが分かった．

文

献[1] P. A. Bernstein, V. Hadzilacos and N. Goodman “Concurrency Control and Recovery in Database Systems”,
Addison-Wesley Publishing Company, 1987.
[2] H. Berenson, P. Bernstein, J. Gray J. Melton, E.O’Neil andP. O’Neil “A Critique of ANSI SQL Isolation Levels” ACM
SIGMOD, 1995.
[3] C. Amza, A. L. Cox and W. Zwaenepoel “Distributed
Versioning: Consistent Replication for Scaling Back-end
Databases of Dynamic Content Web Sites”[4] J. Gray, P. Helland, P. O’Neil and D.Shasha “The Dangers
of Replication and a Solution” ACM SIGMOD, 1996.
[5] Y. Lin, B. Kemme, M. Patiño-Martı́nez and R. JiménezPeris “Middleware based Data Replication providing Snapshot Isolation” ACM SIGMOD, 2005.
[6] T. Mishima and H. Nakamura “Pangea: An Eager Database
Replication Middleware guaranteeing Snapshot Isolation
without Modification of Database Servers” PVLDB, 2009.
[7] M. A. Bornea, O. Hodson, S. Elnikety and A. Fekete“One-Copy Serializability with Snapshot Isolation under the
Hood” ICDE. 2011.
[8] M. J. Cahill, U. Röhm and A. D. Fekete “Serializable Isolation for Snapshot Databases” ACM SIGMOD, 2008.
[9] “blind write, http://en.wikipedia.org/wiki/Blind write”[10] H. Jung, H. Han, A. Fekete and U. Röhm “Serializable Snapshot Isolation for Replicated Databases in HighUpdate Scenarios” VLDB, 2011.
[11] A. Fekete, D. Liarokapis, E. O’Neil, P. O’Neil and D.Shasha“Making Snapshot Isolation Serializable”[12] “Transaction Processing Performance Council, TPC-W”[13] http://jgroups.org/manual/index.html[14] http://www.cs.cornell.edu/Info/Projects/HORUS/Overview.html[15] http://www.cs.technion.ac.il/Labs/csl/projects/Ensemble