{"article":{"slug":"safe-optimistic-lock-coupling","title":"Safe Optimistic Lock Coupling","subtitle":null,"summary":"Thomas Neumann explains why classic lock coupling scales poorly on many-core CPUs because of physical contention on the root lock, how Optimistic Lock Coupling lets readers validate version numbers instead of writing, and how a C++ lock guard can encode validation in the type system so the compiler catches missed checks.","content_type":"blog_post","language":"en","canonical_url":"https://databasearchitects.blogspot.com/2026/04/safe-optimistic-lock-coupling.html","author":{"name":"Thomas Neumann","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Database Architects","url":"https://databasearchitects.blogspot.com/","listing_slug":null,"listing":null},"topics":[{"name":"Databases","slug":"databases","url":"https://listedarticles.com/topics/databases"},{"name":"Performance","slug":"performance","url":"https://listedarticles.com/topics/performance"},{"name":"Systems Programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"},{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":1105,"reading_minutes":5,"published_at":"2026-04-29T10:22:00.000Z","added_at":"2026-10-05T08:10:42.992Z","updated_at":"2026-10-05T08:10:42.992Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/safe-optimistic-lock-coupling","markdown_url":"https://listedarticles.com/articles/safe-optimistic-lock-coupling.md","example":false,"citation":"Thomas Neumann, Database Architects. \"Safe Optimistic Lock Coupling.\" 29 Apr 2026. https://databasearchitects.blogspot.com/2026/04/safe-optimistic-lock-coupling.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://databasearchitects.blogspot.com/2026/04/safe-optimistic-lock-coupling.html"},"body_markdown":"As the number of CPU cores keeps growing, the scalability of\nconcurrent data structures becomes increasingly important. A data\nstructure that works fine on 4 cores can become a bottleneck on 32, not\nbecause of algorithmic limitations, but because of how it synchronizes\naccess.\n\nWe illustrate that with a simple binary tree. Usually these data\nstructures are protected by some kind of lock:\n\n```\nstruct Node {\n mutex lock;\n \n key_type key;\n value_type value;\n Node* left, *right;\n};\nstruct Tree {\n mutex lock;\n Node* root;\n};\n```\n\nWhen searching a value, we can traverse the data structure, lock the\nparts of the data we are currently touching, and release locks when we\nare done (“lock coupling”):\n\n```\noption Tree::lookup(key_type key) {\n lock.lock_shared();\n mutex* currentLock = &lock;\n Node* iter = root;\n option result;\n while (iter) {\n if (key == iter->key) {\n result = iter->value;\n break;\n }\n Node* next = (key < iter->key) ? iter->left : iter->right;\n if (next) next->lock.lock_shared();\n currentLock->unlock();\n currentLock = next ? &next->lock : nullptr;\n iter = next;\n }\n currentLock->unlock();\n return result;\n}\n```\n\nWhile conceptually simple, lock coupling has quite poor performance\nin practice. The problem is that it creates contention on the locks, in\nparticular for the root node. Every lookup goes through the root node,\nthus the root node is constantly locked and unlocked. While there is no\n*semantic* contention between lookups, as all readers can read\nthe root concurrently, there is *physical* contention on the lock\nitself, which limits scalability. This can be seen below, with\nconcurrent lookups in a tree of 100,000 elements, executed on a 16-core\n/ 32-thread 9950X3D.\n\n*[Figure: Lookup scalability: no locking vs lock coupling]*\n\nLookup scalability: no locking vs lock\ncoupling\n\nThis contention problem can be solved by using [Optimistic Lock\nCoupling](http://sites.computer.org/debull/A19mar/p73.pdf), a synchronization technique where readers do not perform\nany writes. The key idea here is that writers lock as usual, and\nincrease a version number when they are done updating. Readers read the\nversion number before access, read the elements they are interested in,\nand then re-check the version number. If the version number changed (or\nthe element is currently locked), the read fails and the reader tries\nagain. In (slightly simplified) code it looks like this:\n\n```\nstruct Node {\n version_lock lock;\n \n key_type key;\n value_type value;\n Node* left, *right;\n};\nstruct Tree {\n version_lock lock;\n Node* root;\n};\n\noption Tree::lookup(key_type key) {\n restart: lock_guard guard = lock.lock_optimistic();\n Node* iter = root;\n if (!guard.validate()) goto restart;\n option result;\n while (iter) {\n auto currentKey = iter->key;\n if (!guard.validate()) goto restart;\n if (key == currentKey) {\n auto currentValue = iter->value;\n if (!guard.validate()) goto restart;\n result = currentValue;\n break;\n }\n iter = (key < currentKey) ? iter->left : iter->right;\n if (!guard.validate()) goto restart;\n auto nextGuard = iter->lock.lock_optimistic();\n if (!guard.validate()) goto restart;\n guard = nextGuard;\n }\n return result;\n}\n```\n\nIt is not that different from the classic lock coupling code above,\nexcept that we always have to check for concurrent writes before acting\non the read values. The great benefit of this strategy is that the\nlookup code is purely read-only, which allows it to scale nicely with\nthe number of cores:\n\n*[Figure: Lookup scalability: all strategies]*\n\nLookup scalability: all\nstrategies\n\nWhile Optimistic Lock Coupling offers excellent performance, it is a\nbit dangerous to use. If you act upon a value before validating, you\neffectively have a race condition in your code. In this small example it\nis clear when we have to validate, but in complex code fragments it is\neasy to forget to validate.\n\nThe best way to mitigate that is to get compiler support, by encoding\nthe fact that we need to validate in the type system. We can achieve\nthat by representing unvalidated values as a dedicated type, and having\nonly the lock guard expose that value. Conceptually it looks like this\n(variants that validate multiple values omitted for simplicity):\n\n```\ntemplate \nclass unvalidated {\n T value;\n friend class lock_guard;\n};\nclass lock_guard {\n ...\n template \n optional validate(unvalidated value);\n};\n```\n\nBasically we only allow access to the original value by validating,\nwhich makes that construct safe. But how do we ensure that code properly\nwraps everything in `unvalidated`? By exposing only\nan *optimistic view* over the data. Conceptually we do the\nfollowing:\n\n```\nstruct Node {\n class OptimisticView;\n ... // as above\n};\ntemplate \nclass OptimisticPtr\n{\n T* rawPtr;\n public:\n // We cannot use operator-> here unfortunately due to C++ constraints\n typename T::OptimisticView data() const { return T::OptimisticView(rawPtr); }\n};\n// Exposes each member as unvalidated value\nclass Node::OptimisticView {\n class Node* rawData;\n public: \n unvalidated key() { return unvalidated(atomic_ref(rawData->key).load(memory_order_relaxed)); }\n unvalidated value() { return unvalidated(atomic_ref(rawData->value).load(memory_order_relaxed)); }\n unvalidated> left() { return unvalidated(OptimisticPtr(atomic_ref(rawData->left).load(memory_order_relaxed))); }\n unvalidated> right() { return unvalidated(OptimisticPtr(atomic_ref(rawData->right).load(memory_order_relaxed))); }\n unvalidated lock() { return unvalidated(lock_guard(atomic_ref(rawData->lock).load(memory_order_seq_cst))); }\n};\n```\n\nNote that the `lock()` accessor returns an\n`unvalidated`: before we can hand off to\nthe next node’s lock, we must first validate the current guard to ensure\nwe actually read a valid lock. This ensures that lock acquisition itself\nis part of the validated chain.\n\nWith this design, the optimistic code only accesses data via an\nOptimisticPtr, which makes it impossible to access the data without\nprior validation. This greatly improves the robustness of the approach.\nIt is a bit annoying that we have to manually implement accessor\nfunctions in the OptimisticView, but hopefully the [compiler will do that in the future\nautomatically](https://wg21.link/P2996).\n\nUsing these abstractions, our lookup code now becomes:\n\n```\noption Tree::lookup(key_type key) {\n restart: lock_guard guard = lock.lock_optimistic();\n auto iterOpt = guard.validate(getRootOptimistic());\n if (!iterOpt) goto restart;\n OptimisticPtr iter = *iterOpt;\n option result;\n while (iter) {\n auto currentKey = guard.validate(iter.data().key());\n if (!currentKey) goto restart;\n if (key == *currentKey) {\n auto currentValue = guard.validate(iter.data().value());\n if (!currentValue) goto restart;\n result = *currentValue;\n break;\n }\n auto next = guard.validate((key < *currentKey) ? iter.data().left() : iter.data().right());\n if (!next) goto restart;\n iter = *next;\n auto nextGuard = guard.validate(iter.data().lock());\n if (!nextGuard) goto restart;\n guard = *nextGuard; \n }\n return result;\n}\n```\n\nThe code is nearly identical to the unsafe version above, but now it\nbecomes impossible to forget to validate, as the compiler complains\notherwise. This makes this highly attractive concurrency paradigm robust\nand easy to use for all kinds of data structures.\n\nIn summary, Optimistic Lock Coupling gives us near-lockfree read\nscalability while still supporting safe concurrent writes. And by\nencoding validation requirements in the type system, we get the\nperformance benefits without sacrificing correctness. The compiler\ncatches the mistakes that would otherwise become subtle race conditions\nat runtime.\n","body_html":"

As the number of CPU cores keeps growing, the scalability of\nconcurrent data structures becomes increasingly important. A data\nstructure that works fine on 4 cores can become a bottleneck on 32, not\nbecause of algorithmic limitations, but because of how it synchronizes\naccess.

\n

We illustrate that with a simple binary tree. Usually these data\nstructures are protected by some kind of lock:

\n
struct Node {\n   mutex lock;\n   \n   key_type key;\n   value_type value;\n   Node* left, *right;\n};\nstruct Tree {\n   mutex lock;\n   Node* root;\n};
\n

When searching a value, we can traverse the data structure, lock the\nparts of the data we are currently touching, and release locks when we\nare done (“lock coupling”):

\n
option<value_type> Tree::lookup(key_type key) {\n   lock.lock_shared();\n   mutex* currentLock = &lock;\n   Node* iter = root;\n   option<value_type> result;\n   while (iter) {\n      if (key == iter->key) {\n         result = iter->value;\n         break;\n      }\n      Node* next = (key < iter->key) ? iter->left : iter->right;\n      if (next) next->lock.lock_shared();\n      currentLock->unlock();\n      currentLock = next ? &next->lock : nullptr;\n      iter = next;\n   }\n   currentLock->unlock();\n   return result;\n}
\n

While conceptually simple, lock coupling has quite poor performance\nin practice. The problem is that it creates contention on the locks, in\nparticular for the root node. Every lookup goes through the root node,\nthus the root node is constantly locked and unlocked. While there is no\nsemantic contention between lookups, as all readers can read\nthe root concurrently, there is physical contention on the lock\nitself, which limits scalability. This can be seen below, with\nconcurrent lookups in a tree of 100,000 elements, executed on a 16-core\n/ 32-thread 9950X3D.

\n

[Figure: Lookup scalability: no locking vs lock coupling]

\n

Lookup scalability: no locking vs lock\ncoupling

\n

This contention problem can be solved by using Optimistic Lock\nCoupling, a synchronization technique where readers do not perform\nany writes. The key idea here is that writers lock as usual, and\nincrease a version number when they are done updating. Readers read the\nversion number before access, read the elements they are interested in,\nand then re-check the version number. If the version number changed (or\nthe element is currently locked), the read fails and the reader tries\nagain. In (slightly simplified) code it looks like this:

\n
struct Node {\n   version_lock lock;\n   \n   key_type key;\n   value_type value;\n   Node* left, *right;\n};\nstruct Tree {\n   version_lock lock;\n   Node* root;\n};\n\noption<value_type> Tree::lookup(key_type key) {\n   restart: lock_guard guard = lock.lock_optimistic();\n   Node* iter = root;\n   if (!guard.validate()) goto restart;\n   option<value_type> result;\n   while (iter) {\n      auto currentKey = iter->key;\n      if (!guard.validate()) goto restart;\n      if (key == currentKey) {\n         auto currentValue = iter->value;\n         if (!guard.validate()) goto restart;\n         result = currentValue;\n         break;\n      }\n      iter = (key < currentKey) ? iter->left : iter->right;\n      if (!guard.validate()) goto restart;\n      auto nextGuard = iter->lock.lock_optimistic();\n      if (!guard.validate()) goto restart;\n      guard = nextGuard;\n   }\n   return result;\n}
\n

It is not that different from the classic lock coupling code above,\nexcept that we always have to check for concurrent writes before acting\non the read values. The great benefit of this strategy is that the\nlookup code is purely read-only, which allows it to scale nicely with\nthe number of cores:

\n

[Figure: Lookup scalability: all strategies]

\n

Lookup scalability: all\nstrategies

\n

While Optimistic Lock Coupling offers excellent performance, it is a\nbit dangerous to use. If you act upon a value before validating, you\neffectively have a race condition in your code. In this small example it\nis clear when we have to validate, but in complex code fragments it is\neasy to forget to validate.

\n

The best way to mitigate that is to get compiler support, by encoding\nthe fact that we need to validate in the type system. We can achieve\nthat by representing unvalidated values as a dedicated type, and having\nonly the lock guard expose that value. Conceptually it looks like this\n(variants that validate multiple values omitted for simplicity):

\n
template <class T>\nclass unvalidated {\n   T value;\n   friend class lock_guard;\n};\nclass lock_guard {\n   ...\n   template <class T>\n   optional<T> validate(unvalidated<T> value);\n};
\n

Basically we only allow access to the original value by validating,\nwhich makes that construct safe. But how do we ensure that code properly\nwraps everything in unvalidated<T>? By exposing only\nan optimistic view over the data. Conceptually we do the\nfollowing:

\n
struct Node {\n   class OptimisticView;\n   ... // as above\n};\ntemplate <class T>\nclass OptimisticPtr\n{\n   T* rawPtr;\n   public:\n   // We cannot use operator-> here unfortunately due to C++ constraints\n   typename T::OptimisticView data() const { return T::OptimisticView(rawPtr); }\n};\n// Exposes each member as unvalidated<T> value\nclass Node::OptimisticView {\n   class Node* rawData;\n   public:   \n   unvalidated<key_type> key() { return unvalidated(atomic_ref(rawData->key).load(memory_order_relaxed)); }\n   unvalidated<value_type> value() { return unvalidated(atomic_ref(rawData->value).load(memory_order_relaxed)); }\n   unvalidated<OptimisticPtr<Node>> left() { return unvalidated(OptimisticPtr(atomic_ref(rawData->left).load(memory_order_relaxed))); }\n   unvalidated<OptimisticPtr<Node>> right() { return unvalidated(OptimisticPtr(atomic_ref(rawData->right).load(memory_order_relaxed))); }\n   unvalidated<lock_guard> lock() { return unvalidated(lock_guard(atomic_ref(rawData->lock).load(memory_order_seq_cst))); }\n};
\n

Note that the lock() accessor returns an\nunvalidated<lock_guard>: before we can hand off to\nthe next node’s lock, we must first validate the current guard to ensure\nwe actually read a valid lock. This ensures that lock acquisition itself\nis part of the validated chain.

\n

With this design, the optimistic code only accesses data via an\nOptimisticPtr, which makes it impossible to access the data without\nprior validation. This greatly improves the robustness of the approach.\nIt is a bit annoying that we have to manually implement accessor\nfunctions in the OptimisticView, but hopefully the compiler will do that in the future\nautomatically.

\n

Using these abstractions, our lookup code now becomes:

\n
option<value_type> Tree::lookup(key_type key) {\n   restart: lock_guard guard = lock.lock_optimistic();\n   auto iterOpt = guard.validate(getRootOptimistic());\n   if (!iterOpt) goto restart;\n   OptimisticPtr<Node> iter = *iterOpt;\n   option<value_type> result;\n   while (iter) {\n      auto currentKey = guard.validate(iter.data().key());\n      if (!currentKey) goto restart;\n      if (key == *currentKey) {\n         auto currentValue = guard.validate(iter.data().value());\n         if (!currentValue) goto restart;\n         result = *currentValue;\n         break;\n      }\n      auto next = guard.validate((key < *currentKey) ? iter.data().left() : iter.data().right());\n      if (!next) goto restart;\n      iter = *next;\n      auto nextGuard = guard.validate(iter.data().lock());\n      if (!nextGuard) goto restart;\n      guard = *nextGuard;      \n   }\n   return result;\n}
\n

The code is nearly identical to the unsafe version above, but now it\nbecomes impossible to forget to validate, as the compiler complains\notherwise. This makes this highly attractive concurrency paradigm robust\nand easy to use for all kinds of data structures.

\n

In summary, Optimistic Lock Coupling gives us near-lockfree read\nscalability while still supporting safe concurrent writes. And by\nencoding validation requirements in the type system, we get the\nperformance benefits without sacrificing correctness. The compiler\ncatches the mistakes that would otherwise become subtle race conditions\nat runtime.

","headings":[]}}