跳转至

Pebble

1. Pebble详解:入门介绍

Pebble是一个使用Go语言开发的KV单机存储引擎。底层数据模型是LSM树,与LSM树方式实现的其它存储引擎如LevelDB,RocksDB等有类似的特性,是一个不可变的磁盘写优化数据结构,它适用于写入比查找更频繁的系统。

Pebble基于goLevelDB开发,扩展了RocksDB的一些功能,但是并没有完全支持RocksDB的所有功能。其主要目的是替换CockroachDB数据库的存储引擎,目前已经作为其默认存储引擎。

LSM树

日志结构合并树(或LSM树), 是一种分层、有序、面向磁盘的数据组织方式,其核心思想是充分了利用了磁盘顺序写比随机写性能高的特点。

LSM树消除了随机插入、更新和删除,LSM树在内存中写入和更新,直到其大小达到阈值,然后再写出到磁盘。查询数据时需要查找内存部分,如果内存中存在待查找的key则返回,如果不存在,则需要从磁盘文件中查找。虽然LSM树的写入简单高效,但是很明显的缺点是对读取操作,特别是随机读并不友好,对于读取操作,通常需要进行缓存、索引、磁盘文件组织方面的优化。LSM树适合写多读少的场景。

传统关系型数据库通常底层使用的是B+树,B+树和LSM树有什么异同呢?让我们比较一下B+树和LSM树的特性。

LSM树具有以下特性:

  • Append-Only,SST只写在磁盘上一次,从不更新。
  • 读取可能需要从多个SST读取数据,同一个key可能会落在不同的数据文件中,返回给客户端之前,数据必须经过合并。
  • 因为写入和删除都被顺序写入到磁盘中,通常需要压缩操作来合并数据记录和垃圾收集。
  • O(1),读取O(N),经过索引和缓存优化后可以达到O(logN)

B+树具有以下特性:

  • 就地更新和删除。更新操作可能会触发节点分裂和合并,随机读写概率会变大。
  • 是经过读取优化的,这意味着不需要从多个文件读取,读取效率较高。
  • 并发访问需要读写隔离,涉及lock和latch。
  • 更新导致的碎片化可能需要额外的维护和块重写。与LSM树存储相比,B树通常需要较少的维护操作。
  • O(logN),读取O(logN)

从上面的对比可以看出,LSM树对写入友好,但是对读取并不友好,并且频繁触发压缩合并会消耗较多的资源,针对压缩合并也需要大量优化避免对业务造成影响,有些数据库如阿里Polar X-Engine,将压缩卸载到FPGA,以加速压缩来消减CPU瓶颈,避免对计算资源的侵占。

整体架构

整体架构如下图所示:

在Pebble中三个主要的结构是:内存表(memtable)、SST(sstable) 以及预写日志(WAL)。内存表是内存中的结构,新的写入被插入内存表中,并且被写入到预写日志中,预写日志是在存储系统上的顺序写入文件,用于保证数据库系统中的持久性和完整性。在SST中的数据是排好序的,以方便查找。读取必须先查找内存表,再查询SST文件。一旦内存表达到阈值,就会被修改为不可变的,并创建一个新的内存表用于后续的写入。后台线程将内存表的内容刷新到SST文件,之后可以销毁内存表,然后预写日志就可以被安全地删除了。

安装使用

go get -d github.com/cockroachdb/pebble

Pebble以库的方式提供,提供了一个简单的命令用于测试,在 cmd/pebble/ 目录下。如果希望使用所有接口,可以使用单元测试目录下的测试文件进行调试研究具体接口的使用方式。

cd $GOPATH/src/github.com/cockroachdb/pebble/cmd/pebble/
go build
./pebble bench sync ./data/ -d 60s

进入./data 目录,即可看到磁盘上相关的数据库文件。

当前版本依赖cgo,cgo依赖gcc。windows上编译时,可以安装mingw64。

磁盘文件

pebble数据库的磁盘目录组织结构如下所示,后面会详细介绍具体的内容。

000017.sst              // SST
000018.log              // 预写日志文件 
CURRENT                 // 记录当前的MANIFEST
LOCK                    // 锁文件,避免多个进程同时访问这个目录
MANIFEST-000011         // 元数据,SST的层级信息等,合并过程添加新文件并从数据库中删除现有文件
                        // 并通过将它们记录在MANIFEST文件中使这些操作持久化。
OPTIONS-000012          // 配置参数

代码目录

pebble主要模块和文件如下所示:

├── bloom              // 查询时用到的布隆过滤器
├── cmd                // 可执行文件,当前可以用于测试 scan/sync/ycsb 等
├── docs               // 文档
├── sstable            // sstable 模块实现
├── tool               // 用于解析 lsm/sstable/manifest 的工具集
├── vfs                // 虚拟文件系统,用于适配不同平台的文件操作接口
├── batch.go           // 用于支持原子Set/Merge/Delete/DeleteRange的批量操作
├── cache.go           // 用于支持可配置大小的缓存,实际调用内部Cache模块
├── checkpoint.go      // Checkpoint在指定目录中构造数据库实例的快照(磁盘文件)
├── commit.go          // 操作提交,支持pipeline
├── compaction.go      // compaction 相关的逻辑
├── db.go              // DB结构,相关方法实现
├── event.go           // 事件监听模块
├── get_iter.go        // 查询get接口的迭代器,内部使用
├── go.mod             // go module文件
├── ingest.go          // 将指定路径中的所有sstable摄取到当前数据库中
├── iterator.go        // 迭代器在kv对上进行遍历
├── mem_table.go       // memTable实现了LSM在内存中的层
├── merging_iter.go    // 提供LSM不同层多个迭代器的合并视图 
├── metrics.go         // 统计信息
├── open.go            // DB open入口,及相关方法
├── options.go         // 配置选项,各层配置参数
├── snapshot.go        // 快照相关操作,快照是某个时间段的只读视图
├── version_set.go     // 版本集管理不可变多个版本,管理新版本的创建
├── internal           // 内部模块
    ├── ackseq         
    ├── arenaskl       // 跳表,无锁
    ├── base
    ├── batchskl
    ├── bytealloc
    ├── cache          // 基于CLOCK-Pro算法的缓存实现
    ├── crc 
    ├── datadriven
    ├── humanize
    ├── intern
    ├── invariants
    ├── lint
    ├── manifest
    ├── manual
    ├── metamorphic
    ├── pacertoy
    ├── private
    ├── randvar
    ├── rangedel
    ├── rate           // 流控模块
    ├── rawalloc
    └── record

Pebble详解:读写

Pebble中的写操作首先写日志文件,然后再去写内存中的内存表,写日志是为了保证数据的持久性,一旦宕机,内存表中的数据还没有持久化,系统启动时可以从日志文件中读取,进行数据恢复。

Pebble 只允许一个进程打开。操作系统将使用文件锁定来防止多个进程的并发访问。在一个进程中,Pebble 可以由多个线程访问,如果多个线程打开同一个数据库,它将仅允许第一个写线程写入数据库,而其他写线程将被阻塞。对于读写冲突,读取可以从与写入分开的不可变数据中检索数据,更新的版本将在压缩过程中生效。

写入

我们总结下在在LSM-Tree里面如何写数据的?

  1. 当收到一个写请求时,会先把该条数据记录在WAL Log里面,用作故障恢复。

  2. 当写完WAL Log后,会把该条数据写入内存的SSTable里面(删除是通过记录删除标记完成,更新是新生成一条数据),也称memtable。为了维持有序性在内存里面采用跳跃表相关的数据结构。

  3. 当Memtable超过一定的大小后,会在内存里面冻结,变成不可变的memtable,同时为了不阻塞写操作需要生成一个新的memtable继续提供服务。

  4. 把内存中不可变的memtable给dump到到硬盘上的SSTable层中,此步骤也称为Minor Compaction,这里需要注意在L0层的SSTable是没有进行合并的,所以这里的key range在多个SSTable中可能会出现重叠,在层数大于0层之后的SSTable,不存在重叠key。

  5. 当磁盘上每层的的SSTable超过一定的大小或者个数,也会周期性进行合并。此步骤也称为Major Compaction,这个阶段会真正清除掉被标记删除掉的数据以及多版本数据的合并,避免浪费空间,注意由于SSTable都是有序的,我们可以直接采用归并排序进行高效合并。

读取

1,当收到一个读请求的时候,会直接先在内存里面查询,如果查询到就返回。

2,如果没有查询到就会依次下沉,知道把所有的Level层查询一遍得到最终结果。

思考查询步骤,我们会发现如果SSTable的分层越多,那么最坏的情况下要把所有的分层扫描一遍,对于这种情况肯定是需要优化的,如何优化?在 Bigtable 论文中提出了几种方式:

Pebble详解:内存表

内存表(memtable)的写出到磁盘的流程的调用栈如下所示(调试时,可以将MemTableSize大小设置为 4MB,在函数func (m *memTable) unref()中 v == 0的分支设置断点,然后调试跟踪写出流程):

(d *DB) runCompaction  // 新建文件,然后将 memtable 内容写出到磁盘
(d *DB) compact1()
(d *DB) compact()
go d.compact()

pebble.(*DB) maybeScheduleFlush
pebble.(*memTable).unref
pebble.(*DB).makeRoomForWrite
pebble.(*DB).commitWrite
pebble.(*DB).commitWrite-fm
pebble.(*commitPipeline).prepare
pebble.(*commitPipeline).Commit
pebble.(*DB).Apply
pebble.(*Batch).Commit

跳跃表

内存表的默认实现是跳跃表。跳跃表是一个有序集合,当工作负载既有范围扫描,又有写入操作时,这是一个必要的结构。简而言之,跳跃表是一种类似链表的结构,同时允许快速查找。

  | 2 |  |  ------------------------------------->  |
L |   |  |  <-------------------------------------  |
E |   |  |                                          | 
V | 1 |  |  ---------> |  ---------> |  --------->  |
E |   |  |  <--------- |  <--------- |  <---------  |
L |   |  |             |             |              | 
S | 0 |  |  --> |  --> |  --> |  --> |  --> |  --> NIL
  |   |  30 <-- 40 <-- 50 <-- 60 <-- 70 <-- 90 <-- NIL

如上图所示,跳跃表基于层构建。最底层是一个普通的有序链表,高层是底层的快车道。

pebble当前使用的一个跳跃表实现所在路径:pebble/internal/arenaskl。是一个高速、无锁、基于区域的跳跃表,用Go实现。支持双向遍历:

  • 高性能:可以随着核数量增加而线性扩展,通过从固定大小的区域分配内存,避免锁来实现。
  • 可以在堆栈上分配并且可以值克隆的迭代器。
  • 简单易用且低开销的模型,用于检测和处理其他线程的竞争条件。
  • 支持反向遍历(例如:向前的链接)

其主要优势来自于专用性,无法提供通用跳跃表的实现:

  • 区域的大小设置了跳跃表节点,键和值的组合大小的上限。 此限制包括已删除节点,键和值的大小。
  • 不支持删除。相反,更高级别的代码会添加kv值和删除类型的新条目,并需要适当地处理这些条目的删除。
// 跳跃表的节点信息
type node struct {
    // 不可变字段,所以不需要对其加锁访问
    keyOffset uint32
    keySize   uint32
    valueSize int32

    // 每个节点都有 maxHeight 高度个链表,用于指向每层的下一个或者上一个节点,用于加速查找
    // 大部分节点不需要塔的全部高度,因为每个连续层的概率指数下降。
    // 因为这些元素永远不会被访问,不需要被分配。
    // 因此,当在区域中分配节点时,其内存占用被截断,不包括不需要的塔元素。
    // 所有元素的访问都应该使用 CAS 操作,而不需要锁定。
    tower [maxHeight]links
}

// 链接信息
type links struct {
    nextOffset uint32
    prevOffset uint32
}

// 跳跃表是一个快速,并发的实现支持向前,向后遍历。
// 键值一旦被加入到跳跃表中,就是不可变的,不支持删除。
type Skiplist struct {
    arena  *Arena
    cmp    db.Compare
    head   *node
    tail   *node
    height uint32 // 当前高度 1 <= height <= maxHeight. CAS.
}

值得注意的是,节点分配内存,前后指针等,都是在固定区域的内存中分配,指针都是通过偏移来实现。

插入

  1. 随机选择一个新插入节点的高度:h层的概率:rand\_uint64() < max\_uint32 * 1.0/e^{h-1},层数越高,概率约小,指数下降。
  2. 找出每层需要插入的位置,第0层到第h层的位置都找到需要找到。
  3. 然后生成新的节点,根据已经找到的插入位置,修改新节点中每层的前后指针,指向正确的位置。
  4. 然后通过无锁方法,将每层的链表中的前后指针指向新节点。处理完成。

无锁

从第0层到第h层,每一层通过双向链表的无锁CAS实现:

+----------------+     +------------+     +----------------+
|      prev      |     |     nd     |     |      next      |
| prevNextOffset |---->|            |     |                |
|                |<----| prevOffset |     |                |
|                |     | nextOffset |---->|                |
|                |     |            |<----| nextPrevOffset |
+----------------+     +------------+     +----------------+
1. 初始化 prevOffset 和 nextOffset 指向 prev 和 next.
2. 通过 CAS 操作将 prevNextOffset 从 next 重新指向 nd.
3. 通过 CAS 操作将 nextPrevOffset 从 prev 重新指向 nd.

检查next是否有了一个更新后的连接指向prev。如果没有,意味着下面的两种情况:

  1. 加入next的线程还米有计划添加prev链接(但是很短的时间之后会添加)
  2. 另一个线程已经在prev和next之间加了一个新连接

操作过程出现冲突的情况,需要重新定位插入位置,前后指针信息,然后再次插入,如果有一个新的相同key插入了,则报错已存在,然后退出。

详细参考:文件 skl.go 的函数 addInternal 。

查找

当前的arenaskl实现,通过迭代器的方式提供:

// memTable的get方法用于查找对应的key
func (m *memTable) get(key []byte) (value []byte, err error) {
    it := m.skl.NewIter(nil, nil)
    ikey, val := it.SeekGE(key)
    if ikey == nil {
        return nil, db.ErrNotFound
    }
    return val, nil
}

// 迭代器
func (s *Skiplist) NewIter(lower, upper []byte) *Iterator 

// 大于或者等于查找key的kv值
func (it *Iterator) SeekGE(key []byte) (*db.InternalKey, []byte) 

查找算法:

  1. 从跳跃表的最大高度开始,对每层进行查找
  2. 如果找到,判断是否层数为0
  3. 如果层数为0,则查找结束
  4. 如果层数不为0,则找到第0层对应节点的prev节点,结束

参考:

  1. http://ticki.github.io/blog/skip-lists-done-right/
  2. Redis的有序集合也通过skiplist实现
  3. RocksDB默认memtable使用skiplist实现
  4. https://homepage.cs.uiowa.edu/~ghosh/skip.pdf
  5. https://en.wikipedia.org/wiki/Skip_list

Pebble详解:SST

Pebble详解:预写日志

WAL 相关的内容在 pebble/internal/record 目录中。

WAL 日志写出流程:

  1. 在提交写入时(commitWrite),将 wal日志写到队列中
  2. 在一个 goroutine 中循环flushLoop接受数据,然后刷新到磁盘中

Pebble详解:压缩合并

SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分组就可以读取。

这个在前面的写入流程中已经介绍过,通过定期合并瘦身, 可以有效的清除无效数据,缩短读取路径,提高磁盘利用空间。但Compaction操作是非常消耗CPU和磁盘IO的,尤其是在业务高峰期,如果发生了Major Compaction,则会降低整个系统的吞吐量,这也是一些NoSQL数据库,比如Hbase里面常常会禁用Major Compaction,并在凌晨业务低峰期进行合并的原因。

Pebble详解:缓存

因为SSTable在写入磁盘后,除了Compaction之外,是不会变化的,所以我可以将Scan的Block进行缓存,从而提高检索的效率

Pebble详解:Manifest

Pebble详解:Bloom

索引。正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,我们可以对每一个 SSTable 添加 Bloom Filter,因为布隆过滤器在判断一个SSTable不存在某个key的时候,那么就一定不会存在,利用这个特性可以减少不必要的磁盘扫描。

Pebble详解:其它

并发控制/MVCC/数据恢复

snapshot/checkpoint/commit_pipeline/backup/Recovery/GC/ingest/

  • Delete
  • Batch: Get/Set/Delete/Commit/Apply
  • Flush: Flush the memtable to stable storage
  • Metrics
  • NewIter
  • NewSnapshot

为什么不支持事务?

没有冒犯。这是一个有意思的问题:您如何在非事务基础上构建事务?显然可以做到。文件系统不是事务性的,但是事务性数据库经常建立在文件系统之上。关键是寻找要建立的基础属性。对于文件系统,基本属性是fsync提供的持久性。对于Pebble/RocksDB,属性是Batch原语提供的原子性和持久性

请注意,尽管RocksDB具有“事务”,但CockroachDB并未使用它们。可以在非分布式RocksDB事务的基础上构建分布式事务,但这不是必需的。而是如上所述,CockroachDB依赖于批处理的原子性和持久性,并结合了许多自定义算法来实现复制和分布式事务

在Pebble/RocksDB层提供事务有不利之处吗?是。完整的事务意味着一致性和隔离性。提供一致性和隔离的机制可能很复杂,并且会导致大量开销。例如,“一致性和隔离”机制可能必须提供锁机制,锁机制意味着必须处理死锁等问题。这些单节点事务机制可能无法满足CockroachDB提供的分布式事务的需求。

https://github.com/cockroachdb/pebble/issues/581

提交管道

提交管道用于管理一系列原子提交变更(在单批中包含)到DB的阶段。主要包括

  1. 将批写入到WAL,并且可选是否将WAL刷新到磁盘。
  2. 将变更应用到memtable。

这两个步骤在期望高性能的场景下变得很复杂。在没有并发的情况下,性能被限制为一批数据写入(刷新)到WAL以及添加到memtable中的速度,这两个点都在提交管道的范围之外。提交管道主要关注并发场景的性能,同时还要维护下面的两个不变性:

  1. 所有batch需要以序列号的顺序写出到WAL。
  2. 所有batch需要以序列号的顺序对读操作可见。这种不变性源于使用单个序列号来指示哪些变更是可见的。

考虑这两种不变性,让我们重新考虑提交管道需要做的工作。将批量操作以串行化的方式写入WAL是必须的,因为只有一个WAL对象。注意,写WAL非常快,通常都是内存拷贝。将批量变更应用到内存表可以并发处理,因为底层跳跃表支持并发插入。发布可见序列是另一个串行化点,但是有一个变化:可见序列号不能被碰撞,直到早期批次的变更已经完成应用于内存表(可见序列号只是棘轮)。 最后,如果发出请求,则提交等待WAL同步。 请注意,在棘轮显示可见序列号后等待WAL同步,允许另一个goroutine在WAL同步之前读取已提交的数据。这与RocksDB的手动WAL刷新功能类似。 如有必要,应用程序代码需要对此进行保护。

提交管道操作的完整操作如下:

加锁:
    分配批操作序列号
    将批写到WAL
将批刷新到WAL同步列表中(可选)
将批操作应用到memtable中(并发地)
等待更早的批应用完成
棘轮读序列号
等待WAL刷新(可选)

一旦批处理被写入WAL,就会释放提交管道的互斥锁,允许另一个批处理写入WAL。 每个提交操作单独将其批处理应用于提供并发的内存表。 WAL同步与应用内存表同时发生(请参阅commitPipeline.syncLoop)。

“等待早期批次应用”的工作比预期要复杂得多。显而易见的方法是保留待处理批次的队列,并为每个批次等待上一批次完成提交。 这种方法最初尝试过,结果太慢了。 问题在于它会导致过多的Go例程活动,因为每个提交的Go例程都需要唤醒,以便下一个Go例程被解除阻塞。当前代码中采用的方法在概念上是相似的,但它避免唤醒Go例程来执行另一个Go例程可以执行的工作。 commitQueue(单生产者,多消费者队列)包含提交批次的有序列表。 在保存commitPipeline.mutex的同时完成对队列的添加,确保队列中批次的顺序与WAL中的排序相同。 当批处理完成对内存表的应用时,它会自动更新其Batch.applied字段。 通过commitPipeline.publish完成可见序列号的棘轮操作,该循环使“应用”批次出队列并使棘轮显示可见序列号。 如果我们在队列的头部遇到未应用的批处理,我们可以阻塞,因为我们知道提交该未应用的批处理最终将在队列中找到我们的(应用的)批。 请参阅commitPipeline.publish以获取其他评论。

测试

如何细粒度分析Pebble的瓶颈?考虑CPU(cache miss)、内存、磁盘IO、线程切换、锁竞争等瓶颈?

单元测试:

cd $GOPATH/src/github.com/cockroachdb/pebble/
go test

性能测试:

cd $GOPATH/src/github.com/cockroachdb/pebble/cmd/pebble/
./pebble bench scan ./scan_data/
./pebble bench ycsb ./ycsb_data/
ycsb read_95 update_5
1-threads 1702 91
8-threads 8017 418
16-threads 15088 781
32-threads 28922 1531
64-threads 56284 2984
128-threads 110219 5822
256-threads 199014 10467
512-threads 391956 20574
1024-threads 636707 33525
2048-threads 798184 41921
4096-threads 800901 41878
ycsb read_50 update_50
1-threads 542 548
8-threads 2424 2424
16-threads 4488 4525
32-threads 8466 8549
64-threads 16556 16625
128-threads 31148 31006
256-threads 54158 54216
512-threads 57913 57940
1024-threads 58179 57969

性能工具:

import "runtime/pprof"

func startCPUProfile() func() {
    f, err := os.Create("cpu.prof") 
    if err != nil {
        log.Fatal(err)
    }
    if err := pprof.StartCPUProfile(f); err != nil {
        log.Fatal(err)
    }
    return func() {
        pprof.StopCPUProfile()
        f.Close()
    }
}

// go tool pprof cpu.prof

pebble-scan

pebble bench scan --concurrency 4 --duration 30s data_dir

在这个测试中,将key编码为MVCC的格式如下:

bytes(key) | byte(\x00) | uint64(walltime) | uint32(logical) | 1+8+4

其中walltime和logical都是可选的:
1. bytes(key) | byte(\x00) | uint64(walltime) | 1+8
2. bytes(key) | byte(\x00)

参考

  1. https://github.com/cockroachdb/pebble
  2. https://github.com/facebook/rocksdb/wiki/rocksdb-basics
  3. https://github.com/google/leveldb/blob/master/doc/impl.md
  4. Bigtable: A Distributed Storage System for Structured Data
  5. The Log-Structured Merge-Tree (LSM-Tree)
  6. FPGA-Accelerated Compactions for LSM-based Key-Value Store