TerarkDB – 我们发布了一款划时代的存储引擎

2016年7月12日 | By News | Filed in: 未分类.

Source: http://zhuanlan.zhihu.com/p/21493877?utm_campaign=rss&utm_medium=rss&utm_source=rss&utm_content=title

目前世界上绝大多数开源数据库的索引都是由 B+树 或 LSM 实现的,但是 Terark 实现了一种完全不同的索引结构(Succinct Trie),可以把读性能提升一到两个数量级。

TerarkDB作为一个存储引擎,可以嵌入MongoDB、MySQL、SSDB等现有的存储系统中,也可以直接作为独立的存储系统进行使用。

这里是TerarkDB的评测报告

1.前言

在电视剧《硅谷》中,Pied Piper的核心技术是一种可以直接在高度压缩的数据上进行检索的技术:

Terark的存储引擎TerarkDB,就是基于这样一种技术实现的(我们主要是针对文本进行压缩)。

2.主流的算法介绍

2.1.B+ Tree

通常来说,数据库的读写性能,很大程度上取决于索引的结构,我们大家熟知的B+Tree,是目前最被广泛使用的索引结构之一(比如MySQL的InnoDB引擎),它的优点是:

  • 数据顺序写入比较快,直接在叶子节点追加数据即可
  • 线性扫描快,直接遍历叶子节点即可
  • 随机读较快

当然,缺点也是存在的:

  • 一旦有大量的随机写,会产生频繁的re-balance操作,重新调整树的结构,会影响插入速度
  • 数据的压缩率一般

2.2.LSM Tree

Google开源的LevelDB使用了LSM算法,针对B+树做了一些改进,主要是牺牲了部分的读性能,增强写性能,逻辑思路也较为简单: B+树的写入瓶颈主要在于随机的数据写入需要索引树再平衡(re-balance),那么LSM做的就是让所有的写入(主要是随机写),通过在内存中多级子树的形式,一定程度转换成顺序写入。这种做法的缺点是读的时候需要在多级子树上分别查找,同时会占用更多的内存。

3.Succinct Trie简介

Terark通过Succinct技术及自动机的研究,创造性的把两者进行了结合,通过这种方式让数据的索引更小,同时访问速度呈现出数量级上的增强。

3.1.Succinct技术

Berkeley在2015年发表的论文,描述了Succinct在检索压缩数据上的一种用法:Succinct: Enabling Queries on Compressed Data,简单来说Succinct可以被认为是一种让数据的表达更加紧凑,使用更小的内存达到同样效果的数据结构,往往使用位图来表达各类数据结构,使用Rank-Select进行位操作。但是一直以来性能问题是制约Succinct在工程领域被广泛应用的主要原因。

Terark通过自己的Succinct工具库,实现了性能大幅超越各类开源Succinct库的效果。

3.2.嵌套Succinct Trie结构

Terark使用嵌套Trie树作为基本的数据结构,这种结构比传统的Trie树能够节省极大的空间,并且查询性能更优。同时,我们知道Trie树是一种DFA,基于DFA的理论,可以直接在这个结构上实现正则表达式查询。

为了进一步降低嵌套Trie树的尺寸,把Succinct的空间优势利用起来,Terark在复杂的嵌套树的基础上,又引入了Succinct来表达这种数据结构。

4.基于Succinct Trie的TerarkDB

4.1.性能概要

基于Succinct Trie索引,Terark实现了一个存储引擎TerarkDB,这款存储引擎主要的目的是极大的增强海量数据的读性能,同时显著降低内存使用量(即数据的压缩率非常高)。

我们来先看一下在TerarkDB的优势条件下的读性能对比(图片来自Terark官网http://www.terark.com):

  • 数据总量是9G
  • 整个系统内存总量是3G
  • 其他的存储引擎均设置了256MB的专用缓存

其他存储引擎的数据已经看不到了,这是TerarkDB的优势场景,因为3GB的总内存,扣除掉操作系统占用、专用缓存占用,留给存储引擎使用的实际内存只有2.5G左右,而这些存储引擎无法充分利用内存(有块压缩/解压导致的双缓存问题),所以基于大量的内存和磁盘的交互,性能急剧下降。

而对于TerarkDB来说,由于压缩率非常高,所以内存能装载的数据量以及内存的使用效率远远高于其他引擎。同时,也不需要块解压(search on compressed data),而是直接在压缩数据上进行检索。

为了更清楚的看到这种场景下的差距,我们提供了对数坐标系:

4.2.实现原理

4.2.1.压缩率

如上文提到的,Suucinct和嵌套Trie,TerarkDB的索引高压缩率,主要就是来源于此。除此之外,对于数据的压缩,Terark采用了一种独特的采样算法,结合自动机理论对原始数据进行压缩(直接压缩整个数据库)。

4.2.2.超高的读性能

目前,绝大多数数据库的数据库在数据达到一定体积之后,首先要进行块压缩(block compression),一般可以通过设置块大小(block size)来控制压缩阈值,当然,块设置的越大,压缩率就越高,但是相应的随机读性能往往会降低。

这个原因是,当用户随机读取某一条数据的时候,数据库需要在大量的块中,找到该数据所在的那个块, 然后将整个块解压缩放到内存中,最后在解压缩后的数据中检索目标记录。块设置的更大的情况下, 每次需要解压缩出来的数据就越多,浪费了更多的检索。

同时,块压缩技术也会占用更多的内存,首先压缩后的数据需要加载到内存,然后解压后的数据也需要加载到内存以方便检索。

而TerarkDB的实现方式,完全不需要块压缩,自然也就不需要块解压了,可以直接在高度压缩的数据上直接进行精确检索:

  1. 首先和大多数数据库一样,原始数据会依赖于操作系统的缓存(使用mmap)
  2. TerarkDB的所有索引都存在内存,通过索引,在内存中找到目标记录的ID(实际上相当于一个数组下标),这部分与其他引擎的区别在于,其他引擎这时候是去自己的专有缓存中寻找ID,如果专有缓存没有,则需要去被压缩后的块(block)中寻找,当然这里面就需要解压块了
  3. 通过目标记录的ID,直接定位到数据所在的OS Cache位置,单独提取出这一条数据即可
  4. 如果数据暂未被操作系统缓存,则需要先通过mmap加载后,再进行查询,这部分与传统数据库的逻辑类似,但是由于TerarkDB的高压缩率,一次可以加载的数据往往多很多,所以在内存非常紧俏的情况下, 反而TerarkDB的优势会更明显。

5.Terark也在招募新的成员

Terark是一家非常小的中国创业团队,个位数的成员全部来自于Google或Yahoo。

Terark目前在寻找优秀的C/C++(最好是数据库领域的)开发者一起改进TerarkDB,或者基于Succinct Trie技术发掘更多有趣的应用场景,对Terark感兴趣的,请直接联系 contact@terark.com。

来源:知乎 www.zhihu.com

作者:知乎用户(登录查看详情)

【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。
点击下载


Comments are closed here.