7

私はいくつかのロックレス コードの正確性に執着してきました。私の質問は、C++11 のメモリ モデルで取得と解放のセマンティクスを使用して、必要なスレッド間同期を実現する方法についてです。私の質問の前に、いくつかの背景...

MVCCでは、ライターは古いオブジェクト バージョンのリーダーに影響を与えることなく、新しいバージョンのオブジェクトをインストールできます。ただし、より高い番号のタイムスタンプを持つリーダーが古いバージョンへの参照を既に取得しているときに、ライターが新しいバージョンのオブジェクトをインストールすると、ライター トランザクションをロールバックして再試行する必要があります。これは、シリアル化可能なスナップショット分離を維持するためです (つまり、すべての成功したトランザクションがタイムスタンプ順に次々に実行されたかのようになります)。リーダーは書き込みのために再試行する必要はありませんが、ライターのアクティビティがより高い番号のタイムスタンプを持つリーダーの「下からラグを引き出す」場合は、ライターをロールバックして再試行する必要がある場合があります。この制約を実装するには、読み取りタイムスタンプ使用されている。アイデアは、リーダーが参照を取得する前にオブジェクトの読み取りタイムスタンプを独自のタイムスタンプに更新し、ライターが読み取りタイムスタンプをチェックして、そのオブジェクトの新しいバージョンを続行してもよいかどうかを確認するというものです。

T1 (書き込み側) と T2 (読み取り側) の 2 つのトランザクションが別々のスレッドで実行されているとします。

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.

T2 が開始する前に T1 が完全に実行されている (そして T1 の効果が T2 に完全に見える) 場合、問題はありません。T2 は、T1 のタイムスタンプが T2 よりも小さいため、T1 によってインストールされたオブジェクト バージョンへの参照を取得します。(トランザクションは「過去から」オブジェクトを読み取ることができますが、「未来をピアリング」することはできません)。

T1 が開始する前に T2 が完全に実行されている (そして T2 の効果が T1 に完全に見える) 場合、問題はありません。T1 は、"未来からの" トランザクションが古いバージョンのオブジェクトを読み取った可能性があることを確認します。したがって、T1 はロールバックされ、作業の実行を再試行するために新しいトランザクションが作成されます。

問題は (もちろん)、T1 と T2 が同時に実行されたときに正しい動作を保証することです。ミューテックスを使用して競合状態を排除するのは非常に簡単ですが、他に方法がないと確信している場合にのみ、ロックを使用したソリューションを受け入れます。C++11 のメモリ モデルの取得と解放でこれを実行できるはずです。コードが正しいことに満足できる限り、多少の複雑さは問題ありません。私は、MVCC の主なセールス機能である、読者にできるだけ速く実行してもらいたいと思っています。

質問:

1.throw TransactionRetryEx()上記の (部分的な) コードを見て、T2 がオブジェクトの古いバージョンの使用を続行した場合に、T1 が (を介して) ロールバックできなくなるような競合状態が存在すると思いますか?

2.コードが間違っている場合は、その理由を説明し、正しくするための一般的なガイダンスを提供してください。

3.コードが正しく見える場合でも、どのように効率化できるかがわかりますか?

私の推論DataStore::update()は、への呼び出しが__atomic_compare_exchange_n()成功した場合、「競合している」リーダー スレッドがまだ読み取りタイムスタンプを更新していないことを意味するため、オブジェクト バージョンのチェーンをたどって新しくアクセス可能なバージョンを見つけていないことを意味します。インストールしたばかりです。

「Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery」という本を買おうとしていますが、私もあなたに迷惑をかけると思いました :DI もっと早く本を買うべきだったと思いますが、私は'また、自分の仕事の大部分を無効にするようなことは何も学ばないと確信しています。

回答を可能にするのに十分な情報を提供できたことを願っています。建設的な批判を受けた場合は、喜んで質問を編集してより明確にします。この質問 (またはそれによく似た質問) が既に尋ねられて回答されている場合、それは素晴らしいことです。

ありがとう！

4

1 に答える 1

1

これは複雑で、1. と 2. についてはまだ何も言えませんが、3 に関しては次のことに気付きました。

__atomic_compare_exchange_n が false を返すと、*rrp の現在の値が rr に書き込まれるため、ループ内の __atomic_load() は両方とも冗長です (T2 では単に破棄し、T1 では T2 のようにループの前に 1 回実行します)。

一般的な意見として、アルゴリズムの他のすべてが完了するまでは、おそらく取得/解放について考える必要はありません。次に、「どこでも」必要なメモリバリアの強度を確認できます。

于 2012-09-23T11:55:24.883 に答える