高并发读多写少场景下的高效键查询与顺序统计的方案思路

之前在某平台看到一篇有意思的场景——对于高并发读多写少场景下，如何进行高效键查询与统计早于其创建时间且没有被删除的数量（只需要先入先出，不需要从中间删元素）

在高并发、读多写少的场景下，业务需求通常聚焦在以下两点：

1. 高效查询键对应的值 —— 需要能够快速定位特定键的存储值。
2. 统计该键前有多少个未被删除的键值对 —— 需要知道当前键在整个数据序列中的相对顺序，同时剔除已删除的无效数据。

传统的数据库索引或简单的哈希存储难以同时满足这两个需求，尤其是在高并发环境下，如何在不影响查询效率的前提下维持顺序统计成为关键挑战。

核心挑战

1. 高并发读请求的优化 —— 需要降低锁争用，确保查询高效。
2. 如何在键查询的同时，快速获取其顺序统计值 —— 需要维护高效的数据结构来支撑有序查询和统计。
3. 处理删除操作对顺序统计的影响 —— 不能简单地用固定索引，而要考虑动态变化的删除情况。

方案一：map+有序数组

方案一可能是最直观的，就是将两种业务需求通过两个数据结构分别进行解决，一种以空间换时间的典型思路

但方案一存在的问题，不仅仅只是占用了更多的空间，而更在于

1. 数据一致性难以保障
   • 写入时，需要同时写入map和有序数组，只要其中一个失败都会导致数据一致性失效
2. 性能瓶颈
   • 计算前置键值对数量需要遍历，性能较差
   • 写时要同时写两个地方，性能较差，还会影响读取
   • 写入时需要同时获取多个锁，处理不好会造成死锁

方案二：跳表

方案二引入了跳表，跳表的优势在于既能以比较快的速度快速查询到值，而且也具有有序性

但

1. 空间开销较大

   每个节点需要维护多个层级指针，需要额外储存层级、计数信息

2. 并发控制相对复杂

   • 节点更新涉及多个层级的指针修改，需要保证原子性
   • 如果使用粗粒度锁会严重影响并发性能，如果使用细粒度锁，可能会出现死锁
   • 在调整索引层级时，需要处理复杂的并发场景

3. 计算前置节点数量仍需要O(log n)的遍历操作，并可能在最坏情况下发生退化

方案三：双Map+自增ID

这个方案的核心思想是通过两个映射表和一个自增ID来实现所需的所有功能。这种设计利用了FIFO的特性，巧妙地用自增ID来表示元素的插入顺序，从而避免了复杂的数据结构。

数据结构设计

1. 主数据映射表
   • 用途：储存实际键值对（并发安全）
   • 键：用户提供的键
   • 值：包含实际值和对应自增id
2. ID键映射表
   • 用途：储存自增ID到键的映射关系，提供快速顺序查询能力（并发安全）
   • 键：分配该键的自增ID
   • 值：用户提供的键
3. 自增ID管理
   • 当前最大ID：记录已分配的最大ID值
   • 队首ID：记录当前未被删除的最小ID值
   • 特点：使用原子操作确保线程安全

操作原理

写入

1. 获取新自增ID
2. 将键值和自增ID存入主数据映射表
3. 将ID、键对应关系存入ID键映射表

当需要查询某个键对应的值时：

1. 直接从主数据映射表中获取数据

当需要知道某个键之前有多少个元素时：

1. 从主数据映射表中获取目标键的ID
2. 获取当前队首ID（最小未删除ID）
3. 两者相减即可得到前面的元素数量

删除操作由于是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定位分片，然后统计每个分片中本地缓存的目标数量，最后进行合并