2PC 协议

Google Percolator 协议

Percolator 协议就是用来解决 Bigtable 的跨行事务，其本质是二阶段提交协议的优化。
Percolator 利用到 Bigtable 的一个重要特性：每个 cell 的数据保留有时间戳，多版本；读取时可以指定数据的版本。

BigTable 单行事务

支持读修改写操作在单行数据上保证原子性。

引言

eBPF 是 Linux 内核中一个非常灵活与高效的类虚拟机，能够在许多内核hook点安全地执行字节码。eBPF 在将程序附加到内核发生的事件中，每当事件发生，都将触发eBPF程序运行。

原理

eBPF程序是事件驱动的，当内核或应用程序通过某个钩子点（hook point）时触发执行。预定义的钩子包括：系统调用、函数进入/退出、内核跟踪点、网络事件等。

cilium ebpf 使用

项目地址: https://github.com/cilium/ebpf

// 加载提前编译的c语言
objs := bpfObjects{}
if err := loadBpfObjects(&objs, nil); err != nil {
    log.Fatalf("loading objects: %v", err)
}

追踪函数

• kprobes 内核动态探针
  • 分别是pre_handler、post_handler和fault_handler
• kretprobe
  • 用于探测函数的返回值以及计算函数执行的耗时。
• USTD 用户静态探针
  • 用户态预定义静态跟踪，它是用户态下的tracepoints
• uprobes 用户动态探针
  • 在用户态和内核态的kprobe对应，能实现在函数入口、特定偏移处以及函数返回处进行插桩。
• tracepoints 内核静态探针
  • 是内核开发人员在内核代码中的埋点，是开发者在内核源代码中散落的一些hook，开发者可以依托这些hook实现相应的追踪代码插入。通常比较稳定：能够保证不同内核版本间的兼容性

引言

OpenTracing 是分布式调用链标准，用于解决不同的分布式追踪系统API不兼容的问题。

OpenTracing 概念

Trace: 一个完整的请求链路

• 整条链路会用一个唯一标识TraceId来标识。

Span: 一次调用过程

• 一次rpc调用，HTTP请求就是一个Span.

SpanContext: Trace的全局上下文信息，会包含TraceId

• 包含整个链路的调用时间，耗时等信息。

SkyWalking 学习

介绍

BERT的全称是Bidirectional Encoder Representation from Transformers，是 Google 在2018年提出的一种NLP 模型。
BERT逐步取代word2vec与lstm等技术，成为主流NLP主流框架。
BERT是基于transformer衍生出来的预训练模型。

什么是Transformer模型

Transformer 是一种使用注意力机制来提高模型训练速度的模型。

引言

在OLTP场景下，用户需要足够全的字段数据，会对数据频繁的插入更新删除，选择行存储会比较合适。在OTAP的场景下，数据分析可能只需要某些字段，无需将所有字段数据捞出，可能基于多表构建物化视图，这种方式选择列存储更灵活。

哪些数据是行存储，哪些数据库是列存储

行存储的组件有Mysql,TiDB。列存储的产品有Hbase,TiFlash,GP。

列式存储Hbase

Hbase 表存储中有列族与列的定义，列族是固定的，列族下的列是稀疏的，可动态增加。
Hbase 存储按照region进行切分，一个region中包含多个hstore，一个hstore对应table中的一个列族存储的部分数据。一个hstore由两部分组成，一部分是memstore，另一部分是storefile，底层就是Hfile。

行存储TiDB

TiDB的数据存储在TiKV,一条数据映射在TiDB中的结构如下:

1
2

Key:   tablePrefix{TableID}_recordPrefixSep{RowID}
Value: [col1, col2, col3, col4]

其中value会将每个column 按照”,” join存储 。

引言

RocksDB 在 Facebook 开始时是作为各种存储介质上服务器工作负载的存储引擎，最初专注于快速存储（尤其是闪存存储）。这是一个C++库，用于存储任意大小的keys和values。它支持点查找和范围扫描，并提供不同类型的 ACID 保证。
RocksDB借鉴了开源leveldb项目的重要代码以及Apache HBase的想法。最初的代码是从开源leveldb 1.5派生而来。也基于在RocksDB之前在Facebook开发的代码和想法。

上层结构

RocksDB的三个组成部分有memtable，sstfile和logfile。memtable是一个内存型数据结构。新的写入会写进memtable，并且可以有选择的写入logfile。logfile是一个顺序写入的文件。当一个memtable 内存写满，相应的刷写到磁盘上的sstfile，相应的logfile也可以安全的删除。sstfile中的数据是有序的。

源码分析

Memtable 数据结构

Memtable 是一个持有数据的内存数据结构，在落盘成为sstfile文件操作之前。memtable 同时用于读写，新的数据会写入memtable，读操作也必须查询memtable，因为在memtable中的数据是最新的。有一个后台线程会将memtable中的数据刷写到一个SST文件。

默认memtable的实现是基于skiplist。用户也可以使用其他数据结构，比如 HashLinkList，HashSkipList或者Vector

Raft协议

分布式存储系统通常通过维护多个副本来进行容错，提高系统的可用性。要实现此目标，就必须要解决分布式存储系统的最核心问题：维护多个副本的一致性。而Raft正是为探索一种简单易理解的一致性算法而产生的，Raft是管理日志复制的一致性算法。

Raft 协议所要达成的结果与multi-paxos相同，但是Raft协议的结构与Paxos不同，Raft协议更简单，更容易让人理解。

Raft 将一致性算法分解成四个关键模块

• Leader选举
• 日志复制
• 安全性
• 成员变更

状态机复制 Replicated state machines

一致性算法主要出现在状态机复制中。一组机器之间进行数据同步，当一些机器宕机后，还能继续工作。状态机复制就是用来解决在分布式系统产生的一系列容错问题。状态机制复制使用一个日志复制来实现，每个server都有一个log模块包含一系列的命令，这一系列的命令都有相同的顺序，并被各个server有序执行。

保证日志复制的一致性是一致性算法的职责。Server中的一致性模块接受从客户端传来的命令，将这些命令加入到log中。和其他server中的一致性模块沟通保证每一条log都包含相同的请求，并以相同的顺序执行，即使一些server宕机。

一旦命令被正确复制，每个服务器的状态机按日志顺序处理，并将输出返回给客户端。最终，这些servers形成一个单一的，高度可靠的状态机。

实际系统中一致性算法具有以下特性:

• 保证安全性，在所有拜占庭问题，包括网络延迟，分区和数据包丢失，数据包重复和重新排序问题。
• 只要大多数server可以运行，可以相互通信。因此，一个典型的五台server的集群，可以容忍2台server宕机。server失败恢复也可以重新加入集群。
• 不依赖时间保证日志的一致性：错误的时钟和极端的消息延迟，在最坏的情况下，可能会导致可用性问题。
• 绝大多数服务器处理完命令，即可响应请求返回；少数服务器慢不影响整体系统性能。

Paxos 有什么问题？

paxos主要说的单个决策达成一致的协议，比如一条需要复制的数据。多个实例之间组成的一系列决策称之为multi-Paxos。paxos保证了安全性和可用性，也支持集群关系的变更。
不幸的是，Paxos有两个重要的缺点。第一个缺点是Paxos难以理解。
第二个缺点是paxos没有为构建实际实现提供良好的基础。这其中一个原因是多实例paxos算法并没有广泛认可。Lamport的理论大部分都是说的单个决策Paxos协议，对于多实例paxos只是大致勾勒，很多细节是缺失的。

Paxos的架构难以构建实用的系统。

Paxos 的实现采用弱领导化的设计，但是在实际系统中，会选择一个领导者，然后让领导者协调决策更简单、更快捷。因此，实际系统与 Paxos 几乎没有相似之处。每个实现都从 Paxos 开始，发现实现它的困难，然后开发出截然不同的架构。这是耗时且容易出错的，而且理解 Paxos 的困难加剧了这个问题。 Paxos 的公式对于证明其正确性的定理可能是一个很好的公式，但实际的实现与 Paxos 是如此不同，以至于证明几乎没有价值。

由于这些问题，我们得出结论，Paxos 没有为系统构建或教育提供良好的基础。考虑到共识在大规模软件系统中的重要性，我们决定看看我们是否可以设计出一种性能比 Paxos 更好的替代共识算法。 所以提出了 Raft 协议。

做一个可以理解的设计

在设计Raft协议中，要求以下几点目标:

• 可以构建完整和实用的系统，减少开发者的设计量。
  • 在所有条件下是安全的，在典型的操作条件下是可用的。
  • 高效的
  • 最重要的是可理解性。

采用两种方式做好可理解性。第一种方法是问题分解，将问题拆解为:

• leader 选举

• 日志复制

• 安全性

• 成员变更

  第二种方式是简化状态变化，减少需要考虑的状态，使系统更加连贯，消除不确定性。

Raft一致性算法

Raft 是一种用于管理复制日志的算法。Raft 先选举一个leader达成共识，然后让leader完全负责管理复制的日志。领导者接受来自客户端的日志条目，将它们复制到其他服务器上，并告诉服务器何时可以安全地将日志条目应用于其状态机。拥有领导者可以简化复制日志的管理。例如，领导者可以在不咨询其他服务器的情况下决定在日志中放置新条目的位置，并且数据以简单的方式从leader流向其他follower。leader可能会失败或与其他服务器断开连接，在这种情况下会选出新的leader。

采用leader 方法，Raft将一致性问题拆解为三个子问题。

• Leader election: 当已有leader宕机，必须选择一个新的leader。
• Log replication: leader 接受客户端提交的日志，并将其复制到集群中其他节点。
• Safety: 如果大多数服务器已将特定的日志条目应用到其状态机，则没有其他服务器可以对相同的日志索引应用不同的命令。

Raft基础概念

一个Raft集群包含多个节点，一般为5个节点，此时可以允许有两个节点宕机。任何时候每个节点都会处于leader，follower，candidate三种角色中的其中一个。一般情况下，是有一个leader节点，其他节点都是follower节点。followers是被动的，他们不会主动请求更多的是响应leader的请求，leader节点负责处理所有客户端的请求（如果一个客户端将请求打到follower节点，follower节点会转发给leader节点）。第三种状态候选人节点，用于选举一个新的leader节点。

Raft 把时间切割为任意长度的任期，每一个任期都有一个任期号，才用连续的整数。每个任期都由一次选举开始，若选举失败则这个任期内没有leader，如果选举了Leader则这个任期内有Leader负责状态管理。

引言

本文介绍 Golang gorouting 通信的几种机制，了解多协程之间是如何通信的。

Gorouting

Goroutine是Go中最基本的执行单元。相比于线程，线程是进程中一个单位，由物理CPU进行调度，拥有自己的栈空间，共享堆空间。Gorouting是Go的协程实现，在语言层控制，由程序员在代码层显示调度。

Go runtime scheduler

go runtime 会负责goroutine的生老病死，从创建到销毁。Runtime会在程序启动的时候，创建M个线程，创建N个gorouting 都会依附在这M个线程上执行。这就是M:N 模型。

Schedueler 包含三个部分，g，m，p。

• 全局队列（Global Queue）：存放等待运行的 G
• g 代表gorouting
• p 代表一个虚拟的processor，它维护一个处于 Runnable 状态的 g 队列。在程序启动时创建，并保存在数组中。
• m 表示内核线程，包含正在运行的 goroutine 等字段。m线程想运行任务就得获取 P，从 P 的本地队列获取 G，P 队列为空时，M 也会尝试从全局队列拿一批 G 放到 P 的本地队列，或从其他 P 的本地队列偷一半放到自己 P 的本地队列。M 运行 G，G 执行之后，M 会从 P 获取下一个 G，不断重复下去。

有关 P 和 M 的个数问题

P 的数量

• 由启动时$GOMAXPROCS或者由 runtime 的方法GOMAXPROCS()决定。

M 的数量

• go 语言本身的限制：go 程序启动时，会设置 M 的最大数量，默认 10000. 但是内核很难支持这么多的线程数，所以这个限制可以忽略
• runtime/debug 中的 SetMaxThreads 函数，设置 M 的最大数量
• 一个 M 阻塞了，会创建新的 M。

P 和 M 何时会被创建

复用线程：避免频繁的创建、销毁线程，而是对线程的复用。

• work stealing 机制： 当本线程无可运行的 G 时，尝试从其他线程绑定的 P 偷取 G，而不是销毁线程。
• hand off 机制：​ 当本线程因为 G 进行系统调用阻塞时，线程释放绑定的 P，把 P 转移给其他空闲的线程执行。

一个gorouting调度流程如下

1. 创建一个新的gorouting
2. 放到本地或者共享队列中
3. M 负责唤醒线程或者创建线程启动goroutine
4. 循环调度
5. 尝试或者一个gorouting 执行
6. 清理，M进入重新循环调度。

通信方式

• 全局共享变量
• channel通信
• Context包

全局共享变量

声明一个全局环境变量， 所有子goroutine共享这个变量，并不断轮询这个变量检查是否有更新。

channel通信

go中有一个数据类型 chan，用于在gorouteines之间消息通信，具备缓存功能。

channel 特性

• 线程安全：hchan mutex
• 先进先出：copying into and out of hchan buffer
• channel的高性能所在：
  • 调用runtime scheduler实现，OS thread不需要阻塞；
  • 跨goroutine栈可以直接进行读写；

channel的使用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func main() {
	//创建通道
	data := make(chan int)
	//创建一个等待组
	var wg  sync.WaitGroup
	wg.Add(3)
	go func() {
		for d := range data {//通过range不断地处理data
			fmt.Println(d)
			wg.Done()
		}
	}()

	data <- 1//发送要放在接收协程跑起来后面，因为发送后会阻塞等待接收
	data <- 2
	data <- 3
	//等待channel中所有的数据输出
	wg.Wait()
	close(data)
}

channel类型：无缓冲和缓冲类型

channel有两种形式，一种是有缓冲的，一个协程向这个channel发送了消息后，回阻塞当前这个线程，直到其他协程接受到这个channel。

无缓冲的初始化方式

1

intChan := make(chan int)

缓冲channel的初始化方式:

1

intChan := make(chan int， 3)

channel的几种情况

• 当写入数据超出缓冲空间会阻塞。
• 向nil channel写入和读取数据会阻塞

channel一般会和select机制配合，select的运行机制如下：

• 选取一个可执行不阻塞的case分支，如果多个case分支都不阻塞，会随机算一个case分支执行，和case分支在代码里写的顺序没关系。
• 如果所有case分支都阻塞，会进入default分支执行。
• 如果没有default分支，那select会阻塞，直到有一个case分支不阻塞。

channel 通过 mutex（锁）来保证多个 goroutine 来访问 channel 的时候是安全的，它的底层是一个叫做hchan的结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

type hchan struct {
  //channel分为无缓冲和有缓冲两种。
  //对于有缓冲的channel存储数据，借助的是如下循环数组的结构
	qcount   uint           // 循环数组中的元素数量
	dataqsiz uint           // 循环数组的长度
	buf      unsafe.Pointer // 指向底层循环数组的指针
	elemsize uint16 //能够收发元素的大小
  

	closed   uint32   //channel是否关闭的标志
	elemtype *_type //channel中的元素类型
  
  //有缓冲channel内的缓冲数组会被作为一个“环型”来使用。
  //当下标超过数组容量后会回到第一个位置，所以需要有两个字段记录当前读和写的下标位置
	sendx    uint   // 下一次发送数据的下标位置
	recvx    uint   // 下一次读取数据的下标位置
  
  //当循环数组中没有数据时，收到了接收请求，那么接收数据的变量地址将会写入读等待队列
  //当循环数组中数据已满时，收到了发送请求，那么发送数据的变量地址将写入写等待队列
	recvq    waitq  // 读等待队列
	sendq    waitq  // 写等待队列
	lock mutex //互斥锁，保证读写channel时不存在并发竞争问题
}

如上图是channel的底层数据结构。

• buf: 用来保存goroutine之间传递数据的循环链表
• sendx和recvx: 用来记录此循环链表当前发送或接收数据的下标值
• sendq 和 recvq: 用于保存向该chan发送和修改chan接收数据的goroutine的队列
• lock: 保证channel写入和读取数据时线程安全的锁 。

lock 在给channel发送数据和消费的数据的时候使用，发送数据时，给buf加锁，将数据copy到buf中，sendx++，然后释放对buf的锁。

消费数据的时候，对buf加锁，将buf中的数据copy到变量内存中，recvx++,并释放锁。

可以发现底层是通过hchan结构体的buf，使用copy内存的方式进行通信，最终达到共享内存的目的。这也体现了Go中的CSP并发模型。

• CSP并发模型：不要以共享内存的方式来通信，相反，要通过通信的方式来共享内存。

channel发送流程

向一个channel 发送数据的时候，流程如下:

1. 如果接收队列recvq不为空，说明缓冲区中没有数据或者没有缓冲区，此时直接从recvq中取出G,并把数据写入，最后唤醒G。结束发送过程
2. 如果缓冲区有空余位置，将数据写入缓冲区，结束发送过程
3. 如果缓冲区没有空余位置，将待发送数据写入G,将当前G加入sendq，进入睡眠，等待被读G唤醒。

有goroutine阻塞在channel recv队列时，此时缓存队列为空，则直接将消息发送给reciver gourotine，只产生一次数据copy。

channel 写入流程

向一个channel写入数据的时候，流程如下：

1. 如果channel上的recveq队列非空的时候，跳过channel的缓冲队列，直接将数据发送给接受的gorouting
   1. 调用sendDirect方法，将待写入的消息发送给接收的goroutine
   2. 释放channel的全局锁
   3. 调用goready函数，将接收消息的goroutine设置成就绪状态，等待调度
2. 缓存队列未满，则将消息复制到缓存队列上，然后释放全局锁
3. 缓存队列已满且接收消息队列recv为空，则将当前的goroutine加入到send队列
   1. 获取当前gorouting的sudog，然后加入到channel的sendq队列
   2. 将当前gorouting睡眠。

LevelDB RocksDB Boltdb Comparion

LevelDB

LevelDB 是 Google 的 Jeff Dean和Sanjay Ghemawat 设计开发的KV存储类型的依赖包，其本质是一个有序的数据Map。
LevelDB 底层采用 LSM-Tree 数据结构，设计实现类似于单个节点的Bigtable tablet ，两者底层存储的文件数据不一样。

LevelDB 的每个 database 由某个目录下的一堆有序文件组成。其中包含的文件类型有:

log file

用于存储一系列更新的操作。每个操作都会append到当前log 文件，当log文件达到预定大小（默认约为4MB）时，log文件会转换成一个sorted table，并创建出一个新的log文件用于存储新的updates操作。

当前正在写入log file的数据会有一份副本保存在内存结构（memtable）中。每次读取数据都会查阅内存中的副本数据。

Sorted tables

一个sorted table (*.ldb) 存储了一系列基于key排序的数据，每条数据要么是key的value，要么是删除标记。（删除标记是为了隐藏sorted table中已经被删除的数据）。

一系列sorted table 用level级别管理起来，默认生成的sorted table的level是0级别，当level-0级别的文件数量超过了阈值（当前是4），会将4个level-0的文件与已有的level-1文件进行合并。（level-1级别每mb生成一个文件。）

在初级的文件可能包含重复的keys，但是在其他层级这些keys会去重。当Level-L级别的文件存储超过(10^L) MB ，就会将其和Level-(L+1)的文件合并成新的文件。这些合并通过逐步迁移update操作丛低级别到高级别，采用批量读写的方式，保证迁移带来的搜索效率降低。

Manifest文件

MANIFEST 文件列出了组成每个level的sorted tables，以及sorted table的键值范围和其他重要元数据。每当database打开的时候，一个Manifest文件（伴随着一个number）都会创建。MANIFEST 文件会用来做日志记录，当产生文件的添加和删除都会追加到MANIFEST 文件中。

Current

CURRENT 是一个text文件，用于描述当前最新Manifest文件的名字。

Info logs

日志信息会打印到 LOG and LOG.old 文件中。

Others

还有一些其他用处的文件，比如 LOCK, *.dbtmp。

Level 0

当 log file 增长到一个确定的大小（默认是4MB）: 创建一个新的memtable和log file，用于处理新的请求。后台的步骤如下:

1. 将当前memtable写入到一个sstable中。
2. 放弃当前memtable。
3. 删除老的log file 和老的memtable。
4. 添加一个新的sstable加入到level-0层级中。

Compactions

当Level-L的大小超过它的limit，会使用一个后台线程进行压缩。从Level L级别中抽取一个文件，将其和所有Level+1有重叠的文件进行合并。由于Level-L是Level L+1 级别的一部分，当压缩完成后，原有用于合并的Level- L+1的文件会丢弃。对于Level-1和Level-0级别的文件比较特殊，可能会选取多个Level-0级别的文件与Level-1进行合并，因为Level-0级别的文件会有一些重叠。

压缩产生一系列level-(L+1)级别的文件，如果当前输出文件达到(2MB)大小，就会切换输出一个新的level-(L+1)文件。当当前输出的文件键值对范围与下一级别的文件重叠超过了10个文件，也会切换到一个新的文件进行输出，这条规则保证了压缩不会从下一级别抽取太多的数据。

旧的文件文件被丢弃，新文件会标记为处于服务状态。

对于每个Level L级别的文件，我们会记住最后一次压缩的末尾key。下一次压缩会从这个key之后的第一个文件进行合并。（如果没有这个文件，就会将这个key所在文件进行压缩）

压缩会丢弃覆盖的值。如果没有更高Level的文件键值对包含了当前key，就会舍弃已经标记为删除的数据。

Timing

Level-0 级别的压缩，读取四个1MB Level-0文件，最多读取10MB的Level-1文件。我们会读取14MB并写入14MB。

除了Level-0级别的压缩比较特殊，比如我们从 Level-0 读取一个2MB的文件，最坏的情况下，这将与Level L+1 重叠12个文件（其中10个文件是因为Level L+1 是 Level L 的10倍文件范围，另外两个文件处于边界范围，因为Level L与Level L+1的文件范围对齐）。因此，压缩将读取 26MB 并写入 26MB。假设磁盘 IO 速率为 100MB/s（现代驱动器的大致范围），最差的压缩成本将约为 0.5 秒

如果我们将后台写入限制为较小的值，例如 100MB/s 速度的 10%，则压缩可能需要 5 秒。如果用户以 10MB/s 的速度写入，我们可能会构建大量的 0 级文件（约 50 个来容纳 5*10MB）。由于在每次读取时将更多文件合并在一起的开销，这可能会显着增加读取成本。

解决读取成本过高的问题有三种方案：

方案一: 增加log file 阈值大小，这种方式会需要更多的内存保存对应的memtable。

方案二: 降低写入速率。

方案三: 在内存memtable中提前合并，提高效率。

Number of files

与其总是产生2MB的文件，我们可以增加文件大小，减少产生的文件数目。
可能会带来更多的突发性的压缩，我们可以将文件存储到多个目录中。

有一项关于在目录中打开文件数的消耗时间对比:

Recovery

恢复流程如下:

• 读取 CURRENT 文件找到最新提交的 MANIFEST 文件
• 读取 MANIFEST 文件
• 清理旧文件
• 我们可以打开所有的sstables，但最好是懒加载。
• 将log chunk 转换成一个新的level-0 sstable。
• 开始将新的写入到一个新的拥有恢复序列的日志文件。

Garbage collection of files

在每次压缩结束和恢复结束的时候都会调用 RemoveObsoleteFiles 方法。它会查找数据库所有文件，它会删除所有不是当前当前日志文件的日志文件。它会删除所有未从某个Level引用且不是当前正在压缩的输出的table文件。

RocksDB

Rocksdb 是fackebook数据库团队提供。也是采用 Log-Structured-Merge-Database (LSM) 数据结构，可在读放大，写放大， 空间放大之间做好权衡。具有多线程压缩数据的功能，可以用于存储数TB级别的数据。

LSM 介绍

LSM 原理是将数据先写入内存中， 当满足一定大小后，将其刷写到磁盘上生成一个文件。

随着文件越来越多，读操作需要查询多个文件。所以LSM具备Compaction 机制，将生成的文件不停的合并，保证读操作性能。

Compaction 机制有一些取舍，如果不做compaction操作，读取操作性能会越来越低，如果生成文件就立即执行compaction操作，对磁盘压力也很大。

compaction机制的取舍会带来以下三个问题:

• 读放大: LSM 将数据拆分成很多个文件，需要逐级查找，想要查询到想要的数据，可能需要不止一次I/O操作，打开多个文件。

• 空间放大: 由于LSM都有定期压缩的功能，所以无效数据不会立即清理，空间存储有冗余数据。

• 写放大:从用户视角是写了一遍数据，但是在后台包含 redo log的写入/内存数据 Immutable Memtable 写入到 L0 文件以及文件进行压缩重新回写磁盘。

LSM Compaction 有level 和 size-tiered两种实现。

Size-Tiered Compaction

从名字可以看出Size-Tiered 是当Level 0里的文件数量达到一定数量，就开始进行合并至Level 1。每一层都有文件数量的条件判断，满足就进行Compaction。这种方式导致每一层都不是全局有序，只能保证某个文件是有序的。

Leveled Compaction

Leveled 保证每一层都是全局有序的，当Level 0有四个文件后，就将Level 0里文件与Level 1的数据进行合并，保证Level 1全局有序。

Boltdb

boltdb 相比于rocksdb和leveldb，采用的是b+tree数据结构。如果你的场景是大量的随机读写，leveldb是一个不错的选择。如果你的应用读取需要大量读取或者进行大范围的范围扫描，boltdb是一个不错的选择。