scalalang2

스팟 인스턴스를 활용한 클라우드 비용 절감 전략

AWS로부터 시작된 클라우드 컴퓨팅의 개념이 등장한 이후부터 기업은 꾸준히 리소스를 온-프레미스에서 클라우드로 마이그레이션 하고 있습니다. 이에 따라, 클라우드 비용 절감은 기업에서 중요하게 생각하는 토픽입니다. 이 비용에 가장 크게 기여하는 항목 중 하나는 컴퓨팅 리소스인데요. AWS, Azure, GCP 등 대부분의 클라우드 사업자들은 두 가지 인스턴스 타입을 제공합니다.

온-디맨드 인스턴스는 가용성이 높은 타입으로, 엔드-유저의 요청을 직접 서빙하는 서버에서 많이 이용합니다. 반면, 스팟 인스턴스는 데이터센터에서 놀고있는 컴퓨팅 자원을 임대해주는 개념으로 온-디맨드 서비스에 비해 3배에서 11배 저렴한 가격으로 이용할 수 있습니다.

다만, 비선점 자원이기 때문에 다른 곳에서 온-디맨드 서비스를 요구하면 내가 이용하던 스팟 인스턴스를 회수해갑니다. 즉, 가용성이 떨어지며 불확실성을 가지고 있습니다. 이런 특성으로 인해 AI 학습, 대용량 데이터 분석, CI/CD 분야에서 주로 스팟 인스턴스를 이용하며 AI 및 데이터 분석 프레임워크들은 주기적으로 중간 연산 결과를 체크포인트로 남겨서 스팟 인스턴스의 불확실성에 대응하고 있습니다.

대부분, 이 정도만 해도 충분하지만 실제 세상에서는 마감-기한(Deadline-sensitive)이 정해진 작업들이 있습니다. 예를 들어, 추천 서비스의 경우 광고를 등록하면 한시간 내에 바로 엔드-유저에게 노출되어야 한다는 정책이 있으면 단순 전략만으론 요구사항을 충족할 수 없습니다.

USENIX — NSDI ’24 — Can’t Be Late: Optimizing Spot Instance Savings under Deadlines

오늘은 NSDI’24 에서 best paper award를 받은 논문이자, Apache Spark의 개념을 세우는데 기여한 두 명의 교수님 Ion Stoica와 Scott Shenker이 교신저자로 참여한 논문인 Can’t Be Late: Optimizing Spot Instance Savings under Deadlines[1] 을 소개합니다.

이 논문은 마감-기한을 지켜야하는 애플리케이션이 스팟-인스턴스를 어떻게 레버리지 해야하는 지 정책을 세우는데 의의가 있습니다. 연구진들은 이미 여러 클라우드 서비스에 걸쳐서 스팟-인스턴스로 AI학습 비용을 낮추는 SkyPilot 프레임워크[2]를 한 차례 발표한 바 있으며 3개월 동안의 실제 실험을 통해 자신들의 전략이 비용을 절감하는데 효과적이라고 입증했습니다.

SkyPilot : Run AI on Any Infra — Unified, Faster, Cheaper

INDEX

스팟 인스턴스의 특징

스팟 인스턴스의 특징을 이해하는 데서 출발합니다. 스팟 인스턴스는 비선점 자원이기 때문에 현재 내가 이용중이었더라도 자원이 언제라도 회수될 수 있습니다. 그리고 스팟 인스턴스를 사용하고 싶다고 해서 언제나 이용할 수 있는 것도 아닙니다. 저자들은 최근 AI학습으로 많이 요구되고 있는 엔비디아 V100과 K80의 인스턴스의 가용성과 선점(Preemption)현상을 3개월 동안 관찰했습니다.

위 그림에서 왼쪽 그래프는 스팟 인스턴스의 가용성이 가용 영역(AZ)마다 다른 모습을 보여주며, 예측하기 어렵다는 것을 보여줍니다. 그래프에서 가로 실선은 스팟-인스턴스가 가용하다는 것을 나타내며 회색 선은 스팟-인스턴스를 임대 받을 수 없었다는 것을 보여줍니다. 인스턴스가 회수될 때 마다 세로선으로 표기했습니다. 오른쪽 그래프는 인스턴스가 얼마나 가용 가능한 상태였는지를 6 시간 윈도우로 나눈 비율을 보여줍니다.

어떤 AZ에서는 인스턴스의 가용성이 높았던 반면, 다른 AZ에서는 인스턴스를 거의 이용할 수 없는 상태였음을 알 수 있습니다. 이는 AZ 사이의 상관관계는 거의 없으며 논문의 목표에 부합하기 위해서는 불확실성에 견고한 정책을 세워야 함을 의미합니다.

스팟 인스턴스 가용성의 변동성이 매우 큰 반면에 가격 자체는 안정적인 편에 속합니다. 이는 AWS가 스팟-인스턴스의 가격 정책에서 경매 방식을 폐기한 것과 관련 있고, GCP는 30일 동안은 고정된 가격으로 판매하고 있기 때문에 스팟-인스턴스는 비교적 안정적인 가격으로 제공되고 있습니다.

문제 정의 / Deadline-sensitive Problem

지금까지 스팟 인스턴스 특성을 알아봤다면, 이제는 우리가 해를 구해야 하는 문제가 무엇인지 정의해야 합니다. 여기서는 Deadline-senitive한 Task를 안정적으로 운영하는 것을 목표로 하는데요. 그래서 세 가지 변수를 정의합니다.

여기선 C(0)와 R(0)는 처음 시작부터 알 수 있다고 가정합니다. R(0)를 안다는 건 당연하죠. 1시간 뒤에 추천 시스템에 의해 노출되어야 한다면 R(0) = 1시간 입니다.

그리고 세 가지 상태를 정의합니다. ‘Idle’은 작업이 실행되지 않는 상태, ‘VM’은 온-디맨드 인스턴스로 작업을 수행하는 상태, 그리고 ‘Spot’은 스팟 인스턴스로 작업을 실행하는 상태를 나타냅니다. ‘changeover delay(d)’는 상태 전환 시 발생하는 추가 비용을 의미하며, 이는 새 인스턴스 실행 시간, 애플리케이션 구동 시간, 마지막 체크포인트로부터의 복구 시간 등을 포함합니다.

Deadline-sensitive Problem의 목표는 $C(R(0)) \le 0$ 조건을 만족하면서 총 비용을 최소화하는 것입니다. 즉, 주어진 기한 내에 작업을 완료하면서 스팟 인스턴스와 온-디맨드 인스턴스를 최적으로 활용하여 비용 효율성을 극대화하는 것입니다.

Greedy Policy

Greedy 정책은 탐욕법을 적용한 가장 기본적이면서 간단한 정책입니다. 이 정책은 다음과 같은 간단한 규칙을 따릅니다:

  1. 스팟 인스턴스 우선 사용: 가능한 한 스팟 인스턴스를 최대한 활용합니다.
  2. Exploitation Rule: 스팟 인스턴스를 사용 중이면 계속 사용합니다.
  3. Safety Net Rule: 만약 R(t) < C(t) + 2d 조건이 충족되면, 온-디맨드 인스턴스로 전환하여 작업을 완료합니다. 이는 작업 완료를 보장하기 위한 안전장치 역할을 합니다. 만약, R(t) < C(t) + 2d 인데 스팟 인스턴스를 사용하다가 Preemption이 발생하면 마감기한을 지킬 수 없게 되겠죠
  4. Thrifty Rule : C(t) = 0 라면 Idle 상태가 되야 합니다.

여기서 Safety Net Rule, Thrifty Rule, Exploitation Rule 용어는 이 후 반복해서 등장하기에 머리속에 넣어두시면 가독성을 높일 수 있습니다. 그리고, 앞서서 우리는 스팟 인스턴스 가격이 비교적 안정적이라는 사실을 언급했는데요. 미래에 이 가격이 불안정해진다면 Greedy 정책은 동작하지 않겠죠.

Greedy 정책을 적용한 경우의 인스턴스 비용

위 그림은 Greedy 정책을 사용한 경우의 상태 전환 및 비용을 보여줍니다.

비용 분석

앞서 정의한 Deadline-sensitive Problem은 온라인 문제[3]로 해석할 수 있습니다. 온라인 문제 중에 대표 문제인 스키 대여 문제[4]를 다루고 다시 논문 이야기로 돌아오겠습니다.

① 스키 대여 문제

겨울에 스키장에 놀러갔다고 합시다. 스키를 타기 위해 우리에게는 두 가지 선택지가 있습니다.

  1. 스키 장비를 50만원을 주고 구입합니다.
  2. 5만원을 내고 장비를 대여합니다.

어떤 선택을 해야 경제적일까요? 현재로서는 답을 구할 수 없습니다. 그 답은 이번 겨울에 얼마나 자주 스키를 타러 갈 것인지, 스키장이 이번 겨울에는 언제까지 영업할 수 있을지에 따라 달려있죠.

미래의 모든 상황을 알고 있다면 이 결정은 굉장히 간단해집니다. 만약 스키장에 11번 넘게 갈 거라면 분명히 장비를 구입하는게 낫고, 9번 이하로 간다면 대여 하는게 좋습니다. 하지만 온라인 문제에서는 일단 미래의 일은 알 수 없다고 가정합니다.

우리가 일반적으로 다루는 알고리즘은 입력이 모두 주어집니다. 반면 이처럼 모든 입력이 한 번에 모두 주어지지 않고, 일부만 주어지는 문제를 온라인 문제(online problem)라고 하며, 새로운 입력이 주어지면 곧바로 결정을 내리는 알고리즘을 온라인 알고리즘 이라고 합니다.

② 경쟁비

경쟁비란 온라인 알고리즘 출력의 최악의 경우(worst-case) 발생하는 비용과 최적해(optimal solution) 비용의 비율로 온라인 알고리즘을 평가하는 척도입니다.

스키장에 방문한 회수를 t라고 한다면 t = 1 일 때 장비 구입의 경쟁비는 10 입니다. 왜냐면, 최악의 경우의 비용은 50만원으로 장비를 구입한 다음, 두 번 다시 스키장에 방문하지 않는 것이며 이 때의 최적해는 대여 비용인 5만원 이기 때문에 경쟁비는 10입니다.

만약 t = 2 일때의 경쟁비는 어떻게 될까요? t = 1 에서 대여를 한 번 했고, t = 2 에서 구입을 했으니 비용은 55만원입니다. 그리고 최적해는 두 번 모두 대여해서 10만원을 내고 두 번 다시 스키장에 가지 않는 것입니다. 재밌는 사실은 t = 1 일 때의 경쟁비는 10이었죠. t = 2 에서 장비를 구입하는 것의 경쟁비는 5.5로 대략 1.8배 줄어든 것을 알 수 있습니다.

이를 식으로 표현하면 t ≤ 10인 경우의 경쟁비는 (500 + 50(t-1))/50t 이고, t > 10 인 경우에는 처음부터 장비를 구입하는게 최적해가 되기 때문에 식은 (500+50(t-1))/500가 됩니다. 이 해석에 따르면 우리는 10번 스키장에 간 다음에 장비를 사는게 낫습니다.

경쟁비는 논문의 내용을 이해하는데에는 필요한 용어입니다만, 중요한 비중을 가진 단어는 아닙니다. 온라인 문제 자체를 깊이있게 공부하고 싶으신 분은 가젤님 블로그 글을 추천드립니다.

③ Greedy 정책의 worst case 비용 분석

Greedy 정책의 worst case 비용은 어떻게 될까요? 설정한 Greedy 정책에 정확히 반대 포지션을 가진 어떤 정책이 있다고 가정해봅시다. 이 정책은 적대적(Adversarial)이지도 않고 나의 결정을 미리 알 수 있는 오라클도 아니지만 우연히 내가 스팟-인스턴스를 필요로 하는 순간, R(t) ≥ C(t) + 2d, 에 모든 스팟인스턴스를 가져가고 있습니다. 그러면 이 경우의 worst case 비용은 모든 연산을 온-디맨드 인스턴스로 수행하는 경우이고 이 비용을 K라고 정의합니다.

스팟-인스턴스의 가용성이 충분하지 않은 상황에서 Greedy 정책을 사용하는 작업 여러 개를 동시에 돌린다고 가정해도 worst case 비용이 발생할 가능성이 크다고 직관적으로 이해할 수 있습니다.

이런 경우를 피하기 위해서 전체 시간을 사전에 정해진 파라미터 N으로 나눈 다음에 나누어진 구간 별로 Greedy 정책을 적용합니다. 물론 이 경우에도 최악의 비용이 K이기 때문에 n-sliced greedy와 shifted (n-1)-sliced greedy 정책을 시간 t에 대해서 균등한 확률로 선택해서 적용하는데요.

이를 randomizaed shifted greedy (RSF) 라고 부르고, 남은 시간 R(0)가 C(0)보다 2배 이상 크다면 경쟁비가 아래 수식을 따르게 됩니다.

수식에서 (1)은 온-디맨드 인스턴스 비용을 의미하고, (2)는 스팟 인스턴스 비용을 의미합니다. Safety Net Rule에 의해 마지막 1/n 은 어차피 온-디맨드 인스턴스를 돌려야 하고 남는 시간인 (1–1/n)에 대해서 온-디맨드 인스턴스와 스팟 인스턴스가 각각 절반씩 나눠 가집니다.

④ RSF 정책의 평균 비용 분석

위에서 RSF 정책의 경쟁비가 worst case보다 작음을 보여주었습니다. 이제는 평균 비용(Average case)을 알아봅시다. 먼저 용어부터 정의할 건데요. 우리는 스팟 인스턴스의 가용성 수준을 모르기 때문에 스팟 인스턴스를 사용할 수 있는 비율(r)이 일정하다고 가정합니다. 예를 들어보면 총 5시간 중에 4시간은 스팟 인스턴스를 사용할 수 있었고, 1시간은 대기해야만 했다면 r = 0.8 입니다.

그리고, 스팟 인스턴스의 비용은 1로 고정이구요. 온-디맨드 인스턴스의 가격 k는스팟 인스턴스 비용보다는 크기 때문에 k > 1 이라고 가정합니다. 단순 Greedy 전략은 R(t’) < C(t’) + O(d)이 참이라면 스팟-인스턴스를 사용하고 반대의 경우 온-디맨드 인스턴스로 전환하는 전략입니다. 시간 t’ 을 작업이 전환되기 까지의 시간으로 정의하면 평균 비용(p)은 아래 수식으로 정의할 수 있습니다.

r — k가 항상 음수이기 때문에 스팟 인스턴스 사용 시간(t’)이 길수록 비용이 줄어듭니다. 이 간단한 공식의 실효성을 보여주기 위해, 48시간 동안 실제 전략을 적용한 비용 변화를 그래프로 제시합니다.

논문에서 저자들이 주장하고 싶은 바는 RSF전략이 평균적으로 Greedy 보다 더 적은 비용을 사용한다는 것이었죠. RSF 전략은 스팟 인스턴스의 가용성 수준인 R이 평균 r과 분산 v를 가진 확률 변수를 가진다고 가정하고 수식을 전개합니다. (자세한 내용은 논문의 Appendix A.2.2 참고)

v_hat은 R(0)를 n등분한 구역별로 분산을 구한 값이고 v는 전체 R(0) 시간 스케일에 대한 분산 값을 의미합니다. 저자들은 항상 v_hat > v이 참이라고 예상하고 있어서 RSF와 greedy 전략의 비용 차이인 Δ값이 양수라고 예상하고 있습니다.

대충 설명하는 것처럼 느끼실 수 있는데요.
제가 제대로 이해하지 못해서 논문의 내용을 옮겨 왔습니다.

Uniform Progress Policy

이제 이 포스팅의 마지막 단원입니다. 위에서는 이론적인 배경을 먼저 보여주었다면 지금부터는 실제로 이용할 수 있는 정책에 대해 다룹니다. 먼저 RSF의 수정 버전인 Time Sliced 정책을 설명한 다음, 파라미터가 없이 동작하는 Uniform Progress 정책을 다룹니다.

① Time Sliced

Time Sliced는 n-sliced greedy policy를 수정한 버전으로 두 가지 개선점이 있습니다. (1) 스팟을 사용하고 있었다면 C_i(t) ≤ 0이 되어도 계속 이용합니다. (2) 구간 i가 더 많은 일을 한다면 그 진행도를 다음 구간 i+1가 이어 받아서 계산합니다. 그리고 클라우드는 비적대적(non-adversarial) 환경이기 때문에 RSF에서 랜덤하게 선택했던 것을 실제로는 적용하진 않습니다.

Time Sliced와 Greedy 정책의 차이를 보여준다.

저자들은 AWS에서 600개의 랜덤한 p3.2xlarge 인스턴스 타입에 대해 실험을 진행했습니다. Time Sliced 정책에서 파라미터 N을 잘 고르면 33% ~ 62% 까지 비용절감이 가능했다고 하는데요. 문제는 파라미터 N을 결정하는 번거로움에 있습니다. 그래서 여기서 한 단계 더 나아가 완전한 parameter-free 정책인 Uniform Progress를 개발합니다.

② Uniform Progress

Uniform Progress는 파라미터 N까지 제거된 정책입니다. 소위 말하는 딸깍만 하면 바로 적용되는 알고리즘입니다. 먼저 용어부터 알아보겠습니다. cp(t_i)는 시간 t_i에 대해 현재까지 진행된 작업 진척도 입니다.

그리고 ep(t_i)는 최소한 이 정도까지는 작업했어야 함을 의미하는 예상값인데요. R(0)와 C(0)의 비율을 시간만큼 곱한값입니다.

Uniform Progress는 총 4가지 규칙을 따릅니다.

  1. 현재 상태가 Idle 이며 cp(t) < ep(t) 라면 온-디맨드 인스턴스로 전환해서 예상치를 따라갑니다.
  2. Spot 인스턴스를 사용할 수 있으면 on-demand에서 spot으로 전환합니다. 이는 cp(t) < ep(t)여도 마찬가지구요. 한 번 스팟을 사용하면 선점 당할때까지 이용합니다.
  3. 최악의 경우에도 deadline을 지키기 위해서 Safety Net Rule이 최상위 정책으로 있습니다.
  4. Spot Instance가 빈번하게 떨어지는 경우에는 역효과가 있어서, 온-디맨드 상태일 때 cp(t) ≥ ep(t+2d)가 될 때 까지는 온-디맨드를 유지하는 정책을 추가해서 최종 Uniform Progress를 완성합니다.

다음은 Uniform Progress와 Time Sliced의 상태 전이 과정을 State Machine으로 표현한 그림입니다.

평가

논문에서 저자들은 Uniform Progress 정책을 실제로 AWS와 GCP에서 적용해본 결과를 공유했습니다. 스팟 인스턴스의 가용율은 70% ~ 90% 정도 되었다고 하구요. ML 학습과 데이터 분석을 수행한 결과를 보여줍니다.

위 표는 온-디맨드만 사용한 것 대비 얼마나 비용을 아낄 수 있었는지를 보여줍니다. 아래 표에서는 Greedy 정책과 비교하는데요. Greedy 정책에 비해 큰 폭으로 비용이 감소함을 알 수 있습니다.

마지막으로 마감 기한이 짧은 경우(Tight DDL)와 긴 경우 (Loose DDL)에도 유의미하게 작동하는지도 평가합니다. job fraction은 R(0)와 C(0)의 비율을 의미합니다. 이 값이 클 수록 컴퓨팅 파워를 더 타이트하게 운용해야 합니다.

평가표중에 표기된 Omniscient는 클라우드 사업자들이 Spot Availability에 대한 오라클(API)를 제공한다는 가정하에 동작하는 정책입니다. 논문은 꽤 많은 지면을 할애해서 이를 설명하는데요. 이 포스팅에서는 모든 내용을 생략했습니다.

마무리

개발을 잘하기 위해 가장 중요한 능력은 무엇일까요? 많은 중요한 요소들이 있을텐데 제가 가장 부러워 하는 건 문제를 인지하는 능력입니다. 모든 문제해결은 문제를 내가 문제라고 인식하고 있어야 가능합니다.

이 논문의 1저자인 Zhanghao Wu는 스팟인스턴스를 활용하는데 마감기한을 지키기 위해서는 온-디맨드 인스턴스의 사용비율이 높다는 문제를 인식했고 이를 해결하기 위한 사고과정을 거쳐 이 논문을 발표했으며, 이를 적용한 SkyPilot 프레임워크의 개발자이기도 합니다.

만약, 이 것을 문제라고 인식하지 않고 이정도 돈은 낼만 하다고 만족하고 있었다면 이 논문은 나오지 않았을 겁니다.

레퍼런스