并发与 STM:另一种无锁

底盘:百万绿色线程

先交代这条河的跑道。GHC 的线程是运行时自己调度的绿色线程,创建一个几百字节、微秒级,百万并发是常规操作;运行时把它们复用到少量 OS 线程上(N:M 调度),阻塞 IO 自动让位,多核并行开个 -threaded 编译选项即得。这套模型你最近几年见过两个移植:Kotlin 协程、Java 21 的虚拟线程(Project Loom)——又是熟悉的水流方向。开线程是一个普通函数(不是关键字,呼应第 11 章「控制流是库」):

import Control.Concurrent

main = do
  forkIO (worker "甲")       -- forkIO :: IO () -> IO ThreadId
  forkIO (worker "乙")
  threadDelay 1000000        -- 微秒。主线程退场,全员退场——像不像 daemon 线程?

线程有了,问题也跟着来了:纯的世界共享随便(反正没人能改,这是不可变的并发红利),但 IO 世界的线程们要协作,就得有可变的共享点。它们怎么安全地共享数据?Haskell 给了一条阶梯:最底层是 MVar(一个带锁的单格信箱,take 空则阻塞),够用但会遇到锁的所有经典毛病。毛病里最深的那个,值得用一个完整例子钉死。

先认识一下阶梯的底层。MVar 是一个「至多装一个值的信箱」:takeMVar 取走内容(空则阻塞等待),putMVar 放入(满则阻塞)。拿它当锁、当一格队列、当结果回传信道都行:

main = do
  box <- newEmptyMVar
  forkIO $ do
    r <- expensiveQuery          -- 后台线程慢慢算
    putMVar box r                -- 算完投递
  putStrLn "主线程先干点别的……"
  result <- takeMVar box         -- 需要结果时再取,没到就等
  print result

这个「一格信箱」的通信模式,你在 Kotlin 里叫 CompletableDeferred,在 Java 里叫 CompletableFuture。MVar 简单直接,但两个 MVar 一组合,你就站在了下一节的悬崖边。

锁的原罪:正确 + 正确 = 死锁

银行账户,每个配一把锁,「取款」和「存款」各自加锁,各自完全正确。现在写「转账」:

fun transfer(from: Account, to: Account, amt: Long) {
    synchronized(from) {          // 线程1:transfer(a, b) 锁住 a,等 b
        synchronized(to) {        // 线程2:transfer(b, a) 锁住 b,等 a
            from.withdraw(amt)    // ——经典死锁,而且只在生产环境的月黑风高夜出现
            to.deposit(amt)
        }
    }
}

教科书解法是「全局按账户 ID 排序加锁」——能用,但注意它意味着什么:每个调用点都要知道并遵守一个全局约定,而编译器完全不检查,新同事也不会从任何签名里看到它。锁的组合性问题还有个更隐蔽的形态:库作者把加锁封装得再好,调用方想把两个库操作合成一个原子动作(「取款且积分」),要么拿不到锁的把手,要么拿到了就得自己重新推演整个加锁顺序。抽象在锁面前会漏——这是 Simon Peyton Jones 那篇著名论文《Beautiful Concurrency》的出发点。

STM:借数据库的脑子用一用

数据库领域四十年前就解决过「并发读写共享状态」这道题:答案叫事务。STM 把这套搬进内存——共享变量用 TVar,操作打包成 STM 动作,atomically 负责执行:要么整体生效,要么像没发生过:

transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to amt = do
  balance <- readTVar from
  when (balance < amt) retry        -- 余额不够?挂起,等有人存钱再自动重试
  writeTVar from (balance - amt)
  modifyTVar to (+ amt)

main = atomically (transfer alice bob 100)   -- 没有锁。没有加锁顺序。没有死锁。

机制是乐观并发:事务运行时对 TVar 的写全部记在私有日志里(不落地),同时记下「读了哪些 TVar 的哪个版本」,提交瞬间校验——期间有没有别的事务动过我读过的东西?没有,日志一次性落地;有,整本丢弃重跑,对你完全透明。转账台里两种模式各跑几遍,盯住裸写模式的「不变量被破坏」和 STM 模式的 retry 日志:

回到组合性,这才是 STM 的真正胜负手:两个 STM 动作用 do 一串,就是一个更大的原子动作。「取款且积分」?atomically (transfer a b n >> addPoints a 10),完事——不需要知道任何锁序约定,库作者也不需要为「可能被组合」预留设计。组合性还向上生长:标准库在 TVar 之上盖了整层并发数据结构——TChan(事务性队列)、TMVar、TSem(信号量),它们全是普通 STM 代码,你也能盖自己的楼。「从队列 A 取一个、处理、放进队列 B,整体原子」这种跨结构事务,锁世界要精心设计,这里是三行 do。上面代码里的 retry 同样值得多看一眼:「条件不满足就等待」在锁世界是 wait/notify 迷宫(虚假唤醒、丢失通知……),这里是一个词,运行时知道你读过哪些 TVar,其中任何一个被改写就自动重跑你——条件变量被自动化了。

retry 还有个双生组合子把「等待」也变得可组合:orElse a b——先试事务 a,a 调用了 retry 就换 b,两个都 retry 才整体等待。于是「从任何一个有货的队列取一件」写成 foldr1 orElse (map takeQueue qs)(第 5 章的 fold 在并发层再就业);「等结果,但最多等三秒」是 readResult `orElse` timeoutSignal。锁世界里,「等 A 或 B 任一条件」要把两个条件变量的通知逻辑手工缝合;这里是一个二元操作符,而且天然满足结合律——可组合的阻塞,是 STM 最被低估的一件货。

为什么偏偏是 Haskell 做成了

STM 的点子不新,C++/Java/C# 都轰轰烈烈试过,基本都退潮了(Clojure 是少数例外,靠的是全家不可变)。死因清一色:事务可能被重跑任意多次,如果事务体里有不可回滚的副作用——发个网络包、弹个窗、写行日志——重跑三次就发三个包。命令式语言拦不住你在事务里干这些,于是 STM 的安全性靠文档和祈祷。

现在把第 11 章的国境线搬出来:Haskell 的事务体类型是 STM a,这个 Monad 里只有 TVar 操作——IO 动作类型不对,放不进去,编译不过。「事务内禁止副作用」从道德约束升格为类型检查。这是全书「类型系统当架构执行者」的最佳单例:同一个点子,有国境线的语言做成了工业特性,没有的做成了考古遗迹。GHC 的 STM 从 2005 年稳定服役至今,支撑着 Meta Sigma 每秒百万请求的规则引擎。

fetchAll :: IO Dashboard
fetchAll = do
  (user, (orders, stats)) <- concurrently fetchUser
                               (concurrently fetchOrders fetchStats)
  pure (Dashboard user orders stats)