shm_lru_cache 共享内存 并发 变长 LRU 缓存
文章目录
一个基于共享内存，多线程多进程并发安全，key value 变长 的 LRU 缓存。 内部基于 TLSF 内存分配器, 和 LevelDB 的 LRUCache 代码实现
一，介绍
一个基于共享内存，多线程多进程并发安全，key value 变长 的 LRU 缓存。 内部基于 TLSF 内存分配器, 和 LevelDB 的 LRUCache 代码
基于 TLSF 内存分配器。存入多少数据就占用多少内存。释放掉的 key/value 等内存空间自动回收重用。
基于 LevelDB 的 LRUCache ，读操作和写操作可以并发执行，内部通过读引用计数实现。
读操作直接返回指向共享内存的指针，零拷贝。
支持 CompareAndSwap CAS 乐观锁操作
多进程多线程并发读写 ShmLRUCache 时, 如果个别进程异常退出，则其他进程会在读写的时候检测到， 会删除共享内存文件将当前进程退出，等待进程被重启之后重建新的共享内存使用。利用 pthread mutex 的 robust list 实现
支持设置 TTL 过期时间，达到过期时间的 key 会在哈希桶 Lookup 访问过程中被淘汰删除。
开发了配套工具 dump_shm_lru_cache ，可以在运行时只读打印共享内存中的所有 key value
二，使用方法
暂不开源，没有使用方法
常用共享内存相关工具命令：
top 共享内存都算入 top 看到的 SHR 即共享内存这一列，同时也算入 RES 即驻留内存这一列。
du -sh /dev/shm/* 查看共享内存文件实际占用多少物理内存
lsof -p $pid |egrep 'NAME|/dev/shm' 查看进程 $pid 实际打开了哪些共享内存文件
pmap -X $pid |egrep 'Rss|finder_' 查看进程的共享内存文件 finder_* 都映射到哪些地址段
ls -lhS /dev/shm/* 查看共享内存文件最大允许的大小。注意不是实际占用大小。
三，性能测试，固定使用 4 进程 * 4 线程 = 16 线程
下面的性能测试工具代码也和代码在同一个目录下，可以随时自己编译自己复现。
1. 纯读，96% 命中率时 550W QPS，50% 命中率时 640W QPS
2. 覆盖写, 43 WQPS
3. 读写并发进行 ( 4x4=16 个线程读，同时另外有 4x4=16 个线程写)，此时读性能 420W QPS，写性能 41W QPS
4. 典型业务逻辑“先查询如果 miss 就写”，77% 命中率的情况下，400 W QPS
四，几个方面的关键设计
1. 为什么不搞无锁？
因为无锁只能对 8/16 字节的简单内存操作实现原子性，而想实现变长就要搞个主流一点的 best fit 类的内存分配器算法，这类算法都有复杂的管理数据结构，比如由多个链表，bitmap，红黑树 等组成的复合数据结构，其上的操作基本不可能实现成无锁。
2. 怎么应对多进程下某些进程的异常退出？
背景：pthread_mutex 有个 robust list 功能 (PTHREAD_MUTEX_ROBUST) ，其语义是“当多个进程 attach 到同一块共享内存，并且其中一个进程在加锁进入临界区之后被 kill ，则其他进程在下次 pthread_mutex_lock 时会收到特殊返回码 EOWNERDEAD”。
基于 robust list，可以把 “被 kill ” 分为 2 种来做应对：
在临界区内被 kill，这种情况通过 EOWNERDEAD 可以检测到，直接删掉共享内存文件，重启进程就行。
在临界区外被 kill， 只要保证所有修改数据结构的操作都在临界区中，则这种情况不会影响到 lru cache 的数据一致性。
3. 在每个进程映射到同样的起始虚拟地址，还是不同的起始虚拟地址即搞 boost::interprocess::offset_ptr 那种？
这里选择了多进程映射到同样起始地址，同样起始地址的好处是里面的数据结构可以用裸指针，代码实现简单。
背景是因为我发现 X86-64 平台上 48bit 地址空间非常巨大，pmap 看到其实大多数地址空间是没有使用的，目前是从 90TB 这个虚拟地址开始尝试分配，如果冲突就后移。并且这里利用了新一点 Linux kernel 的 MAP_FIXED_NOREPLACE 选项，可以避免覆盖已有的内存映射。
4. 起始虚拟地址是怎么分配出来的？
创建 shm 文件的时候进行分配，读 /proc/self/maps 获知本进程的地址空间分布，从中找到从 90TB 开始并且没有被占用的空洞，来进行 mmap，如果冲突了即地址空间已经被占用了，再次尝试。
其他进程 attach 已经存在的 shm 文件的时候，有个 CheckAttach 的检查逻辑，如果发现本进程的地址空间被占了，会返回 kMMap2BaseAddrConflicted , 然后 Remove 删掉共享内存文件。（Linux 下进程打开文件后，如果被 deleted， 还是可以正常读写的，不受影响。）
这里的过程就有点像个活锁，经过多次互相删除后，最终所有进程会达成统一，在相同的虚拟地址上映射同一个共享内存文件。
不同的 shm_name 文件，会分配出不同的起始地址。
5. 怎么限制内存使用？
目前有 2 种限制策略：总条数限制，和总字节数限制。当达到限制时，会进行淘汰，有 2 种淘汰策略：LRU 和 TTL。
6. 用什么内存分配器算法？
找了目前业界比较成熟的一个嵌入式分配器 TLSF 直接复用。
7. LRU Cache 数据结构怎么实现？
直接把 LevelDB 中的经典 LRU Cache 代码复制出来做改造，该实现的一大亮点是搞了个引用计数，使得读写可以并发进行。并且我直接继承了其很多单元测试，用来保证代码正确性。
8. 节省内存的技巧
使用了 varint 7bit 编码保存 key/value 的长度 。
LRU 中节点的三个指针，换算成到基地址的 offset，并考虑了 align 和 48bit 地址空间后，用位运算压缩到了每个指针 35bit 。
五. 和业界类似项目对比
1. boost::interprocess
(1). shm_lru_cache 在 robust list 检测到 corrupted 后，能定制 多进程 rpc 环境下的恢复策略 : _exit()。
(2). shm 上 robust list 的 mutex 的实现，需要自己实现多进程对 OWNER DIED 状态的发现机制。
(3). shm_allocator 实现了 stateless allocator 无状态的分配器，用于各种库更省内存，比如各种带 Alloc 模板参数的 std 类，容器等。 boost::interprocess 的 allocator 是有状态的。
2. memcached
(1). 没有网络层，因此不可能有网络层的故障
(2). 性能大幅度提升，
3. libshmcache
https://github.com/happyfish100/libshmcache
shm_lru_cache 利用了 robust list 实现的 corrupted 检测，这才是严密的。
TLSF 有 merge/absorb 逻辑，能适应 value 长度的各种变化。
4. lmdb/mdbx
设计用途不同，lmdb/mdbx 是 B+ 树有序 map 数据结构 key-value 存储引擎。性能有限。
5. redis
“Redis 6.0 主备实例测试数据”：
https://support.huaweicloud.com/pwp-dcs/dcs_10_0001.html#section2
https://redis.io/docs/management/optimization/benchmarks/
GET/SET 大概是 15W QPS，当然 redis 是单核还有网络层而且是文件持久化的，适用场景有点不一样。
6. dragonfly
https://github.com/dragonflydb/dragonfly/blob/main/README.zh-CN.md#- 基准测试>
7. golang 的各种 cache
这些都不是基于共享内存的，而且性能也有差距