Java并发进阶系列：深度讨论高并发跳表数据结构ConcurrentSkipListMap的源代码实现（下）

文章说明：因为CSM解析内容较多，因此全文分为“深度讨论高并发跳表数据结构ConcurrentSkipListMap的源代码实现（上）”和“深度讨论高并发跳表数据结构ConcurrentSkipListMap的源代码实现（下）”两篇文章上篇：CSM数据结构设计原理、doGet、doPut核心方法解析下篇：doRemove核心方法解析、总结remove方法：删除操作的设计原理这里先介绍Doug Lea在源代码注释给出算法设计说明：n.helpDelete(b,f)的设计原理上一篇文章的doGet、doPut方法中都有涉及到遇到被标记”删除“的节点时都会加入n.helpDelete(b,f)的处理逻辑，* In addition to using deletion markers, the lists also use * nullness of value fields to indicate deletion, in a style * similar to typical lazy-deletion schemes. If a node's value is * null, then it is considered logically deleted and ignored even * though it is still reachable. This maintains proper control of * concurrent replace vs delete operations -- an attempted replace * must fail if a delete beat it by nulling field, and a delete * must return the last non-null value held in the field. (Note: * Null, rather than some special marker, is used for value fields * here because it just so happens to mesh with the Map API * requirement that method get returns null if there is no * mapping, which allows nodes to remain concurrently readable * even when deleted. Using any other marker value here would be * messy at best.) * n是当前要删除的节点，b是n的前驱节点，f是n的后继节点，开始删除前，(b,n,f)的指向关系如下 * Here's the sequence of events for a deletion of node n with * predecessor b and successor f, initially: * * +------+ +------+ +------+ * ... | b |------| n |-----| f | ... * +------+ +------+ +------+ * * 1. CAS n's value field from non-null to null. * From this point on, no public operations encountering * the node consider this mapping to exist. However, other * ongoing insertions and deletions might still modify * n's next pointer. * * 1、 将删除节点n的value使用cas设成null，表示此刻起，n节点处于待删除状态，虽然其value为null，对于public相关方法如get等，在执行遇到此类型节点时不会将该节点视为有效节点（也即会被跳过处理），但是如果对于正在执行的插入和删除操作的方法来说，可能也可以去更改“此待删除节点n”的后继节点。 * 2. CAS n's next pointer to point to a new marker node. * From this point on, no other nodes can be appended to n. * which avoids deletion errors in CAS-based linked lists. * * +------+ +------+ +------+ +------+ * ... | b |------| n |-----|marker|------| f | ... * +------+ +------+ +------+ +------+ * 2、使用cas将n节点的next字段指向一个marker节点后，从此刻起，任何节点都不会被放在n的后继节点位置，也即不可能出现n-n1、n-n2等，只有n-marker * 3. CAS b's next pointer over both n and its marker. * From this point on, no new traversals will encounter n, * and it can eventually be GCed. * +------+ +------+ * ... | b |-----------------------------------| f | ... * +------+ +------+ * 3、通过cas将b的next指针（越过n节点以及n的后继marker节点）指向f节点，从此刻起，n节点不会被相关操作遍历到，n最终会被GC。可以看出CSM删除操作方面，借用marker节点来实现，将待删除节点的value设为null值来表示该节点处在删除状态但还未真正删除，这种设计风格就像“惰性删除语义(lazy-deletion schemes)”，先标记删，等某个时机再真正执行之。如果CSM的一个节点的value是null，说明该节点在逻辑上已经被删除。以下是remove方法的源代码解析publicVremove(Objectkey){returndoRemove(key,null);//注意只需要比较key即可，不需要考虑value相等才删除！}具体逻辑由doRemove实现finalVdoRemove(Objectkey,Objectvalue){if(key==null)thrownewNullPointerException();Comparator?superKcmp=comparator;outer:for(;;){// 1、和doGet、findNode类似设计，首先找到key的前驱节点for(NodeK,Vb=findPredecessor(key,cmp),n=b.next;;){//Objectv;intc;if(n==null)breakouter;// 经典的(b,n,f)三指针NodeK,Vf=n.next;// 2、n已不是b的后继节点，也即读n节点前后不一致，则重试if(n!=b.next)// inconsistent readbreak;// 3、数据节点n节点被标记为删除状态，那么使用helpDelete把n节点删除，然后重试。if((v=n.value)==null){// n is deletedn.helpDelete(b,f);break;}// 4、key的前驱节点b被标记删除状态，只能重试，读取新的bif(b.value==null||v==n)// b is deletedbreak;//5、 给定的key不在数据链表里面，直接结束if((c=cpr(cmp,key,n.key))0)breakouter;//6、 给定的key比当前数据节点n还大，那么更新b、n向右继续检索if(c0){b=n;n=f;continue;}// 以下找到与key相等的n节点//7、doRemove的入参value默认是null，因此以下会被跳过，若指定value，则还需判断给定的value和当前找到n.value是否相等if(value!=null!value.equals(v))breakouter;//8、执行流运行到这里，说明满足删除n节点的条件也即key=n.key,n就是要删除的目标数据节点，因此将n.value设为null，cas失败则重试，注意这是是标记删除，不是直接把n节点删除。if(!n.casValue(v,null))break;/*9、执行流运行到这里，说明n成功被标记删除状态 条件1：将 b → n → f 变成 b → n → marker → f 条件2：将 b → n → f 变成 b → f 如果条件1CAS失败或者条件2CAS失败，都会调用findNode(key)来删除数据节点n */if(!n.appendMarker(f)||!b.casNext(n,f))findNode(key);// retry via findNodeelse{/*10、不妨假设条件1成立，也即将 b → n → f 变成 b → n → marker → f 需要n节点上方的索引节点都清除（包括清除索引节点的前后指向关系），恰好findPredecessor就是在索引层干这事。 */findPredecessor(key,cmp);// clean indexif(head.right==null)tryReduceLevel();}@SuppressWarnings("unchecked")Vvv=(V)v;returnvv;}}returnnull;}虽然在doGet方法中有给出findPredecessor，它是用在查询场景中，而在本小节中findPredecessor被用来删除n节点对应的上方索引节点场景中，现在结合上方doRmove的源代码理解，将更能掌握其中设计逻辑。privateNodeK,VfindPredecessor(Objectkey,Comparator?superKcmp){if(key==null)thrownewNullPointerException();// don't postpone errorsfor(;;){for(IndexK,Vq=head,r=q.right,d;;){//在当前索引层检索，只要不是来到链表尾部，就继续在该层里面遍历if(r!=null){NodeK,Vn=r.node;Kk=n.key;// 此处对应的是上方doRemove内部将n.value标记为null的情况if(n.value==null){/* 既然数据层的n节点被删除，那么n节点对应上方关联的索引节点r也要删除: 索引层：将 q → r → r.right 变成 q → r.right */if(!q.unlink(r))break;// restart// 索引节点r成功删除后，将r指向q的新right节点，此时q → r 两个索引节点都处于正常状态，继续下一轮遍历。r=q.right;// reread rcontinue;}// 继续在该层索引向右检索，直到cpr(cmp, key, k) =0if(cpr(cmp,key,k)0){q=r;r=r.right;continue;}}// 当q位于第1层索引层位置时，此时q.down指向的是idx=null，因此可退出，到此从入口head到出口q.down=null沿途找到的与n对应的每层索引节点idx都被删除掉。可直接退出if((d=q.down)==null)returnq.node;// 执行流运行到这里，说明还未到达第1层索引层，以上逻辑完成当前层的idx节点删除，那么继续需要处理n节点对应的更低层的索引节点idx。q=d;r=d.right;}}}因此在doRemove方法的角度来看， findPredecessor(key, cmp) 实际意义是单纯用于clean index，而不是为key找到前驱节点b这么简单，这里的clean index功能就是Doug Lea提到的“side-effect”，也即下面这句话的含义：Callers rely on this side-effect of clearing indices to deleted nodes.doRemove作为调用方，能够从调用findPredecessor过程获得额外收益：清除那些已被标记为“删除状态”的数据节点上方对应的每层索引节点idx。关于doRemove的图解这里不再给出，想要深入理解的同学务必自行将删除逻辑对应的图做出来，否则将难以理解其过程的动态处理。tryReduceLevel()方法在doRemove方法的第10个逻辑中，清理完索引节点后，还需要检查是否需要“降层处理”：else{/*10、不妨假设条件1成立，也即将 b → n → f 变成 b → n → marker → f 需要n节点上方的索引节点都清除（包括清除索引节点的前后指向关系），恰好findPredecessor就是在索引层干这事。 */findPredecessor(key,cmp);// clean indexif(head.right==null)tryReduceLevel();