17. May 2012 · Write a comment · Categories: 技术文章 · Tags:

(Source: http://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/

Clojure 有很多功能可以帮助在程序中处理并发问题。本文将关注软件事务内存(Software Transactional Memory,缩写 STM),不过这些并发问题的共性都是由多个部分共同运行来得以解决,因此我们期待一些其他思想的渗入……

STM 是什么?

软件事务内存 (STM) 是一种模拟数据库事务的并发控制机制来控制在并行计算时对共享内存的访问控制。它是锁的一种替代机制。

维基百科 – http://zh.wikipedia.org/wiki/软件事务内存

STM 允许在内存中更新多个数据,这些变更对于其他同时在执行相同逻辑的线程来说,显而易见是原子性的。类似数据库中的事务,如果因为某些原因有些更新没有完成,然后就会取消所有更新操作。

一个典型例子就是银行的交易 – 你希望把你的账户中的一些钱转账到我的账户……,我们将使用这个作为我们的例子,因为从概念上来说大家都熟悉。

目前在计算机科学中,STM 的实现还不是一个已经解决的问题,正在进行的研究是怎样更好的完成它。Clojure 选择了一个基于多版本并发控制(MVCC)的方法,MVCC在一个事务中维护多个(逻辑)版本数据的引用。在你的事务执行过程中,你看到的是一份数据的快照,与事务开始时看到的数据是一样的。当你认为在Clojure中普遍使用持久性数据完成你的很多事情,而不需要做太多额外的工作时,MVCC就是一个显而易见的选择。

为什么我们需要 STM?

STM 的核心是 ref 和 dosync,让我们看一个例子……

(def account1 (ref 100))
(def account2 (ref 0))

; to read the current value of a ref, use (deref refname):
;=> (deref account1)
100
;=> @account1 ; @refname is equivalent to (deref refname)
100

(defn transfer [amount from to]
    (dosync
       (alter from - amount)   ; alter from => (- @from amount)
       (alter to   + amount))) ; alter to   => (+ @to amount)

;=> @account1
100
;=> @account2
0
;=> (transfer 100 account1 account2)
100
;=> @account1
0
;=> @account2
100

你们看到我们在这里定义了两个账户,第一个账户 account1 初始化了 100。(transfer) 函数接收一个数量参数amount,一个来源账户 from 和一个目标账户 to,然后使用 alter 修改两个账户,从 from 账户中减去 amount 的数量,添加同样的 amount 数量给 to 账户。这段代码运行在一个单线程中,但是考虑一下,如果还有一个线程在两个 alter 语句之间运行,修改了两个账户中的值,这会发生什么呢?如果没有 STM 的保护,就很容易丢掉其中一个或者两个账户的变更。

另外一个例子;假设在一天结束时,银行希望给所有账户生成一份结算报表。可能这份报表需要很长时间的运行,但是在报表的生成过程中,依然可以对账户交易,并且为了报表目的,我们应该看到的是一致的数据视图。

在 Clojure 中 STM 是怎样工作的

看下面的这张图,你会看到粉色盒子中的三个事务,你也会看到最左边一列中ref值的不同版本。当一个事务通过 (dosync) 开始后,就会获取到ref的版本。获取到的值是在事务执行过程中 (deref) 返回的值(也就是说在事务中读取的ref都是不变的)。

让我们看看最左面的两个事务,两个事务同时开始,同时获取到了相同的 ref 值,因此两个获得的都是 ref 版本为 0 的一份副本。在事务中会执行一些操作,ref 的值将会被更新。第一个(最左面)的事务首先结束,所以赢得了比赛,把 ref 更新为新值。当第二个事务结束时,它尝试写入它的值,但是写失败了(图例中的红色箭头),因为 ref 的版本不是预期的。在这个例子中,事务就重新执行了。注意当事务重新执行时,它首先获得了 ref 新版本的副本,也就是看到的是第一个事务中变更后的值。然后由于没有其他事务尝试更新 ref,这次第二个事务就完成了。

你也看到这一切在进行的同时,第三个事务一直在运行,但是事务的处理过程中没有更新 ref 的值,所以不需要重试事务操作,事务运行完成。

如果保存在 ref 中的值是持久化的数据结构,在内存中保存这些数据结构的多个逻辑版本是很有效率的,因为这些数据结构会共享内部结构。当然,也会使用额外的资源,在一些场景中可能也会出现问题。当定义 ref 时,你还有一些选项来决定在运行时如何管理这些 ref 的历史(也就是上面讨论的这些版本数字)。

; pre-allocate history and limit max-history
(def myref (ref 1 :min-history 5 :max-history: 10))

; supply a function to validate the ref before commit.
(def myvalidref (ref 1 :validator pos?))

这个可以让你通过使用预分配和限制历史资源的使用,来提高在读取-失败中的边界效率。

宽松的一致性和副作用

在一些并发的事例中,你可以放宽松一点,以获得一些的效率。举个例子,假设你要保留一天的交易日志。如果你知道最后的交易结果始终是正确的,你可能就不大关心这些交易的顺序。说实在的,如果你收到两笔分别是 ¥100和¥50的存款,你可能就不在乎它们是被记录为¥100然后¥50,还是¥50然后¥100。存款的两个事务是可交换的,Clojure 也提供了一个并发操作 (commute) 来完成这样的事情……

(defn log-deposit [account amount]
     (dosync
        (println "Depositing $" amount " into account, balance now: "
            (commute account + amount))))

(def myaccount (ref 0))

(log-deposit myaccount 100)
(log-deposit myaccount 50)

; (as good as) equivalent to 

(log-deposit myaccount 50)
(log-deposit myaccount 100)

需要注意 (commute) 的是,当函数调用时,它设置了ref在事务中的值,但是在提交的时候才会真正的做出修改,是通过再次运行传入给 commute 的函数和最新的 ref 值。 这意味着在你的事务中你计算的值可能不是最终提交给 ref 的值。这需要考虑的认真点,你要确保你的操作过程中不依赖最新的 ref 值。

最后,你可能会疑惑上面例子中的 (println),在事务重试的事件中会产生什么副作用呢?会发生一个很简单的副作用。对于上面的例子,这个可能是个不太重要的事情,就是日志将会不一致,但是数据的真实来源将会是正确的。

Clojure 也提供了一个宏,也就是 io!,这个允许你把代码标记为不允许运行在一个事务中。你可以用这个来保护你自己无意中在一个事务里面调用了有副作用的代码。

例如:

(defn log [s]
   (io!
      (println s)))

(log "Hello World") ; succeeds

(dosync (log "Hello World!")) ; throws IllegalStateException

要正确的在一个事务内部完成 IO,你最好从事务内部把消息扔给Agent,Clojure 中的 Agent 是和 STM 整合在一起的,这样当事务成功时就会发送消息,如果事务失败就会被丢弃。