文章目录
- Rocksdb ConcurrentArena 实现原理
- 基本架构
- 内存分配过程
- 内存释放过程
- ConcurrentArena 分配器 和 其他内存分配器区别和联系
- 总结
还是一起来看看内存分配器。
Rocksdb 作为 LSM-tree 当前业界实现的代表，因为有LSM-tree 的内存组件 – memtable 的存在，肯定会有内存分配的需求 (关于内存分配器的演进，可以通过 内存分配器设计的技术演进 了解一下，能够大概清楚为什么当前对内存有需求的应用程序都需要一个内存分配器)。
而且memtable 作为直接影响写性能的关键组件，除了本身memtable 索引的高效实现之外内存分配的高效性是一个强需求。因为rocksdb 写模型的存在，会有多线程并发写同一个memtable的情况，也就是针对同一个memtable的多核并发内存分配的高效性是一个关键需求；当然，提升性能的同时也需要尽可能得降低内存碎片。
除了memtable 组件之外，能够在rocksdb 的各个内存申请需求中都能看到 内存分配器的身影，比如 iterator 体系的数据存储，block_cache 的数据存储(index_filter/bloom_fiter等)，rocksdb 本身的内存分配器涵盖了基本所有的引擎内部内存申请需求，其性能/内存使用率控制 都需要非常高的要求。
当然，rocksdb也支持其他的内存分配器：glibc-allocator，jemalloc，tcmalloc。
本篇希望能够回答如下几个问题：
- Rocksdb 的 arena 内存分配器设计，包括如何保证多核下的性能 和 降低内存碎片
- Rocksdb Arena Allocator 和 其他内存分配器的"区别" 和 联系
- 为什么 Rocksdb 不直接使用 其他的内存分配器？非要自己搞一套？
相关 rocksdb 源代码: v6.25
Rocksdb ConcurrentArena 实现原理
基本架构
先来上一个基本架构图。
熟悉内存分配器的同学 看到这个图，应该已经能够回答上面的部分问题了。
上图中灰色虚线部分 就是rocksdb的主要两种 用于维护 ConcurrentArena 的数据结构了：
- Arena ，这个不用多说，在glibc-malloc 和 jemalloc 都用它作为内存分配器的后端部分，用于直接从os 申请大块内存进行管理，作为提供给应用程序的内存池。在tcmalloc 中 就是 back-end 的 pagemap 的内存池。通俗的来说 Arena 就是一个应用程序统一管理 堆内存以及系统空闲内存的数据结构。
- shard，这个在 ConcurrentArena 类中其实叫做
shards_，本身是一个corelocal 的数组；形态也就是上图中的样子，每一个cpu-core 会维护一个shard，用来管理运行在当前cpu 的线程的内存申请需求。其实也就是thread-cache 或者说 是 比较新版本 tcmalloc 中推出的 Per-CPU Cache。
为什么需要一个core-local 的shard 或者说 其他的内存分配器 都需要 类似thread-cache 的东西呢，显而易见，多核场景下每一个cpu 访问对自己cpu-cache 友好的数据肯定性能会更好，本来一个cpu 访问自己的cpu-cache 仅仅需要几个ns，但因为这个数据是所有cpu共享的（需要锁），因为缓存一致性协议（其他的cpu在自己的cpu-cache中更新了这个数据，就需要同步到内存中，防止除了这个cpu之外其他的cpu访问到旧数据）那就需要频繁得从内存中加载新的数据，直接放几个ns级别的延时变成了 几十甚至上百ns，性能显然非常差。
所以每个cpu/线程管理自己的 内存申请需求，这样既能降低锁的开销（没有办法避免，有的时候需要从公共的arena 申请），又降低了cpu-cache miss，对多核场景的性能提升有非常大的帮助。
内存分配过程
主要是三种大小的内存申请需求，区间分别为:[0,128KB), [128KB,256KB), [256KB, os上限)
大体流程图如下：
大内存的分配，会直接落在 Allocator上，即当前db 编译时依赖的哪一种分配器，就用哪一种进行分配。
小内存会优先由 各个cpu的 shard满足，如果容量不足，则从arena上申请。
- 小内存申请 < 128KB：默认小于128KB(Options.arena_block_size: 1048576 , 除以 8 是每个shard 维护的
shard_block_size_) 的内存申请需求，会优先从shard 管理的free_begin_ 中申请。
char* AllocateImpl(size_t bytes, bool force_arena, const Func& func) {
...
// 选择当前正在运行的核心，取出之前绑定在这个cpu-核心的shard
Shard* s = shards_.AccessAtCore(cpu & (shards_.Size() - 1));
if (!s->mutex.try_lock()) {
s = Repick();
s->mutex.lock();
}
// shard 粒度的spinlock, 保证当前线程从当前shard 的内存分配是原子的。
std::unique_lock<SpinMutex> lock(s->mutex, std::adopt_lock);
// 取当前shard 还空闲的内存大小
size_t avail = s->allocated_and_unused_.load(std::memory_order_relaxed);
...
s->allocated_and_unused_.store(avail - bytes, std::memory_order_relaxed);
// 保证拿到的内存区域 如果是8byte对齐，则追加在之前的free_begin之后（一般只有一种情况，分配的bytes 都是指针8bytes）
// |++++++used+++++++|---current-bytes--|----unused----|
// |
// free_begin_ --> move
//
// 如果没有对齐，则那到的内存起始地址是按照end 对齐的。
// |----unused----|++++++used+++++++|---current-bytes--|
// |
// move <-- free_begin_
//
char* rv;
if ((bytes % sizeof(void*)) == 0) {
// aligned allocation from the beginning
rv = s->free_begin_;
s->free_begin_ += bytes;
} else {
// unaligned from the end
rv = s->free_begin_ + avail - bytes;
}
return rv;
}- 大于shard 内存大小的 内存申请：128KB – 256KB。如果一个内存申请需求超过了当前默认的shard 内存大小 或者 shard
allocated_and_unused_ 也就是空闲内存不够了，则shard 需要从arena 申请内存，并将申请的内存大小扩充到当前shard的内存中。当然这里shard的内存大小扩充是有限制的，介于 [shard_block_size/2, shard_block_size*2)之间。
从arena 分配的时候需要又一把arena 级别的锁（这个一般是一个memtable一个锁，竞争的激烈程度取决于当前多少个线程在并发写memtable）
// 这里的这个func 是外部传入进来的，也就是arena 的allocate 函数
// [this, bytes]() { return arena_.Allocate(bytes); }
char* AllocateImpl(size_t bytes, bool force_arena, const Func& func) {
...
size_t avail = s->allocated_and_unused_.load(std::memory_order_relaxed);
// 当前shard 剩余的内存无法满足 bytes 的申请需求，则需要从arena分配
if (avail < bytes) {
// reload
// 从 arena 分配的时候需要有一把 arena粒度的锁，保证arena 分配的原子性
std::lock_guard<SpinMutex> reload_lock(arena_mutex_);
// arena 已经分配 但未使用的内存
auto exact = arena_allocated_and_unused_.load(std::memory_order_relaxed);
assert(exact == arena_.AllocatedAndUnused());
// 如果arena 已经分配 但未使用的内存满足 bytes需求，则直接从arena分配内存区域，
// 并返回 内存区域的地址 给用户； 这样能够减少内存碎片。
if (exact >= bytes && arena_.IsInInlineBlock()) {
// If we haven't exhausted arena's inline block yet, allocate from arena
// directly. This ensures that we'll do the first few small allocations
// without allocating any blocks.
// In particular this prevents empty memtables from using
// disproportionately large amount of memory: a memtable allocates on
// the order of 1 KB of memory when created; we wouldn't want to
// allocate a full arena block (typically a few megabytes) for that,
// especially if there are thousands of empty memtables.
auto rv = func();
Fixup();
return rv;// 返回的时候先执行arena分配逻辑
}
// 如果arena 没有已经分配了的空闲内存，则需要从arena上重新分配内存，
// 这个时候需要通过 arena 调整free_begin_ 大小，直到满足用户需求的bytes为止。
// 当然，大内存的分配逻辑 >= 256kb 在这一段逻辑之前已经被挡住了，所以到这里的内存申请需求都是
// < 256kb 的申请需求
avail = exact >= shard_block_size_ / 2 && exact < shard_block_size_ * 2
? exact
: shard_block_size_;
s->free_begin_ = arena_.AllocateAligned(avail);
Fixup();
}
...
}
- 大内存申请 > 256KB.
拿着 当前arena的 spinlock锁，通过 Arena::Allocate --> Arena::AllocateFallback --> Arena::AllocateNewBlock 进行分配。
char* AllocateImpl(size_t bytes, bool force_arena, const Func& func) {
size_t cpu;
// Go directly to the arena if the allocation is too large, or if
// we've never needed to Repick() and the arena mutex is available
// with no waiting. This keeps the fragmentation penalty of
// concurrency zero unless it might actually confer an advantage.
std::unique_lock<SpinMutex> arena_lock(arena_mutex_, std::defer_lock);
if (bytes > shard_block_size_ / 4 || force_arena ||
((cpu = tls_cpuid) == 0 &&
!shards_.AccessAtCore(0)->allocated_and_unused_.load(
std::memory_order_relaxed) &&
arena_lock.try_lock())) {
// 尝试加arena 的锁，直到加到为止
if (!arena_lock.owns_lock()) {
arena_lock.lock();
}
// 在arena_.Allocate(bytes); 中进行大内存的分配
auto rv = func();
Fixup();
return rv;
}
...
}
// Arena::AllocateNewBlock 的分配逻辑入下
char* Arena::AllocateNewBlock(size_t block_bytes) {
// Reserve space in `blocks_` before allocating memory via new.
// Use `emplace_back()` instead of `reserve()` to let std::vector manage its
// own memory and do fewer reallocations.
//
// - If `emplace_back` throws, no memory leaks because we haven't called `new`
// yet.
// - If `new` throws, no memory leaks because the vector will be cleaned up
// via RAII.
blocks_.emplace_back(nullptr);
// new 分配器进行分配，分配好之后的内存对象管理会通过 vector<char*> blokcs_数据结构进行管理
char* block = new char[block_bytes];
size_t allocated_size;
#ifdef ROCKSDB_MALLOC_USABLE_SIZE
allocated_size = malloc_usable_size(block);
#ifndef NDEBUG
// It's hard to predict what malloc_usable_size() returns.
// A callback can allow users to change the costed size.
std::pair<size_t*, size_t*> pair(&allocated_size, &block_bytes);
TEST_SYNC_POINT_CALLBACK("Arena::AllocateNewBlock:0", &pair);
#endif // NDEBUG
#else
allocated_size = block_bytes;
#endif // ROCKSDB_MALLOC_USABLE_SIZE
blocks_memory_ += allocated_size;
if (tracker_ != nullptr) {
tracker_->Allocate(allocated_size);
}
blocks_.back() = block;
return block;
}这里内存申请都是通过按需申请的，写入memtable的是kv，大小就是任意大小，而且128K及以上的value大小对于rocksdb来说已经是超级大value了，大多数用户应该会做一些key的拆分或者用blobdb。
所以通用场景下的小value 内存分配需求基本是满足的，关于内存碎片，因为每个shard 可以管理自己的内存，而且是按需分配（部分场景需要按照16字节对齐），不够了再从arena中申请，内存碎片问题基本可控。
内存释放过程
关于内存释放这里，Arena 数据结构维护了一个 AllocTracker* tracker_;，用于追踪整个组件的内存申请记录。
这个tracker 主要是通过用户配置的write_buffer_manager进行内存的超限释放，每一次Arena::AllocateNewBlock 从arena申请内存，申请的大小都会被记录到这个tracker之中，用来确认是否达到了write_buffer_manager的限制。
在 当前memtable 达到大小阈值之后，析构 这个arena时 会在析构函数中通过tracker 来释放当前在memtable中申请的内存
Arena::~Arena() {
if (tracker_ != nullptr) {
assert(tracker_->is_freed());
tracker_->FreeMem(); // 统一释放在write_buffer_manger 中管理的内存
}
// 之前申请的内存都在 vector<char*> blocks_中，现在释放其中的每一个元素即可
// 这里的释放其实还是 底层allocator的释放（glibc/tcmalloc/jemalloc）
for (const auto& block : blocks_) {
delete[] block;
}
// 后续时一些大页内存的munmap
...
}ConcurrentArena 分配器 和 其他内存分配器区别和联系
这个问题其实和我们文章开头要说的第三个问题关联性比较大，也就是rocksdb 为什么不直接使用其他的内存分配器，而是在他们之上又做了一个Arena？
因为rocksdb 使用内存的地方实在是太多了，而且都是核心链路。
对内存的管理 以及 内存分配的性能都需要非常高的要求，也就是rocksdb 希望能够保证性能的同时对内存有较好的控制；而底层的内存分配器没有这样的主动行为，他们只是尽可能得保证性能的同时，降低内存碎片，更好的情况是提供了一些监控手段来去查看底层的内存占用情况。如果想要主动管理内存，肯定是需要用户介入。所以，ConcurrentArena 只是为 Rocksdb 定制的便于rocksdb 高效管理自身内存使用情况的分配器，对rocksdb友好；其底层实际的内存分配 还是通过传统分配器分配的，要么tcmalloc，要么jemalloc 或者 glibc-malloc。
实现上，大家对内存分配器的设计思路比较接近 ：保证高性能的方式都差不多，小内存的申请 通过thread-cache 或者说 per-cpu cache，保证了cpu 不会频繁的cache-miss；如果支持 MAP_HUGETLB，则会直接mmap；否则大页内存就直接从底层的分配器去申请。
总结
最近对内存分配器的基本设计和实现都有了一个大体的了解，内存分配器的诞生 以及 形态的演进都在伴随着底层架构 和 我们这一些系统用户对性能和成本的高要求 而不断得精进。
- 最开始的os 栈内存自动分配内存，简单-高效。但我们想要自己管理内存，不care大小，不care 自动释放，栈内存满足不了需求。
- 尝试用mmap，但是大大小小的内存申请都要陷入内核，都要cpu-cs，性能满足不了需求。
- 我们有了最简单的bump allocator，但是它就是一个用户态栈空间，大小和生命周期都可控，但是释放是一个问题，即使当前内存对象已经到期，也需要等到栈顶释放了才能释放，释放内存又是一个问题。
- 内存管理通过free-list 单链表进行管理，串起来就好了，这样释放的时候只要遍历到这个链表节点就好了。还是有问题，又回到性能上，不同种大小的内存对象，一股脑塞在一个链表上，释放效率令人发指。
- 于是我们有了 size-buckets(在如今的tcmalloc/jemalloc 中叫size-class)，按照内存大小划分链表，不同大小的range 划分到一个链表节点上，这样释放的时候就可以直接扫对应range的链表了。追逐硬件的极致性能好像是天生的（压榨cpu的每一个逻辑门），就像资本家追逐极致利益，发掘每一个员工的潜力创造财富。这里链表是随机访问，对cpu-cache不友好。
- 将链表换成了数组，并继续维持size-buckets的形态。看起来性能不错了，硬件也在追逐自己的极致性能 – 多核架构 以及超线程出来了。之前的设计都是基于单核场景，那保证多核架构的分配性能，同时避免过多的cache-miss，thread-cache出来了。但是thread-cache 自己管理自己的内存可能会有内存碎片，比如arena 开始给各个thread分配128K内存，但是只有其中一两个thread频繁申请内存，其他的的线程很少，他们拿到的内存就都被搁置浪费了。
- (TCMalloc) 于是为了降低内存使用率，减少内存碎片，推出了transfer-cache，能够将不同的thread-cache 空闲内存回收迁移给其他内存需求比较大的线程。又有性能和内存利用率问题：如果thread-cache按照 thread粒度划分，一个进程开了上万个线程，每个线程有自己的thread-cache，这样每一个thread-cache 可管理的内存就都很小，而且需要频繁的和transfer-cache 以及后台的central-freelist交互，性能不可忍。
- 于是又设计了 Per-CPU -cache，为每一个 processor (超线程粒度)分配属于自己的cache，运行在其上的线程会从per-cpu-cache 申请内存，这样的设计对arena的管理来说也会更友好一些。
- 。。。还有 用户需求，我不知道内存分配器到底分配了多少内存，你们内部的管理形态是什么样。所以还需要提供stats信息。。。
- 。。。
总之，硬件追逐自己本身的极致性能，更高效的cpu，更高效的CPU体系架构（如今的NUMA），而且可见的未来还会不断得演进自己的性能，更快，更强。
软件开发者，尤其是基础软件开发者，想要追逐极致的硬件性能，除了软件本身 的技术栈足够熟悉之外，底层的硬件技术栈必不可少当然，前提是要追逐极致的硬件性能，如果mmap 作为内存分配器的实现，肯定也没问题:)