Modeling Concurrency Control as a Learnable Function

This paper introduces NeurCC, a novel learned concurrency control algorithm that utilizes Bayesian optimization and a graph reduction search to efficiently learn a high-performance function mapping database states to control actions, thereby consistently outperforming state-of-the-art algorithms across diverse and dynamic workloads.

The Gist

Imagine a busy, high-speed kitchen in a restaurant. This kitchen is a database, and the chefs are transactions trying to cook meals (process data) at the same time.

The biggest problem in this kitchen is congestion. If two chefs try to use the same stove or grab the same ingredient at the exact same time, they have to stop and wait. If they aren't careful, they might accidentally ruin a dish (corrupt data) or get stuck in a loop where Chef A waits for Chef B, who is waiting for Chef A, and nobody cooks anything. This is called a deadlock.

Traditionally, restaurants used rigid rules to manage this:

• The "Lock" Rule (2PL): "If you want the stove, you must lock it. No one else can touch it until you're done." This is safe but slow. If the stove is busy, everyone else just stands around waiting.
• The "Guess" Rule (OCC): "Go ahead and cook! If you realize you used an ingredient someone else just changed, throw your dish away and start over." This is fast when things are calm, but chaotic when the kitchen is super busy.

The problem is that real life isn't static. Sometimes the kitchen is quiet (low traffic), and sometimes it's a chaotic dinner rush (high traffic). Old rules are too rigid; they can't switch strategies fast enough when the crowd changes.

Enter NeurCC: The "Smart Kitchen Manager"

The paper introduces NeurCC, a new system that acts like a super-intelligent, learning kitchen manager. Instead of following a single rigid rulebook, NeurCC learns a custom strategy for every single moment in the kitchen.

Here is how it works, using simple analogies:

1. The "Look-Up" Menu (The Function)

Imagine NeurCC doesn't write a new rulebook every time. Instead, it builds a massive, ultra-fast menu.

• The Input (The State): The manager looks at the current situation: Is the kitchen crowded? Is the chef working on a hot dish? Is the ingredient popular?
• The Output (The Action): Based on that situation, the menu instantly tells the chef exactly what to do: "Go ahead and grab the ingredient!" or "Wait 5 seconds!" or "Stop and restart your dish!"

This menu is so fast that the chef doesn't even have to think; they just glance at it and act. This happens in microseconds.

2. Learning by Trial and Error (The Optimization)

How does NeurCC build this perfect menu? It doesn't just guess. It uses a smart "trial and error" process:

• The Simulator (Bayesian Optimization): Instead of actually crashing the kitchen to test a new rule, NeurCC uses a virtual simulator. It predicts, "If we try this new rule, the kitchen will probably run 20% faster." It picks the most promising ideas to test in the real kitchen.
• The Graph Puzzle (Graph Reduction): Sometimes, the rules get complicated (like a tangled knot of chefs waiting for each other). NeurCC uses a special algorithm to untangle the knot, finding the simplest path to let everyone cook without bumping into each other.

3. Adapting to the Crowd (Workload Drift)

This is NeurCC's superpower.

• Old Systems: If the restaurant suddenly goes from a quiet lunch to a chaotic dinner rush, the old manager keeps using the "quiet lunch" rules. The kitchen grinds to a halt until a human manager manually changes the rules (which takes hours).
• NeurCC: It constantly watches the kitchen. The moment it senses the crowd getting bigger, it says, "Okay, the rules aren't working anymore." It quickly runs its simulator, finds a new set of rules for the "dinner rush," and swaps the menu instantly. It does this so fast that the customers (users) barely notice a hiccup.

Why is this a big deal?

Think of it like GPS navigation vs. a static paper map.

• Old Algorithms (Paper Maps): They are great for a specific route. If traffic changes, the map is useless until you buy a new one.
• NeurCC (Live GPS): It knows the current traffic, the accidents, and the road closures. It recalculates the best path in real-time.

The Results

The paper tested NeurCC against the best "static" managers and other "learning" managers.

• Speed: NeurCC was up to 4 times faster than the old methods.
• Adaptability: It learned the best rules 11 times faster than other learning systems.
• Versatility: Whether the kitchen is empty or packed, NeurCC finds the perfect balance between "going fast" and "not crashing."

In short: NeurCC is a database that doesn't just follow rules; it learns how to dance with the data, changing its steps instantly to keep the music playing smoothly, no matter how wild the party gets.

Technical Summary

Here is a detailed technical summary of the paper "Modeling Concurrency Control as a Learnable Function" (NeurCC).

1. Problem Statement

Modern transactional databases rely on Concurrency Control (CC) algorithms to ensure correctness (serializability) while exploiting hardware concurrency. However, existing state-of-the-art CC algorithms face significant limitations:

• Workload Sensitivity: Classical algorithms like Two-Phase Locking (2PL) and Optimistic Concurrency Control (OCC) perform well only under specific conditions (e.g., 2PL for high contention, OCC for low contention) but fail to adapt to diverse or dynamic workloads.
• Dynamic Adaptation: Existing adaptive or learned approaches (e.g., Polyjuice, CormCC) often struggle with workload drifts. They require manual reconfiguration or suffer from prohibitively long optimization times (minutes to hours), making them ineffective for rapidly changing environments.
• Optimization Challenges: Learning optimal CC actions is difficult because:
  1. The search space is vast, combining design choices from many algorithms.
  2. The overhead of the CC mechanism must be negligible (microseconds/nanoseconds) compared to transaction execution.
  3. The optimization landscape is non-continuous and lacks locality (small changes in parameters can cause dependency cycles and massive performance drops), rendering standard gradient-based ML techniques ineffective.

2. Methodology: NeurCC

The authors propose NeurCC, a novel learned CC algorithm that models concurrency control as a learnable function $F: \{s\} \rightarrow \{a\}$, mapping database states to conflict-handling actions.

A. Unified Model of Concurrency Control

NeurCC decomposes CC into a sequence of Conflict Detection and Conflict Resolution actions, rather than selecting a monolithic algorithm.

• State ($s$): A vector of lightweight, lock-free features collected per operation (e.g., data hotness, number of dependent transactions, transaction type, access ID).
• Action ($a$): A tuple containing:
  • Conflict Detection: No detection, Detect critical, or Detect all.
  • Resolution: Timeout value, Transaction priority, and Pipeline-wait rules (e.g., how many accesses of a dependent transaction to wait for).
  • Exposure: Whether to expose uncommitted writes (dirty reads).
• Implementation: The function $F$ is implemented as an in-database lookup table. This ensures the decision-making process takes only hundreds of CPU cycles, fitting within the critical path of transaction execution.

B. Learning and Optimization Pipeline

NeurCC employs a hybrid optimization strategy to find the optimal function $F$ quickly, addressing the non-continuous nature of the search space:

1. Surrogate Modeling (Bayesian Optimization):

   • Instead of running the database for minutes to evaluate a function, NeurCC trains a Gaussian Process (surrogate) model to predict system throughput based on the function parameters.
   • It uses the Upper Confidence Bound (UCB) acquisition function to balance exploration and exploitation, guiding the search toward promising regions.

2. Graph Reduction Search (for Pipeline-Wait Actions):

   • Pipeline-wait actions (critical for avoiding dependency cycles) are non-continuous and hard to optimize via standard Bayesian methods.
   • NeurCC reformulates this as learning an optimal conflict graph. It starts with a full static conflict graph and uses a genetic search-inspired algorithm to mutate the graph (via edge removal and node merging) to find the configuration that minimizes dependency cycles while maximizing concurrency.

3. Optimization Pipeline:

   • The process is staged to prioritize high-impact actions:
     • Stage 1: Optimize Conflict Detection ($F_D$) and Pipeline-Wait ($F_P$) using Graph Reduction (yields ~80% of gains).
     • Stage 2: Optimize Timeout ($F_T$) using Bayesian Optimization.
     • Stage 3 & 4: Refine the conflict graph and fine-tune all parameters.
   • Feature Selection: A separate Bayesian optimization step selects the most influential features to reduce the state space size.

C. Deployment and Adaptation

• Drift Detection: A background monitor tracks throughput. If a relative change (e.g., >10%) is detected, it triggers the optimization pipeline.
• Zero-Downtime Update: New functions are optimized in the background. Once ready, they are loaded into the cache, and an atomic pointer switch updates the active function without blocking ongoing transactions.

3. Key Contributions

1. Novel CC Model: Proposes a unified, learnable function model that captures a wide spectrum of existing CC designs (from 2PL to OCC and pipeline-waiting) and allows for arbitrary combinations of conflict detection and resolution mechanisms.
2. Efficient Optimization Algorithm: Introduces a hybrid approach combining Bayesian Optimization (for continuous parameters like timeouts) and Graph Reduction Search (for discrete pipeline-wait rules) to overcome the lack of locality in the search space.
3. High-Performance Execution: Implements the learned function as a lightweight in-database lookup table, ensuring the overhead is negligible compared to transaction execution time.
4. Comprehensive Evaluation: Extensive experiments comparing NeurCC against five state-of-the-art baselines (2PL, Silo, CormCC, Polyjuice, IC3) across diverse workloads (YCSB, TPC-C) and modes (Stored Procedure, Interactive).

4. Experimental Results

The evaluation was conducted on a 24-core server using YCSB and TPC-C workloads.

• Throughput Performance:
  • NeurCC consistently outperforms all baselines.
  • In Stored Procedure mode, NeurCC achieves up to 3.32× higher throughput than Polyjuice, 4.38× than 2PL, and 4.27× than Silo.
  • In Interactive mode, it achieves up to 1.96× higher throughput than the second-best baseline.
• Optimization Speed:
  • NeurCC converges to peak performance significantly faster. It is 11× faster than Polyjuice (9.67 minutes vs. 1.78 hours on average).
  • This speed allows NeurCC to adapt effectively to workload drifts, whereas baselines often fail to reach optimal performance within the same timeframe.
• Robustness:
  • NeurCC maintains high performance under rapid workload changes (e.g., switching thread counts every second), demonstrating superior stability compared to static or slowly adapting algorithms.
• Ablation Studies:
  • The optimization pipeline's prioritization of $F_D$ and $F_P$ accounts for the majority of performance gains.
  • Both transaction type and execution history features are critical for high performance.

5. Significance

• Paradigm Shift: NeurCC moves beyond "classify-then-assign" heuristics to a fine-grained, operation-level learning approach that synthesizes the best aspects of multiple CC strategies dynamically.
• Practical Viability: By solving the "slow optimization" and "high overhead" problems, NeurCC makes learned concurrency control viable for production databases with dynamic workloads.
• Generalizability: The framework is general enough to cover existing algorithms (2PL, OCC, IC3, etc.) as special cases, providing a unified theoretical and practical foundation for future CC research.

In summary, NeurCC demonstrates that modeling concurrency control as a learnable function, optimized via a specialized hybrid search algorithm, can significantly outperform traditional and existing learned methods in both throughput and adaptability.