LSM树
阅读数:103 评论数:0
跳转到新版页面分类
算法/数据结构
正文
Log Structured Merge Tree,简单地说,LSM的设计目标是提供比传统的B+树更好的写性能。LSM通过将磁盘的随机写转化为顺序写来提高写性能,而付出的代价就是牺牲部分读性能、写放大(B+树同样有写放大的问题,即实际写入的的物理数据量是比写入数据量多)。
LSM相比B+树能提高性能的本质原因是:外存的随机读写都要慢于顺序读写。
优化写性能
如果我们对写性能特别敏感,最好Append Only:所有写操作都是将数据添加到文件末尾。这样做的写性能是最好的,大约等于磁盘的理论速度,但是Append Only的方式带来的问题是:
(1)读操作不方便
(2)很难支持范围操作
(3)需要垃圾回收(合并过期数据)
优化读性能
一般我们有两种方式:
(1)有序存储,比如B+树,SkipList
(2)Hash存储,不支持范围操作
读写性能的权衡
以LevelDB为例:
写操作主要由两步组成:
(1)写日志并持久化(Append Only)
(2)Apply到内存中的memtable(SkipList)
memtable写“满”后,会转换为immutable memtable,然后被后台线程compaction成按key有序存储的sst文件(顺序写)。由于sst文件会有多个,所以LevelDB的读操作可能会有多次贷危机磁盘IO。
SkipList
一个有序的链表,我们选取它的一半的节点来建索引,这样如果插入一个节点,我们比较的次数就减少了一半。这种做法,虽然增加了50%的空间,但是性能提高了一倍。
既然,我们已提取了一层节点索引,那么,可以在第一层索引上再提取索引。
LSM树原理
LSM树由两个或以上的存储结构组成,比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中,称为C0 tree,具体可以是任何方便键值查找的数据结构,比如红黑树、map之类,甚至可以是跳表。另外一个存储结构常驻在硬盘中,称为C1 tree,具体结构类似B树,C1所有节点都是100%满的,节点的大小为磁盘块大小。
1、插入步骤
大体思路:插入一条新的纪录时,首先在日志文件中插入操作日志,以便后面恢复使用,日志是以append形式插入,将新纪录的索引插入到C0中,这里在内存中完成,不涉及磁盘IO操作,当C0大小达到某一阈值时或者每隔一段时间,将C0中记录滚动合并到磁盘C1中,对于多个存储结构的情况,当C1体量越来越大就向C2合并,以此类推,一直往上合并Ck。
2、查找操作
先找内存的C0树,找不到则找磁盘的C1树,然后是C2树,以此类推。
3、删除操作
主要是通过标记来实现,在内存中将要删除的记录标记一下,后面民步执行合并时将相应记录删除。