Modeling Concurrency Control as a Learnable Function

Dit paper introduceert NeurCC, een nieuw geleerd algoritme voor concurrentiecontrole dat door het leren van een efficiënte zoekfunctie met behulp van Bayesiaanse optimalisatie en een grafreductie-algoritme, consistente en snellere prestaties boekt dan bestaande methoden over diverse werklasten.

De kern

Stel je voor dat een database een enorm drukke supermarkt is. Duizenden klanten (transacties) lopen tegelijkertijd rond, pakken producten van de planken en proberen ze te kopen. Het probleem? Soms willen twee klanten tegelijk hetzelfde laatste product pakken. Als ze niet goed worden geregeld, ontstaat er chaos: producten verdwijnen, prijzen worden verkeerd bijgewerkt, of klanten blijven elkaar blokkeren in de gangen.

In de wereld van computers heet dit concurrentiebesturing. De vraag is: hoe regel je deze chaos zodat alles snel gaat, maar toch correct blijft?

Dit paper introduceert NeurCC, een slimme nieuwe manier om deze chaos te regelen. In plaats van een starre set regels te gebruiken, leert NeurCC als een ervaren supermarktmanager die elke dag anders reageert op de drukte.

Hier is hoe het werkt, vertaald naar alledaags taal:

1. Het oude probleem: De "Eén Maat Past Alles" Manager

Vroeger hadden supermarkten twee vaste managers:

• De Strikte Manager (2PL): Deze zegt: "Als je een product wilt, moet je wachten tot de ander klaar is." Dit werkt goed als het druk is, maar als er weinig klanten zijn, staat iedereen alleen maar te wachten. Het is traag.
• De Risicovolle Manager (OCC): Deze zegt: "Pak maar wat je wilt, we checken pas aan het einde of er iets fout is." Dit is supersnel als het rustig is, maar als het druk is, vallen er veel klanten om (transacties worden geannuleerd) omdat ze toch op hetzelfde product stonden te wachten.

Het probleem is dat de drukte in een supermarkt verandert. Soms is het druk (allemaal mensen bij de kassa), soms rustig. Een vaste manager kan hier niet goed op inspelen.

2. De Oplossing: NeurCC, de Leerzame Manager

NeurCC is geen vaste manager, maar een slimme, lerende manager. Hij heeft een magisch notitieboekje (een zoektabel) waarin hij voor elke situatie de perfecte actie noteert.

• Hoe leert hij? Stel, de manager ziet dat er veel mensen zijn die snel door de gangen rennen (hoge drukte). Hij leert dan: "Ah, hier moet ik streng zijn en blokkeren." Maar als hij ziet dat het rustig is, leert hij: "Hier kunnen mensen gewoon vooruit, zonder te wachten."
• Hij combineert het beste van twee werelden: Hij kan kiezen om te wachten, te blokkeren, of zelfs om producten "vuil" te lezen (een product pakken dat nog niet officieel op de plank ligt, maar wel beschikbaar is), afhankelijk van wat op dat moment het snelst is.

3. De Magische Zoektabel (De "Look-up Table")

Stel je voor dat NeurCC een enorme, maar zeer snelle telefoonlijst heeft.

• De Invoer: De manager kijkt naar de situatie: "Hoeveel mensen zijn er? Welke producten worden er gepakt? Is het product populair?"
• De Uitvoer: In een fractie van een seconde (honderden CPU-cycli, wat voor een computer een oogwenk is) slaat hij de lijst op en zegt: "Oké, voor deze situatie: laat de klant A voorbij, maar wacht op klant B."

Dit is veel sneller dan het elke keer opnieuw uitrekenen. De lijst past in het geheugen van de computer, dus het kost bijna geen tijd om te raadplegen.

4. Hoe leert hij zo snel? (De "Proefneming")

Het lastige deel is: hoe vind je de perfecte lijst zonder uren te testen? Als je elke lijst in de echte supermarkt zou testen, zou de winkel urenlang dicht moeten blijven. Dat kan niet.

NeurCC gebruikt twee slimme trucs:

1. De Voorspeller (Bayse Optimalisatie): In plaats van alles in de echte supermarkt te testen, gebruikt NeurCC een "simulatie-manager". Deze voorspeller leert van eerdere tests en zegt: "Ik denk dat deze nieuwe regel waarschijnlijk werkt." Zo hoeft hij niet alles te testen, maar alleen de meest belovende opties.
2. De Kaartverkleiner (Graph Reduction): Soms zijn de regels complex (wie wacht op wie?). NeurCC tekent een kaart van de verwarring. Hij snapt dat sommige lijnen op de kaart niet nodig zijn (bijvoorbeeld: "Als er maar één klant is, hoeft er niemand te wachten"). Hij knipt die onnodige lijnen weg. Hierdoor wordt de zoektocht naar de perfecte regel veel sneller.

5. Waarom is dit zo cool?

• Het past zich aan: Als de supermarkt plotseling een sale heeft (de workload verandert), merkt NeurCC dit direct. Hij start dan een nieuwe leerfase en past zijn regels binnen enkele minuten aan. Andere systemen zouden dagen nodig hebben of helemaal vastlopen.
• Het is sneller: In tests bleek NeurCC tot 3 tot 4 keer sneller te werken dan de beste bestaande systemen.
• Het is slim: Hij leert niet alleen wat te doen, maar ook hoe te doen. Hij leert bijvoorbeeld dat het soms beter is om een klant even te laten wachten op een specifieke manier, in plaats van hem helemaal te blokkeren.

Samenvatting in één zin

NeurCC is als een supermarktmanager die niet vastzit aan oude regels, maar elke dag een nieuwe, slimme strategie bedenkt door te kijken naar de drukte, zodat klanten altijd snel en correct hun boodschappen kunnen doen, of het nu rustig is of een enorme sale.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Modeling Concurrency Control as a Learnable Function" in het Nederlands.

Titel: Modeling Concurrency Control as a Learnable Function (NeurCC)

Auteurs: Hexiang Pan et al. (NUS, Deakin University, Renmin University of China, SUTD, Zhejiang University)

---

1. Het Probleem

Concurrentiebesturing (Concurrency Control - CC) is essentieel voor moderne transactiedatabases om correctheid (transactie-isolatie) te garanderen terwijl hardware-concurrentie wordt benut. Bestaande algoritmen hebben echter twee fundamentele tekortkomingen:

1. Gebrek aan robuustheid: State-of-the-art algoritmen (zoals 2PL, OCC, Silo) presteren goed in specifieke scenario's (bijv. 2PL bij hoge concurrentie, OCC bij lage concurrentie), maar falen vaak bij diverse of veranderende werklasten.
2. Trage aanpassing: Bestaande adaptieve methoden (zoals Polyjuice, CormCC) gebruiken vaak "classify-then-assign" strategieën of evolutionaire algoritmen. Deze vereisen handmatige aanpassingen bij werklast-drifts (veranderingen in het patroon van transacties) of hebben te lange optimalisatietijden, waardoor ze niet snel genoeg reageren op dynamische omgevingen.

Het doel is een CC-algoritme te ontwerpen dat:

• Hoge prestaties levert over een breed scala aan werklasten.
• Snel te optimaliseren is om dynamische drifts bij te houden.
• Een lage overhead heeft (cruciaal voor in-memory databases waar transacties in microseconden worden uitgevoerd).

---

2. Methodologie: NeurCC

NeurCC (Neural Concurrency Control) modelleert concurrentiebesturing niet als een statisch algoritme, maar als een leerbare functie $F: \{s\} \rightarrow \{a\}$. Deze functie mapt de huidige staat van de database ($s$) naar een set van concurrentiebesturingsacties ($a$).

A. Het Leermodel

In plaats van te kiezen uit een beperkt aantal bestaande algoritmen, decomposeert NeurCC CC in een reeks acties die willekeurig kunnen worden gecombineerd:

• Conflictdetectie: Geen detectie, detectie van kritieke conflicten, of detectie van alle conflicten.
• Conflictresolutie: Timeout-waarden, prioriteitstoewijzing (gebaseerd op transactie-eigenschappen), en pipeline-wait acties (waarbij transacties wachten op afhankelijke transacties om door te gaan in plaats van te aborteren).
• Implementatie: De functie $F$ wordt geïmplementeerd als een efficiënte zoektafel (lookup table) binnen de database. De invoer is een compacte vector van staten (bijv. data-hotness, aantal afhankelijke transacties), en de uitvoer is direct de actie. Dit zorgt voor een zeer lage overhead (enkele honderden CPU-cycles).

B. De Leerproces (Optimalisatie)

Het vinden van de optimale functie $F$ is een complex zoekprobleem. NeurCC gebruikt een hybride aanpak om dit snel op te lossen:

1. Bayseiaanse Optimalisatie: Gebruikt een surrogate model (Gaussian Process) om de prestaties van de functie te voorspellen zonder de volledige database te hoeven draaien. Dit vermindert de kostbare evaluatietijd aanzienlijk.
2. Gereduceerde Graaf Zoekalgoritme (Graph Reduction Search): Voor de complexe "pipeline-wait" acties (die discrete en niet-continu variabele zijn) wordt het probleem herschreven als het leren van een optimale conflictgraaf. Het algoritme start met een volledige conflictgraaf en reduceert deze via mutaties (knopen samenvoegen, randen verwijderen) om de beste structuur te vinden. Dit lost het probleem van gebrek aan "locality" op, wat traditionele ML-methoden (zoals Policy Gradient) inefficiënt maakt.
3. Pijplijn van Optimalisatie: Het proces verloopt in vier fasen, waarbij eerst de acties met het grootste potentieel voor verbetering (conflictdetectie en pipeline-wait) worden geoptimaliseerd, gevolgd door fijnafstelling van timeouts en prioriteiten.

C. Werkstroom en Drift-detectie

• Executie: Voor elke transactie-actie wordt de databasestaat verzameld, de functie $F$ opgeroepen (via lookup), en de actie uitgevoerd.
• Drift-detectie: Een achtergrondprocess monitort de TPS (Transactions Per Second). Bij een significante daling (bijv. >10%) wordt de optimalisatie geactiveerd.
• Update: Een nieuwe functie wordt geoptimaliseerd en atomair geladen in de cache zonder bestaande transacties te blokkeren.

---

3. Belangrijkste Bijdragen

1. NeurCC: Een nieuw, leergeleerd CC-algoritme dat hoge prestaties bereikt over diverse werklasten en snel reageert op veranderingen.
2. Universeel Model: Een unificatie van bestaande CC-algoritmen in één leerbare functie die een breed scala aan ontwerppatronen (van 2PL tot OCC en pipeline-wait) kan nabootsen en combineren.
3. Efficiënt Leeralgoritme: Een innovatieve combinatie van Bayseiaanse optimalisatie en graafreductie die de optimalisatietijd drastisch verkort ten opzichte van eerdere methoden.
4. Gedetailleerde Evaluatie: Uitgebreide tests tegen vijf state-of-the-art baselines (2PL, Silo, CormCC, Polyjuice, IC3).

---

4. Resultaten

De evaluatie is uitgevoerd op de Silo database-engine met werklasten zoals YCSB en TPC-C, in zowel "Stored Procedure" als "Interactive Transaction" modus.

• Doorvoer (Throughput): NeurCC presteert consistent beter dan alle baselines.
  • Tot 3.32x hogere doorvoer dan Polyjuice.
  • Tot 4.38x hogere doorvoer dan 2PL.
  • Tot 4.27x hogere doorvoer dan Silo.
• Optimalisatietijd: NeurCC convergeert veel sneller naar een optimale configuratie.
  • 11x sneller dan Polyjuice (gemiddeld 9.67 minuten vs. 1.78 uur).
  • Dit maakt het zeer robuust tegen werklast-drifts; het kan zich aanpassen binnen minuten.
• Stabiliteit: In tegenstelling tot evolutionaire zoekalgoritmen (zoals bij Polyjuice) die grote fluctuaties vertonen, toont NeurCC een stabielere leercurve dankzij de gebruikte surrogate modellen.
• Dynamische Werklasten: Bij plotselinge veranderingen in de werklast (bijv. van 1 naar 16 threads) herstelt NeurCC zich snel en behoudt een hogere doorvoer dan statische algoritmen.

---

5. Betekenis en Impact

Dit paper markeert een verschuiving in hoe concurrentiebesturing wordt benaderd: van handmatig ontworpen, statische algoritmen naar data-gedreven, dynamisch leerbare systemen.

• Adaptiviteit: NeurCC lost het probleem op dat geen enkel enkel CC-algoritme voor alle situaties optimaal is. Door te leren welke combinatie van acties (detectie, timeout, prioriteit) op dat moment werkt, past het zich automatisch aan.
• Efficiëntie: Het bewijst dat machine learning technieken succesvol kunnen worden toegepast in de kritieke paden van database-systemen, mits de overhead laag wordt gehouden (via lookup tables en surrogate modellen).
• Toekomstbestendig: De aanpak is schaalbaar en kan nieuwe werklastpatronen aan, zonder dat database-ontwikkelaars handmatig nieuwe algoritmen hoeven te coderen of te tunen.

Kortom, NeurCC biedt een robuust, snel en hoogpresterend alternatief voor traditionele CC-methoden, wat essentieel is voor moderne, dynamische cloud-databases.