使用jemalloc在围棋中进行手动内存管理

Dgraph Labs自2015年成立以来一直是围棋语言的用户。五年来，我们用了20万行围棋代码，我们很高兴地告诉大家，我们仍然坚信围棋是正确的选择，无论是现在还是现在，我们都坚信围棋是正确的选择。我们对围棋的兴奋已经超越了构建系统，甚至让我们用围棋编写了脚本，这些脚本通常是用Bash或Python编写的。我们发现，使用Go帮助我们构建了一个干净、可读、可维护的代码库--最重要的是--高效和并发。

然而，有一个领域是我们从早期就开始关注的：内存管理。我们并不反对Go垃圾收集器，但虽然它为开发人员提供了便利，但它也有与其他内存垃圾收集器相同的问题：它根本无法与手动内存管理的效率竞争。

当您手动管理内存时，内存使用率更低、更可预测，并且允许内存分配突发不会导致内存使用量的疯狂峰值。对于使用Go Memory的Dgraph来说，所有这些都是一个问题1。事实上，Dgraph内存不足是我们从用户那里听到的一种非常常见的抱怨。

像Rust这样的语言已经取得了一定的进展，部分原因是它允许安全的内存管理。我们完全可以理解这一点。

根据我们的经验，手动分配内存并追踪潜在的内存泄漏比尝试在具有垃圾收集的语言中优化内存使用要少2。在构建能够几乎无限伸缩的数据库系统时，手动内存管理是非常值得的。

我们对围棋的热爱和避免围棋GC的需要让我们找到了在围棋中进行动态内存管理的新方法。当然，大多数围棋用户永远不需要域内存管理；除非您需要，否则我们建议您不要这样做。当你真的需要它的时候，你会知道的。

在这篇文章中，我将分享我们在Dgraph实验室从手动内存管理的实践中学到的东西，并解释我们是如何在围棋中手动管理内存的。

灵感来自CGO wiki中关于将C数组转换为Goslices的部分。我们可以使用Malloc在C中分配内存，并使用unSafe将其传递给Go，而不会受到Go GC的任何干扰。

导入"；C&34；导入"；不安全...。28]C.YourType)(unsafe.Pointer(theCArray))[：length:length]阵列*C.YourType=C.getTheArray()长度：=C.getTheArrayLength()切片：=(*[1；<；<；var。

注意：当前的实现有一个错误。虽然允许GO代码将NIL或C指针(但不是GO指针)写入C内存，但如果C内存的内容显示为GO指针，则当前实现有时可能会导致运行时错误。因此，如果GO代码要在其中存储指针值，请避免将未初始化的C内存传递给GO代码。将C中的内存清零，然后将其传递给Go。

因此，我们没有使用Malloc，而是使用其价格稍高的同类产品calloc。Calloc的工作方式与malloc相同，不同之处在于它在将内存返回给调用者之前将内存清零。

我们一开始只实现了基本的Calloc和Free函数，它们通过CGO为Go分配和取消分配字节片。为了测试这些功能，我们开发并运行了一个持续的内存使用测试。这个测试无休止地重复了一个分配/释放周期，在这个周期中，它首先分配各种随机大小的内存块，直到分配了16 GB的内存，然后释放这些内存块，直到只剩下1 GB的内存分配。

此程序的C等效项的行为符合预期。我们会看到HTOP中的RSS内存增加到16 GB，然后下降到1 GB，然后又增加到16 GB，以此类推。然而，使用Calloc和Free的围棋程序在每个周期之后会逐渐使用更多的内存(见下图)。

我们将此行为归因于默认的C.calloc调用中缺乏线程感知导致的内存碎片。在得到Go#黑暗艺术松弛频道的一些帮助后(特别感谢凯尔·布兰肯希普)，我们决定尝试一下Jemalloc。

Jemalloc是一个通用的Malloc(3)实现，它强调避免碎片和可伸缩的并发支持。Jemalloc在2005年作为FreeBSD libc分配器首次投入使用，从那时起，它就被大量依赖于其可预测行为的应用程序所取代。--http://jemalloc.net。

我们将API转换为使用jemalloc 3进行calloc和free调用。它的执行非常出色：jemalloc本身就支持线程，几乎没有内存碎片。我们的内存使用监控测试中的分配-释放周期在预期限制之间循环，忽略了运行测试所需的混乱。

为了确保我们使用的是jemalloc并避免名称冲突，我们在安装过程中添加了je_prefix，所以我们的API现在调用的是je_calloc和je_free，而不是calloc和free。

在上面的图表中，通过C.calloc分配围棋内存会导致大量内存碎片，导致程序在第11个周期占用20GBs的内存。与jemalloc相同的代码没有明显的碎片，每个周期都会减少近1 GB。

在程序末尾(最右边的小点)，在释放所有分配的内存后，C.calloc程序仍然占用不到20 GB的内存，而jemalloc显示400MB的内存使用量。

Ptr：=C.je_calloc(C.size_t(N)，1)如果ptr==nil{//NB：抛出类似于死机，除非它保证进程将被//终止。下面的调用正是Go运行时在//无法分配内存时调用的。抛出("；out out Memory"；)}uptr：=unSafe.Pointer(PTR)atom ic.AddInt64(&；numBytes，int64(N))//将C指针解释为指向GO数组的指针，然后切片。返回(*[MaxArrayLen]字节)(Uptr)[：n：n]。

我们将此代码作为Ristretto的z包的一部分，因此Dgraph和Badger都可以使用它。为了允许我们的代码切换到使用jemalloc来分配字节片，我们添加了一个构建标记jemalloc。为了进一步简化我们的部署，我们通过设置正确的LDFLAGS，将jemalloc库静态链接到任何生成的GO二进制文件中。

既然我们已经有了分配和释放字节片的方法，下一步就是使用它来布局GO结构。我们可以从一个基本的(完整代码)开始。

Type node struct{val int next*node}var nodeSz=int(unSafe.Sizeof(node{}))func newNode(Val Int)*node{b：=z.Calloc(NodeSz)n：=(*node)(unSafe.Pointer(&；b[0]))n.val=val return n}func FreeNode(n*node){buf：=(*[z.MaxArrayLen]byte)(unsafe.Pointer(n))[：nodeSz:nodeSz]z.Free(Buf)}。

在上面的代码中，我们使用newNode在C分配的内存上布置了一个go结构，并创建了相应的freNode函数，一旦使用完该结构，就可以释放内存。GO结构的基本数据类型是int和指向下一个节点结构的指针，所有这些都是在程序中设置和访问的。我们分配了2M个节点对象，并创建了一个链表来演示jemalloc的正确功能。

对于默认的go内存，我们看到有31MiB的堆被分配给具有2M个对象的链表，但没有通过jemalloc进行分配。

$GO运行。分配的内存：0对象：2000001节点：0...释放后节点：200000。分配的内存：0Heapalc：31 MiB。

使用jemalloc构建标记，我们看到通过jemalloc分配了30MiB的内存，在释放链表之后，这个内存降到了零。Go堆分配只有很小的399 KiB，这可能来自运行程序的开销。

$go run-tag=jemalloc。已分配内存：30 MiB对象：2000001节点：0...节点：200000释放后。分配的内存：0Heapalc：399 KiB。

上面的代码可以很好地避免通过GO分配内存。但是，这也是要付出代价的：较低的性能。用时间运行这两个实例，我们看到在没有jemalloc的情况下，程序运行时间为1.15s。使用jemalloc时，它的运行速度慢了约5倍，为5.29s。

$时间去奔跑，去奔跑。1.15s用户0.25s系统162%cpu 0.861总计$time go run-tag=jemalloc.go run-tag=jemalloc。5.29s用户0.36s系统108%cpu总计5.200。

我们将性能降低归因于每次分配内存时都会进行CGO调用，而且每次CGO调用都会带来一些开销。为了解决这个问题，我们在ristretto/z包中编写了一个分配器库。这个库在一次调用中分配更大的内存块，然后这些内存块可以用来分配许多小对象，从而避免昂贵的CGO调用。

分配器从一个缓冲区开始，当耗尽时，它会创建一个两倍大小的新缓冲区。它维护所有已分配缓冲区的内部列表。最后，当用户处理完数据后，他们可以调用Release来一次性释放所有这些缓冲区。注意，Allocator不做任何内存移动，这有助于确保我们拥有的任何结构指针保持有效。

虽然这看起来有点像tcmalloc/jemalloc使用的板式内存管理，但它要简单得多。一旦分配，就不能只释放一个结构。您只能释放分配器4使用的所有内存。

Allocator做得很好的是以较低的成本布局数百万个结构，并在完成后释放它们，而不涉及Go堆。上面显示的相同程序，当使用新的分配器构建标记运行时，运行速度甚至比Go Memory版本更快。

$time go run-tag="；jemalloc，allocator"；.go run-tag="；jemalloc，allocator"；。1.09s用户0.29s系统143%cpu总计0.956。

从GO 1.14开始，-race标志打开对structs的内存对齐检查。Allocator有一个AllocateAligned方法，该方法返回内存，从右指针对齐开始，以通过这些检查。根据结构的大小，这可能会导致一些内存浪费，但会因为正确的字边界而使CPU指令更有效率。

我们还面临着另一个内存管理问题：有时内存分配发生在与释放非常不同的地方。这两个位置之间唯一的通信可能是分配的结构，它们无法向下传递实际的Allocator对象。为了解决这个问题，我们为每个分配器对象分配了一个唯一的ID，这些对象将其存储在uint64引用中。每个新的分配器对象都存储在针对其引用的全局映射上。然后，可以使用该引用重新调用分配器对象，并在不再需要数据时将其释放。

如上所述，当手动分配结构时，重要的是要确保结构中没有对Go分配的内存的引用。考虑对上面的结构进行轻微修改：

让我们使用上面定义的根：=newNode(Val)函数来按需分配一个。但是，如果我们随后设置root.next=&；node{val：val}，它通过Go Memory来分配链表中的所有其他节点，我们必然会得到以下分段错误：

$GO RUN-RACE-TAG="；jemalloc"；。已分配内存：16 B对象：2000001意外故障地址0x1cccb0致命错误：故障[信号SIGSEGV：分段冲突代码=0x1 Addr=0x1cccb0 PC=0x55a48b]

GO分配的内存会被垃圾回收，因为没有有效的GO结构指向它。只有C分配的内存在引用它，而Go堆没有任何对它的引用，这导致了上面的错误。因此，如果您创建一个结构并手动为其分配内存，重要的是要确保所有递归可访问的字段也都是手动分配的。

例如，如果上面的结构使用一个字节片，我们也使用Allocator来分配该字节片，以避免将GO内存和C内存混为一谈。

分配器非常适合手动分配数百万个结构。然而，我们有需要创建数十亿个小对象并对它们进行排序的用例。在围棋中做到这一点的方法，即使是使用Allocator，看起来也是这样的：

Var Nodes[]*nodefor i：=0；i<；1e9；i++{b：=allocator.AllocateAligned(NodeSz)n：=(*node)(unSafe.Pointer(&；b[0]))n.val=rand.Int63()Nodes=append(Nodes，n)}排序。Slice(Nodes，func(i，j int)bool{Return Nodes[i].val<；Nodes。

所有这些1B节点都是在分配器上手动分配的，这会很昂贵。我们还需要支付Go中的切片成本，8 GB的内存(每个节点指针8字节，1B条目)本身就相当昂贵。

为了处理这类用例，我们构建了z.Buffer，它可以被内存映射到一个文件上，从而允许Linux根据系统的需要调入和调出内存。它实现了io.Writer，取代了我们对bytes.Buffer的依赖。

更重要的是，z.Buffer提供了一种分配较小数据片的新方法。通过调用SliceALLOCATE(N)，z.Buffer将写入要分配的片的长度(N)，然后分配片。这使得z.Buffer能够理解切片边界，并使用SliceIterate正确地迭代它们。

对于排序，我们最初尝试从z.Buffer获取切片偏移量，访问要比较的切片，但只对偏移量进行排序。在给定偏移量的情况下，z.Buffer可以读取偏移量，找到切片的长度并返回该切片。因此，该系统允许我们按排序顺序访问切片，而不会引起任何内存移动。虽然很新奇，但这种机制给内存带来了很大的压力，因为我们仍然在支付8 GB的内存损失，只是为了把这些补偿放入Go内存中。

我们有一个关键的限制，那就是切片的大小不一样。此外，我们只能按顺序访问这些切片，而不能以逆序或随机顺序访问这些切片，而不能提前计算和存储偏移量。大多数就地排序算法都假设值的大小相同为5，可以随机访问，并且可以很容易地交换。去吧。Slice的工作方式是一样的，因此不太适合Z.Buffer。

有了这些限制，我们发现合并排序算法最适合这项工作。使用合并排序，我们可以按顺序对缓冲区进行操作，在缓冲区大小上只需要额外一半的内存命中率。事实证明，这不仅比将偏移量引入内存更便宜，而且在内存使用开销方面也更可预测(大约是缓冲区大小的一半)。更好的是，运行合并排序所需的开销本身就是内存映射的。

合并排序还有一个非常积极的效果。使用基于偏移量的排序，我们不得不在迭代和处理缓冲区时将偏移量保留在内存中，这给内存带来了更大的压力。使用合并排序，所需的额外内存在迭代开始时被释放，这意味着有更多的内存可用于缓冲处理。

Z.Buffer还支持通过Calloc分配内存，一旦内存超过用户指定的限制，就会自动进行内存映射。这使得它在各种大小的数据上都能很好地工作。

Buffer：=z.NewBuffer(256；<；20)//通过Calloc.Buffer.AutoMmapAfter(1<；<；30)从256MB开始//它变成1GB后自动映射。对于i：=0；i<；1e9；i++{b：=Buffer.SliceAllocate(NodeSz)n：=(*node)(unSafe.Point(&；B[0])n.val=rand.Int63()}Buffer.SortSlice(func(Left，Right[]byte)bool{nl：=(*node)(unSafe.Pointer(&；Left[0]))nr：=(*node)(&；right[0])return nl.val<；nr.val})//按val.Buffer.Slicer.Slice.Node递增顺序遍历节点。B[0]))_=n.val返回值为空})。

如果不涉及内存泄漏，所有这些讨论都将是不完整的。现在我们使用的是手动内存分配，在我们忘记释放内存的情况下，必然会有内存泄漏。我们怎么才能抓住它们呢？

我们之前做的一件简单的事情是让原子计数器跟踪通过这些调用分配的字节数，这样我们就可以通过z.NumAllocBytes()快速知道我们在程序中手动分配了多少内存。如果在内存测试结束时仍有剩余内存，则表明存在泄漏。

当我们确实发现了一个漏洞时，我们最初尝试使用jemalloc内存分析器。但是，我们很快意识到这并没有什么用处。由于CGO边界的原因，它看不到整个recall堆栈。分析器看到的所有内容都是来自相同z.Calloc和z.Free调用的分配和释放。

多亏了Go运行时，我们能够快速构建一个简单的系统来将调用者捕获到z.Calloc中，并将它们与z.Free调用进行匹配。这个系统需要互斥锁，所以我们选择默认不启用它。相反，我们使用泄漏构建标志来打开开发人员构建的泄漏调试消息。这会自动检测泄漏，并打印出发生泄漏的位置。

//如果启用了泄漏检测。pc，_，l，ok：=runtime.Caller(1)if ok{dallocsMu.Lock()dallocs[uptr]=&；dalloc{pc：pc，no：l，sz：n，}dallocsMu.Unlock()}//诱导泄漏以演示泄漏捕获。第一个数字显示//分配的大小，后跟函数和//进行分配的行号。$go test-v-tag="；jemalloc leak"；-run=TestCalloc...leak：128 at func：github.com/dgraph-io/ristretto/z.TestCalloc 91。

使用这些技术，我们两全其美：我们可以在关键的、内存受限的代码路径中进行手动内存分配。同时，我们还可以在非关键代码路径中获得自动垃圾回收的好处。即使你不习惯使用CGO或jemalloc，你也可以将这些技术应用到更大的围棋内存上，产生类似的效果。

上面提到的所有库都在Ristretto/z包中的Apache2.0许可下可用。MemTest和演示代码位于Conrib文件夹中。

獾和Dgraph(特别是獾)都已经从使用这些库中获益良多。我们现在可以使用有限的内存来处理TB级的数据--这符合您对C++程序的期望。我们正在进一步找出围棋记忆面临压力的领域，并在有意义的地方切换到手动记忆管理来缓解压力。

Dgraph v20.11(T'；Challa)版本将是第一个包含所有内存管理功能的版本。我们的目标是确保Dgraph永远不需要超过32 GB的物理RAM来运行任何类型的工作负载。使用z.Calloc、z.Free、z.Allocator和z.Buffer可以帮助我们通过Go实现这一目标。

多年来，我们在GO中尝试了所有的交易技巧。使用sync.Pool，维护我们自己的自由列表，尽可能避免堆上的分配，使用缓冲区区域等等。↩︎。

当您获得使用手动内存管理的语言编写代码的经验时，您就会注意到分配和释放。此外，性能分析工具还可以进一步帮助您确定内存泄漏，以便从代码库中消除内存泄漏。这与在Go中编写代码时获得眼向并发模式没有什么不同。在外人看来，并发和手动内存管理都特别困难，但对于经常致力于这两种语言的开发人员来说，它们只是游戏的一部分。↩︎

事实上，由于需要互斥锁，在allocator中管理自由职业者的一些实验被证明比仅仅使用Calloc和Free要慢。↩︎。

可变长度字符串的片段var buf[]字符串的大小仍然是固定的，这取决于对片段的感知。Buf[i]和buf[j]占用的内存量完全相同，因为它们都是指向字符串的指针，并且可以在buf内随时交换。这里的情况并非如此，字节片被放置在一个大得多的字节缓冲区上。↩︎