トランザクション処理技術

2020年10月27日
慶應義塾大学環境情報学部
川島英之

Transaction Processing

Big Data

Can you access DB simultaneously?

研究目的
世界最速のトランザクション処理技術• トランザクション– Concurrency Control– Recovery

Consistency
Isolation
Durability• アプローチ– ビッグアプリとのco-design– ハードを活用するre-design• メニーコア、NVRAM

RecoveryAtomicity

ConcurrencyControl
ビッグデータアプリ
すばる望遠鏡：300GB/夜
苦痛を癒すべくCo-Design

データシステム
ハードを活かすべくRe-Design

先進的ハードウェア
不揮発メモリ・メニーコア

振込と引出最初10000，+1000, -1000,最後は10000?

Begin
Read(口座, x)
x := x + 1000

Begin
Read(口座, y)y := y - 1000
Write(口座, y)CommitWrite(口座, x)Commit

自分バイト先近代的並行性制御法
MethodYearConferenceFeatures
Optimistic
Multi-Version
Optimistic
Pessimistic

CICADA

2017

SIGMOD

MOCC

2016

VLDB

TicToc2016

SIGMOD

Optimistic

ERMIA

2016

SIGMOD

Multi-Version

Silo

2013

SOSP

Optimistic

SI

1995

SIGMOD

Multi-Version

2 Phase Lock1976

Comm. ACM

Pessimistic

2つの謎• 本当に速いのか？
• CC性能は理論（スケジューリング空間）だけでは決まらない。実装が重要（索引で性能激変）• 実験で異なるプラットフォームを利用？

• なぜ速いのか？
• 自分にとって有利な条件で実験してないか？
• 様々な手法があるが、何が性能を決めているのか？

網羅的に分析可能なプラットフォームCCBench
Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, Osamu Tatebe: An Analysis ofConcurrency Control Protocols for In-Memory Database with CCBench. PVLDB, 2020.

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Controland Recovery (The Morgan Kaufmann Series in Data Management Systems), Weikum, Vossen

本当に速いのか？(MOCC)

概ね consistentT. Wang and H. Kimura. Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads ona Thousand Cores. PVLDB, 10(2):49–60, 2016.

本当に速いのか？(Cicada)

理由：複数システムの利用 (DBx1000, Original)
Lim, M. Kaminsky, and D. G. Andersen. Cicada: Dependably fast multi-core in-memory transactions.
In SIGMOD Conf., pages 21-35, 2017.

なぜ速いのか？
224並列環境での分析

Cache(1) Cache-Line-Conflicts

Cache(2) Cache Replacement

1. Silo, TicToc, Cicadaのヘッダは64B. 64B x 10^5 < 38.5 MB. これを超えて性能劣化。
2. それ以下でも性能劣化？レコード数増加に伴うL1/L2ミスの増加。

Delay高競合時には並行性削減

1. Payloadが大きくなれば性能が落ちる筈
2. しかし上がっている？なぜ？
3. 理由は余計な競合が減るから。強制sleepで確かに性能向上。
4. Silo + NoWaitで性能大幅改善。
5. Read Phase Extension

Version Lifetime Management

1. MVCCはversionにより性能向上
2. Version costが負担である点は周知の事実
3. Long transaction が 1つでも入ってきたら性能律速。

TPC-C, Indexの影響• まとめ• 目標：世界最速のトランザクション技法を開拓• 成果：CCBenchで近代的並行性制御法を分析• 予定ConcurrencyControlRecovery• 最速の並行性制御法を実現• Silo++• 新規手法• 永続化法を導入• 並列書き込み（例：P-WAL）• Epoch方式
Yasuhiro Nakamura, Hideyuki Kawashima, Osamu Tatebe: Integration of TicToc Concurrency Control Protocol with Parallel
Write Ahead Logging Protocol. Int. J. Netw. Comput. 9(2): 339-353 (2019)

成果一覧
1. Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, Osamu Tatebe: AnAnalysis of Concurrency Control Protocols for In-Memory Databases withCCBench. Proc. VLDB Endowment 13(13): 3531-3544 (2020), 査読有,
2. Jun Nemoto, Hideyuki Kawashima, Motomichi Toyama: Exploiting SIMD
Instructions in Partial-Evaluation-Based Query Compiler. Proc. The 1st Workshop
on Distributed Infrastructure, Systems, Programming and AI (DISPA), 査読有
3. Kohei Hiraga, Osamu Tatebe, Hideyuki Kawashima: Scalable Distributed
Metadata Server Based on Nonblocking Transactions. J. Univers. Comput. Sci.
26(1): 89-106 (2020)
4. Yasuhiro Nakamura, Hideyuki Kawashima, Osamu Tatebe: Integrationof TicToc Concurrency Control Protocol with Parallel Write Ahead Logging
Protocol. International Journal on Network Computing 9(2): 339-353 (2019), 査読有
5. Harunobu Daikoku, Hideyuki Kawashima, Osamu Tatebe: Skew-Aware
Collective Communication for MapReduce Shuffling. IEICE Transactions onInformation Systems 102-D(12): 2389-2399 (2019), 査読有