The amount of data being generated and consumed by today’s systems and applications is staggering and increasing at a vertiginous rate. Many businesses and entities rely on the analysis and the insights gained from this data to deliver their service. Due to the massive scale of this data, it is not possible to process it on a single machine, requiring instead parallel processing on multiple workers through horizontal scaling. However, even simple operations become complicated in a parallel environment. One such operation are joins, used widely in order to connect data by matching on the value of a shared key. Data-intensive platforms are used in order to make it easier to perform this and other operations at scale. In 2004, MapReduce was presented, revolutionizing the field by introducing a simpler programming model and a fault-tolerant and scalable execution framework. MapReduce’s legacy went on to inspire many processing frameworks, including contemporary ones such as Dataflow, used in this work. The Dataflow programming model (2015) is a unified programming model for parallel processing of data-at-rest and data-in-motion. Despite much work going into optimizing joins in parallel processing, few tackle the problem from a data perspective rather than an engine perspective, tying solutions to the execution engine. The reference implementation of Dataflow, Apache Beam, abstracts the execution engine away, requiring solutions that are platformindependent. This work addresses the optimization of repeated joins, in which the same operation is repeated multiple times by different consumers, e.g., user-specific decryption. These joins might also be skewed, creating uneven work distribution among the workers with a negative impact on performance. The solution introduced, sort merge buckets, is tested on Cloud Dataflow, the platform that implements the eponymous model, achieving promising results compared to the baseline both in terms of compute resources and network traffic. Sort merge buckets uses fewer CPU resources after two join operations and shuffles fewer data after four, for non-skewed inputs. Skew-adjusted sort merge buckets is robust to all types and degrees of skewness tested, and is better than a single join operation in cases of extreme skew. / Mängden data som genereras av applikationer och system ökar med en acceleration som inte tidigare skådats. Trots mängden data måste företag och organisationer kunna dra rätt slutsater av sin data, även om mängden är så stor att det går att behandla på en dator. Istället behövs parallella system för att bearbeta data, men de enklaste operationerna blir lätt komplicerade i ett parallellt system. En sådan enkel operation är join, som grupperar matchande par av datarader för en gemensam nyckel. Processningsramverk har implementerat join och andra operationer för att underlätta utveckling av storskaliga parallella system. MapReduce, som är ett sådant ramverk, presenterades 2004 och var banbrytande genom att tillhandahålla en enkel modell för programmering och en robust och skalbar exekveringsmiljö. MapReduce lade grunden för fler ramverk, till exempel Dataflow som används i denna uppsats. Dataflow (2015) är en programmeringsmodell för att parallellt behandla lagrad data på hårddisk och strömmande data. Join är en kostsam operation och trots att mycket arbete läggs på att optimera join i parallell databehandling, angriper få problemet från ett dataperspektiv istället för att optimera exekveringskod. Apache Beam, referensimplementationen av Dataflow, abstraherar bort exekveringsmiljön och ger utvecklare möjligheten att skriva databehandlingskod som är oberoende av platformen där den exekveras. Denna uppsats utforskar metoder för att optimera joins som utförs på ett repeterande sätt, där operationen utförs på en datamängd, men flera gånger av olika data-pipelines. Ett exempel på en sådan operation är kryptering av användarspecifik data. Join utförs ibland på data som är skev, det vill säga där vissa join-nycklar förekommer oftare än andra, vilket ofta leder till en negativ effekt på prestanda. Sort Merge Bucket Join, en optimering av join operationen och en lösning för skeva datamängder, introduceras i denna uppsats med tillhörande implementation för Cloud Dataflow. Resultaten av denna optimering är lovande med anseende till minskad användning av resurser för processning och nätverkstrafik.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-254663 |
| Date | January 2019 |
| Creators | Nardelli, Andrea |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2019:306 |
Page generated in 0.0027 seconds