前面两篇讲解基本数据系统设计原则和还有如何把现实生活中的对象关系抽象成一个数据模型，被存储的数据可以通过一个特定统一的API访问接口进行访问，而且能保证安全控制。但是问题是怎么存储这些数据？如何把这些结构化和非结构化的数据做存储？数据如何编码？本文为DDIA书的数据编码和索引章节的整理和总结。
如果是一名应用开发程序员是可以不用关注数据是如何存储和如何快速被查询到的。如果对存储和数据检索非常感兴趣可以看看这篇内容，看完你可以自己实现一套存储引擎玩，在实际开发过程中也能从现有的存储引擎中找出一个适合业务场景来使用，知其然知其所以然。
数据存储和编码的方式会影响一些特定场景的性能，例如选择是OLTP还是OLAP？两种方式都有具体应用场景，那对应的底层数据存储格式和编码方式就有要求了，所以使用者要对每种存储方式有充分了解，才能如何选择好用何种存储来组建一个大型数据系统。
现在还有OLTP和OLAP联合一起做的HTAP型的数据库，这是由Gartner公司发明的名词，指既可以用做联机数据处理，也可以用做线上数据分析的混合应用数据库架构。
列式和行式存储
相比计算机内存管理磁盘上的数据就要复杂的多了，因为计算机内存由操作系统帮助我们管理者。基于内存的编程也比在硬盘上编程要简单，而在磁盘上存储数据相比我们必须考虑如何组织数据和管理数据，数据序列化格式，怎么释放存储空间，怎么整理磁盘碎片等...这些非常复杂，但是操作系统为我们提供了更好文件系统结构，对应存储引擎开发者来说我们可以基于现有的文件系统来做开发。
一个组数据在关系模型中会被存储为一张表，而表又是列和行组成的，字段是列和行的交集如图上的Job字段，例如某一列的字段有相同的属性和数据类型，如果我们定义一个用户名字段为字符串类型那么这一列都是相同类型；而多个列中的字段可以组成一行，也就是一条数据记录集合，当多个行记录集合就可以构建一个表。那问题哪来了？如何把这些表中记录存储在底层的磁盘中？用什么样的方式存储呢？
在计算机硬盘上的数据布局是以快进行划分布局的，可以查看这篇文章Linux文件系统设计，磁盘在存储数据和访问数据都是按照固定大小快进行读写；如果把表中同一行的列数据存储在一块中，这样的存储方式就是行式存储，当访问整条记录时非常有用，但是如果是访问某个特定字段时就不那么理想因为其他字段数据也在被访问的数据块中。
而面向列式存储就是把一列的相同类型数据存储在一数据块里，在这种存储布局下我们每次读取一数据块就相当于读取一类数据信息，这样使得面向一些数据分析场景性能不错，不需要去像行式存储那样需要把不符合条件的数据过滤掉，来回频繁读取多个数据块获取需要的列的内容；主要适合于批量数据处理和即时查询。相对应的是行式数据库，数据以行相关的存储体系架构进行空间分配，主要适合于小批量的数据处理，常用于联机事务型数据处理。
面向列的存储方式好处还不只是访问方式的问题，如果你知道CPU读取数据工作原理的话，同类型的数据还能被连续的缓存起来，提高缓存利用率和计算利用率；另外相同的数据类型可以通过特定算法进行数据压缩，可以根据不同的数据类型采用不同压缩方法。
列和行的存储方式区别，你可以想象成一个果篮，面向行的篮子里面装的水果都是很多种类，而面向列的篮子里的水果种类是就一类为同类，如果让快速取出5个为一类的水果，你觉得哪种方式最快？这就要取决于你访问方式了，换到数据库中就是你要读取一行数据所有列的集合那就使用行，而如果要跨多行并且要在某一列上做计算那还是推荐列存储。
存储引擎
存储引擎的索引分成两种版本，一种是日志结构化的引擎，另外一种就是面向页面的存储引擎，面向日志型的存储有Bitcask和而面向页面存储的有B-Tree。
这里的日志是指的是数据写入的方式，传统我们打开一个文件要修改某个内容的时候就需要找到对应的行进行操作然后保存修改，而用日志的方式数据写入的方式采用追加的方式，这样我们就不需要磁盘寻到了，这些数据可能被程序通过特定的方式进行编码而存储的，对普通人类来说无法查看其内容的，要通过特定的方式进行编解码操作。
日志只是每条数据存储记录的方式，而上层通过特定的API接口去访问数据时就要快速查找到那条记录，此时就要索引来配合了。但是索引是一种数据结构，每次索引变动都需要一次对应的数据结构变更，而变更是要付出性能代价的，不能像日志的方式直接追加，并且部分索引要在内存中维护，这是本篇要探讨的问题。
关于我这里有最简单Bitcask引擎的设计例如你可以查看这篇文章：Bitcask Design Paper，这是最简单的日志结构模式的设计与实现。这种基于内存索引的实现局限还是蛮多的，索引在内存中是断电丢失的，并且内存大小有局限性也不能支持范围扫描，从头开始查找某一个指定的键，这是很费时间的。如果数据在内存的缓存里面还可以不用读取文件，如果没有缓存上但是另外一个就是频繁操作IO，就怕小文段操作。
SSTable和LSM-Tree
前面写了Bitcask模型一些简单和实现原理，每次写入数据的时候都直接操作一个值，然后将其刷入到文件中，由于每次都是顺序写入所以在一个文件中的值后面值优先前面一个值，文件中的键是无序的像要支持范围扫描你得弄成有序存储，但是这又违背顺序写的设计原则！怎么解决？有什么办法吗？如果部分开发者应该接触过大文件排序问题，这里我们就可以借助这个思想？类似于归并排序的思路分治法，先在内存中进行排序，然后写入到文件中，然后每个文件就是有序的，然后对这些文件在进行递归操作，这个思路就是本节要讲的SSTable和LSM-Tree。
LSM-Tree的原理是什么？当我写入一个键值对的时候我将其插入到内存中的一个有序结构，这个有序结构可以是二叉搜索树，也可以红黑树等，只要能按照键进行排序的数据结构就可以。这里可以给内存表设置一个大小，当达到阀值的时候就将其写入到指定的一个文件中保存，然后继续在内存中创建一个内存表结构继续读入外部的输入，归档的文件段都是有序的SSTable了，这里称之为排序字符串表，总体流程如下图：
这里注意的是Write ahead Logging，WAL文件的内容是每次当外部调用写入操作的时候要存储的操作记录信息，这个信息是为了防止内存表数据丢失导致的。WAL的生命周期和内存表生命周期是一致的，如果内存表被持久化到磁盘的SSTable文件中，WAL文件也会被重新创建的，也就是存储引擎在工作的时候内存表和WAL也是一致的，这里的一致并不是说内容是一致的，而是说一个WAL和内存表的生命周期是一致的，WAL内容写入顺序取决于请求顺序，WAL文件内容结构如下：
这里的WAL编码方式和Bitcask中的日志记录方式非常接近，只需要记录操作的类型和具体的数据内容启始位置和大小即可，如果需要从WAL恢复数据则从头部读取9字节获取数据偏移量，后面的记录在偏移量基础上以此类推。
下面图就为Sorted String Tables)结构图，SST的特征是每个段中的键值都是经过排序而组成的段，因此多个SST文件合并的时候非常高效，只需要比较每个SST段文件中第一个键的大小，然后将最新的那个键根据排序的顺序写入到文件中，重复这个过程就可以合并出一个新的大文件，丢弃小的旧文件即可。
相比Bitcask那种将索引全部保存在内存中，而SST的方式因为每个段文件都是有序的我们只需要建立一个稀疏索引就可以，如果要查找某个键只需要找到符合稀疏索引区间就可以，读取对应文件数据段查找符合条件的数据即可，如果没有查找到直接返回即可；这里的段文件查找还能做优化，因为是有序的可以使用二分查找来开始搜索到目标。
另外如果是相同的键还可以共享前缀来实现，例如共享前缀字符，这样后面有相同前缀的键结构可以不需要存储完整的键，直接存储共享的键的字符串大小即可拼起完整的数据记录。
因为有了SST的方式，可以存储比内存数据大的多的数据，但是带来另外一个问题就是键太多了，不知道是否存在某个键，这里可以使用布隆过滤器做查找优化，a、b、c都代表一个散列函数，其结构可以去操作一个bits位图中的值，原理图如下：
内存表刷入到磁盘上了之后，大家都知道一个键值长度不是固定的，如果我们要在查找某个键的值怎么办呢？这个值肯定是不确定长度的，就需要一个索引来记录每个键的值的长度的偏移量；此时就要为每个SST中的数据建立一个索引了，这个也叫索引区，但是这个索引区放哪里呢？一般可以将这个索引区放到SST末尾处，但是这个索引区也是不确定大小，还需要一个SST元数据区，用来记录数据区和索引区的大小分界用的，光文字描述这个不好理解，下面是我画一副图：
通过上面这种方式进行数据编码分区，我们在查找数据就很容易解码了，我们只需要反向读取数据就可以，这里的MetaData存储就是索引区大小和数据区大小的信息，先读索引区再通过索引去读数据区中的值即可，例如获取索引区头部偏移量伪代码实现如下：
public class MetaInfo {
private String path;
private Integer size;
private Integer indexAreaSize;
private Integer dataAreaSize;
// 这个就算出来索引区其实位置偏移量
// 读取的从这个偏移量加上offset即可获取整个索引区数据
// 假设2^6是元数据信息大小
public int getIndexAreaOffset() {
return this.size - (2^6) - this.indexAreaSize;
}
}数据压缩
由于这样的设计会带来另外一个问题就是随着时间增长，被刷入的到磁盘的中的SST持久化文件也越来越多；和我们日志使用一些日志库记录日志一样例如Log4j，新的记录永远高于旧的记录，这些记录是重复存储在磁盘上的SST文件中，此时就要去淘汰吊老的文件中的记录，将新的记录继续保存起来为新的SST，但是面临的问题是如何进行合并操作呢？
如果不进行SST文件压缩的话，读取数据时就要访问多个数据源，这样读取数据代价比较大，为了缓解这些问题一些LSM-Tree设计者们引入一个叫compaction周期性动作，这个会定时对持久化SST文件进行压缩，多文件合并到一个新的文件中，然后丢弃老的记录SST文件，保留新的SST文件，下面正式开始讨论具体实现细节。
在压缩过程中我们还要排除掉已经被删除的记录了，这个被删除的记录操作方法和我上面那篇文章删除操作很像，不是直接删除，而是通过一个特殊的位置来表示是否被删除了。传统方式如果直接在内存表中及其删除，如果数据在内存表上是可以被删除的，但是如果数据在持久化的SST文件就中就违背不可变原则了。
并且这种方式只能删除内存表中的数据，而磁盘SST文件还是能查找到这份数据，导致被删除的数据出现了死而复生的情况，所以只能在内存表中对其添加数据标记为删除，这里在某些论文里面称之为🪦墓碑，有了在最新内存表中的墓碑标记，周期性合并时如果发现被删除的标记记录就在新文件中跳过此记录，新生成的SST就没有此条记录了，过成如下图：
数据合并和迭代是整个LSM-Tree引擎中最重要的一个部分，如果这块没有做好可能会出现数据文件泄露的情况，导致外部数据一直刷新存储新的文件占用磁盘空间最终导致整个程序崩溃或者磁盘被占用满情况。在相关论文提出Compaction实现，第一种实现为Minor Compaction组件，主要作用为对其内存数据表压缩刷入到磁盘中保存为数据文件；还有另外一个为Major Compaction组件，主要针对的是磁盘上分级的数据文件进行压缩整理，把2个相邻的层次的数据文件压缩成为一个文件并且放入下一层，持久化的SST存放也是有规律的，每个层次都是从上往下进行存储的并且每层SST文件数量是有限制的，达到限制会触发一次Major Compaction如下图：
文件层次结构是在逻辑上抽象出来一种概念，而实际的数据文件没有层次结构，就需要我们自己通过代码逻辑实现这个文件关系模型，0层中浅蓝色的三个SST文件，加上1层中的绿色的SST文件，四个文件进行了合并，输出成两个按序组织的新的1层SST文件进行替换，那么什么时候会触发进行Major Compaction呢？何时触发？由于Compaction的其中一个目的是为了提高读取的效率，因此不允许0层存在过多的文件数，一旦超过了上限值，即可进行Major Compaction，但是如何将其多个SST文件合并输出到新的文件又成为一个新的问题？如何解决？
面临第一个问题就是如何设计这些SST文件的层次关系，这里笔者的一个想法就是为每层设置SST文件的大小总和，当每层的所有文件总和超过对应的阀值时就触发一次合并，这里我们只需要设置Level 0层的文件大小总和就可以了，其他层的大小程序会自动计算，具体计算看具体实现的策略，也可以规定每层的文件个数，当达到阀值时也会触发一次合并。
比较传统的方法就是使用多路归并排序的方法进行，这和排序算法里面的归并排序差不多，只是针对是每个文件的内容进行排序输出到新的SST文件中，例如下图：
在这个过程要解决多数据版本问题，还有被删除的数据也要被清理的问题，看上去就很简单，实践解决起来极其复杂，因为磁盘的SST也是划分层的我们也可以把这些文件组建成一个树形结构，这里的多个SST文件合并策略有很多种，这里将介绍一些常用的例如二叉排序树，将本层的所有SST文件中的数据读入到树中，然后将这个颗二叉排序树输出到下一层保存为新的SST文件，而被合并的层所有的SST文件将被清理掉，如下图：
这种方式不是没有确定的，因为每层的SST文件中保存的数据记录可能会很多，磁盘SST文件中的数据大于内存可用空间，如果像上面那样把SST数据全部一次性加载到内存中会出现内存不够用的情况，内存排序结构不能满足时，就会面临这个问题？怎么解决？
那有没有什么好的办法吗？能在固定的内存空间里将多个数据输入进行排的方法？这里我们可以使用一个固定大小优先队列，每当队列尾部插入新元素的时候都会进行调整，而对头输出就是最小值或者最大值，具体实现其实就是一个小顶堆，这样就可以固定内存数据结构大小对应就是SST文件输入源的个数，工作原理如下图：
元素位数是在队列初始化的时候就固定的，每当取出一个元素就从被取出元素的输入SST源再读入一个元素，依次递归直到SST数据记录销毁完毕，至于为什么要在被取出元素对应的数据源取下一个元素，留给读者自己思考🤔。
基于SSTable和LSM-Tree不是没有缺点的，存在读写放大与空间放大的问题？这是什么问题？根据上面的LSM-Tree树设计和实现就可以推理出一些规则，由于批量刷写数据到磁盘，在压缩多个SST文件就会发生空间放大问题通过空间换时间，可以在合并的过程中就去除重复记录的存在；但是如果不这么做的话又会出现读放大，也就是每次查询数据要读取多个SST才能找到满足条件的数据记录，所以一项技术没有完美的解决方案，只有合不合适业务场景的解决方案。
小结
本文介绍了数据存储和数据检索等设计相关的细节，多个SSTable可以组成一个树形结构，日志结构索引也会重写数据多次，由于SST文件需要合并导致一些写请求的数据多次写入磁盘，称为写放大；对于大量写请求的应用性能瓶颈很可能在于数据库写入磁盘的速率，写放大会直接影响到性能成本数据刷入磁盘的次数越多磁盘的带宽中每秒能处理的写入就越少。但是如果设计好内存表大小阀值和压缩的频率可以缓解这些问题，总体而言LSM-Tree树对其写操作还是友好的，因为大部分是顺序IO操作的；特别要注意的就是写入吞吐量很高并且压缩没有仔细配置的情况下，很有可能出现外部写入和压缩合并频率不匹配情况，磁盘上未合并段的数量不断增加会导致磁盘被刷满的情况，需要添加相关监控程序来保障。
