高并发读多写少场景下的高效键查询与顺序统计的方案思路
之前在某平台看到一篇有意思的场景——对于高并发读多写少场景下，如何进行高效键查询与统计早于其创建时间且没有被删除的数量（只需要先入先出，不需要从中间删元素）
在高并发、读多写少的场景下，业务需求通常聚焦在以下两点：
- 高效查询键对应的值 —— 需要能够快速定位特定键的存储值。
- 统计该键前有多少个未被删除的键值对 —— 需要知道当前键在整个数据序列中的相对顺序，同时剔除已删除的无效数据。
传统的数据库索引或简单的哈希存储难以同时满足这两个需求，尤其是在高并发环境下，如何在不影响查询效率的前提下维持顺序统计成为关键挑战。
核心挑战
- 高并发读请求的优化 —— 需要降低锁争用，确保查询高效。
- 如何在键查询的同时，快速获取其顺序统计值 —— 需要维护高效的数据结构来支撑有序查询和统计。
- 处理删除操作对顺序统计的影响 —— 不能简单地用固定索引，而要考虑动态变化的删除情况。
方案一：map+有序数组
方案一可能是最直观的，就是将两种业务需求通过两个数据结构分别进行解决，一种以空间换时间的典型思路
但方案一存在的问题，不仅仅只是占用了更多的空间，而更在于
- 数据一致性难以保障
- 写入时，需要同时写入map和有序数组，只要其中一个失败都会导致数据一致性失效
- 性能瓶颈
- 计算前置键值对数量需要遍历，性能较差
- 写时要同时写两个地方，性能较差，还会影响读取
- 写入时需要同时获取多个锁，处理不好会造成死锁
方案二：跳表
方案二引入了跳表，跳表的优势在于既能以比较快的速度快速查询到值，而且也具有有序性
但
-
空间开销较大
每个节点需要维护多个层级指针，需要额外储存层级、计数信息
-
并发控制相对复杂
- 节点更新涉及多个层级的指针修改，需要保证原子性
- 如果使用粗粒度锁会严重影响并发性能，如果使用细粒度锁，可能会出现死锁
- 在调整索引层级时，需要处理复杂的并发场景
-
计算前置节点数量仍需要O(log n)的遍历操作，并可能在最坏情况下发生退化
方案三：双Map+自增ID
这个方案的核心思想是通过两个映射表和一个自增ID来实现所需的所有功能。这种设计利用了FIFO的特性，巧妙地用自增ID来表示元素的插入顺序，从而避免了复杂的数据结构。
数据结构设计
- 主数据映射表
- 用途：储存实际键值对（并发安全）
- 键：用户提供的键
- 值：包含实际值和对应自增id
- ID键映射表
- 用途：储存自增ID到键的映射关系，提供快速顺序查询能力（并发安全）
- 键：分配该键的自增ID
- 值：用户提供的键
- 自增ID管理
- 当前最大ID：记录已分配的最大ID值
- 队首ID：记录当前未被删除的最小ID值
- 特点：使用原子操作确保线程安全
操作原理
写入
- 获取新自增ID
- 将键值和自增ID存入主数据映射表
- 将ID、键对应关系存入ID键映射表
当需要查询某个键对应的值时：
- 直接从主数据映射表中获取数据
当需要知道某个键之前有多少个元素时：
- 从主数据映射表中获取目标键的ID
- 获取当前队首ID（最小未删除ID）
- 两者相减即可得到前面的元素数量
删除操作由于是FIFO队列，只需要删除队首元素：通过原子操作增加队首ID，无需立即从映射表中删除数据，可以通过后台任务定期清理已删除的数据，不影响其他操作的执行
有意思的是这个设计与mysql索引有些类似，主数据映射表就是主键索引，ID键映射表就是二级索引
方案四：redis zset
如果将创建时间作为redis zset的score，那么就能很好满足该场景下的需求
zrank查询对应的值的时候就会返回这个值的排序下标(整个 zset 排序下标从 0 开始), 默认 timestamp 升序, zrank 返回的值减 1 就知道前面有多少个是先于它了.
redis zset其实依然hash表加跳表
性能分析
优势
- zset跳表提供了O(log(N))的查询性能
- redis单线程避免了并发控制的复杂性
- 支持丰富的排序和范围查询操作
- 方便实现分布式拓展
缺点
- 内存占用较高
- 原子性需要通过MULTI/EXEC实现
- 获取有效键数量需要多次操作
- 受Redis单实例内存限制
方案五：分布式
分布式是考虑到极大访问量的场景所应用的方案
kafka+elasticsearch
写入时流转kafka随后写入es，采用es倒排索引作为键快速查询，es聚合功能作为计数统计
分片+本地缓存
通过一致性hash定位分片，然后统计每个分片中本地缓存的目标数量，最后进行合并