免费的网站域名查询方法有哪些,网站栏目设计,摄像网站建设,网站图片像素多少LSM树#xff08;Log-Structured-Merge-Tree#xff09;并不像B、红黑树一样是一颗严格的树状数据结构#xff0c;它其实是一种存储结构#xff0c;像HBase、RocksDB这些NoSQL存储都是采用LSM树。它是一种分层、有序、面向磁盘的数据结构#xff0c;核心思想是顺序写性能远…LSM树Log-Structured-Merge-Tree并不像B、红黑树一样是一颗严格的树状数据结构它其实是一种存储结构像HBase、RocksDB这些NoSQL存储都是采用LSM树。它是一种分层、有序、面向磁盘的数据结构核心思想是顺序写性能远高于随机写性能将批量随机写转化为一次性的顺序写。
一、核心思想
LSM树的核心特点是利用顺序写来提高写性能但因为分层分层是指分位内存和文件两部分的设计会稍微降低读性能但是通过牺牲小部分读性能换来高性能写在一些场景中的收益仍然是非常大的。 1MemTable
MenTable是在内存中的数据结构用于保存最近更新的数据会按照Key有序地组织这些数据LSM树对于具体如何有序地组织数据并没有明确的数据结构定义例如HBase使用跳跃表来保证内存中Key的有序。因为数据保存在内存中内存并不是可靠的存储存在数据丢失风险因此通常会通过WALWrite-ahead logging预写日志的方式来保证数据的可靠性。
2Immutable MemTable
当MemTable达到一定大小后会转化成Immutable MemTable。Immutable MemTable是将MemTable转变为SSTable的一种中间状态。写操作由新的MemTable处理在转存过程中不阻塞数据更新操作。
3SSTableSorted String Table
有序键值对集合是LSM树在磁盘中的数据结构。为了加快SSTable的读取可以通过建立Key的索引以及布隆过滤器来加快Key的查找。 LSM正如它的名字一样会将所有的数据插入、修改、删除等操作记录保存在内存中当此类操作达到一定数据量后再批量顺序写入到磁盘中。这与B树不同B树数据的更新会直接在原数据所在处修改对应的值但是LSM树的数据更新是日志式的当一条数据更新是直接append一条更新记录完成的。这样设计的目的是为了顺序写不断地将Immutable MemTable flush到持久化存储中而不用去修改之前的SSTable中的key保证了顺序写。 因此当MemTable达到一定大小flush到持久化存储变成SSTable后在不同的SSTable中可能存在相同的key的记录最新的记录才是准确的。虽然多大提高了写性能但同时也带来了一些问题 ①冗余存储对于某个Key而言实际除了最新的记录外其他的记录都是冗余的但是仍然占用着存储空间。因此需要进行compact操作来清理冗余的记录。 ②读取时需要从最新的倒序查询直到找到某个key的记录。最坏情况需要查询完所有的SSTable在这里可以通过索引和布隆过滤器来优化查找效率。
二、compact策略
从上可以看到compact是十分关键的操作否则SSTable数量会不断膨胀。compact存在不同的策略不同的策略都是在以下3个概念中进行权衡和取舍。
重要概念
①读放大读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在不存在继续从SSTable中寻找。
②写放大写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发compact操作导致实际写入的数据量远大于该key的数据量。
③空间放大数据实际占用的磁盘空间比数据真正的大小多。上面提到的冗余存储对于一个key来说只有最新的那条记录是有效的而之前的记录都是可以被清理会受到 。
1size-tiered体积阶梯式压缩策略类似Minor
size-tiered策略保证每一层SSTable的大小相近同时限制每一层SSTable的数量。每一层限制SSTable的数量为N当每层达到N后则触发compact合并这些SSTable并将合并后的结果写入到下一层成为一个更大的SSTable。 由此可见当层数达到一定数量时最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即便对于同一层的SSTable每个key的记录是可能存在多份的只有当该层的SSTable执行compact才会消除这些key的冗余记录。
2leveled层级式压缩策略类似Major
leveled也是采用分层的思想每一层限制总文件大小。但是跟size-tiered不同的是leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层全局有序的意味着一个key在每一层至多只有一条记录不存在冗余记录。之所以可以保持全局有序是因为合并策略和size-tiered不同。
① L1的总大小超过L1本身大小限制 ② 此时会从L1中选择至少一个文件然后把它跟L2有交集的部分进行合并。生成的文件会存放在L2 此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable那么就需要将L1中第二个SSTable与L2中前三个SSTable执行compact操作。
③如果L2合并后的结果仍然超出L5的阈值大小需要重复之前的操作选至少一个文件将它合并到下一层。多个不相干的合并是可以并发进行的
相较于size-tiered策略来说每层内key是不会重复的即使是最坏的情况除最外层外其余层都是重复key按照相邻层大小比例为10来算冗余占比也很小因此空间放大问题得到缓解。但是写放大问题会比较突出。最坏场景如果LevelN层每个SSTable的key的方为跨度很大 覆盖了LevelN1层所有key的范围那么进行compact时将涉及LevelN1层的全部数据。
三、对LSM的点查
