安全な楽観的ロックカップリング
Safe Optimistic Lock Coupling (databasearchitects.blogspot.com)
要約
CPUコア数の増加に伴い、並行データ構造のスケーラビリティが重要になっています。従来のロックカップリングはルートノードでの競合が問題となりますが、楽観的ロックカップリング(OLC)は、読み取り時に書き込みを行わず、データ再検証を行うことでこの問題を解決します。型システムに検証要件を組み込むことで、コンパイラが誤りを検出し、パフォーマンスと安全性を両立させる方法を提案しています。
全文翻訳
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]
この競合問題は、書き込みを行わないリーダーを使用する同期技術である楽観的ロックカップリングを使用することで解決できます。ここでの鍵となる考え方は、ライターは通常通りロックし、更新が完了したらバージョン番号を増やすことです。リーダーはアクセス前にバージョン番号を読み取り、関心のある要素を読み取り、その後バージョン番号を再確認します。バージョン番号が変更された場合(または要素が現在ロックされている場合)、読み取りは失敗し、リーダーは再試行します。コード(わずかに簡略化)は次のようになります。
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>値として公開します
class Node::OptimisticView {
class 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;
}
コードは上記の安全でないバージョンとほぼ同じですが、コンパイラがそうしないとエラーになるため、検証を忘れることが不可能になりました。これにより、この非常に魅力的な並列パラダイムが堅牢で使いやすくなり、あらゆる種類のデータ構造に適用できます。
要約すると、楽観的ロックカップリングは、安全な並列書き込みをサポートしながら、ロックフリーに近い読み取りスケーラビリティを提供します。そして、検証要件を型システムにエンコードすることで、正確性を犠牲にすることなくパフォーマンスのメリットを得られます。コンパイラは、ランタイムで微妙な競合状態となる可能性のある間違いを検出します。