电商网站设计风格,网站建设 php,给公司做网站这个工作怎么样,凡科网站建设7个基本流程ConcurrentSkipListMap的源码很复杂#xff0c;但它的核心思想和实现方式非常值得深入学习。下面会提炼出它的关键结构#xff0c;并重点解释最复杂、最值得学习的方法#xff0c;以及它在并发和跳表结合上的独特用法。 1. 关键结构
跳表#xff08;Skip List#xff09;…ConcurrentSkipListMap的源码很复杂但它的核心思想和实现方式非常值得深入学习。下面会提炼出它的关键结构并重点解释最复杂、最值得学习的方法以及它在并发和跳表结合上的独特用法。 1. 关键结构
跳表Skip List基本结构
NodeK,V跳表的基础节点存储key、value和指向下一个节点的指针next。IndexK,V跳表多级索引节点存储指向下方索引down和右侧索引right的指针每个Index节点关联一个Node节点。head顶层索引节点Index类型通过down可以访问到底层。
static final class NodeK,V {final K key;V val;NodeK,V next;...
}
static final class IndexK,V {final NodeK,V node;final IndexK,V down;IndexK,V right;...
}其他核心成员
comparator可选的比较器决定排序规则。LongAdder adder高效计数器记录元素数量。VarHandle机制用来做原子操作支持无锁CASCompare and Swap修改指针和数据。 2. 并发跳表的独特实现
跳表的多层索引 跳表结构使得查找、插入、删除的平均复杂度为O(log n)而且天然适合并发遍历。 索引节点(Index)和底层节点(Node)分离每次变更都只需CAS原子操作避免全局锁。
无锁设计Lock-Free
主要依赖CAS原子操作比如 NEXT.compareAndSet、VAL.compareAndSet避免传统锁带来的性能瓶颈。节点删除采用“懒惰删除”“帮助删除”即遇到被标记为删除的节点时顺便帮忙物理移除所有线程协作完成清理。 doPut插入/更新元素
这是插入和更新的核心方法难点在于
多线程场景下如何安全地插入节点和建立索引如何在概率意义下决定新节点的高度索引层数如何处理并发插入冲突和失败的重试。
简化流程
找到插入位置的前驱节点findPredecessor。通过CAS原子操作插入新节点按概率1/4决定是否生成索引节点并逐层向上插入索引addIndices若有必要增加跳表高度。 doPut 方法是 ConcurrentSkipListMap 的核心插入方法实现了线程安全的键值对插入操作。以下是该方法的详细分析
1. 方法签名与参数说明
private V doPut(K key, V value, boolean onlyIfAbsent)key: 要插入的键value: 要插入的值onlyIfAbsent: 如果为 true仅在键不存在时插入如果为 false则替换已存在的值返回值: 如果是新插入返回 null如果是替换则返回旧值
整体执行流程
第一阶段初始化检查与跳表遍历
if (key null)throw new NullPointerException();
Comparator? super K cmp comparator;
for (;;) { // 无限循环直到操作成功IndexK,V h; NodeK,V b;VarHandle.acquireFence(); // 内存屏障确保可见性关键知识点
使用 无限循环 实现 乐观锁 机制VarHandle.acquireFence() 提供 内存可见性保证类似于 volatile 读操作
第二阶段跳表初始化
if ((h head) null) { // 跳表未初始化NodeK,V base new NodeK,V(null, null, null); // 创建哨兵节点h new IndexK,V(base, null, null); // 创建顶层索引b (HEAD.compareAndSet(this, null, h)) ? base : null; // CAS 操作
}设计要点
使用 哨兵节点 简化边界处理通过 CAS 操作 保证线程安全的初始化如果 CAS 失败说明其他线程已完成初始化重新开始循环 第三阶段跳表索引层遍历
for (IndexK,V q h, r, d;;) { // 从顶层开始遍历while ((r q.right) ! null) { // 水平向右遍历NodeK,V p; K k;if ((p r.node) null || (k p.key) null || p.val null)RIGHT.compareAndSet(q, r, r.right); // 清理已删除节点else if (cpr(cmp, key, k) 0)q r; // 继续向右elsebreak; // 找到插入位置}if ((d q.down) ! null) {levels; // 记录下降层数q d; // 向下一层}else {b q.node; // 找到基础层的前驱节点break;}
}跳表遍历原理
水平遍历在当前层级向右查找直到找到大于等于目标键的位置垂直下降当无法继续右移时下降到下一层级清理机制遍历过程中清理已标记删除的节点维护数据结构完整性
基础层节点插入
寻找精确插入位置
for (;;) { // 在基础层寻找插入点NodeK,V n, p; K k; V v; int c;if ((n b.next) null) {if (b.key null) // 空跳表进行类型检查cpr(cmp, key, key);c -1;}else if ((k n.key) null)break; // 遇到标记节点重新开始else if ((v n.val) null) {unlinkNode(b, n); // 清理已删除节点c 1;}else if ((c cpr(cmp, key, k)) 0)b n; // 继续向右查找else if (c 0 (onlyIfAbsent || VAL.compareAndSet(n, v, value)))return v; // 找到相同键根据 onlyIfAbsent 决定是否更新执行 CAS 插入
if (c 0 NEXT.compareAndSet(b, n, p new NodeK,V(key, value, n))) {z p; // 记录新插入的节点break;
}CAS 插入机制
原子性地将新节点插入到 b 和 n 之间如果 CAS 失败说明其他线程修改了链表结构需要重新查找 来详细解释这段看似复杂的 null 处理逻辑。这些设计都与 ConcurrentSkipListMap 的并发删除机制 密切相关。
1. 类型检查逻辑分析
if (b.key null) // if empty, type check key nowcpr(cmp, key, key);为什么需要这个检查
这个看似奇怪的 cpr(cmp, key, key) 调用实际上是一个 提前类型检查
触发时机当跳表为空时b.key null 表示 b 是哨兵节点目的提前验证 key 的类型是否与比较器兼容机制通过自比较触发潜在的 ClassCastException
// cpr 方法的实现逻辑
static int cpr(Comparator c, Object x, Object y) {return (c ! null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}如果 key 类型不兼容这里会立即抛出异常避免在后续操作中出现问题。
2. 并发删除机制的核心区别
key null vs val null 的本质区别
在 ConcurrentSkipListMap 中这两种 null 状态代表 删除过程的不同阶段
状态含义处理方式原因key null标记节点表示前一个节点正在被删除break 重新开始结构不稳定无法安全插入val null逻辑删除节点已被标记删除但仍在链表中unlinkNode() 物理删除可以安全地完成物理删除
3. 并发删除的三阶段过程
根据代码注释ConcurrentSkipListMap 采用三阶段删除
阶段 1逻辑删除
// 将节点值设为 null标记为已删除
VAL.compareAndSet(n, v, null)阶段 2插入标记节点
// 插入一个 keynull 的标记节点
NEXT.compareAndSet(n, f, new NodeK,V(null, null, f))阶段 3物理删除
// 将前驱节点直接指向后继节点
NEXT.compareAndSet(b, n, p)代码逻辑的并发安全考虑
else if ((k n.key) null)break; // cant append; restart
else if ((v n.val) null) {unlinkNode(b, n);c 1;
}为什么 key null 需要重启
结构不稳定遇到标记节点说明正在进行删除操作无法预测不知道删除何时完成链表结构可能随时改变安全策略重新开始遍历等待删除操作完成
为什么 val null 可以继续
状态确定节点已被逻辑删除不会再被修改助人为乐当前线程可以帮助完成物理删除性能优化避免其他线程重复遇到已删除节点
实际执行流程示例
假设有链表A - B - C要删除节点 B
// 初始状态
A.next - B(keyb, valv) - C// 步骤1逻辑删除 B
A.next - B(keyb, valnull) - C
// 此时遇到 valnull执行 unlinkNode// 步骤2插入标记节点
A.next - B(keyb, valnull) - marker(keynull, valnull) - C
// 此时遇到 keynull执行 break 重启// 步骤3物理删除完成
A.next - C这种设计的巧妙在于
渐进式删除避免一次性操作导致的竞争协作式清理多个线程共同维护数据结构完整性无锁设计通过 CAS 操作保证原子性异常安全提前进行类型检查避免后续错误
这就是为什么同样是 null但处理方式完全不同的根本原因——它们代表了并发删除过程中的不同状态需要采用不同的应对策略来保证线程安全。 索引层构建概率性
随机决定是否添加索引
int lr ThreadLocalRandom.nextSecondarySeed();
if ((lr 0x3) 0) { // 1/4 概率添加索引int hr ThreadLocalRandom.nextSecondarySeed();long rnd ((long)hr 32) | ((long)lr 0xffffffffL);int skips levels; // 从当前层级开始构建索引构建索引链
IndexK,V x null;
for (;;) { // 构建垂直索引链x new IndexK,V(z, x, null); // 创建新索引节点if (rnd 0L || --skips 0)break;elsernd 1; // 左移判断下一层
}跳表索引构建原理
概率性构建每层索引节点数量约为下层的 1/2几何分布通过位运算实现高效的概率计算最大层数限制最多构建 62 层索引 添加索引到跳表
if (addIndices(h, skips, x, cmp) skips 0 head h) {// 需要增加新的顶层IndexK,V hx new IndexK,V(z, x, null);IndexK,V nh new IndexK,V(h.node, h, hx);HEAD.compareAndSet(this, h, nh);
}关键技术特性
并发安全机制 Lock-Free 设计全程无锁使用 CAS 操作保证原子性 内存屏障使用 VarHandle.acquireFence() 确保内存可见性 重试机制失败时重新开始保证最终一致性
性能优化策略 惰性删除标记删除而非立即物理删除 清理机制遍历过程中顺便清理已删除节点 概率性索引平衡查找效率和空间开销
数据结构维护
动态层级调整根据需要增加新的索引层索引一致性确保索引层与基础层数据一致并发清理在操作过程中维护结构完整性 为什么需要标记节点并发链表删除的根本问题
详细解释为什么ConcurrentSkipListMap不能直接CAS删除而必须使用标记节点的分步删除策略。
如果我们尝试直接删除
// 危险的直接删除方式
NEXT.compareAndSet(A, B, C); // 直接让A指向C这会导致严重的并发竞态条件
// 初始状态
A - B - C - D// 线程T1想删除B读取了B.next C
// 线程T2在B和C之间插入了新节点X
A - B - X - C - D// T1执行CASA.next从B改为C
A - C - D // X节点永远丢失unlinkNode的三步删除策略
查看unlinkNode的实现
static K,V void unlinkNode(NodeK,V b, NodeK,V n) {if (b ! null n ! null) {NodeK,V f, p;for (;;) {if ((f n.next) ! null f.key null) {p f.next; // 步骤1发现已有标记节点break;}else if (NEXT.compareAndSet(n, f,new NodeK,V(null, null, f))) {p f; // 步骤2插入标记节点break;}}NEXT.compareAndSet(b, n, p); // 步骤3绕过被删节点}
}为什么分步删除是必需的 无锁并发的本质需求
原子性保证每个CAS操作都是原子的但组合操作不是顺序依赖必须先锁定被删节点的next指针再修改前驱节点状态可见性中间状态必须对所有线程可见和可处理
对比有锁方案
// 如果用锁但ConcurrentSkipListMap是无锁的
synchronized(lock) {A.next B.next; // 可以原子完成
}但无锁环境下我们只能依赖CAS的原子性因此必须分解为原子步骤。
实际运行示例
// 时刻T1初始状态
A.next - B(key5, valhello) - C(key10)// 时刻T2线程1开始删除B执行逻辑删除
A.next - B(key5, valnull) - C(key10)// 时刻T3线程2试图在B后插入节点失败
// 因为发现B.valnull执行unlinkNode帮助删除// 时刻T4插入标记节点
A.next - B(key5, valnull) - marker(keynull, valnull) - C(key10)// 时刻T5物理删除完成
A.next - C(key10)findPredecessor查找前驱节点
负责自顶向下查找过程中顺便帮忙清理已删除节点的索引保证跳表结构整洁。支持并发删除时的“协作清理”。
核心逻辑 private NodeK,V findPredecessor(Object key, Comparator? super K cmp) {IndexK,V q;VarHandle.acquireFence();if ((q head) null || key null)return null;else {for (IndexK,V r, d;;) {while ((r q.right) ! null) {NodeK,V p; K k;if ((p r.node) null || (k p.key) null ||p.val null) // unlink index to deleted nodeRIGHT.compareAndSet(q, r, r.right);else if (cpr(cmp, key, k) 0)q r;elsebreak;}if ((d q.down) ! null)q d;elsereturn q.node;}}} VarHandle.acquireFence() 的作用
VarHandle.acquireFence() 在此处的作用是
保证可见性确保读取到其他线程对 head 字段的最新修改防止重排序确保后续的读操作基于一致的内存状态性能优化避免使用过多 volatile 字段的开销维护弱一致性为无锁数据结构提供必要的内存语义保证
这是 ConcurrentSkipListMap 实现高性能并发访问的关键技术之一。
acquireFence()确保在屏障之后的所有读操作不会被重排序到屏障之前 主要用于确保读取操作能看到最新的写入值是构建更高级并发原语的基础工具。releaseFence(): 确保屏障之前的所有写操作对其他线程可见类似于 StoreStore LoadStorefullFence(): 同时提供获取和释放语义类似于 volatile 变量的读写 内存屏障的核心作用
1. 确保 head 字段的最新值可见
VarHandle.acquireFence();
if ((q head) null || key null)return null;关键问题head 字段可能被其他线程修改如在 doPut、tryReduceLevel 等方法中需要确保当前线程能看到最新的值。
解决方案acquireFence() 提供了类似 volatile 读 的语义确保
读取到 head 的最新值防止编译器和处理器的指令重排序 2. 建立 happens-before 关系
根据代码注释中的设计说明 This form of fence-hoisting is similar to RCU and related techniques... It minimizes overhead that may otherwise occur when using so many volatile-mode reads. 设计思路
避免将每个字段都声明为 volatile通过在关键方法入口处放置内存屏障建立全局的内存可见性保证
为什么选择 acquireFence 而非其他屏障
acquireFence 的特性
// acquireFence 等价于
// 确保屏障之前的读操作不会被重排序到屏障之后
// 提供 acquire 语义类似于 volatile 读或 synchronized 进入与 ConcurrentSkipListMap 的无锁设计契合
无锁遍历findPredecessor 是纯读操作不需要修改数据弱一致性允许看到稍微过时的数据但必须是一致的快照性能优化比使用多个 volatile 字段开销更小
场景分析
场景 1读取跳表头节点
// 其他线程可能正在执行
HEAD.compareAndSet(this, h, nh); // 在 doPut 中更新头节点// 当前线程需要确保看到最新的 head 值
VarHandle.acquireFence();
if ((q head) null || key null) // 必须是最新值场景 2确保索引结构一致性
// 确保读取的索引链是一致的状态
while ((r q.right) ! null) {NodeK,V p; K k;// 这些字段的读取都受到屏障保护if ((p r.node) null || (k p.key) null || p.val null)对比其他方法中的类似用法
可以看到相同的模式
doGet 方法
VarHandle.acquireFence();
if (key null)throw new NullPointerException();findLast 方法
VarHandle.acquireFence();
if ((q head) null)break;doRemove删除元素
先逻辑删除将val设为null再插入一个“marker”节点做物理删除最后CAS更新前驱的next指针。删除后会考虑是否需要降低跳表高度tryReduceLevel。 /*** Main deletion method. Locates node, nulls value, appends a* deletion marker, unlinks predecessor, removes associated index* nodes, and possibly reduces head index level.** param key the key* param value if non-null, the value that must be* associated with key* return the node, or null if not found*/final V doRemove(Object key, Object value) {if (key null)throw new NullPointerException();Comparator? super K cmp comparator;V result null;NodeK,V b;outer: while ((b findPredecessor(key, cmp)) ! null result null) {for (;;) {NodeK,V n; K k; V v; int c;if ((n b.next) null)break outer;else if ((k n.key) null)break;else if ((v n.val) null)unlinkNode(b, n);else if ((c cpr(cmp, key, k)) 0)b n;else if (c 0)break outer;else if (value ! null !value.equals(v))break outer;else if (VAL.compareAndSet(n, v, null)) {result v;unlinkNode(b, n);break; // loop to clean up}}}if (result ! null) {tryReduceLevel();addCount(-1L);}return result;} doRemove 方法是 ConcurrentSkipListMap 中的核心删除实现它完美体现了之前提到的三阶段删除策略。
这个方法实现了无锁并发删除支持两种删除模式
精确删除value ! null 时只有当节点值完全匹配时才删除键删除value null 时删除指定键的节点不关心值
核心执行流程
外层循环定位目标节点
outer: while ((b findPredecessor(key, cmp)) ! null result null) {关键设计
使用 findPredecessor 找到目标键的前驱节点外层循环处理并发冲突重试result null 确保删除成功后不再重试
内层循环执行删除操作
内层循环处理多种并发场景每个分支对应不同的节点状态
场景1链表结束
if ((n b.next) null)break outer;前驱节点后没有节点目标不存在
场景2遇到标记节点
else if ((k n.key) null) break;遇到 key null 的标记节点 表示链表结构正在变化需要重新开始
场景3遇到已删除节点
else if ((v n.val) null)unlinkNode(b, n);遇到 val null 的逻辑删除节点 助人为乐帮助完成物理删除
场景4继续搜索
else if ((c cpr(cmp, key, k)) 0)b n;目标键更大向后移动搜索
场景5目标不存在
else if (c 0)break outer;目标键更小说明不存在该键
场景6值不匹配精确删除
else if (value ! null !value.equals(v))break outer;键匹配但值不匹配删除失败
场景7执行删除核心逻辑
else if (VAL.compareAndSet(n, v, null)) {result v;unlinkNode(b, n);break;
}三阶段删除的具体实现
阶段1逻辑删除
VAL.compareAndSet(n, v, null)原子操作将节点值设为 null标记删除其他线程看到 val null 知道节点已删除CAS失败重试如果失败说明有并发修改继续循环
阶段23物理删除
unlinkNode(b, n);调用 unlinkNode 完成后续的标记节点插入和链表断开。
删除后的清理工作
if (result ! null) {tryReduceLevel(); // 尝试减少跳表层级addCount(-1L); // 更新元素计数
}虽然 doRemove 没有直接清理索引但通过以下机制保证索引一致性
遍历时清理其他方法如 findPredecessor、doGet遍历时会清理指向已删除节点的索引层级缩减tryReduceLevel() 在顶层索引为空时减少跳表高度 unlinkNode 方法详解
unlinkNode 方法是 ConcurrentSkipListMap 实现中用于物理删除节点的关键方法。
unlinkNode 方法的主要任务是将已逻辑删除的节点val null从链表中完全移除。它通过以下步骤实现
插入标记节点在删除节点的 next 指针上插入一个标记节点防止其他线程向该节点追加新节点。断开前驱节点将前驱节点的 next 指针直接指向删除节点的后继节点完成物理删除。 /*** Tries to unlink deleted node n from predecessor b (if both* exist), by first splicing in a marker if not already present.* Upon return, node n is sure to be unlinked from b, possibly* via the actions of some other thread.** param b if nonnull, predecessor* param n if nonnull, node known to be deleted*/static K,V void unlinkNode(NodeK,V b, NodeK,V n) {if (b ! null n ! null) {NodeK,V f, p;for (;;) {if ((f n.next) ! null f.key null) {p f.next; // already markedbreak;}else if (NEXT.compareAndSet(n, f,new NodeK,V(null, null, f))) {p f; // add markerbreak;}}NEXT.compareAndSet(b, n, p);}}
核心执行流程
1. 检查参数
if (b ! null n ! null) {确保 b前驱节点和 n要删除的节点不为空。
2. 插入标记节点
NodeK,V f, p;
for (;;) {if ((f n.next) ! null f.key null) {p f.next; // already markedbreak;}else if (NEXT.compareAndSet(n, f, new NodeK,V(null, null, f))) {p f; // add markerbreak;}
}检查是否已标记如果删除节点的 next 指针指向的节点 key 为 null说明已经有一个标记节点存在。插入新标记节点如果 next 指针没有标记节点则使用 NEXT.compareAndSet 原子操作插入一个新的标记节点。
3. 断开前驱节点
NEXT.compareAndSet(b, n, p);将前驱节点 b 的 next 指针指向删除节点的后继节点 p完成物理删除。 总结
结合并发与跳表的独特之处
极致的无锁化设计所有节点和索引的增删都用CAS而非锁实现高并发下的线程安全。懒惰删除和协作清理任何线程遇到“已删除节点”时都会顺手帮忙清理避免“悬挂节点”影响性能。跳表高度动态调整插入时随机决定高度删除时尝试降低高度避免高度失控。弱一致性遍历迭代器弱一致允许并发修改时遍历不会抛异常适合高并发场景。
