Left-right 是针对单写者数据结构的高并发读取的并发原语。该原语保留数据结构的两个副本，一个由读者访问，另一个由（单个）写者访问。这使得所有读取都可以并行进行，最小化协调，并将协调开销转移到写者。在没有写入的情况下，读取与核心数线性增长。

lib.rs:

针对单写者数据结构的高并发读取的并发原语。

该原语保留数据结构的两个副本，一个由读者访问，另一个由（单个）写者访问。这使得所有读取都可以并行进行，最小化协调，并将协调开销转移到写者。在没有写入的情况下，读取与核心数线性增长。

当写者希望向数据结构公开新更改时（参见 WriteHandle::publish），它“翻转”两个副本，使得后续读取指向旧的“写侧”，而未来的写入指向旧的“读侧”。这个过程会导致读者两次缓存行失效，但不会阻止他们取得进展（即读取是无等待的）。

为了保持两个副本的更新，left-right 保留数据结构所有修改的操作日志（“oplog”），它使用此日志在翻转时将旧的读取数据更新为最新的写入。

权衡

很少有并发优势是不需要付出代价的，这个也不例外。该原语的缺点是

• 增加内存使用：由于我们保留了后备数据结构的两份副本，实际上是将底层数据的内存使用翻倍。通过一些巧妙的去重，这种成本可以在一定程度上得到改善，但这是一个需要注意的问题。此外，尽管向操作日志添加了很多写入操作，但写入者很少调用publish，操作日志本身可能会变得相当大，这会增加额外的开销。
• 确定性操作：由于操作日志的条目被应用两次，一次针对数据副本，因此操作必须是确定的。如果不是这样，两个副本将不再相互镜像，并且会随着时间的推移而继续 diverge。
• 单写入者：左-右只支持单个写入者。要实现多个写入者，你需要确保通过类似Mutex的方式对WriteHandle进行独占访问。
• 慢速写入：通过左-右进行的写入比直接针对后备数据结构的写入要慢。这既是由于它们必须通过操作日志进行，也是因为每个写入都必须应用两次。

它是如何工作的？

请看这个YouTube视频，它讲解了基本的并发算法，以及这个库的初始开发。或者，还有一篇更短（但也不太完整）的介绍，在这次演讲中。

从表面上看，左-右是通过两个常规的T、操作日志、时代计数和一些指针魔法实现的。有一个单一的指针，所有读者都通过它。它指向读者读取数据的T。每次读取访问指针时，它们都会增加一个本地时代计数器，并在完成读取时再次更新它。当发生写入时，写入者更新另一个（没有读者）的T，并将更改的副本存储在日志中。当调用WriteHandle::publish时，写入者原子性地交换读者指针，使其指向另一个T。然后它等待所有当前读者的时代改变，然后重放操作日志，以使旧的副本更新到最新状态。

设计类似于2015年提出的这个左-右并发方案，尽管我不知道是否有关于这项工作的后续工作。

我该如何使用它？

如果你只想使用快速读取的数据结构，你可能想使用使用这个crate的crate，比如evmap。如果你想自己开发这样的crate，以下是你需要做的事情

use left_right::{Absorb, ReadHandle, WriteHandle};

// First, define an operational log type.
// For most real-world use-cases, this will be an `enum`, but we'll keep it simple:
struct CounterAddOp(i32);

// Then, implement the unsafe `Absorb` trait for your data structure type,
// and provide the oplog type as the generic argument.
// You can read this as "`i32` can absorb changes of type `CounterAddOp`".
impl Absorb<CounterAddOp> for i32 {
    // See the documentation of `Absorb::absorb_first`.
    //
    // Essentially, this is where you define what applying
    // the oplog type to the datastructure does.
    fn absorb_first(&mut self, operation: &mut CounterAddOp, _: &Self) {
        *self += operation.0;
    }

    // See the documentation of `Absorb::absorb_second`.
    //
    // This may or may not be the same as `absorb_first`,
    // depending on whether or not you de-duplicate values
    // across the two copies of your data structure.
    fn absorb_second(&mut self, operation: CounterAddOp, _: &Self) {
        *self += operation.0;
    }

    // See the documentation of `Absorb::drop_first`.
    fn drop_first(self: Box<Self>) {}

    fn sync_with(&mut self, first: &Self) {
        *self = *first
    }
}

// Now, you can construct a new left-right over an instance of your data structure.
// This will give you a `WriteHandle` that accepts writes in the form of oplog entries,
// and a (cloneable) `ReadHandle` that gives you `&` access to the data structure.
let (write, read) = left_right::new::<i32, CounterAddOp>();

// You will likely want to embed these handles in your own types so that you can
// provide more ergonomic methods for performing operations on your type.
struct Counter(WriteHandle<i32, CounterAddOp>);
impl Counter {
    // The methods on you write handle type will likely all just add to the operational log.
    pub fn add(&mut self, i: i32) {
        self.0.append(CounterAddOp(i));
    }

    // You should also provide a method for exposing the results of any pending operations.
    //
    // Until this is called, any writes made since the last call to `publish` will not be
    // visible to readers. See `WriteHandle::publish` for more details. Make sure to call
    // this out in _your_ documentation as well, so that your users will be aware of this
    // "weird" behavior.
    pub fn publish(&mut self) {
        self.0.publish();
    }
}

// Similarly, for reads:
#[derive(Clone)]
struct CountReader(ReadHandle<i32>);
impl CountReader {
    pub fn get(&self) -> i32 {
        // The `ReadHandle` itself does not allow you to access the underlying data.
        // Instead, you must first "enter" the data structure. This is similar to
        // taking a `Mutex`, except that no lock is actually taken. When you enter,
        // you are given back a guard, which gives you shared access (through the
        // `Deref` trait) to the "read copy" of the data structure.
        //
        // Note that `enter` may yield `None`, which implies that the `WriteHandle`
        // was dropped, and took the backing data down with it.
        //
        // Note also that for as long as the guard lives, a writer that tries to
        // call `WriteHandle::publish` will be blocked from making progress.
        self.0.enter().map(|guard| *guard).unwrap_or(0)
    }
}

// These wrapper types are likely what you'll give out to your consumers.
let (mut w, r) = (Counter(write), CountReader(read));

// They can then use the type fairly ergonomically:
assert_eq!(r.get(), 0);
w.add(1);
// no call to publish, so read side remains the same:
assert_eq!(r.get(), 0);
w.publish();
assert_eq!(r.get(), 1);
drop(w);
// writer dropped data, so reads yield fallback value:
assert_eq!(r.get(), 0);

一个值得注意的细节：与标准库中的Mutex、RwLock和RefCell类似，从ReadGuard解引用的值与该ReadGuard的生存周期绑定。这可能会使得在读取句柄上编写返回底层数据引用的易用方法变得有些棘手，并可能诱使您克隆数据或使用闭包。相反，可以考虑使用ReadGuard::map和ReadGuard::try_map，它们（就像RefCell的Ref::map一样）允许您在数据结构中提供更深层次的受保护引用。