“LevelDB源码解析(1) Arena内存分配器

你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章

背景

LevelDB中需要频繁申请和释放内存,如果直接使用系统的new/delete或者malloc/free接口申请和释放内存,会产生大量内存碎片,进而拖累系统的性能表现。所以LevelDB实现了一个Area内存分配器来对内存进行管理,以保证性能。

Arena的核心思想

LevelDB本身不再直接申请和释放内存,需要内存时,向Arena申请。内存释放由Arena负责,LevelDB不再关心内存释放问题。

Arena从系统申请内存时是以固定大小(block_size) 整块申请的,LevelDB向Arena申请内存时,Arena按照LevelDB申请的内存大小(request_size)从已申请的内存块中分配,如果内存块中剩下的内存少于request_size,就不能直接分配了。此时分两种情况:如果requet_size 大于block_size的四分之一,Arena会申请一个request_size的内存返回给LevelDB。反之就申请一个block_size的内存块,然后从新的内存块中分配内存给LevelDB。

四分之一策略,让小内存可以都从内存块中分配内存,而较大的内存申请从系统申请。避免了大量的小内存申请和释放,同时也保证了每个内存块被浪费的空间不会超过block_size/4。这里要理解内存浪费是不可避免的,比如如果把四分之一的阈值降低到百分之一,确实每个内存块浪费的空间会减少很多,但是也意味着很多小于block_size/4但是大于block_size/100的的小内存请求都从系统申请了,这就会造成本文开头所提到的内存碎片问题。所以四分之一的阈值其实是在空间浪费和内存碎片之间找的一个平衡点。

如果request_size比block_size还大怎么办?此时,Arena会申请一个request_size大小的内存块,返回给LevelDB。

Arena申请的内存什么时候释放呢?Arena申请的所有内存都是在Arena析构时一起释放的。LevelDB中每个MemTable对象都有一个Arena成员变量,MemTable是LevelDB在内存中的数据缓存结构,每个MemTable写满后就会落盘(写入磁盘),然后被销毁。Arena也会跟着一起析构。所以不用担心内存一直释放不了。

Arena源码解析

注:本文使用的代码版本是是LevelDB 1.22

我们先看头文件arena.h

#include <atomic>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace leveldb
{
  class Arena
  {
  public:
    Arena();

    Arena(const Arena&) = delete;

    Arena& operator=(const Arena&) = delete;

    ~Arena();

    char* Allocate(size_t bytes);

    char* AllocateAligned(size_t bytes);

    size_t MemoryUsage() const
    {
      return memory_usage_.load(std::memory_order_relaxed);
    }

  private:
    char* AllocateFallback(size_t bytes);

    char* AllocateNewBlock(size_t block_bytes);

    char* alloc_ptr_;
    size_t alloc_bytes_remaining_;

    std::vector<char*> blocks_;

    std::atomic<size_t> memory_usage_;
  };

  inline char* Arena::Allocate(size_t bytes)
  {
    assert(bytes > 0);
    if( bytes <= alloc_bytes_remaining_ )
    {
      char* result = alloc_ptr_;
      alloc_ptr_ += bytes;
      alloc_bytes_remaining_ -= bytes;
      return result;
    }
    return AllocateFallback(bytes);
  }
}

Arena的接口很简单,除了构造/析构函数,对外接口实际上只有三个:Allocate,AllocateAligned,MemoryUsage,内部私有接口有两个AllocateFallback和AllocateFallback,有4个私有成员变量

成员变量

alloc_ptr_ 指向当前可分配的内存块空闲空间的头部。
alloc_bytes_remaining_ 存储当前内存空空闲空间的大小
blocks_ 是一个数组,保存了所有已分配内存块的指针
memory_usage_ 保存Arena占用的总内存大小

Allocate函数

Allcate是Arena提供给外部用于申请内存的接口,参数只有一个bytes,代表想要申请的内存大小。

Allocate函数是内联函数,不了解内联函数的同学可以看一下内联函数(inline Function)浅析,函数的实现体如下:

inline char* Arena::Allocate(size_t bytes)
{
  assert(bytes > 0);
  if( bytes <= alloc_bytes_remaining_ )
  {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);
}

Allocate先检查当前内存块的空闲内存是否足够,如果足够就直接从当前内存块分配,如果不足,就调用AllocateFallback来分配内存。AllocateFallback顾名思义,就是在空闲内存不足时的应变分配计划。

如果是直接从当前内存块分配,Arena会从当前空闲内存的头部划出bytes的空间返回给调用方,并把alloc_ptr_指向新的空闲内存头部。并把alloc_bytes_remaining_减去bytes。

下面我们看一下AllocateFallback

AllocateFallback函数

char* Arena::AllocateFallback(size_t bytes)
{
  if( bytes > kBlockSize / 4 )
  {
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

AllocateFallback会先检查申请的bytes是否超过了内存块固定大小kBlockSize的四分之一,
如果超过了就调用AllocateNewBlock直接分配一个bytes大小的内存块。如果没有超过,就调用AllocateNewBlock分配一个kBlockSize的新内存块。alloc_ptr_指向最新的内存块头部,并把alloc_bytes_remaining_置为kBlockSize。然后再从当前内存块分配内存并返回,分配逻辑和在Allocate中直接分配相同。

可以看到,两种情况下AllocateFallback都会调用AllocateNewBlock来分配新的内存块,只是申请的大小和用途不太一样。

AllocateNewBlock函数

AllocateNewBlock函数的实现体如下所示

char* Arena::AllocateNewBlock(size_t block_bytes)
{
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.fetch_add(block_bytes + sizeof(char*), std::memory_order_relaxed);
  return result;
}

AllocateNewBlock的逻辑其实非常简单,首先申请一个size为block_bytes的内存块(这里使用了char数组来实现),然后把内存块的指针存入blocks_数组,然后把block_bytes + sizeof(char*)累加到memory_usage_,可以看到memory_usage_并不是分配的内存块大小,还包含了每个内存块的指针大小。最后AllocateNewBlock返回申请到的内存块指针。

到这里就理清楚了Arena的Allocate分配内存的完整逻辑了,是不是还忘了点什么?

对的,除了Allocate,Arena还提供了另外一个外部接口AllocateAligned。顾名思义,这个接口分配的内存是对齐的。内存对齐是为了减少CPU取数据的次数,提高性能,内存对齐又可以展开为一篇新的文章了,篇幅原因,这里就不赘述了。我们重点介绍AllocateAligned的实现。

AllocateAligned函数

char* Arena::AllocateAligned(size_t bytes)
{
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  static_assert((align & (align - 1)) == 0, "Pointer size should be a power of 2");
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
  size_t slop = (current_mod == 0 ? 0 : align - current_mod);
  size_t needed = bytes + slop;
  char* result;
  if( needed <= alloc_bytes_remaining_ )
  {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  }else
  {
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
  return result;
}
  • Step1:判断当前的系统需要对齐多少字节,指针的size就代表了系统的对齐字节。如果对齐字节小于8,就把align设置为8,反之设置为系统的对齐字节。
  • Step2:断言判断对齐字节数align是否为2的N次方,不是就出大问题了。。想想有一个31bit位的操作系统。这里用了一个比较tricky的方式,通过与操作来判断是否为2的N次方,避免了反复求余。
  • Step3:计算当前空闲内存的首地址未对齐的字节数current_mod。因为align一定是2的n次方,所以其二进制形式肯定是1[0]*这种形式,即一个1,N个0。那么align-1二进制结果就是N个1了。alloc_ptr进行与运算后只保留了低N位的值,自然也就是为对齐的字节数了
  • Step4:求需要补齐的字节数slop,如果current_mod为0,说明已经对齐了,不需要补字节,如果current_mod不为0,就需要补align-current_mode的字节数,这个很好理解。
  • Step5:bytes+slop得到实际需要申请的内存数,即实际申请的内存数应当为原先申请的内存数+对齐补上的字节数。
  • Step6:这里的分配逻辑就和Allocate里面一样了,如果需要内存needed小于等于当前空闲内存,就直接从当前内存块分配,只是首地址加上了对齐字节数的偏移量。这样分配的内存的首地址就是对齐了。
  • Step7:如果剩余空闲内存不足,就调用AllocateFallback进行分配,AllocateFallback是直接从系统申请内存的,所以内存一定是对齐的(不然这个系统要着还有何用),这里可能会让有些同学比较困惑。既然系统分配的内存时对齐的,为什么前面的还需要进行对齐呢?假设现在有一个新的对齐的内存块,首地址为0x00,系统的对齐字节数为8,我们先从内存块分配了5个字节内存,显然这个内存的首地址是对齐的,此时alloc_ptr_的值变为了0x05。如果此时我们再从剩下的空闲内存中分配5个字节的内存,新分配的5字节的首地址就是0x05了,没有对齐,所以需要补上3个字节进行对齐,这样新分配的内存的首地址就变成了0x08,就对齐了。
  • Step8:断言检查分配的内存首地址是否为2的整数倍
  • Step9:返回分配的内存首地址。

可以看到,在AllocateAligned中,使用了static_assert和assert,这个两个都是断言,有什么区别呢,感兴趣的同学可以移步C/C++中的断言(assert与static_assert)

源码版本

https://github.com/google/leveldb/releases/tag/1.22

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数&#xff1a; gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点&#xff1a; 完后运行&#xff0c;r gdb 中的有用命令 下面是一个有用的 gdb 命令子集&#xff0c;按可能需要的顺序大致列出。 第一列给出了命令&#xff0c;可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布&#xff1a; 一元高斯分布&#xff1a;(将多元高斯分布中的D取值1&#xff09; 其中代表的是平均值&#xff0c;是方差的平方&#xff0c;也可以用来表示&#xff0c;是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要&#xff0c;需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容&#xff0c;经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch &#xff0c;简称ES 。是一个全文搜索服务器&#xff0c;也可以作为NoSQL 数据库&#xff0c;存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项&#xff1a; (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候&#xff0c;访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议&#xff1a;以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么&#xff1f; 在java规范中是这样描述的&#xff1a;Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联&#xff0c;线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统&#xff0c;该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口&#xff0c;远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能&#xff0c;出了大概一年了。 程序员们在编程时遇到不会的问题&#xff0c;又没有老师可以提问&#xff0c;就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法&#xff0c;但是不一定得到回复&#xff0c;…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎&#xff0c;题目很狗&#xff0c;第一次踩这个坑&#xff0c;单拉出来写个题解记录一下 题意&#xff1a;给一个数字矩阵&#xff0c;一次操作&#xff1a;对于每一行&#xff0c;可以去掉左端或者右端的数&#xff0c;得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1&#xff09;全特化2&#xff09;偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类&#xff1a; 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…