Sucha's Blog ~ Archive for February, 2024

mmap(1)

自从 cincau 支持多进程的方式之后，同步数据的能力最开始是通过不同 worker 的 UDP socket 来传递的，即时性有限，大概固定几秒钟去同步一次，而且如果数据量大了也是个问题。

相比较下，即时性的问题才是主要的，比如其中一个 worker 接受了用户的登陆状态，用户的下个请求是另外一个 worker 来服务的，此时 cookie 的 session 信息根本还没同步过来，就成了问题。

当然这个问题也有粗放的解决办法，比如用 SQLite 来同步，但是这种 Key/Value 的信息也使用 SQLite 觉得还是太重了。

这里插播一句，之前了解过使用 mmap 来同步数据的 MMKV，因为 mmap 同样可以用来多进程同步数据，因此这个库也是可以多进程同步的，感觉这个库可以解决 95% 以上的同步问题，其他的例外情况，我下面会说。

在展开其他方案之前，我得检讨一下，一开始走了很多的弯路，虽然了解到需要使用一些多进程同步手段，比如最开始的 socket，比如可以使用 Linux 消息队列，以及 mmap，但是我把这个问题想得简单了，而且一开始我也没想起 MMKV。

比如我一开始就选择了 mmap，想做一个 mmap 的有序字典，我手头有 MIT LICENSE 的 AVL tree 代码，相比之下 MMKV 这种 bitcask 结构的数据库，是无序的，除非你 dump 出来所有的 key 再排序，否则你无法快速拿到按照 Key 排序的第一个节点，而 AVL tree 对 Key 排序的方案就可以。

可是已有的 AVL Tree 的方案，其对节点的引用是指针的，虽然 mmap 只管映射内存区域，但是不同的进程，其映射的内存区域很可能不一样，比如我使用的 LuaJIT，除了我自己主动调用的 mmap，其他不知道什么原因，也有不少的 mmap 调用。导致如果使用 AVL tree 的方案，除非是能保证每一个进程 mmap 过来给 AVL tree 使用的内存块，采用同样的起始地址，否则后续的指针计算，指向的节点地址就有问题。

虽然理论上，我可以将进程空间的一大段都交给这个 AVL tree 共享内存的方案，但是实际做起来其实也不方便，而且 mmap 这个系统调用其实很频繁，用 strace 就可以看到，其他的一些文章也有介绍。

所以，不得不将 AVL tree 的指针引用，改成 int32_t 的间接引用，这里的 int32_t 分成了高 16bit 和低 16bit，其中的高 16bit 用于 index 内存区块，低 16bit 用于 index 每个区块内的位置，byte offset。

之所以这么做，是因为内存块是动态申请的，不会一下就申请完所使用的内存，而是根据使用量逐步申请，虽说是共享内存，也总得使用实际内存空间的嘛。

另外这个 AVL tree 的方案相比 MMKV，其实有很大的限制，因为考虑到不想做 bitcask 那样的回收方案（简单点做），因此设置了限定最大的 Key/Value 长度，这个是调用库在初始化的时候就得进行设置的。

比如 Key/Value 的最大长度是 64 字节，其中 Key 是一个 timestamp 占 32 字节，后续的 Value 是一个 MD5 的 hash 占 32 字节，这里还可以插播一句，可以将这个 Value 作为 MMKV 的 Key，这样就实现了 MMKV Key 的有序，回应了最开始说的 95% 的应用场景。不过这里也得提一下，MMKV 还可以设置每个 Key 的过期时间，所以这个 95% 的应用场景，实际上还可以扩大不少。

回到刚刚的 AVL Tree，所有需要同步的数据都存放到 mmap 的内存区块中，每个进程都有对 AVL Tree 的引用，以及自己保留一份已经打开的内存区块列表，当别的进程因为塞入更多的数据申请了新的内存区块，其他进程在进入库调用的时候，检查到这个场景，将新的内存区块也 mmap 到自己的进程空间上。

因为每条数据是固定的长度（最大 Key/Value 长度），所以 AVL Tree 的 index 间接指针会忽略掉不同进程内存区块的起始地址不一致的情况，只关注内存区块的序号，以及每条数据对应内存区块的偏移字节，当这个内存区块已经映射到进程空间上后，对 index 的数据的读写就没有障碍了。

在实际使用中，当内存空间不足时，申请内存区区块序号（2^16个），映射内部的节点地址偏移，两者揉进每个节点的唯一 index，当删除节点时，节点可以回收而不需要整理内存区块，比如将该节点的 index 保存到未使用空间列表节点的 right 指针（间接指针）中。

上面说完了 mmap AVL Tree 的使用场景、面临的问题，提出的解决方案，和该方案的限制，下面列出来了一些实际跑通该场景的有趣细节：

• AVL Tree 需要对比 Key 才能排序然后旋转，但是这个比较函数的运行空间是在不同的进程地址空间，因此每个进程在实际进行查找、插入、删除时，得使用自己进程空间的比较函数来执行，如果比较函数的函数指针，用的是其他进程的，那就有问题了（父子进程不在此讨论范围）
• mmap 有些参数需要注意，除了多进程共享一定会用到的 MAP_SHARED，还得使用 MAP_POPULATE，否则后续其他进程将内存区块加载进来后，会遇到问题，这个参数是告诉 mmap，为了避免后续访问地址的 page fault，得将此文件涉及到的内存地址，先全都映射上来
• mmap 只涉及到共享的内存区块，为了保证数据的一致性，还得在访问时加锁，需要用到 pthread_mutexattr_setpshared 的 PTHREAD_PROCESS_SHARED，除此外，当某个进程 crash 掉而没有清理 pthread 数据时（共享的内存区块中），其他进程在锁的处理过程中，需要 pthread_mutex_consistent，这个是在初始化 mutex 时通过 pthread_mutexattr_setrobust 的 PTHREAD_MUTEX_ROBUST 参数保证的

细节太多了，当然相比较 SQLITE，上述两套方案的效率会高很多。

MMKV 已经很成熟，多平台都能支持，AVL Tree 是我当初小看了 mmap 导致的，而且有先天的短板，虽然说提供了有序 Key 的能力，但这个是在约束了最大 Key、Value（每条数据都是这个最大长度）来达到的，因为可以避免替换 mmap 共享的内存区块。