CSP 期末选题 – 事务并发控制

数据库采用并发控制方法来同时达到高效的事务执行和正确的事务隔离级别(isolation level)。主流的并发控制方法包括two phase locking(2PL)和optimistic concurrency control(OCC)。 这两种方法在实现中会有许多问题需要解决。例如，在2PL中会出现死锁问题，而OCC在高竞争(high contention)的情况下非常低效。在本项目中，大家需要深入调研不同2PL和OCC的实现方法与优化技巧，并尝试比较不同设计和实现之间的取舍。

1. 深入了解实现2PL和OCC中的实现技巧和优化方法。具体的可选的方向包括，但不限于：
   1. Wound-wait是一种处理2PL死锁的方法(System level concurrency control for distributed database systems[TODS’78])
   2. Transaction healing 试图解决OCC中过多abort的问题 (Transaction Healing: Scaling Optimistic Concurrency Control on Multicores[SIGMOD’16])。他在什么情况下能够解决OCC的问题？他的方法具有哪些限制？
   3. OCC的执行可以利用现代处理器硬件来进行加速。 例如，DBX: Using restricted transactional memory to build a scalable in-memory database[Eurosys’14]。 DBX和transactional healing各自从哪个角度来优化OCC的执行？
2. 对一个事务来说，我们能否找到一个方法来总是最优的执行？如果不能，设计者们需要从哪些方面进行取舍？对于只读事务（read-only TX），人们已经找到了理论上的极限。请参考（但不限于）下面两篇论文来阐述，当人们设计事务系统时需要考虑的取舍。
   1. The SNOW Theorem and Latency-Optimal Read-Only Transactions[OSDI’16]
   2. Performance-Optimal Read-Only Transactions [OSDI’20]
   3. 对于最基本的2PL和OCC方法，请阐述他们是否符合理论的结果。
3. (可选) 在一个基本的内存object store上实现一个prototype的事务系统（object系统可以只支持读写操作，而不包括插入和删除）。事务系统需要包括：
   1. 一个基础的并发控制方法，比如最基本的2PL（不带死锁检测）或者最基本的OCC方法（请参考Speedy transactions in multicore in-memory databases [SOSP’13]）
   2. 一个针对基本实现的优化：例如比较不同的死锁处理方法（如wound-wait）；或者OCC的优化方法（如使用HTM）。
   3. 使用一个benchmark来比较优化方法与基本方法之间的性能差别。推荐使用Smallbank[1]来进行比较。

参考资料：

1. [1] https://hstore.cs.brown.edu/documentation/deployment/benchmarks/smallbank