#研究消除随机写的手段

1. 记录级的缓存

  1. 在记录的级别，应用的访问模式通常符合Zipf分布，其中10％的记录所占的访问概率超过90％。如果我们用记录级的缓存，用相当于数据量10％的内存，就可以消除90％的IO，但用页级缓存，这10％的热点记录，很可能就分布在70％的页面上，这样同样10％的内存，很可能只能消除可悲的30％的IO。

    2. Memcached+数据库

  2. 如果仅仅如果更新命中了记录缓存中的记录，则只更新记录缓存，不更新底层的堆等存储。具体细化下来有UPDATE和DELETE两种，NTSE暂时只能搞定UPDATE；
  3. 记录缓存里的东西，总是要有周期的持久化的，否则恢复时间不能保证。这个第三招，就是持久化也就是把记录缓存中的脏记录dump出去的时候，不要去更新对应的堆中的记录，否则短时间就会爆发大规模的随机读写，做法应该是像内存数据库那样，把脏记录用顺序写IO dump出来。NTSE就是这么做的，刷记录缓存脏记录时，我们先看看对应的页面在页面缓存中在不在，在，则更新堆，否则顺序dump到log中。
  4. 在更新时，可以只把UPDATE后的后像插入到记录缓存中，根本不去读原来的记录，当然这个要看具体情况，如果后像是依赖于前像的那这招就不灵，但很多时候是可以用的，比如根据主键找到一条记录，不管3721把其中一些属性改掉。NTSE暂时还搞不定这招，有待改进。

    3. 索引随机IO解决方案:

  5. B+树: 搜索、插入和删除理论上复杂度为O(log(B)(N))次IO, 如果非叶子节点都在内存中, 则是一次随机IO.
  6. LSM-Tree: 主要针对写远多与读的场景, 将索引数据写入内存和log, 定期批量写入磁盘. 采用分级索引块批量更新的方式将随机写IO的开销降低到log(N)/B.
    这样随机写变为了连续写,但是读需要读内存和多个索引文件, 然后merge,开销比较大, 一般采用BloomFilter来过滤随机读,以减少不必要的随机读.
    现在HBase,Cassandra都采用这种方式.
  7. Fractal Tree(分形树TokuDB): 结构上也是多级索引块,从小到大, 随机写性能和LSM-Tree一样. 随机读采用了Fractional Cascading.
    Facebook上有一遍对FC的介绍: http://www.facebook.com/pages/Fractional-cascading/145152932165841
    FC简单点说,就是给每个分级索引块中的每个索引元素加上2个指针,一个指向它前面一个索引块中最小比它大的索引元素,一个指向它后面一个索引块中最小比它大的索引元素.
    据说Range Tree+FC的搜索性能已经逼近了B+树. (题外话, HBase什么时候也考虑考虑引进FC呀.)

    4. 随机IO优化总结:

  8. 采用SSD固态硬盘替换传统机械硬盘,可以大大的提高IOPS.
  9. 采用记录级缓存可以大大缓解随机读的压力.
  10. 采用数据库内置记录缓存可以缓解随机IO读写问题.
  11. 采用LSM-Tree和Fractal Tree可以很好的解决索引的随机插入和删除问题.
  12. 采用Bloom Filter可以消除绝大部分不必要的随机读
  13. 采用Fractional Cascading算法, 可以很大程度提升Range Tree的搜索性能.