乐趣区

关于nosql:日志结构流派存储引擎的演化

jiezi

本文次要内容来自于《数据密集型利用零碎设计》第三章，内容对我很有启发，所以分享给大家，举荐看原作。

背景

存储引擎存在着两个次要流派：

  1. 日志构造流派，只容许追加式更新 / 删除文件，不会批改已写入的文件，Bitcast，SSTables，LSM-Tree，LevelDB，RocksDB，Cassandra，HBase，Lucene 等属于此类
  2. 原地更新流派 ，将磁盘视为能够笼罩的一组固定大小的页。B-tree 就是这一流派的典型代表，已用于所有支流 关系型数据库，以及大量的非关系数据库

大部分人曾经对原地更新流派中 B-tree 曾经比拟相熟了，但对日志构造流派并不是很理解，本文率领大家理解下其演化过程及 LSM-tree 与 B-tree 的比照

演化过程

1. 一个最简略的数据库

基本原理

由两个 Bash 函数实现：

db_set(){echo "$1,$2" >> database}

db_get(){grep "^$1," database | sed -e "s/^$1,//" | tail -n 1}

插入 / 更新数据: 往 database 文本中追加一行 <key，value>

查问数据： 查找文本中最初一次呈现的 <key，value>

例如：

➜  ~ db_set key1 val1
➜  ~ db_set key2 val2
➜  ~ db_set key1 val3
➜  ~ cat database
key1,val1
key2,val2
key1,val3
➜  ~ db_get key1
val3

局限性

db_set: 追加式写，性能高。但db_get: 从头扫描到尾，性能很差

如何解决：

减少一个数据结构：索引

索引：原始数据派生的额定数据结构，适当的索引能够减速，然而加索引会减慢写的速度

2. 哈希索引

基本原理

为了解决上述追加式文件读性能太差的问题，能够在内存中保护一个 <key, offset> 的 哈希表，如下图所示。offset 代表此 key 在文件中偏移量，所以 get 不须要遍历整个文件了。

这听下来可能过于简略，但它确实是一个可行的办法。事实上，Bitcask 就是这么做的（Riak 中默认的存储引擎）

这个简略的想法可行，然而要利用到理论中还须要解决其存在的一些问题或者说须要做一些优化

1. 追加式日志存储冗余太多

压缩思路：一个 key 存在屡次写，能够只保留最新写入的 value

解决方案：将日志分解成肯定大小的段，当文件达到特定大小时敞开以后段文件，写入一个新的段文件。而后在这些段上执行压缩。

能够在一个段内压缩，也能够把多个段合并在一起，下图是一个把两个段合并在一起的例子。

压缩合并：

  • 如果 key 存在于多个段中，保留最新的段中的
  • 压缩合并能够运行在后盾线程
  • 在压缩合并的过程中，能够持续用旧的段读取和写入
  • 合并过程实现后，读和写申请切换到新的段，旧的段能够删除了

当初，每个段在内存中都有本人的哈希表，读取流程为：首先查看最新段的哈希表，如果 key 不存在，查看第二新的段，以此类推。如果 key 不存在，要遍历完所有段的哈希表

2. 文件格式
  • 下面例子应用的 CSV 作为日志格局，为了性能思考，能够应用二进制格局的日志
3. 如何删除
  • 在数据文件中追加一个非凡的删除记录
4. 解体复原

  1. 内存中哈希表会失落

    1. 能够重头到尾从新扫描段文件，复原哈希表，然而复原速度太慢
    2. 将哈希表的快照存在磁盘中，Bitcast 就是这么做的，复原时读取

  2. 存在局部写入的记录

    • 加校验值
5. 并发管制
  • 应用单个线程写

劣势（其实以下是日志构造流派的劣势）

  • 追加和合并都是程序写，程序写与随机写性能之间有 2 个数量级以上的差别
  • 段文件是追加和不可批改的，并发与解体复原简略得多。不用放心重写值时产生解体，留下一个蕴含局部旧值与局部新值混淆在一起的文件
  • 合并旧段能够防止数据文件呈现碎片化的问题

局限性（哈希索引构造）

  1. 哈希表必须全局放入内存，如果数据量比拟多，内存很容易放不下。尽管实践上能够把哈希表放在磁盘保护，然而哈希表放在磁盘的体现并不好，大量随机 IO
  2. 区间查问效率不高，必须遍历所有段的哈希表中每个 key

3. SSTables

基本原理

为了解决上述哈希索引的问题，提出以下要求

  • 段文件中 <key, value> 按 key 排序

这种格局的段文件被称为 排序字符表（SSTable），其绝对哈希索引的日志段有以下劣势

  1. 即便文件大于可用内存，合并段的操作依然是简略而高效的。应用归并排序算法，如下图所示

  1. 不须要在内存中保留所有 key 的索引了。因为其中段文件中 key 是排序的，索引能够十分稠密，每几千个字节存一个索引。而后能够在几千个字节中应用遍历 / 二分查找出特定的 key
  2. 能够将两个索引之间的多个 <key,value> 分组，压缩存储，节俭磁盘 IO

局限性

尽管 SSTable 绝对哈希索引有这么多益处，但其要求段文件中 <key,value> 按 key 排序，这个要求自身就违反了日志构造流派的初心 - 追加程序写，因为用户的写申请不可能是按 key 从小到大程序来的

4. LSM-Tree

LSM-Tree 作为目前日志构造流派的最终 boss 出场了，它的作用是构建和保护 SSTables

原理

写入以任意程序呈现，但能够在内存中保护一个有序的数据结构，如红黑树、AVL 树、跳跃表等。

因而当初的 写入流程 为：

  1. 有新写入时，将其增加到内存中的均衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。
  2. 当 内存表 大于某个阈值（通常为几 MB）时，将其作为 SSTable 文件写入硬盘。因为曾经是有序 <key, value> 对了，写磁盘比拟高效。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入能够在一个新的内存表实例上持续进行。

读取流程 为：

  1. 收到读取申请时，首先尝试在内存表中找到对应的 key
  2. 如果内存表没有就在最近的 SSTable 段中寻找
  3. 如果还没有就在下一个较旧的段中持续寻找，以此类推

后盾线程周期性执行段的合并压缩过程，以合并段文件并将已笼罩或已删除的值抛弃掉

以上还存在一个问题，内存表的数据会在解体中丢掉，这也很好解决，应用 WAL 记录内存表中的写入。下图很形象的形容了 LSM-tree 的工作原理

以上就是 LSM-tree 的根本思维了，其取得了巨大成功，LevelDB，RocksDB，Cassandra，HBase，Lucene 等都应用到了相似的办法。

性能优化

要满足理论利用的需要，总是由很多细节值得深刻

问题 1：查找数据库中不存在的 key 时，要回溯到最旧的段（屡次磁盘拜访）

解决办法： 布隆过滤器

问题 2：合并与压缩 SSTable 的策略: 什么时候去合并压缩 SSTable？应该合并压缩 那几个 SSTable？

解决方案 ：分层压缩（LevelDB 与 RocksDB）与大小分级（HBase）

咱们这里次要介绍下 LevelDB 的实现，其次要思维是把 SSTable 分层，如下图所示：

内存表：

  • 默认 4MB 左右内存块
  • 寄存有序 Key-Value
  • 内存构造为跳跃表
  • 数据先写入 Memtable，达到指定大小后，把它变成 ImmuableTable，之后异步 Compaction 落盘到 Level-0

SSTable 文件：

  • SSTable 文件是层次结构，每层按 key range 分区寄存在多个 SSTable 中
  • Level-0 层 比拟非凡，其上不同 SSTable 的 key range 会存在重叠，其它层 key range 不重叠。level-0 限定总大小 4 MB，单个 SSTable 段 1 MB
  • Level-i（i > 0）的大小呈指数增长，其单个 SSTable 大小限定 2MB，Level-i 层总大小限定大小 10^i MB，第 6 层能包容 1 T 的数据量
  • Level-i 层中的每个 SSTable 最多与 Level-(i+1) 的 10 个 SSTable 存在交加
  • 数据新鲜度：Memtable > ImmutableTable > Level-0 > Level-1 > Level-2 > ..

合并机会：

level-i 的大小超过其限定大小 10^i MB 时，抉择一个 level-i 的 SSTable 与其 level-(i+1) 的 key 存在交加的 SSTable 进行合并。

触发生成新的 SSTable 机会

  • SSTable 文件大小达到 2 MB
  • SSTable 与下一层 key 重叠的 SSTable 数量超过十个

存在的一些问题

  1. 写放大：指一次写入申请造成屡次磁盘写，合并压缩引起
  2. 读放大：指理论读取的数据量大于用户须要的数据量，LSM-tree 从内存表开始，若找不到，会一层层查找前面 SSTable
  3. 空间放大: 不是原地更新，过期数据不会马上删除

合并压缩可能缩小读放大与空间放大，但会带来写放大，三者的关系有点相似 CAP，须要取舍。

LSM-tree 与 B-tree 的比照

只管 B-tree 实现通常比 LSM-tree 实现更成熟，但 LSM-tree 因为其性能特点目前很有吸引力。依据教训，通常 LSM-tree 的写入速度更快，而 B-tree 的读取速度更快。LSM-tree 上的读取通常比较慢，因为它们必须查看几种不同的数据结构和不同压缩（Compaction）层级的 SSTables。

LSM-Tree 劣势

1. 设计简略高效

基本思路是合并压缩排序文件，写入性能高，在并发与解体复原等问题上也简略得多

2. 较低的写放大

B-tree 写数据时，即便只有几个字节更改，也必须接受整个页的开销（有时还可能产生页决裂）

LSM-tree 在压缩和合并 SSTable 的过程中，也会重写数据屡次

论断：LSM-tree 具备较低的写放大

写放大在写入吞吐量和 SSD 磁盘寿命中影响比拟大

3. 程序写

B-tree：随机写

LSM-tree: 程序写

程序写性能更高，在应用一般磁盘的机器中十分要害

4. 反对更好地压缩

B-tree 不反对压缩，面向页的，存在一些碎片无奈应用

LSM-tree 反对压缩，磁盘中文件比 B-tree 小，定期合并 SSTable 打消碎片化

LSM-tree 劣势

1. 后盾压缩合并过程会影响实时读写操作

磁盘的并发资源无限，而压缩合并过程十分占用磁盘资源，会烦扰实时读写申请

LSM-tree 会在更高的百分位查问响应（pct999？）相当高的状况，而 B-tree 的响应提早更具确定性

2. 可能后盾压缩速度赶不上写入速度

硬盘的无限写入带宽须要在初始写入（记录日志和刷新内存表到硬盘）和在后盾运行的压缩线程之间共享。写入空数据库时，能够应用全硬盘带宽进行初始写入，但数据库越大，压缩所需的硬盘带宽就越多。

如果写入吞吐量很高，并且压缩没有认真配置好，有可能导致压缩跟不上写入速率。在这种状况下，硬盘上未合并段的数量一直减少，直到硬盘空间用完，读取速度也会减慢，因为它们须要查看更多的段文件。

通常状况下，即便压缩无奈跟上，基于 SSTable 的存储引擎也不会限度传入写入的速率，所以你须要进行明确的监控来检测这种状况

3. 对事务的反对不如 B-tree

B-tree 中一个 key 存在一个确切的地位，而 LSM-tree 可能存在于不同段中

在许多关系数据库中，事务隔离是通过在键范畴上应用锁来实现的，在 B-tree 索引中，这些锁能够间接附加到树上。在 LSM-tree 对范畴上锁，只能把所有 SSTable 对应地位锁上。

总结

B-tree 在数据库架构中是积重难返的，为许多工作负载都提供了始终如一的良好性能，所以它们不可能很快就会隐没。而在新的数据存储中，日志结构化索引变得越来越风行，日志构造流派的设计足够简略高效，值得咱们学习。

退出移动版