highlight: a11y-dark

1. 术语

1.1 non-blocking, lock-free, wait-free

processor: 可以理解为 竞争一个共享容器的一个例程(一般是线程的形式, 或者coroutine in thread), 特点是 "有快有慢", 其中慢处理的原因可能是: 锁抢占, 缺页中断, 缓存未命中, 极端情况下, 慢例程可能慢到没有任何进展(in progress). 而快的例程就是满足执行条件, 并且很快就能执行完

blocking: 如果一个很慢的例程持久没有进展, 会导致快的例程被阻塞(慢的例程占着茅坑不拉屎)，注意，基于锁的实现也可能是non-blocking的，还是主要看实现，比如snapshot就可以在使用锁的前提下，读写并行.

non-blocking: non-blocking只是一个概念, 其实现方式有很多, 比如直接让快的例程把慢的例程的工作抢过来完成了, 或者慢例程自动放弃执行, 总之结果在并发场景下, 是不会有任何一个processor被其他老乌龟阻塞住.

lock-free: lock-free指不使用 "lock" 这个并发原语(primitive), lock-free不一定是non-blocking的, lock-free也是一个概念，取决于实现, 实现决定了是不是non-blocking的，一般的CAS都不是blocking的。关键在于slower会不会让faster永远无法取得进展.

wait-free: wait-free也是一个概念, 实现上能达成这个概念就行. 但难点在于, 要求越高的概念, 想要满足"可读性, 易懂性"的实现就越难. 所以目前也在一直研究咋写出一个好的wait-free的数据结构, wait-free一定是non-blocking的，不会存在饿死, 任何processor都会取得进展(in-process)并在有限步(a bounded number of time steps)完成工作

1.2 CAS

CAS就是一个指令级别的原子操作 compare_and_swap

CAS(shared_memory_addr, expected_value, new_value)

   // 这个lock是指令级别的, 性能很高
   locked {
       if (*shared_memory_addr == expected_value)
           *shared_memory_addr = new_value
   }

ABA问题: 考虑下面一个timeline

    // processor t1 CAS(addr, A, B)  if A then swap to B atomically
    // processor t2 CAS(addr, B, A)  if B then swap to A atomically
    // processor t3
    
    while (!CAS(addr, A, B)) {
        // t3希望把addr上存的内容从A换成B，他要检查addr上是不是还是A
        
        // 由于无锁实现, 我们假设这里t3发了一会呆，与此同时另外两个processor和t3并发执行
        // 此时t1和t2执行，addr从A换成B，然后换成了A
        
        // 对t3而言，感觉好像啥也没发生, 他并不知道中间经历了"ABA"中的"B"这个过程
    }

ABA解决

• 版本号

    // processor t1 CAS(addr, A, B, v1) if A then swap to B atomically and v1 = v2(原子)
    // processor t2 CAS(addr, A, B, v1) if B then swap to A atomically and v2 = v3
    
    while (!CAS(addr, A, B, v1)) {
        // 如果出现ABA, 再次获取version就不是v
        assert(getVersion() == v1);
    }

1.3 Linearizability

这个概念可以和BASE里的软状态(soft state)类比，或者在分布式系统里有"线性一致性", 其实线性的概念就是这个Linearizability。

简而言之，我们考虑一个执行流

operatorA -> operatorB -> operatorC ... -> operatorN

如果所有processor观察到的都是这个执行流，就不存在"误解"，但对于下面的执行流

operatorA -> operatorB                   end state B -> operatorC
                |____middle state B______|

对于操作B，整个队列的状态会经过一个中间状态B，以dequeue操作为例，整个操作的生效(take effect)意味着指针移动, 并且头结点被释放。 对于middle state B, 可能是一个"头结点被释放，但指针没移动"的软状态，其他processor如果能访问到这个状态， 就可能出现问题。

或者构造一个dequeue和enqueue的流，使得不同的processor在某一时刻观察到的队列数量(不同队列的数量定义方法也不同)不同，就是违背了线性。

在本算法中，由于插入总是插到尾部，任何processor如果发现tail后面还有东西，就会帮助移动tail，也就是，processor如果发现某个只插入了，但是指针没动的soft state，会帮助处理掉这个soft state。而对于删除操作，我们选择的是先移动指针，后释放。因为dequeue的语义是"移动指针就意味着逻辑删除，free意味着物理删除"。也不存在不同processor看到的队列状态不一样的问题。

1.4 Liveness

算法的"活性"，简单理解就是证明算法是"non-blocking"的。 我们证明的方向可以从"non-blocking"的定义入手，证明任何processor不会无限的在某一步上重试。

注意: 尽管CAS操作不涉及到锁，但考虑CAS的本体是一个while循环，如果其他processors会让某个processor永远停滞不前，那我们说尽管这个算法是lock-free的，但并不是non-blocking的。

还是仅证明lock-free算法的Liveness

失败点1: 同时插入

CAS的关键点: 我的失败意味着别人成功，而不是如果我失败了，我让别人也没法成功

下面是一个可能的timeline，还有一种可能processor2在E13也失败了，但无所谓。

processor的流转是

1. 如果tail没被修改，自己就插入
2. 如果tail被修改了，自己尝试移动tail，如果tail已经被移动了，自己就退出。

当前processor的失败，一定意味着其他processor取得了进展(in progress)，这是证明算法为non-blocking的重要一环。 那有没有一种可能，某个processor非常倒霉，每次想干啥都被其他的processor干完了，自己一直空转。理论上有，但概率很低。但不要混淆"non-blocking"的定义，我们证明"non-blocking"只需要证明这个空转是有限步数的，不像死锁，如果真deadlock了，此时想要取得进展就需要"infinity-steps"。

上面的问题其实可以列为"starvation-free"，也就是算法不会饿死，non-blocking不一定说不会饿死某个processor，如果想要starvation-free可能需要设计调度上的细节。

// timeline
// processor1 E5
// processor2 E5
// processor1 完成enqueue
// processor2 在E7失败，进入E13，尝试移动tail

如果processor2 在E7失败，说明其他processor完成了插入。
如果processor2 在E13失败，说明其他processor完成了tail的移动。
如果processor2 在E9失败，说明其他processor完成了插入

失败点2: 同时dequeue或者enqueue和dequeue混着来。

我们要证明"某个processor无论是在enqueue还是dequeue失败，都是因为其他processor在enqueue, dequeue取得进展导致的"

其实失败只发生在CAS上，而且想进入这个失败还需要满足好几个if。所以我们总结下

1. D5为true，但是在D13失败了。如果这样子失败，则说明其他processor一定已经dequeue成功了。
2. D5和D6都为true，但是在D10失败了。这样子失败，则说明 如果其他的processor正在enqueue，则它会导致tail移动而导致D10失败，如果其他的processor正在dequeue，则可能其他的processor会让tail赶进度而导致tail变化，导致本processor失败。因此，无论其他processor是在入队还是出队，如果我们失败了，肯定意味着别人成功了。

1.5 critical path

在衡量并发算法性能时，我们其实只需要求出 所有processor里执行时间最长的那个，这个就是关键路径。

比如对于100w个操作，分配给4个核，理论上每个核的执行时间为 25w个操作 * 平均每个操作的时间

平均每个操作的时间 = 操作本身时间 + 用户处理时间 + 算法overhead

算法overhead 正比于 processors的个数，操作本身时间和用户处理时间在平稳运行的系统中一般不变。

2. 并发容器应该具备的特征

todo: 待更新，好几个并发容器都是和以前的容器斗蛐蛐，然后取长补短+自己的设计，所以每个设计都有每个设计的特征...

• 应用方面

  • 需要实用(in practice), 如果一个并发容器的概念提出后，理解起来和实现起来非常难，用起来也非常难，尽管实现了，但不是好的实现(类比paxos和raft的斗蛐蛐)

• 正确性

  • 在各种并发环境(传统的就是多核多线程, IBM有一种"分配processor"的技术, dedicated processors, 简单理解就是"绑核")下，都能不出现问题(首先不能存在race condition，其次根据需求，需要满足类似线性(linearizable)等特性, 二者一个是required, 一个是optional的

• 通用性

3. 之前研究的斗蛐蛐

4. 算法

实际上这个算法是借鉴了上面的很多实现，然后把一些有问题的修改一些。 作者给出了两个版本，实现无阻塞的并发队列，一个是基于两个锁实现的，另一个是基于CAS实现的

在无锁版本中:

• 数据结构上选择了Valois的单向链表，附带头指针和尾指针。解决了tail可能落后的问题
• 基于counter指针解决了ABA问题，相比Prakash的快照解决方案更简单
• 使用Treiber的算法实现了一个 非阻塞的空闲列表(free-list) ?用于内存管理

4.1 正确性

注意: 原文同时论证了两个算法(lock-free和double-locks)的, 我们这里主要看无锁的实现

无锁链表的性质如下:

1. linkedlist 不会中断
2. 唯一的插入方法是尾插法(所以该并发实现会用做一个FIFO的队列)
3. 唯一的删除方法是头删法(说白了不支持随机插入和随机删除)
4. Head总是指向链表首个node
5. Tail未必指向最后一个node，但一定指向链表中的结点(不会指向已经被dequeue的结点), 用于解决Tail的lag behind问题(算法实现保证了Tail要么指向最后一个结点，要么指向倒数第二个结点)

在我们后面论证实现时, 需要着重来看实现是如何保证下面的Reduction成立的

推论(Reduction):

1. 为了保证链表不中断(某个存在于链表的结点被free了), 所以需要 (1) 只有node被free之前, 其next指针才会被设置为null (2) 只会删除头结点。
2. 无锁版本中, Tail不严格指向最后一个结点, 但保证Tail不会指向链表外的结点(Property 5), 所以为了保证Property 3, 需要在插入时额外处理: 插入仅在结点的next为null的时候成功, 根据Property 1, 既然链表不会中断, 所以next为null的结点的肯定是唯一的, 并且一定是链表的最后一个node
3. 由于Head始终指向链表首个结点, 所以删除时肯定不会删叉劈(因此, 实现上需要保证这一点)
4. Head指针的移动总和删除挂钩: 如果对Head执行了CAS(让Head指向下一个node), 就应该认定Head位置上的node是被删除的
5. Tail始终不会落后于Head, Tail只是说 最终Tail会收敛到链表最后一个结点, 在某一时刻Tail可能位于倒数第二个node上，而且Tail不可能在Head的前面(一顿删然后在某一时刻, 某个processor发现Tail反而位于Head前面, 此时这里的Tail肯定指向被删除的结点, 我们的实现需要杜绝这个问题)

我们简单归纳一下上面的推论

1. 链表不断
2. 插入操作保证插到最后
3. Head总是指向头
4. 移动Head就等于删了原Head对应的node
5. Tail不落后于Head

然后看算法, 重点理解算法的实现是怎么保证上面5条的

1. E5 获取队列里的Tail指针, 要注意此时的Tail不一定是最后一个结点
2. E5-E7可能有多个processor一起进入, 大家可能都拿到相同的Tail, 实现了同样的检查, 但只有一个processor能完成CAS操作, 把新的node插入tail并保证一定插入到最后
3. E8-E10实际上是对应了Reduction2: 在插入时额外检查, 保证插到最后
4. E13对应的case是: processor1完成了插入, processor2负责推进tail指针. 理论上完成插入的processor1会在E17推进tail指针, 但我们要理解 推进tail指针这个操作很可能被某个非enqueue的processor做了, 对于enqueue的processor也没啥问题, 因为他发现tail指针已经被推进之后, CAS失败就退出了, 我们观察到E17的CAS是不带重试的, 如果发现tail已经被推进了, 直接走人.

这里有几个case需要理解

nxt := Q->head.next

1. Q->head == Q->tail && nxt != null
此时可能的情况是, Q->tail还没同步到队列尾, Q->tail前移

   node->next             node->next
    ⬆️           处理后     ⬆️     ⬆️
 head,tail                head  tail
 
 此时链表为空，不处理
 2. Q->head == Q->tail && nxt == null
   node
    ⬆️
 head,tail
 
 删除结点
 这里的dequeue的含义是: 删除旧的head，然后返回新head的值???
 注意下, 我们一般理解dequeue应该是 删除旧head然后返回这个head的值
 本例中这么设计可能是因为, 我们在初始化队列时，填充了一个dummyNode
 所以，当第一个元素enqueue时，如果我们删哪个返回哪个，就会得到一个没意义的dummynode
 如果删哪个返回下一个，就会得到真正的值，同时被删除结点的下一个充当dummynode.
 
 这里违背常识的一点是，在我们常规使用 "伪链表头" 解决链表问题时，我们的dummynode实际上是不动的
 但是本算法里，dummynode随着dequeue而不断的free，然后换成新的dummynode.

1. D2获取head指针, 不同于Tail，Head此时一定指向首个结点, 根据Property4, 不需要做额外处理
2. D7-D10 当head.ptr == tail.ptr时, 算法会停下来专门推进tail的进度, 这里对应Reduction5: tail永远不会落后于head
3. D12返回被删除结点下一个(新head)的值，注意这个设计是为了规避掉一开始插入的dummynode，同时，当元素被删除到只剩一个时，此时有 Q->head == Q->tail && nxt == null, 队列逻辑上为空, 当队列里只有一个node时，队列被视为空，这一点比较关键。而且队列时刻都有一个dummynode，当旧的dummynode被删除后，该node的next值被弹出，此时该node的next成为新的dummynode，并且head时刻指向链表的头，链表头时刻是一个已经逻辑上被dequeue的dummynode
4. D13将Head后移, 根据我们的Reduction4, 此时一定意味着Head被删除了(移Head=删Head)
5. D19 释放被删除结点的空间, 这一点很重要, 也就是对Valois方案的优化

5. 性能

需要关注的点在于

1. 和谁(哪些算法的实现)比
2. 比啥(哪些metric?)
3. 如何保证测试数据真实有效

文章给出了斗蛐蛐的很多算法，包括基于snapshot实现，lock-based的，lock-free但blocking的，以及最原始的一把大锁的并发算法实现。

同时，为了保证真实性，也就是模拟多个processor竞争共享的并发队列，而不是最终的工作都交给一个processor来做，还使用了SGI的特性, 可以分配出指定的处理器个数(processor)和进程个数(process)，这里简单理解为同一个core上有几个thread即可, 因为这个文章是1990年左右发布的，当时的多核和现在的多核多线程还不太一样。

这样的设计充分考虑了真实的并发执行，对于多个processes都在一个processor上执行，会享受到比较高的cache-hit rate，从而使压测数据整体更优。

首先明确下性能的设计

1. 每个enqueue和dequeue操作后面都跟着一个other work，大概6us，用于模拟用户行为

2. 保证多核系统只运行该算法，不运行其他的用户程序

3. 利用SGI的特性，弄出多个processor，不同processor之间是并行的，可以理解为单独享有L1, L2 Cache

4. 在一个processor上跑n个processes，可以认为当n=1时，所有的process都是并行的，当n > 1时，同一个processor上的processes时并发的，文章给出的设计是，在processor=1(单核)的系统上跑，在processors=2和processors=3个核的系统上跑。当processor数上升时，有

   • 由于processor之间L1, L2 Cache不共享，可能有很大的缓存一致性同步开销。
   • 无论是有锁还是无锁实现，必定要处理竞争问题，对于lock-free的实现，我们把这个竞争也叫重叠(overlap)，正如之前所说，一个processor失败意味着另一个processor取得进展，那么对于失败的procesor实际上一部分操作和成功的processor是overlap的，这部分overlap随着processor失败而重启了。于是乎，Cache一致性的问题 和 不同processors之间操作的overlap 导致 "other work"不仅由用户操作组成，还由并发算法本身的overhead组成。

压测结论

1. 当processor = 2时，此时在上面的(4)中论证的由并发算法本身overhead导致的other work没有显著提高，可以认为每个processor处理 {操作总数} / 2个操作。
2. 当processor >= 3时，lock-free实现中processors之间有大量overlap，lock-based实现中有大量加锁开销，导致other work收到算法本身影响(这个类似于 "结构缺陷" 没法避免，只能改进)。

本文给出的lock-free实现在processor数量升高时，仍能保证性能不出现陡降(degradation)，所谓陡降，指的是当processor大于某个临界值时，算法的整体时间直接飘升

如下图，本文提出的算法保持良好的特性，可以看到本质上是 算法本身在多核环境下的overhead，和算法在多核环境获得到的scalable之间的trade-off。算法普遍在processor=2的时候有一个高点，此时就是上不去下不来的状态，一方面引入了多核导致的算法overhead，另一方面又没能利用起多核的并行扩展性。

本文还有一个双锁的实现，在processor=5的时候会有一个陡增点，因此适合于非多核的系统，或者体系结构不支持universal atomic primitive (compare and swap or load linked/store conditional).这些并发原语的系统。

6. 总结

本文提出的无锁算法，能保证在多核环境，支持基本并发原语(compare and swap or load linked/store conditional)的体系结构上，支持高性能，并发的enqueue和dequeue操作.

本文只是给出了一种 queue-based lock-free non-blocking的无锁队列实现。

根据

• 常见的数据格式 {stacks, queues, heaps, search trees, and hash tables}
• 实现的原语 {lock-based, lock-free, wait-free}
• 是否阻塞 {blocking, non-blocking}
• 是否饿死 {starvation-free}

这四个性质，又能组合成一堆并发容器，然后还有一些实现方式

• 一把大锁锁一切
• 根据数据结构的特性，拆分成多个锁(比如juc的 chashmap按buckets加锁)
• 对于计算时间 远大于 网络传输时间的case，把数据统一传输到中心化的计算中心也是一种办法。

最后，non-blocking给我们带来的直接好处就是: 免疫了其他process的延时(对当前process影响)