数据库并发控制

[HUANGChaoLi]

Architecture

Two-Phase Locking

1. 2PL with Deadlock Detection
2. 2PL with Non-waiting Deadlock Prevention(the most scalable deadlock prevention technique)
3. 2PL with Waiting Deadlock Prevention(Wait Die)
4. 2PL with Wound Wait
5. conservative 2PL
6. strict 2PL

Timestamp Ordering

1. Basic T/O
2. OCC
3. MVCC
4. T/O with Partition-level Locking

Deterministic CC

[HUANGChaoLi]

From:

1. https://15721.courses.cs.cmu.edu/spring2020/
2. https://www.zhihu.com/question/60278698

[HUANGChaoLi]

参考文献： [1] Yu X, Bezerra G, Pavlo A, et al. Staring into the abyss: An evaluation of concurrency control with one thousand cores[J]. 2014. [2] Berenson H, Bernstein P, Gray J, et al. A critique of ANSI SQL isolation levels[J]. ACM SIGMOD Record, 1995, 24(2): 1-10. [3] Ports D R K, Grittner K. Serializable snapshot isolation in PostgreSQL[J]. arXiv preprint arXiv:1208.4179, 2012. [4] Wang T, Johnson R, Fekete A, et al. Efficiently making (almost) any concurrency control mechanism serializable[J]. The VLDB Journal, 2017, 26(4): 537-562. [5] 龙逢. OCC 的前世今生[EB/OL]. [2020-03-26]. https://zhuanlan.zhihu.com/p/41505168. [6] Harding R, Van Aken D, Pavlo A, et al. An evaluation of distributed concurrency control[J]. Proceedings of the VLDB Endowment, 2017, 10(5): 553-564. [7] Ren K, Thomson A, Abadi D J. An evaluation of the advantages and disadvantages of deterministic database systems[J]. Proceedings of the VLDB Endowment, 2014, 7(10): 821-832. [8] Wu Y, Arulraj J, Lin J, et al. An empirical evaluation of in-memory multi-version concurrency control[J]. Proceedings of the VLDB Endowment, 2017, 10(7): 781-792. [9] Abadi D J, Faleiro J M. An overview of deterministic database systems[J]. Communications of the ACM, 2018, 61(9): 78-88.

[HUANGChaoLi]

影响基于磁盘的 OLTP 的因素：

1. logging
2. locking
3. latching
4. buffer manager

[1] Stonebraker M, Harizopoulos S, Abadi D J, et al. OLTP Through the looking glass, and what we found there[C]//Proc. of ACM SIGMOD Int. Conf. on Management of Data. 2008.

常见问题：

1. pointer chasing
2. CPU caching (pollutes CPU caches by reading unneeded versions)
3. garbage collection (Txn-Level / Tuple-Level / Epochs)
4. timestamp allocation (Atomic Addition is greater)

[1] Neumann T, Mühlbauer T, Kemper A. Fast serializable multi-version concurrency control for main-memory database systems[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015: 677-689. [2] Böttcher J, Leis V, Neumann T, et al. Scalable garbage collection for in-memory MVCC systems[J]. Proceedings of the VLDB Endowment, 2019, 13(2): 128-141.

[HUANGChaoLi]

业务层分布式事务一致算法（延伸问题）：

1. 两阶段提交（2PC, Two-phase Commit）方案
2. eBay 事件队列方案
3. TCC 补偿模式
4. 缓存数据最终一致性

[1] 网易云 Inc. 常用的分布式事务解决方案有哪些?. https://www.zhihu.com/question/64921387.