存储引擎数据结构优化(2):io bound

经常看到些引擎与别的引擎进行性能对比，测试数据只有100万，然后就得出我的引擎比别的引擎性能要高的结论（我也曾经干过）。
其实这个测试结果意义不大，只能说明在100万这个数据规模，你的引擎性能领先。

100万记录，key 16bytes, values 100bytes，共 100,0000 * (116)Bytes ~110MB。
如果用的buffered-io，测试的基本是引擎的cpu-bound，很少或基本没有触及到后端的disk io。
一个合理的测试，应该是把引擎cache开小点，然后持续压几亿甚至几十亿条数据，结合着它的io行为一起看。如果在这样的条件下，性能一直领先，那说明这个引擎确实不错。

如果引擎A干完一个活需要10次io，而引擎B干完同样的活需要250次io，可简单认为引擎A对io是友好的，本文就谈下针对io-bound的优化，如何设计数据结构，干同样的活，花更少的io。

一个“二维”的tree(索引结构)落在磁盘上的时候，就变成了个“一维”文件。
假设经过多次添加删除等操作后，一个索引tree(这里二叉树是个示例，真正的索引不是这样的结构，fanout要大)如下：
    /*
     *
     * (key-6)
     * / \
     * (key-4) (key-8)
     * / \ / \
     * (key-3) (key-5) (key-7) (key-9)
     *
     *
     */

它在磁盘上的“一维”文件结构是：
    /*
     *
     * | … |(key-6)|(key-3)| … |(key-4)| … |(key-8)|(key-7)| … |(key-5)|
     *
     */
可以看出，节点(key-6)的两个子节点(key-4)和(key-8)分散在文件的两个相对较“遥远”的地方。
如果一条root-to-leaf是：(key-6) → (key-4) → (key-5)
我们需要：
1) 第1次io ,读出(key-6)
2) 第2次io，读出(key-4)
3) 第3次io，读出(key-5)
这条路径耗费的总io数是3。

而另一条root-to-leaf是:（key-6) → (key-8) → (key-7)
则需要：
1)第1次io，读出(key-6)
2)第2次io，读出(key-8)，而紧邻着(key-7)，所以，被prefetching了。
这条路径耗费的总io数则是2。

所以，如果一个节点的周边节点能在文件中紧邻的被存储，当读取其中一个的时候，其他节点被prefetching出来，io数则可以减少。这就是vEB layout:

                
                
vEB layout就是数据要“扎堆”存储，一次顺序读取，能取到更多、更有用(父子关系节点)的数据。
那么，一次顺序读取多大才合适呢？
这个问题可转化为：
一次顺序读取xMB延迟时间 <= 一次随机io延迟时间

如果一个磁盘：disk seek time 10ms；disk bandwidth 150MB/s
x / 150MB/s <= 10ms ，x~ 1.5MB
也就是顺序读超过1.5MB的数据，其延迟基本跟一次随机io相当，所以一次读取的block不应超过1.5MB。

在顺序读取1.5MB的情况下，再看下这个root-to-leaf:（key-6) → (key-8) → (key-7)
这时的3个节点可能都落在这个1.5MB block内，所以只用了1次随机io。io数又进一步减少。

这与cpu的cache-line很相似，这个1.5MB就是个block-line，针对io-bound的优化，就是使数据尽量落在一个block-line里(vEB layout)，以减少io数。
其实只要涉及到跨“层级”的，cpu-->memory或memory-->disk，都可以使用这个方法来作优化。

但是目前针对io-bound的优化，是无法改变算法复杂度的: O(logB(N))，都是常数项的优化：O(logB(N)) / b，不过这威力已经很大。