Netty源码分析——伙伴分配算法

Netty源码分析——伙伴分配算法

前言

今天跟大家一起来看一下伙伴分配算法。这个算法在Netty中用于在PoolChunk中分配内存。而这个算法的有点主要是可以使分配的内存尽可能的连续,不会产生内存碎片。今天来看下这个算法的实现。

基本概念

我研究伙伴分配算法的时候,在网上也看了一些文章,普遍都存在一个问题就是把算法和内存直接挂钩,看上去都是多少多少字节,多少多少KB,很容易把人搞晕。分析算法主要还是让人能看懂,所以我们就分苹果好了,图中用A替代。

首先我们要明确一下伙伴分配算法的基本概念,或者说基本玩法:

  1. 伙伴分配算法只能管理2的指数个苹果的分配,比如2、4、8、16等等。
  2. 索要内存也必须是2的指数,比如索要2个苹果,4个苹果。如果不是2的指数,我们要向上取到2的指数个,比如我要3个苹果,那么分配器会尝试分配给你4个苹果。

实现

现在看一下实现,我们就假设我们要管理4个苹果,这时候我们需要几个人呢?需要7个人(2 * 4 -1)个人来管理这四个苹果。为什么需要这么多人呢,因为我们办事效率低下并且官僚主义。。。开玩笑。这个就是能让整个内存连续被分配的关键所在,因为要实现细粒度的控制,必然要带来一些开销(分苹果的例子中就是要花更多的人来管理苹果):

苹果分配图

如上图所示,四个A相当于四块内存连续。上面的人相当于管理苹果的七个人。越上层的人管理越多的苹果,但是最底层的人才直接掌握着苹果。那么最上层的人掌握的是四个苹果,我们可以理解为他没有真正管理四个苹果,只是管理着两个掌握了两个苹果的人(第二层)。真正的苹果还是在最下面的四个人手里。

我们现在来看看分苹果的实现方式。分几种方式看分配流程:

  1. 第一次要一个苹果,第二次要两个苹果,第三次要一个。
  2. 第一次要一个苹果,第二次要三个苹果(第二次会分配失败)。

分配流程

我们的分配方式是优先左则,就是先从左边开始分配。第一次要一个苹果,要的苹果数量合理(1 = 2的0次方),最上层的人接到通知,按照左则优先规则,先看看自己现在持有四个苹果,能满足1个的要求,那么再看看自己管理的两个人,左边的人有两个,则告知他需要一个苹果。

第二层左边的人接到通知需要一个苹果,而自己现在管理两个苹果,符合要求,那么看看自己管理的两个人,左边那个人有1个苹果,则把苹果交付给客人。目前A1被分配。

这个时候,我们要回过来更新各个人维护的苹果数了,持有A1的那个人当然变成0了,第二层左边的人理所应当变成1了(只剩A2苹果的持有者了,A1被分配出去了)。那么第一层的人这时候管理几个苹果?

可能很多人说,3啊!很明显,1+2。不对!这时候第一层的人持有的苹果是2!图应该是这个样子:

苹果分配图-1

A1已经被分配了,所以给一个别的颜色。

为什么第一层变2不是3,我们继续分就知道了。这时候按照要求要分配两个苹果。这时候第一个人看看,自己管理两个,可以分配,然后看看自己管理的两个人,第一个人只有一个不够了,第二个还有两个,可以分配,所以让第二层右边的人提供两个苹果。第二层右边的人发现自己正好有两个苹果可以分配,但是自己的小弟们都没有两个苹果(每人一个),这说明此时要把自己管理的所有苹果都拿出来才行了,这时候就把自己的两个苹果都拿出来了(A3和A4)。

我们此时发现问题了,为什么此时第一层的人管理的是2而不是3。因为此时他最多一次性拿出2个苹果。那么我们如果想要3个苹果呢(第二次要三个)?会失败。因为我们说过游戏规则,不到2的指数倍的,要被向上取整到2的整数倍,3线上取整就是4,而此时无论如何也没法提供4个苹果了(A1没了)。

这就是为什么,上层节点维护的不是子节点的和,而是左右节点中大的那个。我们说回到第二次需要两个苹果的情况,分配完之后应该是这样的:

苹果分配图-2

回收

用完内存我们需要释放,用完苹果我们需要还。注意这里不能随便换的,我们按照借一个,再借两个来,就得按照还两个和还一个来(顺序无所谓),但是不能还一个,还一个,再还一个这种方式。这是为了我们方便管理。

假设我们先还两个。先跟第一层的人说,我要还两个苹果。这时候就需要算数了,第一层的人一看,哦对,我能管理4个苹果,现在只有1个,还我两个是正常的。然后看看左边的人,左边的人最多管理两个,而他现在已经有了一个,那不行,这两个不能给他,再看看右边的人,他能管理两个,现在管理0个,正好填上两个,给他就好了。

后记+实现

真正实现当然要复杂一些,我只是希望用这种方式来告诉大家算法的原理,有了原理可能有些小伙伴已经可以写出实现了。真正实现中,其实我是使用了一个数组来实现节点管理的,为了直观,这里也给个图:

分配器实现图

我把数组竖着放,就是这个样子,左边的数字是数组下标,颜色对应着每一层的颜色,每个数字就表示管理的苹果数。具体的实现我放在我的github上,有兴趣的同学可以看一下。这里借鉴的wuwenbin的极简实现方式。