Scriptieprijs 2017

Coordination-freeness and Parallel Evaluation of Conjunctive Queries

Brent Chesny
In deze thesis bestuderen we het theoretisch concept van coordination-freeness in een gedistribueerd database systeem en onderzoeken we enkel efficiënte algoritme voor het parallel evalueren van conjunctieve queries.

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.

Bibliografie

[1]  Apache Hadoop. http://hadoop.apache.org. Accessed: 2017-05-15.

[2]  Apache Spark. http://spark.apache.org. Accessed: 2017-04-04.

[3]  Movielens Data Set. https://grouplens.org/datasets/movielens/. Accessed: 2017-03-24.

[4]  Myria. http://myria.cs.washington.edu. Accessed: 2017-05-10.

[5]  Twitter Data Set. https://an.kaist.ac.kr/traces/WWW2010.html.

Accessed: 2017-01-22.

[6]  Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of

Databases. Addison-Wesley, 1995.

[7]  Foto N. Afrati and Je↵rey D. Ullman. Optimizing multiway joins in a map-reduce environment. IEEE Trans. Knowl. Data Eng., 23(9):1282– 1298, 2011.

[8]  Tom J. Ameloot, Frank Neven, and Jan Van den Bussche. Relational transducers for declarative networking. J. ACM, 60(2):15:1–15:38, 2013.

[9]  Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Sys- tems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 273–284, 2013.

[10]  Paul Beame, Paraschos Koutris, and Dan Suciu. Skew in parallel query processing. CoRR, abs/1401.1872, 2014.

[11]  Shumo Chu, Magdalena Balazinska, and Dan Suciu. From theory to practice: E cient join query evaluation in a parallel database system. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 63–78, 2015.

[12]  Hector Garcia-Molina, Je↵rey D. Ullman, and Jennifer Widom. Database systems - the complete book (international edition). Pearson Education, 2002.

[13]  Joseph M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1):5–19, 2010.

[14]  Bas Ketsman and Frank Neven. Optimal broadcasting strategies for conjunctive queries over distributed data. In 18th International Con- ference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, pages 291–307, 2015.

[15]  Bas Ketsman and Dan Suciu. A worst-case optimal multi-round al- gorithm for parallel computation of conjunctive queries. Accepted for publication at PODS, 2017.

[16]  Douglas Laney. The importance of ‘big data’: A defini-

tion. https://www.gartner.com/doc/2057415/importance-big-data- definition, 2012. Accessed: 2017-05-15.

[17]  Todd L. Veldhuizen. Leapfrog triejoin: a worst-case optimal join algo- rithm. CoRR, abs/1210.0481, 2012.

[18]  Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J. Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012, San Jose, CA, USA, April 25-27, 2012, pages 15–28, 2012. 

Universiteit of Hogeschool
Master Informatica
Publicatiejaar
2017
Promotor
Prof. dr. Frank Neven
Kernwoorden
BrentChesny