0%

CKDTree (2)

Basic Idea

这里使用的方法是Trevor Brown的non-blocking binary search tree的实现里面提到的,并没有在论文里说明。

基本思想非常简单,

  1. 读取并保存所有node;
  2. 接着检查已保存的node与当前tree里的node是否都一样,发现不一样的,重新snapshot;
  3. 基于已保存的node,构建一棵新的tree,返回snapshot。

这里的snapshot和上一篇中的就有很大不同。上一篇的snapshot基本上可以算作是在调用snapshot()的时候,tree的状态(特殊情况下需要retry);而这里的必须保证,从第1步完成读取的时刻起,到第2步检查结束,都没有update发生,才能返回snapshot。

要注意的是,在第1和2步中,需要保存和检查所有的node(internal node和leaf)。这不同于使用GCAS的snapshot,只update internal node,在某些时刻,某些leaf实际上是共享的。

size in Snapshot

References

  1. http://www.cs.utoronto.ca/~tabrown/ksts/StaticDictionary5.java, Trevor Brown