CSE_lecture11:Before or after atomicity

Before-or-after atomicity and Serializability

并发能提升吞吐量，但是会危害正确性，因此需要引入before-or-after模型

假设有一个单线程的银行系统，此时请求响应的时间不会仅由RPC和请求处理时间的时间决定，而是由吞吐量决定的。当有多个请求发过来时，请求会陷入排队，出队后才会处理，因此当request arrival rate大于system throughput时，延迟会爆炸

使用concurrency来scaling throughput：

• scale-up: 一台机器跑多线程
• scale-out: 多台机器并发运行

但并发操作容易引发正确性问题：

race condition难以控制，同时不确定性导致难以发现和debug

保证在并发情况下，能够让效果等价于一系列操作的串行执行，因此需要维护一些操作整体为原子的，挡住可能会引发race condition的其他操作

使用全局锁(global lock)可以达到这个效果，但会导致性能很差，如导致不会引发race contidion的操作阻塞，以及拿锁本身也会有开销。因此需要减小锁的范围，比如不同的数据记录（如不同账户）使用不同的锁(fine-grained lock)，但缺点是不能严格保证before-or-after，如存在访问多个数据的操作

对于要处理多个数据的操作，应当在开头拿到所有锁，在结尾才释放掉所有锁

这样的缺点是拿锁的时间会非常长，因此引入two-phase locking(2PL)，即只保证操作在释放某一个锁后不再拿任何新的锁，此时可以实现不在一开头拿完所有锁，也不用在最后才释放所有锁

global lock, fine-grained lock, 2PL lock都能保证before-or-after atomicity

判别是否保证before-or-after的一种方法是能否找到一个等价的串行执行，这不仅要保证写的正确性，也要保证读的正确性，即判别view serializability时，需要找到一个view equivalent的serial schedule，满足每个操作的读正确，最终写正确

而view serializability在操作极多时无法检查，因此使用conflict serializability，定义conflict为：

• 两个操作都在操作同一个数据
• 至少有一个在写
• 属于不同的事务

conflict serializability只需要找到所有conflict的顺序等价于某一个串行的conflict关系。可以认为事务是节点，conflict是有向边（方向为第一个操作发生在哪个事务中），只要其为无环图，就能找到一个拓扑排序，从而实现conflict serializability

但事实上就算有环，也可以找到一个等价的串行执行（写最终正确，每个操作的读正确），因此认为 $\text{view serializability} \supset \text{conflict serializability}$ ，conflict serializability虽然定义更严格，但实现更容易

2PL能够实现conflict serializability，可以用反证法证明

然而2PL其实并不见得一定能保证conflict serializability，因为可能出现错拿锁漏拿锁，比如下图新插入的老师没有涨薪，因为锁是存在在成员内部的，即幻读问题(phantom problem)

解决幻读问题可以用以下方法：

• 谓词锁(predicate lock)，即锁住满足某个条件的所有数据，但开销大
• 为B树非叶子节点上锁，实现范围上锁，或锁住整张表
• 忽略

2PL的另一个问题就是死锁。2PL本身是一个悲观锁(pessimistic)，即认为race condition一定发生，故访问数据前一定上锁，但这样可能引发死锁，即互相等待对方释放锁

死锁的解决方法如下，但事实上都各有各的问题：

• 让大家都按照同一个顺序访问各个数据(pre-defined order)，但难以提前知道要访问哪些数据
• 找到环，并放弃环中的一个事务，但开销极大，而且该事务重做后可能再次被放弃
• 超时后就放弃