Browse

Dynamic Optimization of Large-Scale Data Shuffling in a Data Processing System
데이터 처리 시스템에서의 대규모 데이터 셔플에 대한 동적 최적화

DC Field Value Language
dc.contributor.advisor전병곤-
dc.contributor.author이산하-
dc.date.accessioned2019-05-07T03:18:27Z-
dc.date.available2019-05-07T03:18:27Z-
dc.date.issued2019-02-
dc.identifier.other000000154460-
dc.identifier.urihttps://hdl.handle.net/10371/150791-
dc.description학위논문 (석사)-- 서울대학교 대학원 : 공과대학 컴퓨터공학부, 2019. 2. 전병곤.-
dc.description.abstractThe scale of data used for data analytics is growing rapidly and the ability to process large volumes of data is critical to data processing systems. A scaling bottleneck for processing large amounts of data in the data processing systems is the random disk read overhead that occurs while shuffling data communications between tasks. To reduce this overhead, an external shuffle process can batch the disk read by aggregating the intermediate data through an additional computation. However, the additional computation cannot take advantage of distributed execution capabilities provided by data processing systems such as scheduling, parallelization, or fault recovery. In addition, the systems cannot dynamically optimize the external shuffle process in the same way that they optimize plain jobs without an external process. Instead of launching the external shuffle process, we propose to insert the disk read batching into a job. By doing so, the tasks can fully exploit the features, including the dynamic optimization provided by data processing systems, because the computation for intermediate data aggregation is fully revealed to the systems. Moreover, we suggest a dynamic data skew handling mechanism that can be applied with the disk read batching optimization at the same time. Evaluations show that our implemented technique can mitigate random disk read overhead and data skewness and can reduce the job completion time by up to 54%.-
dc.description.abstract오늘날 데이터 분석 작업에서 사용하는 데이터의 크기가 빠르게 커지고 있으며, 이 때문에 데이터 처리 시스템은 대용량의 데이터를 효율적으로 처리할 수 있어야 한다. 분산 데이터 처리 시스템에서 큰 데이터를 처리할 때의 병목은 태스크 간 데이터 셔플시 발생하는 랜덤 디스크 읽기 비용이다. 이 비용을 줄이기 위하여, 외부 셔플 프로세스가 데이터 처리 시스템 바깥에서 추가적인 계산을 통해 중간 데이터를 병합하여 디스크 읽기를 일괄 처리하도록 할 수 있다. 그러나, 이 경우 추가된 계산은 기존에 데이터 처리 시스템이 제공하는 계산 스케쥴링, 병렬화, 실패 복구 등의 기능을 이용할 수 없다. 또한, 데이터 처리 시스템이 다른 일반적인 작업을 최적화하는 것처럼 이 외부 셔플 프로세스의 동작을 최적화할 수 없다. 이 문제를 해결하기 위하여, 본 논문에서는 디스크 읽기를 일괄 처리하도록 만드는 계산을 작업 수행 내부에 끼워넣는 방식을 고안하였다. 중간 데이터 병합을 위한 계산을 태스크로서 작업에 끼워넣어 데이터 처리 시스템이 이 태스크를 수행하도록 하면 이 태스크들은 동적 최적화를 포함하여 데이터 처리 시스템이 제공하는 모든 기능들을 사용할 수 있다. 또한, 본 논문에서는 이러한 중간 데이터 병합과 호환되는 데이터 치우침 처리 방식을 제안한다. 수행된 실험의 결과를 통해 구현된 최적화가 랜덤 디스크 읽기 비용을 줄이고 데이터 치우침을 완화하여 최대 54%의 성능 향상을 보임을 확인할 수 있다.-
dc.description.tableofcontentsChapter 1 Introduction 2
Chapter 2 Background 4
2.1 Distributed Data Processing Concepts . . . . . . . . . . . . . . . . . . 4
2.2 Random Disk Read Overhead in the Data Shuffle . . . . . . . . . . . . 5
2.3 Existing Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Skew Handling with Disk Read Batching . . . . . . . . . . . . . . . . 8
Chapter 3 Disk Read Batching as a Task 10
3.1 Intermediate Data Aggregation Stage . . . . . . . . . . . . . . . . . . . 10
3.2 Composing with Skew Handling Optimization . . . . . . . . . . . . . . 12
Chapter 4 Implementation 15
4.1 Optimization Pass for Disk Read Batching . . . . . . . . . . . . . . . . 15
4.2 Optimization Pass for Skew Handling . . . . . . . . . . . . . . . . . . 17
Chapter 5 Evaluation 21
5.1 Cluster Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Disk Read Batching Optimization . . . . . . . . . . . . . . . . . . . . 22
5.3 Skew Handling Optimization with Disk Batching . . . . . . . . . . . . 24
Chapter 6 Conclusion 28
Bibliography 29
국문초록 31
-
dc.language.isoeng-
dc.publisher서울대학교 대학원-
dc.subject.ddc621.39-
dc.titleDynamic Optimization of Large-Scale Data Shuffling in a Data Processing System-
dc.title.alternative데이터 처리 시스템에서의 대규모 데이터 셔플에 대한 동적 최적화-
dc.typeThesis-
dc.typeDissertation-
dc.contributor.AlternativeAuthorLee, San Ha-
dc.description.degreeMaster-
dc.contributor.affiliation공과대학 컴퓨터공학부-
dc.date.awarded2019-02-
dc.identifier.uciI804:11032-000000154460-
dc.identifier.holdings000000000026▲000000000039▲000000154460▲-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Computer Science and Engineering (컴퓨터공학부)Theses (Master's Degree_컴퓨터공학부)
Files in This Item:
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse