在共享内存实现 Redis(下)

作者:肖涛

《在共享内存实现 Redis(上)》

一些关键操作的设计:

遍历操作

数据库的遍历接口类似原生Redis接口,用一个整数做游标,这个整数表示平衡树中的排行,即第K个数据,每次遍历时:

1)根据游标找到对应的数据

2)遍历后继数据(节点)并返回指定量,以及新的游标

Randomkey操作

同样利用平衡树的Size字段,根据数据库大小(即根节点Size)随机一个K值,之后返回第K个数据的Key即可

主动超时淘汰

类似Redis在Cron中的做法,每次随机选择一批设置了Expire time的Key进行判断,做法有两种:

1)单独构建一个Expire表,用平衡树存储Key到超时时间的映射,随机淘汰的时候对这个树做上面描述的Randomkey操作即可,缺点是Key需要存两份

2)Expire time作为每个Key的Value的元数据的一部分,Db的平衡树在实现的时候稍微特殊一点,每个节点增加一个Expire size字段,存储此节点为根的子树中有多少Key被设置了超时时间,然后用类似选第K个元素的算法,用Randomkey的方式随机淘汰,缺点是Db的数据结构需要特殊设计实现(每次操作都可能需要额外调整树节点的Expire size域)

渐进式命令执行的实现

需求

在执行读请求的时候,有时候我们得到比较大的数据,具体的场景可能是:有其他进程(如内部运维进程)直接和Redis通讯,请求dump一个Key的Value,由于Value很大,处理耗时很久,而Redis是单线程模型,所以来自客户的业务请求可能会被卡住(共享内存版本的Redis也是单线程模型)

方便起见,我们以单Key的dump需求为例,考虑如何序列化Value返回并且在处理过程中不会造成卡顿的方法,总体来说有两个关键要求:

1)dump的执行应该是渐进式的,不能造成明显卡顿

2)dump出的结果必须是开始执行dump的那个时间点的Value快照,如果dump过程中这个Value被以任何方式修改,都不能影响快照结果

问题分析

如果不考虑上述需求1),则问题就很简单,只需要原子性地处理dump请求即可,或者锁定这个Key,在Cron中渐进式执行dump,在结束之前可以同时响应其他没有加锁的Key-Value的写操作

而要同时实现上面两个需求,我们需要在dump过程中响应并操作正在被dump的Value,同时,由于Value被改变的部分可能还没有被dump到,因此需要实时地先保存一份原来快照的副本,类似Redis通过fork来实现并发RDB的机制,我们在这里实现手工的copy-on-write,即这段时间中Value被修改之前,实时将老的数据copy出一份,同时cow的粒度又要足够小,不能因为这个而导致修改操作卡顿太久;另一方面,cow会消耗额外内存,最好能尽量减少这个内存消耗的峰值

方案

整体思路和Redis的fork的方式类似,只不过fork是利用了操作系统机制,我们用手工的做法:

1)收到dump请求时,对Value做一个快速遍历,记录下dump时可能遍历的实际数据的Block的地址列表(类似fork过程中的页表复制),并将这个列表保存在私有内存中,和dump请求的client对象绑定,相当于一个“待处理任务列表”,这个列表中的元素可以是一个指向Block的指针,也可以是一块实际的Block数据(这样设计的作用见下)

2)在cron过程中,渐进式地处理1)中的列表,对每个元素,访问其引用的Block数据,打包,每次处理一部分,直至结束;为了节省内存,如果实际场景允许的话,也可以做成特殊的dump协议,回复协议做成分段,做一段发送一段,无需全部dump后再发送

3)在渐进式dump过程中,如果这个Value有任何改动,则所有涉及到数据修改的Block(包括上述的增删改、Block分裂、Block合并等等操作)都在其修改之前将Block中的原数据拷贝至1)中对应位置,替换原来保存的Block指针,从而实现手工的copy-on-write

4)由于dump待处理列表是在私有内存,因此程序如果异常终止,资源会自动释放

5)如果同时出现多个client进行dump,则各client可以并行,每个绑定一个dump待处理列表即可,但需要一个全局的列表大小统计,用于统计列表中被cow的Block数据的空间,如果由于client过多或Value的cow内存过大,则可立即令此任务失败,避免出现由于资源占用多导致的其他问题

举例说明:

如图,假设这棵平衡树在dump命令开始时,数据状态是上面黑色Key,之后在dump流程中遇到了若干写操作,流程和列表状态变化:

A)首先做各Block的地址快照,按顺序遍历所有节点,得到列表:

B)在cron任务中先dump了两个Block:NodeA和NodeB,剩余列表:

此时的Dump Key列表:DFGH,即NodeA和NodeB中的数据已经序列化到缓冲,下同

C)有写请求到来,插入了Key L,由于NodeD被修改,且未被dump处理到,所以实时将老数据Block copy到列表中,剩余列表:

此时,列表中NodeC和NodeE维持指针状态,而NodeD则保存了共享内存中对应Block的修改前的快照数据,三者加起来仍然是逻辑上的快照

D)在cron任务中继续dump了一个Block:NodeC,剩余列表:

此时的Dump Key列表:DFGHJ

E)又收到一个写请求,插入了数据Z,导致新增一个Block,这个操作对dump列表无影响

F)下一个写请求是删除Key N,需要对NodeD做cow,但是由于NodeD已经做过了,所以不用做,对dump列表无影响

G)继续在cron中dump NodeD的数据,此时使用之前cow拷出来的数据,剩余列表:

此时的Dump Key列表:DFGHJMN

H)收到插入Key K的请求,影响了NodeC的数据,但是由于NodeC已经被dump过了,所以对dump列表没有影响

I)在cron中dump NodeE的数据,列表清空,dump结束,结果为DFGHJMNX,发送给client即可,可以看到,这个结果就是dump请求处理开始时,平衡树内部数据的精确快照,途中插入的写操作并没有影响到结果,并且我们只耗费了一个Block的额外空间(列表中的元素如果是Block指针的话,耗费会很小)

J)进一步优化:从上面过程中可以看到,如果我们按列表顺序进行dump,被cow的Block NodeD在cow的时候,前面是NodeC还没有被dump,如果列表中各Node的数据可以不用保持有序,则我们可以优先dump那些被cow的Block,这样可以提前将其处理完毕释放

K)关键问题:上面是用平衡树做实例,链表的处理也是类似的,但如果是一个用链表形式保存的长字符串,则在cow时候可能需要将整个字符串拷贝出来,这一点可能还是有改进的空间

RDB的实现

由于数据在共享内存中,不能用fork机制利用操作系统的cow机制,所以RDB的实现还是通过类似上面渐进式的算法,只是稍微复杂一些:

1)先做Db这个平衡树的快照(记录所有涉及的Block的指针)

2)当Db中的Key被修改时,拦截所有对Block可能的写操作,并根据上面的算法进行手动cow

3)优先将脏数据落盘,提早释放空间

其实如果不纠结数据落盘的格式,还可以直接拷贝整个共享内存,因为这块内存就是/dev/shm下的一个文件,将文件按一定大小分页进行拷贝,也是程序手动控制cow,优先拷贝即将被写脏的页。如果想利用一下操作系统,还可以在mmap的参数上做文章:)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

RobotFramework怎么写好用例

github地址:https://github.com/robotframework/HowToWriteGoodTestCases/blob/master/H...

1212
来自专栏liukaili_666888999

开发中用到的设计模式

MVC:它是应用的一种基本架构,主要目的是将不同的代码归并为不同的模块,做到低耦合,代码分配合理,易于扩展维护。

1091
来自专栏IT技术精选文摘

Nginx模块之Filter解析

过滤模块简介 执行时间和内容 过滤(filter)模块是过滤响应头和内容的模块,可以对回复的头和内容进行处理。它的处理时间在获取回复内容之后,向用户发送响...

2199
来自专栏图形学与OpenGL

实验3 文件操作

    (3)     根据这个随机数,从所读取的记录中找到对应的记录,并输出显示;

852
来自专栏企鹅号快讯

讲义15:服务器端编程:Request&Response

一、内容提要 B/S模型 Reponse对象 Request 对象 二、内容及操作步骤 1. B/S模型 Browser: 浏览器 Server: Web 服务...

1906
来自专栏青枫的专栏

ANSI是什么?

ANSI是一种字符代码,为使计算机支持更多语言,通常使用 0x00~0x7f(即0000 0000~0111 1111)范围的1 个字节来表示1个英文字符。超出...

452
来自专栏刘望舒

Android网络编程(十)Retrofit2后篇[注解]

前言 在上一篇Android网络编程(九)Retrofit2前篇[基本使用]中我们了解了Retrofit的最基本的GET方式访问网络的写法以及请求参数的简单介绍...

1796
来自专栏大内老A

WCF服务端运行时架构体系详解[下篇]

作为WCF中一个核心概念,终结点在不同的语境中实际上指代不同的对象。站在服务描述的角度,我们所说的终结点实际上是指ServiceEndpoint对象。如果站在W...

1657
来自专栏同步博客

PHP操作Memcached的方法汇总

memcached非关系型数据库安装、php中的memcache的扩展安装、以及php中的memcached的扩展安装可以参考:

562
来自专栏猿人谷

unix共享内存要点

共享内存优点:     1.在进程之间不通过内核传递数据,即不通过系统调用拷贝数据,达到快速,高效的数据传输。     2.随内核持续     *nix的共享内...

16910

扫码关注云+社区