我知道可以使用ArcSwap来实现类似的功能，通过构造一个Arc<ArcSwap<Arc<T>>>，但这并不像我希望的那样方便。

ArcSwap看起来优化得很好，比ArcShift成熟得多。

然而，例如如果满足以下条件，ArcShift可能会提供类似或甚至更好的性能，同时使用起来稍微简单一些

1. 更新很少
2. 每个线程都可以有自己的（可变的）ArcShift实例副本

对于熟悉arc-swap的人来说，ArcShift实例的行为类似于arc_swap::cache::Cache，而ArcShift相对于ArcSwap的对应物是ArcShiftLight。

我确实找到了一些具有类似功能的crate，但没有找到任何让人信服的。我相信可能存在这样的crate，可能只是我错过了！

使命宣言

ArcShift的要求是

• 只要没有写入操作，常规的共享读取访问应该与Arc<T>一样快。
• 写入可能很昂贵（但当然不能比必要的慢）
• 写入发生后，读取可能会稍微变慢是可以接受的。
• 实现应该是无锁的（因此我们永远不需要挂起线程）
• API必须是100%安全和可靠的。
• 在值更新时，应尽快删除旧值。
• 不应该使用线程局部变量。
• 应该能够拥有对数据的“轻量级”句柄，这些句柄不提供快速访问，但另一方面也不保留旧值。
• 与Arc相比，不应该有任何内存开销。

关于最后两点，任何提供无开销访问T的类型都必须始终保留T的存活状态，否则在授予权限之前需要某种同步（这是昂贵的）。

解决方案想法

我很快确定了一个解决方案，其中ArcShift是Arc的直接替代品，具有相同的通用内存布局。也就是说，ArcShift的每个实例都是一个指向包含实际值的堆块的指针。与Arc一样，ArcShift在堆块中有一个引用计数。与Arc不同，ArcShift只有一个引用计数，没有“弱引用”的概念。ArcShift还有一个“下一个”指针。这个“下一个”指针指向任何更新的值，在没有更新发生之前是null。

一般想法的示意图

注意，下面的图是简化的，请参见下面的文本。

 Heap block 1                                  Heap block 2
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓          ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃  refcount: 1                 ┃    ┌─── ➤┃  refcount: 1                ┃
┃  payload: "First version"    ┃    │     ┃  payload: "Second version"  ┃
┃  next_and_state: ptr ────────┃────┘     ┃  next_and_state: nullptr    ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛          ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
                           ⮝
  ArcShift-instance        │
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃  item: ptr ──────────────┘   ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

由于每个ArcShift实例都包含一个指向包含payload类型T的实例的堆块的指针，因此访问底层值没有开销，这是项目设计中的一个设计约束。每当值更新时，就会在堆块链表中添加另一个节点。

复杂性

我们还希望支持ArcShiftLight实例。这些实例不保证立即指向的堆块包含一个非删除项T。为了实际访问payload T，ArcShiftLight实例需要升级为ArcShift实例。

因此，我们区分了“强链接”和“弱链接”。强链接保证了指向的块以及所有后续块都包含有效的'T'值。弱链接只保证节点链中至少包含一个有效的T对象。强链接将引用计数增加2^19。这意味着最多可以有2^19个弱链接（这足够用于许多目的）。使用64位引用计数，强链接的最大数量约为2^64/2^19，大约是35000亿。

使用的另一个技巧是，'next_and_state'指针的最低两位是一个2位整数，具有以下解释

当没有强链接指向一个节点时，该节点的有效负载可以被丢弃。

正确性

上面的描述可能看起来很简单。然而，这个项目教会我的是，无锁算法绝非儿戏。各种操作之间可以有数千种不同的交错方式。在任何两行代码之间，可能还有数百行其他代码正在执行。

Arcshift使用了大量的不安全Rust代码和无锁算法。这些是众所周知非常难以正确实现的技巧。因此，Arcshift需要一个广泛的测试套件。

单元测试

Arcshift通过大量的单元测试进行验证。

有一些简单的测试路径测试（例如 simple_get，以及其他），以及一些不同的模糊测试案例。模糊测试案例运行不同操作在不同线程上的随机组合。

还有一个详尽的测试套件，它测试了三个并发线程上所有ArcShift操作的组合。

自定义验证功能

启用非默认功能'validate'会导致Arcshift在内存中插入金丝雀，以尽可能检测野指针或线程问题。功能'debug'使详细的调试输出发送到stdout。

经验教训

在开发Arcshift的过程中，我学到了一些教训。

无锁算法真的很困难

众所周知，无锁算法很难做对。然而，在亲身经历后，这个真相对我而言变得更加真实。

无锁错误示例#1

我遇到的一个错误，事后看来非常明显，是（损坏的）看起来有点像这样的代码

    
let count = get_refcount(item)
    .fetch_sub(STRONG_COUNT, Ordering::SeqCst);

if count == STRONG_COUNT {
    drop_item(item);
} else if count < 2*STRONG_COUNT { //WRONG!
    drop_payload(item);
}

想法是我们有一个指向节点'item'的强引用计数。我们减去这个引用计数。如果先前的引用计数值（由AtomicUsize::fetch_sub返回）是STRONG_COUNT，这意味着我们的引用是唯一的剩余引用，我们现在可以丢弃'item'。这有效。

下一个条件尝试检查先前的引用计数是否小于2 * STRONG_COUNT。如果是这样，这意味着没有其他强计数指向该节点，因此我们可以丢弃'item'的有效负载（但不是整个节点）。想法是非当前节点永远不会获得引用计数，因此项目不能回到强链接状态。

然而，这根本不起作用！

在fetch_sub(STRONG_COUNT, Ordering::SeqCst);这一行之后，关于'item'的任何信息都不再存在！其他线程可以很容易地减少计数并在我们执行drop_payload(item)之前丢弃'item'。

这实际上是一个值得记忆的规律。在减少引用计数指针的引用计数后，指针完全无效，绝不能再接触它！

无锁错误示例 #2

如文档中详细说明，Arcshift使用一个单一的64位原子计数器来包含19位弱引用计数（用于ArcShiftLight实例）和45位强引用计数（用于ArcShift实例）。

这在我们增加计数时提出一个有趣的挑战。比如说，我们像这样增加弱计数

let count = item.fetch_add(1, Ordering::SeqCst);
if count == MAX_WEAK_COUNT { //WRONG!
    item.fetch_sub(1, Ordering::SeqCst);
    panic!("Max weak count exceeded");
}

上述代码不起作用，因为两个线程可能会同时执行'fetch_add'，然后第二个线程可能会看到等于MAX_WEAK_COUNT + 1的计数。

解决此问题的一种方法是通过Rust标准库为Arc引用计数所做的方法：预留一定范围的计数作为某种“溢出区域”

let count = item.fetch_add(1, Ordering::SeqCst);
if count >= MAX_WEAK_COUNT/2 { // Only use half the 'available' count range
    item.fetch_sub(1, Ordering::SeqCst);
    panic!("Max weak count exceeded");
}

只要最多MAX_WEAK_COUNT/2个线程同时执行代码，上述方法就能正常工作。对于std库的'Arc'，在64位机器上触发错误的线程数量是2^63，这在实际中显然永远不会发生。

对于ArcShiftLight，MAX_WEAK_COUNT只有2^19，其一半（2^18 = 262144）是一个庞大但实际可能存在的线程数量。我写这段代码的64位Linux机器有

> cat /proc/sys/kernel/threads-max
506892  #<- maximum 506892 threads 

因此，ArcShiftLight不使用原子'add'来增加弱计数，而是使用AtomicUsize::compare_exchange。

对于强计数，对于ArcShift，使用的是“溢出区域”方法。溢出区域大约有180亿个强计数。

不安全的Rust很难

在Arcshift中持有有效载荷值的节点看起来像这样

struct ItemHolder<T: 'static> {
   next_and_state: AtomicPtr<ItemHolder<T>>,
   refcount: AtomicUsize,
   payload: T,
}

当某个项目不再有强链接时，'payload'字段会被丢弃。

我们小心不要在这一点之后对'payload'进行任何访问。然而，结果证明，这并不足够——至少根据miri来看。

问题是像这样的代码

    let ptr: *const ItemHolder<T> = ...;
    let count = unsafe{&*ptr}.refcount.load(Ordering::SeqCst);

... 在'payload'被丢弃时是不合法的。这是因为当其字段之一正在写入时，不允许对*item进行解引用。

相反，可以这样做

    unsafe { &*addr_of!((*ptr).refcount) }.load(Ordering::SeqCst)

这是合法的，因为'addr_of'没有解引用ptr。Rust的批评者可能会指出，这种代码比等效的C++代码更复杂。然而，美丽之处在于这种复杂性完全包含在ArcShift中，一旦ArcShift被验证，就没人再需要考虑它了。

更新：有人指出，更好的解决方案是让'payload'为ManuallyDrop而不是T。

Miri是一个出色的工具

我过去广泛使用了miri，但并没有意识到它不仅是一个确保单线程不安全代码正确性的强大工具，而且对于在多线程不安全代码中查找竞态条件也非常有用。通过使用miri的--many-seeds选项，miri将多次运行相同的测试用例，并使用程序线程的不同调度。默认情况下（撰写本文时），--many-seeds默认为64种不同的调度。可以通过指定范围来控制种子集，例如--many-seeds=0..1000，以尝试更多变体。

match get_next_and_state(candidate).compare_exchange(...)
{
   Ok(_) => {/* handle success */ } 
   Err(other) => {
       if !is_superseded_by_tentative(get_state(other)) {
           // Race condition, but still can advance
           candidate = other;
           continue;
       } else {
           // Race condition, need to retry
           continue;
       }
   }
}