引言

本文为《数据密集型应用系统设计》的读书笔记第一部分第三章的笔记整理，也是个人认为的这本书第一部分最重要的内容。本文将会针对目前数据库系统两个主要阵营进行展开，分别是采用日志型存储结构高速读写的LSM-Tree和面向OLTP的事务数据库BTree两种数据结构对比。

主要内容

本文的主要内容介绍如下：

• 最简单key/value数据库考量和拓展，从零开始了解日志型存储结构。
• 索引对于数据库的重要性，哈希索引如何优化key/value数据库。
• Btree 数据结构的简单介绍，数据结构和特点等。
• LSM-Tree日志存储结构 VS Btree存储引擎，两大阵营的优劣对比。
• OLTP到OLAP的对比，行存储到列式存储结构演进，以及数据仓库出现和数据分析的演进。

数据库底层设计考量

• 底层存储形式：记录存储的基本设计格式，虽然格式会有不同的设计，但是最终都是以文件的形式存储。
• 查询/新增/读取/修改方式：在外部来看也就是在数据库概念中的DML操作，这种操作面对的是客户端，属于对外接口的部分。而从内部来看则是存储数据结构，操作数据结构和并发性能的考量。
• 操作日志：出于持久性的考量，操作日志是不可或缺的因素，也是意外之后数据修复的保证。
• 数据类型：比如Key/value存储还是针对行列的存储结构。

key/value存储结构和哈希索引

关键：#key/value存储结构处理 #哈希索引优化

从零开始设计一个数据库的存储形式，可以从下面的几个点考虑，从存储结构出发我们看日志存储结构数据库是如何出现的。

首先是key/value数据库数据结构设计第一版，从最简单的k/v存储数据库开始了解由此引申出哈希索引的结构：

上面结构有如下的特点：

存储形式：主要以key/value存储形式，key/value可以是任何内容。底层使用纯文本的形式存储，使用追加方式更新数据，相同key使用最后一次读到的key为基准。

读写方式：db_set xx设置数据，db_get xx读取数据，修改一个key通过最后一行追加形式，意味着更新和删除操作没有任何的开销，无需关注并发的问题。

查询性能：查找数据的开销为O(n)，新增和修改的性能都是O(1)。

追加式处理优点

• 顺序写比随机写好很多
• 段文件是追加不可变的，意味着并发访问和崩溃恢复比较容易
• 压缩和合并分段可以防止数据文件碎片化问题

最简单的k/v形式的数据库形成有哪些缺点？

• 追加对于存储空间的浪费，虽然追加对于更新和新增十分方面并且维护成本较低，但是有个明显的问题时存储空间的浪费，同时我们发现其实并不需要存储原始文本的形式，同时数据本身可以通过压缩更加紧凑。
• 查询效率随着数据的膨胀而降低，所以需要对于查询速度进行优化，对于查询最简单的方式是引入索引，而对于key/value存储形式设计索引最为常见的是哈希索引

对于Key/value存储引擎来说哈希是常用的索引类型，哈希索引使用内存中的哈希表进行实现，键值对的键存储数据需要索引的数值，而值存储偏移量，偏移量通过计算获取存储位置，在原始数据中直接找到相关位置的数据直接读取。

下面是哈希索引对于key/value结构数据进行索引优化。

纯文本存储数据膨胀如何防止性能变差？

• 分段数据：当追加到一定程度之后则写入一个新的文件。
  
• 压缩段：将最新的数据进行压缩存储，由于使用追加新增方式，可以直接丢弃旧数据。
  
• 段压缩和多段合并：压缩与合并的过程没有特定规划，取决于数据结构和存储结构的抉择。
  

如何防止性能变差：

哈希表和段进行绑定，一个段对应一个哈希表，同时执行段压缩和多端合并，保证脏数据及时清理，最后一定在内存中引入哈希表进行维护。

了解了大致思路之后，如何进行具体优化？

1. 压缩合并存储：为了让存储数据更加紧凑同时没有浪费，定期对于追加数据进行合并压缩是必要的，同时数据分段也可以提高线程并发读写性能。
2. 数据分段：注意数据分段是结合压缩合并一同处理的，当压缩合并存储的数据到达一定量的时候需要对于数据进行分段处理，目的是防止单文件过大同时可以提高索引的搜索效率。
3. 哈希表：引入哈希表结构，在数据行上加一层索引目录，可以加快查询性能，索引的key存储的是键需要保证唯一，而value则存储了行记录的指针，这适用于分段的数据结构找到数据存储的位置，通过一次遍历分段直接通过偏移指针查指定数据是否符合要求即可。

上面讨论的存储结构其实存在实际的实现方式，此数据库存储引擎便是：Bitcast。

哈希索引：

哈希索引设计特点

• 文件格式：并没有使用纯文本存储而是使用二进制，使用字节来记录字符串长度，后面存储真实数据。（二进制也有利于压缩）
• 崩溃恢复：最大的问题是重启之后哈希表会被释放，如果需要重新建立哈希表需要重新读取段，所以最大的性能开销在扫描段上，有一种优化方式是将哈希表的快照存储道磁盘上直接读取。
• 部分写入记录：使用SHA盐值和操作日志对于部分写入记录进行恢复，操作日志相对于数据存储日志更为简单，只需要做增量操作，因为目的仅仅用于存储引擎崩溃之后可以保证数据的持久性。
• 并发控制：Bitcast实际上是一个写线程和多个读线程，数据使用追加方式可以保证多个线程读取，但是只能保证一个线程写入，但是由于数据分段，可以多线程同时改写不同数据段。

通过上面哈希结构的介绍，我们可以总结出哈希索引的几个特点：

• 哈希索引适用于查询多，增删少的情况，虽然压缩和分段合并可以解决数据存储效率低的问题，但是对于频繁的增删需要额外的开销重新维护改动哈希表。
• 哈希表需要在内存中进行使用，所以受限于内存的大小，当然并不是说磁盘无法存储哈希表，而是哈希表在磁盘中难以维护和存储。

哈希的索引形式也存在局限性：

• 虽然哈希表不一定必须放入内存，理论可以在磁盘上维护哈希表，但是这样做需要大量的IO，同时哈希冲突需要更复杂的处理逻辑。
• 区间查询效率不高，对于范围查询的处理能力较弱，此时时间复杂度会退化为O(n)。

以上是哈希结构对于key/value存储的结构对优化。哈希索引适用场景：

• 点击数：对于数据的准确性要求并不是十分高，但是对于效率要求十分高
• 少量数据的唯一记录查找，注意是少量数据，因为哈希表空间有限。

小结：

我们可以看到，从一个最简单的k/v数据库到哈希索引的结构引入，数据的存储和读取结构逐渐变复杂，可以看到哈希索引非常适合key/value的存储引擎，但是显然它存在比较明显的缺陷，比如只能维护哈希表到内存，并且频繁的更新插入key/value对于索引的维护开销也不小，最后最为致命的是范围查询对于哈希索引是硬伤。

总结：索引特点

• 加快原始数据的查询速度
• 空间换时间，需要更多的存储空间以及更长写数据时间
• 索引很多时候被视为和原始数据分开的结构

通过上面的设计有缺点，针对哈希索引有了第一层进化，那就是 SSTable和LSM-Tree。

SSTable和LSM-Tree结构

#SSTable #LSM-Tree

概念

在具体的内容介绍之前，我们需要弄清楚SSTable和LSM-Tree有什么区别，简单来说LSM-Tree是对SSTable概念和思想的一个继承。另外需要注意这个结构特点正好解决了哈希索引局限性问题，同时SSTable并没有抛弃key/value这样的存储结构，而是在索引结构上进一步升级。

SSTable概念

SSTable起源自谷歌在2006年发布的一篇轰动世界的论文，里面的BigTable就是SSTable和LSM-Tree的前身：Bigtable: A Distributed Storage System for Structured Data。如果觉得论文难以理解，可以参考这篇文章理解：

blog.csdn.net/OpenNaive/a…

这里挑了其中一些和SSTable有关的内容，可惜的是这篇论文并没有详细的介绍SSTable的内部数据结构，在论文第六个小节中介绍了SSTable的作用：

BigTable和GFS 是什么关系呢？在论文中我们可以看到一个类似树的结构，其中根节点为主服务器，主服务器负责接受请求，通过管理分片服务器将请求分片到不同的片服务器中，所以从外层看最终干活的是片服务器，实际上片服务器本身只是负责管理自己分片SSTable，通过特殊索引知道数据在那个SSTable分片中，然后从GFS中读取SSTable文件的数据，而GFS则可能要从多个chuncker server里面搜索数据。

而图中的metatable原数据表可以看作是和SSTable绑定的类似索引的关系，元数据表的数据是不能被外界访问的，外界访问的是元数据对应的SSTable分片，这和后面介绍的LSM-Tree有着十分熟悉的契合关系。

改进与对比

关键点： 数据存储方式，索引查找方式改进

SSTable通常如何工作？

• 写入的时候不写入磁盘而是先写入内存表的数据结构，同时在内存将数据进行排序。
• 当数据结构内存占用超过一定的阈值就可以直接写入到磁盘文件由于已经是排好序的状态，所以可以对于旧结构覆盖，写入效率比较高。并且写入和数据结构改动可以同时进行。
• 读写顺序按照 内存 -> 磁盘 -> 上一次写入文件 -> 未找到这样的顺序进行查找和搜索。
• 后台定时线程定时合并和压缩排序分段，将废弃值给覆盖或者丢弃。

SStable的改进点

下面是SSTable相对于哈希结构的特点：

• 高效合并：合并段的过程更加高效，每一个段都是按照特定顺序排序，当出现多个重复数值的时候可以合并到最新的段，对于旧数据则可以直接舍弃前面的内容。
• 范围索引优化：内存中哈希表也是有序存储，可以将多个kv对应的数据条目一同压缩存储，这样索引条目只需要开头部分的键值即可，因为后续所有的记录都是有序的。
• 索引优化：比起哈希较为松散随意的结构，这样的处理牺牲一定的读写开销换来更加高效的存储和索引结构，并且可以支持范围索引扫描。
• 顺序读写：数据顺序存储的好处是可以顺序读写，避免磁盘的随机读写可以大幅度提升读写性能

下面是改进过后的压缩过程图：

最大的改动点压缩合并的基础上对于SSTable基础内容进行合并操作。

如何维护sstable? 首先是数据如何在内存中排序，可以使用红黑树和AVL树的结构也可以是任意结构，重点是在内存中完成数据压缩合并和排序的操作。

为什么数据集远远大于内存依然可以高效？ 因为使用排序以及分段合并压缩分段的数据，所以一次加在到内存的数据不需要太多，其实只需要把内存索引表查找某个区间段的数据，然后进行顺序查找，由于是按照排序的方式顺序存储的，在段上查找数据集通常可以根据键直接偏移或者按照特定规则二分查找的方式搜索。

SSTable和哈希索引的对比：

可以看到SSTable在哈希索引的基础上进行优化，使用排序的手段虽然会损耗一定的写入消耗，但是换来的是更高效率的范围查询以及更高效率的压缩存储形式。

哈希索引：

• 索引查询效率十分高
• 内存中维护，磁盘IO开销很小
• 非常适用于Key频繁更新的场景

SSTable：

• 利于磁盘维护索引和顺序读写，
• 优化范围查询。
• 将范围搜索的查询效率优化至O(logN)的水平

实际案例和应用

全文索引：

全文索引虽然比key/value复杂很多，但是本质都是类似的，某些数据维护依然基于key/value方式存储，比如词条的映射关系使用的SS Table进行存储，在内存中排好序存储，并且需要的时候进行合并。

LevelDB和RockDB：

LevelDB和RockDB是最为典型的LSM-Tree实践案例，尤其是LSM-Tree作者刚好又是谷歌的工程师，深入了解这两款经典LSM-Tree实现案例可以对于SSTable的设计和应用有更深的了解。

LSM-Tree 的代码非常简单易懂，难懂的地方作者也给了注释，对于我这种JAVA开发者也能了解大概。

SSTable的弊端

• 最大的隐患是在压缩合并分段的时候不能进行数据的读写，否则数据一致性会存在问题，这对于吞吐量要求高的系统很难接受。
• 压缩另一个问题是对于带宽的占用非常高，压缩数据量越大，带宽消耗越高，容易阻塞大量的读写请求。
• 如果压缩速度跟不上写入数据，那么就会出现大量未压缩数据堆积情况，长期累计容易造成磁盘空间不足，但是sstable的数据结构决定了追加写入是不受控制的，需要外部力量监控。