在共享内存实现 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的参数上做文章：）
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。