从Clojure的源码学习STM对引用变量的版本控制原理

原创
2015/08/23 01:25
阅读数 4.5K

《Clojure编程乐趣》这本书看到 11.2.5 压力之下的Ref 的时候,对其中的history的机制和作用完全无法理解。文中只是简单地提到当“执行缓慢的事务”和“执行快速的事务”同时用到同一个Ref,执行效率就会非常的差,而通过增大max-history选项就能缓解这种问题。

关键是 谁能告诉我这是为毛?!?!?!书上没有更多的介绍,求助于Google也没有得到任何有帮助的信息,STM 作为 Clojure 并发的核心,相关书籍基本都没提原理性的东西,例如:什么时候视为脏读、什么时候需要重做事务、事务中引用变量的值如何确定,网络上也甚少讨论这个问题。只好自己硬着头皮看源码,终于摸清楚它背后的原理。

主要相关的是这两个类:clojure.lang.Refclojure.ref.LockingTransaction。经研究它们的工作原理如下:

  1. 事务类维护着一个全局唯一的长整型原子类lastPoint,当事务开始和结束(进出dosync块)时就会自增,作为当前事务的起始位置(Read Point)和提交位置(Commit Point)。
  2. Ref 类采用链表形式的“双端循环队列”保存历史值,因此ref-history-count函数的执行效率是O(n)。引用被创建时可指定min-historymax-history两个属性,其中max-history是队列最大容量,默认值为10min-history的作用下文介绍,默认值为0。初始时队列为空。
  3. Ref 历史队列中的对象Ref.TVal保存值valObject型)和最后更新的位置pointLong型)。
  4. 读取Ref的值时,历史队列从后往前遍历,找到第一个最后更新时间在当前事务启动之前的变量,即变量的point小于当前事务的Read Point
    1. 如果值存在,则返回它的值
    2. 如果不存在,“变量读取失败”计数加一,抛出异常,重做整个事务
  5. 如果事务执行一切顺利,结束时保存更新过的Ref.TVal
    1. 如果(之前发生过#4.2读取错误,并且队列大小 < max-history)或者 队列大小 < min-history,就追加当前值到队尾、队列长度加一、清空错误。
    2. 否则,保持队列长度不变,用当前值覆盖队列的顶端(最久的值)。
  6. 每个事务最多重试10000次,所以Clojure的事务也不是“完全可靠”的,当失败次数太多就会抛RuntimeException

以上就是ClojureSTMRef的历史版本控制机制,它实现的目标是:引用变量的版本在事务整个生命周期里都存在于历史队列中。

上述规则还是太凌乱,直接看代码例子:

(defn fork [f]
  (.start (Thread. f)))

(def a (ref 0))

(fork
 #(dosync
   (println "run1" @a (ref-history-count a))
   (Thread/sleep 1000)
   (println "get1" @a (ref-history-count a))))

(fork
 (dotimes [i 4]
   (dosync
    (Thread/sleep 600)
    (alter a inc))))

执行的结果如下,即第一个事务一共运行了3次,最后历史队列长度为2(不包含当前变量的值)

run1 0 0
run1 1 0
run1 3 1
get1 3 2

这段代码一共涉及5个事务,按照时间先后顺序看每个事务的执行过程:

  1. [0.0] Read Point = 1:事务1启动,输出“run1 0 0”,进入沉睡 # 队列:[{value: 0, point: 0}]

  2. [0.0] Read Point = 2:事务2启动,进入沉睡 # 队列:[{value: 0, point: 0}]

  3. [0.6] Commit Point = 3:事务2成功修改变量@a1 # 队列:[{value: 1, point: 3}]

  4. [0.6] Read Point = 4:事务3启动,进入沉睡 # 队列:[{value: 1, point: 3}]

  5. [1.0] 事务1读取@a,但是Read Point(1)小于3,即事务在中间过程中变量被更新了,因此读取失败,重新启动 # 队列:[{value: 1, point: 3}]

  6. [1.0] Read Point = 5:事务1重启,输出“run1 1 0” # 队列:[{value: 1, point: 3}]

  7. [1.2] Commit Point = 6:事务3修改变量@a2,因为#5发生读取失败,因此当前值追加到历史队列,而不是覆盖 # 队列:[{value: 1, point: 3}, {value: 2, point: 6}]

  8. [1.2] Read Point = 7:事务4启动,进入沉睡 # 队列:[{value: 1, point: 3}, {value: 2, point: 6}]

  9. [1.8] Commit Point = 8:事务4修改变量为@a3 # 队列:[{value: 2, point: 6}, {value: 3, point: 8}]

  10. [1.8] Read Point = 9:事务5启动,进入沉睡 # 队列:[{value: 2, point: 6}, {value: 3, point: 8}]

  11. [2.0] 事务1读取@a,但是Read Point(5)小于最小的point(6),因此读取失败,重新启动 # 队列:[{value: 2, point: 6}, {value: 3, point: 8}]

  12. [2.0] Read Point = 10:事务1重启,输出“run1 3 1” # 队列:[{value: 2, point: 6}, {value: 3, point: 8}]

  13. [2.4] Commit Point = 11:事务5修改变量为@a4,因为#11发生读取失败,因此当前值追加到历史队列,而不是覆盖 # 队列:[{value: 2, point: 6}, {value: 3, point: 8}, {value: 4, point: 11}]

  14. [3.0] Commit Point = 12:事务1读取变量@a,队列中第一个point小于当前Read Point(10)的版本是{value: 3, point: 8},因此输出结果“get1 3 2”

在理解了上述执行过程后,终于明白为什么“慢事务”和“快事务”同时执行时会影响性能:

按照书上的例子:慢事务每200毫秒尝试读取@r;快事务每10毫秒更新r的值。假设这两个事务同时启动,意味着慢事务在读取@r之前,变量的值已经被更新过约200 / 10 = 20次。所以,除非历史列表的容量够大,至少能保存变量20个历史版本的值,否则慢事务将永远会读取失败,知道所有的快事务都执行完毕。因此,在默认情况下(历史列表只能容纳10个版本),这两个事务的执行过程退化成了“串行”执行,慢事务永远在快事务执行完毕后才执行。

解决方法就是讲max-history的值设置为大于20的值。总结refmin-historymax-history属性的作用:

  1. 当队列长度在 [0, min-history) 时,中间计算结果总会放入队列中;
  2. 当队列长度在 [min-history, max-history) 时,仅发生读取失败时才把计算结果放入队列中
  3. 当队列长度在 [max-history, ) 时,仅发生读取失败时才把计算结果覆盖队列中最早的值

因此,如果把 max-history 设置为0,则所有引用相同变量的过程都将变成串行执行!但由于队列查找和统计的开销都是O(n),如果max-history设太大同样有性能问题。

展开阅读全文
加载中
点击加入讨论🔥(2) 发布并加入讨论🔥
打赏
2 评论
10 收藏
1
分享
返回顶部
顶部