Papers we love: Retroactive datastructures

 
01 januari 2017

Deze keer wil ik het onderwerp ‘tijd’ aankaarten. Tijd in combinatie met datastructuren om precies te zijn. Het uitgangspunt van de paper van deze maand is dat er verschillende scenario’s zijn waarin niet alleen de huidige status van een datamodel, belangrijk is, maar ook de manier waarop dit tot stand gekomen is. Hierdoor zou het dan mogelijk moeten zijn om retroactief datamutaties door te voeren. Hierover is in 2007 een paper gepubliceerd met de titel Retroactive Data Structures.

De opzet van het artikel is als volgt: het begint met een introductie over wat retroactieve data structuren zijn, gevolgd door een motivatie over waarom je retroactieve datastructuren nuttig kunnen zijn. Vervolgens worden er twee maten van retroactiviteit bepaald ( partial en full retroactivity). Als laatste zijn er een behoorlijk aantal transformaties beschreven en bewezen die aantonen hoe je bepaalde bekende datastructuren retroactief kunt maken en welke tijd-, en geheugengebruik implicaties dit heeft.

Een beschrijving van een retroactive datastructure is erg eenvoudig: stel je voor dat een bepaalde operatie op een datastructuur onjuist was en verwijderd dient te worden. Dit is bij een op zichzelf staand stukje informatie niet zo’n probleem, maar bij afgeleide informatie is dit veel lastiger om terug te rekenen. Neem het voorbeeld van een hypotheek waarbij er foutief een extra aflossing twee keer is meegenomen in de betalingen. Na drie maanden komt de verstrekker hier achter, en wil deze een correctie uitvoeren. Normaliter zou dit gecrediteerd moeten worden en zou er over het tijdsverschil (de drie maanden) ook een correctie plaats moeten vinden over het renteverschil. Al met al een relatief complexe situatie.

Bij retroactieve datastructuren is het idee dat je de foutieve aflossing direct verwijderd uit het verleden. Doordat de mutatie achteraf gezien nooit heeft bestaan (hij is immers in het ‘verleden’ verwijderd) zullen

eventuele effecten ervan ook geen weerslag meer hebben op de huidige state. Iets algemener: stel je hebt een reeks datamutaties [u1,u2,u3] die op tijdstippen [t1,t2,t3] plaatsvinden. Als deze allemaal aan een queue worden toegevoegd dan zal na t3 de queue er als volgt uit zien: [u1,u2,u3]. Als nu blijkt dat er op t0 eigenlijk nog een element u0 vergeten was kan deze op het moment t4 worden toegevoegd, maar met bewerkingstijd t0. Het resultaat: [u0,u1,u2,u3].

Zoals aangegeven zijn er twee vormen van retroacitiviteit: partial en full (of general). Het bovenstaande voorbeeld is er een uit de eerste categorie. Hierbij kun je mutaties doorvoeren op willekeurige tijdstippen, maar kun je niet per se de state op een willekeurige t bekijken. Bij de tweede categorie kan dat wel, je zou dan dus kunnen stellen ‘geef mij de queue op t = 2’, waarbij je dan dus [u1,u2] terug krijgt. Het nadeel van full retroacivity is wel dat het bij veel datastructuren een behoorlijke extra overhead introduceert waardoor het toepassen erg duur wordt.

Bij het lezen van deze paper worstelde ik zelf continu met de vraag waarom. Waarom zou je dit soort datastructuren inzetten, inclusief bijbehorende performance penalty voor full reactivity, terwijl er ook andere opties zijn? Misschien zit ik er verkeerd in, maar de ideeën uit deze paper komen op mij over als een soort “poor man’s event sourcing”. Hier zijn mutaties ook inzichtelijk, kunnen er queries gedaan worden op willekeurige tijdstippen en is er met enkele kanttekeningen ook retroactiviteit mogelijk. Wat Fowler een ‘incorrect event’ noemt beschrijft een groot stuk van de usecases uit de retroactive datastructures paper.

Iets wat in deze paper echter compleet genegeerd wordt is de complexiteit die retroactiviteit binnen je domein teweeg brengt. Ten eerste kunnen er op arbitraire momenten wijzigingen in de geschiedenis plaatsvinden wat effect heeft op afgeleide state (externe systemen bijvoorbeeld). Daarnaast wordt er ook vrij gemakkelijk omgegaan met mutaties. In tegenstelling tot event sourcing verdwijnen deze geheel en kun je achteraf ook niet meer aantonen dat er een mutatie heeft plaatsgevonden. Er is dus totaal geen accountability, met de bijbehorende risicos van dien.

Kortom, er wordt een interessante maar beperkte case geschetst. Vergelijkbaar met andere ideeën is het wat mij betreft te kortzichtig. Ik kan me usecases indenken dat een full blown event sourcing oplossing te heftig is (bijvoorbeeld in low-memory embedded systemen, tijd-kritische applicaties), maar retroactive datastructures lijken mij zelden de oplossing.


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Gave Technologie