基于时间的定制分配器

2018-11-17

根据业务特点定制的分配器,绝对是最高效的实现之一。比如说,发送网络消息包需要拼凑很多对象来生成包,发送完成后,消息包的那块内存就不再使用了。于是,这里可以申请一块内存反复使用。相比于每次申请释放内存,无论下层的内存管理如何实现,是不可能抵得上重用来得高效的。比如说,业务本身是无锁的,特定实现相比通用的实现就简单的多。

通用的分配器则难以利用到业务特点。通用实现一般是基于地址做回收的,广义概念的回收,不管是 GC 还是 free 的回收。基于地址回收就涉及原内存里面挖了洞,于是要考虑有各式各样大小的对象池子去优化,要考虑回收的时候对象合并,考虑匹配大小的对象,还有内部碎片外部碎片这些。于是有了 freelist,buddy 算法,bitmap 等等很多东西。

我们有一个业务场景,内存分配比较有特点。对象不停的分配,分配出来之后,会存活一段时间,再之后,就很少被使用了。不同于网络消息那种一次的交互的简单例子,它是一段时间内的存在较多交互,存活一段时间。另外一点,在整个存活时间内,内存使用量比较大,小对象特别的多,会对 GC 那边扫描造成非常大的压力。主要还是想优化小对象数量,于是,我设计了一个基于时间的定制分配器。

接口的设计上面,只暴露两个函数:

func alloc(size int) ([]byte, int)
func gc(safeTS int)

注意 alloc 函数的返回值,除了分配的内存本身,它还额外返回了一个 timestamp。这就是这个对象的分配时间(概念上的时间,只是一个单调递增的数字而已)。

然后是 gc 函数,它会回收掉所有在 safeTS 时间之前的对象。

业务使用的时候,必须自己去处理还在使用中的对象,比如说重新分配一下,刷新一下时间,有点像 lease 的续租。然后业务自己去调用 gc 将旧的对象全部释放掉。分配和释放都是由业务自已来控制的。

业务怎么知道哪些对象还会被使用呢? 可以把对象的创建时间存到对象里面。调用 gc 之前,用来跟 safeTS 去比较。如果对象创建时间小于 safeTS,并且它还需要继续被使用,那么就需要重新为它分配,然后让使用者更新对它的引用。被使用者引用在有些业务场景是不知道的,于是就不能这么干了,这是一个限制。当然我们的场景是可以的。

然后实现细节。有一些内存块,比如说每块 1M(随便拍脑袋定的)。分配时从当前内存块里面加划出内存。

回收时,整块内存做回收。每次操作时间会加加。每个内存块上面,会记录一个 minTS。注意有个约束条件,所有在这块内存里面划出去的对象,它们对应的创建时间都是大于 minTS 的。

block1(minTS=0) obj(ts=1) obj(ts=2) ... obj(ts=29) ->
block2(minTS=30) obj(ts=31) obj(ts=32) ... ->
block3(minTS=77) ... ->

整个过程没有删除操作,直到开始回收。把整个旧的大块内存直接删除。假设我们要回收到 safeTS = 44,那么直接删除掉 block1 就好了,因为所有 block1 上面的对象的时间肯定是处于 [1, 30) 的,小于 safeTS。

不像 GC 做标记清扫,这个算法不会根据对象地址去标记,清扫也不用重新整理内存,非常高效。假设对象过了一定时间后都是不再使用的。业务自己要去处理将活着的对象挪走。

大半夜写博客写代码,感觉头脑都不太清醒了...

allocator