关于Clojure STM write skew详解

考虑一个数据库系统重的普遍情形: 对同一个数据, 一个线程对其进行读取, 另一个线程写入, 两者同时发生. 如果不加控制, 结果肯定会出问题, 以表的一个行为例子, 可能一个线程更新了某个字段, 另一个字段还没有更新, 另一个线程就读取了这一行, 等两个线程都执行完成, 他们看到的数据肯定是不一致的. 为了解决这个问题, 最简单, 最直接的方式就是加锁, 读的时候锁定, 其他线程等待, 读完了之后释放, 写的时候也加锁, 其他线程访问的时候等待.

这样的问题也同样出现在多人并行开发的版本控制系统当中, 采用最简单的方法相当于, 某个开发人员修改代码的时候, 文件就会被锁住, 其他人不能访问, 只能干等. 很显然这样的模式可以保证数据的完整性, 但是要牺牲系统的效率.

像GIT这样的版本控制系统采取了不同的方法, 每个人都拥有整个项目的在某个时候的完整副本(或者叫做快照, snapshot), 每个人都有一个在某个时间点中数据保持一致性的独立的世界(术语叫做point in time consistent view). 所有人可以并行的做自己的工作.

这一点体现在数据库系统当中就是采用MVCC并发控制. 这样会提高并发性能, 当然也有代价, 那就是write skew.

MVCC除了用在版本控制系统和数据库当中, 还是STM的实现原理. 这次我们讨论的是Clojure中的STM.

write skew的概念是一种很难用普通的语言可以描述清楚的概念. 他本身描述是一种并发环境中出现的情况, 并且涉及到了快照隔离和MVCC的具体实现细节方面的问题. 目前Clojure和Haskell都支持STM, 要想更好的利用这些系统我们必须理解write skew.

GIT例子

某种意义上GIT也可以看成一个以快照隔离位基础的并发系统, 每一个分支就是一个事务, 而建立分支时候的版本就对应一个系统的快照, 而事务的commit和git某个分支上的comit有所区别, 和事务提交更加类似应该是merge, 即从某个分支上签出的新分支, 完成修改之后通过merge将修改返回到原来的分支当中.

事实上任何具备版本概念的版本控制系统几乎都提供了MVCC的支持.

下面的GIT流程模拟write skew

 
git init
echo 1 > a.txt
echo 2 > b.txt
git add .
git commit -m "initial commit"
git branch t1
git branch t2
git checkout t1
echo 1 > b.txt
git add .
git commit -m "changes in t1"
git checkout master
git merge t1
git checkout t2
echo 2 > a.txt
git add .
git commit -m "changes in t2"
git checkout master
git merge t2
type a.txt
2
type b.txt
1
 

t1提交之后, t2中拿到的快照其实已经失效了, 但是t2的提交却不会造成冲突, 尽管是在没有观察到另一个分支已经修改了原始的数据从而导致快照失效的情况下.

write skew的典型案例之一: 相向拷贝

这篇文章:Thoughts on STM 提到了这个案例的简化版, 并用Clojure写了一个实例程序. 另外一个是用黑棋白棋表示的, 用SQL Server演示:Serializable vs. Snapshot Isolation Level. 其实原理一样.

这个例子及其变种常常用来演示write skew.

 
(defn move [src dst]
    (dosync
        (let [tmp @src]
        (Thread/sleep 500)    ; artifical delay
        (ref-set dst tmp))))
 
(defn ws []
    (let [a (ref 1) b (ref 2)]
        (dorun (pcalls #(move a b) #(move b a)))
        [@a @b]))
 
 

中间那个delay的作用是什么? 其实就是为了让read操作发生在对方transaction commit之前发生, 因为如果一个transaction已经commit了, 另一个transaction中的read会导致retry, 就看不到write skew的现象. 如果没有delay的话, 和可能第一个transaction瞬间完成了, 而第二个transaction还没有开始.

上面的例子中无论哪个transaction先commit, 都可以观察到write skew现象. 下面让第一个transaction先commit, 修改b的值, 而第二个transaction则仍然使用b的旧值, 并且成功提交

 
 
(defn move1 [src dst]
    (dosync
        (let [tmp @src]
        (Thread/sleep 100)    ; artifical delay
        (ref-set dst tmp))))
 
 
(defn move2 [src dst]
    (dosync
        (let [tmp @src]
        (Thread/sleep 500)    ; artifical delay
        (ref-set dst tmp))))
 
(defn ws []
    (let [a (ref 1) b (ref 2)]
        (dorun (pcalls #(move1 a b) #(move2 b a)))
        [@a @b]))
 

如图

 write skew

其实单个ref变量可能看的更加清楚, 对单个ref变量同时启动两个transaction, 一个写入, 一个读取, 最终有可能达到不一致性. 我们设计的两个transaction的交替过程如下

t1 t1同时启动, t1写入, t2读取, t1 commit, t2 commit.

在t2读取的时候, ref在t1的snapshot中已经改变, 但是还没有commit, 这个时候潜在的不一致性的可能性已经存在了, 因为t1 t2两个transaction中的拷贝已经开始分叉了, 假如t2基于所读取到的值去做某些事情, 而这些事情在t1更新后的状态的情况下又是不允许的, 当t1成功提交的时候, 不一致性就显式化了, 而t2所使用值此时就不是最新的值 ,因为t2所看到的值和t2所在的事务是一致的, 即仍然符合point in time consistent view, 这个是实际是一个历史值, 因此t2不会retry, t2也会commit成功.

假设ref的初值是1, t1会增1, 同时ref的值和另外一个状态关联: ref等于1的时候另一个状态必须是"A", ref是2的时候另一个状态必须是B.

下面的代码中有两个事务

 
(let [a (ref 1) associated (atom "A")]
  (pcalls
    #(dosync (println "t1 starting")(Thread/sleep 100) (alter a + 1) (reset! associated "B")  (Thread/sleep 100) (println "t1 commit"))
    #(dosync (println "t2 starting")(Thread/sleep 150)  (println "before read ref, t1 should update but not commit") (if (= @a 1) (do (println "a is 1 inconsistent") (reset! associated "A")) (do (println " a is " @a) (reset! associated "B"))) (Thread/sleep 150) (println "after reading ref, if retry this should not show up") (println "t2 commit"))
  )
  (Thread/sleep 1000)
  (println "a is " @a " associated is " @associated)
)
 

单独的看两个事务, 他们都保持了ref和另外一个状态的关联关系, 但是这段代码如果大家贴到REPL里面, 结果是

 
a is  2  associated is  A