本文首发于2018年。
作者：冯轲（千路），OceanBase架构师。
我们做到了什么？
在SSD成为在线业务标准存储的今天，存储容量已经越来越成为制约整个IT系统部署密度、影响系统成本的主要因素。对于数据库来说，解决这个问题的办法有很多，数据库压缩就是其中一种重要的优化技术，这种技术的好处在于对业务逻辑透明，同时对于在线库和历史库都适用。
说到数据库压缩，很容易让人联想到数据压缩，联想到lz4、snappy、zstd、zlib这些通用压缩算法，应该说，这些通用的压缩算法已经在数据库中被广泛地采用，在OceanBase1.0中，我们已经引入了这些算法作为后端压缩并取得了非常好的压缩效果，但它们并不是数据库压缩的全部。
在OceanBase 2.0中，我们引入了一个全新的高级数据压缩特性（Advanced Compression），新特性包括一种全新设计的行列混合存储结构（PAX），以及高效的数据编码技术（Encoding）。高级数据压缩特性可以实现在使用相同的后端压缩下，存储空间大幅减少，从目前已经上线的业务来看，所有业务在引入该特性后，其存储空间都至少降低了1/3，部分业务甚至获得了存储空间减半的效果。重要的是，实现这样的一个目标，系统并没有损失任何性能，我们的查询性能基本没有变化，我们的写入（合并）性能反而较原有系统有了较大的提升。
这听上去有点天方夜谈，为什么使用相同的压缩算法，最后的存储空间差距会如此之大呢？其实回答这个问题很简单，关键就在于数据压缩 ≠ 数据库压缩。
通用的数据压缩算法并不是为数据库专门设计的，这些压缩算法将输入看成是一个连续的字节流，并基于一些经典的编码算法，比如串编码（lzw）、嫡商编码（huffman、代数编码）来实现对信息的压缩。但数据库中存放的是结构化数据，数据中存在着明确的字段边界，以及丰富的类型信息，利用这些信息，采用一定的数据编码技术，就可以实现比直接使用通用压缩算法好得多的压缩效果。
数据编码技术并不是OceanBase的首创，十年来，数据编码技术已经广泛地用在各种分析型数据库中，比如著名的商业分析型数据库产品Vertica，就曾经成功地将OLAP领域世界标准测试基准TPC-H的数据压缩到了6：1，这是目前任何通用压缩算法所无法达到的高度。但是将完整的数据编码技术用于OLTP在线数据库，应该说OceanBase的尝试属业内首次，这背后包含了我们对现有OceanBase存储架构的理解，以及对一些很有挑战性的优化目标的实现。
接下来我会详细地说明，OceanBase到底实现了哪些数据编码技术，我们是如何做到在引入这些编码技术的同时，系统的性能不降低；有些读者会问，既然这些编码技术那么好，为什么传统的在线数据库，比如ORACLE、MySQL中不采用这种技术，这个问题我也会在本文中回答。
OceanBase如何实现高压缩？
OceanBase 2.0通过数据编码技术实现高压缩。数据编码是基于数据库关系表中不同字段的值域和类型信息，所产生的一系列的编码方式，它比通用的压缩算法更懂数据，从而能够实现更高的压缩效率。
首先，数据编码按照列编码，我们知道：按列压缩会比按行压缩更有效，这是因为关系表从列的方向去看，相邻字段由于具有相同数据类型和值域范围，其数据的相似性要远远好于从行的维度，这个是已经被业界广泛证明的了。
另外，数据编码使得同一个数据块中能够容纳更多的数据，我们知道：更大的输入有利于压缩。
在引入数据编码技术之后，OceanBase 2.0在原有的行存存储结构上，新增了一种新的行列混合存储结构。在这种存储结构中，同一行的所有数据仍然存放在一个数据块中，但在该数据块内的所有行按照列进行存储。新的存储结构在实现高效压缩的同时，能够非常好地兼顾OLTP与OLAP业务的性能需求。
数据编码有利于提高查询性能，这是因为编码后的数据不需要解码，就可以直接支持部分查询，而即使最快速的lz4压缩算法，也需要在数据访问前将整个数据块进行解压。我们做个简单的计算，假设1GB的数据，直接通过lz4压缩，变成500MB，现在我们先通过数据编码，把它变成了400MB，再通过lz4压缩，把它变成了250MB，可以看到，我们调用lz4压缩算法的输入和输出长度，是数据编码后的长度，与原始长度相比大大减小了，系统整体的写入和查询能力，更依赖于数据编码，而不是后端的通用压缩算法。这意味着：
1）我们的解码速度实际上是提高了，因为数据编码不需要解码即可查询；
2）未来我们可以在系统中引入一些压缩率更好、但是编解码速度相对较差的压缩算法，比如zstd，后者的性能劣势将会被数据编码进行很好地补偿。
目前所有的这些，听上去都有些抽象，下面我具体的介绍一下目前OceanBase 2.0已经支持的数据编码方法。
- 字典编码：所有数据编码技术中最常用、也是最有效的方法。字典编码的思想很简单，就是把重复性较高的数据进行去重，把去重后的数据建立字典，而把原来存放数据的地方存成指向特定字典下标的引用。
- 数据的访问逻辑是非常直接的，没有解码过程。特别要注意，字典中的各数据是按类型序排序的，这样做有两个好处：一是有序的数据更有利于压缩；二是有序的数据意味着我们在做谓词计算时，可以将谓词逻辑直接下压到字典，并通过二分逻辑完成快速迭代，这点在我们支持复杂计算时，将发挥非常重要的作用。
- RLE编码：适用于连续相等的数据，比如形如1，1，1，2，2，...之类的，我们可以把这些连续相等的数据去重，并只保留其起始行号，RLE编码在数据库中主要用于处理有序的数据（比如索引的前缀）。
- 常量编码：针对近似常量化的数据，编码识别一个最常见的数据作为常量，而只记录所有不等于这个常量的异常值和它们的行号，常量编码在实际业务数据中非常有用，后者往往存在着一些业务增加、但是并不使用的字段，这些字段同样占据了空间，并呈现出常量化（默认值）的数据分布。
- 差值（数值型）编码：适用于在一个小值域范围内分布的整数型数据，通过计算区间内的MIN、MAX，将数据减去MIN后，用更小的位宽进行编码。比较常见的数据是时间类型，连续生成的时间类型数据通常有非常好的局部性（比如差值在几秒钟以内）。
- 差值（定长字符型）编码：适用于定长的、有确定业务规则的字符型数据，通过构造公共串，将数据中只记录差异部分。这类数据在业务中非常常见，通常用于主键，比如订单号、用户账号等。
- 前缀（字符型）编码：适用于前缀相同的字符型数据，通过构造公共前缀，将数据中只记录差异的后缀。这个不用多说了吧，其它一些数据库，比如SQL Server、HBase中也经常使用，这类数据在业务中也很常见，比如部分主键。
- 前面提到的数据编码都是列内编码，即只考虑同一列内各字段的数据相似性，除此之外，OceanBase还实现了一组列间的数据编码，也就是考虑同一行的不同列间数据的相似性。
- 列间（数值型）编码：适用于两列近似相等的整数型数据，这样，其中的一列只需要存储和另一列的差异值。这种列间相等的数据编码有它很强的适用场景，比如我们知道业务在数据表中通常都会记录生成和最近一次更新的时间戳，如果某些流水数据从不会发生更新，那么这两个字段就存在很强的列间相等关系。
- 列间（字符型）编码：适用于两列存在子串关系的字符型数据，也就是一列是另一列的子串（包括前缀、后缀、相等关系）。实际业务中许多长字符型字段并不是由用户随意生成的，而是基于一定的业务规则，将多个基础字段拼接而成，这时候这些基础字段就和前者存在子串关系。
仔细去看一看这些数据编码，会发现它们都具有相同的特征：解码过程非常简单，解码特定一行的数据，并不需要依赖其它行，这种近似O(1)复杂度的设计提高了数据投影的性能，使得其可以被用于在线系统。
了解OceanBase的同学都知道，OceanBase存储架构是基于LSM-Tree的，其中基线数据是采用两层缓存结构，原始（外存）数据存放在块缓存中，热点数据存放在行缓存中，行缓存与增量数据一起，用于实现对在线处理的高效支持，这意味着，我们只需要在二级缓存，也就是块缓存中保留这种数据编码格式，而在将其转入行缓存时，我们仍然可以选择还原出完整的行数据来进一步加速投影的性能。
性能是引入数据编码技术需要考虑的重点问题，我在设计将数据编码引入OceanBase之初，已经仔细权衡过了这一点，相对来说，数据编码后的压缩率和查询性能并不是太大的问题，那个完全是可以预期的，真正需要担心的是编码速度，也就是写入能力，这也是我们在实现中遇到的最大的技术挑战。我们希望在引入数据编码后，系统的写入能力，或者说合并性能，不仅不会降低，还会比原有水平有显著提升。
这是一个巨大的技术挑战！有那么多的编码方法需要支持，那么问题就来了，我们应该怎么样为每一列选择最合适的数据编码呢？我们给自己设定的第一个目标是：这个选择过程必须由数据库自己来完成，而不是交给业务或DBA。这个决策的业务价值不用我解释，但做出这个决策，确实使得我们的目标达成变得异常困难。数据库自动为每一列选择合适的数据编码，这个选择过程是非常耗时的，如何保证编码性能？
对于智能选择算法的讨论，已经远远超出了本文的讨论范围，事实上这也是我们到目前为止一直还在优化的工作重点之一。这里我想提的并不是这个，而是另一个重要的优化，就是对于同一张业务表，其数据分布是具有很强的稳定性的，具体地说，如果我们在上一个数据块中，选择某一列应该使用字典编码，那么在下一个数据块中，我们认为这列有非常大的概率，仍然会使用字典编码，因此我们可以直接尝试对该列进行字典编码，如果编码后的反馈（压缩比）证明这种选择是正确的，那么我们成功了，否则我们会尽快退出，重新在该列上开启自动选择。
这个过程的实现远比听上去要复杂，这意味着我们需要为每种编码方法至少设计两种编码实现：自动选择和指定编码。优化的空间一下被打开了，代码量和系统的复杂度也随之上升。不过需要注意到，至今为止，我们所有涉及到的改动只有块内格式，在这种局部收敛的地方，实现得复杂一点并没有什么关系。
能够实现编码方法在块间复用，是我们认为有可能实现基础合并性能大幅提升的重要基础，但是这个重要基础最根本的来源，是因为OceanBase独特的存储架构，是因为其支持批量更新的能力所决定的。
为什么传统在线数据库难以实现高压缩？
传统在线数据库无法实现高压缩，这是由它们的存储架构决定的。这些传统的数据库产品，包括ORACLE、MySQL等，它们的存储架构的基础是数据按照固定长度的块进行组织，对数据的更新是立即作用到块上，这种存储架构我们把它叫做原地更新。设计这种原地更新的存储架构，是有其历史原因的，因为对于早期的硬盘来说，IOPS和带宽都是大问题，所有的数据设计都是面向如何优化IO来进行的，而当时的CPU资源是非常珍贵的，因此数据压缩被认为是非常昂贵、只能够在部分离线业务中使用的选择。
从技术原理上去解释为什么这种原地更新的存储架构，无法实现高效的数据库压缩，我觉得有三点可以谈谈。
第一点，是关于定长块的基础假设，所有块必须是定长的，这种假设大大简化了数据库的底层结构设计，但是当引入压缩算法时问题来了，压缩之后如何保证块是定长的？我们不可能事先知道，多大的数据在通过lz4压缩后，正好会是16KB。所以我们很难在商业OLTP数据库中，看到直接引入通用压缩的例子。
MySQL在其新产品5.7中解决了这个问题，它的解决方案是长度不变，也就是一个16KB的块，不管它被压缩后长度是多少，都继续按照16KB长度进行存储，但是文件系统只会为实际的数据分配空间。打个比方，如果16KB数据压缩后是10KB，假设扇区长度是4KB（SSD），那么压缩后的数据在存储上仍是按16KB存放，但是由于其实际只占用了3个扇区，所以最后一个扇区文件系统并不会实际分配空间。
MySQL的这种方式很好地利用了文件系统提供的空洞能力，最大好处是地址空间没有变化，所以对整个块压缩以上的处理逻辑来说，是完全透明的，因此这种技术也被称为Transparent Page Compression。但这种实现方案也有其缺点：首先我们会浪费掉半个扇区，在上面那个例子中，我们平均会浪费1/8的存储空间；第二，如果数据在开始生成时比较小，但是随着持续更新而不断膨胀的时候，意味着我们需要文件系统去不断动态地填补那些当初留下的空洞的时候，严重的IO碎化问题随之而来，这种不断增长的场景是所有块内原地更新的存储架构很难支持的。
而OceanBase的存储架构中完全没有这种问题，任何在线更新并不立即作用于基础数据块，而是在合并时，以批量重写的方式进行，我们对于块长度有一定的长度分布要求，但是并不要求它们定长！
第二点，为了保证性能，原地更新的存储架构在设计块存储格式时，需要重点考虑对于在线更新的支持，而这和数据编码的设计原则是冲突的，我们知道，数据压缩本质上更适合一次生成、反复查询，而不适合实时更新。比如，如果一列当前使用字典编码，这时应用将其中某个值更新成了当前字典中不存在的值怎么办？如果一列使用差值（整数型）编码，新插入的数据比MAX还大怎么办？这意味着我们修改个字段的同时，可能导致该列的所有字段都被修改，这在性能上是无法接受的。
从11g开始，ORACLE在其产品中首次引入了OLTP压缩技术（Table Compression），这本质上是一种字典编码技术。为了减少引入编码后的性能损失，ORACLE做了一个简单的优化，也就是数据一开始按照非压缩格式进行存储，当存满一个块（达到PCTFREE限制）时，尝试对块内的所有数据进行字典编码，编码并不是按列、而是全局进行的，压缩完成后，后续插入的数据会先比较字典，如果能够去重，则存放字典下标。即使实现了这些优化，ORACLE也要求应用开发者谨慎使用这一特性，因为它会对更新性能造成明显的影响。可以看到，在传统数据库的理念中，频繁更新的表都是不适合压缩的。
而OceanBase的存储架构中完全没有这种问题，增量数据和基线数据是完全分离的，这意味着我们实际上是为了在线更新和紧凑存储各自设计了一套存储格式，我们把这个难解的问题一分为二了！
第三点，我们在OceanBase的设计中已经看到，引入多种数据编码带来的一个重要挑战，是你如何快速地决定应该为每一列选择最合适的数据编码。在OceanBase中，我们通过支持块间重用编码方法来显著提升编码性能，同时又保持对数据变化的敏感性（退出机制）。
而在原地更新的存储架构中，这种优化变得非常困难，因为这种架构下数据的持久化，是发生在缓存中的脏块被写回时，这是一种以块为窗口、准实时更新的方式，这时候让系统去了解这个脏块相邻的块的编码方法是难以实现的。这也是为什么数据编码这种技术在以批量导入的分析型数据库中大行其道，但在传统在线数据库中难以见到的重要原因。
一些后续工作
我们差不多花了一年多的时间来仔细地设计各种数据编码技术，研究如何解决不同的编码方法的智能选择问题，并不断提高性能。最终我们将其中成熟的部分发布到OceanBase 2.0中，并已经开始在部分业务中上线应用。
新特性极大地降低了系统的存储成本，并显著增加了基于SSD存储的数据库集群的部署密度。一个明显的例子是：在这个新特性发布之后，我们更新了我们原有的经验公式，即过去我们将MySQL的业务迁移至OceanBase时，我们通常会按照4:1来进行容量规划，现在，这个经验公式变成了6:1。所以重点是，客户通过使用我们的高级压缩特性会得到什么？客户会得到一个存储空间接近减半、写入能力显著提升、查询性能无影响的全新的数据库产品，而得到这种能力，并不需要我们的客户付出任何人工干预的成本，再没有比这更让人感到愉悦的事情了。
我们在设计中也规划了一些其它更复杂的数据编码，比如差值（逐行）编码、组合编码、列间（推导）编码等，这些编码在压缩效果上，可能比现有的数据编码更加有效，但是它们的缺点在于解码性能。我们会在OceanBase后续的发布版本中尝试引入这些数据编码，客户可以将其用于历史库等一些成本敏感型的业务场景中。
最后，细心的读者可能已经注意到了，我在前面说字典编码的时候，提到过其有序的字典组织非常适合于处理复杂查询中的谓词计算，这是另外一个巨大的优化方向，字典编码的这种优化也只是冰山中的一角。对于HTAP混合负载场景的支持，将会成为今后一段时间我们的工作重点，这个能帮助我们去适应客户更为复杂的应用场景，真正去实现一个通用的商业数据库应有的重要能力。
等到有一天，在OceanBase已经具备非常优秀的计算能力的时候，我们再回过头来看我们今天所做的工作，会发现：数据编码技术，并不是一种简单的数据压缩方法，它是真正和SQL处理、数据存取深度结合起来，从而能够全面提升数据库存储和计算能力的完整的解决方案。
