Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sort Merge Buckets: Optimizing Repeated Skewed Joins in Dataflow
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2019. , p. 76
Series
TRITA-EECS-EX ; 2019:306
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-254663OAI: oai:DiVA.org:kth-254663DiVA, id: diva2:1334587
External cooperation
Spotify AB
Supervisors
Examiners
Available from: 2019-07-03 Created: 2019-07-03 Last updated: 2019-07-03Bibliographically approved

Open Access in DiVA

fulltext(1334 kB)23 downloads
File information
File name FULLTEXT01.pdfFile size 1334 kBChecksum SHA-512
4121ce9af293cf46963e326d20119fcfe705b7468865cf0b2bce66ef41374602b45a34fa0c2e1e17844ad35ca0075c9c8384857d0b0529d72b2061d2a63be34c
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 84 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf