1.

2. -

3. Ø Ø Ø X 2005 11 12 POLARDB

4.

5. • ACID • A I • LSN ID

6. MVCC • MVCC • MVCC •

7. • LSN • • • LSN

8. Lamport • LC counter • Counter • LC happen-before A1 B2 C3 # event is known time = time + 1; # event happens send(message, time); #receiving a message (message, time_stamp) = receive(); time = max(time_stamp, time) + 1;

9. HLC HLC l.j Logic Time c.j pt.j Initial l.j := 0; c.j :=0 • Send or local event l’.j := l.j; l.j := max(l’.j, pt.j); IF (l.j == l’.j) THEN c.j := c.j + 1 ELSE c.j := 0; Timestmap with l.j, c.j j wall time • Receive event of message m l’.j := l.j; l.j := max(l’.j, l.m, pt.j); IF (l.j == l’.j == l.m) THEN c.j :=max(c.j, c.m) + 1 ELSEIF (l.j == l’.j) THEN c.j:= c.j + 1 ELSEIF (l.j == l.m) THEN c.j:= c.m + 1 ELSE c.j := 0 Timestamp with l.j, c.j • • HLC bounded

10. HLC • TSO • HLC • happen before TSO HLC T1 T1 start end T1 T1 T3 T2 HLC T3 T2 T3 T3 T4 T4 1 T1,T2,T4 1 2 t1 < t2 < t4 T1,T2,T3 th2 2 th1 < th2 th4 th1 < th3

11. TSO HLC GTM Truetime SCN

12. VS. VS. Truetime Truetime HA HLC • • • • region HA wall time DB • • • • • skew skew

13.

14. 1 Update Table 1 set C2=1 where C2=2 2 1 Table1 row1 row2 Table1 C1 1 3 C2 2 1 row1 row2 C1 2 7 C2 2 4 • • 1 2 row1 row1 1 1 2 2

15. 2 Update Table 1 set C2=1 where C2=2 • 2 1 Table1 row1 row2 Table1 C1 1 3 C2 2 1 @t1 row1 row2 C1 2 7 C2 2 4 @t2 • 1 2

16. • Prepare • prepare • • • prepare • prepare abort International Journal of Intelligent Information and Database Systems 4(4):373-412 · September 2010 From “Atomic commit protocols, their integration, and their optimisations in distributed database systems”,

17. MVOCC

18. HLC HLC HLC 1 HLC begin 1000 HLC 0 Select * from t1 2 HLC 1001 10 999 20 1001 10 1000 0 1002 0 1001 0 1002 0 Insert into t1 values 1 only Insert into t1 values 2 only Prepare 1 Prepare 2 Commit 1 Commit 2 1002 0 1002 0 1002 0

19. Read sql select * from t1 ( 1 HLC service: 103 update to 1000 T2 Context: T3 Context: T4 Context: (key1, v2) (key2, v2) (key3, v3) (key4, v4) T3:xid3 N/A T2 T3 T4 2 HLC service: 1000 T1 Context: T2 :xid2 commit_ts:101 T1 T4:xid4 prepare_ts:102 read_snapshot:1 000 read with snapshot 1000 read with snapshot 1000 T3 prepare key3 HLC 1000 T3 commit_timestamp>prepare_timestamp>1000 Try update No need HLC service 1002 T3 Context: T4 Context: (key30, v30) (key40, v4) T3:xid2 prepare_ts:998 Read table Table t1 Key1(93) à old_v1 Key2(xid2) à v2 Key2(36) à old_v2 Key3(xid3) à v3 Key4(xid4) à v4 Key4(78) à old_v4 T3 T4 prepare 998 read snapshot commit_timestamp>1000 102 1000 1000<=read snapshot, (key4, v4) 1000 (key40, v40) Table t1 Key30(xid2) à v30 Key40(1000)à v40 T4:xid4 N/A

20. HLC • HLC peak TPS • TPS=logical counter • / Peak TPS = 2^16 / 2 / 0.001 = 3 • 5ms • Peak TPS = 2^16 / 2 / 0.005 = 6 peak TPS • • • • switchover • • HLC logic counter overflow /

21. • • • • • • •

22. HLC • • • • • • / happen-before

23.

24.