2025-01-25 02:00:00
读、写键值是 KV 数据库中最重要的两个操作,LevelDB 中提供了一个 Put 接口,用于写入键值对。使用方法很简单:
1 |
leveldb::Status status = leveldb::DB::Open(options, "./db", &db); |
LevelDB 最大的优点就是写入速度也非常快,可以支持很高的并发随机写。官方给过一个写入压力测试结果:
1 |
fillseq : 1.765 micros/op; 62.7 MB/s |
可以看到这里不强制要求刷磁盘的话,随机写入的速度达到 45.0 MB/s,每秒支持写入 40 万次。如果强制要求刷磁盘,写入速度会下降不少,也能够到 0.4 MB/s, 每秒支持写入 3700 次左右。
这里 Put 接口具体做了什么?数据的写入又是如何进行的?LevelDB 又有哪些优化?本文一起来看看。开始之前,先看一个大致的流程图:
LevelDB 支持一次写入一个键值对,也支持一次写入多个键值对。不论是单个写入,还是批量写内部都是通过 WriteBatch 来处理。
1 |
Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) { |
我们可以选择在调用 LevelDB 接口的应用层聚合写入操作,从而实现批量写入,提高写入吞吐。例如,在应用层可以设计一个缓冲机制,收集一定时间内的写入请求,然后将它们打包在一个 WriteBatch 中提交。这种方式可以减少磁盘的写入次数和上下文切换,从而提高性能。
当然也可以每次都写入单个键值,这时候 LevelDB 内部会通过 WriteBatch 来处理。如果在高并发情况下,可能会在内部合并多个写操作,然后将这批键值对写入 WAL 并更新到 memtable。
这里整体写入还是比较复杂的,本篇文章只先关注写入到 WAL 和 memtable 的过程。
完整的写入部分代码在 leveldb/db/db_impl.cc 的 DBImpl::Write 方法中,咱们一点点拆开看吧。
1 |
Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) { |
开始部分把 WriteBatch 和 sync 参数赋值给 Writer 结构体,然后通过一个 writers_ 队列来管理多个 Writer 结构体。这两个结构体和队列在整个写入过程中还是挺重要的,先来看看。
这里 writers_ 是一个 std::deque<Writer*>
类型的队列,用于管理多个 Writer 结构体。
1 |
std::deque<Writer*> writers_ GUARDED_BY(mutex_); |
这里队列用 GUARDED_BY(mutex_)
装饰,表示队列的访问需要通过 mutex_
互斥锁来保护。这个用到了 Clang 的静态线程安全分析功能,可以参考我之前的文章 LevelDB 源码阅读:利用 Clang 的静态线程安全分析
这里 Writer 结构体定义如下:
1 |
struct DBImpl::Writer { |
这里 Writer 结构体封装了不少参数,其中最重要是一个 WriteBatch 指针,记录了每个 WriteBatch 写请求的数据。然后用一个 status 用来记录每个 WriteBatch 写请求的错误状态。
此外,用一个 sync 来标记每个 WriteBatch 写请求是否需要立马刷到磁盘中。默认是 false,不强制刷磁盘,如果系统崩溃,可能会丢掉部分还没来得及写进磁盘的数据。如果打开了 sync 选项,每次写入都会立马刷到磁盘,整体写入耗时会上涨,但是可以保证只要写入成功,数据就不会丢失。关于刷磁盘文件的更多细节,可以参考我之前的文章LevelDB 源码阅读:Posix 文件操作接口实现细节。
还有一个 done 则用来标记每个 WriteBatch 的写请求是否完成。这里因为内部可能会合并写入多个 WriteBatch,当本次写入请求被合并到其他批次写入后,本次请求标记完成,就不需要再处理了。从而避免重复执行,提高并发的写入效率。
为了实现等待和通知,这里还有一个条件变量 cv,用于支持多个写请求的批量处理,并实现多个写请求的同步。写入的时候,多个线程可以同时提交写入请求,每个写请求都会先被放入写入队列。实际写入过程,则是串行化写入,同一时刻只有一批写入过程在执行。每次会从队列中取出队首的写请求,如果此时队列中还有其他等待的写任务,则会被合并为一个批次一起处理。在当前批次的写入请求处理过程中,后续来的请求进入队列后都需要等待。当前批次的请求处理完成后,会通知后面进入队列在等待中的写请求。
结合这里的介绍,应该能看懂前面 Write 方法开始部分代码的含义了。对于每个写入请求,都会先创建一个 Writer 结构体,然后将其放入 writers_ 队列中。接下来在 while 循环中,判断当前写入请求是否完成,如果完成就会直接返回当前写入的状态结果。如果当前写入请求没在队首,则需要等待在 cv 条件变量上。
如果当前写入请求在队首,那么就需要执行实际的写入操作了,这里具体写入流程是什么样呢?
接下来在正式写入前,要先确保有足够的空间来写入数据。这里会调用 MakeRoomForWrite 方法,确保在进行写入操作之前,有足够的资源和空间来处理新的写入请求。它负责管理内存表(memtable)的使用情况、控制 Level 0 文件的数量,并在需要时触发后台压缩。
1 |
// REQUIRES: this thread is currently at the front of the writer queue |
这里开始部分是一些验证部分,用 AssertHeld 验证当前线程必须持有 mutex_ 互斥锁,并且 writers_ 队列不能为空。接着会判断 bg_error_ 是否为空,如果不为空,则直接返回 bg_error_ 状态。在下文中会看到,如果写入 WAL 刷磁盘失败,就会设置 bg_error_ ,这样会让后续的写入都直接返回失败。
在 while 循环中,接着是一系列 if 分支检查,处理不同情况。
1 |
else if (allow_delay && versions_->NumLevelFiles(0) >= |
首先当 Level 0 文件数量接近 kL0_SlowdownWritesTrigger=8 阈值时,暂时释放锁,延迟 1 毫秒,以减缓写入速度。当然这里只允许延迟一次,避免长时间阻塞单个写入。这里之所以设置一个小的 Level 0 文件数量阈值,是为了防止 Level 0 文件太多后,到达系统瓶颈后,后续写入卡太长时间。在没到瓶颈前,就开始把延迟平摊到每个请求上,从而减缓压力。这里的注释也写的很清楚,上面也都贴出来了。
1 |
else if (!force && |
接着这里判断如果当前 memtable 的使用量没超过最大容量,就直接返回了。这里 write_buffer_size 是 memtable 的最大容量,默认是 4MB。这里可以调整配置,如果大一点的话,会在内存缓存更多数据,提高写入的性能,但是会占用更多内存,并且下次打开 db 的时候,恢复时间也会更长些。
接下来有两种情况,是当前没有地方可以写入,因此需要等待了。
1 |
else if (imm_ != nullptr) { |
第一种情况是不可变的 memtable 还在写入中,因此需要等待它写入完成。LevelDB 会维护两个 memtable,一个是当前可以写入的 memtable mem_,一个是不可变的 memtable imm_。每次写满一个 mem_ 后,就会把它转为 imm_ 然后刷数据到磁盘。如果 imm_ 还没完成刷磁盘,那么就必须等待刷完后才能把现有的 mem_ 转为新的 imm_。
第二种情况是 Level 0 文件数量太多,需要等待压缩完成。LevelDB 配置了 Level 0 文件数量的阈值 kL0_StopWritesTrigger,默认是 12,当 Level 0 文件数量超过这个阈值时,那么当前写入请求就需要等待。因为 Level 0 层的文件之间没有全局排序的保证,多个 Level 0 文件可能包含重叠的键范围。对于读来说,查询操作需要在所有 L0 文件中查找,文件数量过多会增加读取延迟。对于写来说,文件数量多,后台压缩的工作量也会增加,影响整体系统性能。所以这里强制控制 Level 0 的文件数量,达到阈值后就直接不给写入。
接下来的情况就是不可变的 imm_ 为空,同时 mem_ 也没足够空间,这时候要做的事情比较多:
这里可以看到 memtable 和 WAL 文件一一对应的,每个 memtable 对应一个 WAL 文件,WAL 文件记录写入 memtable 的所有操作,当 memtable 满时,同时切换 WAL 文件。同一时刻,前台 memtable 和新的 WAL 日志文件处理新的请求,同时后台的 imm_ 和旧的 WAL 文件处理压缩任务。等压缩完成,就可以删除旧的 WAL 文件了。
接着是合并写入的逻辑,核心代码如下:
1 |
uint64_t last_sequence = versions_->LastSequence(); |
首先是获取当前全局的 sequence 值,这里 sequence 用来记录写入键值对的版本号,全局单调递增。每个写入请求都会被分配一个唯一的 sequence 值,通过版本号机制来实现 MVCC 等特性。在写入当前批次键值对的时候,会先设置 sequence 值,写入成功后,还会更新 last_sequence 值。
为了提高写入并发性能,每次写入的时候,不止需要写队首的任务,还会尝试合并队列中后续的写入任务。这里合并的逻辑放在 BuildBatchGroup 中,主要是遍历整个写入队列,在控制整体批次的大小,以及保证刷磁盘的级别情况下,不断把队列后面的写入任务合并到队首的写入任务中。整体构建好的写入批次,会放到一个临时的对象 tmp_batch_ 中,在完整的写入操作完成后,会清空 tmp_batch_ 对象。
我们提到的每个写入任务其实封装为了一个 WriteBatch 对象,该类的实现支持了不同写入任务合并,以及获取任务的大小等。相关细节实现可以参考我前面的文章 LevelDB 源码阅读:如何优雅地合并写入和删除操作。
上面代码其实忽略了核心的写入到 WAL 和 memtable 的逻辑,下面来看看这部分的实现。
LevelDB 中写入键值对,会先写 WAL 日志,然后写入到 memtable 中。WAL 日志是 LevelDB 中实现数据恢复的关键,memtable 则是 LevelDB 中实现内存缓存和快速查询的关键。写入关键代码如下:
1 |
// Add to log and apply to memtable. We can release the lock |
这里在写入到 WAL 和 memtable 的时候,会先释放 mutex_ 互斥锁,写入完成后,再重新加锁。注释也专门解释了下,因为当前队首 &w
正在负责写入 WAL 和 memtable,后续的写入调用,可以拿到 mutex_ 互斥锁,因此可以完成入队操作。但是因为不是队首,需要等在条件变量上,只有当前任务处理完成,才有机会执行。所以写入 WAL 和 memtable 的过程,虽然释放了锁,但整体还是串行化写入的。WAL 和 memtable 本身也不需要保证线程安全。
不过因为写 WAL 和 memtable 相对耗时,释放锁之后,其他需要用到 mutex_ 的地方,都可以拿到锁继续执行了,整体提高了系统的并发。
WAL(Write-Ahead Logging)是一种日志记录机制,它允许在数据写入磁盘之前,先记录日志。WAL 日志是追加写入,磁盘的顺序 IO 性能优于随机 IO 性能,因此追加写入一般效率比较高。写入 WAL 成功后,再把数据放到 memtable 中,memtable 是内存结构,写入效率也很高,等在内存积累到一定量级,再写入磁盘。如果系统崩溃重启,内存中 memtable 的数据可能会丢失,但是通过 WAL 日志,可以重放写入操作,从而恢复数据状态,确保数据的完整性。
这里具体写入,只是简单的调用 log::Writer 对象 log_ 的 AddRecord 方法来写入 WriteBatch 数据。log::Writer 会把这里的数据进行组织,然后在适当的时机写入磁盘,详细实现可以参考我前面的文章LevelDB 源码阅读:读写 WAL 日志保证持久性。
当然,如果写入的时候带了 sync=true,那么这里写入 WAL 成功后,会调用 logfile_->Sync() 方法,强制刷磁盘。这里稍微补充说明下,这里往文件里写内容是会通过系统调用 write
来完成,这个系统调用返回成功,并不保证数据一定被写入磁盘。文件系统一般会把数据先放到缓冲区,然后根据情况,选择合适的时机刷到磁盘中。要保证一定刷到磁盘中去,则需要另外的系统调用,不同平台有不同的接口,具体可以参考我之前的文章LevelDB 源码阅读:Posix 文件操作接口实现细节。
如果强制刷磁盘过程发生错误,那么这里会调用 RecordBackgroundError 方法,记录错误状态到 bg_error_ 中,这样后续所有的写入操作都会返回失败。
在写入 WAL 成功后,就可以写入 memtable 了。这里调用 WriteBatchInternal::InsertInto 方法,把 WriteBatch 数据插入到 memtable 中。关于 memtable 的实现,我后面文章会详细介绍。
写入批次完成后,就需要更新批次写任务的状态,从 writers_ 队列的前端取出最先入队的 Writer 对象,然后开始遍历,直到批次中的最后一个写入任务。这里更新所有已经完成任务的状态,然后唤醒所有等待的写入任务。核心实现如下:
1 |
while (true) { |
最后如果队列中还有写入任务,则需要唤醒队首的写入任务,继续处理。至此整个写入处理完毕,可以返回给调用方写入的结果了。
整个写入过程到此分析完了,不过还有些工程实现细节,值得一起看看。
如果有一批写入请求,其中既有 sync 又有非 sync 的写入,那么 LevelDB 内部会怎么处理呢?
前面分析可以看到每次取出队首的写入任务后,会尝试合并队列中后续的写入任务。因为每个写入任务可以强制 sync 刷磁盘,也可以不刷,合并的时候,怎么处理这种混合不同 sync 配置的写入任务呢?
这里配置 sync=true 的时候写入会强制刷磁盘,对于合并后的批次写入,取得是队首的 sync。核心代码如下:
1 |
Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) { |
所以,如果队首是的任务是不需要刷磁盘,那么合并的时候,就不能合并 sync=true 的写入任务。核心实现代码如下:
1 |
for (; iter != writers_.end(); ++iter) { |
不过如果队首是 sync=true 的写入任务,那么合并的时候,就不需要考虑被合并的写入任务的 sync 设置。因为整个合并后的批次,都会被强制刷磁盘。这样就可以保证不会降低写入的持久化保证级别,但是可以适当提升写入的持久化保证级别。当然这里提升写入的持久化级别保证,其实也并不会导致整体耗时上涨,因为这里队首一定要刷磁盘,顺带着多一点不需要刷磁盘的写入任务,也不会导致耗时上涨。
上面实现可以看到,如果大批量并发写入的时候,写入请求会先被放入队列中,然后串行化写入。如果写入的 key 都比较小,那么从队首取出一个写入任务,然后和当前队列中的其他写入合并为一个批次。合并的时候,需要设置一个 max_size 来限制合并的 key 数量,那么这里 max_size 要设置多少合理呢?
这里 LevelDB 给了一个经验值,默认是 1 << 20 个字节。但是考虑一个场景,如果写入的 key 都比较小,合并的时候,可能会合并很多 key,从而导致写入耗时变长。由于是小 key 的写入,写入耗时长的话,体验上来并不好。
所以这里加了个小优化,如果当前队首写入任务的整体 size 小于 128 << 10 个字节,那么这里 max_size 就会小很多。当然,这个值应该也只是经验值,我也没找到官方具体的说明。相关代码在
BuildBatchGroup 中:
1 |
// Allow the group to grow up to a maximum size, but if the |
写入过程,会先写入 WAL 日志,写成功后,才写 memtable。但这两个写入并不是原子的,如果写 WAL 失败,不回写 memtable,并且会阻塞后续所有的写入,这样是合理的,也不会有问题。
但是如果写入 WAL 日志成功,但是写入 memtable 失败的话,返回给调用方的状态是写入失败,调用可能认为写失败。但是 WAL 成功写入,并且其他流程都是正常执行,也更新了全局的 sequence。万一这时候故障,从 WAL 恢复数据的时候,会把写 memtable 失败的也恢复,这样就导致调用方认为写失败的数据,其实成功写入了。
这里自己暂时还没彻底搞明白,可能是 LevelDB 的潜在 bug,也可能是自己对整体代码还没理解透。这里尝试用 GPT O1 和 Deepseek 的 R1 深度思考分析了下,都倾向这里是 bug。Deepseek 给的思考过程也比较有意思:
我需要确认在LevelDB的实际运行中,这种情况发生的概率有多大。MemTable的写入失败通常可能由什么原因引起?比如内存不足,或者其他不可恢复的错误?如果是暂时性的错误,LevelDB是否有重试机制?
另外,查看LevelDB的官方文档或相关讨论,是否有提到这种情况的处理方式。比如,是否在写入MemTable失败时,LevelDB会主动删除或无效化对应的WAL记录?
可能还需要考虑数据库恢复流程。当LevelDB重启时,会读取WAL并重新构建MemTable。如果某个WAL记录对应的写入在MemTable失败,但WAL存在,恢复时会再次尝试写入MemTable。如果此时条件允许(比如内存足够),写入可能成功,导致不一致。但如果原来的失败是持久性的(如数据结构错误),恢复时可能再次失败,导致数据库无法打开,从而避免不一致。
此外,用户的问题是否假设了某些特定场景?例如,MemTable写入失败但数据库没有崩溃,之后正常关闭,这时候WAL未被清除,恢复时重新应用。这种情况是否可能?
AI 现在的深度思考能力,逻辑推理的能力还是非常强的,考虑问题比较全面。这里也欢迎读者留言讨论这个问题哈。
文章有点长,这里简单总结下吧。LevelDB 的写入操作设计充分考虑了高并发和性能优化,通过一系列精巧的机制实现了高效的键值对写入。下面是一些值得借鉴的设计:
批量合并写入: LevelDB 通过 Writer 队列将多个写入请求合并处理,避免了频繁的磁盘 IO。每个写入请求会被放入队列,队列头部的写入请求负责合并后续请求,形成一个大的 WriteBatch。这种设计显著提高了吞吐量,尤其适合高并发的小键值对写入场景。
WAL 日志处理崩溃恢复: WAL(Write-Ahead Log):所有写入操作首先顺序写入 WAL 日志,确保数据持久性。写入 WAL 后才更新内存中的 MemTable,这种 “先日志后内存” 的设计是 LevelDB 崩溃恢复的基石。
内存双缓冲机制: 当 MemTable 写满后,会转换为 Immutable MemTable 并触发后台压缩,同时创建新的 MemTable 和 WAL 文件。这种双缓冲机制避免了写入阻塞,实现了平滑的内存-磁盘数据流转。
写入限流与自适应延迟: 通过 kL0_SlowdownWritesTrigger 和 kL0_StopWritesTrigger 阈值,在 Level 0 文件过多时主动引入写入延迟或暂停写入。这种 “软限流” 策略避免了系统过载后的雪崩效应。
动态批次合并: 根据当前队列头部请求的大小,动态调整合并批次的最大尺寸(如小请求合并 128KB,大请求合并 1MB),在吞吐量和延迟之间取得平衡。
条件变量唤醒机制: 通过 CondVar 实现高效的线程等待-通知,确保合并写入时不会长时间阻塞后续请求。
混合 Sync 处理: 支持同时处理需要强制刷盘(sync=true)和非强制刷盘的请求,优先保证队首请求的持久化级别,避免降低数据安全性。
错误隔离: WAL 写入失败会标记全局错误状态 bg_error_,直接拒绝掉所有后续写请求,防止数据不一致。
最后,欢迎大家留言讨论,一起学习 LevelDB 的实现细节。
2025-01-14 06:00:00
LevelDB 支持写入单个键值对和批量写入多个键值对,这两种操作的处理流程本质上是相同的,都会被封装进一个 WriteBatch 对象中,这样就可以提高写操作的效率。
在 LevelDB 中,WriteBatch 是通过一个简单的数据结构实现的,其中包含了一系列的写入操作。这些操作被序列化(转换为字节流)并存储在内部的一个字符串中。每个操作都包括操作类型(如插入或删除),键和值(对于插入操作)。
当 WriteBatch 被提交给数据库时,其内容被解析并应用到 WAL 日志和 memtable 中。不管 WriteBatch 中包含多少操作,它们都将作为一个整体进行处理和日志记录。
WriteBatch 的实现主要涉及到 4 个文件,接下来一起看看。
我们先来看 write_batch.h 文件,这里定义了 WriteBatch 类对外暴露的一些接口。 LevelDB 代码中的注释十分清晰,不过这里先省略注释:
1 |
class LEVELDB_EXPORT WriteBatch { |
其中 WriteBatch::Handler 是一个抽象基类,定义了处理键值对操作的接口,只包括 Put 和 Delete 方法。这样的设计允许 WriteBatch 类实现与具体存储操作解耦,使得 WriteBatch 不必直接知道如何将操作应用到底层存储(如 MemTable)。
通过继承 Handler 类,可以创建多种处理器,它们可以以不同的方式实现这些方法。比如:
另外还有一个 friend class WriteBatchInternal
作为 WriteBatch 的友元类,能够访问其私有和受保护成员。WriteBatchInternal 主要用来封装一些内部操作,这些方法不需要对外暴露,只在内部用到。通过将内部操作方法隐藏在 WriteBatchInternal 中,保持了对象的接口清晰,可以自由地修改内部实现而不影响到使用这些对象的代码。
在应用层,我们可以通过 WriteBatch 来批量写入多个键值对,然后通过 DB::Write
方法将 WriteBatch 写入到数据库中。
这里 WriteBatch 支持 Put 和 Delete 操作,可以合并多个 WriteBatch。如下使用示例:
1 |
WriteBatch batch; |
那么 WriteBatch 是怎么实现的呢?关键在 db/write_batch.cc,该类中有一个 private 成员 std::string rep_
来存储序列化后的键值操作。我们先来看看这里的存储数据协议:
1 |
+---------------+---------------+----------------------------------------+ |
该字符串前 12 个字节是头部元数据部分,包括 8 个字节的序列号和 4 个字节的 count 数。接下来是一个或多个操作记录,每个记录包含一个操作类型和键值对。操作类型是一个字节,可以是 Put 或者 Delete 操作。键和值都是可变长度的字符串,格式为 varstring。
rep_ 头部 8 个字节代表64位的数字 sequence(序列号),WriteBatchInternal 友元类提供了两个方法来获取和设置 sequence number,内部是用 EncodeFixed64 和 DecodeFixed64 方法来编解码 64 位的序列号。
1 |
SequenceNumber WriteBatchInternal::Sequence(const WriteBatch* b) { |
序列号是 LevelDB 中的全局递增标识符,用于实现版本控制和操作排序。每个 WriteBatch 在执行时会获得一段连续的序列号,批次内的每个操作(Put/Delete)都会分配到其中的一个序列号。序列号在 LevelDB 中有三个核心作用:
这种设计让 LevelDB 既保证了数据一致性,又实现了高效的并发控制。
设置序列号的逻辑在 DBImpl::Write 方法中,首先获取当前最大序列号,然后为 WriteBatch 分配一个新的序列号。
1 |
Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) { |
如果 WriteBatch 包含多个操作,那么这些操作会连续地分配序列号。在写入 WAL 日志时,会将 WriteBatch 的序列号写入到日志中,这样在恢复时可以根据序列号来恢复操作的顺序。写入 memtable 之后,会更新当前最大序列号,以便下次分配。
头部还有 4 个字节的 count,用于记录 WriteBatch 中包含的操作数。这里每次 put 或者 delete 操作都会增加 count 的值。如下示例:
1 |
WriteBatch batch; |
在合并两个 WriteBatch 的时候,也会累计两部分的 count 的值,如下 WriteBatchInternal::Append 方法:
1 |
void WriteBatchInternal::Append(WriteBatch* dst, const WriteBatch* src) { |
使用 count 的地方主要有两个,一个是在迭代这里每个记录的时候,会用 count 来做完整性检查,确保没有遗漏操作。
1 |
Status WriteBatch::Iterate(Handler* handler) const { |
另一个是在 db 写入的时候,根据 count 可以预先知道需要分配多少序列号,保证序列号连续性。如下 DBImpl::Write:
1 |
WriteBatchInternal::SetSequence(write_batch, last_sequence + 1); |
在头部的 sequence 和 count 之后,rep_ 紧跟着的是一系列的记录,每个记录包含一个操作类型和键值。这里记录可以通过 Put 和 Delete 方法来添加,其中 Put 方法的实现如下:
1 |
void WriteBatch::Put(const Slice& key, const Slice& value) { |
这里更新了 count,然后添加了 kTypeValue 操作类型,接着是添加 key 和 value。Delete 操作类似,count 计数也是要加 1,然后操作类型是 kTypeDeletion,最后只用添加 key 即可。
1 |
void WriteBatch::Delete(const Slice& key) { |
上面是往 rep_ 中添加记录,那么如何从 rep_ 中解析出这些记录呢?这里 WriteBatch 类中提供了一个 Iterate 方法,该方法遍历 rep_ 中的每条记录,然后通过传入的 Handler 接口来灵活处理这些记录。
此外该方法的实现中还有数据格式验证,会检查头部大小、操作类型、操作数量是否匹配。可以返回 Corruption 错误,表示数据格式不正确等。Iterate 核心代码如下:
1 |
Status WriteBatch::Iterate(Handler* handler) const { |
前面提过 Handler 是 WriteBatch 的抽象基类,可以传入不同的实现。在 LevelDB 写数据的时候,这里传入的是 MemTableInserter 类,该类将操作数据存储到 MemTable 中。具体可以调用这里的实现:
1 |
Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) { |
整体上看 WriteBatch 负责存储键值操作的数据,进行编码解码等,而 Handler 负责具体处理里面的每条数据。这样 WriteBatch 的操作就可以被灵活地应用到不同场景中,方便扩展。
最后再来看看 write_batch_test.cc,这里提供了一些测试用例,用于测试 WriteBatch 的功能。
首先定义了一个 PrintContents 函数,用来输出 WriteBatch 中的所有操作记录。这里用 MemTableInserter 将 WriteBatch 中的操作记录存储到 MemTable 中,然后通过 MemTable 的迭代器遍历所有记录,并保存到字符串中。
这里测试用例覆盖了下面这些情况:
这里通过测试用例,基本就能知道怎么使用 WriteBatch 了。比较有意思的是,前面在看 Append 代码的时候,没太留意到合并后这里序列号是用谁的。这里结合测试用例,才发现取的目标 WriteBatch 的序列号。
1 |
TEST(WriteBatchTest, Append) { |
通过深入分析 LevelDB 的 WriteBatch 实现,我们可以清晰地看到其设计精妙之处。WriteBatch 通过将多个写入和删除操作封装在一起,不仅提高了写操作的效率,还简化了并发控制和故障恢复的实现。有几个亮点值得借鉴:
当然本篇只是分析 WriteBatch 的实现,并没有串起 LevelDB 的整个写入流程,后续文章我们会继续分析,写入一个 key 的完整流程。
2025-01-11 05:00:00
只要你写过比较复杂的 C++ 项目,应该都或多或少遇见过进程 Coredump 的问题。Coredump 是程序运行过程中发生严重错误时,操作系统将程序当前的内存状态记录下来的一种机制。
C++ 中导致进程 Coredump 的原因有很多,比如:
遇到 Coredump 问题时,一般需要打开 core 文件,然后根据 core 文件来进行问题分析和调试。分析 core 文件有时候还是比较难的,需要对 C++ 的内存模型、异常处理机制、系统调用等有深入的理解。
本文不会过多介绍分析 core 文件的方法,而是通过几个真实项目中的案例,来让大家在写代码时候,能够有意识地避免这些错误。
业务代码中最常见的导致进程 crash 的原因,就是不小心抛出异常却没有捕获。比如一个字符串转整数的函数中,用了 std::stoi 来转换。但是这里万一字符串没法转成数字,就会抛出 std::invalid_argument
异常。如果框架层或者调用方没有捕获异常,就会导致进程 crash 掉。
就拿标准库来说,可能抛出异常的函数还是挺多的,常见的有:
std::out_of_range
异常。std::bad_alloc
异常。std::out_of_range
异常。在使用这些可能抛出异常的标准库函数的时候,一定要妥善处理好异常。另外如果是自定义类,不建议抛出异常,可以用错误码来处理。当然对使用异常还是错误码这里一直有争论,可以按照自己比较熟悉或者项目中的惯例来处理就好。如果是明确不抛出异常的函数,可以加上 noexcept 来告诉编译器和使用方。
这里再补充说下,有时候有些函数调用不会抛异常,但是会导致未定义行为,也是可能导致进程 crash 的。比如 atoi 函数,如果字符串没法转成数字,这里会导致未定义行为。未定义行为在某些场景下,会导致进程 crash。
平常在使用一些基础函数的时候,如果对该函数不清楚的话,可以查看 cplusplus 的文档,来确定该函数是否会在某些场景抛异常,是否会导致未定义行为。比如对于 vector :
std::vector::front()
Calling this function on an empty container causes undefined behavior.std::vector::push_back()
If a reallocation happens, the storage is allocated using the container’s allocator, which may throw exceptions on failure (for the default allocator, bad_alloc is thrown if the allocation request does not succeed).
除了抛出异常,还有一类问题也比较常见,那就是数组下标访问越界。我们都知道在 C++ 中访问数组的时候如果下标越界,会导致访问非法内存地址,可能导致进程 crash。你可能会觉得,怎么会数组访问越界?我遍历的时候限制长度就行了呀。
别急,看下面来自业务中的真实例子。当然为了演示,这里简化了很多实际业务逻辑,只保留核心部分。
1 |
|
这里刚开始实现的时候,第一次遍历 src 用来初始化 dest。然后中间有一些其他代码,接着后面又遍历 src,根据 src 的内容对初始化后的 dest 再进行某些处理。
刚开始实现的时候,这样没什么问题,然后某天可能加了个需求,需要过滤掉 src 中某些数据,于是就加了 if 判断来跳过某些内容。改动的人,可能没注意到后面对 src 和 dest 的遍历,没意识到过滤会导致 dest 的长度已经变了。
这个场景有时候比较难触发 coredump,可能只有极少场景才会有过滤导致长度不一样。并且这里就算第二轮访问了越界下标,用 [] 访问的话,也可能不会 core。上面示例代码为了必现 core,故意改成用 at 访问,这样下标越界就会抛异常。
除了下标访问越界,还有一类问题比较常见,那就是访问失效的迭代器。迭代器是一种设计模式,它提供了一种方法来访问容器对象中的元素,而无需暴露该对象的内部表示。在 C++ 中,迭代器是一个非常重要的概念,它是容器和算法之间的桥梁。
C++ 标准库中,很多容器都提供了迭代器,比如 vector、list、map 等。访问这些容器的迭代器时候,如果迭代器已经失效,就会导致未定义行为,可能导致进程 coredump。
导致迭代器失效的原因有很多,比如 vector 扩容,导致之前的迭代器失效。最常见的一个例子就是删除 vector 中偶数位置的元素,很多新手可能像下面这样写:
1 |
for (auto it = numbers.begin(); it != numbers.end(); ++it) { |
这里当调用 erase
删除元素时,会导致删除位置和它之后的所有迭代器都失效。所以循环中接着访问 it
就会导致未定义行为。正确做法是使用 erase 的返回值,来更新迭代器,或者使用 remove_if 和 erase 来删除元素。
当然这个示例比较简单,在实际业务中,我们遇见过一些比较隐蔽的迭代器失效问题。背景是这样,我们有个批处理任务,会用协程池来处理一批 IO 密集的任务,并且把结果写回到一个 vector 中。为了示例,这里代码简化如下:
1 |
// 模拟异步任务处理函数 |
这里我们保存了 results.back()
的引用,并在异步任务中使用它。在异步任务执行期间,results
vector 继续添加新元素。当 vector 需要扩容时,原有的内存会被释放,新的内存会被分配。此时异步任务中持有的引用就变成了悬空引用,访问它会导致未定义行为。
正确的做法应该是使用 reserve
预分配空间,避免扩容。或者保存索引,使用索引值而不是引用。
还有一类 crash 问题,是因为并发导致的数据竞争。经常有这么一个场景,就是服务中有一个后台线程,会从某个配置中心拉取配置更新到本地。然后有多个业务线程,会并发读取这里的配置。
因为是经典的读多写少场景,所以一般会用读写锁来实现。多个读线程可以同时持有读锁,写线程必须独占,写的过程需要保证无其他读或写操作。写操作期间,新的读操作需要等待。一个可能的执行序列如下:
1 |
Time ──────────────────────────────────────────────────────▶ |
这里 W 代表一次写入,R 代表一次读取。可以看到,写操作期间,新的读操作需要等待。我们在实际场景中,有遇见过一个 crash 就是错误的使用读写锁。整体比较复杂,下面简化下逻辑,给出核心代码。
1 |
class DataManager { |
完整的演示代码在 core_share.cpp 中,感兴趣的可以看下。这里 loadData 中,先准备好配置数据,然后用写锁来更新配置。在 readData 中,则用读锁来读取配置。
看起来没啥问题呀?因为当时是很偶发的 crash,这里业务代码也很久没动过了,只能开了 core 文件来分析。结果 core 的堆栈很奇怪,在 loadData 方法里,localdata 的析构过程发生的 crash。这里 localdata 是局部变量,最后析构前交换了 m_data 和 localdata 的值。那就是 m_data 的数据内存布局有问题了,m_data 只有这里会写,其他地方全部是“读“。
又仔细翻了下业务代码,发现 m_data 读的时候,用了 [] 来拿 unordered_map 的值。对于 unordered_map 来说,如果 key 不存在,[] 会导致插入一个默认值。啊!!这里本来意图是用读锁保护只读操作,结果不小心还执行了写操作。我们知道,并发写 unordered_map 会有数据竞争,怪不得导致 crash。
当然这里 core 的堆栈其实不一定是析构时候,比如示例的代码,堆栈就是在读线程 readData 的时候,如下图:
上面的示例其实平时多注意的话,还是能避免的。但下面这个,一般人还是很少知道,很容易踩坑。
我们有个地方需要判断字符串中是否有一对括号,于是用了 C++ 的正则表达式。相关代码简化如下:
1 |
|
上面代码中,我构造了一个很长的字符串,然后使用正则表达式来匹配。用 g++ 编译后,运行程序,程序就会 coredump 掉。如果用 gdb 看堆栈的话,如下:
这是因为正则引擎进行了大量的回溯,每次回溯都会在调用栈上创建新的栈帧。导致这里栈的深度特别长,最终超出栈大小限制,进程 coredump 了。
这个就是所谓的灾难性回溯(Catastrophic Backtracking),实际开发中,对于复杂的文本处理,最好对输入长度进行限制。如果能用循环或者其他非递归的方案解决,就尽量不用正则表达式。如果一定要用正则表达式,可以限制重复次数(使用 {n,m} 而不是 + 或 *),另外也要注意避免嵌套的重复(如 (.+)+)。
上面的正则表达式,可以改成:
1 |
std::regex re(R"(\([^\)]{1,100}\))"); |
当然除了这里递归回溯导致的栈溢出,还有其他一些场景,比如无限递归、大数组分配在栈上,都可能导致栈溢出。好在栈溢出的话,有 core 文件还是能比较好定位到原因的。
遇到 crash 问题,一般需要打开 core 文件。真实业务环境中,业务进程如果占内存比较大,crash 后保存 core 文件可能会持续比较久的时间。而真实业务中,一般会有守护进程定时拨测业务进程,如果发现业务进程没回应,有的会用 kill -9
来杀死进程并重启。这时候,业务进程的 core 文件可能只写了一半,我们拿到的是不完整的 core 文件。这时候就要修改守护进程,等 core 文件写完再重启进程。
拿到 core 文件后,用 gdb 来分析,如果堆栈比较明确,一般就能很快定位到问题。但很多时候,可能看到的堆栈不完整,是一堆 ??。比如上面访问失效的迭代器,用 gdb 来运行,crash 之后看到堆栈如下:
这里堆栈没有什么有用的信息,比较难分析。对于示例这种能稳定复现的问题,使用 Valgrind 来辅助分析,会更容易定位。上面代码分析结果如下:
从这里分析结果可以看到,主要有两个问题,无效读取(Invalid read)和无效写入(Invalid write)。发生问题的代码行数这里也有,所以可以很快定位到问题。
本文介绍了 5 个自己遇到过的导致进程 Coredump 的经典案例:
at()
方法来进行带边界检查的访问。当然还有些不常见的 core,比如我之前遇到的:Bazel 依赖缺失导致的 C++ 进程 coredump 问题分析。大家有遇见过什么印象深刻的 crash 案例,欢迎留言分享。
2025-01-03 06:00:00
LevelDB 中有一些宏比较有意思,平时自己写代码的时候,还基本没用过。这些宏在 thread_annotations.h 中定义,可以在编译时使用 Clang 编译器的线程安全分析工具,来检测潜在的线程安全问题。
比如下面这些宏,到底有什么作用呢?本文就一起来看看吧。
1 |
GUARDED_BY(x) // 表示变量必须在持有锁x时才能访问 |
在很多类的成员变量定义中,都有 GUARDED_BY(mutex_)
这样的注解,有什么作用呢?比如 LRU Cache 的定义:
1 |
class LRUCache { |
其实这就是 Clang 的线程安全注解,编译的时候,Clang 会检查所有对 usage_
和 table_
的访问是否都在持有 mutex_
锁的情况下进行。另外,在函数或代码块结束时,编译器还会检查所有应该释放的锁是否都已经释放,可以防止遗漏锁释放导致的资源泄露或死锁。
反观我们平时在写业务代码的时候,几乎没用过这些线程安全注解。顶多注释下这里不是线程安全的,要加锁访问,全靠开发的自觉。可想而知,业务中肯定会遇见各种奇怪的多线程数据竞争问题。
LevelDB 实现的时候,加了很多类似的线程安全注解,不仅可以明确告诉其他开发者这个变量需要锁保护,还可以在编译期就发现潜在的线程安全问题,从而减少多线程环境下可能出现的竞态条件、死锁等问题。
下面通过一个完整的例子来看看 Clang 的线程安全注解作用。这里 SharedData 类中,counter_
变量需要锁保护,mutex_
是我们封装的一个锁实现。
1 |
// guard.cpp |
当然这里的测试代码为了直接能运行,就没有依赖 LevelDB 中的宏定义 GUARDED_BY。下面的 __attribute__((guarded_by(mutex_)))
和宏展开的结果是一样的。
用 Clang 编译上面的代码,就能看到告警信息:
1 |
clang++ -pthread -Wthread-safety -std=c++17 guard.cpp -o guard |
可以看到,编译器在编译的时候,就发现了 counter_
变量在未持有 mutex_
锁的情况下被访问,从而告警。
这里 GUARDED_BY 通常用在对象的非指针成员上,用来保护成员变量自身。而 PT_GUARDED_BY 则是用在指针和智能指针成员上,用来保护指针指向的数据。注意这里 PT_GUARDED_BY 只保护指针指向的数据,指针本身并没有约束的。可以看下面的例子:
1 |
Mutex mu; |
上面的例子中,我们没有直接用标准库的 mutex 互斥锁,而是简单封装了一个 Mutex
类。在类定义那里,用了 __attribute__((capability("mutex")))
注解。
这是因为 Clang 的线程安全分析需要知道哪些类型是锁,需要去追踪锁的获取和释放状态。而标准库的类型没有这些注解,不能直接用于 Clang 的线程安全分析。这里用到了 clang 的 capability("mutex")
属性,用来指定该类具有锁的特性。
LevelDB 中定义锁的代码也用到了注解,不过稍微不同,用的是 LOCKABLE
,代码如下:
1 |
class LOCKABLE Mutex { |
这是因为早期版本的 Clang 使用 lockable 属性,后来引入了更通用的 capability 属性。为了向后兼容,lockable 被保留为 capability(“mutex”) 的别名。所以,这两者是等效的。
上面例子有点简单,其实从本质上来看,这里 clang 静态线程安全分析想做的事情,就是在编译器提供一种保护资源的能力。这里资源可以是数据成员,比如前面的 counter_
,也可以是提供对某些底层资源访问的函数/方法。clang 可以在编译期确保,除非某个线程有访问资源的能力,否则它无法访问资源。
这里线程安全分析使用属性来声明这里的资源约束,属性可以附加到类、方法和数据成员前面。Clang 官方也提供了一系列属性定义宏,可以直接拿来用。LevelDB 中定义了自己的宏,也可以参考。
前面给的例子中,注解主要用在数据成员上,其实也可以用在函数上。比如 LevelDB 中定义的锁对象 Mutex,在成员函数上用到了这些注解:
1 |
class LOCKABLE Mutex { |
这些注解主要用于标记锁对象的成员函数,告诉编译器这些函数会如何改变锁的状态:
当然这些是 clang 早期的线程安全注解,主要为了锁来命名。上面这几个现在可以用 ACQUIRE(…), ACQUIRE_SHARED(…), RELEASE(…), RELEASE_SHARED(…) 来替代。
此外,还有其他一些注解,可以参考 Clang 官方的文档 Thread Safety Analysis 了解更多细节。
2024-12-26 05:00:00
哈希表(HashTable) 是一个经典的数据结构,只要写点过代码,应该都有用过哈希表。每种语言都有自己的哈希表实现,基本都是开箱即用。以至于虽然用过哈希表的人很多,但自己动手写过哈希表的人估计没多少吧。
要设计一个高性能的哈希表,其实还是有不少细节需要考虑的。比如如何处理哈希冲突,如何处理哈希表扩容等。一些成熟的哈希表实现,比如 C++ 标准库中的哈希表,代码量比较大,也比较难理解。
好在 LevelDB 在实现 LRU Cache 的时候,顺便实现了一个简单高效的哈希表,整体代码写的很精简,麻雀虽小五脏俱全,非常值得学习。本文以 LevelDB 的哈希表实现为例,分析下如何设计一个高性能的哈希表。
C++ 标准库已经有了哈希表实现,为什么 LevelDB 还要实现一个自己的哈希表呢?官方是这样说的:
We provide our own simple hash table since it removes a whole bunch
of porting hacks and is also faster than some of the built-in hash
table implementations in some of the compiler/runtime combinations
we have tested. E.g., readrandom speeds up by ~5% over the g++
4.4.3’s builtin hashtable.
这里简单总结就是,其他实现有些冗杂,这里自己实现不依赖第三方库,代码精简的同时,也能保证实现的性能。
这里 HashTable 实现的思想其实和 C++ 标准库中的哈希表实现差不多,用数组来存储哈希桶。插入、查找、删除操作的平均时间复杂度都是 O(1),首先根据 key 的 hash 值定位到具体某个哈希桶,然后在冲突链表上执行相应的操作。同时,如果插入的时候发现哈希表的负载因子过高,则进行扩容。
这里补充一点,因为 LevelDB 的哈希表是用来实现 LRU Cache 的,所以这里哈希表的元素类型是 LRUHandle
,除了有 key 和 value 两个字段外,还有一个 next_hash 指针,用链地址法来处理哈希冲突。另外,这里也存储了 hash 值,一般是调用方生成后保存下来。这样在后续的查找、插入和删除操作中,可以直接使用这个 hash 值来定位到具体的哈希桶。LRUHandle 的其他字段主要是在 LRU Cache 中使用,这里就不展开了。
接着我们先看看查找指定 key 的操作,LevelDB 封装了一个基础的 FindPointer()
方法,返回了一个指向 key 的二级指针。具体实现如下:
1 |
// Return a pointer to slot that points to a cache entry that |
这里根据 key 的 hash 值定位到具体的哈希桶,如果桶为空,则直接返回指向桶头指针 nullptr 的地址。如果桶不为空,则用经典的链地址法处理哈希冲突。遍历哈希桶上的冲突链表,如果找到对应的 key,则返回指向该节点的二级指针。如果遍历完链表都没有找到,则返回链表的尾指针地址。
这里比较巧妙的是返回了一个二级指针,这样就能在查找、插入和删除操作中都复用该方法。在查找时,直接解引用返回的指针就能获得目标节点。在插入时,通过这个指针可以既能检查是否存在相同key的节点,又能直接在正确的位置插入新节点。在删除时,可以直接通过修改这个指针指向的值来完成节点的移除,而不需要额外记录前驱节点。
查找节点就是直接调前面的 FindPointer
方法,然后解引用即可,这里不再赘述。我们来看看删除 key 的 Remove 方法,代码如下:
1 |
LRUHandle* Remove(const Slice& key, uint32_t hash) { |
很简单吧!为了在一个链表中删除指定节点,这里先用 FindPointer 找到指向链表节点指针的地址,然后将要删除节点的下一个节点地址(result->next_hash)赋值给原指针位置,就完成了删除操作。本方法返回了被删除的节点指针,方便调用者进行后续处理(如内存释放等)。这里的实现方式,不需要额外记录前驱节点,操作简单高效,也能够正确处理链表头节点的删除情况。
这里的删除方法可以优雅下面的所有情况:
情况 | 描述 | 初始状态 | 删除后状态 |
---|---|---|---|
1 | 删除链表第一个节点 A | list_[i] –> [A] –> [B] –> [C] –> nullptr | list_[i] –> [B] –> [C] –> nullptr |
2 | 删除链表中间节点 B | list_[i] –> [A] –> [B] –> [C] –> nullptr | list_[i] –> [A] –> [C] –> nullptr |
3 | 删除链表最后节点 C | list_[i] –> [A] –> [B] –> [C] –> nullptr | list_[i] –> [A] –> [B] –> nullptr |
4 | 删除链表唯一节点 A | list_[i] –> [A] –> nullptr | list_[i] –> nullptr |
5 | 要删除的key不存在 | list_[i] –> [A] –> [B] –> nullptr | list_[i] –> [A] –> [B] –> nullptr |
6 | hash桶为空 | list_[i] –> nullptr | list_[i] –> nullptr |
插入节点的方法 Insert 和删除节点有点类似,也是先找到插入位置,然后进行插入操作。
1 |
LRUHandle* Insert(LRUHandle* h) { |
这里第 4 行,用二级指针一次性处理了下面所有情况,文章后面会再详细介绍这里的二级指针。
情况 | 描述 | 初始状态 | 插入后状态 | 返回值 |
---|---|---|---|---|
1 | 插入到空桶 | list_[i] –> nullptr | list_[i] –> [H] –> nullptr | nullptr |
2 | 插入时key已存在(第一个节点) | list_[i] –> [A] –> [B] –> nullptr | list_[i] –> [H] –> [B] –> nullptr | A |
3 | 插入时key已存在(中间节点) | list_[i] –> [A] –> [B] –> [C] –> nullptr | list_[i] –> [A] –> [H] –> [C] –> nullptr | B |
4 | 插入时key已存在(最后节点) | list_[i] –> [A] –> [B] –> nullptr | list_[i] –> [A] –> [H] –> nullptr | B |
5 | 插入新key(非空桶) | list_[i] –> [A] –> [B] –> nullptr | list_[i] –> [A] –> [B] –> [H] –> nullptr | nullptr |
这里插入后,还会根据 old 判断是否是新增节点,如果是新增节点,则更新哈希表的元素数量,并且要判断是否需要动态扩容,接下来看看这里扩容逻辑。
对于某个固定桶数量的哈希表,随着插入元素的变多,哈希冲突的概率会变大。极端情况下,可能每个 key 都有很长的冲突链表,导致 hashtable 的查找和删除性能退化。为了衡量这里哈希冲突的严重程度,我们可以定义负载因子 = 哈希表的元素数量 / 哈希桶数量,一旦这个值超过某个阈值,则需要进行扩容。
前面 Insert 方法在插入元素的时候,会统计当前 hashtable 的元素数量。一旦负载因子超过阈值 1,则调用 Resize()
进行扩容。
1 |
if (old == nullptr) { |
这里扩容第一个要解决的问题就是决定新的哈希桶数量。LevelDB 的实现如下:
1 |
void Resize() { |
其实在标准库的 vector 扩容时候,也是选择按照 2 的整数倍进行扩容。这里扩容系数如果选择的太大,可能浪费比较多空间,选择倍数太小,可能导致频繁扩容。工程实践中,一般会选择 2 作为扩容倍数。
决定好新的桶大小后,就先创建这个更大容量的哈希桶,然后遍历所有旧的哈希桶,对于每个桶,还要遍历冲突链表上的每个 key,然后将每个 key 插入到新的链表上。核心的实现如下:
1 |
void Resize() { |
这里在 Resize 的时候,每次成功一个 key 到新的哈希表中,都会更新哈希表的元素数量。之后会用 assert 断言来检查扩容后,哈希表的元素数量是否正确。所有 key 都插入到新哈希表后,就可以回收旧哈希表的内存,然后替换 list_ 为新哈希表,并更新哈希表容量。
前面省略了关键的插入部分逻辑,这里在 while 循环中会遍历旧哈希表冲突链表中的每个 key,然后用头插法插入到新哈希表中,下面看看头插法的详细实现。
这里前面 Resize 省略的头插法的核心代码如下:
1 |
void Resize() { |
头插法的核心思想是:将新节点插入到链表的头部。假设原始链表中如下:
1 |
list_[i] --> [A] --> [B] --> [C] --> nullptr |
重哈希过程会依次处理 A、B、C 三个节点,将其插入到新哈希表中。如果在新的哈希表中,A、B 个节点依旧在同一个桶中,则重哈希后的链表状态如下:
1 |
new_list[hash_a] --> [B] --> [A] --> nullptr |
这里 A 和 B 在新的链表中依旧在同一个桶中,但是 A 和 B 的顺序反过来了。相比传统的遍历到链表尾部进行插入,头插法的实现比较简单,只用在头部插入,不需要遍历到链表尾部,所以操作时间复杂度是O(1)。并且使用头插法也不需要维护尾指针,空间效率更高。此外,头插法还有缓存局部性,最近插入的节点在链表头部,对于某些访问模式下查找效率更高。
前面链表的操作代码十分简介,没有各种复杂的条件判断,正是因为用好了二级指针,那么要怎么理解 C++ 中的二级指针呢?C++ 中的对象有值和对应内存地址,指针存储的是对象的内存地址,而二级指针存储的是指针的地址。
举个例子来看更清晰些,比如某个 bucket 上有 bucket->A->B->nullptr
这样一个冲突链表,对应可以用下面 C++ 代码表示:
1 |
LRUHandle *node_a; // 地址:0x100,数据:{value: "A", next_hash: 0x200} |
当然这里内存地址的具体值只是为了方便理解,实际运行的内存地址位置会不一样。现在有一个新的节点 node_h,地址是 0x500,如果要在上面链表中用头插法插入该节点,核心代码只有 3 行,如下:
1 |
LRUHandle** ptr = &new_list[hash & (new_length - 1)]; |
我们来看这里每一行带来的变化。第一行执行完,这里整体内存布局如下:
变量名 | 内存地址 | 存储的值 |
---|---|---|
ptr | 0x400 | 0x300 |
bucket | 0x300 | 0x100 |
node_a | 0x100 | {value: “A”, next_hash: 0x200} |
node_b | 0x200 | {value: “B”, next_hash: nullptr} |
接着执行 h->next_hash = *ptr
把 node_h 的 next_hash 指向 *ptr,这里 *ptr 拿到的就是 A 的地址,整体内存布局如下:
变量名 | 内存地址 | 存储的值 |
---|---|---|
ptr | 0x400 | 0x300 |
bucket | 0x300 | 0x100 (*ptr) |
node_h | 0x500 | {value: “H”, next_hash: 0x100} |
node_a | 0x100 | {value: “A”, next_hash: 0x200} |
node_b | 0x200 | {value: “B”, next_hash: nullptr} |
这时候我们已经建好了 H->A->B->nullptr 链。只是 bucket 还是指向了 A,所以要接着执行 *ptr = h
让 bucket 指向 node_h 的地址,这一步完成后整体内存布局如下:
变量名 | 内存地址 | 存储的值 |
---|---|---|
ptr | 0x400 | 0x300 |
bucket | 0x300 | 0x500 |
node_h | 0x500 | {value: “H”, next_hash: 0x100} |
node_a | 0x100 | {value: “A”, next_hash: 0x200} |
node_b | 0x200 | {value: “B”, next_hash: nullptr} |
至此,我们就完成了 p->bucket->H->A->B->nullptr
的构建。
我们详细分析了 LevelDB 的哈希表实现,看完应该能设计一个高性能的哈希表了吧,哈哈。最后总结下 LevelDB 哈希表实现的关键点:
虽然这里哈希表主要用于 LevelDB 的 LRU Cache,但其中的很多设计思想对于实现其他高性能数据结构都很有参考价值。
2024-09-25 05:00:00
在上篇 LevelDB 源码阅读:跳表的原理、实现以及可视化中,详细分析了 LevelDB 中跳表的实现。然后在 LevelDB 源码阅读:如何正确测试跳表的并行读写? 中,分析了 LevelDB 跳表的测试代码,最后还剩下一个问题,怎么分析跳表的时间复杂度呢?
在分析完跳表的时间复杂度之后,就能明白 LevelDB 中概率值和最大高度的选择,以及 Redis 为什么选择不同的最大高度。最后本文也会提供一个简单的压测代码,来看看跳表的性能如何。
本文不会有很高深的数学知识,只涉及简单的概率论,可以放心往下看。跳表的性能分析有不少思路很值得借鉴,希望本文能抛砖引玉,给大家带来一些启发。
在知道 LevelDB 的原理和实现后,我们可以推测出来,在极端情况下,每个节点的高度都是 1,那么跳表的查找、插入、删除操作的时间复杂度都会退化到 O(n)。在这种情况下,性能比平衡树差了不少。当然,因为有随机性在里面,所以没有输入序列能始终导致性能最差。
那么跳表的平均性能如何呢?前面给出过结论,和平衡树的平均性能差不多。引入一个简单的随机高度,就能保证跳表的平均性能和平衡树差不多。这背后有没有什么分析方法,能够分析跳表的性能呢?
还得看论文,论文中给出了一个不错的分析方法,不过这里的思路其实有点难想到,理解起来也有点费劲。我会把问题尽量拆分,然后一步步来推导整个过程,每一步涉及到的数学推导也尽量给出来。哈哈,这不就是思维链嘛,拆解问题并逐步推理,是人和 AI 解决复杂问题的必备技能啊。这里的推导可以分为几个小问题:
好了,下面我们逐个问题分析。
第一个小问题比较简单。在前文讲跳表的原理和实现中,我们知道,对于插入和删除操作,也需要先通过查找操作找到对应的位置。之后就是几个指针操作,代价都是常量时间,可以忽略。所以,跳表操作的时间复杂度就是看查找操作的复杂度。
查找操作的过程就是往右,往下搜索跳表,直到找到目标元素。如果我们能知道这里搜索的平均复杂度,那么就可以知道跳表操作的平均复杂度。直接分析查找操作的平均复杂度,有点无从下手。按照 LevelDB 里面的实现,每次是从当前跳表中节点的最高层数开始找。但是节点高度是随机的,最高层数也是随机的,似乎没法分析从随机高度开始的查找操作的平均复杂度。
先放弃直接分析,来尝试回答前面第二个问题。假设从任意层 k 开始往下找,平均要多少次才能找到目标位置呢?这里的分析思路比较跳跃,我们反过来分析从目标位置,往上往左查找,平均要多少步才能往上查 k 层。并且假设链表中节点高度是在反向查找过程中,根据概率 p 来随机决定的。
这种假设和分析过程得到的平均查找次数和真实查找情况等价吗?我们知道往右往下执行查找的时候,节点的高度都是已经决定的了。但是考虑到节点的高度本来就是随机决定的,假设反向查找时候来决定高度,并且逆向整个搜索过程,在统计上没有什么不同。
接下来我们假设当前处在节点 x 的任意一层 i (下图中的情形 a),从这个位置往上查 k 层置需要 $ C(k) $ 步。我们不知道节点 x 上面还有没有层,也不知道节点 x 的左边还有没有节点(下图中用阴影问号表示这种未知)。再假设 x 不是 header 节点,左边还有节点(其实这里分析的话可以假设左边有无穷多节点)。
那么整个链表的节点情况有两种可能,整体如上图:
也就是说,对于从任意层 i 开始查找,往上跳 $ k $ 层需要的期望步数为:
$$ \begin{align}
C(k) &= (1 - p) * (C(k) + 1) + p * (C(k-1) + 1)
\end{align} $$
化简这个方程得到下面结果:
$$
\begin{align}
C(k) &= 1/p + C(k-1)
\\
C(k) &= k/p
\end{align}
$$
这里从任意层 i 开始查找往上跳 k 层需要的期望步数 $ k/p $ ,也等价于从第 k 层开始正常步骤查找,到最底层目标位置需要的期望步数。这个公式很重要,只要理解了这里的逆向分析步骤,最后公式也比较好推导出来。但是用这个公式还是没法直接分析出跳表的平均性能,中间缺少了点什么。
从上面分析可以看到从第 K 层查找到底层的时间复杂度是 $ k/p $,那么实际跳表查找的时候,从哪层开始搜索比较好呢?在LevelDB 源码阅读:跳表的原理、实现以及可视化可以知道跳表中节点的层高是随机的,对于其中某层,可能有多个节点,越往上层,节点数越少。
LevelDB 的实现中,是从跳表的最高层开始查找的。但其实如果从最高层开始搜索,可能会做很多无用功。比如下面的跳表中,其中 79 对应的层非常高,从这层开始搜索,需要往下走很多步,都是无效搜索。如果从 5 对应的层高开始搜索,则节省了不少搜索步骤。下图来自跳表的可视化页面:
理想情况下,我们希望从一个”合适“的层级开始搜索。论文中是这样定义合适的层:在该层期望看到 $1/p$ 个节点。因为我们的 p 一般取值 1/2,1/4 这样的值,所以这里一般从有 2 或者 4 个节点的层开始搜索。从这个层开始搜索,不至于做无用功,也不至于从太低层开始的话,失去跳表的优势。接下来只需要知道这样的层,平均有多高,然后结合前面的 $ k/p $ 就可以知道整体的搜索复杂度了。
现在来看看具体的推算步骤。假设一共有 $ n $ 个节点,然后在第 $ L $ 层有 $ 1/p $ 个节点。因为每次以 $ p $ 的概率决定是否向上层跳,所以有:
$$ n * p^{L-1} = 1/p $$
注意 L 层跳 $L-1$ 次,所以这里的 $ p^{L-1} $ 是 L-1 次幂。将等式两边同时乘以 p:
$$
\begin{align}
(n \cdot p^{L-1}) \cdot p &= \frac{1}{p} \cdot p \\
n \cdot p^{L} &= 1
\end{align}
$$
然后两边取对数 $ log_{1/p} $,如下,这里用到了对数的乘法法则和幂法则:
$$
\begin{align}
\log_{1/p} (n \cdot p^{L}) &= \log_{1/p} 1
\\
\log_{1/p} n + L \cdot \log_{1/p} p &= 0
\end{align}
$$
接着进行简化:
$$
\begin{align}
log_{1/p} p &= -1
\\
log_{1/p} n + L * (-1) &= 0
\end{align}
$$
所以我们得到:
$$
L = log_{1/p} n
$$
也就是说,在 $ L = log_{1/p} n$ 层,期望有 $ 1/p $ 个节点。这里再补充下上面的推导过程用到的对数的法则:
$$
\begin{align}
\log(xy) &= \log(x) + \log(y) &\text{对数的乘法法则}
\\
\log(x^n) &= n \cdot \log(x) &\text{对数的幂法则}
\end{align}
$$
好了,到此关键部分已经分析完了,下面综合上面的结论来看看总的时间复杂度。对于有 $n$ 个节点的跳表,可以将查找过程分为两部分,一个是从第 $L$ 层到最底层,另一个是从顶部到第 $L$ 层。
从第 $L$ 层到最底层,按照前面的等价逆向分享,相当于从底层往上爬 $L$ 层,这里爬升的成本是:
$$
\begin{align}
O(n) &= \frac{L}{p}
\\
O(n) &= \frac{log_{1/p} n}{p}
\end{align}
$$
接着是从顶部到第 $L$ 层,这部分也是分为向左和向上。向左的步数最多也就是 $L$ 层的节点数 $\frac{1}{p}$。向上的话,从 LevelDB 的实现中,最高层次限制了 12 层,所以向上的步数也是一个常量。其实就算不限制整个跳表的高度,它的最大高度期望也可以计算出来(这里忽略计算过程,不是很重要):
$$ H ≤ L + \frac{1}{1-p}$$
所以不限制高度的情况下,这里的整体时间复杂度上限是:
$$ O(n) = \frac{log_{1/p} n}{p} + \frac{1}{1-p} + \frac{1}{p} $$
上面的时间复杂度其实也就是 $ O(log n) $。最后再多说一点,虽然从第 L 层开始搜索比较好,但是实际实现中也没必要这样。像 LevelDB 一样,限制了整体跳表高度后,从当前跳表的最大高度开始查找,性能也不会差多少的。因为从第 L 层开始往上的搜索代价是常数级别的,所以没有大影响。此外,其实实现中最大层数也是根据 p 和 n 推算的一个接近 L 层的值。
论文中还分析了 p 值选择对性能和空间占用的影响,这里也顺便提下。显而易见,p 值越小,空间效率越高(每个节点的指针更少),但搜索时间通常会增加。整体如下表:
p | Normalized search times (i.e., normalized L(n)/p) | Avg. # of pointers per node (i.e., 1/(1-p)) |
---|---|---|
1/2 | 1 | 2 |
1/e | 0.94… | 1.58… |
1/4 | 1 | 1.33… |
1/8 | 1.33… | 1.14… |
1/16 | 2 | 1.07… |
论文推荐这里的 p 值选择 1/4,既有不错的时间常数,每个节点平均空间也比较少。LevelDB 中实现选择了 p = 1/4,Redis 的 zset 实现中也是选择了 ZSKIPLIST_P=1/4。
此外关于最高层数选择,LevelDB 中实现选择了 12 层,Redis 中选择了 32 层。这里是基于什么考虑呢?
回到前面的分析中,我们知道从一个合适的层开始搜索效率最高,这里合适的层是 $ log_{1/p} n $。现在 p 已经确定是 1/4,只要能预估跳表的最大节点数 N,那么就能知道合适的层是多少。然后设置最大层数为这个值,就能保证跳表的平均性能。下面是 p=1/4 时,不同节点数对应的合适层数:
概率值 p | 节点数 n | 合适的层数(最大层) |
---|---|---|
1/4 | $2^{16}$ | 8 |
1/4 | $2^{20}$ | 10 |
1/4 | $2^{24}$ | 12 |
1/4 | $2^{32}$ | 16 |
1/4 | $2^{64}$ | 32 |
Redis 中选择了 32 层,因为要支持最多 2^64 个元素。LevelDB 中在 Memtable 和 SSTable 中用跳表存储 key,里面 key 的数量不会很多,因此选择了 12 层,可以最大支持 2^24 个元素。
LevelDB 中没有对跳表的性能进行测试,我们自己来简单写一个。这里用 Google 的 benchmark 库,来测试跳表的插入和查找性能。为了方便对比,这里也加了一个对 unordered_map 的测试,看看这两个的性能差异。跳表插入的测试核心代码如下:
1 |
static void BM_SkipListInsertSingle(benchmark::State& state) { |
这里针对不同跳表和 unordered_map 表的长度,执行随机数字插入和查找,然后计算平均耗时。完整的代码在 skiplist_benchmark。注意这里 benchmark 会自动决定 Iterations 的次数,跳表插入每次初始化有点久,所以这里手动指定了 Iterations 为 1000。
./skiplist_benchmark –benchmark_min_time=1000x
运行结果如下:
虽然这里是编译的 Debug 版本,没有优化。但是根据这里的测试结果可以看到,虽然跳表长度增加,但是插入耗时并没有显著增加。查找性能和 unordered_map 相比,差别也不是很大。
本文是 LevelDB 跳表的最后一篇了,详细分析了跳表的时间复杂度。通过拆解查找问题,逆向整个查找过程,以及找到合适的 L 层,最后推导出跳表的时间复杂度。在知道时间复杂度的基础上,进而推导如何选择概率 p,以及 redis 和 LevelDB 中跳表的最大高度选择原因。最后通过简单的 benchmark 测试了跳表的性能,并与 unordered_map 进行了对比。
本系列其他两篇文章: