海量存储系列之九

终于来到了COLA树系，这套东西目前来看呢，确实不如LSM火，不过作为可选方案，也是个值得了解的尝试，不过这块因为只有一组MIT的人搞了个东西出来，所以其实真正的方案也语焉不详的。从性能来说，tokuDB的写入性能很高，但更新似乎不是很给力，查询较好，占用较少的内存。

http://www.mysqlperformanceblog.com/2009/04/28/detailed-review-of-tokutek-storage-engine/

这里有一些性能上的指标和分析性文字。确实看起来很心动，不过这东西只适合磁盘结构，到了SSD似乎就挂了。原因不详，因为没有实际的看过他们的代码，所以一切都是推测，如果有问题，请告知我。

先说原理，上ppt http://tokutek.com/presentations/bender-Scalperf-9-09.pdf，简单来说，就是一帮MIT的小子们，分析了一下为什么磁盘写性能这么慢，读的性能也这么慢，然后一拍脑袋，说：“哎呀，我知道了，对于两级的存储（比如磁盘对应内存，或内存对于缓存，有两个属性是会对整个查询和写入造成影响的，一个是容量空间小但速度更快的存储的size，另外一个则是一次传输的block的size.而我们要做的事情，就是尽可能让每次的操作传输尽可能少的数据块。

传输的越少，那么查询的性能就越好。

进而，有人提出了更多种的解决方案。

•B-tree [Bayer, McCreight 72]
• cache-oblivious B-tree [Bender, Demaine, Farach-Colton 00]
• buffer tree [Arge 95]
• buffered-repositorytree[Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook 00]
• Bε
• tree[Brodal, Fagerberg 03]
• log-structured merge tree [O’Neil, Cheng, Gawlick, O’Neil 96]
• string B-tree [Ferragina, Grossi 99]

这些结构都是用于解决这样一个问题，在磁盘上能够创建动态的有序查询结构。

在今天，主要想介绍的就是COLA，所谓cache-oblivious 就是说，他不需要知道具体的内存大小和一个块的大小，或者说，无论内存多大，块有多大，都可以使用同一套逻辑进行处理，这无疑是具有优势的，因为内存大小虽然可以知道，但内存是随时可能被临时的占用去做其他事情的，这时候，CO就非常有用了。

其他我就不多说了，看一下细节吧~再说这个我自己都快绕进去了。

众所周知的，磁盘需要的是顺序写入，下一个问题就是，怎么能够保证数据的顺序写。

我们假定有这样一个空的数据集合

 
可以认为树的高度是log2N。

每行要么就是空的，要么就是满的，每行数据都是排序后的数据。

如果再写一个值的时候，会写在第一行，比如写了3。

再写一个值11的时候，因为第一行已经写满了，所以将3取出来，和11做排序，尝试写第二行。又因为第二行也满了，所以将第二行的5和10也取出，对3,11,5,10 进行排序。写入第四行   

这就是COLA的写入过程。

可以很清楚的看出，COLA的核心其实和LSM类似，每次“将数据从上一层取出，与外部数据进行归并排序后写入新的array”的这个操作，对sas磁盘非常友好。因此，写入性能就会有非常大的提升。

并且因为数据结构简单，没有维持太多额外的指针，所以相对的比较节省空间。

但这样查询会需要针对每个array都进行一次二分查找。

性能似乎还不是很高，所以，他们想到了下面这种方式，把它的命名为fractal tree,分形树。

用更简单的方法来说的话呢，就是在merge的时候，上层持有下层数据的一个额外的指针。

来协助进行二分查找。

这样，利用空间换时间，他的查询速度就又回到了log2N这个级别了。

到此，又一个有序结构被我囫囵吞枣了。

嘿嘿

在下一篇，我们将进入大家期待的分布式k-V场景，也就是noSQL的范畴了，让我们拨开nosql的神秘面纱，看看这东西到底意味着什么。