MycatBigMemory仿造Netty中PooledDirectByteBuf的内存池管理策略,并对大于Chunk Size的内存请求管理进行扩充,以支持对BigMemory的管理。 **与https://github.com/orgs/MyCATApache的关系**:本repository作为MycatBigMemory实现的候选者之一,供开发人员交流。
[TOC]
##内存分配策略 针对小于ChunkSize(默认8K*2048)的内存请求,MycatBigMemory的内存分配策略与Netty一致,将用户的内存请求值转换成相应的normCapacity:
- tiny:将小于512字节的内存请求值对应到区间[16,512)内,即内存分配最小为16,不满足则每次增加16,直到512,一共有32个不同normCapacity值(16,32,48,64,80,.... , 496)。
- small:用于分配大于等于512字节但是小于pageSize的内存,内存分配最小为512,不满足则每次*2,一共有4个不同normCapacity值(512, 1024, 2048, 4096)。
- large:用于分配大于等于pageSize但是小于chunkSize的内存,normCapacity值最小为8K,不满足则以2倍进行扩充,一直到chunkSize边界。
- huge:用于分配大于等于chunkSize的内存,当内存请求值小于等于1/2ArenaSize,则采用chunk[]+memoryIdx方式记录占用的内存,除chunk[length-1]之外,都是被整块占用的chunk,而chunk[length-1]对应占用了一部分的memoryIdx值。
- superHuge:当内存请求值大于1/2ArenaSize,则直接另外分配堆外内存,不占用Arena内的空间, 但是Arena会负责对其进行回收和swap。
###Subpage 管理策略等同于io.netty.buffer.PoolSubpage,本段可以认为是对PoolSubpage的解析。
####内部元素
-
pageSize:Subpage的字节长度,大小为$2^n$,默认为8K
-
elemSize,maxNumElems:为了更好的利用Subpage内的空间,将等分为更小的内存段,每小段的长度就是elemSize。因此maxNumElems = pageSize / elemSize |elem|elem|elem|...|...|elem|elem| | :-------- | --------:| :--: |
-
long[] bitmap:使用bit来记录Subpage内每个element内存段的占用情况。一个long可以描述$2^6$即64个内存段,因此bitmap初始化如下
bitmapLength = maxNumElems >>> 6
for (int i = 0; i < bitmapLength; i ++) {
bitmap[i] = 0;
}
- prev, next:使用双向链表来关联相同elemSize的Subpage。
- chunk, memoryMapIdx, runOffset:分别标识该SubPage所属的Chunk,以及在该Chunk中的memoryMapIdx(Chunk章节中会有详细描述),和Chunk实际内存地址上的(chunk.memory)的偏移量 ####bitmap的分配方式
private int findNextAvail()
{
final long[] bitmap = this.bitmap;
final int bitmapLength = this.bitmapLength;
for (int i = 0; i < bitmapLength; i ++) {
long bits = bitmap[i];
if (~bits != 0) {
//该bits中有空闲位
//从左向右遍历bits,找到为0的空闲位,返回格式为: i<<64|空闲位bit值
return findNextAvail0(i, bits);
}
}
return -1;
}
###Chunk 管理策略等同于io.netty.buffer.PoolChunk,本段可以认为是对PoolChunk的解析。 ####基本描述
- 一个page是chunk能够分配的最小内存单位。
- chunk是pages的集合。
- chunkSize = 2^{maxOrder} * pageSize
- chunk是有实际物理内存分配的,并且在初始化时候已经分配好,堆外就是使用UNSAFE.allocateMemory(chunkSize)
####byte[] memoryMap
-
使用一个存放在byte数组中的平衡二叉树来标识chunk内的内存占用情况,并且此二叉树可以用来定位查找以及判断chunk是否能够满足需要申请的内存大小。
depth0 node1 / \ depth1 node2 node3 / \ / \ depth2 node4 node5 node6 node7 ...... ...... ...... ...... ...... ...... / depth9 node512 / \ depth10 node1024 node1025 / \ / \ depth11 node2048 node2049 node2050 node2051 .... node4195
-
depth=maxOrder是树的叶节点,用于对应pages,如图depth11(maxOrder默认为11)可以记录2048个page 即$chunkSize/2^{maxOrder} = pageSize$
-
当需要申请分配一个chunkSize/2^k大小的内存段,只需要在depth_k从左向右寻找第一个可用的节点。例如k=1,则分配1/2*chunkSize,立此类推。
-
memoryMap[node_id] = x ,
- x = depth_of_node_id => memoryMap初始化值或未分配时
- x > depth_of_node_id => 至少该节点下的一个子节点已经被分配了,所以不能在本节点上分配对应大小的内存段,需要向右继续寻找合适的同级兄弟节点进行分配,但是不妨碍该节点下的字节点响应对应大小的内存分配请求。 例如:node2048(8k)上已被分配,node2049~node4195未被分配, 则node1024无法响应16k的分配请求,需要在node1025上分配,但是node1024上仍可以响应8k的分配请求。
- x = maxOrder + 1 => 这个节点和其下字节点都已经被分配完毕。
####分配算法
- allocateNode(d) => 在高度h上从左向右查找第一个可用的节点
- 从 depth = 0 (node_id = 1)开始遍历 如果memoryMap[ 1 ]>d, 则说明整个chunk都无法分配。 如果memoryMap[node_id] < d, 则说明d不在此层,通过 node_id <<= 1 向下一层寻找。
- 如果memoryMap[node_id] > depth_of_node_id,参照定义, 本节点无法满足分配要求, 需要在同级兄弟节点上继续查找。
- 如果memoryMap[node_id] <= h,则子节点或者本级叶节点可以找到可分配的节点。 4)节点node_id分配完成后, 需要将memoryMap[node_id] 设置为 maxOrder + 1,同时递归更新父节点。 5)父节点更新方法为将memoryMap[parent_node_id]设置成左右子节点中值最小的那个。
- allocateRun(size)=> 用于分配>=pageSize的内存请求,size已经是经过处理的normCapacity,可以保证(详见后续“内存分配策略”中的描述)是pageSize的$2^n$倍。
- Compute d =
$log_2(chunkSize/size)$ - Return allocateNode(d)
- allocateSubpage(size) => 用于分配<pageSize的内存请求,size已经是经过处理的normCapacity
- 使用allocateNode(maxOrder)找出一个未使用的叶子节点。
- 根据normCapacity构造和初始化Subpage对象实例,并放入内部属性PoolSubpage[] subpages中,对应的叶子节点的node_id即是其下标值,便于后续方便查找。
###PoolChunkList PoolChunkList维护了两个链表,一个是PoolChunkList之间的链表,一个是PoolChunkList内部PoolChunk的链表。
- PoolChunkList之间的链表:根据minUsage和maxUsage定义的使用量进行划分为qInit,q000,q025,q050,q075, q100六个不同的区间,内存分配优先级为q050=>q025=>q000=>qInit=>q075。两个相邻的chunkList,前一个的maxUsage和后一个的minUsage必须有一段交叉值进行缓冲,否则会出现某个chunk的usage处于临界值,而导致不停的在两个chunk间移动。
- PoolChunkList内部PoolChunk链表内存分配的时候,从内部PoolChunk链表head开始,尝试分配所需内存,如果分配失败,则尝试next chunk,不断循环直到成功。分配成功后,判断当前已分配的总使用量是否超过maxUsage, 若超过, 则将此chunk移动到前一个PoolChunkList链表中。
###Arena Arena负责管理Arena内所有被分配的内存。
与Netty不同, 当前Arena不实现与线程的绑定,以及Cache。 ####针对tiny的内存管理 使用Subpage[]来记录所有已分配tiny大小内存的Subpages,数组下标为normCapacity>>>4,也就是length=32,里面存放的是对应Subpage.head。
####针对small的内存管理 使用Subpage[]来记录所有已分配small大小内存的Subpages,数组length=4 (参见“内存分配策略”),里面存放的是对应Subpage.head。
####针对large的内存管理 使用qInit,q000,q025,q050,q075,q100这5个PoolChunkList按照使用率来记录所有已分配的Chunk清单。
####针对huge的内存管理 小于1/2ArenaSize的huge内存同large的内存管理方式。
####针对superHuge的内存管理 大于1/2ArenaSize的huge内存,直接使用MycatBigMemoryBuf[] superHuge来存放引用。
####内存分配锁
##MycatBigMemoryAllocator 内存分配/回收器, 支持回收策略定制。 待补充。
##MycatBigMemoryByteBuf java.nio.ByteBuffer的重新实现,创建方式为Unsafe Direct方式。 ####内部元素
- Chunk chunk[] : 所包含的chunks引用。如果length>1,则说明此ByteBuff有多个离散的(也可能是连续的)chunk内存空间组成。在put/get时需要计算好偏移量。
- memory, offset :chunk[length-1]里,此MycatBigMemoryByteBuf包含的空间,即chunk内存首地址和偏移量。
##swap swap到FileChannel或者其他Channel的能力,待开发。
##碎片整理 需求待收集。