欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/

本文来自OceanBase社区分享，仅限交换探讨。原作者马伟，长期从事互联网广告检索系统的研发，对数据库，编译器等畛域也有浓厚兴趣。

咱们在前文介绍过，多款分布式数据库都应用了LSM树作为底层的存储引擎，其中就包含TiDB和Oceanbase。与TiDB等数据库的存储引擎将RocksDB作为一个黑盒应用不同，尽管OceanBase的存储尽管也是基于LSM树，但却是齐全本人实现，并且和本人的存储引擎做了深度的定制和整合。与RocksDB中可能存在5，6层的LSM不同，OceanBase的实现中，将LSM树划分为三层，第一层MemTable，第二层OceanBase成为增量层，也称转储层(即LSM树C0层)，第三层OB称为基线层(即LSM树C1)层。

与RocksDB中实现一样，OceanBase的增量层(C0)多个SSTable之间Key会存在区间重叠的关系，读取的时候须要遍历查找每个增量SSTable能力确定Key是否存在，本文将以OceanBase 3.x版本为例，解说其如何针对这一问题进行优化。OceanBase 的基线层数据是全局有序的，所有SSTable之间的Key不会存在区间重叠的问题。

1. MemTable

OceanBase 数据库的内存存储引擎 MemTable 由 BTree 和 Hashtable 组成。在插入/更新/删除数据时，首先记录Redo日志，并通过RPC进行Paxos协定复制到其余少数正本，而后再将数据写入内存块，在 HashTable 和 BTree 中存储的均为指向对应数据的指针。正本通过接管Master节点发送过去的Redo日志进行重做回放将数据到本身的MemTable。

MemTable在内存中保护了历史版本的事务，每⼀⾏将历史事务针对该⾏的操作依照工夫程序组织成⾏操作链，新事务提交时会往⾏操作链尾部追加新的⾏操作。如果⾏操作链保留的历史事务过多，将影响读取性能，此时须要触发内存compaction操作，交融这些历史事务以⽣成新的⾏操作链。

两种索引构造各自有优缺点，独自无奈很好的实现数据库的点查和范畴查找的需要，所以OB将两者联合起来应用，惟一的代价就是在多线程并发环境下数据写入须要对两种数据结构都进行操作，实现绝对简单。

数据结构长处毛病
HashTable· 插入一行数据的时候，须要先查看此行数据是否曾经存在，当且仅当数据不存在时能力插入，查看抵触时，Hashtable 要比 BTree 快。 · 事务在插入或更新一行数据的时候，须要找到此行并对其进行上锁，避免其它事务批改此行，OceanBase 数据库的行锁放在 ObMvccRow 中，须要先找到它，能力上锁。不适宜对范畴查问应用HashTable。
BTree范畴查找时，因为 BTree node 中的数据都是有序的，因而只须要搜寻部分的数据就能够了。单行的查找，也须要进行大量的 rowkey 比拟，从根结点找到叶子结点，而 rowkey 比拟性能是较差的，因而实践上性能比 HashTable 慢很多。

2. SSTable

当 MemTable 的大小达到某个阈值后，OceanBase 数据库会将 MemTable 中的数据转存于磁盘上，转储后的构造称之为 SSTable。OceanBase的SSTable是不定长的，其外部会被切分为2MB一个的定长数据块，OB称之为宏块(Macro Block)。宏块是OB写数据到磁盘的根本IO单位。

宏块外部会被划分为多个16KB左右的变长数据块，OB称之为微块(Micro Block)。微块中会存储若干数据行(Row)，微块是OB数据文件读取的根本单位。微块在结构时会写入间断的数据行，到16KB左右，而后再通过通用压缩算法(LZ4, ZSTD等)，而后再退出到宏块当中。

宏块是定长的，大小为固定的 2MB，长度不能够被调整；微块默认大小为16KB，经通用压缩后是变长的。OB在进行 IO 读取时，会依照 4KB 来做 IO 对齐，因而一次 IO 读的长度并不一定与微块长度完全一致。微块长度能够被批改，通过以下的语句能够对于不同的表设置不同的微块长度：

ALTER TABLE mytest SET block_size = 131072;

一般来说微块长度越大，数据的压缩比会越高，但相应的一次 IO 读的代价也会越大；微块长度越小，数据的压缩比会越低，但相应的一次 IO 读的代价会更小。

3. 数据压缩

3.1. 传统关系数据库数据压缩实现

传统关系型数据库实践和架构在20世纪70，80年代被确定下来，直到2010年的挪动互联网时代之前，其架构都没有大的扭转。晚期数据库系统，CPU算力较弱，而数据压缩是十分消耗CPU的操作，因而传统基于页面行存的关系数据库中一开始都没有为数据压缩进行顶层设计。到互联网时代面对海量数据，传统的关系型数据库也开始思考减少压缩个性，升高用户的存储老本。

传统的关系型数据库的压缩，次要有两个方向，一个是针对OLTP，即事务处理的workload提供的计划。另外一种是针对OLAP，即数据分析型的workload提供的计划。

针对OLTP的workload提供的计划次要是基于页面的通用压缩。OLTP型的workload，通常须要对行内的数据进行更改，一般来说，采纳行存储性能较好。这种负载下，一个页面内的行可能会被下层利用重复批改，因而行与行之间的数据压缩根本难以进行，支流厂商个别都是才用了基于页面的整体通用压缩。以MySQL的InnoDB引擎为例，一个页面未压缩前，在磁盘上占用16KB的空间，压缩后只有11KB，那么依照4KB进行IO对齐的话，压缩后的数据占用12KB的磁盘空间。InnoDB的这个页面在文件中依然占用16KB的空间，然而利用操作系统的稠密文件(Sparse File)个性，操作系统理论只为这个页面申请了12KB的磁盘空间，因而能够节约4KB的空间。

这种压缩形式也会带来很多问题：

  • 如果一个页面被批改很频繁的话，重复的读出和写入数据的过程中须要进行压缩/解压，对CPU的开销也不可疏忽。
  • 如果页面被批改并压缩后，其大小比原来减少了，如原来压缩后是12KB，当初压缩后是13KB。操作系统须要为新减少的数据调配磁盘空间，此时调配的磁盘空间通常都不是和之前的12KB的空间间断的。这样对这个页面的读取，IO是不间断的，性能会变差。

总结起来就是，传统数据库的基于行存页面的压缩，通常状况下，只能帮忙用户节约一部分存储空间，并不会带来性能的晋升。如果使用不当，性能有可能还会降落。

OLAP型负载的数据压缩，通常数据都是只读的，没有了数据更新的限度，数据压缩做的十分激进。在页面内的数据能够不按行存，而是依照列存。雷同列的数据放在一起，能够做十分多的压缩，如常量编码，字典编码，Delta编码，RLE编码等等。这些数据编码能够无效缩小页面的存储空间，同时不会对数据查问有任何的影响。因为OB也采纳了相似的压缩计划，因而这里的列存压缩计划，会放到OB的压缩实现中去讲。

传统的基于页面存储的关系数据库还有一个问题就是，OLAP和OLTP两种负载的不可和谐性。要想OLAP解决能力强，数据个别都是行存的；要想OLTP解决能力强，数据须要是列存的。如果要想两者都要(小孩才做抉择，成年人全都要)，那么必须要部署两套异构的存储(只管数据库服务程序可能是一个/一套)，一套专门用于OLTP，一套用于OLAP，二者之间还须要通过数据链路进行同步。这无疑显著减少了硬件和运维治理的老本。

3.2. LSM树数据压缩劣势综述

基于LSM的存储引擎，其在磁盘上的数据，在下一次合并之前，都是只读而不会被批改的。通过BigTable和LevelDB引入的SSTable，SSTable外部再分Block存储的概念目前曾经是LSM树实现的标配。这些只读的Block，类比传统数据库的页的话，是十分好的压缩指标。相比OLTP数据库的页面，SSTable的Block压缩有以下几个劣势：

  • 数据只读，不会因为重复批改而带来重复的压缩/解压的CPU耗费，也不会因为重复批改带来的数据收缩导致的IO不间断。
  • 数据内聚，一个Block内通常有几十乃至更多的行，能够在Block写入的时候一次性的针对这些行做列式压缩，能够失去更好的压缩比，而且能够减速后续的查问。

业内基于LSM的存储其实也看到了这些压缩劣势并有了相当的实现，如Facebook提出的RCFile。然而这类利用通常也都是Hadoop等批处理场景，理论在OLTP数据库场景使用这种压缩计划的，据理解就Spanner和OceanBase。

3.3. OB数据压缩实现

咱们后面提到，OB的SSTable的格局，是分为SSTable，Macro Block, Micro Block三级。OB的开源3.x版本只实现了Micro Block内的行存储，外部版本中实现了Micro Block内的列存储。OB在Micro Block内基于列存储进行高效的编码压缩，而后在整体以Micro Block为单位进行通用算法压缩。依照OB晚期的文章的声称，客户在进行MySQL数据迁徙的时候，教训公式是依照6:1进行容量布局的，即OB依照列式编码压缩+通用压缩之后的数据，只有等同MySQL的1/6(该论断未做深刻考据，不确定是否蕴含OB三正本，以及MySQL数据是否启用压缩，仅供参考)。

3.3.1. 通用压缩

咱们当初能见到的，压缩解压代价绝对可控的通用压缩算法，根本都是基于Abraham Lempel与Jacob Ziv在1977/1978论文中发表的LZ77/LZ78算法变种得来，如LZW，LZ4，Snappy，ZSTD等。LZ系的通用压缩算法实质是一种在字节流上的基于滑动窗口的字典压缩算法。算法会动静的在最近一段数据流中寻找反复呈现的字节片段，而后进行压缩。

OB在Micro Block粒度是反对抉择通用压缩算法来对整个Micro Block进行通用压缩的，用户能够通过表的属性来进行设置。通用压缩尽管也能带来肯定的数据压缩比，然而这是有性能损失的。OB的Micro Block在压缩前是16KB，是一次读IO读取的数据的大小。当OB的Micro Block被通用压缩之后，OB一次IO的大小依然是16KB。压缩后的数据还须要解压之后能力应用。即是是以后最快的通用压缩算法LZ4，其解压速度也只有约5GB/S，只有内存数据拷贝(memcpy)的35%左右。

CompressorRatioCompressionDecompression
memcpy1.00013700 MB/s13700 MB/s
LZ4 default (v1.9.0)2.101780 MB/s4970 MB/s
LZO 2.092.108670 MB/s860 MB/s
Snappy 1.1.42.091565 MB/s1950 MB/s
Zstandard 1.4.0 -12.883515 MB/s1380 MB/s
LZ4 HC -9 (v1.9.0)2.72141 MB/s4900 MB/s

况且，通用的数据压缩算法并不是为数据库专门设计的，这些压缩算法将输出看成是一个间断的字节流，并不对数据的pattern做任何先验假如。但实际上数据库中寄存的是结构化数据，是有明确的schema的，每行数据每个字段都有明确的类型和大小。利用这些信息，采纳肯定的数据编码技术，就能够实现比间接应用通用压缩算法好得多的压缩成果。这些数据编码技术，岂但能进步数据的压缩比，还能根本不升高数据的查问效率。某些查问状况下，甚至还能减速查问。

3.3.2. 编码压缩

OB中的Micro Block正是在列存的根底上，联合了数据schema，进行了一系列的高效的数据编码压缩。其次要的数据编码压缩算法有以下几类。

  • 字典编码：所有数据编码技术中最罕用、也是最无效的办法。字典编码的思维很简略，就是把重复性较高的数据进行去重，把去重后的数据建设字典，而把原来存放数据的中央存成指向特定字典下标的援用。数据的拜访逻辑是十分间接的，没有解码过程。特地要留神，字典中的各数据是按类型序排序的，这样做有两个益处：一是有序的数据更有利于压缩；二是有序的数据意味着咱们在做谓词计算时，能够将谓词逻辑间接下压到字典，并通过二分逻辑实现疾速迭代，这点在咱们反对简单计算时，将施展十分重要的作用。
  • RLE编码：实用于间断相等的数据，比方形如1，1，1，2，2，...之类的，咱们能够把这些间断相等的数据去重，并只保留其起始行号，RLE编码在数据库中次要用于解决有序的数据（比方索引的前缀）。
  • 常量编码：针对近似常量化的数据，编码辨认一个最常见的数据作为常量，而只记录所有不等于这个常量的异样值和它们的行号，常量编码在理论业务数据中十分有用，后者往往存在着一些业务减少、然而并不应用的字段，这些字段同样占据了空间，并呈现出常量化（默认值）的数据分布。
  • 差值编码(数值字段)：实用于在一个小值域范畴内散布的整数型数据，通过计算区间内的MIN、MAX，将数据减去MIN后，用更小的位宽进行编码。比拟常见的数据是工夫类型，间断生成的工夫类型数据通常有十分好的局部性（比方差值在几秒钟以内）。
  • 差值编码(字符字段)：实用于定长的、有确定业务规定的字符型数据，通过结构公共串，将数据中只记录差别局部。这类数据在业务中十分常见，通常用于主键，比方订单号、用户账号等。
  • 前缀编码：实用于前缀雷同的字符型数据，通过结构公共前缀，将数据中只记录差别的后缀。其它一些数据库，比方SQL Server、HBase中也常常应用，这类数据在业务中也很常见，比方局部主键。后面提到的数据编码都是列内编码，即只思考同一列内各字段的数据相似性，除此之外，OceanBase还实现了一组列间的数据编码，也就是思考同一行的不同列间数据的相似性。
  • 列间编码(数值字段)：实用于两列近似相等的整数型数据，这样，其中的一列只须要存储和另一列的差别值。这种列间相等的数据编码有它很强的实用场景，比方咱们晓得业务在数据表中通常都会记录生成和最近一次更新的工夫戳，如果某些流水数据从不会产生更新，那么这两个字段就存在很强的列间相等关系。
  • 列间编码(字符字段)：实用于两列存在子串关系的字符型数据，也就是一列是另一列的子串（包含前缀、后缀、相等关系）。理论业务中许多长字符型字段并不是由用户随便生成的，而是基于肯定的业务规定，将多个根底字段拼接而成，这时候这些根底字段就和前者存在子串关系。

OB所采纳的这些编码压缩算法，解码过程非常简单，解码特定一行的数据，并不需要依赖其它行，这种近似O(1)复杂度的设计进步了数据投影的性能，使得其可能被用于在线零碎。

尽管这些编码压缩算法解码简略，然而编码过程却并不那么trivial。只管OB晓得每张表每一列数据的属性，然而数据的散布OB却并没那么的理解，如某一列尽管是64位整数，然而OB事先并不一定晓得它所有值都是一个无限的枚举类型，只有等到须要Compact压缩一个Micro Block的时候能力晓得。为了加重DBA的心智累赘，OB并不心愿把每一列的编码压缩算法都由DBA来指定，而心愿是OB本人依据以后数据的散布来智能抉择。这就波及到一个比拟大的问题，如何智能的为每一列来抉择最优的编码压缩算法。

OB的做法是如果上一个Micro Block某一列通过计算抉择了某种编码算法，那么如果数据分布稳固的话，下一个Micro Block的雷同列大概率最优的编码算法跟上一个Block一样。OB会优先尝试通过这个编码算法对列进行压缩，如果压缩后的后果(压缩比)证实这个抉择正确，那么就会采纳这个编码算法来压缩当前列；否则会退回从新抉择适合的编码算法。

OB的公开材料示意，这块还有较大的优化空间。而且业内目前也有一些新鲜的想法，如通过机器学习来预测数据的最优编码压缩算法。置信后续OB的新版本中会有继续改良和晋升。

3.4. TiDB数据压缩实现

TiDB的存储层TiKV是根底RocksDB的，前文咱们也提到，RocksDB是在LevelDB的根底上改良来的，而原始的LevelDB只实现了基于Block的整体通用压缩，并未在Block内采纳列存及数据编码压缩。因而采纳RocksDB作为底层存储的TiDB，也未应用Block内的列存及数据编码压缩。

TiDB为了应答OLAP类需要，专门另外波及并实现了一套存储格局，采纳了列存的形式，此处不展开讨论，有趣味的同学能够参考文档(PS: TiDB不愧是开源标杆，文档十分欠缺，轻易翻翻也能学习到不少货色)。部署时，须要部署专门的从库来接管主库的数据同步，而后改为列存存储以应答OLAP查问需要。

4. 缓存策略

因为很多数据存储于 SSTable，为了减速查问，OB须要对数据进行缓存。OceanBase 数据库并不需要对缓存的大小进行设置，相似于 Linux 对于 page cache 的控制策略，OceanBase 数据库会尽量应用租户的内存，直到租户的内存达到肯定阈值后，才会触发对 Cache 的淘汰。同时 OceanBase 数据库也是一个多租户零碎，对于每一个租户都会有各自的 Cache，但 OceanBase 数据库会对所有租户的缓存进行对立治理。

4.1. Row Cache

传统关系型数据库并不对独自的某行进行缓存，OB基于LSM的存储引擎却实现了行级缓存。OB的Row Cache 缓存具体的数据行，在进行 Get/MultiGet 查问时，可能会将对应查到的数据行放入 Row Cache，这样在进行热点行的查问时，就能够极大地晋升查问性能。

4.2. Block Cache

传统的关系数据库中，缓存是以IO页面为单位进行缓存的。在LSM为存储引擎的数据库中，IO页面为单位的缓存策略也须要随着LSM构造来进行适配。咱们之前提到过，OB的IO读的最小单位是微块，OB的Block Cache是以微块(Micro Block)为单位的，其缓存的数据是解压缩后的微块数据，大小是变长的。

另外，数据查问的时候，如果没有在Row Cache或者MemTable中查问到数据话，咱们须要去Block Cache或者磁盘中查问数据。查问数据的第一步是须要先确定数据在哪个微块，这也须要咱们将一部分微块的索引缓存在内存中。

OB的Block Index Cache即缓存微块的索引，相似于 BTree 的中间层，在数据结构上和 Block Cache 有一些区别，因为中间层通常不大，Block Index Cache 的命中率通常都比拟高。

4.3. Filter Cache

LSM树是基于排序的的存储构造，这类构造通常在进行点查问的时候，对不存在的数据的查问和确认是不高效的。不存在的数据，通常咱们在内存中也无奈缓存，内存查问也就无奈命中，只有通过IO去读取数据所在范畴的SSTable(微块)来确认数据是否存在。这样对于数据的存在性查问将变得十分低效。因而各种LSM树的实现中都引入了Blook Filter来进行存在性过滤，OB也在宏块(Macro Block)层引入了Bloom Filter用于数据存在性过滤。

Bloom Filter是一种只能插入元素，无奈删除元素的数据结构。在传统的关系数据库中，IO页面(Page)随时可能会被利用批改，一行数据随时都可能被删除，因而无奈高效的应用Bloom Filter来作为空数据过滤器。而基于LSM树存储引擎则不同，其磁盘上的数据，在下一次合并(Compaction)之前，都是不可变的。Compaction间隔时间通常都是以小时为单位，这种场景非常适合Bloom Filter的应用。Bloom Filter也是一种能够非常容易通过空间来调整查问错误率的数据结构，利用能够轻易的通过调整每个元素所占用的空间(Row per bits)，来调整查问的错误率(即数据不在SSTable中，然而通过Bloom Filter查问被确认存在的概率)。

OB中的Bloom Filter的构建策略是按需构建，当一个宏块上的空查次数超过某个阈值时，就会主动构建 Bloom Filter，并将 Bloom Filter 放入 Cache。

5. 合并策略

后面咱们曾经讲过合并是LSM树类存储系统中最简单，也是对系统性能/稳定性影响最大的一个过程。因而，OB实现的LSM树在数据合并上也是进行了十分粗疏的波及，提供了多种合并策略，力求合并过程平滑可控。OceanBase的合并策略，依据表上是否有DDL操作，如加列，减列，批改压缩算法等，会才去不同的策略。当表上无DDL操作时，OceanBase次要采取增量合并策略；反之则会采纳渐进合并或者全量合并策略。

5.1. 增量合并

增量合并的状况下，咱们晓得表的Schema没有批改，因而能够在合并的时候，在不同粒度上看数据是否能够重用。OB的Macro Block划分为2M一个，这个是一个绝对较小的尺寸。当表绝对较大的时候，如一张100G的表，零碎里会有102400个Macro Block。数据更新的时候，这些Macro Block中很多有可能都没有被批改过，因而能够间接重用，这种形式称之为增量合并。

绝对于全量合并的把所有的宏块的重写一边而言，增量合并只重写产生了批改的宏块。增量合并极大地缩小了合并的工作量，也是 OceanBase 数据库目前默认的合并算法。

更进一步地，对于宏块外部的微块，很多状况下也并不是所有的微块都会被批改。当发现宏块有行被批改过期，在解决每一个微块时，会先判断这个微块是否有行被批改过，如果没有，只须要把这个微块的数据间接拷贝到新的宏块上，这样没被批改过的微块就省去了解析行、抉择编码规定、对行进行编码以及计算列 Checksum 等操作。微块级增量合并进一步缩小了合并的工夫。

5.2. 渐进合并

在执行某些 DDL 操作时，例如执行表的加列、减列、批改压缩算法等操作后，数据须要齐全重写一遍能力在磁盘上失效。OceanBase 数据库并不会立刻对数据执行重写操作，而是将重写动作提早到合并时进行。基于增量合并的形式，无奈实现对未修改数据的重写，为此 OceanBase 数据库引入了“渐进合并”，即把数据的重写扩散到屡次合并中去做，在一次合并中只进行局部数据的重写。

用户能够通过参数指定渐进合并的轮次，如：

ALTER TABLE mytest SET progressive_merge_num=60;

示意将mytest表的渐进轮次设置为60，在DDL操作实现之后的60次渐进合并过程中，每一次合并会重写60分之一的数据，在60轮合并过后，数据就被整体重写了一遍。

当未对表的progressive_merge_num进行设置时，其默认值为0，目前语义为在执行须要重写数据的DDL操作之后，做渐进轮次为100的渐进合并。当表的progressive_merge_num被设置为1时，示意强制走全量合并。

5.3. 全量合并

OB的全量合并和 HBase 与 Rocksdb 的 Major Compaction 过程是相似的。顾名思义，在全量合并过程中，会把以后的基线数据都读取进去，和增量数据合并后，再写到磁盘下来作为新的基线数据。在这个过程中，会把所有数据都重写一遍。全量合并会极大的消耗磁盘 IO 和空间，如非必要或者 DBA 强制指定，OceanBase 数据库个别不会被动做全量合并。

OceanBase 数据库发动的全量合并个别产生在列类型批改等 DDL 操作之后。DDL 变更是实时失效的，不阻塞读写，也不会影响到多正本间的 Paxos 同步，将对存储数据的变更延后到合并的时候来做，这时就须要将所有数据重写一遍。

5.4. 轮转合并

一般来说合并会在业务低峰期进行，但并不是所有业务都有业务低峰期。在合并期间，会耗费比拟多的 CPU 和 IO，此时如果有大量业务申请，势必会对业务造成影响。为了躲避合并对业务的影响。借助 OceanBase 数据库的多正本分布式架构，引入了轮转合并的机制。

个别配置下，OceanBase 数据库会同时有 3 个数据正本，当一个数据正本在进行合并时，能够将这个正本上的查问流量切到其余没在合并的集群下面，这样业务的查问就不受每日合并的影响。等这个正本合并实现后，再将查问流量切回来，持续做其余正本的合并，这一机制称之为轮转合并。

为了防止流量切过去后，Cache 较冷造成的 RT 稳定，在流量切换之前，OceanBase 数据库还会做 Cache 的预热，通过参数能够管制预热的工夫。

6. 总结

到此，《数据库存储与索引技术》系列的内容就完结了。存储和索引技术作为数据库底层的重要根底，把握其相干常识有助于咱们进一步提高对数据库底层原理的意识。心愿通过本系列三篇文章的介绍，可能让大家对数据库底层技术以及目前国内支流的分布式数据库底层实现有所理解，在大家当前的工作中可能有所帮忙！

参考文献

\1. Oceanbase文档系列

• OB数据库存储架构：https://www.oceanbase.com/docs/oceanbase-database/oceanbase-d...

• OB数据存储管理：https://www.oceanbase.com/docs/oceanbase-database/oceanbase-d...

• OB数据库压缩个性：https://zhuanlan.zhihu.com/p/49161275

• OB存储引擎详解：https://www.modb.pro/db/137286

• OB博客文章全系列：https://open.oceanbase.com/articles

\2. 其余

• LZ4 Benchmark : https://github.com/lz4/lz4

欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/