Het geheim achter schaalbaarheid – deel 3

De vorige artikelen hadden snelheid als onderwerp. Het werd toen duidelijk dat, zodra je meerdere dingen parallel wilt gaan doen, het lastiger wordt om te voorspellen hoe snel de applicatie zal zijn. Maar dat is niet het enige wat lastiger wordt: ook de functionele correctheid wordt een stuk ingewikkelder.

Samenwerken is lastig

 

Samenwerken is soms voor mensen lastig en hetzelfde geldt eigenlijk voor computers. Doordat bepaalde taken ineens parallel uitgevoerd worden, ontstaan allerlei nieuwe problemen die je met een enkel proces niet hebt. Eén probleem is bijvoorbeeld timing. Niet alle taken zullen even lang duren. Wanneer een volgende taak input nodig heeft van voorgaande taken, dan moet er een mechanisme komen om dat te coördineren. De volgorde en de duur van de taken is meestal niet te voorspellen en dus kan de executievolgorde van een groep van taken elke keer anders zijn.

 

 

Een heel ander probleem ontstaat, wanneer twee taken tegelijkertijd dezelfde resource willen gebruiken. Neem bijvoorbeeld het printen van twee documenten op dezelfde printer. Als beide taken tegelijk worden uitgevoerd, dan komen bij de printer afwisselend stukjes van het ene document en van het andere document. Als daar geen rekening mee gehouden is, dan worden de printjes vrij onleesbaar.

 

Threads

Om parallellisme te introduceren zijn er verschillende stijlen van programmeren. De meest bekende stijl is wel het werken met threads. Deze stijl heeft als basiselementen geheugen, logica en threads. In Java wordt het geheugen gevormd door objecten. De logica wordt beschreven in methoden. Deze logica wordt vervolgens uitgevoerd door een thread. Als er meerdere threads zijn, dan kunnen meerdere methoden tegelijkertijd uitgevoerd worden. Het geheugen wordt gedeeld door alle processen. Zo kunnen de threads hun (deel)resultaten publiceren door bijvoorbeeld de state van een object aan te passen. Als er meer threads dan core's zijn, dan wordt door de JVM (of het besturingssysteem) de beschikbare rekentijd eerlijk verdeeld over de threads. Dit noem je scheduling.

 

Soms worden threads tijdelijk gepauzeerd om een andere thread wat tijd te geven. Deze manier van parallel programmeren is vrij primitief. Er is geen enkel handvat om volgordelijkheid aan te geven tussen threads. Als verschillende threads met dezelfde objecten willen werken, dan is het lastig om ervoor te zorgen dat ze elkaars werk niet overschrijven. Om het printerprobleem uit de vorige paragraaf te voorkomen, zal een thread het printer object moeten reserveren. Dat reserveren kan door bijvoorbeeld een vlaggetje inUse (een lock) te zetten en daarmee de printer te claimen. Alle threads moeten dus eerst kijken of dat vlaggetje gezet is, voordat die thread de printer kan claimen. Bijvoorbeeld:

class Printer {
            boolean inUse;
            public boolean inUse() { return inUse; }
 
            public void claim() { inUse = true; }
            public void release() { inUse = false; }
            public void print(String document) { }
};
           
private Printer printer;
 
class PrintableDocument extends Thread {
            public void run() {
                        while (printer.inUse()) {
                                    Thread.yield();
                        }
                        printer.claim();
                        printer.print(document);
                        printer.release();
            }
}

 

Die inUse en claim operaties zijn twee losse instructies. Wat nu als een thread precies gepauzeerd wordt na de inUse check, maar voordat hij de printer kan claimen? Dan claimen twee threads de printer en dit is precies wat we willen voorkomen. Wat misschien nog wel erger is, is er wel een garantie dat er precies één kopie is van dat vlaggetje? Misschien wordt die wel gecachet in een register van een van de core's.  En -om hier nog een schepje bovenop te doen- de JVM, maar ook alle moderne cpu's, mogen instructies in een andere volgorde uitvoeren en herschrijven, zolang dat maar vanuit een enkele thread geredeneerd hetzelfde resultaat oplevert. Er is geen garantie dat de check wel voor de set wordt uitgevoerd, als door bijvoorbeeld de JVM besloten wordt de code te herschrijven.

 

private static Printer theInstance;
 
public static Printer getInstance() {
            if (theInstance == null) {
                        theInstance = new Printer();
            }
 
            return theInstance;
}

 

Quizvraag: Is de printer hier gegarandeerd een singleton? En kan getInstance() null teruggeven?

 

In Java bestaat een belangrijk keyword dat hier de oplossing biedt: synchronized. Zo'n stuk code wat gedeeld geheugen benaderd, noem je een kritieke sectie. Om die kritieke sectie kun je een synchronized blok plaatsen, met als parameter een willekeurig Object. Dit synchronized keyword zorgt ervoor dat, voor alle gesynchroniseerde blokken rondom hetzelfde Object, er maximaal 1 thread actief kan zijn. Gezien vanuit het perspectief van de gesynchroniseerde threads is die sectie nu ook atomair. Ook geldt voor die threads dat voor elk object wat je benadert in die kritieke sectie er nog maar één kopie is. Het keyword synchronized zorgt er dus voor dat de draaiende threads op dat moment op elkaar afgestemd worden.

 

Kritieke secties die niet (volledig) gesynchroniseerd zijn, kunnen leiden tot dure bugs. Ze treden alleen op bij combinaties van threads en zijn lastig te reproduceren. Dit is meestal het geval als de applicatie het wat drukker heeft en er meer om de resources gevraagd wordt. En dat zijn nou juist de momenten waarop je geen problemen erbij wilt hebben. Te grote stukken synchroniseren om problemen te voorkomen is ook niet wenselijk, effectief reduceer je dan de concurrency van je applicatie. En die verhogen, daar is het nu juist om te doen.

 

Deadlock en starvation

Door het locken van resources krijg je meer grip op hoe threads samenwerken, maar het introduceert ook weer nieuwe typen problemen. Een deadlock kan ontstaan, wanneer twee threads beide een resource gelockt hebben die de ander nodig heeft. Beide threads wachten nu op elkaar.

 

Deadlock: Thread A lockt resource 1 en wacht op resource 2, Thread B doet het omgekeerde.

 

Om dit op te lossen zijn talloze mogelijkheden, maar het is lastig om het helemaal correct te krijgen. Kijk bijvoorbeeld maar eens naar het ‘dining philosophers problem’[1] van Dijkstra.

 

Een andere categorie problemen kan samengevat worden onder starvation. Threads die veel resources locken of resources voor een lange tijd bezet houden, blokkeren vele andere threads. Als threads meer tijd besteden aan het wachten op locks of op elkaars resultaat, dan heeft parallelliseren weinig zin meer. De overhead wordt dan op een gegeven moment te groot. Wanneer processen niet of nauwelijks bij de benodigde resources kunnen komen, dan noem je dat starvation. Het kiezen wanneer welke thread rekentijd krijgt, is de taak van de scheduler en deze is dus in grote mate bepalend of en waar starvation optreedt.

 

Andere stijlen

Gelukkig zijn er ook andere programmeerstijlen die wat minder foutgevoelig zijn. In de vorige editie van Java Magazine heb je al iets kunnen lezen over Akka. Deze bibliotheek hangt een andere stijl aan, die van agents of actors. Het grote verschil met threads is dat actors geen geheugen delen. In plaats daarvan kunnen ze berichten naar elkaar sturen. De synchronisatie tussen de actors wordt geregeld door het framework. Iets minder krachtig, maar volgens een vergelijkbaar idioom kun je in Java 8 met (Completable)Futures werken. Hoewel het niet voor iedereen even intuïtief werkt, voorkomt het een aantal van de bovenstaande problemen. Het nadeel is vaak wel dat door de vele hoeveelheden agents die ontstaan, het lastig is om de structuur van de applicatie en het algoritme te snappen.

 

Netwerken

In voorgaande paragrafen ging het over threads die op één enkele machine draaiden. Het centrale probleemgebied is de communicatie tussen threads die nodig is om te synchroniseren. Of dat nu via gedeeld geheugen gaat of via berichten, de impliciete aanname is steeds dat het signaal altijd aankomt. Maar als dat signaal nu over een netwerk kabel gaat, bijvoorbeeld wanneer de threads op verschillende machines draaien? Die kunnen stuk gaan. TCP/IP lost een hoop voor ons op, maar het houdt op bij een kapotte netwerkkabel zonder alternatieve route.

 

Een mooie illustratie van het probleem is het zogenaamde 'Two generals problem'. Het beschrijft twee legers, een blauw en een rood leger. Het rode leger is groter dan het blauwe leger maar is gesplitst in twee gelijke delen (A1 en A2), gelegerd aan verschillende kanten van het blauwe leger. Het rode leger kan winnen, mits beide helften tegelijk aanvallen. Als slechts één helft aanvalt, dan gaat blauw winnen. De enige manier die de rode generaals hebben om onderling te communiceren is een soldaat een bericht meegeven en hem, door de vijandelijke linies heen, te sturen naar de andere kant. Er is een goede kans dat het bericht niet aankomt. Is er een manier te vinden, zodat de rode generaals zeker weten van elkaar op welk tijdstip ze kunnen aanvallen? Een voorbeeld, generaal A1 stuurt een soldaat met het bericht “val om 12 uur aan”. Nadat de soldaat vertrokken is, bedenkt de generaal dat hij nu niet weet of het bericht wel aankomt. Misschien valt hij dan in zijn eentje aan. Hij stuurt een tweede soldaat met het bericht 'val om 12 uur aan, stuur me een bericht terug als je het ontvangen hebt, anders gaat het niet door'. Maar nu heeft generaal A2 een probleem: als hij het tweede bericht ontvangt, dan kan generaal A2 wel een soldaat terugsturen, maar hoe weet A2 of die soldaat wel aankomt. Misschien valt A2 dan wel alleen aan. Het probleem is onoplosbaar. Communicatie en daarmee atomaire transacties, zoals we die gewend zijn op een enkele machine, zijn niet mogelijk.

 

Two generals problem (wikipedia)

 

CAP theorie

Brewer maakte op basis van dit fenomeen een observatie. Een gedistribueerd systeem heeft drie eigenschappen: consistentie, beschikbaarheid en partitioneerbaarheid (CAP theory: consistency, availability and partitionability). Van die drie eigenschappen kun je er slechts twee realiseren, de derde vervalt automatisch.

 

Hoewel het niet strikt is gedefinieerd wat hij precies bedoelde met die termen, en zonder exacte definities wil het nogal eens tot discussie leiden, is de strekking vrij duidelijk. Grofweg kun je zeggen dat een systeem consistent is, wanneer je iets vraagt aan een willekeurige server en je altijd hetzelfde antwoord krijgt. Dat betekent dat elke server dezelfde 'waarheid' moet zien. Beschikbaarheid betekent dat het systeem nog steeds moet functioneren, ook als een server stuk is. En partitioneerbaarheid betekent dat communicatie tussen servers kan uitvallen en er partities kunnen ontstaan. Dat laatste krijg je vanzelf als je meerdere servers over een netwerk verbindt die allemaal een deel van de waarheid kennen.

 

In de praktijk zie je dit ook terug. Je hoort niemand klagen dat Facebook op je mobiel een andere timeline toont dan de website. Consistentie is voor hen minder belangrijk dan beschikbaarheid. De grootte van hun dataset maakt partitionering onvermijdelijk. Banken maken typisch andere keuzes: daar is consistentie het grootste goed. Zodra een bank groter wordt en partitionering in het spel komt, dan sneuvelt de beschikbaarheid. En dan is er nog de gelukkige groep die geen partitionering nodig heeft: zij hoeven niet te kiezen tussen consistentie en beschikbaarheid. Totdat ze groter groeien.

 

De grote verscheidenheid aan NoSQL databases vindt hun grondslag in deze theorie: ergens moeten harde keuzes gemaakt worden. Die keuzes kun je maar beter bewust maken, anders heeft iemand anders ze wel voor je gemaakt. Daar waar een klassieke database voor ACID properties zorgt (atomic, consistent, isolated en durable), kiezen de NoSQL databases vaak voor BASE (basically available, eventually consistent). Ook hier geldt dat daar geen harde definities voor zijn. Een handige omschrijving van deze keuzes is bijvoorbeeld een quorem. Een quorem zet het aantal servers (N) af tegen hoeveel lees- (R) en schrijfacties (W) die gedaan moeten zijn op die servers, voordat een operatie als succesvol mag worden beschouwd. Enkele voorbeelden:

R = N, W = 1	Master-slave setup (1 schrijfbare master, meerdere leesbare slaves)	Hoge kans op inconsistentie
R + W  > 2N	Alle acties moeten bevestigd worden door alle servers	Klassieke ACID properties mogelijk, maar geen beschikbaarheid
R + W > N	Aantal servers kleiner dan benodigde bevestigingen	Inconsistentie is mogelijk, maar te detecteren
R < N, W < N	Niet alle servers hoeven te bevestigen	Inconsistentie, maar wel beschikbaar

Natuurkunde en quantum mechanica

Mark Burgess maakt in zijn boek 'The science of our information structure' de vergelijking tussen natuurkunde en informatica. Er zijn een aantal opvallende gelijkenissen die in deze context gemaakt kunnen worden. Een vergelijking die voor de hand ligt is dat, net als in de natuurkunde, het observeren of monitoren van een systeem, dat systeem ook automatisch beïnvloed. Het meten zelf kost immers ook resources.

 

Materiaalkunde kan uitspraken doen over gemiddelde eigenschappen van materiaal, dat terwijl de kleinste onderdelen zich niet eens deterministisch gedragen. Ook hier kan iets geleerd worden uit de natuurkunde, wanneer vele servers of agents gebruikt worden.

 

Een ander mooi voorbeeld is het 'split brain' probleem. Dit ontstaat bijvoorbeeld bij een gedistribueerd systeem dat verdeeld is over twee datacenters. Wanneer de verbinding tussen beiden wegvalt, kunnen beide datacenters besluiten dat het andere datacenter stuk is. Ze acteren dan beide als 'master' en creëren daarmee hun eigen werkelijkheid. ID's kunnen dubbel worden uitgegeven en tegengestelde beslissingen kunnen worden genomen. Pas zodra de communicatie hersteld is, blijkt dat er meerdere werkelijkheden zijn. Welke van deze waarheden wint, hangt af van de applicatie. De vergelijking met Schrödingers kat[2] is snel gemaakt. Een grote webwinkel had bijvoorbeeld een dergelijk probleem met hun winkelmandjes. Hun oplossing was commercieel gezien erg handig: de twee versies van de winkelmandjes werden gewoon bij elkaar opgeteld.

 

Om grip te krijgen op deze onderwerpen heeft Mark Burgess de 'promise theory' [3] ontwikkeld. Dit is een systeem kan alleen beloften doet over dingen die dat systeem zelf onder controle heeft. En je kunt er niet zonder meer vanuit gaan dat die belofte nagekomen wordt, er kunnen immers dingen fout gaan. Daar waar het programmeren van agents al lastig kan zijn, met promise theory gaat het nog een stapje verder.

 

Conclusie

In drie artikelen is een theoretische achtergrond geschetst bij schaalbaarheid. Allereerst kun je algoritmische complexiteit verminderen en je beschikbare geheugen optimaal benutten met caching. Als dat niet genoeg performance oplevert, dan wordt het tijd om te schalen. Eerst door meerdere cores te gebruiken en later zelfs door meerdere servers te gebruiken. In welke mate dat kan, is ervan afhankelijk of de hoeveelheid werk meegroeit. Daarnaast wordt het correct houden van je applicatie vele malen ingewikkelder. Het werken met parallelle processen is een stuk lastiger, dan wanneer het een puur sequentieel programma is. Het lijkt een eenvoudige rekensom: een server extra kopen is een stuk goedkoper dan programmeurs aan het werk zetten. Maar de vraag is dan of alles nog wel blijft werken zoals het bedoeld is. De keuzes die gemaakt worden, zijn niet triviaal en moeten goed uitgelegd worden aan de eindklant.

 

Voor ons vakgebied is het in ieder geval goed nieuws. Of de klant nou besluit om meer hardware te kopen of niet, voor programmeurs is er altijd werk aan de winkel!

 

[1] https://en.wikipedia.org/wiki/Dining_philosophers_problem

[2] https://en.wikipedia.org/wiki/Schrodingers_cat

[3] https://en.wikipedia.org/wiki/Promise_theory