Postgres DELETE kan echt schalen

DELETE in Postgres heeft een slechte reputatie. Veel high-performance systemen kiezen ervoor om deletes volledig te vermijden en maken gegevens in plaats daarvan schoon door volledige tabellen te truncaten of volledige partities te verwijderen. Als deletes niet zouden schalen, zou dat jammer zijn, want DELETE is veel flexibeler dan het verwijderen van partities of tabellen, vooral wanneer data heterogeen is en sommige items langer bewaard moeten blijven dan andere.

De kritiek is niet onterecht: Postgres DELETE maakt gebruik van kostbare mechanismen om te garanderen dat verwijderingen transactioneel veilig zijn. Het verwijderen van elke rij in een tabel is dan ook ordes van grootte trager dan het simpelweg verwijderen van de tabel. Toch kan DELETE schalen, zeker voor workloads die de flexibiliteit en sterke garanties ervan vereisen.

In dit artikel laten we zien hoe Postgres DELETE met de juiste optimalisaties op schaal kan worden gebruikt. We richten ons op hoe we DELETE hebben afgestemd in een workload voor duurzame workflows en wachtrijen op basis van Postgres, waarbij we de cache- en indexprestaties hebben geoptimaliseerd om retentiebeleid toe te passen op een systeem dat tienduizenden workflows en stappen per seconde verwerkt.

Hoe Postgres een rij verwijdert

Om te begrijpen waarom deletes in Postgres zo kostbaar zijn, moeten we begrijpen hoe ze werken. Wanneer je een rij verwijdert in Postgres, verwijdert de database de rij niet fysiek. Dit is omdat Postgres isolatie tussen databasetransacties moet bieden: als jouw transactie een rij verwijdert, mag die verwijdering niet zichtbaar zijn totdat je de transactie commit. Als Postgres rijen direct zou verwijderen, zouden die verwijderingen onmiddellijk zichtbaar zijn voor andere transacties (tenzij er dure locking wordt gebruikt), wat de isolatie zou schenden.

In plaats daarvan implementeert Postgres multi-version concurrency control (MVCC). Elke keer dat een rij wordt bijgewerkt, voegt Postgres een nieuwe versie van de rij in de tabel en indexen in met de bijgewerkte gegevens. Elke versie is voorzien van het transactie-ID van de transactie die deze heeft aangemaakt en het ID van de transactie die deze heeft vervangen. Wanneer je een rij verwijdert, markeert Postgres de laatste versie met jouw transactie-ID, waardoor de rij onzichtbaar wordt voor latere transacties. Dit ontwerp zorgt voor transactie-isolatie: updates door een transactie zijn niet zichtbaar tot de commit, en langlopende transacties kunnen oude versies raadplegen om een consistent "snapshot" van de gegevens te zien.

Een gevolg van MVCC is churn. Elke update en delete creëert een "dead tuple" (een oude versie van een rij), die Postgres op een gegeven moment fysiek moet verwijderen om schijfruimte terug te winnen. Postgres ruimt dead tuples op via de VACUUM-operatie (periodiek uitgevoerd door de autovacuum), die alle dead tuples vindt en verwijdert die niet langer zichtbaar zijn voor enige actieve transactie. Bij het bouwen van een systeem voor duurzame uitvoering, dat regelmatig gegevens van miljoenen workflows en hun stappen moet verwijderen, reageert deze MVCC-churn op subtiele wijze met de caching en indexen van Postgres, waardoor deletes kostbaarder worden dan ze lijken.

Problemen met lokaliteit

Workflow-verwijderingen volgen doorgaans een retentiebeleid: de gebruiker stelt een beleid in (bijvoorbeeld: "verwijder alle workflows die meer dan een week geleden zijn voltooid") en de workflow-engine handhaaft dit door periodiek alle workflows te verwijderen die de deadline hebben overschreden. De DELETE-commando's worden uitgevoerd in batches van grootte N, waarbij herhaaldelijk de N oudste workflows worden verwijderd totdat er geen workflows meer over zijn die ouder zijn dan de retentiecutoff.

Interessant genoeg ligt de prestatie-uitdaging niet bij het verwijderen van de workflows zelf, maar bij het verwijderen van de bijbehorende gegevens in andere tabellen. Workflows bestaan bijvoorbeeld meestal uit verschillende stappen, die hun output schrijven naar een aparte stepoutputs-tabel. Om de stapgegevens synchroon te houden met de workflowgegevens, gebruikten we oorspronkelijk een foreign key: elke rij in stepoutputs verwees naar de rij van de workflow in workflow_status met ON DELETE CASCADE, zodat het verwijderen van een workflow automatisch ook de stappen verwijderde.

Dit is een schoolvoorbeeld van ontwerp dat vanuit het perspectief van dataintegriteit logisch is. Maar op schaal zijn de prestaties hiervan verschrikkelijk. De reden is cache locality (cache-lokaliteit). Telkens wanneer een workflow werd verwijderd, moest Postgres elke bijbehorende stap vinden en ook verwijderen. Omdat een workflow doorgaans veel stappen uitvoert over een langere periode, staan deze stapgegevens verspreid over de schijf. Hierdoor moet voor elke stapverwijdering een volledige pagina van schijf naar het geheugen worden opgehaald, bijgewerkt en weer terug naar schijf worden geschreven. Deze cache-churn zorgde ervoor dat het verwijderen van workflows veel trager was dan het uitvoeren ervan.

Foreign keys verwijderen

Om de prestaties van de retentie te verbeteren, hebben we de foreign keys die naar de workflow_status-tabel verwezen verwijderd en de gegevens uit elke tabel afzonderlijk verwijderd. Zonder de foreign keys verloopt de retentie in fasen:

1. Eerst verwijderen we de workflow-rijen zoals voorheen. Zonder cascade-effect is dit snel.
2. Daarna voeren we soortgelijke batch-verwijderingen uit op tabellen die workflowgegevens opslaan, zoals step_outputs.

Deze batch-verwijderingen zijn snel om dezelfde reden als bij workflow_status: ze verwijderen rijen in de volgorde van hun fysieke creatie, waardoor de cache-lokaliteit hoog is.

Een complicatie in dit ontwerp is dat workflows worden verwijderd op basis van hun voltooiingstijd, terwijl de datatabellen alleen de creatietijd opslaan. Om te voorkomen dat gegevens van een nog actieve, langlopende workflow worden verwijderd, voegen we een anti-join toe aan de batch-delete; we verwijderen alleen gegevens waarvan de bijbehorende workflow al is verwijderd.

Debuggen van een index-zoekopdracht van 20 minuten

Hoewel dit nieuwe mechanisme in theorie logisch was, stuitten we tijdens de implementatie op een bizarre prestatiebug: een index-zoekopdracht die 20 minuten duurde. Het probleem zat in de eerste query van de batch-delete, die de createdat timestamp van de N-de oudste rij in de tabel zoekt. Deze query wordt correct ondersteund door een index op createdat, dus hij zou snel moeten zijn. Meestal was dat ook zo, maar soms, bij een database die bijna verzadigd was, stortten de prestaties in en duurde deze eenvoudige query meer dan 20 minuten, zelfs met een queryplan dat correct de index gebruikte.

Het bleek dat dit te maken had met hoe Postgres MVCC verwijderingen uitvoert. Om een rij te verwijderen, markeert Postgres deze met het transactie-ID van de verwijderende transactie. Latere transacties weten zo dat ze de rij moeten negeren, en de autovacuum kan deze opruimen. Deze markering wordt echter alleen op de rij zelf toegepast, niet op de indexen die naar de rij verwijzen. Dit betekent dat een query die een rij via een index zoekt, de rij zelf moet controleren (niet alleen de index-entry) om te bevestigen dat de rij niet "dood" is.

Normaal gesproken is dit geen probleem omdat dead tuples gelijkmatig over een index zijn verdeeld. Maar deze specifieke SELECT-query creëerde een worst-case scenario. Om de N-de oudste rij te vinden, loopt de query door de created_at-index van oud naar nieuw. Normaal gesproken gebeurt dit in $O(N)$ tijd. Het probleem is echter dat rijen juist van oud naar nieuw worden verwijderd. Als er onlangs een andere verwijderingsronde had plaatsgevonden en de autovacuum nog niet was begonnen, konden er miljoenen dead tuples aan het begin van de index staan. De query moet elke tuple ophalen en controleren of deze dood is voordat hij verder kan gaan. Deze miljoenen controles zorgden ervoor dat de query uitliep tot 20 minuten.

De oplossing was eenvoudig: we voegden een handmatige VACUUM op de tabel toe, vlak voor en vlak na elke retentieronde. Hierdoor worden dead tuples opgeruimd voordat ze toekomstige retentieperiodes kunnen vertragen. Door de cache-lokaliteit te verbeteren en pathologische index-scans te voorkomen, verbeterde de combinatie van handmatige VACUUM en het verwijderen van foreign keys de prestaties van de deletes met een factor tien.

Waarom geen partities?

Tot slot willen we ingaan op het alternatief: het verwijderen van partities (of het truncaten van tabellen). Sommige high-performance systemen op basis van Postgres (zoals pgmq of PgQue) vermijden DELETE volledig door datatabellen op tijd te partitioneren en oude partities te droppen zodra de gegevens niet meer nodig zijn. Dit is veel sneller omdat het MVCC volledig omzeilt; Postgres verwijdert simpelweg de bestanden op schijf.

Het probleem met partitionering is de inflexibiliteit. Een partitie kan pas worden verwijderd als élk stukje data in die partitie niet meer nodig is. Dit is geschikt voor systemen zoals berichtenwachtrijen, waar data voor een voorspelbare tijd nodig is. Het is echter niet geschikt voor een workflow-systeem dat langlopende workflows ondersteunt. Een handvol workflows die weken of maanden duren, kan het verwijderen van miljarden rijen van kortere workflows blokkeren. Daarnaast ondersteunt een partitie-gebaseerd systeem geen complexe retentiebezoeken, zoals het bewaren van verschillende klassen workflows voor verschillende periodes, of het langer bewaren van mislukte workflows dan geslaagde workflows.