CSE_lecture12:Transaction

Serializability, OCC & Transaction

OCC: optimistic concurrency control

死锁难以解决，因此需要避免，可以引入乐观并发控制(OCC)，其认为数据不会被race condition，因此不用拿锁，检查结果，如果真的发生race condition就放弃并重试

OCC执行事务分为以下三个阶段：

• 并发本地控制：不上锁，读数据放入read set，写操作进行缓存而非直接写，放入write set
• 操作完成后进行可串行化检查：检查read set里面的数据是否被别人修改
• 检查失败就放弃，成功就将write set写入磁盘

只通过数据的值来判断race condition是有问题的，因为可能被另一个事务修改过后又被第三个事务改回去了，因此需要维护一个严格递增的version

OCC还需要保证单个数据的读取是原子性的，一种方法是拿锁，另一种方法是最先拿version，读取数据的值后再检查version是否变化

写操作时在更新write set后，需要更新read set，保证后续read能读到write后的值

OCC的阶段2(validation)和阶段3(abort/commitment)也要保证before-or-after，是不能拆开的，即实现一整个critical section，可以上一个全局锁，也可以为每个set里的数据上2PL锁，但缺点是没有规避死锁，以及拿锁有开销

死锁的解决方法为按照从小到大的顺序拿锁，在OCC可以这样做，因为提交阶段可以确定所有的操作，因此直接排序就好了；而为了优化拿锁的开销，可以不拿read set的锁，因为validation本身就是一个隐形的锁

def validate_and_commit() // phase 2 & 3
    for d in sorted(write-set):
        d.lock()
    for d in read-set:
        if d has changed:
            abort()
    for d in write-set:
        write(d)
    // release th locks

上述代码并非没有问题，可能出现read-write conflict

因此在validation阶段需要检查是否上锁：

def validate_and_commit() // phase 2 & 3 with before-or-after
    for d in sorted(write-set):
        d.lock()
    for d in read-set:
        if d has changed or d has been locked:
            abort()
    for d in write-set:
        write(d)
    // release th locks

OCC的好处在于能减少拿锁的开销，因为拿锁的开销是很大的，尤其是相较于read

但OCC也有问题，即不必要的放弃，对于没有环的两个事务，OCC因为只能允许某一种顺序，会放弃其他可以等效串行化的顺序

当read非常多时，放弃的概率会更高，这会引发活锁，即事务在反复重试

低并发情况下OCC吞吐量更高，高并发情况下2PL更高，但性能都下降了

使用fast path和slow path，使用fast path加速，并进行validate，失败再采用slow path，这建立在两个假设：fast path + validate加起来快于slow path，且fast path常见

在LLM中，要加速很大的模型的推理速度，可以先用小模型推理，再用大的模型验证，验证失败再重新让大的模型推理

Hardware Transactional Memory(HTM)是一种用于多并发的新CPU特性，在intel中为RTM(Restricted Transactional Memory)，提供了两个指令：xbegin和xend，当出现race condition时会放弃并返回abort code，而直接重试不能解决问题，因为RTM本质也是OCC

在RTM中，使用cache来记录read/write sets来防止外泄，其修改时就会广播，从而知道发生了race condition，这限制了read/write sets的大小；另一方面，操作系统中线程会定期中断并切换，此时cache会刷到内存，而这会导致数据泄露，RTM会直接放弃

对于简单的操作，HTM比软件层面的OCC性能更高，但一旦复杂起来就表现很差了

transactions

事务是一个管理数据的抽象，其保证了ACID(Atomicity, consistency, isolation, durability)

atomicity保证了all-or-nothing，isolation保证了before-or-after，durability保证了事务提交后，数据能被持久化

consistency和atomicity不同，其是面向用户的，即数据库只管理atomicity，而应用层保证用户定义的consistency，比如转账时银行总金额不变。但一般而言consistency和atomicity + isolation关联很强

目前OCC和2PL不能达到要求，但在特殊情况下它们可以很快