并发跳表：标记删除、乐观加锁与 ConcurrentSkipListMap
内容提要
并发跳表的核心难点是：一次插入或删除需修改多个指针，而CAS只能原子修改一个字。常见误解如“每层独立CAS即可”会导致并发插入节点丢失，实验在64万次操作中出现七千多次错误。文章梳理了从Pugh写锁、Harris标记到无锁及lazy方案的谱系，并对照JDK、LevelDB、RocksDB源码，讨论线性化点、内存回收与吞吐实验。
延伸解读
朴素CAS删除的陷阱
文章通过实验表明，在单链表上使用朴素CAS删除会导致并发插入的节点丢失。64万次操作中出现七千多次错误，约每50次操作出错一次。这是因为插入和删除的CAS比较的是不同内存字，可能同时成功，导致新节点挂在已删除节点后不可达。这提醒我们，并发跳表不能简单地对每层独立CAS，必须采用标记删除等机制。
标记删除如何解决问题
Harris标记删除通过两步操作解决上述问题：先CAS设置被删节点next指针的标记位（逻辑删除），再CAS让前驱跳过它（物理删除）。标记后，任何以未标记旧值为期望的插入CAS都会失败，从而防止节点挂到已删节点后。文章实验显示，采用Harris标记后，5个种子下丢失和幽灵错误均为0，验证了其有效性。
不同实现的线性化点差异
文章对比了多种并发跳表实现，发现删除的线性化点位置不同：Pugh和lazy方案放在标志或摘除上，Fraser和JDK放在value字段，而本文实现放在第0层next指针的标记位。此外，LevelDB和RocksDB的memtable不支持删除节点，从而避免了标记和回收问题。这些差异反映了设计权衡，读者需根据场景选择。
无锁与加锁的性能对比
文章指出，无锁并不一定比加锁快。HLLS论文在读多写少负载下测得两者相当；本文在3个物理核上的测量中，两者吞吐都随线程数上升，差距在11%到47%之间，与负载和数据规模有关。因此，选择并发方案时需结合实际负载测试，而非盲目追求无锁。
Q&A
为什么在跳表中用简单的CAS删除会导致并发插入的节点丢失？
因为一次插入或删除需要修改多个指针，而CAS只能原子修改一个字。例如，线程T1在节点5后插入6，线程T2删除节点5，两个CAS操作比较不同的内存字（5.next和1.next），都会成功，导致6挂在已不可达的节点5上，插入返回成功但6丢失。
Harris标记删除是如何解决并发跳表中插入丢失问题的？
Harris标记删除分两步：先用CAS在被删节点的next指针上置标记位（逻辑删除），再用另一次CAS让前驱跳过它（物理删除）。标记后，任何以未标记旧值为期望的插入CAS都会失败，插入者重新查找时会看到标记并先摘掉被删节点，再在正确位置插入。
Pugh的并发跳表方案中，删除节点时为什么要进行指针反转？
指针反转是为了让正在经过被删节点的查找能够退回到链表中正确的位置。删除节点x时，除了让前驱跳过x，还把x自己的指针改成指回原来的前驱，这样查找即使停在已删除的x上，也能沿反向指针回来，继续往前走。
在无锁跳表中，插入操作的线性化点在哪里？
插入操作的线性化点在第0层（最底层）的那次CAS成功，即CAS(preds[0]->next[0], succs[0], n)。一旦这个CAS成功，节点就成为了集合成员，上层链表的链接只影响查找速度，不影响正确性。
LevelDB和RocksDB的memtable为什么不需要处理删除和内存回收问题？
因为LevelDB和RocksDB的memtable不支持删除节点，删除操作通过写入一条墓碑记录来实现，这本身也是一次插入。因此，标记、帮助和内存回收问题全部消失，只需要处理插入的发布顺序。
无锁跳表一定比加锁跳表快吗？实验数据怎么说？
不一定。HLLS论文在读多写少负载下测得两者性能相当；本文在3个物理核上的测量显示，两者吞吐都随线程数上升，差距在11%到47%之间，具体取决于负载和数据规模。
