[14 ASPLOS] Quasar: Resource-efficient and QoS-Aware Cluster Management

0 Absctract

클라우드 컴퓨팅은 사용자에게는 유연성과 고성능을, 운영자에게는 높은 비용 효율성을 약속한다. 그럼에도 불구하고 대부분의 클라우드 시스템에서는 매우 낮은 utilization으로 동작하기 때문에 cost-efficiency와 scalability을 모두 저해하고 있다.

Resource utilization을 높여 지속적으로 높은 애플리케이션 성능을 제공할 수 있는 클러스터 관리 시스템인 Quasar를 소개한다. Quasar는 세 가지 기술을 사용한다. 첫째, 사용자에 의한 복잡한 코드를 통해 workload dynamics 및 물리적 리소스 요구 사항을 제시해야하는 resource reservation 방법에 의존하지 않는 대신 사용자로부터 각 워크로드에 대한 성능 제약만을 표기하도록 요구하여 Quasar가 언제든지 이러한 제약을 충족할 수 있는 적절한 양의 리소스를 결정할 수 있도록 한다. 둘째, Quasar는 classification 기술을 사용하여 각 워크로드의 성능에 대한 리소스 양(scale-out, scale-up), 리소스 종류 및 간섭의 영향을 빠르고 정확하게 결정한다. 셋째, classification 결과를 사용하여 리소스 allocation과 assignment를 수행하고 사용 가능한 리소스에 워크로드를 효율적으로 pack할 수 있도록 한다. Quasar는 워크로드의 성능을 모니터링하고 필요할 때 리소스 allocation 및 assignment를 조정한다. 로컬 클러스터와 전용 EC2 서버 클러스터 모두에서 distributed analytics framework와 low-latency 조합 그리고 stateful services 조합 등 여러 워크로드 시나리오에 대해 Quasar를 평가하였다. 안정적인 상태에서 Quasar는 200개 서버 EC2 클러스터에서 리소스 활용도를 47% 향상시키면서 모든 유형의 워크로드에 대한 성능 제약 조건을 충족할 수 있었다.

1 Introduction

둘째, Quasar는 워크로드 성능에 대한 다양한 리소스의 할당을 위해 fast classification 기술을 사용한다. 워크로드에 대한 소량의 프로파일링 정보와 이전에 예약된 워크로드의 대용량 데이터를 결합하여 Quasar는 애플리케이션과 사용되는 데이터에 대한 사전 분석 없이 효율적인 자원 할당에 필요한 정보를 빠르고 정확하게 생성한다. 특히 Quasar는 각 애플리케이션에 대해 4가지 병렬 분류를 수행하여 리소스 할당에 중요한 4가지 측면을 평가한다. scale-up의 영향 (각 서버에 필요한 리소스의 양), scale-out의 여향 (워크로드 당 필요한 서버의 수), server configuration의 영향, interference의 영향 (어떤 워크로드가 같은 서버에 배치될 수 있는지).

2 Motivation

2.1 Cluster Management Overview

A cluster management framework provides various services including security, fault tolerance, and monitoring.

This paper focuses on the two tasks most relevant to resource efficiency: resource allocation and resource assignment of incoming workloads.

Resource allocation: Allocation refers to determining the amount of resources used by a workload (number of servers, number of cores and amount of memory and bandwidth resources per server)

Managers like Mesos [32], Torque [58], and Omega [54] expect workloads to make resource reservations.

Resource assignment: Assignment refers to selecting the specific resource that satisfy an allocation.

The two challenges of assignments are server heterogeneity and interference between colocated workloads.

The most closely related work to this paper is Paragon. Paragon uses classification techniques to quickly estimate the impact of heterogeneity and interference on performance.

3. Quasar

3.2 Fast and Accurate Classification

Collaborative filitering 기술은 extremely sparse input과 함께 추천 시스템에서 자주 사용된다[50]. 가장 널리 알려진 용도 중 하나는 Netflix Challenge[11]로, SVD(Singular Value Decomposition)와 PQ-reconstruction[13, 35, 50, 66]과 같은 기술을 사용하여 소수의 영화에 평점을 남긴 사용자에게 다른 사용자의 많은 평가를 이용하여 영화 추천을 제공한 경우가 있다. 이 경우 SVD에 대한 입력은 사용자를 행으로, 영화를 열로 두고 평점을 값으로 사용한 sparse 행렬 $A$이다. SVD는 $A$의 유사성 개념을 나타내는 singular value $\Sigma$를 가지는 행렬을 만들기 위해 $A$를 $U$와 $V$라는 두 종류의 백터로 분해한다. $U$는 $A$의 row와의 유사성 개념 간의 correlation을 나타내는 left singular vector이고 $V$는 $A$의 column과의 correlation을 나타내는 right singlar vector 이다. 분해된 A는 $A = U \cdot \Sigma \cdot V^T$로 표현된다. 유사성 개념의 예시로 "반지의 제왕 1"을 좋아한 사용자가 "반지의 제왕 2"를 좋아했다는 것을 알 수 있다.  Simple latent-factor model[13, 66]인 SGD(Stochastic Gradient Descent)를 활용한 PQ-reconstruction은 $\Sigma$, $U$ 그리고 $V$를 사용하여 $A$의 누락된 항목을 재구성한다. SVD 출력으로 시작하여 $P^T$는 $\Sigma V^T$ 그리고 $Q$, $A$의 초기 재구성을 제공하는 $U$로 초기화된다. 그 후, 재구성된 행렬 $R = Q \cdot P^T$의 모든 값에서 SGD가 수렴될 때까지 동작을 반복한다. ($R$의 element인 각 $r_{ui}$에 대해서 $|\epsilon|_{L_{2}}$가 marginal이 될 때까지 반복함) $\eta$는 learning rate이고 $\lambda$는 SGD의 regularization factor이고 그 값들은 empirical하게 결정된다. 위의 모델에서 average rating $mu$와 user bias인 $b_u$ 또한 포함시켰다. 행렬이 한번 재구성되면, SVD는 영화 추천을 생성하기 위해 기존 user와 새로운 user의 correlation을 계산하여 한번 더 적용된다. SVD의 complexity는 $O(min(N^2M,M^2N))$이며 이때 $M, N$은 $A$의 dimension이고 PQ-reconstruction의 complexity는 $O(N \cdot M)$이다.

Paragon [20]에서는 interference와 heterogeneity와 관련하여 워크로드를 빠르게 분류하기 위해 collaborative filtering이 사용되었다. 일부 어플리케이션은 다양한 서버와 다양한 amounts of interference에서 성능을 계산하기 위해 완전히 오프라인으로 프로파일링된다. 어플리케이션은 공유 리소스에 대한 간섭이 있는 서버와 없는 서버에서 1분 동안 프로파일링된다. SVD와 PQ-reconstruction은 나머지 서버 구성에서 나머지 유형의 리소스에 대한 interference로 워크로드의 성능을 정확하게 추정하는데 사용된다. Paragon은 collaborative filitering이 수십 개의 서버 구성과 수십 개의 interference source와 관련하여 알려지지 않은 어플리케이션을 빠르고 정확하게 분류할 수 있음을 보여주었다.
Quasar의 분류 엔진은 두 가지 방식으로 Paragon의 분류 엔진을 확장하였다. 첫째, collaborative filtering을 사용하여 리소스 scale-out(더 많은 서버) 및 scale-up(서버당 더 많은 리소스)이 애플리케이션 성능에 미치는 영향을 추정한다. 이러한 추가적인 classification은 리소스 allocation에 필수적이다. 둘째, 다양한 워크로드 유형에 맞게 classification를 조정한다. 이는 워크로드 유형마다 contraints과 allocation knobs가 다르기 때문에 추가가 필요하였다. 예를 들면 웹 서버에서 scale-out과 scale-up을 모두 적용할 수 있으며 QPS(queries per second)와 latency를 모니터링해야 한다. Hadoop의 경우 노드당 mapper의 수, 힙 크기 및 압축과 같은 워크로드 매개변수도 구성할 수 있다. 단일 노드 워크로드의 경우 scale-up이 유일한 옵션일 수 있지만 주요 메트릭은 instructions per second가 될 수 있다. Quasar의 performance constraints 인터페이스는 사용자가 어플리케이션 유형에 대해 이러한 사항을 지정할 수 있도록 한다.

전체적으로 Quasar는 scale-up, scale-out, heterogeneity, and interference 에 대해서 classification을 진행한다.

Scale-up classification: 이 분류는 한개의 서버 내에서 사용되는 리소스의 양에 따라 성능이 어떻게 달라지는지 살펴본다. Quasar는 현재 core, memory와 storage capacity에 중점을 두고 있지만 향후 작업에서 네트워크 대역폭을 추가할 예정이다. 가장 많은 scale-up 옵션을 제공하는 최고급 플랫폼에서 scale-up 분류를 수행하였다. 워크로드가 실행되면 먼저 무작위로 선택된 두 개의 scale-up allocation으로 간략하게 프로파일링을 수행한다. 프로파일링의 매개변수와 기간(duration)은 워크로드 유형에 따라 다르다. memcached와 같은 latency-critical service는 두 가지 다른 core/thread 수와 메모리 allocation을 사용하여 라이브 트래픽에서 5-10초 동안 프로파일링됩니다 (프로파일링 실행 수에 대한 sensitivity 분석은 validation section 참조). Hadoop과 같은 워크로드의 경우에는 여러 map task의 작은 subset (2-6)을 두 종류의 allocation과 중요 프레임워크 매개변수 configuration(예: mappers per node, JVM heapsize, block size, memory per task, replication factor, compression)에서 프로파일링을 수행한다. 프로파일링은 map task가 최소 20% 완료될 때까지 지속되며, 이는 일반적으로 progress rate[70]과 unifrom task duction[32]을 사용하여 작업 완료 시간을 추정하기에 충분하다. Section 4.3에서는 non-uniform task duration distribution과 straggler(낙오자) 문제를 다룬다. 마지막으로 Cassandra[14]와 같은 상태 저장 서비스의 경우 Quasar는 서로 다른 allocation으로 input load를 프로파일링하기 전에 서비스 setup이 완료될 때까지 기다린다. 이 작업은 길어야 3-5분이 소요되며 long-running 서비스에 대해서는 이 정도의 대기 시간은 허용될 정도이다. Section 4.2는 Quasar가 프로파일링 실행을 위해 side-effect가 없는 어플리케이션 사본을 보장하는 방법을 설명한다.
프로파일링은 결과는 각 어플리케이션의 성능 목표(e.g., expected completion time이나 QPS) 형식으로 performance measurement를 수집하고 워크로드를 row, scale-up configuration을 column으로 사용하는 행렬 $A$에 삽입된다. Scale-up configuratino에는 compute (core), memory, storage allocation과 같은 서버 정보 또는 Hadoop과 같은 워크로드에 대한 프레임워크 매개변수 값이 포함되어있다. column의 개수를 제한하기 위해 벡터를 memory, storage의 block과 core를 정수로 양자화한다. 이는 다소 suboptimal(차선)의 결정을 초래할 수 있지만 실제로는 편차가 작은 것을 확인하였다. 이후 SVD와 PQ-reconstruction을 사용한 classificatio을 통해 모든 scale-up allocation에서 워크로드의 성능을 계산한다.
Scale-out classfication: 이 유형의 classification은 distributed frameworks(예: Hadoop 또는 Spark), stateless(예: webserving) 또는 stateful (예: memcached 또는 Cassandra) distributed services와 distributed computation (예: MPI Jobs)와 같이 여러 서버를 사용할 수 있는 워크로드에만 적용 가능하다. Scale-out classification은 scale-up classification을 위해 수행되는 단일 노드 실행 외에 추가적인 실행이 필요하다. 일관된 결과를 얻기 위해 프로파일링은 scale-up 실행중 동일한 워크로드와 같은 파라미터로 (예: JVM heapsize) 수행된다. 마찬가지로 row는 워크로드이고 column은 scale-out allocation(서버의 수)인 행렬 $A$에 두 개의 값을 생성한다. 그런 다음 collaborative filtering은 모든 노드 개수에 대한 누락된 entries를 계산한다. Scale-out classification에는 프로파일링을 위한 추가 서버가 필요하다. 시스템이 온라인 상태일 때 classification overhead가 증가하는 것을 방지하기 위해 1~4개의 노드에서만 어플리케이션을 프로파일링한다. 더 많은 노드 수에 대해 들어오는 워크로드의 성능을 정확하게 추정하기 위해 오프라인 모드에서 노드 수 1~100에 대해 소수의 서로 다른 워크로드 유형(20-30)을 철저하게 프로파일링했습니다. 이러한 실행은 분류 엔진에 밀도 정보를 제공합니다. 더 많은 노드 수에 대한 워크로드 동작. 클러스터의 하드웨어 또는 응용 프로그램 구조에 큰 변경 사항이 없는 한 이 단계를 반복할 필요가 없습니다.