JVector项目中DenseIntMap并发修改导致size计数异常问题分析

背景

在JVector项目的DenseIntMap实现中，存在一个并发场景下的size计数异常问题。DenseIntMap是一种基于数组实现的密集键值映射结构，它使用乐观读锁机制来提高并发性能，但在特定并发操作组合下会导致size计数永久性不一致。

问题本质

DenseIntMap的size计数机制在并发环境下存在同步漏洞。具体表现为：

1. 当put和remove操作并发执行于同一个未存在的键时
2. put操作首先修改了底层数组
3. remove操作获取写锁并删除值(减少size计数)
4. put操作检测到版本戳失效后重试
5. 重试的put操作再次插入值(增加size计数)

最终结果是map中存在新插入的值，但size计数没有相应增加，导致永久性的计数不准确。

技术细节分析

DenseIntMap的实现采用了乐观并发控制策略：

• 读操作使用乐观锁，通过版本戳(stamp)检测并发修改
• 写操作(remove和扩容)使用悲观写锁
• put操作在检测到版本戳变化时会重试

这种设计在大多数情况下能提供良好的并发性能，但在特定时序下会出现问题：

// 伪代码展示问题场景
void put(K key, V value) {
    do {
        stamp = readStamp(); // 获取当前版本
        oldValue = map.get(key);
        isInsert = (oldValue == null);
        // 此时另一个线程执行remove操作
    } while (!validate(stamp)); // 检测到版本变化重试
    
    if (isInsert) size.increment();
}

当重试发生时，虽然操作成功插入了值，但size计数可能已经因为并发remove而减少，导致最终计数不准确。

解决方案探讨

项目维护者考虑了多种解决方案：

1. 悲观锁方案：改用ReadWriteLock完全同步，虽然实现简单但会降低并发性能
2. 弱化size保证：
   • 保留O(1)的isEmpty()检查
   • 提供O(1)的modificationCount
   • 将size()改为O(N)操作(遍历计数非空键)
3. 保持乐观锁但修复计数：通过更精细的版本控制确保计数准确

最终采用了第一种方案，因为：

• 实际性能测试显示乐观/悲观锁对put操作影响不大
• 实现简单可靠
• 在JVector的使用场景中，构建索引时的节点添加操作本身开销较大

经验总结

这个案例展示了并发编程中的典型陷阱：

1. 乐观并发控制虽然能提高性能，但需要仔细考虑所有可能的执行路径
2. 复合操作(检查-执行)在并发环境下需要特别处理
3. 有时简单的同步方案反而比复杂的无锁方案更可靠
4. 性能优化应该基于实际场景的基准测试，而非理论假设

对于类似的高并发数据结构实现，开发者需要：

• 全面分析所有可能的并发操作组合
• 考虑重试机制对状态的影响
• 在性能与正确性之间做出合理权衡