rs-lockfree

• Concurrently R/W 共享对象 是高性能并发程序中最常见的操作之一。有多种实现方式，例如 R/W 锁，引用计数，危害指针，基于周期的回收，基于静默状态的回收。
• 面对锁竞争时，当前线程通常会暂停并等待触发器唤醒。因此，如果重试操作的成本低于上下文切换，则无锁结构是我们的首选。
• 引用计数有两个缺点
  • 每次读取都需要修改全局引用计数。在高并发情况下，对同一对象的原子操作可能成为性能瓶颈。
  • 管理引用对象将带来额外的维护成本并增加实现复杂性。
• 危害指针 算法首先将共享对象的指针保存到本地线程，然后访问它，访问完成后移除。只有当没有线程包含其引用时，才能释放对象，这解决了 ABA 问题。
• 危害指针解决了由原子引用计数引起的性能瓶颈问题，但也存在一些不足
  • 每个共享对象都应该与线程保持关系，这增加了使用的成本。
  • 在回收内存时，遍历全局数组需要花费很多时间。
  • 遍历全局数组不能保证原子性。
• OceanBase 提供了一种使用危害指针实现无锁结构的方法，这给了我很多启发。
  • GV(全局增量版本)需要用来识别要回收的共享对象。
  • 在访问共享对象之前，将 GV 保存到本地线程并命名为 TV
  • 在回收共享对象时，首先，将其保存为 OV 并原子添加(GV, 1)；其次，遍历所有线程并找到最小的 TV 作为 RV；最后，如果 OV < RV，则回收此共享对象。
  • 由于遍历数组将花费很多时间，因此需要类似延迟回收的机制。

使用

• 截至目前，此库仅支持 x86_64 架构，因为除了高性能服务器程序之外，很少有场景需要无锁解决方案。

• 由于 False sharing，部分成员变量可能会被不同的线程频繁修改，这些变量被对齐到64字节。这可能导致初始化时栈溢出。因此，在 Cargo.toml 中提供了3个功能：max_thread_count_16（默认）、max_thread_count_256、max_thread_count_4096（需要手动更改最小栈大小或设置 RUST_MIN_STACK 为 6000000）。

• 大多数分配器选择128K（默认设置）作为是否通过 mmap 分配内存的阈值。为了提高性能，最好在栈上分配 HazardEpoch、LockFreeQueue 或 LockFreeStack。

• 示例

  • example_hazard_epoch 展示了多个生产者和多个读取者处理一个配置的场景。运行命令

    RUST_LOG=INFO cargo run --release --example example_hazard_epoch
    

  • example_lockfree_queue 展示了多个生产者和多个消费者的场景。运行命令

    RUST_LOG=INFO cargo run --release --example example_lockfree_queue
    

  • example_lockfree_stack 展示了多个生产者和多个消费者的场景。运行命令

    RUST_LOG=INFO cargo run --release --example example_lockfree_stack
    

变更日志

• 版本 0.1.1
  • 移除了对 allocator_api 的使用，因为 rust-nightly 改变这个功能的频率太高。