ConcurrentSkipListMap结构一探

发表于 分类于
本文字数： 996 阅读时长 ≈ 4 分钟

前言

在研究Redis底层的时候，一个经典应用就是Redis的跳表，而Java中也有类似的实现，就研究记录一下。

ConcurrentSkipListMap 实现原理

1. 数据结构

  • 跳表（Skip List）：
    • 多层有序链表，底层包含所有元素，上层通过概率性索引加速查询。
    • 每个节点（Index）包含键值对、多层前向指针（next）和后向指针（down）。
  • 层数随机生成：
    • 插入节点时，通过随机算法（如抛硬币）决定层数，确保高层索引稀疏分布。
    • 典型实现中，最大层数限制为32或动态调整。

2. 并发控制

  • 无锁（Lock-Free）设计：
    • 使用CAS（Compare and Swap）操作更新指针，避免全局锁。
    • 插入/删除时，通过“标记节点”机制处理并发冲突（如逻辑删除标记）。
  • 快照迭代器：
    • 迭代器基于某一时刻的数据快照，避免遍历时数据变动的影响。

3. 核心操作

  • 插入：
    1. 查找插入位置，自顶向下逐层锁定前驱节点。
    2. 生成随机层数，创建新节点并更新各层指针。
    3. 使用CAS原子操作提交变更，失败则重试。
  • 查询：
    • 从最高层开始，向右查找直到遇到更大的键，再向下一层继续，时间复杂度 **O(log n)**。
  • 删除：
    • 逻辑标记节点为已删除，物理删除延迟到后续操作中完成。

应用场景

1. 高并发有序集合

  • 需排序的并发缓存：如维护全局排行榜（按分数排序）。
  • 范围查询（Range Query）：利用subMap()快速获取区间数据。

2. 替代ConcurrentHashMap的场景

  • 需要自然顺序或自定义排序的键值存储。
  • 需要范围操作（如最近10分钟的数据）。

3. 事件调度系统

  • 按时间戳有序存储任务，支持高效的定时任务触发。

与Redis跳表的对比

维度 Java ConcurrentSkipListMap Redis Sorted Set（跳表）
设计目标 高并发、线程安全的有序Map 单线程内存数据库的有序集合
并发控制 无锁CAS + 逻辑删除标记 无（Redis单线程模型）
内存占用 节点包含多层指针，内存开销较高 跳表节点更紧凑，且共享字符串对象
层数生成策略 随机概率（通常1/2的升级概率） 幂次定律（节点层数分布更稀疏）
数据持久化 仅内存，无内置持久化 支持RDB/AOF持久化
应用场景 JVM内高并发排序、范围查询 分布式场景下的排行榜、范围查询
时间复杂度 查询/插入/删除均为 O(log n) 同左，但单线程下无锁竞争更高效
扩展性 适合多线程写入 适合单线程高吞吐，横向扩展依赖集群

关键差异总结

  1. 并发模型：

    • Java：通过CAS实现无锁并发，适合多线程竞争。
    • Redis：单线程无需并发控制，但受限于单节点吞吐量。

  2. 内存优化：

    • Redis：使用共享字符串（SDS）和紧凑编码，内存利用率更高。
    • Java：对象头开销较大，且多层指针占用更多内存。

  3. 持久化与分布式：

    • Redis：支持数据持久化和集群分片，适合分布式场景。
    • Java：仅限于单JVM内存，需外部实现持久化和分布式。

何时选择？

  • 选ConcurrentSkipListMap：

    • JVM内需要高并发有序访问，如实时计算中的排序中间结果。
    • 需要利用NavigableMap接口的范围查询功能（如ceilingKey()、floorEntry()）。

  • 选Redis跳表：

    • 分布式系统中需持久化的有序集合（如用户排行榜）。
    • 需结合过期时间、发布订阅等Redis特有功能。

通过这种设计，ConcurrentSkipListMap在JVM内部实现了高效的有序并发访问，而Redis跳表则在分布式存储和持久化场景中展现出独特优势。