Epoch-Based Reclamation算法

https://www.zhihu.com/question/406428296/answer/1345620324

概述

EBR是在无锁或低锁并发结构中常用的聂村回收机制。核心目标是解决并发环境中内存安全释放的问题。

在并发数据结构中，删除节点不等于可以立即释放内存。

比如在删除的时候，其他线程可能仍然持有指针，但删除线程无法知道。

常见的类似方案

• RCU：read-copy-update。写操作不直接修改正在被读取的对象，而是创建新的副本。类似COW
• 引用计数，开销稍大。
• Hazard Pointers：精确但复杂

EBR的思想是：延迟释放

核心

Bw-Tree（B-link Tree without latches）是一种无锁的并发B+树变体。目标是实现高并发环境下实现高吞吐的索引结构。避免传统B+树锁竞争的问题。

Bw-Tree主要针对内存数据库和无锁结构。

• 每个操作在开始的时候注册到一个Epoch，可以根据物理时间，每10ms作为一个epoch
• 操作开始时增加Epoch counter，操作结束时减少Epoch counter
• 操作过程中，产生的垃圾都放到epoch内部的garbage list上
• 当这个epoch的所有操作都结束了，即counter为0时，这个epoch的所有资源都可以被释放

用上图举例，这是BwTree的内存垃圾回收。众所周知BwTree是一个latch-free的高性能索引，既然要latch-free那么内存分配一定不能拖后腿了。在对索引进行操作时，例如删除索引的一条数据，并不能直接释放内存，否则无锁算法很容易出现ABA问题。所以在操作过程中产生的垃圾，都放到epoch的garbage list上，当所有线程都退出这个epoch就可以安全地释放掉所有资源。（事实上，上面这个图还是Centralized，Open-BwTree里用了扩展性更好的Decentrailzed实现）

EBR算法的回收是机会式回收。是许多lock-free数据结构的默认实现方式。

相比RC

相比RC（reference counting）引用计数法，EBR有更好的缓存局部性。

引用计数每次操作都要原子写入。这会导致cpu的缓存行竞争严重。多次出发缓存行失效是严重的性能问题。

EBR 也不是完美的。一个线程的sllep会导致全局epoch无法推荐。导致重试列表无限增长。内存回收也可能会不及时导致内存占用更高。

EBR 的效率来自：消除 per-access 原子操作，把回收同步从“每次访问”降低到“偶尔 epoch 推进”。