近代的トランザクション処理技法
Feb. 27, 2022
Hideyuki Kawashima

概要
• 内容
– 近代的トランザクションの基礎であるSiloを解説– 話者の授業「大規模データシステム論」（対象：1-4年）の一部• なぜSilo？
– 依然として強力であり，近代的技法の多くが依拠• 話さないこと– 分散，適応，MVCC，チェックポインティング，線形化可能性• 想定聴講者– 授業で2PL，recoveryを聞いたことがある方

Agenda• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions

Transaction Processing System =Concurrency Control + Recovery

Concurrency
Control
Recovery
Database
Applications: bank, credit card, distributed file system (spotify), blockchain…

Why transaction?
ATM: Your DB is 30,000 first.
Read(DB, x);x := x + 10,000;

Read(DB, y);y := y – 10,000;
Write(DB, y);You
Write(DB, x);Company

Final value:
40,000?

Lost UpdateT2 write has gone…

r1 𝑥𝑥 … 𝑤𝑤2 𝑥𝑥 … 𝑤𝑤𝑤 𝑥𝑥 … 𝑐𝑐𝑐
T1

T2

Read(x)Read (x)Write(x)Write(x)CommitIsolation Levels & Anomalies

Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, Patrick E.
O'Neil: A Critique of ANSI SQL Isolation Levels. SIGMOD Conference 1995: 1-10

Serializability--Equivalent to Serial Exec?-T2

T1

T2

T1

R(a)

R(a)

R(a)

R(a)

W(a)

W(a)

W(a)

W(a)

R(b)

R(b)

R(b)

R(b)

W(b)

W(b)

W(b)

W(b)

T2

T1

R(a)

R(a)

W(a)

W(a)

R(b)

R(b)

W(b)

W(b)

Quiz
How many serial orders?
• Number oftransactions
–2
–3
–4
–5
–N

A
B

C

B

C

C

B

A

C

C

A

A

B

B

A

Serializable schedules
T1

T2

T1

R(a)

R(a)

R(a)

R(a)

W(a)

W(a)

W(a)

W(a)

R(b)

R(b)

R(b)

R(a)

W(b)

W(b)

W(b)

W(a)

CommitCommitCommit

R(b)

W(a)

W(b)

W(b)

R(b)

CommitCommit

W(b)

T2

T1

T2

R(a)
R(b)

CommitT1 operations →T2 operations
T2 operations →T1 operations

If not serializable…
Reading Uncommitted Data
T1

T2

T1

R(a)

R(a)

R(a)

a = a – 100;a = a * 1.06;

W(a)

W(a)

W(a)

R(a)

R(b)

R(b)

W(a)

b = b + 100;b = b * 1.06;

R(b)

W(b)

W(b)

W(b)

CommitCommitCommitT1: Transfter $100 from A to B
T2: Increment A & B by 6 %Ideal:
A: 200->100->106
B: 200->300->318

Real:
A: 200->100->106
B: 200->212->312

T2

R(b)
W(b)
CommitB lossT1 should
access b first.

Serializable(Conflict Serializable (Final State, View))
𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;Transaction ID（1）No!

Data ID（A)

2 𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 𝑎𝑎 TX： 𝑟𝑟𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑖𝑖 𝑌𝑌 ;WW to the same data item: 𝑤𝑤𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑗𝑗 𝑋𝑋 ;RW to the same data item: 𝑟𝑟𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑗𝑗 𝑋𝑋 ;WR to the same data item: 𝑤𝑤𝑗𝑗 𝑋𝑋 ; 𝑟𝑟𝑖𝑖 𝑋𝑋 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;

Quiz: Serializable?
• Quiz-1
𝑟𝑟1 𝑥𝑥 ; 𝑟𝑟2 𝑥𝑥 ; 𝑟𝑟1 𝑧𝑧 ; 𝑤𝑤1 𝑥𝑥 ; 𝑤𝑤2 𝑦𝑦 ; 𝑟𝑟3 𝑧𝑧 ; 𝑤𝑤3 𝑦𝑦 ; 𝑤𝑤3 𝑧𝑧 ;• Quiz-2

𝑟𝑟1 𝑥𝑥 ; 𝑟𝑟3 𝑤𝑤 ; 𝑟𝑟2 𝑦𝑦 ; 𝑤𝑤1 𝑦𝑦 ; 𝑤𝑤1 𝑥𝑥 ; 𝑤𝑤2 𝑥𝑥 ; 𝑤𝑤2 𝑧𝑧 ; 𝑤𝑤3 𝑥𝑥 ;• Quiz-3

𝑟𝑟1 𝑥𝑥 ; 𝑟𝑟2 𝑥𝑥 ; 𝑤𝑤2 𝑦𝑦 ; 𝑤𝑤1 𝑥𝑥 ;1, 3: Serializable

Concurrency Control Protocols• Pessimistic– Conflict…(;_:)– Acquire lock→DB
access→Release lock

• Optimistic– No conflict (@^^)/~~~– Read data→Validate→Acquire
lock→DB access→Release lock

• Multi-version– Using multiple versions.

Strict 2 Phase Locking (S2PL)• 2 rules– Acquire locks before accessing DB• Read-read is not blocked (rigt table)– Release all locks at the end• Growing phase & shrinking phase
Serialization point#Locks

Time

rl wl
rl

Y

N

wl N N

Concurrency Control Protocols• Pessimistic– Conflict…(;_:)– Acquire lock→DB
access→Release lock

• Optimistic– No conflict (@^^)/~~~– Read data→Validate→Acquire
lock→DB access→Release lock

• Multi-version– Using multiple versions.

Kung-Robinson Model

3 phases: read, validate, write• READ (no read lock!)– Copy from DB to thread– Update local data

• VALIDATE

WorkerThreadDB– Check conflicts• WRITE– If no conflicts, write backto DB

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM
Trans. Database Syst. 6(2): 213-226 (1981)

Read

Validate

Write
Time

Validation Case 1

Ta completes its write phase before Tb starts its read phase
Tb ReadTa Read

Validate

Validate

Write

Write

Validation Case 2

The write set of Ta does not intersect the read set of Tb, and Ta completes its
write phase before Tb starts its write phase.
Tb ReadTa Read

Validate

Write

Validate

Write

TXstart ← TX global
Acquire GiantLock
TXend ← TXglobal
valid ← true
For t from (TX start + 1) to (TX end )if (writeset of t intersects my readset)
valid ← false
if (valid = true)
writephase
TXglobal ← TX global + 1
TX mine ← TXglobal

Release GiantLock

READ

VALIDATEWRITE

TXstart ← TX global Who is finished when I start?

READ

VALIDATE
Acquire GiantLock My turn!
WRITE
TXend ← TXglobal This is the end of checking scope
valid ← true I wish I win…..!
For t from (TX start + 1) to (TX end ) Scope, case 1 is out of scope
if (writeset of t intersects my readset) Check the case 2
valid ← false Sigh…
if (valid = true) Yeah!
writephase Time to say “write”
TXglobal ← TX global + 1 Increment succeeded TX, which is me!

TX mine ← TXglobal This is my ID, will be checked later by another TX

Release GiantLock Bye!

An Example
1

Start

Acquire Lock

Release Lock2
3

TXend ← 6

TXstart ← 3

Read Phase

Validation Phase

4

W

Check Case 2
(4～6)

5
6
7

TXmine ← TXglobal ← 7Timeline

1．Only 1 TX can enter Validation phase (Critical Section)
2. Read phases can be conducted by multiple TXs.
３. “Serial Validation” (Section 4) in K&R paper is a referenceAgenda• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions

Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden: Speedytransactions in multicore in-memory databases. SOSP 2013: 18-32

Lock

Validate

Write
Production Example: Sho Nakazono et al., LineairDB.
https://lineairdb.github.io/LineairDB/html/index.html

Silo Concurrency Control Protocol: 3 phases
Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock)for record, new-value in sorted(W)lock(record);// Phase 2 (validate)
for record, read-tid in R
if record.tid ≠ read-tid or record.locked
abort();
commit-tid ← generate-tid(R, W);// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
unlock(record);

Silo Concurrency Control Protocol
Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;Quiz: serializable?

T1: readset

T2: readset

T1: writeset

Header

Key

Value

A

10

B

20

T2: writeset

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T2: readset

T1: writeset

A:10:ptr

Header

Key

Value

A

10

B

20

T2: writeset

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T2: readset

T1: writeset

B:20:ptr

A:10:ptr

Header

Key

Value

A

10

B

20

T2: writeset

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T1: writeset

T2: readset

A:10:ptr

B:5:ptr

B:20:ptr

Header

Key

Value

A

10

B

20

T2: writeset

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T1: writeset

T2: readset

T2: writeset

A:10:ptr

B:5:ptr

B:20:ptr

A:-1:ptr

ヘッダ

Key

Value

A

10

B

20

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;May run concurrently

T1: readset

T1: writeset

T2: readset

T2: writeset

A:10:ptr

B:5:ptr

B:20:ptr

A:-1:ptr

ヘッダ

Key

Value

A

10

B

20

Silo Concurrency Control Protocol

3 Phases

Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);

Silo commit protocolの例

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐵𝐵!= 𝐵𝐵’

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ;T1: readset

T1: writeset

T2: readset

T2: writeset

A:10:ptr

B:5:ptr

B:20:ptr

A:-1:ptr

ヘッダ

Key

Value

A

10

B

20

Silo commit protocolの例

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐵𝐵!= 𝐵𝐵’

T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝐿𝐿2 𝐴𝐴 ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 {𝐵𝐵};𝐴𝐴 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 {𝐵𝐵};𝐵𝐵 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉1 {𝐴𝐴};……T1 ok……T1 okSilo Concurrency Control Protocol

Why sort?

Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);

Deadlock
alice

bob

x, y

y, x

𝑤𝑤𝑤𝑤𝑎𝑎 𝑥𝑥 ; 𝑤𝑤𝑤𝑤𝑏𝑏 𝑦𝑦 ; 𝑤𝑤𝑤𝑤𝑎𝑎 𝑦𝑦 ; 𝑤𝑤𝑤𝑤𝑏𝑏 𝑥𝑥 ;

Deadlock Detection• Wait graph– Create a node N(Ti) for Ti– When Ti waits for Tj, N(Ti)→N(Tj)– If cycled, deadlock…

1

2

3

T1 X(C)
T2
T3

4

5

6

X(A)
X(B)

T2(B)

T1(C)

X(C)
X(A)

X(B)

T3(A)

Deadlock avoidance• Conservative S2PL
– If you fail to acquire a lock, abort & retry• Sort access order before accessing DB[MOCC]– 𝐴𝐴 → 𝐵𝐵 → 𝐶𝐶
[MOCC] Tianzheng Wang, Hideaki Kimura: Mostly-Optimistic Concurrency Control forHighly Contended Dynamic Workloads on a Thousand Cores. PVLDB 10(2): 49-60(2016)

Silo Concurrency Control Protocol

Why?

Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐵𝐵!= 𝐵𝐵’

T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝐿𝐿2 𝐴𝐴 ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 {𝐵𝐵};𝐵𝐵 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 {𝐵𝐵};𝐴𝐴 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉1 {𝐴𝐴};……T1 ok……T1 okConflict (RW, WR, WW)
𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;Transaction ID（1）No
SwitchData ID（A)

2 𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 𝑎𝑎 TX： 𝑟𝑟𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑖𝑖 𝑌𝑌 ;WW to the same data item: 𝑤𝑤𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑗𝑗 𝑋𝑋 ;RW to the same data item: 𝑟𝑟𝑖𝑖 𝑋𝑋 ; 𝑤𝑤𝑗𝑗 𝑋𝑋 ;WR to the same data item: 𝑤𝑤𝑗𝑗 𝑋𝑋 ; 𝑟𝑟𝑖𝑖 𝑋𝑋 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟2 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤1 𝐴𝐴 ; 𝑟𝑟1 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑟𝑟2 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐵𝐵 ;

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T1: writeset

T2: readset

T2: writeset

A:10:80

B:5:90

B:20:90

A:-1:80

TID

Lock

Key

Value

80

1

A

10

91

0

B

5

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵

T2：I read B. I found B was concurrently updated by T1.
T2：Oh, I found I was conflicted with T1 on B…
T2：T1 updated B before my access. Then, the schedule should be T1->T2.
Thus, I need to read the result of T1.
T2：But I read result of T0…This is inconsistent. Abort sayonara.
Transaction requires serializablity. T1 → T2 or T2 → T1

Silo Concurrency Control Protocol

Why?

Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);

Silo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐵𝐵!= 𝐵𝐵’

T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝐿𝐿2 𝐴𝐴 ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 𝐵𝐵 ;T1 ok

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑊𝑊1 𝐵𝐵′ ; 𝑈𝑈1 𝐵𝐵’ ; 𝑉𝑉2 {𝐵𝐵};𝐵𝐵 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 {𝐵𝐵};𝐴𝐴 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉1 {𝐴𝐴};……T1 ok……T1 okSilo commit protocol

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤1 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑐𝑐1 ; 𝑐𝑐2 ;T1: readset

T1: writeset

T2: readset

T2: writeset

A:10:80

B:5:90

B:20:90

A:-1:80

rl wl

TID

Lock

Key

Value

80

0

A

10

rl

90

1

B

20

wl N N

𝑐𝑐1 ; 𝑐𝑐2 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 {𝐴𝐴}; 𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 {𝐵𝐵};Y

N

T2：I read B, B is locked by another one.
T2：As you know, if an item is write-locked, then we cannot obtain read lock…
T2：I believed that I succeeded to acquire read lock, but it was just my dream…
T2：Since I failed to acquire a read lock, I abort. Sayonara!

Silo Concurrency Control Protocol

Done

Data: read set R, write set W// Phase 0 (read and write)R ← value and pointer of read(); W ← pointer of write();// Phase 1 (lock) On “commit”, it starts
for record, new-value in sorted(W)lock(record);
Lock records (DB)．Sorting is for deadlock avoidance.
// Phase 2 (validate)
for record, read-tid in R Record-TID and RS-TID are different? abort．
if record.tid ≠ read-tid or record.locked
Record is locked, abort．
abort();
commit-tid ← generate-tid(R, W); Generage new TID.
// Phase 3 (write)
for record, new-value in W
write(record, new-value, commit-tid);
Update TID, write data, unlock
unlock(record);Quiz• Can a CC prevent following?
– S2PL– SiloNon-Serializable Schedule

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐1 𝑐𝑐2 ;Answer𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐1 𝑐𝑐2 ;

𝑙𝑙𝑟𝑟1 𝐴𝐴 𝑙𝑙𝑙𝑙1 𝐵𝐵 𝑙𝑙𝑟𝑟2 𝐵𝐵 𝑟𝑟1 𝐴𝐴 𝑤𝑤1 𝐵𝐵 𝑢𝑢𝑢𝑢1 𝐴𝐴 𝑢𝑢𝑢𝑢1 𝐵𝐵 ; 𝑐𝑐1 ;
𝑙𝑙𝑙𝑙2 𝐴𝐴 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑢𝑢𝑢𝑢2 𝐵𝐵 𝑢𝑢𝑢𝑢2 𝐴𝐴 ; 𝑐𝑐2 ;T2 is blocked by here．If conservative, T2 aborts．

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ;T2 may start earlier.
T1 can start earlier.

T1 aborts since it is lockedQuiz• Can Silo pass the following?
Serializable Schedule

𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐2 ; 𝑐𝑐1 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐2 ; 𝐿𝐿2 𝐴𝐴 ; 𝑊𝑊2 𝐴𝐴 ; 𝑈𝑈2 𝐴𝐴 ; 𝑐𝑐1 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ;𝑟𝑟1 𝐴𝐴 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐2 ; 𝐿𝐿2 𝐴𝐴 ; 𝑐𝑐1 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ;Serializable but…．False negative．

Why is Silo speedy?
1. Short blocking
2. Native latch
3. Invisible read (no cache manipulation)

1. Shorter blocking time.
Silo locks after commit
𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐1 𝑐𝑐2 ;

𝑙𝑙𝑟𝑟1 𝐴𝐴 𝑙𝑙𝑙𝑙1 𝐵𝐵 𝑙𝑙𝑟𝑟2 𝐵𝐵 𝑟𝑟1 𝐴𝐴 𝑤𝑤1 𝐵𝐵 𝑢𝑢𝑢𝑢1 𝐴𝐴 𝑢𝑢𝑢𝑢1 𝐵𝐵 ; 𝑐𝑐1 ;
𝑙𝑙𝑙𝑙2 𝐴𝐴 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑢𝑢𝑢𝑢2 𝐵𝐵 𝑢𝑢𝑢𝑢2 𝐴𝐴 ; 𝑐𝑐2 ;T2 is blocked by here．If conservative, T2 aborts．

𝑟𝑟1 𝐴𝐴 ; 𝑟𝑟2 𝐵𝐵 ; 𝑤𝑤2 𝐴𝐴 ; 𝑤𝑤1 𝐵𝐵 ; 𝑐𝑐1 ; 𝑐𝑐2 ;𝐿𝐿2 𝐴𝐴 ; 𝑉𝑉2 𝐵𝐵 ; 𝐿𝐿1 𝐵𝐵 ; 𝑉𝑉1 𝐴𝐴 ;T2 may start earlier.
T1 can start earlier.

T1 aborts since it is locked2. Native latch
Centralized lock manager is slow
• Disadvantage– Locking may be necessary
for hash.
– Locking is necessary foraccessing an item.
– Many pointer accesses.

• Native latch– A mutex for a record.
– Latching by CAS;
Silo does have a lock manager.
Latches are decentralized like VLL, MOCC.

I14

I28

T23

T1

T8

T2

I4

T23
Granted

I8

T1

T23

Waiting

I12

T8

Database System Concepts, 7th Ed., A. Silberschatz, H. Korth, S. Sudarshan, McGraw-Hill

T. Wang and H. Kimura: Mostly-Optimistic Concurrency Control for Highly Contended
Dynamic Workloads on a Thousand Cores, PVLDB Vol. 10, 2016.

Agenda• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions

If you insert a new data,
a leaf version is updated, then abort
Leaf node: bottom level node.

What is this?
Phantom avoidance
using index

PhantomT1: more results at 2nd read?

𝑟𝑟𝑟 𝑃𝑃 … 𝑤𝑤𝑤 𝑦𝑦 𝑖𝑖𝑖𝑖 𝑃𝑃 … 𝑐𝑐𝑐 … 𝑟𝑟𝑟 𝑃𝑃 … 𝑐𝑐𝑐

P: Predicate
Ex: read <=10
T1

T2

Read
-> x
Insert (z)CommitRead-> x, zCommitx (10), y (30)x (10), y (30), z(3)Concurrent tree
Tree-Locking• B+-tree for serial updates

Lock

Waiting on a queue…

• Only one can access the tree
• No Concurrency

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on BTrees. ACM Trans. Database Syst. 6(4): 650-670 (1981)

Example (Tree-Locking)

7 13

9 11

35

1 2

3 4

5 6

7 8

9 10

15

11 12

13 14

15 16

Concurrent tree
Lock-Coupling• B+-tree for concurrent updates• Top to bottom• Locking area is narrower
𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊 𝑚𝑚 ≠ 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 {𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿(𝑚𝑚)𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑖𝑖𝑖𝑖 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤
𝑛𝑛 ← 𝑚𝑚. 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿(𝑛𝑛)Unlock parent
𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈𝑈(𝑚𝑚)}Lock

Principles of Transaction Processing, 2nd Edition,
Philip Bernstein Eric Newcomer, Section 6.9.

Lock

Example (Lock-Coupling)

7 13

9 11

35

1 2

3 4

5 6

7 8

9 10

15

11 12

13 14

15 16

Concurrent tree
B-link-tree• B+-tree for concurrent
updates– Multithreading• Additional data structure– high_key– Right_link• Features

1. Deadlock free
2. Sorted keys
3. PostgreSQL

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on BTrees. ACM Trans. Database Syst. 6(4): 650-670 (1981)

Example (B-link-tree)

7 13

9 11

35

1 2

3 4

5 6

7 8

9 10

15

11 12

13 14

15 16

insertleaf = find_leaf (key); No locks!
lock(leaf); Lock is acquired at leaf
leaf = move_right (leaf, key);
If (safe) {insert_in_leaf(leaf, key, data);
unlock(leaf);} else { // split
split();
insert_in_parent(leaf, leaf.high_key,
right);}

move_rightwhile (n.high_key < key) {lock(n.right_link);
unlock(n);n = n.right_link;}
return n;

1. Find leaf (key = 25)
Max20
2. 20 < 25

3. move_rightMax30
4. 30 < 25

TX1: insert (27) TX2: search (25)
30

10

20

25
25

10

40

30

20
25

25
10

30

40

30

40

27

30

20
25

30

27

TX1: root
TX1: left
TX1: lock left
TX2: root
TX2: left leaf
TX2: stop at left (blocked)
TX1: Split
TX1: lock root
TX1: unlock left
TX2: lock left
TX2: what’s? -> move_rightWhy deadlock? Two directions.
alice

bob

x, y

y, x

𝑤𝑤𝑤𝑤𝑎𝑎 𝑥𝑥 ; 𝑤𝑤𝑤𝑤𝑏𝑏 𝑦𝑦 ; 𝑤𝑤𝑤𝑤𝑎𝑎 𝑦𝑦 ; 𝑤𝑤𝑤𝑤𝑏𝑏 𝑥𝑥 ;One direction in B-link

Blue can be blocked, but
it will make progress
eventually.

7 13

9 11

35

1 2

3 4

5 6

7 8

9 10

15

11 12

13 14

15 16

Hard to implement…
Why are you there?
• Cause– Inappropriate traversal• How to fix?
– Approach: pencil• No GDB or valgrind…

– Update order• Pointers from right to left
• Keys from right to left

Ideal
1, 2, 3

Real…
1, 3, 2

PostgreSQL Code
Lehman and Yao don't require read locks, but assume thatin-memory copies of tree pages are unshared. Postgres
shares in-memory buffers among backends.
As a result, we do page-level read locking on btree pages
in order to guarantee that no record is modified while weare examining it.
This reduces concurrency but guarantees correct behavior.
An advantage is that when trading in a read lock for awrite lock, we need not re-read the page after getting thewrite lock. Since we're also holding a pin on the sharedbuffer containing the page, we know that buffer stillcontains the page and is up-to-date.
https://github.com/postgres/postgres/tree/master/src/backend/access/nbtree

Concurrent trees• OLFIT– S. K. Cha, S. Hwang, K. Kim, and K. Kwon.
Cache conscious concurrency control ofmain-memory indexes on shared-memory
multiprocessor systems. PVLDB’01.

• PALM– J. Sewall, J. Chhugani, C. Kim, N. Satish, and
P. Dubey. PALM: Parallel architecturefriendly latch-free modifications to B+ trees
on many-core processors. PVLDB’11.

• Masstree

Interior
Node

B+-tree
BorderNode– Y. Mao,, et, al. Cache craftiness for fastmulticore key-value storage. EuroSys’12.
SILO.

• Bw-tree– J. Levandoski, et, al. The Bw-Tree: A B-tree
for new hardware platforms. ICDE’13. MS
SQL Server (Hekaton)– Ziqi Wang, Andrew Pavlo, Hyeontaek Lim,
Viktor Leis, Huanchen Zhang, Michael
Kaminsky, David G. Andersen: Building a
Bw-Tree Takes More Than Just Buzz Words.
SIGMOD’18.

B+-treeIf one inserts a data item,a leaf version is updated, then abort
Leaf node: bottom level node.

What is this?
Phantom avoidance
using index

Agenda• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions

Transaction Processing System =Concurrency Control + Recovery

Concurrency
Control
Recovery

Bank, DFS, blockchain

Motivation• Atomicity– Transactions may abort(“Rollback”)• Durability– What if DBMS stops
running ?

• Preferred– T1, T2, T3: durable– T4, T5: abort

Tx-1
Tx-2
Tx-3
Tx-4
Tx-5

Write Log records on normal process.
Repeating the history
by redoing logs on crash recovery.

Review: Recovery for
Write Ahead Logging (WAL)
Transfer A to B
10000 yen

Write log before modifying DB
RecordA
B

4. Notification

2. CC
Update buffer;
B(-10,000);
A(+10,000);

WDRAM

3. WAL
Generate andflush logs;

Database

Log
Storage(SSD, NVRAM)

Problem of WAL (1)Storage AccessWorkerThreadL

Worker2
L

Worker
1
L

WorkerN
L: Log Record

Write multiple logs together→ Reduces I/O (Group Commit)
Append Sequentially→ Suited for HDD
In Memory
write

HDD
File

L

L

L

L

L

L

L

74

Problem of WAL (2)Mutual Execution on Log Insert

WorkerThreadL

Worker
1
L

Worker2
L

WorkerN
L: Log Record

In Memory
HDD
File

75

Change of Architecture• No more CPU frequency– Shift to many-cores• Development ofFlash/NVRAM– Parallel access with multiple
channel provides highperformance.

Serial WAL is out-of-date
for today’s architecturePerformance of Parallel Write

ioDrive: PCI Express 2.0 x8, SLC, 160GB
SSD:
2.5 inch SATA 3.0, MLC, 120GB
HDD:
2.5 inch SAS 2 6Gb/s, 15,000rpm

ioDrive #8
ioDrive #1

Better

SSD #8
SSD #1
HDD #8HDD #1

Today:Parallel Write Ahead Logging
1. Multiple WAL buffers
2. Multiple WAL files
3. Early Lock Release
神谷，星野，川島，建部：並列ログ先行書き込み手法P-WAL, IPSJ（TOD）, 2017.
Hideaki Kimura: FOEDUS: OLTP Engine for a Thousand Cores and NVRAM. SIGMOD’15
Stephen Tu, et al.: Speedy transactions in multicore in-memory databases. SOSP’13
Tianzheng Wang, et al.: Scalable Logging through Emerging Non-Volatile Memory. PVLDB’14

P-WAL (1/3)
Multiple WAL buffers
Conventional WAL
worker worker
worker
1
2
N
L
L
Collisions
WAL
Buffer L

P-WAL
worker worker
1
2
L
No LCollision
WAL
Buffer

L
L
RAM

RAM

workerN
L

P-WAL (2/3)
Multiple WAL files
RAM

Classical

P-WAL

RAM

L

WAL
Buffer L
L

WAL
Buffer L
L

L

L

L

L

L

L

Sequential
write
WAL
File
HDD

File

write

L

Not contiguous
write
write

WAL
File File 1
SSD

File 2File NP-WAL (3/3)
Early Lock Release• Algorithm– Unlock data items before
writing log records• Pros– Reduce locking time,
provides better throughput• Cons– Worsen latency

D1

D2

D3

1. Lock data
2. Modify data
3. Generate log
4. Write log
5. Unlock data

1. Lock data
2. Modify data
3. Generate Log
4. Unlock data
5. Write log

Ryan Johnson, et al.: Aether: A Scalable Approach to Logging. PVLDB 2010 81

Early Lock Release• Why do we conduct
ELR?
– It improves throughput– Because blocking timeby lock waiting is
reduced• Dirty read anomaly?
– T1 may abort after T2
reads x

T1

T2

Write(x)Read(x)
Abort
CommitCoping with dirty read: notification control
Threads read data in secret to users…
T1

T2

Write(x)Read(x)Commitor Abort
Write(x)1. Here, future of T1 is unknown. Let’s go! (optimistic)
2. If T1 pre-commits (CC ok), T2 pre-commits (CC ok).
Flush logs. Go 4.
3. Else T1 aborts, also T2 (cascading abort (T3,..,Tn))
4. Wait until history completes because we are not surewhether prev. logs are all written to storage.(== no lackof log)Commit

並列ログ先行書き込み手法P-WAL, IPSJ（TOD） 10(1), 24-39, 2017-03-22
Q. Does P-WAL require a centralized counter (LSN)?

Coping with dirty read: notification control
Threads read data in secret to users…
T1

T2

Write(x)Read(x)Commitor Abort

1. Here, future of T1 is unknown. Let’s go! (optimistic)
2. If T1 pre-commits (CC ok), T2 pre-commits (CC ok).
Flush logs. Go 4.
3. Else T1 aborts, also T2 (cascading abort (T3,..,Tn))
4. Wait until history completes or prev. logs are all
written to storage.(== no lack of log)
(MIN_MAX_F_LSN=5)
F_LSN=8 F_LSN=5
F_LSN=9
6,7

Write(x)Commit

TX-1
TX-4
TX-8

TX-2
TX-5

TX-3
TX-9

Complete history by 5
Can notify by 5

並列ログ先行書き込み手法P-WAL, IPSJ（TOD） 10(1), 24-39, 2017-03-22
Q. Does P-WAL require a centralized counter (LSN)?

Thinking about Locking+1+1Counter+10Lock library

Any problem?
counter_pthread_lock.cc% time ./counter_pthread_lockAtomic Add% time ./counter_fetch_and_add

Atomic Add at Many-Core Era

Read epoch here.

What is this?
Phantom avoidance
using index

Q. Why does a thread read epoch at this place?

Epoch based synchronization

All TXs in an epoch become durable at the same time.
e = 1, d = 0• Epoch– A centralized counter, updated only
by a special thread.
– Epoch e– Durable epoch d• Threads

TX-1:e1
TX-4:e1
TX-8:e1– Notifier• Wait until d is less than e in TX.

TX-3:e1
TX-9:e1

No TX are durable.
e = 2, d = 1– Worker• On commit, reads e. No update to e.
No lock is necessary.
• Writes logs with e.

TX-2:e1
TX-5:e1

TX-1:e1
TX-4:e1
TX-8:e1

TX-2:e1
TX-5:e1

TX-3:e1
TX-9:e1

All TX are durable.

All the logs at epoch=Ek is persisted at the same time.
Q. Recovery order and CC order are not the same?
CC: [1->4->8 or 2->5 or 3->9], Rec: [1,4,8,2,5,3,9] same.
CC order <= Rec. order (Never inverse order)Read epoch here.

What is this?
Phantom avoidance
using index

Q. Why does a thread read epoch at this place?

Transaction Processing System =Concurrency Control + Recovery

Concurrency
Control
Recovery
Database
Applications: bank, credit card, distributed file system (spotify), blockchain…

Place of the Epoch

Serialization point of 2PL
For r1(x)w2(x),CC order: 1 → 2
Recovery order: 1 → 2#LocksTime

Place of the Epochw2(x);

r1(x);
r1(x); w2(x);c1;c2

Why not here?

V1(x); L2(x);Then, CC order is determined to 1->2
Because read lock by T1 is ok, thenWrite lock by T2 is ok.
T1 may have many reads…
T2: epoch = 10
epoch++
T1: epoch = 11

CC order: T1 → T2
Recovery order: T2 → T1
No, Inverse Order!

Place of the Epochw2(x);

r1(x);
r1(x); w2(x);c1;c2

V1(x); L2(x);Then, CC order is determined to 1->2
Because read lock by T1 is ok, thenWrite lock by T2 is ok.

Why not here?

T2: epoch = 10
epoch++
T1: epoch = 11

CC order: T1 → T2
Recovery order: T2 → T1
No, Inverse Order!

Q. Is inverse order a problem? T1 is read only, it is not logged. Any problem?

Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden: Speedytransactions in multicore in-memory databases. SOSP 2013: 18-32

Lock

Validate

Write
Production Example: Sho Nakazono et al., LineairDB.
https://lineairdb.github.io/LineairDB/html/index.html

Agenda• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions

Modern CC
MethodYear

Conference

FeaturesPolyjuice

2021

OSDI

Optimistic
Machine Learning

Bamboo2021

SIGMOD

PCC, dirty read

Cicada2017

SIGMOD

Optimistic
Multi-Version

SSN

2017

VLDBJ

Multi-Version

MOCC

2016

VLDB

Optimistic
Pessimistic

TicToc2016

SIGMOD

Optimistic

Silo

2013

SOSP

Optimistic

SI

1995

SIGMOD

Multi-Version

2 Phase Lock1976

Comm. ACM

Pessimistic

Two Mysteries…
• Really fast?

– Using different platform?
[Cicada]– Demonstrating only strong
points?

• Why fast?

– Each paper proposes avariety of fancy techs.
– CC performance depends
on both theory andengineering.
– What is essential for
performance?
From Transactional Information Systems, Weikum, Vossen

Analysis system: CCBenchhttps://github.com/thawk105/ccbench
1. Shared modules.
2. Careful tuning for performance.
3. Masstree

1. Can we apply opt-method X proposed in protocol A to another protocol B?
2. What is the meaning of the optimization methods.
Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, Osamu Tatebe: An Analysis of Concurrency
Control Protocols for In-Memory Database with CCBench. Proc. VLDB Endow. 13(13): 3531-3544 (2020)

Really fast? (MOCC)
Reproducible

Yes, reproducible
T. Wang and H. Kimura. Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads
on a Thousand Cores. PVLDB, 10(2):49–60, 2016.

Why fast?

224 threads analysis (others scalability only)

Answer：Cache, Delay, Version

Cache-Line-Conflicts

Read=95%, Write=5%

1. SI’s scheduling space islargest, but slow
2. Silo/MOCC are nice
3. Centralized ordering is bad

Read=100%, Write=0%

PhantomT1: more results at 2nd read?

𝑟𝑟𝑟 𝑃𝑃 … 𝑤𝑤𝑤 𝑦𝑦 𝑖𝑖𝑖𝑖 𝑃𝑃 … 𝑐𝑐𝑐 … 𝑟𝑟𝑟 𝑃𝑃 … 𝑐𝑐𝑐

P: Predicate
Ex: read <= 10
T1

T2

Read
-> x
Insert (z)CommitRead-> x, zCommitx (10), y (30)x (10), y (30), z(3)• A weaker isolation level should have a wider
scheduling space.
• Wider scheduling space should be faster…

Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, Patrick E.
O'Neil: A Critique of ANSI SQL Isolation Levels. SIGMOD Conference 1995: 1-10

Cache-Line-Conflicts

Read=95%, Write=5%

1. SI’s scheduling space islargest, but slow
2. Silo/MOCC are nice
3. Centralized ordering is bad

Read=100%, Write=0%

Modern CC Research• Assumption– Short– Stored procedure (No NW)• Target Workloads– Whole-sale (TPC-C)– Web (YCSB)

Method

Year

Venue

FeaturesPolyjuice

2021

OSDI

Learning

Bamboo2021

SIGMOD

PCC, dirty
read

Cicada2017

SIGMOD

OCC
MVCC

SSN

2017

VLDBJ

MVCC

MOCC

2016

VLDB

OCC/PCC

TicToc2016

SIGMOD

OCC

Silo

2013

SOSP

OCC

SI

1995

SIGMOD

MVCC

2PL

1976

Comm.
ACM

PCC

Is throttling enough?
Masumura, Hoshino, Kawashima, Accelerating Concurrency Control with Active Thread Adjustment, BigComp’22, Best Paper (2nd)Future Directions• Security (SGX 1TB) [1]• Adaptivity [2]– Self-management/driving• Distributed database [3]– Blockchain, ledger[1] より抜粋• Embedded (CPS) [4,5]– Autonomous car/robot• Batch (long) ???
[1] EnclaveDB: A Secure Database using SGX, IEEE S&P 2018
[2] CMU 15-799 - Spring 2022, Special Topics: Self-Driving Database Management Systems[3] Scalar DLT: https://scalar-labs.com/product/[4] Superfast Subsystem Cooperation, A ROS Centric Database System, ROS World’21.
[5] Making ROS TF Transactional: Ogiwara, Kawashima, et al, ICCPS’22 (WiP, accepted)

Summary• Transaction• Silo CC• Concurrent index• Silo recovery• Modern CC and future directions– Security, Finance, CPS, batch