Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

Lock Free中的Hazard Pointer(下)

在前面几篇文章里,我们介绍了Hazard Pointer,一种用于lock free data structure设计中内存管理的利器,这个利器不仅思想简单,还可以用来防止ABA问题,读者诸君务必掌握。

本文作为第三部分,给出工业级代码中,实现Hazard Pointer的一些策略和需要注意的点。

Hazard Pointer管理

我们知道Hazard Pointer封装了原始指针,那么Hazard Pointer的内存和生命周期本身如何管理呢?以下是常见的策略:

1,Hazard Pointer本身的内存只分配,不释放。在stack、queue等数据结构里,需要的Hazard Pointer数量一般为1或者2,所以不释放问题不大。对于skip list这种数据结构又有遍历需求的,那么Hazard Pointer可能就不是非常适用了,可以考虑使用Epoch Based Reclamation技术。据我所知,这也是memsql使用的内存回收策略。

2,每个线程拥有、管理自己的retire list和hazard pointer list ,而不是所有线程共享一个retire list,这样可以避免维护retire list和hazard pointer list的开销,否则我们可能又得想尽脑汁去设计另外一套lock free的策略来管理这些list,先有鸡先有蛋,无穷无尽。所谓retire list就是指逻辑删除后待物理回收的指针列表。

3,每个线程负责回收自己的retire list中记录维护的内存。这样,retire list是一个线程局部的数据结构,自己写,自己读,吃自己的狗粮。

4,只有当retire list的大小(数量)达到一定的阈值时,才进行GC。这样,可以把GC的开销进行分摊,同时,应该尽可能使用Jemalloc或者TCmalloc这些高效的、带线程局部缓存的内存分配器。

acquire和release动作

所谓acquire,就是线程需要对一个资源进行访问,需要对它进行保护;所谓release,就是线程停止对资源的访问,结束对它的保护。

这两个动作基本上都是成对出现的,因此,可以封装成一个Guard。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   struct HazardPointerRecord
    {
      HazardPointerRecord(HplfdsHazardPointer<MemoryAllocator> &manager,
                          void *p, int thread_id): manager_(manager)
      {
        p_ = p;
        thread_id_ = thread_id;
        manager.acquire(p_, thread_id_);
      }
      ~HazardPointerRecord()
      {
        manager_.release(p_, thread_id_);
      }
      HplfdsHazardPointer<MemoryAllocator> &manager_;
      void *p_;
      int thread_id_;
    };

    #define ACQUIRE_POINTER(p)\
  HazardPointerRecord record##p(memory_manager_, p, thread_id);

更多细节,可以参考业余时间编写的lock free ms queue中的用法。

实现

我在我的HPLFDS开源项目中,给出了一个实现。虽然reclaim可以做的更加高效,然而在大部分场景下已经足够用了。