Akira
发布于

linux经典面试题之服务器内存碎片

Linux 服务器开发相关视频解析:

90 分钟了解 Linux 内存架构,numa 的优势,slab 的实现,vmalloc 原理

linux 多线程之 epoll 原理剖析与 reactor 原理及应用

以前在面试某两个大厂都遇到过这个问题,一个问到 Linux 下 gcc 的 malloc 函数如何分配内存的,还有一个在二面时通过一个链表的数据结构也间接地问到了这个问题。

且不说面试可能会遇到这个问题,我们很多服务器程序在长周期或者大量访问的情况后会变得反应迟钝,排查原因发现占用内存会随着请求数量的增多不规律而且不正常地增长,和内存泄漏一样。如果使用 valgrind 这样的内存泄露工具排查却发现并无内存泄露,其根本原因是内存碎片造成的。这也是我们在开发高性能服务器需要解决的一个问题,那如何解决这个问题呢?

一、 内存分配与内存碎片

经典的进程内存布局如图 1 所示。

「linux」经典面试题之服务器内存碎片

图 1 内存布局图

图 1 中底端是内存地址为 0 的地方,顶端是内存线性地址最大的地方(如 32 位下线性地址最大值是 0xFFFFFFFF),而占据顶端的就是内核空间,这里是操作系统内核预留的空间区域。第二部分是栈空间,也就是堆栈所在的内存空间,众所周知,栈是自高地址处向低地址处增长的,这在图中也有所反映。最后一部分是堆空间,在这个简化的理论模型上所有的剩余空间都预留给了堆,堆是从低地址向高地址增长的。

当然这只是一个简化模型,实际上在堆的下方,还会为静态内存空间预留内存,而堆与栈的中间可能还有供 mmap(内存映射)使用的区域。此外,由于栈的空间有限,而且只用来管理所谓的“自动变量”,因此我们在实际程序中需要大量使用到堆。堆空间不仅可用内存多,而且可以动态分配,也就是说按需获取,按需使用,不需要时释放即可。C 中的 malloc/free 与 C++ 中的 new/delete 就是用来管理内存的。但是较

少有人去深入了解 malloc/free 或者 new/delete 到底为我们做了什么。

首先,内存管理函数并不会直接去向操作系统索要内存,因为系统调用的开销比较大,这样做是非常不值的。此外,直接使用过系统调用的人都知道,在 Linux 下分配堆内存需要使用 brk 系统调用,而这个系统调用只是简单地改变堆顶指针而已,也就是将堆扩大或者缩小。所以如果我们遇到这种情况,是没有办法直接将内存归还给操作系统的,如图 2 所示。

「linux」经典面试题之服务器内存碎片

图 2 内存图

这种情况下,假设我们先分配了 memory2,再分配 memory1。现在 memory2 内存不需要了,我们想还给内存,但是遇到问题了——如果我们改变 brk 指针,那么 memory1 也会被还给系统,这样是不可行的。

我们有两种解决方案:一是将 memory2 内存中的数据复制到 memory1 中,但是这样一来,所有的内存地址都会发生变化,是不可行的;二是将 memory2 的内存缓存下来,下一次用户申请内存时我们不需要直接使用系统调用,而是直接从缓存的内存中划出一块交给用户。等到用户完全不使用 memory1 和 memory2 了再将这两块内存释放。所以在 C/C++ 真正的内存管理中,都会有这么一个内存管理器,它负责向操作系统申请内存,并将内存缓存下来,并通过某种算法从缓存的内存中划出一块交给用户,这样一可以提高程序的运行效率,二可以提高内存的使用效率,一举两得。这个内存管理器就像一个“批发商”,一次性向操作系统索要可观的内存数量,并直接将自己“批发”来的内存销售给调用内存管理函数的用户。

但是,如果我们这个“批发商”对商品管理不当,还是会出很大问题的,如图 3 所示。

「linux」经典面试题之服务器内存碎片

图 3 原始内存图

其中,每个字符串我们都分配了一定数量的空间,如字符串“a”需要 2 字节(C 中字符串需要一个额外的 0 字符用于标识字符串结束)。现在我们发现“a”、“c”、“e”这 3 个字符串再也不需要了,所以我们将其释放,现在内存如图 4 所示。

「linux」经典面试题之服务器内存碎片

图 4 释放字符串之后的内存图

这样这 3 块内存又可以重复利用了。但是这些内存太小了,为了保证之后可以更好地利用,我们需要将其合并起来(合并成一块内存),这样再次分配内存时,只要用户需要的内存不超过 6 字节,只需要从中划出一块分给用户即可。合并之后的内存图如图 5 所示。

「linux」经典面试题之服务器内存碎片

图 5 合并之后的内存图

【文章福利】需要 C/C++ Linux 服务器架构师学习资料加群 812855908(资料包括 C/C++,Linux,golang 技术,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK,FFmpeg 等)

「linux」经典面试题之服务器内存碎片

但这是一种非常理想的情况,而且是一种极端最优情况。让我们来看另一种极端最坏的情况,假设我们分配内存如图 6 所示。

「linux」经典面试题之服务器内存碎片

图 6 内存图

现在看起来是正常的。但是如果我们不需要那几个 2 字节的内存空间,内存如图 7 所示。

「linux」经典面试题之服务器内存碎片

图 7 内存图

现在那几个 2 字节的空间是被还给内存管理器了,但是内存管理器没办法对其进行合并,因为这几个很小的空间是零碎分布在这片内存中的。一个极端情况是:如果程序再也没有 2 字节的动态内存可以分配了,而且这几个 4 字节内存是永远占用的,那么这几个 2 字节内存又该如何使用呢?

很明显,这几块内存已经再也无法使用了,既不能分配又不能归还——这就是所谓的内存碎片。小规模的内存分配越多,内存碎片也就会越严重。而 gcc 默认使用的 ptmalloc 分配器对这种内存碎片的优化不是非常理想,导致了 Samuel 出现了看似是“内存泄漏”的问题,实际上是内存碎片问题。

此外,我们想象另一个场景,如果每个线程并发分配堆,由于对于每个进程堆是唯一的,因此我们再分配内存时还需要上锁,如果在一个程序中需要在短时间内频繁地分配小内存,那么又会出现因为频繁上锁而导致的性能损耗。这是我们无法接受的。

二、tcmalloc

为了解决这些问题,我们可以使用一些更好的内存管理器替代默认的内存管理器,如 Google 开发的 tcmalloc 和 jemalloc 等内存管理库,这些库使用得非常频繁,而且不需要改变原有代码,对于频繁使用内存的程序,是非常值得使用的,例如,Redis 为了获得最好的性能就使用了 tcmalloc 和 jemalloc。(Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API,是目前最流行的缓存解决方案之一。)

tcmalloc 和 jemalloc 的原理非常相似,都是在链接时期替代标准 libc 中的 malloc 和 free,因此加载程序后就会替代原有的 malloc 和 free 进行工作,因此在不改动代码的情况下,就可以解决内存碎片的问题。

下面介绍一下 tcmalloc。

tcmalloc 就是一个内存分配器,管理堆内存,主要影响 malloc 和 free,用于降低频繁分配、释放内存造成的性能损耗,并且有效地控制内存碎片。glibc 中的内存分配器是 ptmalloc2,tcmalloc 号称要比它快。一次 malloc 和 free 操作,ptmalloc 需要 300 ns,而 tcmalloc 只要 50 ns。同时 tcmalloc 也优化了小对象的存储,需要更少的空间。tcmalloc 特别对多线程做了优化,对于小对象的分配基本上不存在锁竞争,而大对象使用了细粒度、高效的自旋锁(Spinlock)。分配给线程的本地缓存在长时间空闲的情况下会被回收,供其他线程使用,这样提高了在多线程情况下的内存利用率,不会浪费内存,而这一点 ptmalloc2 是做不到的。tcmalloc 区别地对待大、小对象。它为每个线程分配了一个线程局部的 cache,线程需要的小对象都是在其 cache 中分配的,由于是 thread local 的,所以基本上是无锁操作(在 cache 不够,需要增加内存时,会加锁)。同时,tcmalloc 维护了进程级别的 cache,所有的大对象都在这个 cache 中分配,由于多个线程的大对象的分配都从这个 cache 进行,所以必须加锁访问。在实际

的程序中,小对象分配的频率要远远高于大对象,通过这种方式(小对象无锁分配,大对象加锁分配)可以提升整体性能。

线程级别 cache 和进程级别 cache 实际上就是一个多级的空闲块列表(Free List)。一个空闲块列表以大小为 k B 倍数的空闲块进行分配,包含 n 个链表,每个链表存放大小为 n×k B 的空闲块。在 tcmalloc 中,小于等于 32 KB 的对象被称为小对象,大于 32 KB 的是大对象。在小对象中,小于等于 1024 B 的对象以 8n B 分配,大于 1025 B,小于等于 32 KB 的对象以 128n B 大小分配,例如,要分配 20 B 则返回的空闲块大小是 24 B,小于等于 B 的,这样在小于等于 1024 B 的情况下最多浪费 7 B,大于 1025 B 则浪费 127 B。而大对象是以页大小 4 KB 进行对齐的,最多会浪费 4KB-1 B。图 8 所示为一个空闲块列表的示意图。

「linux」经典面试题之服务器内存碎片

图 8  tcmalloc 空闲链表示意图

实际上,一个空闲块列表就是一个数组索引多个链表,每个链表存放相同大小的块。可以根据要分配的内存大小 size 算出合适的块在 free list 中的下标,然后找到对应的空闲块链表。

tcmalloc 的数据结构组织如图 9 所示。

「linux」经典面试题之服务器内存碎片

图 9 tcmalloc 数据组织

  1. 线程局部空闲链表:线程本地的空闲块 cache,用于分配小对象。
  2. 堆空闲链表:中心 free list,全局唯一,用于按页对齐分配大对象或者将连续的多个页(被称作 span)分割成多个小对象的空闲块分配给 thread-local free list。
  3. 页面数组:用于描述当前 tcmalloc 持有的内存状态,完成从 page number 到 span 的映射。

小对象的分配过程如下。

  1. 根据分配的 size 计算出对应的空闲块大小,从而确定对应空闲块链表,然后从 thread local 的 free list 进行分配。
  2. 如果空闲块链表非空,直接将头结点对应的空闲块返回并从空闲块链表中将其删除。
  3. 如果空闲块链表是空的,需要从 heap free list 获取一个 span。如果 heap free list 非空,则将 span 切分成多个相同大小的空闲块插入空闲块链表中,然后返回头节点。
  4. 如果 heap free list 是空的,则调用 sbrk 或者 mmap 进行内存的分配,一系列连续的内存页作为 span,然后切分成多个相同大小的空闲块插入空闲块链表,然后返回头结点。大对象的分配简单得多,直接从 heap free list 分配 4n KB 大小的空闲块即可,如果 heap free list 不存在该大小的空闲块,通过系统调用分配连续的内存页。

tcmalloc 还会对 thread local cache 进行垃圾收集,从而避免内存浪费。或者我们还可以使用一个传统的解决方案——内存池。

三、内存池

内存池的思想很简单,既然对于特定用途通用内存管理器已经无法很好地运作了,那么干脆就模仿内存管理器,直接在系统分配的一块大内存上建立我们自己的内存管理机制,并设计一套数据结构与算法来适应我们特殊的内存分配需求即可。

如果是通用内存池,我们可以模仿通用的内存管理器,通过如图 10 所示的数据结构来管理内存空间。

「linux」经典面试题之服务器内存碎片

图 10 内存分配示意图

其中,上面一块是元数据区域,用来记录我们的内存分配信息,元数据区域中最重要的是一个链表,这个链表维护了我们所使用的内存数据。分配内存时我们从内存中分出一块并加入一个表项到链表中;释放内存时,我们将内存从链表中移除。

图 10 只是一个示意图,如果只是简单地这样管理内存,依然无法解决内存碎片问题,需要对数据结构进行优化,这需要读者自行阅读相关资料。

内存池的另一个好处是我们可以为每个线程单独分配一个内存池,而不需要整个进程共用,这样在多线程的程序中,还可以避免多个线程之间同时分配内存时频繁上锁。除此之外,我们还可以在用户引用错误内存时给出更清晰、更明确的异常信息,并进行 Heap Dump,总之就是可以增强我们对内存的控制能力。

此外,如果将内存池技术和句柄技术结合,我们可以更好地解决内存碎片问题,如图 11 所示。

「linux」经典面试题之服务器内存碎片

图 11 内存池与句柄

我们将链表中的每个对象都看成一个句柄,并为这些句柄进行编号。用户不再使用直接的指针,而是使用我们包装过的句柄引用对象。这些对象里包含的是句柄的编号。当我们发现由于小块内存过多而引发内存碎片时,只需要将数据内存中的内存进行压缩(也就是将正在使用的内存重新排布到一起,将空闲的内存空间预留出来,可以看成内存的碎片整理),并修改句柄列表中句柄指向的实际地址,这样就可以一定程度上解决内存碎片问题。虽然这样会引起程序的暂时停顿,但是在不直接和用户进行 UI 交互的服务器程序中,这种小间断往往是可以接受的,尤其是那些追求高吞吐量同时又要避免内存碎片的程序非常适合使用这种模型。

评论