安全な楽観的ロックカップリング

Wednesday, April 29, 2026 Safe Optimistic Lock Coupling CPUコア数が増加し続けるにつれて、並行データ構造のスケーラビリティはますます重要になっています。4コアでは問題なく動作するデータ構造も、アルゴリズムの制限ではなく、同期アクセス方法のために32コアではボトルネックになる可能性があります。これを単純な二分木で説明します。 通常、これらのデータ構造は、何らかのロックで保護されています。 struct Node { mutex lock; key_type key; value_type value; Node* left, *right; }; struct Tree { mutex lock; Node* root; }; 値を検索する際、データ構造をたどり、現在触れている部分にロックをかけ、完了したらロックを解除します（「ロックカップリング」）。 option<value_type> Tree::lookup(key_type key) { lock.lock_shared(); mutex* currentLock = &lock; Node* iter = root; option<value_type> result; while (iter) { if (key == iter->key) { result = iter->value; break; } Node* next = (key < iter->key) ? iter->left : iter->right; if (next) next->lock.lock_shared(); currentLock->unlock(); currentLock = next ? &next->lock : nullptr; iter = next; } currentLock->unlock(); return result; } 概念的には単純ですが、ロックカップリングは実際にはパフォーマンスが非常に悪いです。問題は、特にルートノードでロックの競合を引き起こすことです。すべての検索はルートノードを通過するため、ルートノードは常にロックおよびアンロックされます。検索間に意味的な競合はありませんが（すべてのリーダーはルートを同時に読み取ることができます）、ロック自体に物理的な競合があり、スケーラビリティを制限します。これは、100,000要素のツリーで、16コア/32スレッドの9950X3Dで実行された同時検索で以下のように見られます。 Lookup scalability: no locking vs lock coupling この競合問題は、書き込みを行わないリーダーを使用する同期技術である楽観的ロックカップリング（Optimistic Lock Coupling）を使用して解決できます。 ここでの鍵となる考え方は、ライターは通常通りロックし、更新が完了したらバージョン番号を増やすということです。リーダーはアクセス前にバージョン番号を読み取り、関心のある要素を読み取り、その後バージョン番号を再確認します。バージョン番号が変更された場合（または要素が現在ロックされている場合）、読み取りは失敗し、リーダーは再試行します。 （わずかに簡略化された）コードでは、次のようになります。 struct Node { version_lock lock; key_type key; value_type value; Node* left, *right; }; struct Tree { version_lock lock; Node* root; }; option<value_type> Tree::lookup(key_type key) { restart: lock_guard guard = lock.lock_optimistic(); Node* iter = root; if (!guard.validate()) goto restart; option<value_type> result; while (iter) { auto currentKey = iter->key; if (!guard.validate()) goto restart; if (key == currentKey) { auto currentValue = iter->value; if (!guard.validate()) goto restart; result = currentValue; break; } iter = (key < currentKey) ? iter->left : iter->right; if (!guard.validate()) goto restart; auto nextGuard = iter->lock.lock_optimistic(); if (!guard.validate()) goto restart; guard = nextGuard; } return result; } 上記の古典的なロックカップリングコードとそれほど違いはありませんが、読み取った値に基づいて行動する前に常に同時書き込みをチェックする必要がある点が異なります。この戦略の大きな利点は、検索コードが純粋に読み取り専用であるため、コア数に応じてうまくスケーリングできることです。 Lookup scalability: all strategies 楽観的ロックカップリングは優れたパフォーマンスを提供しますが、使用するには少し危険です。検証する前に値に基づいて行動すると、コードに競合状態が発生します。この小さな例では、いつ検証する必要があるかは明らかですが、複雑なコードフラグメントでは検証を忘れるのは簡単です。 これを軽減する最善の方法は、検証が必要であることを型システムにエンコードすることで、コンパイラのサポートを得ることです。検証されていない値を専用の型として表現し、ロックガードのみがその値を公開することでこれを実現できます。概念的には次のようになります（単純化のため、複数の値を検証するバリアントは省略）。 template <class T> class unvalidated { T value; friend class lock_guard; }; class lock_guard { ... template <class T> optional<T> validate(unvalidated<T> value); }; 基本的に、検証によって元の値へのアクセスのみを許可するため、この構造は安全になります。しかし、コードがすべてを unvalidated<T> で正しくラップすることをどのように保証できるでしょうか？データに対する楽観的なビューのみを公開することによってです。概念的には、次のことを行います。 struct Node { class OptimisticView; ... // 上記と同様 }; template <class T> class OptimisticPtr { T* rawPtr; public: // C++の制約により、残念ながらoperator->は使用できません typename T::OptimisticView data() const { return T::OptimisticView(rawPtr); } }; // 各メンバーを unvalidated<T> value として公開します class Node::OptimisticView { Node* rawData; public: unvalidated<key_type> key() { return unvalidated(atomic_ref(rawData->key).load(memory_order_relaxed)); } unvalidated<value_type> value() { return unvalidated(atomic_ref(rawData->value).load(memory_order_relaxed)); } unvalidated<OptimisticPtr<Node>> left() { return unvalidated(OptimisticPtr(atomic_ref(rawData->left).load(memory_order_relaxed))); } unvalidated<OptimisticPtr<Node>> right() { return unvalidated(OptimisticPtr(atomic_ref(rawData->right).load(memory_order_relaxed))); } unvalidated<lock_guard> lock() { return unvalidated(lock_guard(atomic_ref(rawData->lock).load(memory_order_seq_cst))); } }; lock() アクセサは unvalidated<lock_guard> を返します。次のノードのロックに引き渡す前に、現在のガードを検証して、有効なロックを実際に読み取ったことを確認する必要があります。これにより、ロック取得自体が検証されたチェーンの一部であることが保証されます。 この設計では、楽観的なコードは OptimisticPtr を介してのみデータにアクセスするため、事前の検証なしにデータにアクセスすることは不可能になります。これにより、アプローチの堅牢性が大幅に向上します。 OptimisticView でアクセサ関数を手動で実装する必要があるのは少し面倒ですが、将来的にはコンパイラが自動的に行ってくれることを期待しています。 これらの抽象化を使用すると、検索コードは次のようになります。 option<value_type> Tree::lookup(key_type key) { restart: lock_guard guard = lock.lock_optimistic(); auto iterOpt = guard.validate(getRootOptimistic()); if (!iterOpt) goto restart; OptimisticPtr<Node> iter = *iterOpt; option<value_type> result; while (iter) { auto currentKey = guard.validate(iter.data().key()); if (!currentKey) goto restart; if (key == *currentKey) { auto currentValue = guard.validate(iter.data().value()); if (!currentValue) goto restart; result = *currentValue; break; } auto next = guard.validate((key < *currentKey) ? iter.data().left() : iter.data().right()); if (!next) goto restart; iter = *next; auto nextGuard = guard.validate(iter.data().lock()); if (!nextGuard) goto restart; guard = *nextGuard; } return result; } コードは上記の安全でないバージョンとほぼ同じですが、コンパイラがそうしないとエラーになるため、検証を忘れることが不可能になりました。これにより、この非常に魅力的な並行パラダイムが、あらゆる種類のデータ構造に対して堅牢で使いやすくなります。 要約すると、楽観的ロックカップリングは、安全な同時書き込みをサポートしながら、ロックフリーに近い読み取りスケーラビリティを提供します。そして、検証要件を型システムにエンコードすることで、正確性を犠牲にすることなくパフォーマンスのメリットを得られます。コンパイラは、実行時に微妙な競合状態になる可能性のある間違いを検出します。 Posted by Thomas Neumann at 12:22 PM Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest Labels: locking, typesafety No comments: Post a Comment Newer Post Older Post Home Subscribe to: Post Comments (Atom)