Coordination-freeness and Parallel Evaluation of Conjunctive Queries

We leven in een tijdperk waarin heel wat bedrijven en organisaties over enorme hoeveelheden data beschikken. Denk maar aan bedrijven zoals bijvoorbeeld Amazon, dat over de koopgegevens van miljoenen klanten beschikt. Deze data bezitten is één ding, maar men wil ze ook kunnen verwerken en analyseren. In het geval van Amazon kan men bijvoorbeeld uit deze gegevens de voorkeuren van een klant afleiden om op deze manier nieuwe producten te kunnen aanbevelen aan deze klant. Het probleem is echter dat de hoeveelheid data zo groot is dat ze niet meer op één computer kan worden verwerkt. We spreken in dit geval over big data. 

Om met deze problematiek om te gaan wordt er vaak beroep gedaan op clusters van gewone computers die met een network verbonden zijn. De beschikbare data kan dan worden verdeeld over deze computers die vervolgens in parallel kunnen samenwerken om de nodige berekeningen te doen. Zo'n berekening noemen we een query in de context van databases. Het gedistribueerd uitvoeren van een query brengt echter enkele nieuwe uitdagingen met zich mee, waarvan er twee in deze thesis behandeld worden.

Coördinatie-vrijheid

Wanneer er gebruik gemaakt wordt van een netwerk van computers om een query uit te voeren, kan het gebeuren dat deze computers onderling moeten coördineren om tot het gewenste resultaat te komen. Dit kan bijvoorbeeld het geval zijn wanneer de nodige data zich op verschillende computers in het netwerk bevindt. De synchronisatie tussen de verschillende computers die nodig is voor dergelijke coördinatie is echter een bron van inefficiëntie tijdens de berekening van de query. Het is daarom interessant om te onderzoeken welk soort queries kunnen berekend worden zonder expliciete coördinatie. In 2012 werd er een theoretisch model opgesteld om te redeneren over gedistribueerde berekeningen. Met behulp van dit model werd vervolgens formeel gedefiniëerd wat het betekent voor een query om berekenbaar te zijn zonder expliciete coördinatie. In deze thesis formaliseren we een alternatieve definitie voor coördinatie-vrijheid die in sommige gevallen iets intuïtiever is om mee te redeneren, en tonen we aan dat deze equivalent is. Verder stellen we ook een variatie voor op het theoretisch model waarbij alle messages steeds worden ontvangen in dezelfde volgorde als dat ze werden verzonden. Het originele model beschouwt een betrouwbaar netwerk in de zin dat messages nooit verloren gaan, maar hun volgorde blijft niet behouden. Dit in tegenstelling tot de betrouwbaarheidsgaranties van het populaire TCP-protocol. 

Efficiëntie van de Berekening

Een andere uitdaging bestaat erin om de berekening zelf zo efficiënt mogelijk te laten verlopen. Hiervoor bestuderen we enkele algoritmen die trachtten om de hoeveelheid communicatie die nodig is tussen de verschillende computers te minimaliseren. Het eerste algoritme is een verbeterde versie van het naiëve broadcasting, waarbij elke computer de data die hij bezit doorstuurt naar alle ander computers. In de verbeterde versie zullen gegevens enkel worden doorgestuurd indien ze wel degelijk kunnen bijdragen aan het resultaat. Het tweede algoritme, HyperCube genaamd, maakt gebruik van hash-functies om de data die samen tot een resultaat kan leiden naar dezelfde computer in het netwerk te sturen. De naam van dit algoritme volgt uit het feit dat we de computers in een denkbeeldige multidimensionale hypercube schikken om te bepalen welke data we naar welke computer sturen. Dit algoritme is optimaal wanneer er in de data die we verwerken geen waarden zitten die veel vaker voorkomen dan de andere waarden. Met optimaliteit bedoelen we hier dat de maximale hoeveelheid data die op één computer verzameld wordt zo klein mogelijk wordt gehouden. Tot slot beschrijven we een derde algoritme dat gebaseerd is op het HyperCube algoritme, maar geen restricties legt op de data. Dit algoritme bepaalt op voorhand welke waarden zeer vaak voorkomen in de data en welke rol deze waarden spelen in de te berekenen query. Afhankelijk hiervan worden bepaalde deelverzamelingen van de data met een gespecialiseerd algoritme verwerkt om te vermijden dat er te veel data naar één enkele computer gestuurd wordt.

Implementatie

Zowel het HyperCube algoritme als het op HyperCube gebaseerde algoritme werden in het kader van deze thesis geprogrammeerd in het populaire big data framework Apache Spark. Zo kon er een experimentele analyse van het gedrag van deze algoritmen uitgevoerd worden. Hieruit bleek onder andere dat het HyperCube algoritme zeer efficiënt is voor het berekenen van queries die veel tussenliggende resultaten genereren tijdens de berekening. Voor queries waarbij dit niet het geval is bleek HyperCube niet bepaald snelheidswinst op te leveren.

Conclusie

In deze thesis trachten we een antwoord te geven op enkele praktische uitdagingen die het gedistribueerd verwerken van grote hoeveelheden data met zich meebrengt. De algoritmen die hierboven vermeld werden zijn slechts van toepassing op een specifieke deelklasse van queries. Er is dus nog veel onderzoek mogelijk naar efficiënte algoritmen, zowel op theoretisch als op praktisch vlak.