CKDTree (2)

Posted on Edited on In Disqus:
这篇记录了另一种简单的方法来实现concurrent KDTree snapshot，当然简单是有代价的，那就是在snapshot的时候不允许并发的update（inset，delete）。

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