Papers we love: In Search of an Understandable Consensus Algorithm

Momenteel zijn gedistribueerde systemen een hot topic. We zien steeds vaker dat dezelfde functionaliteit van applicaties over meerdere machines wordt opgedeeld. Het buzzword “horizontal schaling” gaat hier bijvoorbeeld over. Dit schalen over meerdere machines is relatief eenvoudig wanneer je niet over (gedeelde) state na hoeft te denken. Wanneer een applicatie, laten we hem foo noemen, alleen maar rekentaken uitvoert is het bijvoorbeeld eenvoudig om deze te schalen. Indien de capaciteit van deze applicatie gemaximaliseerd is kun je hier een tweede instantie bij plaatsen, waarna je het werk verdeeld over de twee nodes. Je krijgt dan dus fooA en fooB. Dit zelfde principe is dan ook toe te passen voor beschikbaarheid. Het falen van individuele machines is daarmee geen groot probleem meer.

Hiermee loop je echter al snel tegen problemen op. Wat gebeurt er als je een andere applicatie, bar, hebt, die gebruik wil maken van de dienst van foo? Moet bar dan kennis hebben van alleen fooA? Of alleen fooB? Of juist allebei? Maar wat gebeurt er dan wanneer een van de instanties van foo verdwijnt? Of er juist een bij komt? En wat gebeurt er als bar zelf bijvoorbeeld ook weer gaat schalen? Of als machines (permanent) onbereikbaar zijn?

Zoals je kunt begrijpen hebben we hier nog maar het puntje van de ijsberg blootgelegd. Er is echter wel duidelijk een onderliggend patroon te herkennen. Wat je eigenlijk wilt is het creëren van een gedeelde state (de lijst van instanties van foo’s) welke gedeeld wordt tussen meerdere machines. Deze dient dan gelijk te zijn over de verschillende deelnemers. Foutscenarios, zoals bijvoorbeeld die hierboven beschreven is, mogen deze aanname niet breken. Uitval van individuele machines moet dus de gelijkheid van de data over verschillende machines niet beïnvloeden. Wanneer je deze garantie niet meer kunt geven (bijvoorbeeld omdat er geen meerderheid meer beschikbaar is) dienen de machines hier zich ook van bewust te zijn. Hiermee voorkom je dan dus ook een single point of failure.

Het probleem wat hierboven is beschreven wordt vaak aangeduid met de term consensus . Centraal staat de vraag hoe je een akkoord kunt bereiken wanneer er meerdere nodes zijn, die zich potentieel misdragen. Eind jaren 80 is er, met de publicatie van Paxos, al een fundamentele oplossing voor dit probleem gegeven. Er zijn nog wel veel recente ontwikkelingen, zoals bijvoorbeeld Zookeeper. Paxos is vrij lang het standaard model omtrent consensus vraagstukken geweest, al zijn de meeste mensen het over een ding eens: het is een vrij complex concept en de implementatie is behoorlijk foutgevoelig.

Diego Ongaro heeft (een deel van) zijn promotieonderzoek besteed aan het maken van alternatief voor Paxos. Een van de voornaamste doelen was zorgen dat men volledig begrijpt wat het consensus protocol precies doet. Samen met John Ousterhout heeft Diego een paper geschreven met de titel In Search of an Understandable Consensus Algorithm, waarin zij hun voorstel Raft presenteren. Door de nadruk op eenvoud en het feit dat deze nieuwe implementatie erg betrouwbaar en efficiënt is, is hun voorstel erg snel omarmt door de engineering community. Dit heeft als leuke randeffect dat er ook erg laagdrempelige materialen te vinden zijn die je rond kunnen leiden door wat Raft nu precies is. Erg interessante links zijn een website met een high level overview en zelfs een interactieve simulatie en een presentatie die je stap voor stap door het protocol heen loopt.

De doelstelling eenvoud is ook goed te herkennen in de paper zelf. Ik vind hem goed leesbaar, maar vooral ook goed gestructureerd. Alle verschillende deelproblemen worden helemaal losgetrokken en individueel behandeld. Het is daarnaast ook een vrij eerlijke, of misschien zelfs wel open paper. Er worden een aantal voorbeelden genoemd waarin men eerst een andere keuze gemaakt heeft dan hetgeen het eindresultaat geworden is. De eerste opzet resulteerde bijvoorbeeld in minder stabiele of complexere code, waardoor de werking niet meer kon worden gegarandeerd. Na enkele iteraties om het te finetunen besluit men dan toch te kiezen voor een andere aanpak en geven ze aan dat ze dankzij voortschrijdend inzicht een betere oplossing kunnen definiëren. Hierdoor voelt het echt alsof je een beschrijving van een proces aan het lezen ben, niet alleen de (erg indrukwekkende) eindsituatie.

Een ander gaaf aspect is hoe ontzettend dichtbij deze paper bij dagelijkse werkzaamheden staat. Gedistribueerde systemen klinken als een niche, maar consensus is iets wat toch al snel naar voren komt. Iedereen die bijvoorbeeld te maken heeft met microservices (service discovery) of clusters (shared state, reboot strategieën) zal de problemen herkennen en begrijpen waarin Raft je kan helpen. Daarnaast zijn grote en hele bekende producten als Consul en etcd direct op (verschillende!) implementaties van Raft gebouwd, ondanks dat het zo jong is. Dit is dus helemaal geen theoretische ver-van-je-bed-show paper, maar juist een die slaat op zaken die je in het dagelijks werk gewoon tegen komt.

Wat voor je eigen engineering werkzaamheden ook erg interessant is, zijn de keuzes die door de hele paper heen worden gemaakt. Een typisch voorbeeld is bijvoorbeeld de sectie over elections. Hierbij zijn een behoorlijk aantal (zeldzame) foutscenario’s op een conceptuele hoop geschoven. Deze worden dan allemaal op een manier opgelost: de huidige verkiezing mislukt, waarna de volgende wordt gestart. Hiermee blijft de implementatie eenvoudig en ben je al vrij snel in staat om te redeneren over hoe een verkiezing er stap voor stap aan toe gaat.

Kortom, het is een leuke paper die een praktische blik werpt op een complex probleem wat dicht bij het werk van een engineer zal liggen. De expliciete doelstelling om complexiteit te tacklen vind ik daarnaast ook noemenswaardig. Een leuke take-home message is wat mij betreft ook de eerste alinea uit de conclusie van de paper. Bij implementatie van algoritmes is het niet te voorkomen dat je af zult wijken van de pure vorm zoals deze beschreven en/of bewezen is. Het is hierdoor dan ook extra belangrijk om echt te begrijpen wat een algoritme doet. Wanneer je het complete begrip mist ben je gedoemd implementatiefouten te maken, waardoor alle (bewezen) eigenschappen van het originele algoritme in feite niets meer waard zijn.


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.