[16 NSDI] Ernest: Efficient Performance Prediction for Large-Scale Advanced Analytics

0 Abstract

클라우드 컴퓨팅 인프라에서 머신러닝, 유전체학과 같은 과학 워크로드의 배포가 증가하는 추세이다. 이러한 워크로드를 수행하면서 성능과 비용을 크게 향상시키기 위해서는 적절한 하드웨어 구성을 선택하는 것이 중요하다. 위의 문제를 해결하기 위해서 최적의 구성을 자동으로 선택할 수 있도록 다양한 리소스들을 분석하여 애플리케이션의 성능을 예측하는 기능이 필요하다.
많은 워크로드들은 계산 및 통신 측면에서 예측 가능한 구조를 가지고 있다. 따라서 작은 데이터 샘플를 처리하는 워크로드의 동작을 기반으로 성능 모델을 구축한 다음 더 큰 데이터 세트 및 클러스터 크기에서 성능을 예측할 것이다. 모델을 구축하는 데 소요되는 시간과 리소스를 최소화하기 위해 최적의 실험 설계, 즉 필요한 만큼의 훈련 포인트를 수집할 수 있는 통계적 기법을 사용한다. 대규모 분석을 위한 성능 예측 프레임워크인 Ernest를 구축했으며 여러 워크로드를 사용하여 Amazon EC2를 평가한 결과 예측 오류가 낮은 것을 확인하였다. 또한 long-running job에 대한 training 오버헤드가 5% 미만인 것으로 나타났다.

1 Introduction

One approach to address this challenge is to predict the performance of a job based on monitoring the job’s previous runs [39, 44].

[39] A. D. Ferguson, P. Bodik, S. Kandula, E. Boutin, and R. Fonseca. Jockey: guaranteed job latency in data parallel clusters. In Eurosys 2012, pages 99– 112.

[44] B. He, M. Yang, Z. Guo, R. Chen, W. Lin, B. Su, H. Wang, and L. Zhou. Wave computing in the cloud. In HotOS, 2009.

문제점: 첫째, 작업이 주기적으로 실행되더라도 일반적으로 크기와 내용이 크게 다를 수 있는 데이터 세트에서 실행된다. 예를 들어, 예측 알고리즘은 다른 날짜 또는 시간 단위에 해당하는 데이터 세트에서 실행될 수 있다.

둘째, 대화형 기계 학습[9, 55] 및 매개변수 조정과 같은 워크로드는 관련 이력이 거의 또는 전혀 없는 고유한 작업을 생성한다.

Another approach to predict job performance is to build a detailed parametric model for the job. 

최근 MapReduce와 유사한 프레임워크의 맥락에서 여러 기술이 제안되었다[77, 52]. 이러한 기술은 2단계로 이루어진 MapReduce 모델의 고유한 단순성에 의해 제안되었다. 하지만 Dryad [51] and Spark[83]과 같은 최신 parallel computation engine들은 더 복잡하기 때문에 이것을 적용하기가 어렵다.

이 논문에서는 주어진 analytics workload의 성능을 정확하게 예측할 수 있는 새로운 접근 방식을 제안한다. 주요 아이디어는 입력 샘플에서 전체 워크로드를 실행하고 이 데이터를 training에 사용하여 성능 모델을 만드는 것이다. 일반적으로 전체 작업을 실행하는 것보다 training할 작업을 실행하는 시간과 리소스가 훨씬 적기 때문에 이 접근 방식은 오버헤드가 적다. 이것이 블랙박스 접근 방식이라는 사실에도 불구하고(즉, 워크로드 내부에 대한 지식이 필요하지 않음) 놀라울 정도로 잘 작동한다.
이 접근 방식이 잘 작동하는 이유는 많은 고급 analytics workload는 구조가 단순하며 실행시간과 데이터의 크기 또는 실행시간과 노드 수 간의 의존성은 상대적으로 적은 수의 smooth function이라는 일반적인 특성만 있기 때문이다. 이는 빅 데이터 연구자와 실무자가 입력 데이터의 크기 측면에서 선형 또는 준선형이고 노드 수에 따라 잘 확장되는 알고리즘을 개발해왔기 때문에 놀라운 일이 아니다. 간단한 예로서 선형 회귀에 사용되는 mini-batch gradient descent 알고리즘을 고려해보면 된다. Partition 당 m개의 데이터 포인트와 n개의 function이 있는 데이터 세트의 경우 각 작업에서 gradient를 계산하는 데 걸리는 시간은 균일하고(mn) 유사하게 모든 작업의 ​​출력 크기는 크기가 n인 벡터와 동일하다.

 

연구에서 내세우는 contributions:

• Unmodified job으로 동작하고 최적의 실험 설계를 사용하여 낮은 오버헤드를 달성하는 성능 예측 프레임워크인 Ernest를 제안한다. (job을 수정하지 않고 그대로 쓸 수 있음)
• Ernest가 모델이 적절하지 않은 경우를 감지하는 방법과 복잡한 워크로드를 모델링하는 데 소규모 확장을 사용하는 방법을 보여준다.
• EC2에 대한 실험을 사용하여 다양한 알고리즘, input size 및 클러스터 크기에 대해 Ernest가 정확함을 보여준다.

 

3 Modeling Advanced Analytics Jobs

3.1 Features for Prediction

End-to-end unmodified job modeling의 결과 중 하나는 성능 변화를 관찰하기 위해 변경할 수 있는 매개변수가 몇 개 밖에 없다는 것이다. Job, dataset, machine type이 고정되어 있다고 가정할 때 수정이 가능한 두 가지 주요 feature는 (a) the number of rows 또는 fraction of data used (scale) 그리고 (b) 실행헤 사용되는 the number of machines 이다. 모델링 프로세스에서 우리의 목표는 필요한 훈련 데이터의 양이 기능의 수에 따라 선형적으로 증가하는 데 필요한 최소한의 기능을 도출하는 것입니다.
모델을 구축하기 위해 §2.3에서 논의된 계산 및 통신 패턴과 관련된 용어를 추가합니다. 선형 모델에 추가한 항은 (a) 연속 계산에 소요된 시간을 나타내는 고정 비용 항 (b) 규모와 기계 수의 역수 간의 상호 작용; 이것은 계산이 데이터와 선형적으로 확장되는 알고리즘에 대한 병렬 계산 시간을 캡처하는 것입니다. 즉, 동일한 수의 기계로 데이터 크기를 두 배로 늘리면 계산 시간이 선형적으로 증가합니다. (c) log(machines) 항 집계 트리와 같은 모델 통신 패턴 (d) 일대일 통신 패턴을 캡처하는 선형 용어 O(머신) 및 작업 스케줄링/직렬화와 같은 고정 오버헤드(즉, 시스템에 더 많은 머신을 추가함에 따라 확장되는 오버헤드). 비선형 기능의 선형 조합을 사용하므로 비선형 동작도 모델링할 수 있습니다.