c++ - MVCC 实现中的无锁读写器同步

Question

我一直在关注一些无锁代码的正确性，我真的很感激我能得到的任何输入。我的问题是关于如何在 C++11 的内存模型中使用获取和释放语义来实现一些所需的线程间同步。在我的问题之前，一些背景...

在 MVCC ，作者可以安装对象的新版本而不影响旧对象版本的读者。但是，如果在具有更高编号时间戳的读取器已经获得对旧版本的引用时，写入器安装对象的新版本，则写入器事务将必须回滚并重试。这是为了保持可序列化的快照隔离(所以就好像所有成功的事务都按时间戳顺序一个接一个地执行)。读者永远不必由于写入而重试，但如果作者的事件会“从下面拉出地毯”，则可能必须回滚并重试具有更高编号时间戳的读者。为了实现此约束，使用了读取时间戳。这个想法是，读取器在获取引用之前将对象的读取时间戳更新为其自己的时间戳，而写入器将检查读取时间戳以查看是否可以继续使用该对象的新版本。

假设有两个事务:T1(写入者)和 T2(读取者)，它们在不同的线程中运行。

T1(作者)这样做:

void
DataStore::update(CachedObject* oldObject, CachedObject* newObject)
{
    .
    .
    .
    COcontainer* container = oldObject->parent();
    tid_t newTID = newObject->revision();
    container->setObject(newObject);
    tid_t* rrp = &container->readRevision;
    tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
    while (true)
    {
        if (rr > newTID) throw TransactionRetryEx();
        if (__atomic_compare_exchange_n(
            rrp,
            &rr,
            rr,
            false,
            __ATOMIC_RELEASE,
            __ATOMIC_RELAXED)
        {
            break;
        }
    }
}

T2(读者)这样做:

CachedObject*
Transaction::onRead(CachedObject* object)
{
    tid_t tid = Transaction::mine()->tid();
    COcontainer* container = object->parent();
    tid_t* rrp = &container->readRevision;
    tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
    while (rr < tid)
    {
        if (__atomic_compare_exchange_n(
            rrp,
            &rr,
            tid,
            false,
            __ATOMIC_ACQUIRE,
            __ATOMIC_ACQUIRE))
        {
            break;
        }
    }
    // follow the chain of objects to find the newest one this transaction can use
    object = object->newest();
    // caller can use object now
    return object;
}

这是我担心的情况的简单总结:

     A    B    C
<----*----*----*---->
   timestamp order

A: old object's timestamp
B: new object's timestamp (T1's timestamp)
C: "future" reader's timestamp (T2's timestamp)

* If T2@C reads object@A, T1@B must be rolled back.

如果 T1 在 T2 开始之前完全执行(并且 T1 的效果对 T2 完全可见)，那么没有问题。 T2 将获取对 T1 安装的对象版本的引用，它可以使用它，因为 T1 的时间戳小于 T2 的时间戳。 (事务可以“从过去”读取对象，但不能“对等 future ”)。

如果 T2 在 T1 开始之前完全执行(并且 T2 的效果对 T1 完全可见)，那么没有问题。 T1 将看到“来自 future ”的事务可能读取了对象的旧版本。因此，T1 将被回滚并创建一个新事务来重试工作的执行。

当 T1 和 T2 同时运行时，问题(当然)是保证正确的行为。仅使用互斥锁来消除竞争条件会非常简单，但如果我确信没有其他方法，我只会接受带锁的解决方案。我很确定使用 C++11 的获取和释放内存模型应该可以做到这一点。我可以接受一些复杂性，只要我对代码正确感到满意。我真的希望读者尽可能快地运行，这是 MVCC 的主要卖点。

问题:

1. 查看以上(部分)代码，您是否认为存在竞争条件，因此在 T2 继续使用对象的旧版本的情况下，T1 可能无法回滚(通过 throw TransactionRetryEx())？

2. 如果代码错误，请解释原因，并提供一般指导以使其正确。

3. 即使代码看起来正确，你能看到它如何更高效吗？

我在 DataStore::update() 中的推理就是如果打电话到 __atomic_compare_exchange_n()成功，这意味着“冲突”的读取器线程尚未更新读取时间戳，因此它也没有遍历对象版本链以找到刚刚安装的新可访问版本。

我要买书 "Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery" ，但我想我也会打扰你 :D 我想我应该早点买这本书，但我也相当确定我不会学到任何会使我的大部分工作无效的东西。

我希望我已经提供了足够的信息以使答案成为可能。如果我收到 build 性的批评，我很乐意编辑我的问题以使其更清楚。如果已经有人问过并回答了这个问题(或类似的问题)，那就太好了。

谢谢!

Answer 1

这很复杂，我还不能对 1. 和 2. 说任何话，但是关于 3，我注意到了一些事情:

当 __atomic_compare_exchange_n 返回 false 时，*rrp 的当前值被写入 rr，因此循环中的 __atomic_load() 都是多余的(在 T2 中只是将其扔掉，在 T1 中像在 T2 中那样在循环之前执行一次)。

一般而言，在算法中的其他所有内容完成之前，可能没有必要考虑获取/释放；然后您可以检查“无处不在”需要多强的内存屏障。