IT技术互动交流平台

infQ不受限于内存的队列

来源:IT165收集  发布日期:2016-02-29 21:17:52

一、背景

在常见的内存队列(redis的list结构)中,经常会因为队列阻塞,导致内存撑爆。类似的,在redis主从同步过程中,由于内存限制,redo log的buffer是固定的,如果从库的进度在buffer之外,就需要进行一次全量同步,这是一个非常重量级的操作。
为解决上述问题,本文设计并实现一种数据结构,用于基本无内存限制的存储队列(受限于磁盘空间)。基本思路是限制队列使用的内存,将中间部分数据写到磁盘,push端和pop端在内存操作,通过后台线程在内存和磁盘间交换数据。

二、整体结构


InfQ内部结构包括: 1)内存队列:用于push和pop的buffer,保证push和pop都是内存操作。占用固定大小的内存block,并划分成n个大小相同的内存块。 2)文件队列:当内存队列空间耗尽时,存储中间数据,以腾出内存。由内存block dump成的文件组成。 3)后台线程:存在两种类型: - dumper:在Push Queue内存使用超过一定阈值时,将内存block dump成文件块,添加到文件队列。 - loader:当Pop Queue存在空闲空间时,将文件队列中的文件块,load成内存block添加到POP Queue。

1. 内存队列

内存队列可以看成是二级队列,第一级是由内存block组成的环形队列。在初始化时,指定block的个数,保证占用固定大小内存。每一个内存block又组成了一个队列。结构如下:

2. 文件队列

文件队列实际上就是一个file block的链表,以file block作为操作单元。在执行内存块dump和load时,都是顺序io,所以不存在性能瓶颈。同时,由于两端有内存队列用于缓冲,从而保证push和pop操作不涉及io操作。

3. 后台线程

后台线程用于执行io相关操作,保证内存队列始终有空闲空间,使得push和pop都是内存操作。每个后台线程有一个job队列,用暂存主线程提交的job,如果队列为空,后台线程会阻塞等待。
1)dumper 在Push Queue内存使用超过一定阈值时,dumper会依次将最老的内存块dump成文件块,添加到文件队列。内存块dump的时机需要精心选择,不然存在两种问题: (1)dump的过早(内存使用阈值过低),会导致不必要的内存块dump,产生磁盘IO。
(2)dump的过晚(内存使用阈值过高),在执行push操作时,没有内存,需要阻塞等待dump完成,以空出内存。 所以,阈值选择需要经过测试,选择最佳值。 2)loader 对于Pop Queue,内存块load的逻辑要简单一些,只要存在空闲的内存块,就将文件块加载到内存。

三、详细设计

1. push流程


2. pop流程


3. 后台线程

为避免无谓使用cpu,后台线程在没有任务执行时会一直阻塞。dumper线程分配任务的逻辑很简单,在完成一个内存块时,就为其分配一个任务,由dumper执行。loader线程要稍微复杂一些,因为它的执行依赖于文件队列以及Pop queue。loader的任务分配的时机是在每次pop调用时,主动去检查,如果有空闲内存块,并且文件队列非空,就会创建一个任务,加载内存块。

四、随机访问

1. 不支持随机访问

如果只支持push,pop,那么内存块的结构就会比较简单,不需要维护全局索引。

每个元素包括:4字节的length,随后是其数据,最后是padding,保证地址是4字节对齐的。由于没有全局索引,可以直接将内存块dump成文件,即生成对应的文件块。

2. 支持随机访问

1)内存块 内存块布局如下:

随机访问依赖于全局索引,每个内存块具有属性start index,表示内存块第一个元素在整个队列的下标。可以据此计算内存块中所有元素的下标。同时,还有offset array,用于根据全局下标索引到对应的元素,其值就是元素在内存块的偏移量。
在进行随机访问时,输入是全局下标,具体步骤如下:
(1)根据全局下标和start index,计算出元素在offset array的局部下标。
(2)然后局部下标找到对应的offset,读取元素
2)文件块 文件块需要增加一个header,用于存放全局索引,布局如下:

在读文件块时,需要两次io,一次将header读到内存,第二次是读取对应的元素。为避免header产生的io,对于每个文件块,在内存中会存一份元数据,包含header信息。由于header本身很小(10w个元素,只占8KB),所以内存开销可以忽略不计。
3)随机访问流程 下图是队列运行一段时间之后的状态,内存块和文件块中的数字是该块的第一个元素对应的全局下标。

每个元素都有一个下标,这个下标是全局递增的,可以通过[n,m]表示当前队列的下标范围,把这个下标称为物理下标。在对外接口中用的是逻辑下标,是从0开始的,所以需要进行一次转换。比如,访问逻辑下标x对应的元素,其物理下标是 x + min_index。
接下来,根据物理下标要找到对应的内存块或者文件块。因为块是按照起始下标排序,所以可以通过二分查找完成。 如果访问的数据在内存中,直接读取即可。但是,如果在文件中,就需要磁盘io,可以通过引入cache避免io。系统page cache会缓存部分读取的内容,是粗粒度的cache,这里实现一个细粒度的cache,用于缓存一个range的元素(比如,下标a-b的元素)。在访问文件块时,首先检查是否命中上述cache,如果没命中在去读文件。

五、持久化

为了将infQ集成到redis,需要支持RDB和主从同步,所以需要支持infQ的持久化。在进行持久化时需要将infQ的内存状态序列化为字节数组,其内存状态包括: - Push Queue - Pop Queue - File Queue - infQ整体状态 以上3个Queue都包括元数据和数据。对于元数据,所有Queue都需要持久化。而对于数据,由于File Queue的所有数据已经持久化到磁盘上,所以不需要再次持久化。 持久化流程: - 持久化Push Queue - 持久化Pop Queue - 根据当前infQ的状态,生成字节数组 在持久化Push Queue时,就是将所有的内存块dump成文件块,然后追加到File Queue上,之后Push Queue的数据就都由File Queue接管,最后生成的持久化只需要File Queue即可。

六、源码

https://github.com/chosen0ne/infQ
Tag标签: 队列   内存  
  • 专题推荐

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规