LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构,它其实是一种存储结构
LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中,当此类操作达到一定的数据量后,再批量地顺序写入到磁盘当中。这与B+树不同,B+树数据的更新会直接在原数据所在处修改对应的值,但是LSM数的数据更新是日志式的,当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写,不断地将Immutable MemTable flush到持久化存储即可,而不用去修改之前的SSTable中的key,保证了顺序写。
1)读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在,不存在继续从SSTable中寻找。
2)写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作,导致实际写入的数据量远大于该key的数据量。
3)空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储,对于一个key来说,只有最新的那条记录是有效的,而之前的记录都是可以被清理回收的。
所谓空间放大(space amplification),就是指存储引擎中的数据实际占用的磁盘空间比数据的真正大小偏多的情况。例如,数据的真正大小是10MB,但实际存储时耗掉了25MB空间,那么空间放大因子(space amplification factor)就是2.5。
为什么会出现空间放大呢?很显然,LSM-based存储引擎中数据的增删改都不是in-place的,而是需要等待compaction执行到对应的key才算完。也就是说,一个key可能会同时对应多个value(删除标记算作特殊的value),而只有一个value是真正有效的,其余那些就算做空间放大。另外,在compaction过程中,原始数据在执行完成之前是不能删除的(防止出现意外无法恢复),所以同一份被compaction的数据最多可能膨胀成原来的两倍,这也算作空间放大的范畴。