Het wait() en is voorbij

 
26 april 2009

Tijdens de J-Spring 2009 heb ik een sessie bijgewoond over Multiverse: een Java implementatie van Software Transactional Memory. Tijdens deze sessie vergelijkt Peter Veentjer de gangbare manier van concurrency control in het geheugen met de manier waarop multiverse hiermee omgaat.

Plussen en minnen
De traditionele manier van concurrency control is lock-based zoals in het volgende voorbeeldje:

Op deze manier weet je zeker dat de methoden op elkaar moeten wachten en dat wijzigingen aan balance zichtbaar zijn voor alle threads (na de wijziging).
Lock-based concurrency control heeft ook nadelen, een daarvan is deadlocks. Als de code van het voorbeeld uitgevoerd wordt blijven beide threads op elkaar wachten waardoor ze nooit eindigen. Een ander nadeel: het is moeilijk om atomic behaviour af te dwingen. Wat gebeurt er als het saldo te laag is om over te boeken of als het bijschrijven op de andere rekening niet lukt, maar de bijbehorende bij- of afschrijving wel is uitgevoerd?

Voor dit probleem zijn een aantal oplossingen:

  • Gebruik een database  als transactional memory. Een database heeft volledige ACID (Atomicity, Consistency, Isolation, Durability) waardoor betrouwbare transacties verzekerd zijn. Nadelen van deze mogelijkheid zijn bijvoorbeeld relatief trage I/O (t.o.v. RAM), en de ontbrekende polling mogelijkheden.
  • Transactional Memory. Hier zijn alle wijzigingen atomic. Dat houdt dus in dat een wijziging of wel of niet plaatsvindt, maar nooit gedeeltelijk. Dat betekent dus ook dat een object voor de buitenwereld altijd in een consistente staat verkeert. Een ander kenmerk is dat je er vanuit kunt gaan dat de code uitvoer sequentieel plaatsvindt – althans, dat is het resultaat.

Zoals ik al zei is Multiverse een Java implementatie van Software Transactional Memory met de volgende eigenschappen:

  • POJO gebaseerd
  • Geen overbodige optimalisaties: minimale overhead op read/write
  • Hibernate-achtige semantiek
  • Gebruikt Multiverse Concurrency Control (wordt gebruikt in databases: elke gebruiker krijgt een snapshot van de database; wijzigingen zijn pas zichtbaar voor anderen nadat de transactie gecommit is).
  • Thread notification in de vorm van een Retry of OrElse i.p.v. de old-skool wait() en notifyAll()

Retry
Het retry mechanisme werkt als volgt: Er wordt een RetryError gegooid als een transactie afbreekt met een retry. De RetryError wordt opgevangen door de TransactionTemplate (vergelijkbaar met een Spring HibernateTemplate), die vervolgens een Latch registeert bij alle adressen die gelezen zijn tijdens de transactie. Als de Latch geopend is begint een nieuwe transactie.

OrElse
OrElse voert ook een transactie uit. Zodra die transactie afbreekt met een retry wordt een tweede transactie uitgevoerd. Als beide transacties afbreken met een retry worden beide transacties opnieuw uitgevoerd zodra een er een relevante wijziging is gemaakt. Kort gezegd in pseudo:

doit:
try {
    x
} orelse {
    try {
        y
    } orelse {
        waitForRelevantChange();
        break doit;
    }
}

Conclusie
Een duidelijk voordeel van STM is dat het concurrency control vereenvoudigt en daarmee een complex probleem oplost. STM introduceert echter nieuwe complexe problemen: de implementatie moet bekend zijn en er treden problemen op die vergelijkbaar zijn met bijvoorbeeld de Hibernate database-abstractie. Multiverse is nog in ontwikkeling en ik denk dat de problemen die het ‘veroorzaakt’ minder zwaar wegen dan de problemen die het oplost. Voor meer informatie over STM / multiverse en de broncode de kun je kijken op googlecode. Peter Veentjer heeft zelf ook een blog waarop hij zo nu en dan wat schrijft over multiverse. 
Overige literatuur over dit onderwerp kun je onder andere vinden in het boek Transactional Memory van James Larus en Ravi Rajwar en in het boek The art of multiprocessor programming, geschreven voor Maurice Herlihy en Nir Shavit.


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Architectuur, Java (EE)

Tags: , , ,