LSM

LSM Tree 适用于写多读少的场景

Log-Append

最快的写入方式就是追加写入, 追加写入和随机写入的差距在机械硬盘中体现的完完全全

#!/bin/bash
db_set () {    
        echo "$1,$2" >> database
}

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

$db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}' 

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

这是一个最简单的数据库, 两个函数实现了key-value键值对的读写. 如果单纯看写入操作, 时间在O(1). 但是对于读操作, 时间在O(n)

如果我们能实现索引功能的话, 就能提高读的效率. 但是在读提高的同时, 写的效率会下降. 因为索引是从主数据“附加**出来的结构, 它不会影响到内容, 但我们也需要花时间去记录它

顺着索引的思路, 我们可以创建一个类似hashmap的数据结构, key为数据的key, value为数据在文件中的偏移量, 如下图所示

image.png

为了加快访问速度. 我们把它放到内存里, 称自为 In-memory hash map (Bitcask就是这么实现的)

上文的思路中存在一个问题, 因为是追加, 所以一个文件中势必会存在大量的重复key. 这样下去, 文件的体积会越来越大

好的解决方法是把文件分成 段, Segment(每个段含有固定的大小), 当段文件达到该大小时, 关闭该文件, 创建新的段文件

image.png

现在每个段文件都有自己的内存散列表, 将键和偏移量映射到内存中. 当我们进行查找时, 如果最新段文件不存在该key, 那么就找下一个段文件

来总结下这个架构还待优化的地方:

1. 数据的存储我们之前用的是CSV方法, 如果改成二进制存储会更好, String.length + raw data
2. 对于删除操作, 我们只需要查找到该key, 并作上一个特殊的标记, 这样当合并的时候, 后台会自行删除
3. 崩溃恢复,此时如果崩溃了, 需要遍历所有段, 重新构建内存散列表. 可以拍摄快照

对于这样的结构, 开启一个写线程, 多个读线程就足够满足日常的请求.

相比更新替换值, 追加写的好处体现在:

• 磁盘顺序写和随机写的性能不在一个级别上(即便是SSD), 涉及到的追加和分段都是顺序写入操作
• 并发和崩溃变得简单, 一方面, 我们不需要涉及各种各样的锁, 所有的写入操作只能写在最新文件, 并且只能是追加写入,具备原子性. 同时, 您不必担心在覆盖值时发生崩溃的情况, 而导致旧值和新值和在了一起

SST(Sorted String Table)

随着数据不断的增多, 哈希索引的局限性逐渐暴露:

• 哈希表必须全部能装进内存
• 如果存在大量的键, 原则上可以将哈希表存入磁盘, 但也会导致产生大量的随机访问I/O
• 范围查询效率不高, 例如想查找xx00 - xx100的数据, 需要遍历所有的段文件

我们对段文件的格式作出改变: 按顺序对key排序, 我们称自为排序字符串表, Sorted String Table.它给我们带来了以下提升:

1. 合并变得更加高效快捷, 即便文件的总大小大于内存, 我们通过归并算法, 进行合并排序(因为每个文件都是排好序的了, 从开头逐一比较)
2. 文件按key顺序, 所以我们不需要对每个key都作索引, 我们可以将key划分称若干个 block, 只索引每个block开头的start_key, 对于这样子的索引, 我们称作 稀疏索引
   
   image.png
3. 以block为最小单元, 使得我们能更有效率的压缩空间, 提高查询效率, 减少I/O
4. 可以单点查询, 也可以范围查询

那如何保证每个SSTable有序呢?

MemTable

SSTable和MemTable的概念, 最早来源于Google的BitTable论文, 有兴趣的读者可自行参考.

理念是: 我们将数据先写入到内存, 待到一定大小的时候, 就写入硬盘, 转换生成新的SST文件. 写入内存时, 只要保持数据有序就好. 一般常用的结构为平衡树(AVL树, 红黑树), 或者跳表

唯一要注意的事, 如果还没写入到磁盘时, 电脑崩溃了怎么办. 对于先写入内存再刷盘的这一类机制, 我们都会引入 WAL(Write-Append-Log), 预写日志机制, 写入内存前, 先顺序写入日志, 在写入内存. 当崩溃时, 我们可以读取该日志, 重新构建MemTable树

至此, LSM的三个核心组件: SSTable, MemTable, WAL机制都已经到齐了. 我们来提前总结下:

在很多大数据的环境下, 人们比起读效率, 更看重写的效率. 所以LSM的机制, 就吸引了很多企业的目光, 比如LevelDB, RocksDB,Cassandra, HBase等. LSM不仅是在写机制上做的很好, 对于SSTable不可更改的特性, 也简化了并发和异常的配置. 唯一需要上锁的, 是存储在内存中的 MemTable

随着硬件性能不断的提升, 可用的内存增加, 通过操作系统提供的大文件缓存, 可以提高我们的读优化, 除此之外, LSM机制还引入了 BloomFilter, 布隆过滤器. 对于每个Segment文件, 我们先用布隆过滤器来判断key存在与否, 加速读优化

合并策略

目前广泛应用的合并策略有两种: size-tiered 和 leveled. 感兴趣的可以参考LSM存储引擎基本原理, 从朴素解释出发解释leveldb的设计

这些改变表明按层合并的策略减小了合并操作的影响，同时减少了空间需求。除此之外，它也有更好的读性能。但是对于大多数场景，总体的IO次数变的更多，一些更简单的写场景不适用。