DEIM Forum 2017 P1-2

並行実行制御手法 TicToc の調査中村 泰大†

川島 英之††

建部修見††† 筑波大学 情報学群情報科学類 〒 305–8571 茨城県つくば市天王台 1 丁目 1–1†† 筑波大学 計算科学研究センター 〒 305–8571 茨城県つくば市天王台 1 丁目 1–1
E-mail: †nakamura@hpcs.cs.tsukuba.ac.jp, ††{kawasima,tatebe}@cs.tsukuba.ac.jp
あらまし SIGMOD’16 にて、並行実行制御手法 TicToc が提案された。それが報告と一貫した性能を示すのか調査を行った。3 つのマイクロベンチマークを作成し、それぞれ測定したところ、いずれもスケールアップを観察した。この

時最大で、280 万 transaction/sec を達成することを観察した。また、Intel Xeon Phi Knights Landing 上で 256 スレッドまでスレッド数を変化させて測定した。この環境でもスケールアップが観察され、最大で 4000 万 transaction/secを達成することを観察した。
キーワード トランザクション、並行実行制御、データベースシステム

1. 序論

データベースシステムに複数のトランザクションが到着した

1 つの 64 bit word に格納して保管する。これを Timestampword(TS word) と呼ぶ。Timestamp word の内訳は以下に示すとおりである。

とき、それらが及ぼす作用の結果がデータベースに非一貫性をもたらさぬよう、データベースシステムは並行実行制御を行う。

TS word[63]: Lock bit (1 bit).
TS word[62:48]: delta = rts - wts (15 bits).

SIGMOD’16 では、2013 年に提案された Silo [1] に勝る並行TS word[47:0]: wts (48 bits).

実行制御手法が複数提案 [2], [3] された。それらの手法の中にTicToc [3] がある。TicToc は OCC [4] の弱点であるタイムスタンプ生成コスト [5] を削減し、Silo を上回る性能を発揮することが報告されている。本論文では、TicToc を再実装し、それが報告と一貫した性能を発揮するのか調査を行った。
本報告の構成は以下の通りである。2 節では TicToc とその再実装について述べる。3 節では評価方法と結果を述べる。4節では評価を基に結論を述べる。

2. TicToc
OCC では、トランザクションのタイムスタンプを得るために共有メモリ上のカウンタを用い、それに対して排他制御やfetch-and-add オペレーションを発行していた。TicToc ではそのボトルネックをなくすために、トランザクションのタイムスタンプは全てワーカーが計算によって求める。

2. 1 データ構造
TicToc のタプルは Write Timestamp (wts) と Read Times-

2. 2 プロトコル
TicToc のプロトコルは OCC や Silo と同様に Read フェー
ズ、Validation フェーズ、Write フェーズの 3 つに分割される。
トランザクション処理の流れを Algorithm 1 に示す。はじめにRead フェーズを実行し操作の対象となるタプルをワーカーにコピーする。コピーしたタプルに対してオペレーションを実行する。オペレーションの結果が他のワーカーと整合性を保っているかを Validation フェーズで検証する。整合性を保っていることが確認されたのち、Write フェーズでデータの変更をデータベースに反映する。不整合が検知された場合は Read フェーズから再度実行する。

Algorithm 1 execute transaction
Retry point:
1: read phase()
2: do operation()tamp (rts) を持つ。これらはそれぞれ、そのタプルの値が書き

3: if validation phase() is failure then

込まれたタイムスタンプと最後に読まれたタイムスタンプであ4:abort()る。タプルが wts と rts を持つのは、タプルの値が有効な範囲

5:retry()を示すためである。あるタプル A を読み込んだ時に、タイムスタンプがそれぞれ wts = 3、rts = 6 だったとする。タプル Aを読み込んだトランザクションのタイムスタンプが 5 だと算出された場合、タプル A の値はタイムスタンプ 3 から 6 の間で有効であるから、タイムスタンプが 5 の時もタプル A の値は有効だと判断できる。

TicToc は正しく有効な範囲を取得するために、wts と rts をアトミックに読み込む必要がある。そこで TicToc はそれらを

6: end if
7: write phase()

2. 2. 1 Read フェーズ
Read フェーズのアルゴリズムを Algorithm 2 に示す。TicToc はタイムスタンプと値の正しい組を得る必要がある。そこ
で、TicToc はそれらをアトミックに読み込むために TS wordを 2 回読み込む (Algorithm 2 - line 2〜4)。そして TS word

に変更がなかった場合に、タイムスタンプと値の正しい組を取得できたとし、ワーカースレッドのローカル領域にタプルをコAlgorithm 3 Validation Phase ( [3] より引用)
Data: read set RS, write set W S

ピーする (Algorithm 2 - line 6〜7)。タプルがロックされてい1: for w in sorted(W S) do

る場合は、タプルへの操作が中途半端な状態であり、タイムス2:

タンプと値の正しい組を得られない可能性がある (Algorithm

3: end for2 - line 5)。従って、ロックが解除されるまで読み込みを繰り返す。

Data: read set entry r, tuple t
1: do
2:
3:
4:

4: commit ts ← 0

5: for e in W S ∪ RS do
6:

Algorithm 2 Read Phase ( [3] より引用)

v1 ← t.read ts word()read(r.read, t.data)v2 ← t.read ts word()

5: while v1 =| v2 or v1.lock bit == 1
6: r.wts ← v1.wts

7: r.rts ← v1.wts + v1.delta

7:
8:
9:
10:

if e in W S thencommit ts ← max(commit ts, e.tuple.rts + 1)

else

commit ts ← max(commit ts, e.wts)

end if

11: end for
12: for r in RS do
13:
14:

if r.rts < commit ts thenif w.wts =| r.tuple.wts or (r.tuple.rts <= commit ts andisLocked(r.tuple) and r.tuple not in W ) thenabort()

15:
16:

2. 2. 2 Validation フェーズ

17:

Validation フェーズのアルゴリズム及びタイムスタンプの算

18:

出を Algorithm 3 に示す。タイムスタンプの算出には、Read19:

フェーズでワーカーのローカル領域にコピーしたタプル（ローlock(w.tuple)else
r.tuple.rts ← max(commit ts, r.tuple.rts)

end ifend if

20: end forカルタプル）を用いる。タイムスタンプは、Read セットにあるローカルタプルの wts と Write セットにあるタプルの rts +Algorithm 4 Write Phase ( [3] より引用)

1 で最大のものとなる (Algorithm 3 - line 4〜11)。

Data: write set W S, commit timestamp commit ts

算出したタイムスタンプを元に、トランザクションが有効であるか、以下のように確認を行う (Algorithm 3 - line 12〜20)。算出したタイムスタンプが、Read セットにあるローカルタプルの rts 以下である場合 (Algorithm 3 - line 13)、wts から rts に間そのタプルは値が変わらないことが保証されているため不整合は起こらない。従って、ローカルタプルを確認するだけでよく、データベース上のタプルに再度アクセスする必要はない。タイムスタンプが rts を超えている場合、データベース上にあるタプルの wts とローカルタプルの wts が等しいか確認する (Algorithm 3 - line 14)。等しい場合、タプルの値はRead フェーズでコピーしてから変更されていないため不整合は発生していない。この時、コミットタイムスタンプまで値が変わらないことを保証するために、タプルの rts をタイムスタンプまで延長する (Algorithm 3 - line 17)。rts の延長にはcompare-and-swap 命令を用いる。wts が異なる場合、別のワーカースレッドがタプルを変更しているため、このトランザクションをアボートし、トランザクションを再実行する (Algorithm 3- line 15)。Write セットにあるタプルは、Validation フェーズの初めにロックを獲得するため、確認を行わなくて良い。

2. 2. 3 Write フェーズ
Write フェーズのアルゴリズムを Algorithm 4 に示す。Validation フェーズを通過し、不整合がないと判断されたトランザクションが Write フェーズを実行する。トランザクションはタプルの値を新しい値に、wts と rts を算出したコミットタイムスタンプに更新する。その後トランザクションは、タプルのロックを解放する。

1: for w in W S do
2:write(w.tuple.value, w.value)

3:w.tuple.wts ← w.tuple.rts ← commit ts

4:

unlock(w.tuple)

5: end for2. 3 再 実 装提案論文をもとに、C++を用いて TicToc の実装を行った。
また、比較対象としてナイーブな OCC の実装を行った。

3. 評

価

再実装した TicToc および OCC についてスレッド数を変化させながらスループットを測定した。ワークロード中の各トランザクションはオペレーションを 10 件含む。データベースの初期タプル数は 1 万件であり、オペレーションの対象となるタプルはランダムに選択される。
ワークロードは 3 種類用意した。一つは全て Read トランザクションであるワークロード（Read only）、一つは Read トランザクションと Write トランザクションが半数ずつあるワークロード（Even）、最後に全て Write トランザクションであるワークロード（Write）である。

3. 1 マルチコア環境
評価環境を表 1 に、評価結果を図 1 に示す。ワーカー数を 1スレッドから 24 スレッドまで変化させて、3 つのワークロードをそれぞれ実行した。トランザクション数は全体で 100 万件とした。図 1 から、TicToc はどのワークロードでも線形にスループットが向上していることがわかる。また、TicToc はどの74.5x10

ワークロードでも OCC に比べて良いスループットを示していることがわかる。TicToc がスケールアップするのは、TicToc

3.5x107

評価環境を表 2 に、評価結果を図 2 に示す。ワーカー数を1 スレッドから 256 スレッドまで変化させて、Read only ワー
クロードと Even ワークロードを実行した。トランザクション

Throughput [tps]では共有カウンタのボトルネックが排除されているためである。

3. 2 メニーコア環境

3x107
2.5x1072x107
1.5x107

数は、ワーカーごとに 200 万件とした。図 2 から、どちらの1x107ワークロードでもスケールアップしていることがわかる。Read

5x106

only では、65 スレッド、129 スレッド、および 193 スレッド時0に大きく性能が劣化している。これは、各コアで動くスレッド
図2ことが原因であると考えられる。
マルチコアの評価環境

050

100

150

200

250

300

Worker [threads]

数が均一でなくなることでロードインバランスが起こっている

表1

Read only
Even4x107

謝

メニーコア環境でのワークロードのスループット

辞プロセッサIntel(R) Xeon(R) CPU E5-2695 v2 @ 2.40GHz

コア

24

メモリ

64GB

インテンシブサイエンスのためのシステムソフトウェア」、JST

OS

CentOS release 6.8 (Final)

CREST「EBD:次世代の年ヨッタバイト処理に向けたエクス

本研究の一部は、JST CREST「ポストペタスケールデータトリームビッグデータの基盤技術」、JST CREST「広域撮像探査観測のビッグデータ分析による統計計算物理学」、科研費「#16K00150」による。
文

図1

マルチコア環境での各ワークロードのスループット

表2

メニーコアの評価環境

プロセッサIntel(R) Xeon Phi(TM) CPU 7210 @ 1.30GHz

コア

64 (256 スレッド)

メモリ

MCDRAM: 16 GB
DRAM: 96 GB

OS

4. 結

CentOS Linux release 7.2.1511 (Core)論

TicToc はマルチコア環境とメニーコア環境のどちらにおいてもスケールする結果が得られた。ピーク性能として 4000 万transaction/sec (tps) を達成できることが観察された。
原論文 [3] では永続化については具体的に検討されておらず、本論文でも永続化については考慮していない。トランザクショ
ン処理において、永続化は必要不可欠 [6] [7] である。今後はTicToc に永続化処理を施す手法を探求する。

献[1] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov,and Samuel Madden. Speedy transactions in multicore inmemory databases. In Proceedings of the Twenty-Fourth
ACM Symposium on Operating Systems Principles, SOSP’13, pp. 18–32, New York, NY, USA, 2013. ACM.
[2] Kangnyeon Kim, Tianzheng Wang, Ryan Johnson, and Ippokratis Pandis. Ermia: Fast memory-optimized databasesystem for heterogeneous workloads. In Proceedings of the2016 International Conference on Management of Data,
SIGMOD ’16, pp. 1675–1687, New York, NY, USA, 2016.
ACM.
[3] Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas
Devadas. Tictoc: Time traveling optimistic concurrency
control. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, pp. 1629–1642,
New York, NY, USA, 2016. ACM.
[4] H. T. Kung and John T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst.,
Vol. 6, No. 2, pp. 213–226, June 1981.
[5] Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. Staring into the abyss: Anevaluation of concurrency control with one thousand cores.
Proc. VLDB Endow., Vol. 8, No. 3, pp. 209–220, November
2014.
[6] C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh,
and Peter Schwarz. Aries: A transaction recovery method
supporting fine-granularity locking and partial rollbacks
using write-ahead logging. ACM Trans. Database Syst.,
Vol. 17, No. 1, pp. 94–162, March 1992.
[7] Jim Gray. The transaction concept: Virtues and limitations(invited paper). In Proceedings of the Seventh International
Conference on Very Large Data Bases - Volume 7, VLDB’81, pp. 144–154. VLDB Endowment, 1981.