返回题库

基于纪元的内存回收

Epoch Based Reclamation

专题
Systems & Architecture / 系统与架构
难度
L3
来源
MyntBit

题目详情

在低延迟交易系统中，无锁数据结构被广泛使用以确保确定性性能和避免线程竞争。但这些结构中的内存回收具有挑战：一个线程可能在另一线程并发读取同一节点时尝试释放它。Epoch-Based Reclamation（EBR）通过推迟被移除节点的销毁来解决此问题。

任务：实现 EpochManager 类，提供 enter/leave/try_reclaim 操作，维护全局 epoch 和线程本地 epoch 记录，安全回收在旧 epoch 中移除的节点。

英文原题

In low-latency trading systems, lock-free data structures are extensively used to ensure deterministic performance and avoid thread contention. However, memory reclamation in these structures is challenging because a thread might attempt to free a node while another thread is concurrently reading it. Epoch-Based Reclamation (EBR) is a widely used technique that defers the destruction of removed nodes until no active thread can possibly hold a reference to them.
Task
Implement an EpochBasedRecla

解析

问题分析

基于纪元的内存回收是无锁数据结构中安全释放内存的常用技术。每个对象标记所属纪元，当所有线程都离开该纪元后，对应的内存批次可以安全回收。

实现

class EpochManager {
    static constexpr int MAX_EPOCHS = 3;
    std::atomic<unsigned> global_epoch_{0};
    std::atomic<unsigned> thread_count_[MAX_EPOCHS]{};
    std::vector<void*> retire_lists_[MAX_EPOCHS];
    std::mutex mtx_;
public:
    unsigned enter() {
        unsigned e = global_epoch_.load(std::memory_order_acquire);
        thread_count_[e].fetch_add(1, std::memory_order_acquire);
        return e;
    }
    void leave(unsigned epoch) { thread_count_[epoch].fetch_sub(1); }
    void retire(void* ptr) {
        std::lock_guard lk(mtx_);
        retire_lists_[global_epoch_].push_back(ptr);
    }
    void advance() {
        unsigned next = (global_epoch_ + 1) % MAX_EPOCHS;
        while (thread_count_[next].load() > 0) std::this_thread::yield();
        for (auto* ptr : retire_lists_[next]) { ::operator delete(ptr); }
        retire_lists_[next].clear();
        global_epoch_.store(next, std::memory_order_release);
    }
};

复杂度与边界

  • 时间复杂度：enter/leave O(1)，advance O(待回收对象数)
  • 空间复杂度：O(MAX_EPOCHS * 对象数)
  • 边界条件：(1) 纪元回绕需 MAX_EPOCHS > 最大并发读 (2) advance 频率需平衡内存和延迟

英文解析

Analysis

Epoch-based reclamation is a common technique for safely freeing memory in lock-free data structures. Each object is tagged with its belonging epoch. When all threads have left that epoch, the corresponding batch of memory can be safely reclaimed.

Solution

class EpochManager {
    static constexpr int MAX_EPOCHS = 3;
    std::atomic<unsigned> global_epoch_{0};
    std::atomic<unsigned> thread_count_[MAX_EPOCHS]{};
    std::vector<void*> retire_lists_[MAX_EPOCHS];
    std::mutex mtx_;
public:
    unsigned enter() {
        unsigned e = global_epoch_.load(std::memory_order_acquire);
        thread_count_[e].fetch_add(1, std::memory_order_acquire);
        return e;
    }
    void leave(unsigned epoch) { thread_count_[epoch].fetch_sub(1); }
    void retire(void* ptr) {
        std::lock_guard lk(mtx_);
        retire_lists_[global_epoch_].push_back(ptr);
    }
    void advance() {
        unsigned next = (global_epoch_ + 1) % MAX_EPOCHS;
        if (thread_count_[next].load() == 0) {
            global_epoch_.store(next);
            for (auto* p : retire_lists_[next]) ::operator delete(p);
            retire_lists_[next].clear();
        }
    }
};

Complexity & Edge Cases

  • Time complexity: O(1) for enter/leave epoch; O(R) for reclaiming R retired objects per epoch advancement
  • Space complexity: O(A + R) for A active and R retired object records
  • Edge cases: (1) Thread that never leaves epoch blocks reclamation indefinitely. (2) Deferred reclamation must not free objects still referenced by in-progress operations. (3) Epoch counter wrapping on 32-bit integers.

Key Considerations

  1. Batch reclamation: Objects retired in epoch N can only be freed when all threads have moved past epoch N, guaranteeing no thread holds a stale reference.
  2. Minimal overhead: enter/leave are single atomic operations; no CAS loops needed.
  3. Epoch limit: MAX_EPOCHS=3 balances memory retention vs. reclamation frequency.
  4. Time complexity: enter/leave/retire O(1); advance O(retired objects in old epoch).