Epoch Based Reclamation 的个人理解

• 缘起
• 什么是Epoch based Reclamation
• 为什么要Epoch based Reclamation
• Epoch based Reclamation的原理概述
• 来个小例子
• 结语

最近在看大佬视频，在用rust实现一个concurrenthashmap的时候，用到了crossbeam中epoch，顿时一阵懵逼，囊碟括咧（这啥玩意啊）？于是便开始启动搜索引擎大发，再整合诸多信息后，有了此偏小记。

大概意思上来说，这是无锁编程模式下的一种内存管理回收方案，官方定义可参考论文。而crossbeam-epoch是其rust下的一种实现。

设想我们要在无gc的语言中实现一种无锁但支持并发的数据结构。线程A想替换该数据结构中的某个数据节点，线程A使用newNode原子替换了oldNode，本着负责到底的态度，线程A释放了oldNode，防止了内存泄露，这一切看起来没什么问题。
恰好此时，线程B读取了该node，而且要命的是，线程B在线程A替换前便进行了读取，因此线程B中拥有访问oldNode的指针，于是，bang！由于oldNode已被线程A释放，那么线程B此时持有的便是一个悬空指针。
在拥有gc的语言中，如java, golang，不会出现这种问题。但是对于rust，c，c++，则没有一种很好的方法应对这问题，除非非gc语言也有一种延迟回收内存的机制，于是Epoch based Reclamation作为其中一种方法应运而生。

学习最好的方式还是拜读大佬的文章。
其中，有对此的讲解，建议反复阅读:

The epoch scheme works by having:

A global epoch counter (taking on values 0, 1, and 2); A global list
of garbage for each epoch; An “active” flag for each thread; An epoch
counter for each thread. The epochs are used to discover when garbage
can safely be freed, because no thread can reach it. Unlike
traditional GC, this does not require walking through live data; it’s
purely a matter of checking epoch counts.

When a thread wants to perform an operation on the data structure, it
first sets its “active” flag, and then updates its local epoch to
match the global one. If the thread removes a node from the data
structure, it adds that node to the garbage list for the current
global epoch. (Note: it’s very important that the garbage go into the
current global epoch, not the previous local snapshot.) When it
completes its operation, it clears the “active” flag.

To try to collect the garbage (which can be done at any point), a
thread walks over the flags for all participating threads, and checks
whether all active threads are in the current epoch. If so, it can
attempt to increment the global epoch (modulo 3). If the increment
succeeds, the garbage from two epochs ago can be freed.

也就是说，总共有3种epoch计数，0， 1， 2。epoch计数循环增长，如0120120120…。
对于每个epoch计数012，都有一个对应的回收队列retireList。
有一个全局epoch计数，记为E

另外，每个线程有个局部计数，记为e，另外有一个bool变量active表示该线程是否处于临界区，即是否正在访问共享数据。任一线程在进入临界区时，先置active=true， e = E，退出临界区时，置active=false

任一线程，如果其对共享数据做出了更改，则需要删除的数据（如上例种的oldNode），不会直接删除，而是将其放入对应e的回收队列中。e.g. 线程A当前e=0,则oldNode放入retireList[0]中。

在此，首先需要关注的是，每个活跃线程（active = true）的局部计数e，只可能为E，或者(E - 1) % 3。(后续将省略模3的写法)。这是因为E的增长规则: 只有当所有活跃线程（active = true）中的e都等于E的情况下，才置E = E + 1。换言之，若有某一个活跃线程中的局部e为E-1的时候，E不会增长，故而不会存在有e=E-2的线程。

对于读取线程(epoch计数为e)，如果e=E，因目前所有活跃线程只可能为E或者E-1，故其可能引用到retireList[E]或者retireList[E-1]中的数据。如果e=E-1,则其可能引用到retireList[E]或者retireList[E-1]或者retireList[E-2]中的数据。因此retireList[E-2]无法释放。

当最后一个e=E-1的线程完成了临界区操作，也即所有活跃线程中epoch计数都等于E的时候，也就是说E - 2（也即E + 1）对应的回收队列retireList中的节点再也没有任何一个线程访问了，故而retireList[E - 2]中的数据可以真正的释放了。如此做后，全局计数E = E + 1

假设就两个线程A,B,一个共享数据N,初始数据为N0。A不断更改N，B则不断读取N。
E = 0
A: e = 0 用N1替代N0,N0放入retireList[0]
B: e = 0 读N，得到N0的引用
retireList[0] = [N0] retireList[1]=[] retireList[2]=[]
触发gc, E = 1, 释放retireList[1] =>
retireList[0] = [N0] retireList[1]=[] retireList[2]=[]

A: e = 1 用N2替代N1,N1放入retireList[1]
B: e = 1 读N，得到N1的引用
retireList[0] = [N0] retireList[1] = [N1] retireList[2]=[]
触发gc, E = 2, 释放retireList[2] =>
retireList[0] = [N0] retireList[1] = [N1] retireList[2]=[]

A: e = 2 用N3替代N2, N2放入retireList[2]
B: e = 2 读N，得到N2的引用
retireList[0] = [N0] retireList[1] = [N1] retireList[2]=[N2]
触发gc, E = 0, 释放retireList[0] =>
retireList[0] =[] retireList[1] = [N1] retireList[2]=[N2]

A: e = 0 用N4替代N3,N3放入retireList[0]
B: e = 0 读N，得到N3的引用
retireList[0] = [N3] retireList[1]=[N1] retireList[2]=[N2]
触发gc, E = 1, 释放retireList[1] =>
retireList[0] = [N3] retireList[1]=[] retireList[2]=[N2]

当然，这仅仅是一种可能的执行情况，可以列举其他情况，加深感性认识。

个人理解，仅供参考