泉源：雷鹏，首发《程序员》杂志
www.iteye.com/news/32473
作者：雷鹏，Terark核心技能发明人。曾就职奇虎360，负责搜刮引擎核心研发；曾就职Yahoo！北研所负责搜刮广告、广告买卖业务（AdExchange）等项目。在数据库、高性能盘算、分布式、体系架构上都深有造诣。
作为数据库，在体系资源（CPU、内存、SSD、磁盘等）肯定的条件下，我们盼望：
存储的数据更多：采取压缩，这个天下上有各种各样的压缩算法；
访问的速率更快：更快的压缩（写）/解压（读）算法、更大的缓存。
险些全部压缩算法都严峻依靠上下文：
位置相邻的数据，一样平常环境下相干性更高，内涵冗余度更大；
上下文越大，压缩率的上限越大（有极限值）。
块压缩
传统数据库中的块压缩技能
对于平凡的以数据块/文件为单位的压缩，传统的（流式）数据压缩算法工作得不错，时间长了，各人也都风俗了这种数据压缩的模式。基于这种模式的数据压缩算法层出不穷，不绝有新的算法实现。包罗利用最广泛的gzip、bzip2、Google的Snappy、新秀Zstd等。
gzip险些在在全部平台上都有支持，而且也已经成为一个行业标准，压缩率、压缩速率、解压速率都比力均衡；
bzip2是基于BWT变更的一种压缩，本质是上对输入分块，每个块单独压缩，长处是压缩率很高，但压缩息争压速率都比力慢；
Snappy是Google出品，长处是压缩息争压都很快，缺点是压缩率比力低，实用于对压缩率要求不高的及时压缩场景；
LZ4是Snappy一个强有力的竞争对手，速率比Snappy更快，特别是解压速率；
Zstd是一个压缩新秀，压缩率比LZ4和Snappy都高不少，压缩息争压速率略低；相比gzip，压缩率中分秋色，但压缩/解压速率要高很多。
对于数据库，在盘算机天下的太古代，为I/O优化的Btree不停是不可撼动的，为磁盘优化的Btreeblock/pagesize比力大，恰好让传统数据压缩算法能得到较大的上下文，于是，基于block/page的压缩也就天然而然地应用到了各种数据库中。在这个蛮荒期间，内存的性能、容量与磁盘的性能、容量泾渭分明，各种应用对性能的需求也比力小，各人都相安无事。
如今，我们有了SSD、PCIeSSD、3DXPoint等，内存也越来越大，块压缩的缺点也日益突出：
块选小了，压缩率不敷；块选大了，性能没法忍；
更致命的是，块压缩节流的只是更大更自制的磁盘、SSD；
更贵更小的内存不但没有节流，反而更浪费了（双缓存题目）。
于是，对于很多及时性要求较高的应用，只能关闭压缩。
块压缩的原理
利用通用压缩技能（Snappy、LZ4、zip、bzip2、Zstd等），按块/页（block/page）举行压缩（块尺寸通常是4KB~32KB，以压缩率著称的TokuDB块尺寸是2MB~4MB），这个块是逻辑块，而不是内存分页、块装备概念中的那种物理块。
启用压缩时，随之而来的是访问速率降落，这是由于：
写入时，很多条记录被打包在一起压缩成一个个的块，增大块尺寸，压缩算法可以得到更大的上下文，从而进步压缩率；相反地，减小块尺寸，会低落压缩率。
读取时，即便是读取很短的数据，也必要先把整个块解压，再去读取解压后的数据。如许，块尺寸越大，同一个块内包罗的记录数量越多。为读取一条数据，所做的不须要解压就也就越多，性能也就越差。相反地，块尺寸越小，性能也就越好。
一旦启用压缩，为了缓解以上题目，传统数据库一样平常都必要比力大的专用缓存，用来缓存解压后的数据，如许可以大幅进步热数据的访问性能，但又引起了双缓存的空间占用题目：一是操纵体系缓存中的压缩数据；二是专用缓存（比方RocksDB中的DBCache）中解压后的数据。尚有一个同样很严峻的题目：专用缓存终归是缓存，当缓存未掷中时，仍必要解压整个块，这就是慢Query题目的一个重要泉源（慢Query的另一个重要泉源是在操纵体系缓存未掷中时）。
这些都导致现有传统数据库在访问速率和空间占用上是一个此消彼长、无法彻底办理的题目，只能采取一些折衷。
RocksDB的块压缩
以RocksDB为例，RocksDB中的BlockBasedTable就是一个块压缩的SSTable，利用块压缩，索引只定位到块，块的尺寸在dboption里设定，一个块中包罗多条（key，value）数据，比方M条，如许索引的尺寸就减小到了1/M：
M越大，索引的尺寸越小；
M越大，Block的尺寸越大，压缩算法（gzip、Snappy等）可以得到的上下文也越大，压缩率也就越高。
创建BlockBasedTable时，KeyValue被逐条填入buffer，当buffer尺寸到达预定巨细（块尺寸，固然，一样平常buffer尺寸不会正确地刚好便是预设的块尺寸），就将buffer压缩并写入BlockBasedTable文件，并记录文件偏移和buffer中的第一个Key（创建index要用），假如单条数据太大，比预设的块尺寸还大，这条数据就单独占一个块（单条数据不管多大也不会分割成多个块）。全部KeyValue写完以后，根据之前记录的每个块的起始Key和文件偏移，创建一个索引。以是在BlockBasedTable文件中，数据在前，索引在后，文件末端包罗元信息（作用相称于常用的FileHeader，只是位置在文件末端，以是叫footer）。
搜刮时，先利用searchkey找到searchkey地点的block，然后到DBCache中搜刮这个块，找到后就进一步在块中搜刮searchkey，假如找不到，就从磁盘/SSD读取这个块，解压后放入DBCache。RocksDB中的DBCache有多种实现，常用的包罗LRUCache，别的尚有ClockCache、CountingCache（用来统计Cache掷中率等），尚有其他一些特别的Cache。
一样平常环境下，操纵体系会有文件缓存，以是同一份数据大概既在DBCache中（解压后的数据），又在操纵体系Cache中（压缩的数据）。如许会造成内存浪费，以是RocksDB提供了一个折衷：在dboption中设置DIRECT_IO选项，绕过操纵体系Cache，如许就只有DBCache，可以节流一部分内存，但在肯定程度上会低落性能。
传统非主流压缩：FM-Index
FM-Index的全名是FullTextMatchingIndex，属于SuccinctDataStructure家属，对数据有肯定的压缩本领，而且可以直接在压缩的数据上实行搜刮和访问。
FM-Index的功能非常丰富，汗青也已经相称久长，不算是一种新技能，在一些特别场景下也已经得到了广泛应用，但是由于各种缘故起因，不停不温不火。近来几年，FM-Index开始有些活泼，起首是GitHub上有个大牛实现了全套Succinct算法，此中包罗FM-Index，其次Berkeley的Succinct项目也利用了FM-Index。
FM-Index属于Offline算法（一次性压缩全部数据，压缩好之后不可修改），一样平常基于BWT变更（BWT变更基于后缀数组），压缩好的FM-Index支持以下两个最重要的操纵：
data=extract(offset,length)
{offset}=search(string)，返回多个匹配string的位置/偏移（offset）
FM-Index还支持更多其他操纵，感爱好的朋侪可以进一步调研。
但是，在笔者看来，FM-Index有几个致命的缺点：
实现太复杂（这一点可以被少数大牛们降服，不提也罢）；
压缩率不高（比流式压缩比方gzip差太多）；
搜刮（search）和访问（extract）速率都很慢（在2016年最快的CPUi7-6700K上，单线程吞吐率不高出7MB/sec）；
压缩过程又慢又耗内存（Berkeley的Succinct压缩过程内存斲丧是源数据的50倍以上）；
数据模子是FlatText，不是数据库的KeyValue模子。
可以用一种简单的方式把FlatModel转化成KeyValueModel：挑选一个在Key和Value中都不会出现的字符“#”（假如无法找出如许的字符，必要举行转义编码），每个Key前后都插入该字符，Key之后紧邻的就是Value。云云，search(#key#)返回了#key#出现的位置，我们就能很轻易地拿到Value了。
Berkeley的Succinc项目在FM-Index的FlatText模子上实现了更丰富的行列（Row-Column）模子，付出了巨大的积极，到达了肯定的结果，但离实用还相差太远。
感爱好的朋侪可以细致调研下FM-Index，以验证笔者的总结与判定。
Terark的可检索压缩（SearchableCompression）
Terark公司提出了“可检索压缩（SearchableCompression）”的概念，其核心也是直接在压缩的数据上实行搜刮（search）和访问（extract），但数据模子本身就是KeyValue模子，根据其测试陈诉，速率要比FM-Index快得多（两个数量级），具体叙述：
摒弃传统数据库的块压缩技能，采取全局压缩；
对Key和Value利用差别的全局压缩技能；
对Key利用有搜刮功能的全局压缩技能COIndex（对应FM-Index的search）；
对Value利用可定点访问的全局压缩技能PA-Zip（对应FM-Index的extract）。
对Key的压缩：CO-Index
我们必要对Key举行索引，才华有效地举行搜刮，并访问必要的数据。
平凡的索引技能，索引的尺寸相对于索引中原始Key的尺寸要大很多，有些索引利用前缀压缩，能在肯定程度上缓解索引的膨胀，但仍旧无法办理索引占用内存过大的题目。
我们提出了CO-Index（CompressedOrderedIndex）的概念，而且通过一种叫做NestedSuccinctTrie的数据布局实践了这一概念。
较之传统实现索引的数据布局，NestedSuccinctTrie的空间占用小十几倍乃至几十倍。而在保持该压缩率的同时，还支持丰富的搜刮功能：
正确搜刮；
范围搜刮；
次序遍历；
前缀搜刮；
正则表达式搜刮（不是逐条遍历）。
与FM-Index相比，CO-Index也有其上风（假定FM-Index中全部的数据都是Key）。
表1FM-Index对比CO-Index
CO-Index的原理
实际上我们实现了很多种CO-Index，此中NestedSuccinctTrie是实用性最广的一种，在这里对其原理做一个简单先容：
SuccinctDataStructure先容
SuccinctDataStructure是一种可以或许在靠近于信息论下限的空间内来表达对象的技能，通常利用位图来表现，用位图上的rank和select来定位。
固然可以或许极大低落内存占用量，但实现起来较为复杂，而且性能低很多（时间复杂度的常数项很大）。如今开源的有SDSL-Lite，我们则利用本身实现的Rank-Select，性能也高于开源实现。
以二叉树为例
传统的表现情势是一个结点中包罗两个指针：structNode{Node*left,*right;};
每个结点占用2ptr，假如我们对传统方法举行优化，结点指针用最小的bits数来表达，N个结点就必要2*[log2(N)]个bits。
对比传统根本版和传统优化版，假设共有216个结点（包罗null结点），传统优化版必要2bytes，传统根本版必要4/8bytes。
对比传统优化版和Succinct，假设共有10亿(~230)个结点。
传统优化版每个指针占用[log2(230)]=30bits，总内存占用：($frac{2*30}{8}$)*230≈7.5GB。
利用Succinct，占用：($frac{2.5}{8}$)*230≈312.5MB(每个结点2.5bits，此中0.5bits是rank-select索引占用的空间）。
SuccinctTree
SuccinctTree有很多种表达方式，这里列出常见的两种：
图1SuccinctTree表达方式示例
SuccinctTrie=SuccinctTree+TrieLabel
Trie可以用来实现Index，图2这个SuccinctTrie用的是LOUDS表达方式，此中生存了hat、is、it、a、四个Key。
PatriciaTrie加嵌套
仅利用Succinct技能，压缩率远远不敷，以是又应用了路径压缩和嵌套。如许一来，压缩率就上了一个新台阶。
把上面这些技能综合到一起，就是我们的NestSuccinctTrie。
对Value的压缩:PA-Zip
我们研发了一种叫做PA-Zip(PointAccessibleZip)的压缩技能：每条数据关联一个ID，数据压缩好之后，就可以用相应的ID访问那条数据。这里，ID就是谁人Point，以是叫做PointAccessibleZip。
PA-Zip对整个数据库中的全部Value（KeyValue数据库中全部Value的聚集）举行全局压缩，而不是按block/page举行压缩。这是针对数据库的需求（KeyValue模子），专门计划的一个压缩算法，用来办理传统数据库压缩的题目：
压缩率更高，没有双缓存的题目，只要把压缩后的数据装进内存，不必要专用缓存，可以按ID直接读取单条数据，假如把这种读取单条数据看作是一种解压，那么：
按ID次序解压时，解压速率（Throughput）一样平常在500MB每秒（单线程），最高到达约7GB/s，得当离线分析性需求，传统数据库压缩也能做到这一点；
按ID随机解压时，解压速率一样平常在300MB每秒（单线程），最高到达约3GB/s，得当在线服务需求，这一点完胜传统数据库压缩：按随机解压300MB/s算，假如每条记录均匀长度1K，相称于QPS=30万；假如每条记录均匀长度300个字节，相称于QPS=100万；
预热（warmup），在某些特别场景下，数据库大概必要预热。由于去掉了专用缓存，TerarkDB的预热相对简单高效，只要把mmap的内存预热一下（克制PageFault即可），数据库加载乐成后就是预热好的，这个预热的Throughput就是SSD连续读的IO性能（较新的SSD读性能高出3GB/s）。
与FM-Index相比，PA-Zip办理的是FM-Index的extract操纵，但性能和压缩率都要好得多：
表2FM-Index对比PA-Zip
连合Key与Value
Key以全局压缩的情势生存在CO-Index中，Value以全局压缩的情势生存在PA-Zip中。搜刮一个Key，会得到一个内部ID，根据这个ID，去PA-Zip中定点访问该ID对应的Value，整个过程中只触碰必要的数据，不必要触碰其他数据。
云云无需专用缓存（比方RocksDB中的DBCache），仅利用mmap，美满共同文件体系缓存，整个DB只有mmap的文件体系缓存这一层缓存，再加上超高的压缩率，大幅低落了内存用量，而且极大简化了体系的复杂性，终极完成数据库性能的大幅提拔，从而同时实现了超高的压缩率和超高的随机读性能。
从更高的哲学层面看，我们的存储引擎很像是用构造法推导出来的，由于CO-Index和PA-Zip精密共同，美满匹配KeyValue模子，功能上“刚好够用”，性能上压榨硬件极限，压缩率逼近信息论的下限。相比其他方案：
传统块压缩是从通用的流式压缩衍生而来，流式压缩的功能非常有限，只有压缩息争压两个操纵，对太小的数据块没有压缩结果，也无法压缩数据块之间的冗余。把它用到数据库上，必要大量的工程积极，就像给汽车装上飞机机翼，然后要让它飞起来。
相比FM-Index，环境则相反，FM-Index的功能非常丰富，它就肯定要为此付出一些代价——压缩率和性能。而在KeyValue模子中，我们只必要它那些丰富功能的一个非常小的子集（还要颠末适配和转化），其他更多的功能毫无用武之地，却仍旧要付出那些代价，就像我们花了很高的代价造了一架飞机，却把它按在地上，只用轮子跑，当汽车用。
图2用LOUDS方式表达的SuccinctTree
图3路径压缩与嵌套
附录
压缩率性能测试比力
数据集：Amazonmoviedata
Amazonmoviedata(~8millionreviews)，数据集的总巨细约为9GB,记录数约莫为800万条，均匀每条数据长度约莫1K。
压缩率（见图4）
图4压缩率对比
随机读（见图5）
图5随机读性能对比
这是在内存充足的环境下，各个存储引擎的性能。
耽误曲线（见图6）
图6耽误曲线对比
数据集：Wikipedia英文版
Wikipedia英文版的全部文本数据，109G，压缩到23G。
数据集：TPC-H
在TPC-H的lineitem数据上，利用TerarkDB和原版RocksDB（BlockBasedTable）举行对比测试：
表3TerarkDB与原版RocksDB对比测试
API接口
TerarkDB=TerarkSSTable+RocksDB
RocksDB最初是Facebook对Google的LevelDB的一个fork，编程接口上兼容LevelDB，并增长了很多改进。
RocksDB对我们有效的地方在于其SSTable可以plugin，以是我们实现了一个RocksDB的SSTable，将我们的技能上风通过RocksDB发挥出来。
固然RocksDB提供了一个相对完备的KeyValueDB框架，但要完全适配我们特有的技能，仍有一些短缺，以是必要对RocksDB本身也做一些修改。将来大概有一天我们会将本身的修改提交到RocksDB官方版。
Github链接：TerarkDB（https://github.com/Terark/terarkdb），TerarkDB包罗两部分：
terark-zip-rocksdb（https://github.com/terark/terark-zip-rocksdb），（TerarkSSTableforrocksdb）
Terarkforkrocksdb（https://github.com/Terark/rocksdb），（必须利用这个修改版的rocksdb）
为了更好的兼容性，TerarkDB对RocksDB的API没有做任何修改，为了进一步方便用户利用TerarkDB，我们乃至提供了一种方式：程序无需重新编译，只必要更换librocksdb.so并设置几个环境变量，就能体验TerarkDB。
假如用户必要更风雅的控制，可以利用C++API具体设置TerarkDB的各种选项。
如今各人可以免费试用，可以做性能评测，但是不能用于production，由于试用版会随机删掉0.1%的数据。
Terark下令行工具集
我们提供了一组下令行工具，这些工具可以将输入数据压缩成差别的情势，压缩后的文件可以利用TerarkAPI或（该工具会合的）其他下令行工具解压或定点访问。
详情拜见Terarkwiki中文版（https://github.com/Terark/terark-wiki-zh_cn）。
CopyrightYourWebSite.SomeRightsReserved.
京ICP备2023016396号-1PoweredByESCLINK.
我要评论