MapReduce: hoe Google leerde rekenen op duizenden computers tegelijk
Stel je voor dat je moet uitzoeken hoe vaak elk woord voorkomt in miljoenen boeken. Alleen zou je daar jaren over doen. Maar als je het werk verdeelt over duizenden mensen, elk met een stapeltje boeken, en ze tellen daarna hun deelresultaten bij elkaar op, is het karwei in een middag geklaard. Dat is in essentie wat MapReduce doet, maar dan met computers in plaats van mensen, en met complete kopieën van het internet in plaats van boeken.
MapReduce is een programmeermodel en bijbehorend systeem dat door Google is ontwikkeld om enorme hoeveelheden data te verwerken door het werk automatisch te verdelen over heel veel computers tegelijk, een zogeheten cluster. De programmeur hoeft alleen te beschrijven wat er met een klein stukje data moet gebeuren en hoe de deelresultaten samengevoegd moeten worden; het systeem regelt zelf de verdeling van het werk, de communicatie tussen machines en wat er gebeurt als een van die machines uitvalt.
Wat is het precies?
MapReduce werkt in twee hoofdstappen, die de naam van het systeem verklaren. In de Map-fase wordt een grote hoeveelheid data eerst opgeknipt in kleine stukken, die over de beschikbare machines in het cluster worden verdeeld. Elke machine, ook wel een node genoemd, voert dezelfde bewerking uit op zijn eigen stukje data en produceert daaruit een lijst van zogeheten key-value paren: een sleutel (bijvoorbeeld een woord) met een bijbehorende waarde (bijvoorbeeld het getal 1, voor 'één keer gezien').
Daarna volgt de shuffle-stap: het systeem verzamelt alle key-value paren met dezelfde sleutel en stuurt ze naar dezelfde machine, ongeacht waar ze oorspronkelijk vandaan kwamen. Dat is technisch het lastigste onderdeel, omdat er enorme hoeveelheden data tussen machines over het netwerk moeten worden verplaatst en gesorteerd.
Ten slotte is er de Reduce-fase. Elke machine krijgt nu alle waarden die bij één sleutel horen en voegt die samen tot een eindresultaat, bijvoorbeeld door ze op te tellen. Voor het woordentelvoorbeeld betekent dit dat alle losse '1'-tjes voor het woord 'de' worden samengeteld tot het totale aantal keren dat 'de' voorkomt in de hele dataset.
Wat MapReduce bijzonder maakte, is de manier waarop het omgaat met fouten. Bij een cluster van duizenden gewone servers valt er vrijwel altijd wel een machine uit tijdens een grote berekening. MapReduce houdt dit in de gaten en herstart automatisch het werk van een uitgevallen machine op een andere, zonder dat de hele berekening opnieuw hoeft te beginnen. De data zelf staat meestal op een gedistribueerd bestandssysteem, een opslagsysteem dat bestanden in meerdere kopieën over veel machines verspreidt zodat data niet verloren gaat als één schijf of server crasht. Bij Google heette dit systeem het Google File System (GFS); de latere open-source variant heet HDFS (Hadoop Distributed File System).
Wat wil men ermee bereiken?
Het achterliggende doel van MapReduce was vooral praktisch: Google moest regelmatig bewerkingen uitvoeren op een kopie van vrijwel het hele world wide web, bijvoorbeeld om de zoekindex te bouwen waarmee Google Search resultaten kan tonen. Dat soort taken is met één supercomputer niet te doen, maar wel als je het werk verdeelt over duizenden gewone, relatief goedkope servers.
Voor het paper uit 2004 schreven Google-ingenieurs Jeffrey Dean en Sanjay Ghemawat vaak losse, ingewikkelde programma's voor elke nieuwe grootschalige klus, telkens met eigen code voor het verdelen van werk, het herstellen van fouten en het verplaatsen van data tussen machines. MapReduce moest die herhaling wegnemen: programmeurs zouden zich alleen nog hoeven te concentreren op de kern van hun probleem (wat moet er met de data gebeuren), terwijl het systeem de lastige, foutgevoelige infrastructuur voor zijn rekening nam.
Daarmee streefde MapReduce drie dingen na: schaalbaarheid (moeiteloos meer machines toevoegen als de data groeit), betrouwbaarheid (blijven werken ook als onderdelen van het cluster uitvallen) en eenvoud voor de programmeur, die geen expert in gedistribueerde systemen hoefde te zijn om toch gebruik te maken van duizenden machines tegelijk.
Voorbeelden uit de praktijk
Google gebruikte MapReduce intern vanaf het begin van de jaren 2000 voor uiteenlopende taken, met als bekendste toepassing het periodiek herbouwen van de index waarmee Google Search het web doorzoekbaar maakt.
Een van de bekendste voorbeelden buiten Google is The New York Times, die in 2007 met de open-source variant Hadoop op de cloudinfrastructuur van Amazon (EC2) ongeveer vier miljoen gescande krantenpagina's uit het archief omzette naar PDF-bestanden. Het werk, dat op één machine weken zou hebben gekost, was met een tijdelijk gehuurd cluster in ongeveer een dag klaar.
Yahoo was een van de eerste grote bedrijven die investeerde in de ontwikkeling van Hadoop en zette het systeem op zeer grote schaal in, op clusters met duizenden machines, onder meer voor het bouwen van zoek- en advertentiesystemen.
Facebook bouwde in de jaren daarna een van de grootste Hadoop-gebaseerde datawarehouses ter wereld, gebruikt voor intern analytics-werk op de enorme hoeveelheden gebruikersdata die het bedrijf verzamelde.
Ook Amazon Web Services speelde hierop in met de clouddienst Amazon EMR (Elastic MapReduce), waarmee bedrijven een Hadoop-cluster konden opstarten zonder zelf servers te hoeven beheren, en het alleen betalen zolang ze het gebruikten.
Hoe ver is de techniek?
MapReduce is inmiddels meer een historisch fundament dan een actief ontwikkelde technologie op zichzelf. Na het invloedrijke Google-paper uit 2004 ontstond binnen enkele jaren Apache Hadoop, een open-source implementatie van dezelfde ideeën, die rond 2008 een volwaardig project van de Apache Software Foundation werd. Hadoop maakte MapReduce toegankelijk voor bedrijven buiten Google en vormde tussen ongeveer 2008 en 2014 de ruggengraat van veel 'big data'-projecten.
Sindsdien is het veld flink veranderd. MapReduce schrijft tussentijdse resultaten telkens weg naar schijf, wat betrouwbaar is maar relatief traag. Vanaf 2009-2010 ontwikkelde het AMPLab van UC Berkeley Apache Spark, dat waar mogelijk data in het werkgeheugen (RAM) houdt in plaats van naar schijf te schrijven, en daardoor voor veel taken aanzienlijk sneller is. Spark heeft MapReduce in de praktijk grotendeels verdrongen als standaardkeuze voor nieuwe big-data-toepassingen.
Ook Google zelf gebruikt MapReduce als los systeem al lang niet meer als hoofdtechnologie. Intern stapte het bedrijf over op flexibelere opvolgers zoals FlumeJava en later Google Cloud Dataflow, dat mede de basis vormde voor het open Apache Beam-project. Het is dus eerlijk om te zeggen dat het onderliggende idee van MapReduce (data opsplitsen, parallel verwerken, resultaten samenvoegen) nog springlevend is en in talloze moderne systemen doorleeft, maar dat MapReduce als specifieke techniek en merknaam grotendeels tot het verleden behoort. Wie vandaag 'MapReduce' hoort, gebruikt in de praktijk vaak eerder Spark of een clouddienst die op vergelijkbare beginselen is gebouwd.
Wie werken eraan?
Google publiceerde het oorspronkelijke concept en gebruikte het jarenlang intern, met Jeffrey Dean en Sanjay Ghemawat als de auteurs van het grondleggende paper. De Apache Software Foundation beheert sindsdien Hadoop als open-source project, met Doug Cutting en Mike Cafarella als de oorspronkelijke bedenkers, die het systeem eerst bouwden voor het zoekmachineproject Nutch.
Yahoo was historisch een belangrijke sponsor en grootgebruiker van Hadoop-ontwikkeling. Commerciële bedrijven als Cloudera en Hortonworks (die later fuseerden) bouwden bedrijfsmodellen rond ondersteuning en distributie van Hadoop. Amazon Web Services biedt met Amazon EMR een cloudversie aan, en Facebook was een van de bedrijven die Hadoop op zeer grote schaal inzetten.
Voor de opvolger Spark is Databricks, opgericht door de oorspronkelijke makers van Spark aan UC Berkeley, tegenwoordig de belangrijkste commerciële speler, naast een brede open-source gemeenschap onder de vlag van de Apache Software Foundation.