STM事务日志概念及重试成功时的演变分析（附Haskell示例）

示例代码 #

我们以窗口管理器中移动窗口的STM函数为例：

moveWindowSTM :: Display -> Window -> Desktop -> Desktop -> STM ()
moveWindowSTM disp win a b = do
  wa <- readTVar ma
  wb <- readTVar mb
  writeTVar ma (Set.delete win wa)
  writeTVar mb (Set.insert win wb)
 where
  ma = disp ! a
  mb = disp ! b

对应的IO包装器：

moveWindow :: Display -> Window -> Desktop -> Desktop -> IO ()
moveWindow disp win a b = atomically $ moveWindowSTM disp win a b

STM事务日志核心概念 #

STM事务通过累积执行过程中所有readTVar和writeTVar操作的日志来工作，该日志有三个核心作用：

• 将writeTVar操作暂存于日志而非直接写入主内存，这样中止事务时只需丢弃日志即可，成本固定且低廉。
• 每次执行readTVar时，都会遍历日志检查该TVar是否已被当前事务内的writeTVar修改过，因此readTVar是一个与日志长度相关的O(n)操作。
• 日志记录了事务所有readTVar操作，可据此确定事务读取的TVars集合，这是实现retry机制的必要信息。

当事务执行到末尾时，STM会将日志中记录的读取值与主内存当前内容比对：若完全匹配，则将日志中的写入操作提交到主内存；否则丢弃日志，从头重试事务。提交阶段会锁定事务涉及的所有TVars以保证原子性，GHC的STM实现不使用全局锁，仅在提交阶段锁定相关TVars，因此操作不相交TVars集合的事务可并行执行互不干扰。

给定场景下的日志演变与验证失败分析 #

假设事务在第三次尝试时成功，前两次失败原因分别为：

• 第一次尝试：执行完wa <- readTVar ma后，并发事务修改了ma
• 第二次尝试：执行完writeTVar ma (Set.delete win wa)后，并发事务修改了ma和/或mb

第一次尝试（失败） #

1. 执行wa <- readTVar ma：日志添加读取记录(ma, 初始wa值)
2. 执行wb <- readTVar mb：日志添加读取记录(mb, 初始wb值)
3. 执行writeTVar ma (Set.delete win wa)：日志添加写入记录(ma, 删除窗口后的wa集合)
4. 执行writeTVar mb (Set.insert win wb)：日志添加写入记录(mb, 添加窗口后的wb集合)
5. 提交验证阶段：STM对比日志中ma的读取值与主内存当前值，发现不匹配，验证失败
6. 丢弃本次日志，触发重试

第二次尝试（失败） #

1. 从头执行，wa <- readTVar ma：日志添加读取记录(ma, 并发修改后的wa值)
2. wb <- readTVar mb：日志添加读取记录(mb, 当前wb值)
3. writeTVar ma (Set.delete win wa)：日志添加写入记录(ma, 删除窗口后的wa集合)
4. writeTVar mb (Set.insert win wb)：日志添加写入记录(mb, 添加窗口后的wb集合)
5. 提交验证阶段：STM对比日志中ma和/或mb的读取值与主内存当前值，发现不匹配，验证失败
6. 丢弃本次日志，触发重试

第三次尝试（成功） #

1. 从头执行，wa <- readTVar ma：日志添加读取记录(ma, 当前wa值)
2. wb <- readTVar mb：日志添加读取记录(mb, 当前wb值)
3. writeTVar ma (Set.delete win wa)：日志添加写入记录(ma, 删除窗口后的wa集合)
4. writeTVar mb (Set.insert win wb)：日志添加写入记录(mb, 添加窗口后的wb集合)
5. 提交验证阶段：STM对比所有读取值与主内存当前值，完全匹配
6. 锁定ma和mb，将日志中的写入操作提交到主内存
7. 释放锁，事务完成，日志被清理

关键结论 #

• 每次重试都会生成独立的新日志，失败事务的日志会被直接丢弃，不会影响主内存
• 验证失败仅发生在事务执行完毕后的提交阶段，STM不会在执行过程中实时检查冲突
• 并发事务对TVars的修改，只会导致当前事务在提交验证时失败，进而触发重试

内容的提问来源于stack exchange，提问作者Enlico