软件事务内存导论(二)软件事务内存

声明：本文是《Java虚拟机并发编程》的第六章，感谢华章出版社授权并发编程网站发布此文，禁止以任何形式转载此文。

1.1    软件事务内存

将实体与状态分离的做法有助于STM（软件事务内存）解决与同步相关的两大主要问题：跨越内存栅栏和避免竞争条件。让我们先来看一下在Clojure上下文中的STM是什么样子，然后再在Java里面使用它。

通过将对内存的访问封装在事务（transactions）中，Clojure消除了内存同步过程中我们易犯的那些错误（见《Programming Clojure》[Hal09]和《The Joy of Clojure》[FH11]）。Clojure会敏锐地观察和协调线程的所有活动。如果没有任何冲突——例如，每个线程都在存取不同账户——则整个过程中就不会涉及到任何锁，于是也就不会有延迟，并最终达到最大的并发度。当有两个线程试图访问相同数据时，事务管理器就会介入解决冲突，而我们的代码也就无需涉及任何显式加锁的操作。下面让我们一起研究一下这套系统是如何运作的。

在设计上，值（values）是不可变的，而实体（identities）也仅在Clojure的事务中是可变的。在Clojure中，压根就没有改变状态的方法，也没有任何相关的编程工具可用。而如果出现任何试图在事务之外改变实体的动作时，系统就会抛出illegalStateException异常。换句话说，一旦与事务进行了绑定，在没有冲突时，所有变更都是即时生效的；而一旦发生冲突，Clojure将会自动将事务回滚并重试。我们程序员的主要职责是保证事务中的代码都是幂等的——这是我们在函数式编程中避免副作用的常用手段，而这种手段在Clojure的编程模型中也同样适用。

是时候该看一个Clojure STM的例子了。我们可以用ref在Clojure中创建多个可变的实体，其中每个ref都提供了对于其表示的不可变状态的实体的可协调同步变更[1]。下面就让我们创建一个ref并尝试改变它。

(def balance(ref 0))

(println "Balance is "@balance)

(ref-set balance 100)

(println "Balance is now" @balance)

在上面的代码中，我们定义了一个名为balance的变量并用ref将其标记为可变的，此时balance就表示了一个带有不可变数值0的可变实体。然后我们将该实体的当前值打印了出来。接着我们会通过ref-set命令来尝试修改balance的值。如果该操作成功，我们就可以通过最后一条打印语句看到balance的新值。下面就让我们来看看这段代码的执行结果。我是用clj mutable.clj来运行这个脚本的，关于如何在你的系统上安装和运行Clojure脚本请参阅Clojure的文档。

“Clojure还提供了一些我在本书中未能覆盖的其他并发模型，如Agents，Atoms和Vars。更多信息请参阅Clojure的官方文档和相关书籍。”

Balance is 0
Ecception in thread "main"
   java.lang.IllegalStateException : No transaction running(mutate.clj:0)
...

从结果来看，由于控制台正常打印出了实体balance的值0，因此前两行代码应该是没问题的。由于我们在事务之外更改了变量的值，以至于惹恼了Clojure之神，所以在执行到第三行的时候系统抛了IlligalStateException异常。当我们在没进行同步就更改共享可变变量的时候，与Java里那些人神共愤的行为相比，Clojure抛出的这种清晰明确的失败简直是程序员的福音。这对于程序开发来说是一个相当大的改进，因为我们宁愿代码要么正确要么明确地抛出错误，而不是默默地产生一些不可预测的结果。问题进行到这里，原本我还想邀你庆祝一下我们获得了这么好的特性呢，不过看你的样子可能更希望先修复一下Clojure STM所抛出的那个错误，所以让我们继续往下看。

在Clojure中创建一个事务是很容易的，只需要用一个dosync调用把代码段包装起来就行了。在结构上，这种做法十分类似于Java中用synchronized修饰代码段的做法，但二者其实还是有不少区别的：

• 如果我们忘记了为需要同步的代码段加上dosync的话，系统会对此予以清晰的警告
• dosync并没有创建任何互斥锁，而是通过将代码段用一个事务包装起来的方式与其他线程进行公平竞争
• 由于并未使用任何显式的锁，所以我们可以无须担心加锁顺序并享受这种不会死锁的并发所带来的好处
• STM提供了一套简单的运行时事务组合锁，所以我们无需在程序设计期间预先考虑诸如“谁用什么顺序锁住了什么”这样的问题
• 不使用显式的锁就意味着程序员无须再使用保守的互斥代码块了（即synchronized代码块——译者注）。于是程序整体的并发度可以得到最大程度的开发，并且其效果只受程序行为和数据访问方式的影响。

当一个事务运行起来之后，如果没有与之冲突的线程/事务，则该事务一定可以完成，并且其所做的更改可以被写到内存中。然而，一旦发现之前启动的其他事务可能会干扰到本事务运行的时候，Clojure就会自动将之前所做的变更进行回滚并重做本事务。在对代码经过下面的修正之后，我们就可以成功地更改balance实体的值了。

(def balance(ref 0))

(println "Balance is "@balance)

(dosync
   (ref-set balance 100))

(println "Balance is now"@balance)

这段代码较之上一版本唯一的变化就是将ref-set用dosync包裹起来。当然，dosync的作用域并不仅仅局限于单条语句，而是可以覆盖整个代码块或同一事务中的多个表达式。下面让我们运行这段代码并观察其结果。

Balance is 0
Balance is now 100

我们知道，balance的状态值（value）“0”是不可变的，而balance本身则是一个可变实体。在dosync作用域内所形成的这个事务中，我们先是创建了一个值100的常量，然后修改balance令其指向这个常量（我们要逐步习惯接受常量的概念）。但此时旧的常量0依然还在，balance也正指向该常量，所以我们需要在新的常量（100）创建完成之后，立即告知Clojure修改balance内部的指针，使其指向该常量。如果后面不再有任何引用指向旧常量“0”，则垃圾回收器会负责将其回收掉。

• Clojure提供了3种改变可变实体的方法，并且所有这三种方法都只能被封装在事务中才能使用：
• ref-set命令可以设置实体的值并在操作完成后返回该值。
• alter命令能够将实体在事务中的值设置成某特定函数的返回值，并在操作完成后返回该值。使用该命令是改变一个可变实体值的最佳方法。

commute命令与alter命令功能类似，二者的主要区别是commute会将提交点（commit point）与事务中所发生的变化分离开来。该命令的主要功能也是将实体在事务中的值设置成某特定函数的返回值，并在操作完成后返回该值。当代码运行至提交点的时候，只有最后一个对实体的变更操作才能最终生效，而中间值都将被忽略。

commute是一个非常好用的命令，尤其是我们遇到类似“谁留到最后谁是赢家”这类应用的时候，其并发度要大大高于alter命令。但在除此之外的大多数情况下，alter都是要比commute更合适的。

除了ref命令簇之外，Clojure还提供了能够同步地更改数据的atom命令簇。与ref命令簇所不同的是，由atom命令簇所作出的变更是不接受调整的，并且同一事务下用atom所做的变更也不能和其他变更组合在一起。究其本质，是因为atom命令簇其实并不属于事务内的操作（我们可以将每个atom变更看作是一个独立的事务）。为了清晰起见，离散的变更最好用atom命令簇，而对于多个需要组合或协调的变更则最好使用ref命令簇。

1.2    STM中的事务

相信你之前一定在数据库中使用过事务，所以对原子性、一致性、隔离性和持久性这些事务的基本属性应该非常熟悉了。Clojure的STM对事务的支持与数据库有所不同，由于STM中的数据是全都放在内存而不是数据库或文件系统里的，所以STM只提供了事务的前三个属性，而缺少了对持久性的支持。

原子性：STM事务是原子的。即我们在一个事务中所做的变更要么对所有其他外部事务可见，要么完全不可见。更具体一些，就是一个事务中所有ref的变更要么都生效，要么都不生效。

一致性：是指事务应该要么执行完成并令外界看到其造成的变化，要么执行失败并使所有相关数据都保持原状。如果有多个事务同时运行，那么从这些事务之外的角度来进行观察，我们可以看到它们所造成的变化始终是一个接着一个发生的，中间不会有任何交叉。例如，在（对同一个账户——译者注）两个独立且并发的存款和取款事务完成之后，账户余额应该是两个操作所产生的累加效果（取钱是对账户加上一个负数——译者注）。

隔离性：本事务无法看到其他事务的局部变更结果，即事务所造成的变更只能在其成功完成后才对外可见。

我们可以看到，这些属性都是侧重于数据的完整性和可见性的。其中，隔离性并不意味着事务之间就不能进行协调了。相反地，STM会密切监控所有事务的进展情况并努力使所有事务都能跑完（除非遇到由应用程序产生的异常）。

Clojure的STM采用了与数据库相似的多版本并发控制技术（MVCC），其并发控制也和数据库中的乐观锁（optimistic locking）很像。当我们启动一个事务的时候，STM会记录一下时间戳，并将事务中将会用到所有ref都拷贝一份。由于状态是不可变的，所以对于ref的拷贝是多快好省的。当对某个不可变状态进行“变更”的时候，我们其实并没有改变它的值（value），而是为其创建了一个含有新值的拷贝。该拷贝是本事务的一个内部状态，并且由于我们使用了持久化的数据结构（见3.6节），这一步也是多快好省的。而如果STM识别出我们操作过的ref已经被别的事务改了的话，它就会中止并重做本事务。当事务成功完成时，所有的变更都会被写入内存，而时间戳也将被更新（见图 6‑1）。

1.3    用STM实现并发

用事务来实现并发自然是极好的，但如果两个事务都试图更改同一实体的话会是什么状况呢？放心，我不会让你等很久的，本节我们将研究几个关于这方面问题的例子。

在进入实例研究之前我有句话要提醒你：由于事务可能被重复执行多次，所以在写代码的时候请务必确保事务是幂等的并且没有任何副作用。这意味着在事务中控制台不能有任何输出、不能打日志、不能发邮件、也不能做任何不可逆操作。如果违背了上述任何一点，我们只能后果自负。一般而言，我们最好是把这些有副作用的操作收拢起来，在事务完成之后再统一执行它们。

在示例代码中，我并没有完全遵循上述警告，所以你将会在代码中看到打印语句。但这纯粹只是为了演示的需要才加进去的，请千万不要在办公室这么写代码！

通过之前的例子，我们已经知道了如何在一个事务中更改balance的值。现在让我们写一个多事务竞争更改balance的程序：

(defn deposit [balance amout])
  (dosync
    (println "Ready to deposit..." amout)
    (let [current-balance @balance]
      (println "simulating delay in deposit...")
      (. Thread sleep 2000)
      (alter balance + amout)
      (println "done with deposit of" amount))))

(defn withdraw [balance amount])
  (dosync
   (println "Ready to withdraw..." amout)
   (let [current-balance @balance]
    (println "simulating delay in withdraw...")
      (. Thread sleep 2000)
      (alter balance - amout)
      (println "done with withdraw of" amount))))

(def balance(ref 100))

(println "Balancel is" @balancel)

(future (deposit balance1 20))
(future (withdraw balance1 10))

(. Thread sleep 10000)

(println "Balancel now is" @balance1)

本例中我们创建了两个事务，分别用于存款和取款。在deposit()函数中，我们先把balance复制了一份，然后插入一个2秒的延时以便模拟事务冲突的环境。在延时结束之后，我们将当前余额与待存入钱数（amount的值）进行累加从而得到存入后的余额。withdraw()函数的实现与deposit()十分类似，唯一区别就是需要用当前余额减去取款金额。这两个方法之后的代码都是用于测试执行结果用的：我们首先将变量balance1的初始值设为100，然后用future()函数分别启动两个独立的线程来执行上述两个函数。下面让我们观察一下程序的输出结果：

Balance1 is 100
Ready to deposit... 20
simulating delay in deposit...
Ready to withdraw...10
simulating delay in withdraw...
done with withdraw of 20
Ready to withdraw...10
simulating delay in withdraw...
done with withdraw of 10
Balancel now is 110

deposit()函数和withdraw()函数都持有一个balance的本地拷贝。当模拟延时结束之后，deposit()事务也随即很快执行完毕，但withdraw()函数就没那么幸运了。因为withdraw()函数从延时中返回之后发现balance的值已经发生了变化，这意味着其本地拷贝已经失效，所以后面的动作再进行下去也没意义了，于是Clojure的STM迅速终止并重做了该事务。事务代码中的打印语句为我们理解STM的运作机制提供了很大的帮助，如果没有那些打印语句，我们就不会注意到这些细节。除了STM运作细节之外，本例中我们最值得注意的地方是在两个事务竞争执行的环境下，balance保持了一致性，其值正确地反映了存取款动作对其造成的影响。

本例中，我们通过读取余额并延迟后续操作执行的方式故意将两个事务置于冲突环境下。但如果把let语句都去掉，我们就会发现两个事务都能在保持一致性的前提下无重做地完成。这一现象向我们充分展示了STM既能保持一致性又可以提供最大程度并发性的能力。

通过上面的例子我们已经知道如何更改一个简单变量，但如果我们有一堆变量时该怎么办呢？Clojure里面的list是不可变的，但我们可以通过一个能改变其实体指向的可变引用来模拟List变更的行为。在这种方式下，我们只是简单地改变了list的视图，list本身则并没有改变。下面就让我们通过一个例子来看一下具体如何运作。我的家庭梦想表单里原本只有一个iPad，现在我想往里面再添加一个新的MacBook Pro（MBP）和一个我儿子想要的新自行车进去，于是我就通过两个线程分别把这两个心愿添加到表单里。下面就是相关的实现代码：

(defn add-item [withlist item])
  (dosyn (alert wishlist conj item))

(def fammily-wishlist (ref '("ipad")))
(def original-wishlist @family-wishlist)

(print "Original wish list is " original-wishlist)

(futrue (addItem family-wishlist "MBP"))
(futrue (addItem family-wishlist "Bike"))

(. Thread sleep 1000)

(print "Original wish list is" original-wishlist)
(print "Update wish list is" @family-wishlist)

addItem()函数的功能是将给定心愿项添加到心愿单里，其中alter方法的功能是用给定的函数（在本例中特指conj()函数）来更改事务内的ref变量。而conj()函数则可以返回一个新的集合，该集合是待加入项与原集合的并集。随后我们在两个不同的线程中调用了addItem()函数，并在最后将结果打印出来。下面就是代码的执行结果：

Original wish list is (iPad)
Original wish list is (iPad)
Update wish list is (Bike MBP iPad)

原始的心愿单是不可变的，所以从代码结尾的输出来看它仍然保持不变。当我们向心愿单添加新项目时，本来是应该将原始心愿单数据复制一份来用的。但是由于采用了持久化的数据结构，我们就可以通过共享心愿项的方式兼顾内存使用与性能，其实现方式如图 6‑2所示。

图 6‑2 向不可变的心愿单中“添加”心愿项

心愿单的状态与originalWishList引用都是不可变的，而familyWishList则是一个可变的引用。所有添加心愿项的请求都是在各自独立的事物中运行的。第一个完成添加的事务更改了familyWishList，使其指向新的心愿单（如图 6‑2中(2)所示）。与此同时，由于心愿单本身是不可变的，所以新的心愿单可以与原始的心愿单共享“iPad”这一项。当第二个添加心愿的事务完成时，新的心愿单同样可以与之前的心愿单共享前两个心愿项（如图 6‑2中(3)所示）。

处理写偏斜异常（write sskew anomaly）

前面我们已经学习了STM是如何处理事务间写冲突的，但有些时候冲突并非如此显而易见。假设我们在某银行有一个支票账户和一个储蓄账户，且银行规定两个账户的最小总余额不得低于$1000，而此时两个账户的余额分别为$500和$600。根据银行的规定可知，我们现在只能从其中一个账户中取$100。如果我们按顺序分别从两个账户取$100，那么第一个请求会成功而第二个请求则会失败。如果两个取款请求是并发执行的，那么由于所谓写偏斜异常的存在，两个事务都能够顺利完成－－两个取款事务看到的总余额都超过了$1000，同时二者更改的又是不同的变量，所以根本不存在写冲突的问题。其造成的结果是，账户总余额最终为$900，低于银行设定的最低限额。下面让我们用代码构建出这种异常，然后再研究如何解决这个问题。

(def  checking-balance (ref 500))

(def  savings-balance (ref 600))

(defn withdraw-account [from balance constraining-balance amout]

  (dosyn

  (let [total-balamce(+@from-balance @constrainning - balance)]

    (. Thread sleep 1000)

    (if (>=(- total -balance  amount ) 1000)

     (alert  from-balance -amout )

     (println "Sorry,can,t withdraw due to constraint violation")))))

(println "checking-balance is" @checking-balance)
(println "savings-balance is" @savings-balance)
(println "Total balance is" (+@checking-balance @savings-balance))

(future (Withdraw-account checking-balance savings-balance 100))
(future (Withdraw-account saving-balance checking-balance 100))

(. Thread sleep 1000)

(println "checking-balance is" @checking-balance)
(println "savings-balance is" @savings-balance)
(println "Total balance is" (+@checking-balance @savings-balance))

代码的前两行是对账户余额进行赋初始值。在withdraw-account()函数中，我们会读取两个账户的余额并将二者相加得到总余额（total-balance）。为了制造事务冲突的环境，我们在计算余额之后会人为地插入一个延时。随后，只要在减去取款金额之后两个账户的总余额不低于银行的最小限额的话，我们就会更新from-balance所代表的那个账户的余额。在余下的代码里，我们并发地执行了两个取款的事务，其中第一个事务从支票账户中取了$100而第二个事务则从储蓄账户中取了$100。正如我们在程序的输出结果中所看到的那样，由于两个事务是分别独立执行且二者没有任何交集，所以它们无法意识到彼此已经陷入到写偏斜并使最终结果违反了银行的规定。

checking-balance is 500
savings-balance is 600
Total balance is 1100
checking-balance is 400
savings-balance is 500
Total balance is 900

在Clojure中，我们可以通过ensure()函数很容易地避免写偏斜问题。通过该方法，我们可以告诉事务要睁大眼睛盯着某个本事务只读不改的变量。这样一来，STM就可以确保只有在我们盯着的这个变量没有在本事务外被修改的情况下，本事务的写操作才能被提交；或者一旦盯着的那个变量有改变，则STM要重做本事务。

根据上述思路，让我们修改一下withdraw-account()函数：

(defn withdraw-account [from-balance constrainting-balance amount]
  (dosync
    (let [total-balace (+ @from-balance (ensure constrainting-balance ))]
    (. Thread sleep 1000)
    (if (>= (-total-balace -amount))
    (println "Sorry,can't withdraw due to constraint violation")))))

在代码第3行，我们调用ensure()函数来监控constraining-balance这个本事务只读不改的变量的值。事实上，STM在这行代码中对constraining-balance变量加了一个读锁，其目的是为了阻止其他事务获得该变量的写锁。在本事务临近结束的时候，STM会在执行提交动作之前释放所有的读锁，这样就可以在并发度增加的时候避免死锁的发生。

正如我们在下面输出结果中所看到的那样，即使我们像刚才一样并发执行两个取款事务，但由于我们在withdraw-account()函数里调用了ensure()，所以银行对两个帐户的最小总余额限制仍然能够得以保持。

checking-balance is 500
savings-balance is 600
Total balance is 1100
checking-balance is 400
savings-balance is 500
Total balance is 1000
Sorry,can't withdraw due to constraint violation

STM的显式锁无关执行模型是相当强大的。如果事务间没有冲突，那就不会有任何阻塞发生。而一旦存在冲突，则至少有一个事务可以无障碍地执行下去，而其他竞争者则需要重做。对于需要重做的事务，Clojure设定了一个最大重做次数，并能够保证两个线程不会因为重做节奏相同而导致反复冲突重做。当我们的业务模型是读多、写冲突非常少的情况时，STM的执行模型就更能体现其优势。例如，该模型非常适合于传统的网络应用——通常情况是，多个用户并发地更新他们各自的数据，用户之间的共享状态冲突非常少，而这些少量的写冲突则可以通过STM来轻松处理掉。

由于能够解决如此多令人头痛的并发问题，Clojure的STM可以称得上是并发编程世界里的阿司匹林了。如果忘了创建事务，我们就会被系统严厉地斥责（指抛异常——译者注）。而与之相反的是，只需简单地把dosync放到正确的位置上，系统就能够回馈给我们多线程环境下的高并发和一致性。如此低的使用门槛，简洁、明确以及可预测的行为都使得Clojure STM成为我们开发并发应用时一个非常值得认真考虑的选择。