LevelDB之Leveled-Compaction

2024-01-20 20:32
文章标签 compaction leveldb leveled

本文主要是介绍LevelDB之Leveled-Compaction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://github.com/imjoey/blog/issues/6

https://www.jianshu.com/p/99cc0df8ed21

https://juejin.im/post/5c99f0556fb9a070e82c1fcf

目录

一、前言

二、LSM

1、MemTable

2、ImmutableMemTable

3、SSTable

4、SSTable Compaction

三、RockDB的合并策略图解

1、 L0 compaction

2、 高层Compaction

3、 并行Compaction

四、size-tired和level合并策略比较

一、前言

LevelDB是Google出品的具有读写高性能的存储引擎，其没有采用传统的B+ Tree（MySQL InnoDB）的存储模型，而是使用了LSM（Log Structure Merge-Tree)。LSM模型中的一个重要组成就是称作SSTable（Sorted String Table）的结构。本文先简单介绍LSM中使用的几种结构，然后着重介绍在众多Compaction算法中的Leveled-Compaction。

二、LSM

LSM是通过将磁盘的随机写改为顺序写来提高写的性能，核心思想是把数据的添加或修改放到内存中，当内存中数据达到一定size后，然后dump（也就是变成了顺序写）到磁盘中。LSM中有MemTable、ImmutableMemTable、SSTable等几个概念，下面分别介绍

1、MemTable

MemTable在内存中，记录最近修改的数据。一般其内部使用SkipList结构存储按key排序后的有序数据，当其存储的数据达到一定size后，就变成ImmutableMemTable，同时新建一个新的MemTable；后续的数据修改操作均在新的MemTable内进行。

2、ImmutableMemTable

ImmutableMemTable就是只读不写的MemTable，它与MemTable一起保证的写操作无锁化。其内部的数据是有序的，所以dump到磁盘时保证了高效的顺序写，形成了新的SSTable文件。

3、SSTable

SSTable内存储的是一系列的有序键值对，形式如下图所示。当SSTable文件较大时，为了提高读的性能，也可以生成key-offset索引，此索引一般都记录在内存中。

4、SSTable Compaction

由于不断有ImmutableMemTable会dump到磁盘中成为新的SSTable文件，所以SSTable文件的数量会逐渐增多，其内部存储的数据也会产生很多过期数据（key的旧数据），所以需要对SSTable文件进行定期Compaction，一方面减少SSTable文件的数量，同时也删除过期的数据。

SSTable Compaction有多种算法，比如Cassandra默认的基于文件大小的Size-Tired Compaction、基于时间序列的Date-Tiered Compaction，以及Leveled Compaction。

这里主要以Cassandra中的Leveled Compaction算法为例来分析（这也是LevelDB名字的由来）。

Leveled Compaction

SSTable被划分到不同的level中，详细的Leveled Compaction算法描述如下：

  • 每个SSTable文件的固定大小为160M

  • 从ImmutableMemTable创建的SSTable文件划分到Level-0中

  • 每个Level有SSTable文件数量的限制。在除了Level-0的任意Level中，两级Level之间的SSTable文件数量呈指数级倍数。比如：Level-1中有10个SSTable文件，Level-2有100个SSTable文件

  • 在除了Level-0的任意Level中，SSTable文件之间所包含的key的范围不重叠。（也就是说，每个Level的所有SSTable文件，可以看做是一个大的SSTable文件）

  • 如果Level-0中SSTable数量超过限制（比如：4），那么自动回将这4个Level-0的SSTable文件与Level-1的所有10个SSTable文件进行Compaction。（这里需要特别注意：level-0比较特殊，各个SSTable之间是有重叠的，所以只能将4个SSTable与Level1中所有进行整体上的Merge和切分（如原博客所述）。但level-1及其以上，各个SSTable之间没有重叠key，当SSTable个数超过阈值时，可以只选择一个或者多个SSTable与下一level值域对应的SSTable进行合并，由于每一级的SSTable大小相同，可以有效避免写放大）

  • 在Compaction过程中，首先对所有的SSTable文件按key进行归并排序，然后将排序后结果写入到新的SSTable文件中，如果SSTable文件大小到了160M上限，就新生成SSTable继续写。如此类推，直到写完所有数据。

  • 删除参与Compaction的Level-0的4个和Level-1的10个旧的SSTable文件

  • 此时Level-0的SSTable便merge到Level-1中了，那么如果Level-1的SSTable文件数量超过上限，那么就从Level-1中选出 1 个超量的SSTable文件，然后将其与Level-2中的SSTable文件进行Compaction。

    • 查看选出的Level-1 SSTable文件中key的范围

    • 从Level-2中选出能覆盖该范围的所有SSTable文件

    • 将以上的所有SSTable文件根据上面介绍的算法继续进行Compaction

    注：一般情况下，Level-1和Level-2的Compaction，只会涉及Level-2内大概1/10的SSTable文件，这样可以大幅降低参与Compcation的SSTable文件数量（相比于Size-Tired Compaction），进一步提升提升性能

  • 如果Level-2中的文件数量超过限制，则继续按照上述算法选出超量的SSTable文件与Level-3中的SSTable文件进行Compaction

三、RockDB的合并策略图解

1、 L0 compaction

当L0的文件数量达到level0_file_num_compaction_trigger的值时，触发L0和L1的合并。通常必须将所有L0的文件合并到L1中，因为L0的文件的key是有交叠的(overlapping)。

L0与L1的compaction

2、 高层Compaction

当L0 compaction完成后，L1的文件总size或者文件数量可能会超过阈值，触发L1向L2的合并。从L1至少选择一个文件，合并到L2中key有交叠的文件中。

L1向L2合并

同样的，合并后可能会触发下一各level的compaction。

合并后的L2

L2向L3合并

合并后的L3也需要做Compaction.

 

合并后的L3

3、 并行Compaction

并行compaction

max_background_compactions控制了并行compaction的最大数量。

四、size-tired和level合并策略比较

上文已经提到，我们需要对SSTables做合并：将多个SSTable文件合并成一个SSTable文件，并对同一个key，只保留最新的值。

那这里讨论的合并策略（Compaction Strategy）又是什么呢？

A compaction strategy is what determines which of the sstables will be compacted, and when.

也就是说，合并策略是指：1）选择什么时候做合并；2）哪些SSTable会合并成一个SSTable。

目前广泛应用的策略有两种：size-tiered策略和leveled策略。

  • HBase采用的是size-tiered策略。
  • LevelDB和RocksDB采用的是leveled策略。
  • Cassandra两种策略都支持。

这里简要介绍下两种策略的基本原理。后面研究LevelDB源码时再详细描述leveled策略。

size-tiered策略

简称STCS（Size-Tiered Compaction Strategy）。其基本原理是，每当某个尺寸的SSTable数量达到既定个数时，合并成一个大的SSTable，如下图所示：

 

stcs

 

 

它的优点是比较直观，实现简单，但是缺点是合并时的空间放大效应（Space Amplification）比较严重，具体请参考Scylla’s Compaction Strategies Series: Space Amplification in Size-Tiered Compaction。

空间放大效应，比如说数据本身只占用2GB，但是在合并时需要有额外的8G空间才能完成合并，那空间放大就是4倍。

leveled策略

STCS策略之所以有严重的空间放大问题，主要是因为它需要将所有SSTable文件合并成一个文件，只有在合并完成后才能删除小的SSTable文件。那如果我们可以每次只处理小部分SSTable文件，就可以大大改善空间放大问题了。

leveled策略，简称LCS（Leveled Compaction Strategy），核心思想就是将数据分成互不重叠的一系列固定大小（例如 2 MB）的SSTable文件，再将其分层（level）管理。对每个Level，我们都有一份清单文件记录着当前Level内每个SSTable文件存储的key的范围。

Level和Level的区别在于它所保存的SSTable文件的最大数量：Level-L最多只能保存 10 L 个SSTable文件（但是Level 0是个例外，后面再说）。

 

lcs

 

 

注：上图中，"run of"就表示一个系列，这些文件互不重叠，共同组成该level的所有数据。Level 1有10个文件；Level 2有100个文件；依此类推。

下面对照着上图再详细描述下LCS压缩策略：

先来看一下当Level >= 1时的合并策略。以Level 1为例，当Level 1的SSTable数量超过10个时，我们将多余的SSTable转存到Level-2。为了不破坏Level-2本身的互不重叠性，我们需要将Level-2内与这些待转存的SSTable有重叠的SSTable挑出来，然后将这些SSTable文件重新合并去重，形成新的一组SSTable文件。如果这组新的SSTable文件导致Level-2的总文件数量超过100个，再将多余的文件按照同样的规则转存到Level-3。

再来看看Level 0。Level 0的SSTable文件是直接从memtable转化来的：你没法保证这些SSTable互不重叠。所以，我们规定Level 0数量不能超过4个：当达到4个时，我们将这4个文件一起处理：合并去重，形成一组互不重叠的SSTable文件，再将其按照上一段描述的策略转存到Level 1。

 

这篇关于LevelDB之Leveled-Compaction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/627244。

相关文章

HBase原理 | HBase Compaction介绍与参数调优

HBase原理 | HBase Compaction介绍与参数调优

我们知道，数据达到HBase服务端会写WAL-写Memstore，然后定期或满足一定条件时刷写磁盘生成一个HFile文件，随着时间推移生成的HFile会越来越多，将会影响HBase查询性能，同时会对HDFS造成一定影响。因此HBase会定期执行Compaction操作以合并减少HFile数量。 1.两种合并 HBase中Compaction分为两种。Minor Compaction称为小合并，主
阅读更多...
在netbeans下编译leveldb源码

在netbeans下编译leveldb源码

第一步：# git clone https://code.google.com/p/leveldb 下载leveldb源码 #cd leveldb #sudo chmod +x build_platform 修改为可执行文件 第二步：下载netbeans8.1 sh     xxxxxx.sh   即可安装 第三步：将leveldb源码导入netbeans
阅读更多...
【AI】caffe使用步骤（一）：将标注数据生成lmdb或leveldb

【AI】caffe使用步骤（一）：将标注数据生成lmdb或leveldb

1、简述 caffe使用工具 convert_imageset 将标注数据转换成lmdb或leveldb格式，convert_imageset 使用方法可以参考脚本examples/imagenet/create_imagenet.sh。 convert_imageset 在./build/tools/中。 2、convert_imageset命令行参数 ./build/tools/conv
阅读更多...
HBase_HBase_原理_Compaction 基于HBase 2.0

HBase_HBase_原理_Compaction 基于HBase 2.0

参考文章： 深入理解 HBase Compaction 机制 https://blog.csdn.net/u011598442/article/details/90632702   HBase的文件合并（minor/major compact） http://www.bubuko.com/infodetail-3366448.html   HBase的文件合并（minor/major
阅读更多...
leveldb 键值数据库

leveldb 键值数据库

#git clone --recurse-submodules https://github.com/google/leveldb.git拉取子模块 及第三方库#mkdir -p build && cd build#cmake -DCMAKE_BUILD_TYPE=Releas .. && make 测试demo #include <assert.h>#include <string.h
阅读更多...
ActiveMQ高可用集群安装、配置（zookeeper + LevelDB）

ActiveMQ高可用集群安装、配置（zookeeper + LevelDB）

从ActiveMQ5.9开始，ActiveMQ的集群实现方式取消了传统的Master-Slave方式，增加了基于zookeeper + LevelDB的Master-Slave实现方式，其他两种方式“目录共享”和“数据库共享”依然存在。 三种集群方式的对比： （1）基于共享文件系统（KahaDB，默认） <persistenceAdapter>     <kahaDB directory="
阅读更多...
LevelDB

LevelDB

levelDB介绍 官方文档的介绍翻译：Leveldb 基本介绍和使用指南 介绍lDB的起源和特性：LevelDB介绍（非常详细） 详细介绍levelDB的缓存架构和持久化文件结构、基本操作接口：【深度知识】区块链数据库LevelDB从入门到原理详解
阅读更多...
分布式专题——详解Google levelDB底层原理

分布式专题——详解Google levelDB底层原理

本文始发于个人公众号：TechFlow，原创不易，求个关注 今天是分布式专题的第10篇文章，我们继续来聊聊LSMT这个数据结构。 LSMT是一个在分布式系统当中应用非常广泛，并且原理直观简单的数据结构。在上一篇文章当中我们进行了详细的讨论，有所遗忘或者是新关注的同学可以点击下方的链接回顾一下上一讲的内容。 分布式——吞吐量巨强、Hbase的承载者 LSMT leveldb简介 上一篇的内容
阅读更多...
ios-leveldb

ios-leveldb

http://blog.devzeng.com/blog/ios-leveldb.html http://www.code4app.com/thread-11657-1-1.html 去掉armv6,armv7,以及模拟器的架构。
阅读更多...
leveldb源码阅读-memtable

leveldb源码阅读-memtable

memtable在leveldb中扮演着及其重要的地位，用于存储最新的数据修改信息，当数据的规模达到一定的上限之后，就会将数据转存储为immutable memtable，这时候就会被存储到sstale中；因此总的来说，所有在内存的数据都是以memtable进行存储的； memtable的接口如下： void Ref() { ++refs_; }//引用次数// Drop referenc
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2