Lock‑Free Transactions and Cache Switching: MVCC Techniques for Key‑Value Stores

Lock‑Free Transactions and Cache Switching

ACID is the cornerstone of relational databases, but its classic transaction model often cannot meet the performance, scale, and availability demands of modern large‑scale and NoSQL systems. Consequently, custom or semi‑transactional models are replacing the traditional approach.

Atomic Cache Switch with Read‑Committed Isolation

A simple method suitable for read‑heavy workloads (e.g., e‑commerce data updates) loads all data into a cache and uses a proxy that interacts with two caches, A and B, following these steps:

Only one cache is active at any time; the proxy routes all requests to the active cache.

When updating, new data is loaded into the inactive cache.

The switch flag is toggled so the proxy starts directing reads to the newly active cache.

If "non‑repeatable reads" are allowed, the old cache can be cleared immediately; otherwise the proxy maintains a list of in‑flight transactions and routes their requests to the old cache until all those transactions commit or abort, after which the old data is removed.

Partial Cache Switch for Incremental Updates

The same principle can be extended to three caches to support partial updates:

Read requests go to the primary cache ("PRIMARY").

New or updated entries are written to a "NEW" cache; keys of deleted items go to a "DELETE" cache.

During commit, a global flag tells the proxy to check "NEW" and "DELETE" first; if the data is not found there, it falls back to "PRIMARY".

After commit, changes from "NEW" and "DELETE" are merged back into "PRIMARY" in a non‑atomic way.

The global flag is then reset, and all reads return to the primary cache.

Optionally, the old data can be copied to another cache to enable rollback, even for full‑scale updates.

MVCC Transaction Model (Repeatable‑Read Isolation)

Isolation can be achieved by versioning each data item, similar to PostgreSQL's MVCC. Each transaction receives a globally unique, monotonically increasing transaction ID (XID). Every cache entry stores two timestamps, xmin and xmax, assigned as follows:

When a transaction creates an entry, xmin is set to its XID and xmax is null.

When a transaction deletes an entry, xmin stays unchanged and xmax is set to the deleting transaction's XID; the entry remains in the cache but is marked as deleted.

When a transaction updates an entry, the old version receives xmax equal to the updating transaction's XID, and a new version is inserted with xmin set to that XID and xmax null (effectively a delete‑plus‑insert).

An entry is visible to a transaction if both conditions hold: xmin is set and ≤ the current transaction's XID. xmax is null, or equals the XID of an uncommitted/aborted transaction, or is > the current transaction's XID.

Both xmin and xmax can carry a bit indicating whether the transaction was committed or aborted, enabling the visibility check.

Drawbacks include the complexity of cleaning up obsolete versions because different transactions may see different versions. Two common strategies mitigate this:

Store all versions in the same key‑value space without limit and run a background process to reclaim old versions, either on a schedule or triggered by reads/writes.

Keep only the latest version in the primary key‑value space; older versions are stored elsewhere in a fixed‑size area. The latest version points to the previous one, but the chain cannot be traversed arbitrarily, and very old versions may be discarded, causing lookup failures for transactions that need them.