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,所以可以使用它.(事务可以"从过去"读取对象,但它不能"窥视未来").

如果T2在T1开始之前完全执行(并且T2的效果对T1完全可见),则没有问题.T1将看到"来自未来"的事务可能已读取旧版本的对象.因此,将回滚T1并创建新事务以重试工作的性能.

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

问题:

1.查看上面的(部分)代码,您认为存在竞争条件,以便throw TransactionRetryEx()在T2继续使用旧版本的对象时,T1可能无法回滚(通过)吗？

2.如果代码错误,请解释原因并请提供正确的指导.

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

我的理由DataStore::update()是,如果调用__atomic_compare_exchange_n()成功,则意味着"冲突"读者线程尚未更新读取时间戳,因此它也没有遍历对象版本链以找到新的可访问版本刚装好.

我即将购买"交易信息系统:理论,算法,并发控制和恢复的实践"这本书,但我想我也会打扰你:DI认为我应该早点买这本书,但我'我也相当肯定我不会学到任何会使我的大部分工作无效的东西.

我希望我已经提供了足够的信息来回答问题.如果我收到建设性的批评,我会很乐意编辑我的问题,以便更清楚.如果这个问题(或类似的问题)已被提出并回答,那就太好了.

谢谢!

Answer 1

这很复杂，我还不能对 1. 和 2. 说什么，但关于 3 我注意到了一些事情：

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

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