B树,LSM树, Fractal树和TokuDB中的COLA树

  |   0 评论   |   1,111 浏览

B树


B-树的数据量和吞吐的关系

Image title

一句话概括

  • B树适合于查询多,插入少的情形。


适用场景

  • 数据量超过内存限制
  • 查询性能要求高
  • 读比写重要

不适用场景

  • 接收事件日志
  • 存储传感器日志
  • 追踪用户点击

提高B树性能的方法

  • 增大内存
  • 换用更快的存储



我们来看看其它的数据结论。下图是理论上的吞吐性能示意图。

Image title



B树对于顺序写入性能是非常好的,但是对于随机写入,由于有节点的分裂操作,会造成很大的磁盘IO。


因此LSM树和Fractal树的优化点均在于,减少待写入数据项的随机性,顺便也提高了压缩比,稳定了IO的写入波动,尤其适用于falsh/SSD磁盘。


LSM树


LSM树最早出现在1996年的Google的BigTables中,随后Cassandra, LevelDB, HBase, bdb Java edition, RocksDB也实现了LSM树。其主要原理为:

  1. 将数据变动存在缓存buffer中(即memtable)
  2. 缓存buffer满了时,排序数据,写入存储

如图示


Image title


缺点

很明显其缺点为,在写入磁盘的SST文件中,每一个SST文件都是有序的,但是没有全局顺序。同样的key,可以存在于多个SST文件中。


这导致查询单独的SST文件很快,但是查询全局顺序会很慢。


查询优化方式


不同产商的处理方式有

  • 文件归并:将多个文件合并成一个
  • 文件区间:文件之间是分区间的,避免一个key存在于多个文件中(比如文件1:A-G,文件2:H-M,文件3:O-Z)
  • Bloom过滤器:提高key查询速度,但是对于范围查询没有帮助



Fractal树


Fractal树有着与B树类似的结构,但是对于B树的改动是有缓存buffer的。当buffer满了时,才会把改动推到树中。


Image title



优点:

合并了多个随机写操作,为一个事务操作。


缺点:

buffer中有着大量的message信息,导致查询时必须遍历所有的message信息,这点尤其对于单key的查询操作是非常不利的。

对于unique key和无序的primary key的查询操作,会严重影响性能。


适用场景:

  • 数据库中有大量的表和索引(尤其是非unique索引)
  • 写多
  • 存储IO慢
  • 存储空间贵




Tokutek的Fractal树


这个方法是有专利的[2],通过提高CPU使用率来降低磁盘IO,来达到更高的批量插入吞吐。


原理


数据结构:相邻行空间加倍,每一行要么全满要么全空,全满行的数据都是排好序的。如下图所示



如果插入3和11后,则



磁盘IO性能

合并


如果合并操作涉及x个数据点,每个block大小为B,则一共需要O(X/B)次IO,平均每个数据点为O(1/B),最坏情况为O(N/B)。如果数据总数为N,由于一个数据最多被合并logN次,所以总时长为O(logN/B)。


另外一种改善插入最环情况的方法是:对每个level复制一个同样大小的辅助数组(如下图的两行一组的结构),所有被插入的数据先放入原空间,如果原空间满了则放入这个新建空间。


下图中显示插入了数字31的的合并情况


论文[4]中推导中,对于k个level的数据库来说,每次merge的时候只要从低到高移动2k+2的数据项,就能保证相邻的两个level不会同时出现满员的情况


即对于一个数量为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在每个数据上做了一个指针,指向下一行中第一个比它大的数据的位置(即Fractional Cascading)。



由于高度为LogB(N) ,则磁盘访问次数为logB(N);与B-Tree相比,由于B树高度为logB(N),磁盘访问次数为logB(N),两者是一样的。


优点

  • TokuDB数据随机插入(比InnoDB)快20-80倍,顺序插入慢3.5倍
  • TokuDB进行了压缩


缺点

  • update没有InnoDB快
  • 限制记录不能太大,不适合存储blob


附记:

TokuTek的工程师将MongoDB的底层存储引擎换为了TokuDB的存储引擎,效果非常明显,见下图[5]


测试环境:


  • HP Proliant DL380 G6, (2) Xeon 5520, 16GB RAM, P410i (512MB, write-back), 8x10K SAS/RAID 0
  • Centos 5.8 (64-bit), XFS file system
  • MongoDB v2.2.3 and MongoDB v2.2.0 + Fractal Tree Indexes



详细内容请看下面的原文:

1. How Three Fundamental Data Structures Impact Storage and Retrieval

2. Tokutek’s Fractal Tree Indexes

3. [转]TokuDB中的COLA-Tree和TokuMax中的Fractal tree(分形树)

4. http://www.cs.sunysb.edu/~bender/newpub/BenderFaFi07.pdf

5. https://www.percona.com/blog/2013/06/06/iibench-benchmark-tokumx-vs-mongodb/

6. [转]TokuMX - 拥有一身MongoDB的外表和一颗TokuDB的心

7. B+树 LSM 树 COLA树 原理及在海量存储中的应用

评论

发表评论

validate