本文由Yurii原创,转载请注明来源: Life Sailor

本文链接 翻译文档:TokuMX的分形索引是什么?


本文翻译自 TokuMX Fractal Tree(R) indexes, what are they?

TokuMX的一大创新在于,它打破了一条长久存在的关于数据库的规则:要保证好的写入性能,索引的工作集应当能够放在内存里。标准答案是这样的:如果索引的工作集比内存要大,写入就需要执行I/O,I/O就会成为限制因素,性能就会下降。所以,要么让索引小到能全部放进内存,要么提供一种索引写入模式,避免工作集过大,比如MongoDB所采用的,内存中只为最近插入的数据保存索引。

但对TokuMX来说,这是绝对不成立的。依靠TokuMX所提供的创新性的分形树索引,索引的工作集可以比内存更大,同时写入性能不受影响。分形树索引为什么在重度写入(无论是MongoDB还是MySQL)的评测中能表现优异,原因就在这里。

其他数据库仍在苦苦挣扎时,TokuMX是如何提供这种写入性能的?做法就是将众多数据库(MongoDB, MySQL, BerkelyDB等等)使用的主要存储结构——B树索引,替换成为写入优化的数据结构——分形树索引。

“为写入优化的数据结构”意味着什么?

为了解这一点,首先你需要理解,为什么B树索引在索引超出内存限制时的表现会变差?下面是B树的图。

B树是种简单(同时美观)的数据结构。在B树中,内部节点存储支点(Pivot)及指针,叶子节点存储全部真正的数据。在B树上插入时,需要找到数据对应叶子节点,再将数据写入。如果所有节点都在内存里,这样做的速度是很快的。但是如果大部分数据不在内存里(在上图中,只有内部节点和极少数叶子节点在内存里),检索叶子节点就需要执行I/O操作。其实,基本上所有的插入都会执行I/O操作。I/O的瓶颈就从这里来。写入性能下降的根源就在这里。如果硬盘每秒可以执行数百次I/O操作,那么B树充其量也只能执行这么几百次写入操作。所以MongoDB和MySQL会在iiBench测试中败下阵来,自然而然地,用户会被告知“应当把索引的工作集保存在内存里”。

那么,分形树索引的速度为什么会快很多?简单说,它大量减少了I/O操作。下面解释原因。

分形树索引和B树索引的主要差别,解释了在内部节点中的写入性能差别。

  • 使用B树时,内部节点只保存支点和指向各子节点的指针。
  • 使用分形树索引时,内部节点保存支点、指针,以及各子节点的缓冲区

请注意,在上图中,每个内部节点中都有其子节点对应的缓冲区(灰色)。

依靠缓冲,写操作可以累积起来批量执行,所以整个过程是这样的:

  • 从根节点出发,找到应当向下开始遍历的那个子节点
  • 将待定(pending)的写操作加入缓冲区
  • 如果该子节点对应的缓冲去还有空间,返回。否则,将待定的写操作到下一层节点的缓冲区中,腾出空间用于未来的写入。

在根节点执行刷缓冲区,可能导致一系列的缓冲区刷新。也就是说,在根节点刷缓冲区可能将大量数据刷向其子节点,结果子节点的缓冲区也满了,于是它们也需要刷缓冲区。这种情况会持续发生,最终刷到叶子节点为止。

这种算法为什么会提供如此好的性能呢?简单说是减少了I/O(真的,关键就在I/O)。I/O的代价日益高昂,如果要执行I/O操作,总得有对应的回报来合算。如果使用B树索引,每插入一小篇文档,或者一行数据,或者一个键值对,就需要执行一次I/O。如果使用分形树索引,可以假设根节点是常驻内存的,所以我们知道,如果在某次写入时引发了了I/O操作,其实是写入了一整个缓冲区的数据。这可能包含很多文档(或者很多行,很多键值对…)。因为每个I/O操作其实归拢了很多写入,所以分形树索引大大减少了I/O操作的数量,也就解除了B树索引中的I/O瓶颈。

因为I/O的减少,分形树索引不会要求索引必须小于内存。即使超过内存的限制,TokuMX依然可以维持很高的写入性能。

关于这种算法,还有一点也值得一提,如果数据都存在内存里,在写入性能上,分形树索引相对B树索引并没有算法上的优势。如果内存足够大,从算法来分析,B树和分形树都很快。