Yang Suli的Blog: Some Cache Oblivious Database

1. TokuDB:
paper here: "Cache Oblivious Streamng B-trees"
  http://www.cs.sunysb.edu/~bender/newpub/BenderFaFi07.pdf
Some description in the bottom.

TokuDB is good for bulk insertion, then bulk look-up. It is not so good for a mix of insertion and look-up. This could be potentially alleviated by adding a bloom-filter on top of their B-tree to do search. But they didn't implement it.

2. Acunu's Castle project
  http://www.acunu.com/2/post/2011/07/castle-behind-the-scenes-with-acunus-new-storage-engine.html
They have bloom-filter built in.
They have the whole thing built in kernel, and have a ring for user space application to put/get key/values.
They also batch system calls into the kernel to reduce overhead.
  They seem to use "doubling arrays" as the key data structure, but it seems very similar to TokuDB's fractal trees. If so, they might have the same downsides too; good for large number of updates/writes followed by a large number of lookups/reads ; bad for a mix of updates and reads.

数据库索引原理（1）-----TokuDB中的COLA-Tree/Cache-Oblivious Lookahead Array（Fractal Tree）

目前无论是商业的SQL Server，还是开源的MySQL，都基本上还在用比较老的B+Tree（SQL Server用的是标准的B-Tree）的索引结构。从原理来说，B系列树在查询过程中应该是不会慢的，而主要问题就是出现在插入。B-Tree在插入的时候，如果是最后一个node，那么速度非常快，因为是顺序写。但如果数据插入比较无序的时候，比如先插入5然后10000然后3然后800这样跨度很大的数据的时候，就需要先“找到这个数据应该被插入的位置”，然后插入数据。这个查找到位置的过程，如果非常离散，那么就意味着每次查找的时候，他的子叶节点都不在内存中，这时候就必须使用磁盘寻道时间来进行查找了。更新基本与插入是相同的。如果是一个运行时间很长的B-Tree，那么几乎所有的请求，都是随机IO。以上就是B-Tree在磁盘结构中最大的问题了。

随机IO几乎是令所有DBA谈虎色变的一个问题，当数据量小的时候，所有数据都能一下放到内存中那么就没有这个问题（其实这个时候也就没有必要用B-Tree的这种块结构了），但是一旦数据量大于内存的话这个问题就陡然出现了。其实从本质来说，k-v存储要解决的问题就是这么一个：尽可能快得写入，以及尽可能快的读取。

在分析解决方法之前，我们讨论几个极端。走一个极端的话，如果我每次写数据都顺序写，那么对Insert来说的话是最快的，但是每次Query就没法读了，因为我每次都需要Scan一遍整个表。那么如果我想获取最佳的读性能，那么方法就是像B-Tree那样全部排个序呗。但是因为B-Tree有那样的随机IO，这样我们有没有办法得到顺序写的写性能，有同时达到B-Tree的读性能呢？目前的方法主要有两种，一种是LMS-Tree（我将会在后面的博客中再做介绍，如果您实在等不及请见July大牛的博文），另一种是COLA Tree。下面介绍的就是TokuDB中采用的COLA-Tree。

一、原理

我们假设有这样一种集合的结构，相邻行空间加倍。每一行要么全满要么全空，全满行的数据都是排好序的。

数据插入的时候，以上图的数据存储状态为例，如果再写一个值的时候，会写在第一行，比如写了3，这个时候第一行是空的，所以就放到第一行。再写一个值11的时候，因为第一行已经写满了，所以将3取出来，和11做排序，尝试写第二行。又因为第二行也满了，所以将第二行的5和10也取出，对3,11,5,10进行排序。写入第三行。最后的结果就是：

二、磁盘IO访问的性能

分析一下磁盘IO量。合并两行数据总数为X一共需要O(X/B)次IO（B是磁盘的一个block的大小），平摊到每个数据上只要O(1/B)次。如果数据总数为N，那么一个数据最多只可能merge logN次，所以做一次插入的cost只要O(logN / B)。对比使用B-Tree作为索引的话，由于B-tree高度为LogB(N)，对于磁盘IO来说，访问磁盘的次数为logB(N) = logN/logB，对于数据的query来说访问磁盘的次数是一样的。

这是TokuDB做的分析，其实我觉得这个分析有点牵强，我觉得这有点欺负B-Tree只能单个数据单个数据的插入，对于大量数据的同时插入没有优势。如果CacheOblivious Tree也是单个的插入，那么单个插入访问IO的最坏情况是O(N/B)?

翻阅原论文，原论文中承认了单个插入访问IO的最坏情况是O(N/B)，但这个论文里提出了方法将最坏的这个情况改善了，主要方法是对每个level复制一个同样大小的辅助数组（如下图的两行一组的结构），所有被插入的数据先放入原空间，如果原空间满了则放入这个新建空间（如果新建空间同时也满了则是算法设计失败）。Insert的时候由一个线程完成，对于要插入一个数据的情况，这时把要Insert的数据放入Level-0的空间中（如果原数组空间为空则放入原数组空间，若满则放入辅助数组，如果辅助数组满则是算法设计的失败）；另外一个线程进行merge，merge的时候按下图的结构从左到右进行，把全满的一对level空间合并排序到下一个level存放（下一个level的原数组空间为空则放入原数组空间，若满则放入辅助数组，如果辅助数组满则是算法设计的失败）。每一次merge的结束有两个标志，其中之一是所有需要merge的level对全部merge完，其二就是merge过程一共移动了m个数据。那么m的取值是多少呢？应该满足两个原则，其一是需要保证每次merge不能使得相邻两个level同时出现全满的情况；其二就是m的取值应该尽可能的小（很显然插入的最坏情况下的时间复杂度是O(m)的）。这些牛逼的作者们推出了这么一个定理：对于k个level的数据库来说，每次merge的时候只要从低到高移动2k+2的数据项，就能保证相邻的两个level不会同时出现满员的情况（这个证明过程说实话我没有看的太懂，希望懂的各位能够指导我理解一下，谢谢各位！论文在此的第9页的LEMMA-21）。这样对于一个数量为N的数据库来说，level层数为log(N)，那么每次merge要移动的数据量为2log(N)+2，即IO次数只要（2log(N)+2）/B，即O(log(N)/B)。于是这个最坏情况的IO就神奇地从O(N/B)降到了O(log(N)/B)。

看看查询的性能。为了提高查找的性能，TokuDB在每个数据上加了一个forwardpointer，指向下一行中第一个比它大的数据的位置(这个叫做Fractional Cascading)。平均地看，上一级的每个数都把下一级搜索范围限制到了常数个，所以磁盘IO的次数最差应该为O(logN)，好像这个没有问题。