Log Structured Merge Tree LSM原理
# Log Structured Merge Tree LSM原理
最近在看Google十年前发表的BigTable论文,BigTable这玩意,最骚的一点就是改变了大多数传统数据库所使用的文件组织方法,业界对这种新一代的文件组织方法进行了实现,叫做Log Structured Merge Tree,简称LSM,中文叫做日志结构的合并树。
LSM目前被用于多个面向大数据的数据库产品: HBase、Cassandra、LevelDB等。
# 诞生背景
无论B树和B+树在写入的时候,为了能处理数据库异常崩溃的场景,通常都会有额外的结构,学名叫做预写式日志(WAL,write-ahead log),在Mysql 中叫做 redo log。在写入数据之前,会将操作都写入这个redo log(这个文件在磁盘上),然后再从这个redo log中将数据同步到具体的B树中。这样即使数据库发生崩溃,也能够通过这个日志文件,让B树恢复到一致的状态。
但是B树难以应对并发操作的情况,在多个线程同时访问B树的时候需要加锁,需要保证树的结构是一致和完整的,否则不同的线程就会看到树处于不一致的状态。Msql会有各个隔离级别和各种锁,也是因为这个原因。
为了加快写入的速度,就诞生了LSM这个算法。
LSM的思想,在对于数据修改采用增量的方式保存在内存中,内存容量达到指定的限制时就将操作的数据批量写入到磁盘(SSTable,Sorted String Table)中,相比较于写入操作的高性能,读取操作需要合并内存中最近修改的操作和磁盘中的历史数据,需要先看内存,如果没有命中还要访问磁盘文件。将之前使用一个大的查找结构(造成随机读写,影响写性能),变换为将写操作顺序的保存到一些相似的有序文件(也就是sstable)中。所以每个文件包含短时间内的一些改动。因为文件是有序的,所以之后查找也会很快。文件是不可修改的,他们永远不会被更新,新的更新操作只会写到新的文件中。通过周期性的合并这些文件来减少文件个数。
# B树对比LSM树
B树在写入的时候至少会被写入两次,一次是WAL(redo log),另一次是树结构本身。即使树只有几个字节的变化,也需要接受整个页面写入的开销。如果一张表存在多个索引树,那肯定会对硬盘造成多次写入。
一次数据库操作导入对磁盘上的文件多次写入,被称之为写放大。
LSM树会有更低的写放大,因为磁盘上的SSTable是顺序且紧凑的而不是必须复写树结构。
而且LSM树可以对文件进行压缩和排序,这是SSTable的特性所决定的,Stored String Table中的数据是可排序的,也就意味着可以用前缀树来进行排序。然后由于sstable文件是不可修改的,这让对他们的锁操作非常简单。一般来说,唯一的竞争资源就是memtable,相对来说需要相对复杂的锁机制来管理在不同的级别。
# LSM树
LSM本质上并不是一种树,而是一种文件组织的形式,将数据进行一个分层以便于获得更好的性能。
从结构上分为两类,一种是存储在内存中的Memtable,另一种则是存储在磁盘中的SSTable。
一般简单的都会划分为两层,Level 0 是存储在内存上的Memtable,Level 0以上则是存在磁盘中的SSTable
# 基本原理
写入操作
当一些更新操作到达时,他们会被写到内存缓存(也就是memtable)中,memtable使用树结构来保持key的有序.
在大部分的实现中,memtable会通过写WAL的方式备份到磁盘,用来恢复数据,防止数据丢失。
当memtable数据达到一定规模时会被刷新到磁盘上的一个新文件,重要的是系统只做了顺序磁盘读写,因为没有文件被编辑,新的内容或者修改只用简单的生成新的文件。
合并文件
所以越多的数据存储到系统中,就会有越多的不可修改的,顺序的sstable文件被创建,它们代表了小的,按时间顺序的修改。
因为比较旧的文件不会被更新,重复的记录只会通过创建新的记录来覆盖,这也就产生了一些冗余的数据。
所以系统会周期的执行合并操作(compaction)。 合并操作选择一些文件,并把他们合并到一起,移除重复的更新或者删除记录,同时也会删除上述的冗余。更重要的是,通过减少文件个数的增长,保证读操作的性 能。因为sstable文件都是有序结构的,所以合并操作也是非常高效的。
读操作
读操作优先判断key是否在MemTable, 如果不在的话,则把覆盖该key range的所有SSTable都查找一遍。简单,但是低效。因此,在工程实现上,一般会为SSTable加入索引。可以是一个key-offset索引(类似于kafka的index文件),也可以是布隆过滤器(Bloom Filter)。布隆过滤器有一个特性:如果bloom说一个key不存在,就一定不存在,而当bloom说一个key存在于这个文件,可能是不存在的。实现层面上,布隆过滤器就是
key--比特位
的映射。理想情况下,当然是一个key对应一个比特实现全映射,但是太消耗内存。因此,一般通过控制假阳性概率来节约内存,代价是牺牲了一定的读性能。对于我们的应用场景,我们将该概率从0.99降低到0.8,布隆过滤器的内存消耗从2GB+下降到了300MB,数据读取速度有所降低,但在感知层面可忽略。
# 总结
LSM Tree 思想是把随机写入转化成顺序写入,这样可以大幅度提升写入的性能,但是查询性能会有一部分牺牲。
在时序数据库运用这一特性非常合适。持续写入数据量大,数据和时间,将时间编码到 key 值中很容易使 key 值有序。读取操作通常是根据某个Key的值,去获取一段时间范围内的数据。这样就把 LSM Tree 读取性能差的劣势缩小了,反而因为数据在 SSTable 中是按照 key 值顺序排列,读取大块连续的数据时效率也很高。
- 01
- Jackson配置BigDecimal序列化保留小数点位数03-19
- 02
- elegraph上传图片Image dimensions invalid03-19
- 03
- arm64 版 picgo 提示已损坏解决办法02-19