Php做网站创业,go语言网站开发,企业网站建设优化,软件商店appLSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象#xff0c;事实上#xff0c;LSM树并不像B树、红黑树一样是一颗严格的树状数据结构#xff0c;它其实是一种存储结构#xff0c;目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。
LSM树的核…LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象事实上LSM树并不像B树、红黑树一样是一颗严格的树状数据结构它其实是一种存储结构目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。
LSM树的核心特点是利用顺序写来提高写性能但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能但是通过牺牲小部分读性能换来高性能写使得LSM树成为非常流行的存储结构。
1、LSM树的核心思想 如上图所示LSM树有以下三个重要组成部分
1) MemTable
MemTable是在内存中的数据结构用于保存最近更新的数据会按照Key有序地组织这些数据LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义例如Hbase使跳跃表来保证内存中key的有序。
因为数据暂时保存在内存中内存并不是可靠存储如果断电会丢失数据因此通常会通过WAL(Write-ahead logging预写式日志)的方式来保证数据的可靠性。
2) Immutable MemTable
当 MemTable达到一定大小后会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理在转存过程中不阻塞数据更新操作。
3) SSTable(Sorted String Table)
有序键值对集合是LSM树组在磁盘中的数据结构。为了加快SSTable的读取可以通过建立key的索引以及布隆过滤器来加快key的查找。 这里需要关注一个重点LSM树(Log-Structured-Merge-Tree)正如它的名字一样LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中当此类操作达到一定的数据量后再批量地顺序写入到磁盘当中。这与B树不同B树数据的更新会直接在原数据所在处修改对应的值但是LSM数的数据更新是日志式的当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写不断地将Immutable MemTable flush到持久化存储即可而不用去修改之前的SSTable中的key保证了顺序写。
因此当MemTable达到一定大小flush到持久化存储变成SSTable后在不同的SSTable中可能存在相同Key的记录当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能但同时也会带来一些问题
1冗余存储对于某个key实际上除了最新的那条记录外其他的记录都是冗余无用的但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。 2读取时需要从最新的倒着查询直到找到某个key的记录。最坏情况需要查询完所有的SSTable这里可以通过前面提到的索引/布隆过滤器来优化查找速度。 2、LSM树的Compact策略
从上面可以看出Compact操作是十分关键的操作否则SSTable数量会不断膨胀。在Compact策略上主要介绍两种基本策略size-tiered和leveled。
不过在介绍这两种策略之前先介绍三个比较重要的概念事实上不同的策略就是围绕这三个概念之间做出权衡和取舍。
1读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在不存在继续从SSTable中寻找。 2写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作导致实际写入的数据量远大于该key的数据量。 3空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储对于一个key来说只有最新的那条记录是有效的而之前的记录都是可以被清理回收的。 1) size-tiered 策略 size-tiered策略保证每层SSTable的大小相近同时限制每一层SSTable的数量。如上图每层限制SSTable为N当每层SSTable达到N后则触发Compact操作合并这些SSTable并将合并后的结果写入到下一层成为一个更大的sstable。
由此可以看出当层数达到一定数量时最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable每个key的记录是可能存在多份的只有当该层的SSTable执行compact操作才会消除这些key的冗余记录。
2) leveled策略 每一层的总大小固定从上到下逐渐变大
leveled策略也是采用分层的思想每一层限制总文件的大小。
但是跟size-tiered策略不同的是leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的意味着一个key在每一层至多只有1条记录不存在冗余记录。之所以可以保证全局有序是因为合并策略和size-tiered不同接下来会详细提到。 每一层的SSTable是全局有序的
假设存在以下这样的场景:
1) L1的总大小超过L1本身大小限制 此时L1超过了最大阈值限制
2) 此时会从L1中选择至少一个文件然后把它跟L2有交集的部分(非常关键)进行合并。生成的文件会放在L2: 如上图所示此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact操作。
3) 如果L2合并后的结果仍旧超出L5的阈值大小需要重复之前的操作 —— 选至少一个文件然后把它合并到下一层: 需要注意的是多个不相干的合并是可以并发进行的 leveled策略相较于size-tiered策略来说每层内key是不会重复的即使是最坏的情况除开最底层外其余层都是重复key按照相邻层大小比例为10来算冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景如果LevelN层某个SSTable的key的范围跨度非常大覆盖了LevelN1层所有key的范围那么进行Compact时将涉及LevelN1层的全部数据。
3、总结
LSM树是非常值得了解的知识理解了LSM树可以很自然地理解HbaseLevelDb等存储组件的架构设计。ClickHouse中的MergeTree也是LSM树的思想Log-Structured还可以联想到Kafka的存储方式。
虽然介绍了上面两种策略但是各个存储都在自己的Compact策略上面做了很多特定的优化例如Hbase分为Major和Minor两种Compact这里不再做过多介绍推荐阅读文末的RocksDb合并策略介绍。
