数据库内核杂谈 - 存储

马上农历新年了，在这里，给大家拜个早年，祝大家新年快乐，"猪"事顺利！

再和大家说声抱歉，这数据库内核杂谈的第三篇-存储，让大家久等了，由于种种原因(主要是懒)，拖了这么久。新一年，立个flag，做到每个月一篇，希望自己能够坚持下来。

言归正传，来谈存储。数据库是用来存储海量数据的。存储如此大量的数据，自然而然想到的就是以文件的形式存储在硬盘(HDD或SSD)中。当然，一些商用数据库为了追求性能，是将数据优先存储在内存中(比如SAP的HANA和MemSQL)来获得更高速的读写。本文主要涉及的是关系型数据库针对硬盘的存储。对于内存数据库来说，依然需要硬盘作为备份或者2级存储，所以相关知识也是适用的。

相较于列举常见的存储形式然后对比优缺点的分类法，我们今天另辟蹊径，从"演化论"的角度来看，不同的存储形式和优化方法是怎么一步一步进化出来的。

一个数据库存的是什么呢？这里简单介绍一下关系模型(relational model: https://en.wikipedia.org/wiki/Relational_model)。关系模型由 Ted Codd1970年提出，关系模型定义了所有的数据都是以元组(tuple)的形式存在，每个元组定义了多个属性(attribute)的键值对，多个含有相同属性的元组排列在一起就形成了一个关系(relation)。元组，属性和关系对应到数据库中的概念就是行(row)，列(column), 和表(table)。一个表定义了多个column，每个column有一个type，每个row对应于每一个column都有一个取值(取值满足type的定义)，每个表又由多个row构成。不同的数据库虽然有库（database)，schema或者命名空间(namespace)等不同级别的逻辑抽象，但是表却是每个关系型数据库最基本的存储对象。

好了，确认了数据库需要存储的基本单元是表。那么给定一张表，应该怎么存在文件中呢？如果还能回想起上一讲的内容，你会说，可以用comma-separated-value(CSV)格式的文件来存储。确实，CSV文件中的每一行对应于一条row，每个row的不同column用逗号隔开，一个文件对应了一张表。下图截取了一段Titanic幸存者的CSV文件。

titanic_survivor.csv

这样的一一对应确实清楚。那么问题来了，上述的CSV形式有什么缺点吗？有些读者发现了，文件里并没有定义column的类型和命名。我们来看应该怎样补全这个定义。方法一，我们把CSV文件的第一行预留给column的定义，如下图所示，补上了所有column的命名(原文中并没有定义类型，我们可以自行脑补，在每个column后面加入"(type)")。

titanic_survivor_with_header.csv

方法二，把column的定义(我们通常称之为表的元数据)和数据分开存储。比如存在一个叫titanic_survivor.header的文件中，下图给了文件的示意。

titanic_survivor.header

比较这两种方法，哪一种更好呢？我们可以从支持数据库操作的角度出发来看。对于表，数据库系统会支持新增一个新属性，修改或删除已有属性。如果把属性放在csv文件的第一行，对于任何一种属性操作，需要对文件进行大量的改动：对于删除一个已有属性，需要删除所有行的对应数据来保证CSV文件的有效性，对于新增一个新属性，同样需要修改每一行。如果数据文件非常大(1 billion rows), 会消耗大量时间来更新数据。对于第二种方法，修改的代价就小很多，只需要对header文件进行修改即可。你可能会有疑问，如果单单修改header文件，岂不是和数据文件就对应不上了。一个可行的解决方案就是在对header文件修改时，加上标注。比如对于删除一个现有属性，只需要标注这个属性被删除，并不直接在header文件里删除这个属性的定义。当数据库对表的数据进行读取时，我们只需要同时读取header文件，然后根据最新的定义，对于读取的每一行数据，忽略已经被删除的属性值即可。同理，当新增一个新属性时，标注这是一个新属性，并给定默认值(不给定数据库会定义为NULL)，那在读取每一行数据时，如果没有新属性，就赋予默认值即可。

这种分离元数据和数据的另一个好处在于，方便数据库统一管理所有表的元数据。几乎所有的数据库都会提供类似于information schema的功能，用来显示数据库的各种元数据。比如有几个namespace，对于每个namespace分别有几个表，每个表都有哪些属性。单独存储表的属性就更方便读取和管理。 

为了更好得支对表的元数据的管理和变更操作，我们从原有的csv文件进化出了第一个特性，分离元数据和数据的存储。

讨论完了元数据的管理，我们再来看CSV文件对于其他常见的数据库操作还有什么做得不够好的。除了最频繁的查询语句，另一类常见的操作就是添加，修改或者删除表里的数据。对于添加，我们只需要将新数据添加到文件的末尾。对于修改，如改变某一行的某一个属性或删除某一行，就需要在数据文件中进行修改。相较于在文件末尾添加，文件中的修改会低效很多，尤其是当数据文件特别大的时候。

有什么思路来改进呢？那些数据库先贤就想了一招，分开管理的思路也可以用在数据本身呢。设想一下，除了CSV存放每一行数据外，我们再单独维护一个slot_table的文件，这个文件存啥呢，就存对应CSV数据文件每一行的标注信息，比如对应原始的CSV文件，我们先生成对应的slot_table如下：

tianic_survivor.slot_table

对应每一行，我们标注V表示(valid)。对应于新增数据操作，我们只要同时append数据行和slot_table行即可。如果我们现在执行了一个更新语句，删除姓名起始为"Cumings"的数据，那第二行的数据就要被删除。对应的，我们可以不用修改CSV文件，只是把slot_table中的2:V改为2:D(deleted)。如果要执行更新语句呢，比如把姓名为"Braund, Mr. Owen Harris"年龄纪录更新成37岁，这又应该怎么操作呢？我们可以在数据文件中添加一行新数据(第9行)，这行数据复制了第一行但是把年龄改成37。在slot_table文件中把1改为D,然后添加9:V。修改后的slot_table和数据文件如下：

updated titanic_survivor.slot_table updated titanic_survivor.csv (line 9)

读者可能会发问，虽然保证了数据文件的append only，但是slot_table还是会在文件中进行修改，如果数据量一大，依然会增加读写负担。还能不能进一步优化？答案是可以的。我们其实可以把标注信息也以append only的形式添加到slot_table中，比如上述的删除和修改操作完成后，slot_table如下：

append only titanic_survivor.slot_table

然后在读取数据的时候，先读取slot_table，然后逆序读取所有行的标注信息(读取到2D后就忽略第二行)，就能知道哪些行是有效的，哪些行可以略过不用读取了。

对于数据的增删改，我们已经可以对数据文件和slot_table都实现append_only。还有什么问题吗？对于一个数据表，每次操作都会添加新信息，久而久之，数据文件越来越大，而且无效的行越来越多，岂不是很浪费空间。有什么办法可以优化呢？有。数据库都会支持vacuum操作(或者叫compact)，这个操作所做的就是读取数据文件和slot_table，然后根据标注把有效的数据行写回新的文件。比如，对我们的示例进行vacuum操作，新的数据文件和slot_table如下所示:

vacuumed titanic_survivor.csv vacuumed titanic_survivor.slot_table

为了更高效地实现增删改数据，我们引入了第二个特性，slot_table以及标注信息来纪录对数据的增删改，并且引入vacuum操作定期清理无用的行数据。

对于CSV，还有什么能改进的吗？你可能已经发现了，CSV是用明文来存储数据，太低效了。比如对应一个boolean的类型，明文存成true或者false，如果用ascii编码就是32或者40个bit(按照8bit的extended ascii编码)。但如果用byte存储，只要1个bit即可(即便是用0,1明文来存储boolean也还是没有byte高效)。CSV为了方便用户直接能够理解，所以牺牲了效率。但是数据文件完全由数据库系统管理和读取，可以存储raw byte配上高效的编码和解码算法来进一步优化。那如何才能更高效得存储呢？这里我就不给出具体的实现了，可以参考现在流行的RPC框架比如Thrift(https://thrift.apache.org/)和Protocol Buffers(https://developers.google.com/protocol-buffers/)，这些网络端传输数据的协议，为了追求效率对数据的编码和解码有很多优化。相对应的，slot_table里存储的不再只是行号，而应该是该条数据对应在文件中的byte offset。

为了更高效得存储数据，我们引入了第三个特性，用raw byte来存储数据配合高效的编码和解码算法来加速读取和写入。

还有什么能再进一步优化吗？说下一步优化前，我们先来了解这样一类数据库。这类数据库并不进行修改和添加操作，但是存储了大量的数据，并且要运行大量非常复杂的分析语句。没错，这类数据库是数据仓库(Data warehouse)。区别于普通的Online transactional processing(OLTP)的数据库，通过抓取，清洗和变化OLTP数据库的数据然后导入到数据仓库负责分析报表等需要查询大量历史数据的复杂语句。这类数据库的表结构称之为雪花模型(snowflake schema)，由一张或者多张的实体数据表(entity table)，配合一些辅助表(英文里称dimension table)。实体数据表通常是交易记录等存有大量数据(亿甚至千亿级别)，辅助表则只有少量的相关信息比如国家，商户等的具体信息。下图引用了TPC-H(非常有名的数据库基准测试)的雪花模型(from https://www.researchgate.net/figure/Snowflake-Schema-based-on-TPC-H_fig1_37684343)，其中表lineitem_orders就是一个包含所有交易纪录的实体表。

TPC-H snowflake schema

实体表不仅有大量数据行，属性也很多(100到200都很常见)。可是，大部分的分析报表语句仅需要读取相关的几个属性(列)。为了运行该语句，就需要把整个实体表的数据读到内存中来抽取需要的属性列。设想一个实体表有100个属性，10亿条数据，但某个语句只需要用到3个属性。按照CSV方式读取数据，97%的数据是没有用处的。贪得无厌的数据库的大牛想，有什么办法可以优化需要读取的数据吗？于是列存(column-oriented store)就这样出现了。

类似于CSV这样把每一个tuple的数据存放在一起的存储方式叫行存(row-oriented store)。相对应的列存，就是指把一个表的每个属性， 单独存在一个数据文件中。还是沿用上面titanic的例子，我们会有单独的数据文件(还有slot_table文件)来存储姓名，船票价格，登船码头，等等。在读取的时候，根据查询语句需求，需要用到哪个属性就读取哪个属性的数据文件。按照前面的例子，我们只需要读取原来的3个属性的数据文件，读取速度自然就提高了。

除了可以避免读取不必要的数据，列存还能带来什么优势？因为每一列的类型是相同的，比如都是整形或者是字符串。在存储同类型的数据时，压缩算法能够更有效地进行压缩，使得数据量更近一步减少，来加快读取速度。举个简单的例子，上述titanic的例子中有一列Cabin纪录了仓位信息(假设值分为A1，A2，A3，B1，...等)，相较于对于每一行都直接用字符串来存储，我们可以采用下面enum的压缩方式。因为仓位类型不多，所以对于每一行，只需要用tiny就能存下是哪个仓位了。只需要数据库系统在读取数据的时候根据meta把对应数据换出即可。

cabin.titanic_survivor.column_store

为了应对数据仓库中复杂报表的查询语句和超大量的数据读取，我们引入了第四个优化，把行存转换为列存，并且由于存储的数据是一个类型的，可以进一步用压缩算法来优化数据量。

小结

至此，我们从最原始的使用CSV文件格式来存储数据，一步一步根据数据库的操作需要，"进化"出了下面这些优化方法: 

1) 为了更好得支持对表的元数据的管理和变更操作, 分离元数据和数据的存储

2) 为了更高效地实现增删改数据，引入slot_table以及标注信息来纪录对数据的增删改，并且引入vacuum操作定期清理无用的行数据

3) 为了更高效得存储数据，用byte来存储数据配合高效的编码和解码算法来加速读取和写入

4) 为了应对数据仓库中复杂报表的查询语句和超大量的数据读取，引入列存概念，并且用压缩算法来进一步优化数据量

具体到真正数据库的实现，还有无数各个方面的工程优化。比如，为了提高从文件系统读取数据到内存的速度，把文件块的大小设置得和内存页一致，用内置的缓存机制来提前换进和换出数据页(相对于操作系统的默认缓存机制，数据库系统更清楚哪些数据会一起被使用从而可以提前做好准备)。但是各种优化，也并不是数据库大牛拍脑袋想出来的。而是针对问题，提出思路和解决方案，一步一步实践出来的。所以面对工作中的工程问题，我们也应该本着这种心态去处理和解决。

最后留个坑，虽然列存的实现，使得我们不用读取无用列的数据，但针对某些点查询的语句(point query)，比如"select col2 from table1 where col1 = 10", 我们依然需要读取col1和col2两列的全部数据。有什么办法可以优化这类查询吗？下一期，我们接着聊这类优化-索引(indexing)。