0%

jemalloc内存分配浅析

背景介绍

前段时间,基础架构的同事分享了一些东西,其中提到对openjdk做了一些优化,其中主要包括提前引入一些高版本的优良小功能,优化内存使用,异常日志展示出代码列位置,其中内存优化部分主要是把内存分配从glibc默认的malloc切换到了jemalloc(Jason Evans malloc),这个优化在生产环境中最显著的效果是程序的内存使用减少了一些。

简单分析

应用程序例如c中使用malloc和free来做变量的创建和销毁,cpp中使用new和delete,至于Java中使用了new来分配对象,销毁依赖gc自动执行,这些最终都是调用malloc和free,默认情况下会使用glibc的实现,用户可以通过在编译或者链接时指定其他实现。

这一类的malloc/free其实都是对内存申请和销毁系统调用(system call) brk 和 mmap 的包装,因为操作系统一般是按照一次4k(一个page)来分配内存的(如果每次程序申请内存都从操作系统分配,操作系统管理内存会很麻烦,而且会有太多系统中断)。
虚拟内存的布局如下图
virtual memory layout
其中,brk主要是对堆(Heap)界限地址的增加,相当于扩大堆的大小(修改上图中的Program break),从而分配了内存,主要针对小内存(128k以内)分,主要针对小内存(128k以内)分配。
mmap是直接在虚拟内存中找一段空闲的来使用(Program break 和 top of stack 之间),主要针对大内存(128k以上)的分配。
值得注意的是这两种方式分配的都是虚拟内存,当分配的这个内存被访问的时候会触发缺页中断进入内核态,操作系统将为其分配物理内存并关联到虚拟内存。

我们可以通过下面的测试代码验证malloc所使用的系统调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <jemalloc/jemalloc.h>

#define malloc(size) je_malloc(size)

int main() {
printf("start here --------------\n");
for (int i = 0; i < 5; ++i) {
char * s = malloc(50000);
s[0] = 'h';
printf("allocate small %p\n", s);
}
printf("finish small allocator\n");
for (int i = 0; i < 2; ++i) {
char * s = malloc(5000000);
s[0] = 'h';
printf("allocate large %p\n", s);
}
printf("finish here --------------\n");
return 0;
}

编译并运行

1
2
gcc -g dummy.c -o dummy
strace ./dummy

截取相关输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
brk(NULL)                               = 0x115c000
brk(0x117d000) = 0x117d000
brk(NULL) = 0x117d000
write(1, "start here --------------\n", 26start here --------------
) = 26
write(1, "allocate small 0x115c6b0\n", 25allocate small 0x115c6b0
) = 25
write(1, "allocate small 0x1168a10\n", 25allocate small 0x1168a10
) = 25
brk(NULL) = 0x117d000
brk(0x11a2000) = 0x11a2000
write(1, "allocate small 0x1174d70\n", 25allocate small 0x1174d70
) = 25
write(1, "allocate small 0x11810d0\n", 25allocate small 0x11810d0
) = 25
write(1, "allocate small 0x118d430\n", 25allocate small 0x118d430
) = 25
write(1, "finish small allocator\n", 23finish small allocator
) = 23
mmap(NULL, 5001216, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f8bafb3b000
write(1, "allocate large 0x7f8bafb3b010\n", 30allocate large 0x7f8bafb3b010
) = 30
mmap(NULL, 5001216, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f8baf676000
write(1, "allocate large 0x7f8baf676010\n", 30allocate large 0x7f8baf676010
) = 30
write(1, "finish here --------------\n", 27finish here --------------
) = 27

从strace结果可以看出,在glibc实现中,malloc在分配小内存块的时候,会调用brk,分配大内存块的时候会调用mmap,其中brk可能调一次就够多次内存分使用了。

我们改成使用jemalloc,通过下面的命令编译并运行。(这个前提是在redis的dep里把jemalloc先编译好,不要install)

1
2
3
4
gcc -g -Ideps/jemalloc/include dummy.c deps/jemalloc/lib/libjemalloc.a -lpthread -o dummy
// 或者分开(抄的Redis里的Makefile的)
cc -std=c99 -pedantic -DREDIS_STATIC= -Wall -W -Wno-missing-field-initializers -O2 -g -ggdb -DUSE_JEMALLOC -Ideps/jemalloc/include -c dummy.c
cc -g -ggdb -rdynamic -o dummy dummy.o -lm -ldl deps/jemalloc/lib/libjemalloc.a

我们发现无论小内存块还是大内存块都是用mmap系统调用申请的,从jemalloc文档中得到了

Traditionally, allocators have used sbrk(2) to obtain memory, which is suboptimal for several reasons, including race conditions, increased fragmentation, and artificial limitations on maximum usable memory. If sbrk(2) is supported by the operating system, this allocator uses both mmap(2) and sbrk(2), in that order of preference; otherwise only mmap(2) is used.

同时从jemalloc的代码中我们也能看到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// chunk_dss.h
#define DSS_PREC_DEFAULT dss_prec_secondary

// chunk.c
static void *
chunk_alloc_core(arena_t *arena, void *new_addr, size_t size, size_t alignment,
bool *zero, bool *commit, dss_prec_t dss_prec)
{
void *ret;
chunk_hooks_t chunk_hooks = CHUNK_HOOKS_INITIALIZER;

assert(size != 0);
assert((size & chunksize_mask) == 0);
assert(alignment != 0);
assert((alignment & chunksize_mask) == 0);

/* Retained. */
if ((ret = chunk_recycle(arena, &chunk_hooks,
&arena->chunks_szad_retained, &arena->chunks_ad_retained, false,
new_addr, size, alignment, zero, commit, true)) != NULL)
return (ret);

/* "primary" dss. */
if (have_dss && dss_prec == dss_prec_primary && (ret =
chunk_alloc_dss(arena, new_addr, size, alignment, zero, commit)) !=
NULL)
return (ret);
/*
* mmap. Requesting an address is not implemented for
* chunk_alloc_mmap(), so only call it if (new_addr == NULL).
*/
if (new_addr == NULL && (ret = chunk_alloc_mmap(size, alignment, zero,
commit)) != NULL)
return (ret);
/* "secondary" dss. */
if (have_dss && dss_prec == dss_prec_secondary && (ret =
chunk_alloc_dss(arena, new_addr, size, alignment, zero, commit)) !=
NULL)
return (ret);

/* All strategies for allocation failed. */
return (NULL);
}

其实就是jemalloc通过dss_prec来控制是否优先使用brk,默认是不优先使用,因此每次是先用mmap分配,如果没分配到再用brk,而一般mmap都是能分配到内存的,所以就没有用brk了。

jemalloc是众多malloc实现中的一种,Jason Evans在2005年为FreeBSD开发的malloc实现,且在Mozilla Firefox浏览器中被使用到了,它是在多核处理器开始广泛使用 和 内存越来越便宜的情况下,对内存分配的一个优化,和传统的malloc相比,更多的是考虑如何减少多核同时申请内存并发的情况、如何减少内存碎片、以及如何提高缓存的locality(CacheLine相关的东西),但是归根结底来说,它也和其他的xxmalloc一样是对系统调用 brk/mmap 的包装,只是内部的策略不一样。

实现原理

下面简单介绍下jemalloc的实现原理
首先,我们了解下外部碎片和内部碎片两个基础概念,后面会用到
fragmemtation
外部碎片就是程序内存块中除了分配给程序的剩下的内存,内部碎片是程序申请内存在使用的剩余,例如需要7Byte内存,实际上会申请8Byte的内存(个人理解主要是基于整个内存分配的效率问题以及内存对齐)

其次,我们了解下buddy allocator和slab allocator两种基本的内存分配策略,后面会用到
allocator
如上图,buddy allocator(以binary allocator为例),对于申请NByte内存,会将MByte大小的内存块不断等分,直到符合申请的内存大小,例如从4K的内存块中申请一个996Byte的内存,首先会将4K内存等分到2K,然后等分到1K,这样就返回给申请内存的进程了(不能再分了,再分就不够了),这里多出来的部分(1024Byte-996Byte=28Byte)其实就是上面所说的内部碎片。
而slab allocator值的是将内存分配成固定大小的块,申请的时候直接从中获取空闲块,例如将4K的分成4个1K的块。

简单来说,jemalloc(或者说其他同类的xxmalloc)本质上都是在应用程序和操作系统中间,做一个内存分配的适配,jemalloc会将管理从操作系统申请到的page(大小4k),并通过一些策略来为应用程序提供高效的内存分配,在单核CPU情况下,分配内存是不存在竞争的,但是在目前多核CPU光房使用的情况下,需要考虑并发申请内存的情况,jemalloc按照round-robin方式将进程映射到不同的arean来处理内存分配,arean数量默认是多核CPU数量的四倍。不过,为了进一步减少线程之前的竞争,在arena前面加了一层tcache,每个进程一个tcache,根据size class缓存一些较小的内存块,方便直接使用。

下图是jemalloc的大体的结构:
jemalloc implementation
从图中可以看出,每个进程对应一个arena,arena内部有维护dirty和space chunck的红黑树,chunk会在后面介绍,同时还有一个bins数组,里面每一个bin对应的是一个size class,size class分为下面三大类(里面每一个小类对应一个类型的bin):

  • small [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
  • large [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
  • huge [4 MiB, 8 MiB, 12 MiB, …]

bin内部用红黑树存储了这个size class的所有run(runs),按照其实地址排序,同时还有一个runcur,作为当前的run来分配内存使用,当runcur分配完了之后就会从红黑树找下一个run替换runcur来支撑后续的内存分配,run放在chunk里面,一个chunk里面有多个run。

A bin is what keeps track of free regions of a specific size. All the runs in a Bin have the same region size, equal to the binRegionSize. Every Run is part of some Bin. A Bin can manage multiple Runs.

chunck 是jemalloc的内存分配基本单元,最小单元,默认是2M,其结构如下:
jemalloc chunk
可以看到chunk header里面指向了特定arean,同时根据buddy allocator将chunk分割成不同大小的run(每个run负责分配固定大小的内存块),run的大小是page的倍数(4K),如果是small size,run内部会按照slab allocator将内存划分为大小一样的region,如果是large size的内存(比chunk小,比page大)会直接返回一个run,如果是huge size则会申请多个连续的chunk返回。

总的来说,分配内存的流程是 Client Thread -> arena -> bin -> runcur -> region/直接用run 返回。

性能对比

为了得到jemalloc对比glibc malloc性能优势的直观数据,我们用Redis的benchmark脚本来简单压测一下,因为之前注意到Redis是支持glibc默认malloc、jemalloc、tcmalloc三种内存分配器的(都包装在zmalloc里)。本来想用raspberry pi压测一下,但是测试了下发现QPS只能到3000左右(50 client, 官方说ARM上能跑两万多),而且响应时间能到几百毫秒,一压测CPU就90%以上,感觉结果可能不会太置信。最后还是决定用2台vultr的云机器压测,压测之前先配好private ip,一台跑压测脚本,一台运行 Redis Server
压测的重点是关注 SET 命令的 响应时间和内存占用以及碎片率,因为SET操作是需要不断分配内存的,压测机器配置

1
2
3
4
OS: CentOS SELinux 8 x64
CPU: 1 vCore
RAM: 1024M
Storate: 25 GB SSD

先安装和编译 Redis

1
2
3
4
5
6
7
8
9
wget https://github.com/redis/redis/archive/refs/tags/4.0.0.tar.gz
tar zxvf 4.0.0.tar.gz
cd redis-4.0.0/src
yum install gcc make -y
make MALLOC=jemalloc # 按需选择
./redis-server
./redis-cli
# 允许跨机器访问
CONFIG SET protected-mode no

除了jemmaloc版本的,我们另外还编译了一个默认的(修改make后面的MALLOC参数即可),供对比使用。

在压测机器上执行命令

1
./redis-benchmark -h 10.40.112.4 -p 6379 -t set -n 1000000 -r 10000000000000000 -d 16

默认50个client,value长度是16个字节(-d),key后缀的范围是0 ~ 10000000000000000(-r),请求100W次(-n) set(-t) 命令,一定注意上面的 -r 是指 key 的数值范围,而不是key的位数,压测时候key会带一个前缀,加上这个范围的数字
为了减少误差,我们每次压测前都重启 Redis Server 所在的机器,并重复三次,得到平均值,同时注意压测前把上一次的rdb文件删除了再启动,可以观察到压测的时候CPU保持在25%左右,最终一些关键指标如下:
jemalloc vs glibc malloc

从压测结果可以看出,jemalloc在内存占用和内存碎片上有显著优势,jelloc内存占用只有glibc malloc的87%,而rss内存只有65%,且P995耗时上jemalloc有微弱优势,最大耗时上jemalloc也是会稍微少一点

两者差异的原因,我们做个简单分析,首先,由于key和value的长度比较小,glibc会使用brk分配内存,这个我已经通过strace redis-server验证了,而jemalloc会使用mmap分配内存,这个同样得到了验证,而且我们发现glibc调用brk的频率会明显高于jemalloc,因为我只抓到个位数的mmap调用,而且一次申请的内存块很大,但是brk是有十多次的调用,每次申请的内存块不是特别大。

结论

大白话来说,jemlloc能节省内存(从redis benchmark可以看出),按照大型公司的服务部署所需要的内存使用量来看,节省的内存卡数量会很客观,也就是能很多省钱。
其实这里引出来另一个问题是为什么mmap比brk高效果,这个留到后面有时间再讨论。

Reference

  1. A Memory Allocator(glibc)
  2. A Scalable Concurrent malloc(3) Implementation for FreeBSD - jemalloc
  3. How processes get more memory. (mmap, brk)
  4. Structures in jemalloc
  5. phrack.org
  6. jemalloc 源码分析
  7. What’s the difference between slab and buddy system?
  8. Scalable memory allocation using jemalloc
  9. How Process Get More Memory
  10. 在Linux安装和编译jemalloc的方法
  11. jemalloc example
如果您觉得这些内容对您有帮助,你可以赞助我以提高站点的文章质量