Erlang垃圾回收

这是Erlang的运行时Erts的内部文档,重点介绍了Erts是如何进行内存垃圾回收的

原文地址: Erlang Garbage Collector

Erlang使用追踪式垃圾回收来管理它的动态内存。更确切的说是每个进程都独立使用基于Cheney复制算法的半空间分代复制垃圾回收器,同时它们共享一个全局的对象空间(具体可参考C. J. Cheney1)。

概览

每个Erlang进行都有自己的堆栈空间,该堆栈空间分配在一个整体的内存块上,Erlang的进程堆栈向对方所在的方向增长(堆是向上增长的,栈是向下增长的)。当堆栈的地址重合了,就会触发垃圾回收操作,清理出足够的内存空间。如果没有足够多的内存,就对堆空间进行扩容。

创建数据

在进行表达式求值的过程中,会在堆上创建term。这里主要有两种类型的term无需使用堆的立即数(小整数,原子,Pid,Port的id等)以及需要分配堆空间的cons或者是装箱数(元组,大数,binary等)。立即数不需要堆空间,是因为他们被内嵌到一些数据结构中了。 让我们看看下面这个例子,该例子返回了一个包含了新数据的元组:

1
2
3
4
data(Foo) ->
   Cons = [42|Foo],
   Literal = {text, "hello world!"},
   {tag, Cons, Literal}.

在这个例子中,我们可以看到,我们用整数创建了一个cons单元以及用字符串创建了一个元组。然后我们又创建了一个有三个元素的元组,其中包含了前面的两个元素和一个名字为tag的原子,并将该元组返回。

元组会在堆上为每个元素以及元组头申请一个字的空间。一般cons单元会分配2个字。将这些东西加起来,我们的两个元组占用了7个字,cons单元占用了26个字。因为"hello world!"是一个cons单元列表,因此它占用了24个字的空间。因为原子tag和整数42是立即数并不需要额外的堆空间。因此在上面这个例子中,我们需要在堆上分配33个字的空间。

我们可以通过编译成beam的汇编(erlc -S)来看下它们到底是怎么回事:

1
2
3
4
5
6
7
8
...
{test_heap,6,1}.
{put_list,{integer,42},{x,0},{x,1}}.
{put_tuple,3,{x,0}}.
{put,{atom,tag}}.
{put,{x,1}}.
{put,{literal,{text,"hello world!"}}}.
return.

通过这段汇编代码我们可以看到3件事情:通过{test_heap,6,1}指令,我们可以知道这个函数只需要6个字的堆空间。分配内存的操作被合并为一个指令。块数据{text,"hello world!"}是一个 字面值 ,或者我们常说的常数值,并且它们并没有在函数内分配空间,因为它们是模块的一部分,在模块加载的时候就已经分配了相应的空间。

如果没有足够的空间可以满足test_heap指令所要求的字数,此时,内存垃圾回收就会被触发。内存垃圾回收会根据进程状态在test_heap指令执行时立刻触发,或者会延迟到特定时间才执行。如果垃圾回收延迟执行,任何所需的内存都会在堆内存分段中进行分配。堆内存分段,是一段额外的内存区域,稍后它将是年轻代堆的一部分,但是这并不是平时分配给term的连续内存区域。更多细节请查阅年轻堆

回收器

Erlang拥有半空间复制垃圾回收器。这代表当进行垃圾回收时,term会从一个被称为 from space 的区域,复制到另一个被称为 to space 的区域。垃圾回收器通过扫描根节点(栈,寄存器,等)。

它将从指向堆根节点的指针出发,一个字一个字的将term复制到 to space

在term的首个字被复制到 to space 后,一个迁移标记被放置在了相同的位置上,并且指向 to space 的term。任何其它的term在复制的过程中,任何指向这个被复制的term,都会看到迁移标记,并复制其所指向的地址代替当前地址。举个例子,如果我们有下面这样一段Erlang代码:

1
2
3
foo(Arg) ->
    T = {test, Arg},
    {wrapper, T, T, T}.

只会有一份T存在堆栈上,并且在垃圾回收的时候,只有第一遇到T时,才会对T进行复制。

根节点所指向的所有的term都完成复制后,垃圾回收器会扫描_目标空间_并且将他们所指向的所有的term都复制到 to space 中。当进行扫描时,垃圾回收器遍历 to space 内的term,然后将 from space 中被 to space 中所指向的term都复制到 to space 。有些term包含了非term数据(堆上binary),当垃圾回收器遍历到这些非term时,并不会进行复制,只是简单的跳过。

每个可以被我们遍历term对象都会被复制到 to space 并存放在 scan stop 地址的上方,同时我们会将 scan stop 指向最后一个对象的结尾。

scan stop 标记和 scan start 标记重合时,整个垃圾回收结束了,至此我们可以释放整个 from space 从而获得一个全新的年轻堆。

分代内存回收

除了上面描述的回收算法,Erlang垃圾回收器还提供了分代垃圾回收。它会提供一个额外的堆,称为老年堆,用来存储长时间存活的数据。最开始的堆被称为年轻堆或者也可以被称为分配堆。

当我们将这点考虑进去后,再次会看Erlang的垃圾回收器。在复制阶段,任何低于high-watermark的对象都应该复制到老年堆上而非 to space 上。

high-watermark会被放置前次垃圾回收(参考概述的内容)结束的地方,同时我们引入一个被称为老年堆的新区域。在执行正常的垃圾收集时,对于任意位于high-watermark以下的term都将会复制到老年堆上,而非年轻堆。

在下一次垃圾回收中,任何指向老年堆的指针都将被忽略并且不会被扫描。 这样垃圾回收器就不必扫描长期存在的term。

分代垃圾回收旨在以牺牲内存为代价来提高性能。 这是因为在大多数垃圾回收只考虑年轻的、较小的堆。

分代理论假设绝大部分term是在年轻代就会被释放(参考D. Ungar2),对于像Erlang这种变量不可变的语言,年轻代term被释放的概率远大于其它语言。因此,对于大多数情况,新堆中的数据在分配后会很快就被释放。这就非常具有优势了,因为它限制了复制到老年堆数据的数据量,同时提高了垃圾回收的效率。

这里需要注意的一个关键性问题,年轻堆上的任何term都可以引用老年堆上的term,但是老年堆上的term不可以引用年轻堆上的term。这是因为复制算法造成的。老年堆上term所引用的任何内容都不应该被引用树,根节点和它的后继者所包含,因此它们也不会被复制。如果不限制这种情况,这些数据会发生丢失,从而会发生巨大灾难。幸运的是,这是Erlang与生俱来的特性,因为term是不可变的,因此老年堆上的指针是不可能发生改变而指向年轻堆的。

为了从老年堆上回收空间,垃圾回收的过程中会把年轻堆和老年堆都包含在其中,并将它们复制到一个公共的 to space 。然后年轻堆和老年堆都会被作为 from space 给释放掉。这种类型的垃圾回收被称为fullsweep,当high-watermark以下的区域大小已经超过了老年堆中的未使用空间时会触发此种垃圾回收过程。它也可以通过主动调用erlang:garbage_collect()或者通过spawn_opt(fun(),{fullsweep_after, N})设置年轻代垃圾回收运行次数来触发,这里面N代表在强制执行年轻堆和老年堆的垃圾回收之前需要对年轻代垃圾回收N次。

年轻堆

年轻堆或分配堆如概述中所述的那样是由栈和堆组成的。当然,有时它也包含附加在它上面的堆分段内存。所有的堆分段内存都被认为是年轻堆中在high-watermark位置之上的部分。堆分段内存是包含了那些无法放到堆上的term或者是另一个进程创建后附加到当前堆上的。举个例子,如果调用binary_to_term/1这个BIF时,创建出一个当前堆无法存放的term,并且此时无法进行垃圾回收,那么它就将为这个term创建一个堆分段内存,并且在稍后会调度一次内存垃圾回收。此外,如果消息被发送到Erlang进程,消息的内容可能会被放到堆分段上,并且当消息被receive中的模式匹配到后这个堆分段会放到年轻堆中。

这个处理流程与Erlang/OTP 19.0的工作方式有所不同。在19.0之前,只有年轻堆和栈所在的连续内存快被认为是年轻堆的一部分。在Erlang程序去匹配堆分段和消息之前,堆分段和消息就会被复制到年轻堆中。19.0中引入的方案,在很多方面都有很多提升,最重要的是,必须的复制操作和垃圾回收器的根集合数量都得到了减少。

堆的大小

在概述中我们提到堆为了容纳更多数据是会进行扩容的。堆扩容分为2个阶段,第一阶段堆的初始值为233个字,使用斐波那契数列的变种算法。当堆有1兆字大小时,它每次只会增加20%

以下两种场景,年轻堆会进行扩容:

  1. 堆大小+消息和堆分段大小已经超过了当前堆的大小。
  2. 在fullsweep后,存活对象的总内存超过75%。

以下两种场景,年轻堆会进行收缩:

  1. 如果进行完年轻代垃圾回收后,存活对象总内存少于25%,并且年轻堆很“大”。
  2. 在fullsweep后,存活对象的总内存少于25%

老年堆的增长总是会先于年轻堆。

字面量

当内存回收堆的时候(年轻堆和老年堆),所有的字面量都不会被复制。为了判断是否会要复制相应的term,在垃圾回收时会使用下面这段伪代码进行判断:

1
2
3
4
5
if (erts_is_literal(ptr) || (on_old_heap(ptr) && !fullsweep)) {
  /* literal or non fullsweep - do not copy */
} else {
  copy(ptr);
}

erts_is_literal的行为和操作系统以及系统架构有很大关系,会因为系统和架构不同而不同。

在允许映射非保留虚拟内存区域的64位系统(除 Windows 之外的大多数操作系统)上,映射大小为1GB(默认情况下)的区域,然后所有字面量都放置在该区域内。然后为了确定某个对象是否是字面量,此处只需要进行两次指针检查。该系统依赖这样一个事实,如果一个内存页面没有被使用,那么它就不会被分配实际的内存。因此,即使映射了1GB的虚拟内存,也只会在内存中分配字面量实际使用的内存。字面量区域大小可以通过+MIscs erts_alloc选项来进行配置。

在32位的操作系统上,没有足够的虚拟内存去给字面量分配1GB的内存,因此需要按需256KB大小的字面量区域,并使用一个可以覆盖整个32位内存空间的位数组索引来保存这些字面量区域指针,从而确定一个term是否是字面量。由于总内存空间只有32位,因此索引数组只有256个字大小。在64位系统上,相同的位数组将会需要1T字的大小,因此这个技术只适用于32位系统。在数组中查找比仅使用指针比较的64位系统而言要更耗费一些时间,但是并没有额外耗费很多。

在64位Windows上,erts_alloc不能映射非保留的内存区域,所以在Erlang的term对象上使用一个特殊标记去判断一个term是否是字面量。这个操作代价非常小,但是它仅仅存在于64位的系统中,并且在将来这种标签可以进行其它的优化(例如更紧凑的列表实现),因此这项技术在那些不需要的操作系统上,并不会被使用。

该行为在Erlang/OTP 19.0之前是完全不同的。在19.0之前,字面量的检查,是通过检查指针是否指向年轻堆和老年堆中的块来完成的。如果指针并没有指向堆,那么就将其视为字面量。这导致了相当大的开销和一些奇怪的内存使用情况,因此在19.0中将这个行为删除掉了。

Binary堆

Binary堆是用来存储那些超过64字节的Binary term(现在被成为堆外Binary)的大对象空间。Binary堆使用引用计数技术,并在在进程堆上存储一个指向堆外Binary的指针。为了跟踪何时该减少对外Binary的引用计数,一个包含了函数,外部引用以及堆外Binary的链表(MSO-标记和清楚对象列表)组成了一个堆。在完成垃圾回收后,MSO列表将会被清除,任何头字节没被写入迁移标记的堆外Binary都会减少引用值并有可能被释放

MSO列表中所有项目都是按照他们被添加到进程堆中的时间进行排序的,因此在进行次要垃圾回收时,在遇到老年堆上的堆外Binary之前,MSO清理程序会一直进行清理。

虚拟Binary堆

每个进程都有一个与之关联的虚拟Binary堆,这个堆中保存了所有该进程所引用的堆外Binary的大小。虚拟Binary堆,也是有限制的,也会根据进程使用堆外Binary的情况进行扩容和收缩。Binary堆和term堆,使用相同的机制来扩容和收缩,都是先使用斐波那契数列变形算法然后用20%增加的方法。

虚拟的Binary堆存在是为了当有非常大的堆外Binary可能会被回收的情况下,尽早的触发垃圾回收。该方案并不能解决所有Binary内存不能及时释放的问题,但是它可以解决绝大部分这种情况。

消息

消息可以在特定的时间成为进程堆的一部分。这取决进程配置的方式,我们可以使用process_flag(message_queue_data, off_heap | on_heap)来设置进程处理消息的行为,或者我们可以使用+hmqd为所有的进程设置一个默认的选项。

这些不同的配置有什么作用,我们什么时候应该使用它们? 让我们先看看当一个Erlang进程向另一个进程发送消息时会发生什么。 发送过程需要做几件事:

  1. 计算发送的消息体大小
  2. 为整个消息分配空间
  3. 复制消息
  4. 为消息分配一个带有元信息的容器
  5. 将消息容器插入接收者的消息队列

接收进程的message_queue_data参数,可以控制步骤2中发送进程分配消息的策略以及垃圾回收该如何处理消息数据。

上述过程与OTP 19.0之前的工作方式不同。 在19.0之前没有配置项,其行为总是与19.0中的on_heap选项非常相似。

消息分配策略

如果设置了on_heap,发送进程将首先尝试直接在接收进程的年轻堆上为消息分配空间。但是这并总是可行的,因为它需要先获取接收进程的_主进程锁_。当进程在执行的时候,主进程锁是被锁住的,因此,在高度协作的系统中很可能发生锁冲突。 如果发送进程无法获取主进程锁,就会创建出一个堆分段,并将消息复制到上面。如果使用off_heap,发送进程永远都是创建堆分段并复制消息到上面。

在我们选择一个则略时,我们需要权衡很多事情。

使用off_heap似乎可以获得更具扩展性的系统,因为对主进程锁的争夺会少一些。但是,分配堆分段要比直接在接收进程堆中的分配空间耗费更多。因此,如果发生锁争用的可能性很小的时候,则应该尝试直接在接收进程的堆上分配空间。

使用on_heap会强制所有消息成为年轻堆的一部分,这将增加垃圾回收器必须移动数据的数据量。所以如果在处理大量消息时触发垃圾回收,这些消息将被复制到年轻堆。 这反过来将导致消息迅速的被提升到了老年堆中,从而增加其大小。这需要取决具体进程是做什么的,才能说这种情况是好还是坏。一个非常大的老年堆意味着年轻堆也会很大,这反过会减少处理消息队列时触发垃圾回收的次数。这将以更多内存为代价,短暂的换来进程吞吐量的增加。但是,在所有的消息都被消费后,进程进入一个只少量消息的状态时。这个进程可能需要很长时间才会进行fullsweep,并且很多消息会一直保存在老年堆上,直到fullsweep发生才会被清理掉。虽然on_heap可能比其它模式更快,但它会占用更多的内存和更长时间占用这些内存。这种模式是遗留的模式,我们可以认为19.0之前的消息处理方式都是这样的。

这些策略中的哪一个最好取决于Erlang进程正在做什么以及它如何与其它进程交互。 因此,一如既往,我们需要对应用程序进行概要分析并查看它在不同选项下的表现。

参考

1 C. J. Cheney. A nonrecursive list compacting algorithm. Commun. ACM, 13(11):677–678, Nov. 1970. & Cheney’s algorithm

2 D. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. SIGSOFT Softw. Eng. Notes, 9(3):157–167, Apr. 1984. & 论文

译注

之前分析过OTP 17.0的代码,RabbitMQ的代码,其中对RabbitMQ为什么需要进行手动GC很不理解。但是这个文章已经充分的解答了我的一些疑惑,并且从这个文章中可以看出,OTP 19.0之后,内存的分配策略更加多样性,并且进行了很多优化。

无论何时,时间空间都是一对矛盾体。Erlang的变量不可变性质,导致了Erlang需要很多内存复制和内存占用。但是带来的好处是在很多语言中很难实现的并发垃圾回收,在Erlang中可以轻而易举的实现,在很多语言中不可避免的Stop Word,在Erlang中几乎不会存在。同时Erlang也在不断的改进其内存回收的执行效率,降低消息和Binary等被多次复制的可能性。正是Erlang团队在每个小细节上不断进行优化,才不断提高了Erlang/OTP平台的消息吞吐量。

个人认为理解Erlang的垃圾回收优化,会有助于我们对RabbitMQ,EMQx和ejabberd的优化,以及提高我们自己的Erlang编程水平。