공부 기록

💡 요약
- abstract: 컨테이너화된 환경을 위해 설계된 IO 제어 솔루션에 관한 연구
- introduction: 블록 스토리지를 위한 기존의 IO 제어 메커니즘은 스토리지 디바이스의 하드웨어 이질성과 데이터센터에 배포된 워크로드의 특수성을 고려하면서 최신 SSD에 알맞게 낮은 오버헤드로 실행되지 못한다는 문제가 있다.
- related works:
  - IO 제어 및 공정성 분야의 다양한 관련 연구
  - 프로덕션 스토리지 디바이스 전반의 성능 변동성, SSD 성능 예측을 위한 모델링 접근법, 가상 머신 모니터를 위한 IO 솔루션에 대한 연구
  - IO 스택의 여러 계층에 걸친 정보를 고려해야 할 필요성
  - 컨테이너를 위한 리소스 관리 솔루션과 아키텍처 확장
- method: 디바이스별 모델을 사용하여 각 IO 요청의 디바이스 점유율을 추정하는 방식으로 작동한다. => 오프라인 프로파일링, 디바이스 모델링, 새로운 작업 절약형 예산 기부 알고리즘을 활용하여 데이터센터의 다양한 워크로드와 이기종 스토리지 디바이스에 대해 확장 가능하고 작업을 절약하며 오버헤드가 낮은 IO 제어 기능을 제공함
- experiment: Meta의 모든 컨테이너에 IOCost를 배포하여 평가한 결과, IOCost는 최소한의 오버헤드로 비례적이고 작업을 절약하며 메모리 관리를 인식하는 IO 제어 성능이 뛰어났다.
- conclusion & discussion: IOCost는 ZooKeeper 배포, AWS Elastic Block Store/Google Cloud Persistent Disk 등의 원격 스토리지에서도 사용 가능하다.

Introduction

최근 주요 클라우드 업체들에서 컨테이너 기반 솔루션을 제공하고 있으며,

• https://aws.amazon.com/ko/containers/
• https://cloud.google.com/containers?hl=ko
• https://azure.microsoft.com/en-us/products/container-instances/

프라이빗 데이터센터에서도 컨테이너로 운영되는 추세이다. (Facebook도 전체 데이터센터가 컨테이너로만 운영되고 있다고 함)

기존에는 컴퓨팅, 메모리, 네트워크에 대한 리소스 격리에 대해 많은 연구가 이루어져왔는데, 블록 스토리지에 대한 기존 IO 제어 메커니즘도 개선이 필요하다.

• IO 제어는 데이터센터의 하드웨어 이질성을 고려해야 한다. 디바이스 종류 뿐만 아니라 한 유형 내에서도 지연 시간 및 처리량 측면에서 크게 다른 성능 특성을 가지기도 함.
  • 특히 짧은 순간에 성능을 과도하게 발휘한 후 급격히 느려져 스택 환경에 악영향을 미칠 수 있는 SSD 특성을 고려해야
• IO 제어는 다양한 애플리케이션의 이질성을 고려해야 한다.
  • 지연 시간에 민감 vs 처리량 vs 순차적 또는 무작위 액세스를 버스트 또는 연속적으로 수행

=> 하드웨어 + 애플리케이션 이질성으로 인해 지연 시간과 처리량 간의 균형점을 파악하는 것이 어렵다

• IO 격리는 페이지 회수 및 스왑과 같은 메모리 관리 작업과 잘 상호 작용 할 수 있도록 고려되어야 한다.

Background

1) cgroup: 컨테이너별 리소스 할당을 구성하기 위한 기술

컨테이너 런타임은 리소스 제어 및 격리를 위해 cgroup을 사용한다.

• cgroup: 컨테이너가 프로세스를 계층적으로 구성하고 계층을 따라 시스템 리소스를 제어 및 구성 가능한 방식으로 배포하기 위한 기본 메커니즘
  • 개별 cgroup이 계층 구조를 형성하고, 프로세스는 하나의 cgroup에 속한다.
  • cgroup 컨트롤러는 주로 가중치를 활용하여 CPU, 메모리 및 IO와 같은 특정 시스템 리소스를 트리를 따라 배포한다.
    • 모든 형제 cgroup의 가중치를 합산하고 각각에 합계에 대한 가중치의 비율을 부여하여 리소스를 배포

2) Linux 블록 레이어와 기존 IO 제어 솔루션

애플리케이션과 파일시스템은 블록 계층을 사용하여 블록 디바이스에 접근한다.

그림과 같이 userspace에서 시스템 호출을 통해 커널과 상호 작용하며, 파일시스템에 대한 읽기 및 쓰기 작업은 파일시스템 IO(FS IO)로 블록 레이어로 전달된다.

블록 레이어는 bio 데이터 구조를 사용하여 아래와 같은 다양한 정보를 전달한다.

• 요청 유형: read/write
• 크기
• 대상 장치
• 장치의 섹터 오프셋
• 요청한 cgroup
• 데이터를 복사하거나 복사할 메모리 등의 정보

Linux 커널에는 활성화할 수 있는 여러 가지 IO 스케줄러가 있다.

• cgroup 제어가 없는 IO 스케줄링: 컨테이너에 특정 IO 리소스를 보장하기보다는 일반적인 성능 속성을 유지하는 데 우선순위를 둔다. 전체 시스템 성능을 유지하기 위해 일반적으로 느린 비동기 read가 일반적으로 빠르고 즉각적인 응답이 필요한 동기 read보다 우선권을 갖지 못하도록 한다.
  • 스케줄러 없는 경우
  • mq-deadline
  • kyber 
• blk-throttle: read/write IOPS 또는 초당 바이트의 형태로 IO 제한을 설정할 수 있으나, 유휴 상태이거나 사용하지 않는 리소스를 필요로 하는 컨테이너 또는 워크로드에 할당할 수 없다는 단점이 있다.
• BFQ: IO 리소스를 비례적으로 제어할 수 있으나, 메모리 관리와의 상호 작용을 간과하여 잠재적으로 격리 문제를 일으킬 수 있다. 요청당 오버헤드가 높고 지연 시간 편차가 크며, 컨테이너당 read/write 섹터를 기반으로 하는 라운드 로빈 스케줄링은 내부 작업이 복잡한 최신 디바이스에는 효과적이지 않다는 단점이 있다.
• IOLatency: 개별 cgroup에 대한 IO 레이턴시 목표를 설정할 수 있으며, 다른 cgroup의 IO가 레이턴시 목표를 초과하면 이전 cgroup이 호출된다. IOLatency는 주로 엄격한 우선순위를 가진 컨테이너 간에 스케줄링은 적합하지만, 동일한 우선순위를 가진 컨테이너에 대해 비례 제어가 부족하여 워크로드 간의 공평성을 보장하기 어렵다는 한계가 있다.

3) 이기종 블록 장치와 워크로드가 있는 최신 데이터센터의 컨텍스트

Meta의 데이터센터에는 다양한 SSD가 있고, SSD간에 하드웨어 디바이스적 성능 특성이 매우 이질적이다.

• H: 낮은 레이턴시에서 높은 IOPS를 달성
• G: 낮은 IOPS와 상대적으로 낮은 레이턴시를 제공
• A: 높은 레이턴시와 함께 중간 정도의 IOPS를 제공

Meta의 애플리케이션을 분석해보면 IO 워크로드가 매우 다양함을 알 수 있다.

• Web A /B: 가장 일반적인 Meta 워크로드로, 읽기 및 쓰기가 무작위 및 순차 작업 측면에서 거의 동일하게 혼합되어 있다.
• serverless: 할당용량을 초과하는 경우가 많으며, 읽기 및 쓰기 양이 거의 동일하게 혼합되어 있다.
• Cache A/B: 인메모리 캐시를 위한 백업 저장소로 고속 블록 장치를 사용하는 인메모리 캐싱 서비스로, 두 캐시 모두 많은 양의 순차적 IO로 이루어져있다. (주로 스토리지 관련 작업을 수행)

Related Work

• 기존 연구는 대부분 하이퍼바이저를 개선하기 위함 + VM 기반 가상화 환경에 중점
  • 단일 공유 운영 체제, 메모리 하위 시스템과 IO의 상호 작용, 고도로 스택된 배포와 같은 컨테이너의 복잡성을 고려하지 않는다는 한계점이 존재한다.
• Linux 커널의 IO 제어는 BFQ 또는 최대 대역폭 사용량(IOPS 또는 바이트) 기반의 제한에 의존
  • BFQ: 우선순위와 요청량에 따라 각 프로세스에 디스크 시간 예산을 할당하여 여러 프로세스 또는 애플리케이션 간에 디스크 대역폭을 공정하게 할당하는 것을 목표로 하는 알고리즘 => 특정 프로세스가 디스크 독점 방지/모든 프로세스가 공평하게 IO 리소스를 할당받을 수 있도록 함
  • 디바이스의 유휴 자원을 모두 활용하지 못하거나, 빠른 저장장치에 과도한 성능 오버헤드를 추가하는 한계점
• 기존의 CPU 스케줄링은 가중 공정 큐잉과 같은 기술을 사용하여 CPU 사용 시간을 측정하여 CPU 점유율을 비례적으로 배분했는데, I/O 제어에 사용되는 IOPS나 바이트와 같은 지표는 특히 블록 디바이스의 다양성을 고려할 때 점유율을 측정하기 좋지 않다.
  • 최신 블록 디바이스는 내부 버퍼링과 가비지 컬렉션과 같은 복잡한 지연 작업에 크게 의존하므로, 디바이스 시간 공유에 의존하거나 주로 IOPS 또는 바이트를 기반의 공정성 보장 기술에 문제가 있다.

Method

IOCost는 디바이스의 복잡성과 무관하게 워크로드를 구성하기 위해 디바이스와 워크로드 구성을 분리한다.

• 각 디바이스에 대해 IOCost는 비용 모델과 디바이스 동작을 정의하고 규제하는 일련의 서비스 품질(QoS) 파라미터를 설정
• 각 워크로드에 대해 IOCost는 비례 구성을 위해 cgroup 가중치(hweight = 해당 cgroup이 받을 수 있는 IO 디바이스의 최종적인 비중)를 활용
• 지연 시간이 짧은 issue path 와 주기적으로 동작하는 planning path 를 분리

1) IO 디바이스 점유율을 추정하는 모델링: 개별 bio 작업의 점유를 추정 => 이 점유 추정치를 사용하여 각 cgroup에 할당된 가중치에 따라 스케줄링 결정을 내린다.

• 선형 모델을 사용하여 읽기/쓰기 초당 바이트 수, 초당 4kB 순차 및 랜덤 IO(IOPS) 등의 매개변수를 기반으로 IO 작업 비용을 계산한다.
  • fio 오픈소스 도구를 이용하여 다양한 블록 크기 및 액세스 패턴(순차 또는 임의), 읽기/쓰기과 같은 다양한 유형의 I/O 워크로드를 시뮬레이션하여 평가함
• 단순한 선형 모델링만으로는 복잡한 캐싱 메커니즘, 요청 재정렬, 가비지 컬렉션이 있는 최신 SSD의 복잡성을 포착하기에 충분하지 않으므로, 모델의 부정확성을 보완하기 위해 IOCost는 cgroup 사용량과 IO 완료 대기 시간에 대한 실시간 통계를 기반으로 IO 제어를 런타임에 조정한다.
  • 요청 시 자원부족 및 지연 시간 목표 위반을 추적하여(디바이스 포화 상태를 파악) 디바이스로 전송되는 총 IO를 제한하고 QoS 매개변수를 사용하여 디바이스 동작을 규제함 => 일관된 지연 시간 제어
  • QoS 매개변수: 가상 워크로드(ResourceControlBench)를 사용하여 지연에 민감한 서비스의 동작을 관찰하고 그에 따라 QoS 매개변수를 조정하는 체계적인 접근 방식을 개발했다. 다양한 전송률 범위에서 성능을 분석하여 IO 제어를 위한 최적의 지점을 파악 => 일관된 지연 시간을 달성하기 위해 디바이스를 스로틀링하는 방법을 결정

2) 디바이스의 유휴자원을 모두 활용할 수 있는 작업 보존 알고리즘 => 컨테이너가 과도한 메모리를 사용할 때 다른 컨테이너가 불이익을 받는 리소스 격리 문제 해결 = 컨테이너에 대한 블록 IO 제어

• 개별 cgroup에 할당된 IO 용량을 완전히 활용하지 못하는 경우에는 해당 cgroup의 가중치를 동적으로 낮춤으로써 다른 cgroup이 장치를 활용하고 사용하지 않은 리소스를을 공유할 수 있도록 하여 효율적인 리소스 활용을 보장한다.

3) 런타임 오버헤드를 최소화하기 위해 IO 제어를 빠른 IO별 이슈 경로와 느린 주기적 계획 경로로 분리

• wall clock time: 작업을 수행하는 데 걸리는 실제 시간으로, 측정된 작업 완료 시간은 당시 시스템에서 수행 중인 다른 작업(CPU, I/O, Sub Program 등)의 영향을 받을 수 있다.
• vtime(virtual time rate): Wall clock time과 함께 진행되는 글로벌 가상 시간으로, IOCost 시스템에서 각 cgroup 내의 IO 작업의 진행 상황을 추적하고 관리하기 위해 사용되는 개념이다.
  • 로컬 vtime: 특정 cgroup 내 IO 작업의 진행 상황을 나타낸다. 각 cgroup의 IO 작업에 따라 증가하며, 증가하는 속도는 해당 IO 작업의 상대적 비용(동일한 cgroup 내의 다른 작업과 비교하여 IO 작업이 얼마나 많은 리소스 또는 시간을 필요로 하는지)에 의해 결정됨
  • 글로벌 vtime: 모든 cgroup의 모든 IO 작업에 대한 전반적인 진행 상황을 나타낸다. 이는 가상 시간 속도(vrate)에 의해 결정된 Wall clock time과 함께 진행되는 가상 시간이다. 
  • 스로틀링 결정은 cgroup의 로컬 vtime과 글로벌 vtime 간의 차이(=cgroup의 현재 IO 예산)를 비교하여 이루어지며, 이를 통해 IO를 즉시 실행할 수 있는지 또는 할당된 예산 내에서 유지하기 위해 추가 진행 상황을 기다려야 하는지를 결정함
    • group의 현재 IO 예산이 IO의 상대적 비용을 충당하기에 충분하면 즉시 실행되고, 그렇지 않으면 글로벌 vtime이 더 진행될 때까지 IO가 대기한다.

• issue path: 로컬 및 글로벌 vtime에 따라 IO 작업의 비용을 결정하고, features에 따라 비용모델을 이용하여 bio의 절대 비용을 계산하고, 스로틀링 결정을 내린다. 각 cgroup에는 가중치(형제 그룹에서의 IO 점유 비율)가 할당되며, 이러한 가중치는 hweight로 재계산되어 캐싱된다.
  • IOCost는 활성 cgroup과 비활성 cgroup을 구분하여, 유휴 cgroup의 남는 자원을 활성 cgroup에서 사용할 수 있도록 한다. 만약 활성/비활성 cgroup의 상태가 변경되면 hweight 가중치를 재계산한다.
    • 활성 cgroup: IO 요청이 있는 경우
    • 비활성 cgroup: IO 없이 전체 planning 기간(= IO 제어 결정이 내려지는 전체 기간)이 지나는 경우로, 가중치 계산 시 무시된다.
• planning path: 글로벌 오케스트레이션을 담당하며, 데이터센터의 각 cgroup 운영을 조정하여 IO 리소스를 효율적이고 공정하게 분배할 수 있도록 한다. 주기적으로 각 cgroup의 IO 사용량을 평가하고, 그에 따라 가중치를 조정한다. 또한 서비스 품질(QoS) 매개변수를 통해 vrate를 수정하여 cgroup 당 발생하는 IO 요청량을 조정한다.

Evaluation

다양한 유형의 SSD가 장착된 단일 소켓 64GB 서버에서 테스트 수행

1) 데이터 센터의 고속 SSD에 대한 IO를 제어할 때는 오버헤드를 최소화하는 것이 중요하다.

=> 최대 초당 입출력 작업 수(IOPS)를 측정하는 실험

• none = 소프트웨어 스케줄러나 컨트롤러가 실행되지 않은 상태로, 디바이스에서 블록 레이어의 달성 가능한 최대 처리량
• IOCost: issue path/planning path로 분할하므로, 복잡한 스로틀링 로직을 가지고 있음에도 오버헤드가 발생하지 않는다.

2) 유휴 자원의 효율적 활용을 보장하는 것이 중요하다.

=> 서로 다른 우선순위를 가진 워크로드에 대해 요청 지연 시간의 특정 임계값을 초과하지 않고 원활하게 실행되는지 평가

• cgroup 인식 IO 제어 메커니즘의 성능 => High:Low = 2:1 이 최적의 분배일때
• IOCost: 예상되는 2:1 비율과 정확히 일치하여 비례 제어에 효과적임을 입증

=> 서로 다른 우선순위를 가진 워크로드에 대해 우선순위 및 지연 시간 요구 사항을 고려하면서, 얼마나 리소스를 비례적으로 잘 배분할 수 있는지 평가

** think time: 다음 연속적인 요청을 실행하기까지 대기/지연 시간 = 새로운 요청이 발생하지 않는 유휴시간

• IOCost: 우선순위가 높은 워크로드의 레이턴시를 효과적으로 관리하면서, 우선순위가 낮은 워크로드가 유휴자원을 활용할 수 있도록 허용함을 입증

3) 다양한 워크로드 간의 공정성과 적절한 격리를 보장하는 것이 중요하다.

=> 각 메커니즘이 디바이스 점유 측면에서 얼마나 공정성을 제공하고 우선순위가 높은 워크로드와 낮은 워크로드 간에 원하는 비율을 유지하는지를 평가

• IOCost: random/sequential IO의 비용을 모델링하고 디바이스 점유 측면에서 공정성을 보장함으로써 모든 시나리오에서 원하는 2:1의 비율을 유지한다. 

4) 최신 SSD의 경우, 단순한 모델링 접근 방식은 부정확하기 때문에 이를 효과적으로 보정하는 것이 중요하다.

=> SSD 워크로드에 대해 원하는 서비스 품질(QoS)을 유지하는 데 있어 IOCost의 동적 조정(vrate)의 효과를 평가

• 처음에는 vrate가 약 100으로 유지
• 0.5x of model(모델 매개변수 값을 감소 = 장치의 점유량이 이전보다 절반으로 줄어드는 경우): IOPs(읽기 속도)가 떨어지지만, QoS를 유지하며 발급 속도를 약 두 배로 상승시켜 IOPs를 유지한다.
• 2x of model(모델 매개변수 값을 증가 = 디바이스의 점유량이 이전보다 두 배로 늘어나는 경우): 처음에는 디바이스를 과도하게 포화시켜 지연 시간이 급증하지만, QoS를 유지하기 위해 vrate가 초기 값의 약 절반으로 떨어지면서 지연 시간이 감소한다.

5) 효율적인 리소스 확보를 위해 메모리 관리 통합이 중요하다. (우선순위가 높은 워크로드에 리소스를 보장하면서 우선순위가 낮은 워크로드가 나머지 리소스를 활용할 수 있도록 리소스를 적절하게 회수하기 위해)

=> 여러 조건에서 웹 서버 처리량을 평가

• IOCost: 메모리 누수 프로세스와 같은 까다로운 조건에서도 웹 서버 처리량을 일정하게 유지

=> 오버커밋 환경에서 IOCost의 성능을 평가

• ramp up time: 본 실험에서 최대 부하의 40% -> 80%로 확장하는 데 걸리는 시간
• IOCost: BFQ보다 약 5배 빠르게 스케일업을 완료할 수 있다

6) 여러 컨테이너 간에 IO 서비스의 공정한 할당이 중요하다.

=>  Zookeeper와 유사한 워크로드에서 노이즈가 많은 이웃 앙상블과 스냅샷의 영향을 얼마나 잘 차단하는지, 그리고 읽기 및 쓰기 작업에 대한 레이턴시 서비스 수준 목표(SLO)를 충족할 수 있는지 평가

• IOCost: 노이즈가 많은 이웃 앙상블과 스냅샷의 영향을 효과적으로 격리하여 서비스의 레이턴시 SLO 위반을 최소화한다.
  • SLO 위반이 1.5s, 1.04s 두번만 발생함

7) 퍼블릭 클라우드와 같은 원격 블록 스토리지 환경에도 적용 할 수 있어야한다.

=> 로컬 스토리지와 원격 연결 스토리지를 포함한 다양한 구성에서(AWS 및 Google Cloud와 같은 퍼블릭 클라우드) IOCost가 IO를 얼마나 잘 격리할 수 있는지 평가

• 지연 시간에 민감한 워크로드(ResourceControlBench)를 AWS Elastic Block Store(gp3-3000iops, io2-64000iops) 및 Google Cloud persistent disk(balanced, SSD)를 사용하여 다양한 구성에서 메모리 누수 워크로드와 함께 배치
• IOCost를 적용하지 않은 경우: 두 워크로드 간에 간섭이 발생하여 RPS(초당 요청)가 감소
• IOCost가 적용된 경우: 메모리 누수 워크로드로 인한 간섭으로부터 ResourceControlBench를 효과적으로 격리하고 보호하여 RPS가 높은 값으로 나타난다.

8) 경합이 심한 조건에서도 시스템 서비스 및 워크로드 간에 IO 리소스를 공정하게 분배(비례 제어 기능)할 수 있어야한다.

** IO 고갈로 인한 통신 장애 및 성능 저하가 발생할 수 있는 데이터센터의 패키지 가져오기 장애/컨테이너 정리 장애에 유용

=> 비례 제어 기능을 갖춘 IOCost가 이러한 장애 발생을 크게 줄이고 시스템 안정성과 리소스 관리를 개선할 수 있음을 입증

- package fetching: 컨테이너화된 애플리케이션에 필요한 소프트웨어 패키지 또는 종속성을 검색하는 프로세스 => IO 고갈(충분한 입출력 리소스 부족)이 발생하면 패키지 검색에 실패하고 후속 컨테이너 업데이트에 실패할 수 있다.

• IOCost가 활성화되면 해당 리전에서 package fetching 오류의 비율이 감소하여 IOLatency와 비교했을 때 오류가 10배 감소

- container cleanup: 데이터센터 환경에서 오래된 컨테이너를 제거하거나 삭제하는 프로세스 => 리소스 경합이나 기타 요인으로 인해 이 작업 중에 IO 고갈이 발생하면 오래된 컨테이너 정리가 지연되어 성능이 저하되거나 충분한 디스크 공간을 확보할 수 없을 수 있다.

• IOCost가 활성화되면 container cleanup 실패 발생이 IOLatency에 비해 3배 감소

Discussion

요즘 연구해보고 싶은 분야와 비슷해서 정말 많이 도움됐다.

컨테이너 기술 동향에 대해서도 살펴볼 수 있었다.

** 컨테이너를 위한 아키텍처 및 OS 확장에 관한 연구

• D. Skarlatos, Q. Chen, J. Chen, T. Xu and J. Torrellas, "Draco: Architectural and Operating System Support for System Call Security," 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), Athens, Greece, 2020, pp. 42-57, doi: 10.1109/MICRO50266.2020.00017.
• D. Skarlatos, U. Darbaz, B. Gopireddy, N. Sung Kim and J. Torrellas, "BabelFish: Fusing Address Translations for Containers," in IEEE Micro, vol. 41, no. 3, pp. 57-62, 1 May-June 2021, doi: 10.1109/MM.2021.3073194.

💡 요약
- abstract: 컨테이너 라이브 마이그레이션의 사전 복사 알고리즘에 더티 페이지가 반복적으로 전송되는 문제를 해결하기 위한 연구
- introduction: 라이브 마이그레이션에서 가장 널리 사용되는 기술인 사전 복사 알고리즘은 메모리 집약적인 시나리오에서 메모리 페이지의 복사를 반복하기 때문에 전송되는 데이터의 양과 총 마이그레이션 시간이 늘어날 뿐만 아니라 반복 프로세스가 수렴되지 않아 마이그레이션이 실패할 수 있다는 문제가 있다.
- related works: 
- method: 프로그램 운영체제의 locality 원칙을 활용하고, 더티 페이지 예측을 위해 랜덤 포레스트 모델을 사용하여 반복되는 더티 페이지 전송을 건너뛴다. 페이지 압축과 함께 incremental page만 전송하여 기존의 사전 복사 방식에 비해 데이터 전송 및 마이그레이션 시간을 크게 단축했다. => 메모리 페이지와 인접한 페이지의 더티 레코드를 수집하고 머신러닝 모델을 사용하여 향후 페이지가 더티화될지 여부를 예측함
- experiment: 더티 페이지가 적게/많이 발생하는 환경에서 제안하는 알고리즘은 가장 최적의 결과를 보여주었다. 
- conclusion & discussion: ML 접근법을 사용하여 컨테이너 라이브 마이그레이션을 최적화하기 위한 알고리즘을 설계했으며, 전송 데이터를 줄이기 위해 압축 알고리즘을 함께 사용했다.

Introduction

• 가상화
  • 가상 머신
  • 컨테이너 가상화:
    • 경량, 휴대성, 빠른 시작 속도
    • Docker, LXC, Podman 
• 서비스 마이그레이션: 가상시스템을 다른 곳으로 이동
  • 콜드 마이그레이션: 전원이 꺼져 있거나 일시 중단된 가상 시스템을 새 호스트로 이동
  • 라이브 마이그레이션 (=핫 마이그레이션): 전원이 켜진 가상 시스템을 새 호스트로 이동
    • 마이그레이션 과정에서 서비스가 영향을 받지 않도록 하는 것을 목표로 한다.
• 사전 복사(pre-copy) 알고리즘: 라이브 마이그레이션에서 가장 널리 사용되는 기술로, 컨테이너가 실행되는 동안 메모리 페이지가 소스에서 대상으로 전송된다.
  • 사전 복사는 일반적으로 남아 있는 더티 페이지 수가 충분히 낮을 때 종료된다. => 메모리 집약적인 시나리오에서 사전 복사 알고리즘은 반복 단계에서 메모리 페이지의 복사를 반복하기 때문에 전송되는 데이터의 양과 총 마이그레이션 시간이 늘어날 뿐만 아니라 반복 프로세스가 수렴되지 않아 마이그레이션이 실패할 수 있다.
  • c.f. Post-copy는 네트워크를 통해 각 페이지를 한 번만 전송하는 반면, Pre-copy는 마이그레이션 중에 페이지가 소스에서 반복적으로 write가 발생하는 경우 동일한 페이지를 여러 번 전송할 수 있다.
    • Pre-copy: 마이그레이션 중에 source에서 VM 상태를 최신 상태로 유지
    • Post-copy: source와 destination 간에 VM 상태를 분할
    • 실시간 마이그레이션 중에 대상이 실패하면 사전 복사는 VM을 복구할 수 있지만 사후 복사는 복구할 수 없다

Related Work

• pre-copy: 더티 메모리 페이지를 반복적으로 복사하여 가상 머신 다운타임을 단축, 부하가 높고 메모리 쓰기 집약적인 시나리오에서는 반복 단계에서 일부 메모리 페이지가 자주 수정되어 매우 더티한 일부 메모리 페이지가 반복적으로 전송될 수 있어서 전송되는 데이터의 양을 증가시킬 뿐만 아니라 반복 프로세스가 수렴하지 못하는 원인이 될 수 있다
  • 페이지 중복 전송 문제를 피하기 위해, 자주 더럽혀지는 페이지를 추적하여 전송 종료 단계에 저장하는 재사용 거리 개념 제안
  • 마르코프 예측 모델을 사용하여 메모리 페이지의 기록된 과거 동작을 사용하여 상태 전이 행렬을 통해 페이지가 다시 수정될 확률을 계산하고 예측 확률이 낮은 페이지만 전송하는 방법을 제안
  • related dirty rate에 기반한 예측 방법을 제안했다. 페이지의 수정 확률 P를 실제 수정 시간 R과 결합하여 관련 더티 페이지 비율 PR을 얻은 후, R과 PR이 모두 설정된 임계값보다 큰 경우에만 페이지 전송을 건너뛴다.
  • => 페이지의 시간적 상관관계만 고려할 뿐 공간적 상관관계는 고려하지 않음
  • 마이그레이션 과정에서 메모리 더티 페이지의 생성 속도를 줄이기 위해 CPU 스케줄링을 사용하여 마이그레이션의 원활한 진행을 보장함 => 필연적으로 애플리케이션 성능 저하로 이어질 수 있으며 여러 번의 반복이 완전히 해결되지 않음
  • 대역폭 인식 기반의 데이터 압축 방법을 제안하여, 마이그레이션 대역폭에 따라 적절한 압축 알고리즘을 동적으로 선택하여 전송할 페이지를 압축한 후 목적지로 전송함으로써 전송 데이터의 양을 줄이고 전체 마이그레이션 시간을 단축함
• post-copy
• hybrid copy
• 로그 기반 추적
• 복제 마이그레이션

가상 머신에 비해 컨테이너 라이브 마이그레이션에 대한 연구는 상대적으로 적다.

• Virtuozzo: 컨테이너에서 라이브 마이그레이션을 지원한다. 마이그레이션을 수행하는 데 필요한 주요 프로세스와 기능을 커널에 통합하여 구현하기 때문에 Virtuozzo 커널은 고도로 커스터마이징된 커널로, 메인스트림 Linux 커널에서 동일한 기능을 구현하기 위해 Virtuozzo는 CRIU 프로젝트를 설립했다.
  • CRIU: Linux에서 실행되는 오픈 소스 소프트웨어 도구로, 사용자 공간에서 프로세스를 체크포인트 및 복원할 수 있다. 즉, 체크포인트 메커니즘을 사용하여 실행 중인 애플리케이션을 동결하고 해당 상태 정보를 디스크에 이미지 파일로 덤프한 다음, 이 이미지 파일을 사용하여 복원 작업을 수행하여 동결된 지점에서 복구하고 프로그램을 다시 실행할 수 있다.
  • => 현재 Docker에는 컨테이너 마이그레이션 작업을 지원하는 통합 CRIU 도구가 있지만, 이 접근 방식은 상태 저장 컨테이너 마이그레이션을 지원할 수 없으며 과도한 다운타임을 초래한다.
• P.Haul: Docker 컨테이너의 외부 마이그레이션을 가능하게 하는 OpenVZ에서 시작한 프로젝트로, 외부 마이그레이션은 P.Haul이 CRIU를 통해 Docker 컨테이너 내 프로세스의 실시간 마이그레이션만 구현하기 때문에, 이 방식은 destination 단의 Docker 엔진이 컨테이너를 관리할 수 있는 기능을 상실하게 된다.
• 중첩 가상화와 컨테이너 마이그레이션을 통해 메모리 공간을 리매핑하여 동일한 호스트에서 컨테이너 메모리 마이그레이션을 최적화 => 호스트 간 컨테이너 마이그레이션을 지원하지 않는다.
• NFS를 사용하여 데이터 전송을 용이하게 하는 방법도 있는데, 이는 메모리 집약적인 워크로드를 마이그레이션할 때 긴 다운타임을 유발한다.
• 파일 시스템 공유 방식을 사용하여 포스트카피와 파일 시스템 유니온을 기반으로 실시간 마이그레이션을 하는 방법도 있다.

Method

• original pre-copy algorithm: 
  • 반복 마이그레이션 단계: 첫 번째 라운드에서 모든 메모리 페이지를 대상 호스트로 전송하고, 이후 각 라운드에서는 이전 라운드 반복 후 수정된 메모리 페이지(더티 페이지)만 전송한다. 셧다운 마이그레이션 조건이 충족될 때까지 이 반복 프로세스를 반복한다.
  • 셧다운 마이그레이션 단계: source 호스트는 컨테이너를 잠시 중지하고, 더티 메모리 페이지의 마지막 라운드와 CPU 등의 기타 상태 정보를 대상 호스트에 전송한 후, 이러한 정보에 따라 destination 호스트에서 컨테이너를 재시작한다.
  • => 메모리 집약적인 쓰기 부하에서는 반복적인 마이그레이션 단계에서 일부 메모리 페이지가 자주 쓰기 되어 페이지 전송이 반복됨

1. 일정 기간 동안 컨테이너 메모리의 변경 사항을 수집
2. 수집한 메모리 더티 데이터를 사용하여 생성된 더티 페이지를 예측 => 더티 페이지가 많은 페이지의 전송을 생략하고 페이지 압축을 사용하여 데이터 전송을 줄인다.
3. (반복적인 복사본 마이그레이션 단계) 페이지 예측과 페이지 압축을 사용하여 더티 페이지의 전송을 최적화한다. 최대 반복 횟수에 도달하거나 더티 페이지 데이터 크기가 수렴하는 등 셧다운 마이그레이션 조건이 충족되면 셧다운 마이그레이션 단계로 진입
4. 셧다운 마이그레이션 단계로, source 호스트는 컨테이너 실행을 중지하고 컨테이너의 남은 더티 페이지를 압축한 후 CPU 및 기타 상태 정보와 함께 대상 호스트에 전송
5. 컨테이너 복구 단계로, destination 호스트는 수신한 메모리 데이터 정보에 따라 컨테이너의 동작을 재개

더티 페이지의 반복 전송 문제를 해결하기 위해

• 더티 페이지 예측: 일정 기간 동안 컨테이너 메모리의 변경 사항을 수집하여 더티 페이지가 향후에도 계속 더티 페이지가 될 확률을 예측하여 더티 비율이 낮은 페이지를 전송할 페이지 세트에 추가하고 더티 비율이 높은 페이지의 전송을 건너 뛴다.
  • 기존의 더티 페이지 예측 방법은 대부분 시계열 예측 방법을 사용하는데, 본 논문에서는 기존 방식과 달리 머신러닝 방식을 사용한다.
    • 특징 추출 방법: 지역성 원리에 기반한 특징 선택
      • 시간적 지역성: 현재 더럽혀진 페이지가 가까운 미래에 다시 더럽혀질 가능성이 높다는 것을 의미
      • 공간적 지역성: 현재 더럽혀진 페이지에 인접한 주소 페이지가 가까운 미래에 더럽혀질 가능성이 높다는 것을 의미
    • 오프라인에서 모델을 학습하는 데 사용하여 컨테이너의 온라인 마이그레이션에 적용한다. 
      • 랜덤 포레스트: 과적합이 쉽지 않고 일반화 능력이 높기 때문에 예측 모델로 선택했으며, 특징 윈도우 m*n이 증가함에 따라 모델 예측 정확도가 증가하는 것을 확인함
      • 실제 컨테이너 마이그레이션에서는 피처 윈도우가 커질수록 예측 시간 오버헤드가 발생하게 되므로, 본 논문에서는 예측 효과와 예측 시간의 균형을 맞추기 위해 피처 윈도우 m=5, n=5로 고정

• PageList: 컨테이너 메모리에 있는 모든 페이지의 집합 => 각 반복 후 관련 페이지 정보를 업데이트해야 한다.
• Dirty: 이번 라운드의 더티 페이지 집합
• ToTransmit: 이번 반복에서 최종적으로 전송할 페이지의 집합
• ToSkip: 반복 중에 전송을 건너뛰는 페이지의 집합
• RFModel: 랜덤 포레스트 예측 모델로, 예측이 1이면 향후에도 페이지가 dirty 할 것을 의미한다. 

각 반복 라운드에서 랜덤 포레스트 모델을 사용하여 현재 더티 페이지가 1로 예측되면 현재 라운드에서 해당 페이지의 전송을 건너뛰고 ToSkip에 추가하고, 예측이 0이면 이번 라운드에서 페이지가 destination에 전송된다.

이번 라운드의 클린 페이지의 경우 이전 반복에서 전송을 건너뛰고 ToSkip에 저장한 경우 이번 라운드에서 제 시간에 대상에 전송해야 한다.

• 전송되는 메모리 페이지 압축: 전송할 페이지를 압축하여 네트워크에서 전송되는 데이터의 양을 더욱 줄인다.
  • 페이지를 전송할 때 페이지 단위가 아닌 바이트 단위로 전송한다. 한 반복 내에서 전송할 더티 메모리 페이지가 처음 전송되는지 여부를 확인하고, 처음 전송되는 페이지가 아니면 지난번에 destination으로 전송한 페이지 데이터와 XOR하여 페이지 증분값을 구한 뒤 페이지 증분값을 압축하여 전송한다.
    • 증분 압축의 장점은 페이지 증분에는 반복되는 0이 많이 포함되어 페이지의 압축률을 향상시키는 데 도움이 된다는 것이다.
    • 압축 알고리즘은 LZ4 압축 알고리즘을 선택했으며, 이는 무손실 압축 알고리즘으로 압축 속도가 빨라 메모리 데이터 압축 장면에 적합하고 압축 비율과 압축 속도를 넓은 범위에서 조정할 수 있다.
  • 데이터를 수신한 destination에서는 압축을 풀고 다시 XOR하여 이번 라운드의 실제 메모리 페이지 데이터를 얻는다.

Experiment

실험 환경: 두 개의 가상 머신에서 Docker 컨테이너의 라이브 마이그레이션을 테스트

• Ubuntu 18.04 LTS, CPU 코어 2개, 8GB RAM 및 50GB 디스크
• 두 가상 머신 간의 네트워크 대역폭은 100Mbps

컨테이너가 실행 중일 때 다양한 메모리 쓰기 부하를 시뮬레이션하기 위해 모든 크기의 연속 메모리를 신청하고 연속 쓰기 작업을 수행할 수 있는 MemChange 프로그램을 작성하고 이를 컨테이너화했다. 

사전 복사 알고리즘은 메모리 더티율이 전송 대역폭을 초과할 수 없어야 하며, 그렇지 않으면 반복 프로세스가 수렴하지 않거나 심지어 중지되므로 실험 환경의 네트워크 대역폭 100Mbps에 따라 두 가지 메모리 더티 레이트 부하를 설계했다. 
- 메모리 저속 부하: 메모리 더티율 1-2M/s 
- 메모리 고속 부하: 메모리 더티율 11~12M/s 

본 논문에서 제안한 마이그레이션 방법 = MBDPC

예측 알고리즘의 성능을 객관적으로 비교하기 위해 MBDPC에서 압축 알고리즘을 제거한 알고리즘 = MBDP

1. 더티 페이지 예측 비교

마르코프, PR 예측 알고리즘과 비교했을 때, 본 논문에서 제안하는 더티페이지 예측 알고리즘의 AUC 값이 약 17% 증가하여 더티 페이지 예측 효과가 더 우수하다는 것을 알 수 있다.

• x축: FPR(오탐률)
• y축: TPR(진탐률)
• AUC: 곡선 아래 영역으로, 모델의 전반적인 랭킹 능력을 반영한다. 넓을수록 좋음

2. 다운 타임: 컨테이너가 중지된 후 서비스 복구까지 걸리는 시간 = T stop + T restore

그림은 다양한 메모리 크기일 때, 저속부하에서의 다운 타임을 보여주는데, 기존 사전 복사 알고리즘과 비교했을 때, 마르코프와 PR은 평균 1.1%, 1.3% 감소한 반면, MBDP와 MBDPC는 평균 2.1%, 2.8% 감소했다.

즉, 컨테이너 메모리가 작을 경우 마르코프, PR, MBDP, MBDPC는 최적화 효과가 거의 없는데, = 저속 시나리오에서는 컨테이너 메모리의 수정 속도가 낮기 때문에 1~2회 반복하면 더티 페이지 수가 즉시 종료 조건을 충족하고 종료 마이그레이션 단계로 들어감 (메모리 크기와 메모리 더티율이 낮은 경우 예측 알고리즘에는 일정한 한계가 있다)

다양한 메모리 크기에서 메모리 고속 부하의 다운타임을 살펴보면, 메모리 더티율이 높을 때 마르코프와 PR은 원본 사전 복사본에 비해 평균 3.3%와 4.1% 감소한 반면, MBDP와 MBDPC는 평균 3.7%와 34.9% 감소했다.

페이지 예측은 반복 프로세스의 속도를 높이고 셧다운 마이그레이션 단계에서 더티 페이지의 수를 줄일 수 있음을 알 수 있으며, MBDPC는 반복 프로세스의 속도를 더 빠르게 할 뿐만 아니라 페이지 압축을 통해 종료 단계에서 전송 시간 Tstop을 크게 단축할 수 있었다.

3. Total Migration Time: 첫 번째 iteration 부터 대상 컨테이너가 컨테이너를 재시작할 때까지의 시간 = ∑T iterative(i) + T stop + T restore

• 저속 부하에서는 페이지 더티율이 낮음
  • 마코프와 PR이 원본 프리카피에 비해 총 마이그레이션 시간을 단축하는 효과가 적다
  • MBDP와 MBDPC는 평균 3%, 16.5% 단축하여 최적화 효과가 더 높다
• 고속 로드에서는 페이지 더티율이 높다
  • 원래의 사전 복사 알고리즘은 높은 더티 페이지를 반복적으로 전송하여 라운드당 더티 페이지 수가 종료 임계값보다 낮아질 수 없다. 따라서 반복 시간 n i=1 Titerative(i)가 길어지고 총 마이그레이션 시간이 증가한다.
  • 원본 사전 복사본과 비교하여 예측 알고리즘은 매우 더티한 페이지의 반복 전송을 피함으로써 반복 시간을 줄일 수 있다.

=> 메모리 더티율이 높을 경우 MBDPC가 총 마이그레이션 시간을 더 잘 줄일 수 있다.

4. 총 전송 데이터: 전체 마이그레이션 과정에서 전송된 데이터의 총량 = ∑TD iterative(i) + TD stop

• 앞선 내용들과 마찬가지로 메모리 더티율이 낮으면 iteration 프로세스가 빠르게 멈추기 때문에 마르코프, PR, MBDP 알고리즘의 최적화 효과는 상대적으로 적다.
• 고속 워크로드에서(메모리 더티율이 높으면) 예측 알고리즘은 원본 사전 복사본과 비교하여 반복 과정에서 매우 더티한 메모리 페이지의 반복 전송을 피함으로써 전송되는 데이터의 양을 줄일 수 있다. MBDPC는 페이지 압축을 사용하기 때문에 전송되는 데이터의 총량을 더 줄일 수 있다.

5. iteration 당 전송되는 데이터의 양:

제안한 MBDPC 방식은 각 라운드의 데이터 양과 마지막에 전송되는 총 데이터 양이 다른 알고리즘에 비해 낮다.

메모리 데이터를 미리 수집하고 첫 번째 라운드에서 예측을 하기 때문에 첫 번째 라운드에서 불필요한 페이지 전송을 피할 수 있다.

Discussion

본 논문에서는 머신러닝 기법의 더티 페이지 예측을 기반으로 하는 컨테이너 사전 복사 마이그레이션 방법인 MBDPC를 제안했다.

MBDPC는 프로그램 로컬리티 원리를 이용해 메모리 더티 페이지를 예측하여 페이지가 반복 전송되는 것을 방지했다.

본 논문은 단일 컨테이너의 마이그레이션에 대한 연구이며, 향후 쿠버네티스와 같이 널리 사용되는 컨테이너 오케스트레이션 도구와 결합하여 여러 컨테이너 간의 마이그레이션 문제를 해결하는 방법을 고려하면 좋을 것 같다.

메모리 접근 특성을 분석하여 시스템 내에서 메모리 관리에 사용하는 쪽만 생각했었는데, 이렇게 라이브 마이그레이션에도 사용할 수 있다는 것을 알 수 있었다. 라이브 마이그레이션에서는 아무래도 전송량이 중요하기 때문에 더티페이지 예측 뿐만 아니라 메모리 압축 기술을 사용했나보다

💡 요약
- abstract: 다양한 워크로드에 대처할 수 있는 유연성을 높이기 위해 컨테이너 기반 애플리케이션의 수평 및 수직 탄력성을 제어하기 위한 강화 학습(RL) 솔루션을 제안한 연구
- introduction: 컨테이너 기반 애플리케이션을 확장할 때 효율성을 최적화하기 위해 확장 정책이 유연하고 적응적으로 동작해야 한다는 과제가 있다.
- related works: 기존에는 수직적 탄력성과 수평적 탄력성을 결합한 연구가 소수만 이루어졌다. 또한 기존에는 탄력성을 구동하기 위해 임계값을 사용했다.
- method: 컨테이너 기반 애플리케이션의 탄력성을 제어하기 위해 모델 없는 솔루션과 모델 기반 솔루션을 포함한 다양한 RL 정책을 사용할 것을 제안했다.
- experiment: 시뮬레이션과 프로토타입 기반 실험을 통해 다양한 RL 접근 방식을 평가했다. 결과적으로 결과는 모델 기반 접근 방식이 사용자 정의 배포 목표에 따라 최상의 적응 정책을 성공적으로 학습할 수 있음을 보여주었다.
- conclusion & discussion: 모델 기반 RL 접근법을 사용하여 컨테이너 기반 애플리케이션의 탄력성을 제어하기 위한 RL 알고리즘을 설계했으며, 제안된 정책을 컨테이너 오케스트레이션 도구인 Docker Swarm에 자체 적응 기능을 도입하는 확장 기능인 Elastic Docker Swarm을 적용했다.

Introduction

컨테이너를 사용하면 수평 및 수직 확장을 통해 애플리케이션 배포를 쉽게 조정할 수 있다.

• 수평적 탄력성: 애플리케이션 인스턴스(컨테이너) 수를 늘린다. => 컨테이너 구성을 변경하므로 새 구성을 적용하는 데 필요한 시간 동안 전체 애플리케이션을 사용할 수 없게 됨(다운타임 발생)
• 수직적 탄력성: 애플리케이션 인스턴스에 할당된 컴퓨팅 리소스의 양을 늘리거나 줄인다 => 일반적으로 추가적인 다운타임이 발생하지는 않지만, Docker Swarm에서 스케일 아웃을 수행하면 적응 비용이 발생
  • Docker Swarm에서 스케일 아웃을 수행하면 적응 비용이 발생하는 이유?
  • Docker Swarm의 트래픽 라우팅 전략 때문이다. 새로운 인스턴스가 실행되기 전에도 Docker Swarm은 애플리케이션 요청을 새로 추가된 인스턴스로 보내려고 시도하는데, 이때 해당 인스턴스가 아직 실행 중이지 않으면 응답하지 못할 가능성이 있다. 따라서 이전 버전의 컨테이너를 사용하여 요청을 처리하기 위해 일시적으로 다운 타임이 발생할 수 있다.

이러한 컨테이너의 특성을 사용하여 런타임에 애플리케이션 배포를 적절히 조정하여 성능을 유지할 수 있다

Related Work

(1) 탄력성 조치를 적용하는 범위에 따른 연구

• 인프라 수준: 인프라 수준에서 탄력성 컨트롤러는 일반적으로 VM을 획득하고 해제하여 컴퓨팅 리소스의 수를 변경한다.
• 애플리케이션 수준: 애플리케이션 수준에서 컨트롤러는 애플리케이션에 직접 할당된 컴퓨팅 리소스를 조정한다(ex. 병렬 처리 수준 변경) 또는, 탄력성 컨트롤러를 애플리케이션 코드 내에 통합하는 임베디드 탄력성을 사용하는데, 이 경우 애플리케이션 자체에서 적응을 조정하는 메커니즘과 정책도 구현해야 한다. 

외부 컨트롤러를 사용하여 컴퓨팅 리소스를 조정하는 방식은 소프트웨어 모듈성과 유연성을 향상시키기 때문에, 본 논문에서는 분산 컨테이너화된 애플리케이션의 수평 및 수직 탄력성을 관리하기 위한 외부 컨트롤러를 제안하고 있다.

(2) 탄력성 조치 적용의 목표에 따른 연구

• 애플리케이션 성능 개선: 로드 밸런싱 및 리소스 활용
• 에너지 효율성
• 배포 비용 절감

대부분의 연구는 단일 수준의 배포 목표를 고려하기 때문에, 본 연구 또한 단일 수준의 배포에 초점을 맞추고 컨테이너 수준에서 탄력성을 활용한다.

(3) 배포를 조정하는 데 사용되는 작업 및 방법론에 따른 연구

• 수학적 프로그래밍 접근법: 컨테이너의 초기 배치와 런타임 배포 적응 비용(배포 재구성으로 인한 성능 저하) 을 고려하여 배포를 조정함
• 휴리스틱: 임계값 기반 및 RL 기반 솔루션
  • 임계값 기반: 클라우드 인프라 레이어뿐만 아니라 런타임에 컨테이너를 확장하는 데 가장 많이 사용되는 접근 방식으로, 기존의 오케스트레이션 프레임워크(Kubernetes, Docker Swarm, Amazon ECS 등)는 일반적으로 일부 로드 메트릭(ex. CPU 사용률)에 기반한 최선의 임계값 기반 정책에 의존하고 있다. => 효과적인 임계값 기반 정책을 사용하려면 임계값 매개변수를 올바르게 설정해야 하며, 이를 위해서는 애플리케이션 리소스 소비에 대한 어느 정도 지식이 필요하며, 수직 확장에 대한 연구는 별로 이루어지지 못했다. = 매우 번거롭다
  • RL 기반 솔루션: Q-Learning 을 이용하여 가상 머신 할당 및 프로비저닝을 위한 정책 수립 등에 적용되어왔다. => 모델이 없는 솔루션이기 때문에 수렴이 느리다는 문제가 있다.

본 논문에서는 빠르게 학습시키기 위해 시스템 지식을 활용하는 새로운 모델 기반 RL 정책을 제안하며, 애플리케이션 배포를 런타임에 적응하기 위해 특히 수직 및 수평 탄력성을 공동으로 활용할 때의 이점을 조사한다.

Background

A. Docker Swarm

Docker는 컨테이너화된 애플리케이션을 생성하고 관리하기 위한 플랫폼으로, Docker를 사용하여 특정 리소스 할당량을 가진 컨테이너를 구성할 수 있고, 런타임에 업데이트하여 수직적 탄력성을 활성화할 수 있다.

Docker Swarm은 master-worker 패턴에 따라 여러 노드에서 컨테이너 실행을 단순화하는 클러스터링 시스템이다.

Method

• 강화학습(Reinforcement Learning): 런타임에 컨테이너 기반 애플리케이션에 대한 최적의 적응 전략을 학습한다.
  • 에이전트(agent): 개별적인 시간 단위로 애플리케이션과 상호 작용하고, 애플리케이션 상태(state)를 관찰하며 예상되는 장기 비용을 최소화하기 위한 작업을 수행한다.
  • 상태(state): 컨테이너 수(=인스턴스 수), CPU 사용률, 각 컨테이너에 할당된 CPU 점유율의 튜플로 정의한다.
  • cost function: 애플리케이션 상태가 s에서 s'로 전환될 때 작업 a를 수행하는 데 드는 비용을 나타낸다. => 비용 최소화는 일반적으로 RL 에이전트의 제약 조건 또는 부차적인 목표이다.
    • 본 논문에서는 적응 비용(컨테이너 추가 또는 제거와 같은 작업에 대한 비용), 성능 비용(애플리케이션 응답 시간 제한을 초과할 때마다), 리소스 비용(애플리케이션 인스턴스 수 및 할당된 CPU 점유율에 비례) 을 단일 가중치 비용 함수로 결합하여 사용한다.
• solution1) Q-learning: 강화 학습에서 샘플링 평균을 통해 최적의 Q-function을 추정하는 데 사용되는 모델 없는 알고리즘이다. 본 논문에서는 greedy 정책으로 기반으로 작업을 선택하지만, 낮은 확률로 차선의 작업도 탐색한다. 각 시간 슬롯이 끝날 때마다 학습 속도 매개변수와 향후 보상의 중요성을 결정하는 discount factor 를 사용하여 관찰된 state-action 쌍에 대한 Q값이 업데이트됨
  • Q-function=Q(s,a): 상태 s에서 액션 a를 실행 시 예상되는 장기 비용을 나타낸다. 컨테이너 확장에 대한 결정을 내리는 데 사용되며, 실제 발생한 비용을 관찰하여 시간이 지남에 따라 업데이트된다. => 높은 보상을 받을 가능성이 가장 높은 행동을 결정할 때 사용
  • Dyna-Q: 애플리케이션과 환경 간의 상호 작용을 시뮬레이션하여 학습 프로세스의 속도를 높이는 강화 학습 알고리즘이다. 런타임에 Dyna-Q는 애플리케이션 상태를 관찰하고 Q-러닝과 유사하게 Q(s, a)의 추정치를 사용하여 적응 action을 선택한 뒤, 탐색된 (s, a)에 대한 다음 상태 s'와 비용 c를 저장하여 런타임에 시스템 모델인 모델(s, a)을 업데이트한다. 모델은 Q-함수를 업데이트하는 데 사용된다.
• solution2) 모델 기반 강화 학습: 본 논문에서는 경험적 데이터를 사용하여 시스템 모델의 전이 확률과 비용 함수를 추정하는 전체 백업 모델 기반 강화학습 접근 방식을 적용했다.
  • 전체 백업 접근법: 추정 가능한 시스템 모델에 의존하며, 벨만 방정식을 사용하여 Q 함수 계산한다. 
  • 샘플 값을 사용하여 비용 추정치를 업데이트하는 동안, 특정 속성을 적용하여 컨테이너 수가 감소하거나 CPU 사용률이 증가하거나 CPU 점유율이 감소할 때 Rmax 위반으로 인한 예상 비용이 낮아지지 않도록 한다

본 논문에서는 Docker Swarm에 모니터링/분석/계획/실행 제어 루프를 적용함으로써 Elastic Docker Swarm(EDS) 아키텍쳐로 확장했다. EDS는 RL 정책을 사용하여 애플리케이션 배포 및 재구성 시기/방법을 결정하며, Docker Swarm API를 활용한다.

• Docker Monitor: 각 노드에서 실행되며, 노드에서 실행 중인 컨테이너의 CPU 사용률에 대한 정보를 메시지 브로커(Apache Kafka)에 주기적으로 게시
• Container Manager: 메시지 브로커를 통해 모니터링 정보를 수신하고, RL 에이전트를 사용하여 분석 및 계획 단계를 수행
  1. RL 에이전트가 애플리케이션 상태를 판단하고 Q-function 을 업데이트한다.
  2. RL 에이전트를 사용하여 수행해야 할 확장 작업을 식별한다.
  3. 애플리케이션 배포를 조정하기 위해 EDS는 Docker Swarm API를 활용한다.

Experiment

• 시뮬레이션 실험: 애플리케이션이 무작위적이고 독립적인 요청(M)을 수신하고, 서버가 요청을 처리하는 데 걸리는 시간(D)은 고정되어 있으며 변하지 않으며, 서버 수는 시간 단계 i에서 사용된 컨테이너 수(ki)와 같다고 가정한다.

• 최대 응답 시간(Rmax) 위반을 방지하는 데 중점을 둔 경우, 모델 기반 솔루션은 응답 시간 위반이 2.85%에 불과하여 모델 없는 접근 방식보다 성능이 더 우수했다. 또한, 리소스 중점 시나리오에서는 모델 기반 솔루션이 애플리케이션 응답 시간이 길어지는 대신 리소스 활용도를 성공적으로 개선했다.
• 5-액션 모델은 학습 작업을 간소화하고 모든 RL 정책에 대한 Rmax 위반을 줄이는 반면, 9-액션 모델은 학습 프로세스를 느리게 했다.

=> 모델 기반 접근 방식이 더 우수하다 = 시스템에 대한 사전 지식이 매우 중요하다

*모델 기반 접근 방식: 시스템의 동적인 특성을 사전에 알고 있는 경우, 이를 활용하여 강화학습 모델이 더욱 효과적으로 학습할 수 있도록 하는 방법

• 프로토타입 기반 실험: Amazon EC2 인스턴스로 구성된 클러스터에서 EDS로 제안된 정책을 사용하여 실제 환경에서 강화 학습(RL) 알고리즘을 평가함

• 목표 응답 시간 위반을 줄이고 워크로드 변동에 적응하는 측면에서 모델 기반 정책이 Q-러닝보다 우수한 것으로 나타났다.
  •  Q러닝은 모델 기반 솔루션과 유사한 솔루션을 찾지만 애플리케이션 배포를 더 자주 변경했다.
  • 모델 기반 솔루션은 Q-러닝보다 Rmax 위반 횟수를 줄이고 애플리케이션 배포를 덜 변경하여 애플리케이션 가용성을 높이는 것으로 나타났다.
• 모델 기반 접근 방식은 수직 확장보다 수평 확장을 선호하는 것으로 관찰되었다.
  • Elastic 배포 시스템(EDS)의 적응 비용 정의에 따라 컨테이너 구성 변경(수직 확장)이 새 컨테이너 추가(수평 확장)보다 비용이 더 많이 들기 때문

=> RL 기반 접근 방식이 갑작스러운 워크로드 변화에 적응할 수 있어서 더 좋지만, 모델 기반 솔루션은 모든 상태, 동작, 다음 상태를 반복해야 하므로 계산이 많이 필요하며, 사용 가능한 동작과 전환 확률이 제한되어 있기 때문에 복잡성이 크다

💡 요약
- abstract: 라이브 VM 마이그레이션을 사용하여 마이크로 아키텍처 리소스의 충돌을 완화하고, 클러스터 수준 가상 머신 스케줄링 기법을 제안한 연구
- introduction: 모바일 디바이스에서 연산 오프로드를 위해 컴퓨팅 리소스를 요구 방식과 클라우드 제공업체의 리소스 제공 방식이 일치하지 않고, 모바일 디바이스가 오프로딩을 사용할 경우 무선네트워크를 사용하는데 이러한 경우 오프로딩 성능의 저하, 높은 비용이 발생한다는 문제점이 있다.
- related works: 시스템 내 스케줄링이나 스레드 스케줄링 위주의 연구가 이루어짐으로써 NUMA 선호도나 공유 캐시는 고려되지 않아 경합의 영향을 완화하기 어렵다.
- method: 캐시 인식 스케줄러 & NUMA 인식 스케줄러
- experiment: 가장 최악의 경우(클라우드 시스템에서 소켓당 LLC 누락의 최대치와 최소치 간의 차이가 가장 큰 매핑 & 모든 VM의 메모리 페이지가 원격 소켓에 할당)보다 성능 향상 관찰
- conclusion & discussion: 본 논문에서는 VM의 동작에 대한 사전 지식이 필요하지 않은 메모리 인식 클라우드 스케줄링 기법을 제안하고 평가했으며, 추후 핫 페이지 마이그레이션을 통해 보다 효율적인 NUMA 인식 스케줄링의 확장 가능성을 제시했다.

Introduction

• 가상화 기반 클라우드 시스템에서 가상머신(VM)은 물리적 리소스를 공유 => 리소스 경합이 발생하는 경우 성능 저하
• 이후 멀티코어의 등장으로 공유 캐시 및 메모리 컨트롤러와 같은 마이크로 아키텍쳐 리소스를 공유 =>  마이크로 아키텍쳐 리소스에 대한 경합은 CPU, 메모리, I/O를 동일하게 공유하더라도 공동 실행중인 애플리케이션에 의해 영향 (성능 편차의 주요 원인)

본 논문에서는 라이브 VM 마이그레이션을 사용하여 공유 캐시 및 메모리 컨트롤러의 경합을 최소화하기 위해 VM을 동적으로 스케줄링하며, 클라우드 서버에서 일반적으로 사용되는 멀티 소켓 시스템에서 NUMA의 영향을 고려함으로써 캐시 공유 및 NUMA 선호도를 위한 경합 인식 클라우드 스케줄링 기법을 제안한다.

• 온라인에서 VM의 캐시 동작을 식별
• 현재 VM의 배치가 과도한 공유 캐시 충돌이나 잘못된 NUMA 선호도를 유발하는 경우 VM을 동적으로 마이그레이션

• 장점: VM 동작을 동적으로 식별하고 실시간 마이그레이션을 통해 충돌 해결 => VM 동작에 대한 사전 지식이 필요X
• 캐시를 고려한 스케줄링은 클라우드 시스템에서 전체 Last Level Cache(LLC) 누락을 최소화
• NUMA 인식 클라우드 스케줄링은 NUMA 선호도를 고려함으로써 캐시를 고려한 스케줄링을 확장

Related Works

리소스 공유로 인힌 리소스 경합을 완화하기 위해

• 기존의 클라우드 시스템: 라이브 마이그레이션 기술을 사용하여 실행중인 VM의 배치를 변경하는 동적 VM 스케줄링을 사용
• 단일 시스템일 때: 스레드를 신중하게 스케줄링하여 공유 캐시 및 메모리 컨트롤러에 대한 경합의 영향을 완화하기 위해 애플리케이션을 그룹화하여 캐시를 공유함으로써 시스템의 전체 캐시 누락을 최소화
  • 메모리 동작의 이질성에 의존하며, 단일 시스템에서 유사한 캐시 동작을 하는 애플리케이션을 실행하는 경우 이러한 시스템 내 스케줄링으로는 경합을 완화할 수 없다
• 스레드 스케줄링: 스레드를 그룹화하고, 서로 다른 소켓에 매핑하여 모든 공유 LLC에서 캐시 누락의 합을 최소화
  • NUMA 선호도는 캐시를 고려한 스케줄링을 복잡하게 만든다.
  • 가상화 시스템에서 일부 상용 하이퍼바이저는 VM의 메모리 액세스 지연 시간을 줄이기 위해 동적 페이지 마이그레이션을 제공하지만 캐시 공유 효과는 고려하지 않았다.

단일 시스템에서의 스케줄링은 코어 수가 적고 LLC를 공유하는 최적의 스레드 그룹을 찾는데 제한이 있다. 하지만 클라우드와 같이 많은 수의 노드로 구성된 가상화된 시스템에서는 VM이 물리적 시스템 경계를 넘어 마이그레이션 할 수 있으므로, 공유 LLC를 위한 더 나은 VM 그룹을 찾고 NUMA 친화성을 지원할 수 있을 가능성이 높다.

Backgrounds

1. 라이브 마이그레이션: 

CPU, 메모리, I/O 하위 시스템과 같은 기존의 할당 가능한 시스템 리소스에서 충돌을 해결하거나 부하를 분산하는데 사용된 기술로, 클라우드 시스템에서 VM에 대한 리소스 사용량을 모니터링하여 트리거한다. CPU, 메모리, I/O 하위 시스템과 같은 기존의 할당 가능한 시스템 리소스에서 충돌을 해결하거나 부하를 분산하는데 사용된 기술로, 클라우드 시스템에서 VM에 대한 리소스 사용량을 모니터링하여 트리거한다. 가장 중요한 점은 실행 중인 가상 머신을 서비스 중단 없이 물리적 호스트 간에 이동시킨다는 점이다. 

구글 사례 를 살펴보면 아래와 같다.

• VM을 현재 호스트 시스템에서 제거해야 한다는 알림 발생
  • 알림은 파일 변경(예: 새 BIOS를 사용할 수 있음을 나타내는 릴리스 엔지니어), 하드웨어 작업 일정 유지 관리, 임박한 하드웨어 오류의 자동 신호 등으로 시작될 수 있다.
• 클러스터 관리 소프트웨어는 이러한 이벤트를 지속적으로 감시하고, 이를 기반으로 데이터 센터(예: 용량 활용률) 및 작업(예: 한 번에 마이그레이션할 수 있는 단일 고객의 VM 수)을 제어하는 ​​정책을 스케줄링
• 마이그레이션을 위해 VM이 선택되면 게스트에게 알림 제공
• 대기 기간 후 대상 호스트가 선택되고 호스트는 마이그레이션 중인 "소스" VM을 수신하기 위해 비어 있는 새 "대상" VM을 설정하라는 요청을 받는다.
  • 소스와 대상 간의 연결을 설정할 때 인증 사용
  • 브라운 아웃 기간: 새로운 VM이 가동된 상태로, 메모리 상의 데이터 등의 VM 내용을 새로운 VM에 복사
  • 블랙 아웃 기간: 이전 VM의 모든 동작을 일순간만 정지시켜 브라운 대기 중에 받은 네트워크 패킷을 새로운 VM에 전송
  • 마이그레이션 이후 브라운 아웃 기간: 이전 VM은 이후에도 남겨, 블랙 아웃 기간 중 받은 네트워크 패킷을 새로운 VM에 전송
• 마이그레이션이 완료되면 시스템이 소스 VM을 삭제 (고객은 로그에서 마이그레이션 수행 여부를 알 수 있다)

2. NUMA(Non-uniform Memory Access)

위 그림과 같이 NUMA 구조에서는 여러 개의 CPU 모듈이 있고 각 CPU 모듈에는 여러 개의 CPU가 포함되며 독립적인 로컬 메모리, I/O 슬롯 등이 있다. 그 결과 메모리 접근 시간이 프로세서와 관련된 메모리 위치에 따라 달라진다. 

• NUMA Affinity: NUMA 영역 간의 메모리 접근은 메모리 버스를 통과해야 할 뿐만 아니라 데이터에 액세스하기 위해 영역 간 버스를 통과해야하기 때문에 지연시간이 증가하고, 버스에서 충돌이 발생할 수도 있다.
  • CPU에 NUMA Affinity를 설정함으로써, NUMA 토폴로지를 선택하여 VM에 할당된 CPU가 있는 NUMA 지역을 제한

Motivation

2.1 Cache Sharing and NUMA Affinity

공유 캐시: 코어 간 동적 용량 공유를 통해 잠재적으로 캐시의 효율성을 향상시킬 수 있지만, 코어 중 하나가 과도한 캐시 미스를 생성하여 다른 코어에서 캐시된 데이터를 제거할 때 경합 문제가 발생할 수도 있다.

공유 캐시에서 이러한 부정적인 간섭을 완화하기 위해:

• 캐시 분할
• 신중한 스레드 스케줄링: 스레드를 그룹화하고, 서로 다른 소켓에 매핑하여 모든 공유 LLC에서 캐시 누락의 합을 최소화

2.2 Performance Implication in Clouds

아래 그림은 NUMA 인식 VM 스케줄링 정책의 조합을 보여준다. 각 조합에서 첫 번째 문자는 캐시 정책을 나타내고 두 번째 문자는 NUMA 정책을 나타내는데, W-W 정책에 비해 성능 향상이 일어났음을 확인할 수 있다.

캐시 공유 측면에서는 두 가지 매핑 정책을 제시한다:

• 가장 좋은 경우(B): 클라우드 시스템의 모든 소켓에서 LLC 누락의 합이 최소화되도록 VM을 코어에 매핑
• 최악의 경우(W): 클라우드 시스템에서 소켓당 LLC 누락의 최대치와 최소치 간의 차이가 가장 큰 매핑

NUMA 선호도에 대해 세 가지 매핑정책을 제시한다:

• 최악의 경우 = 모든 VM의 메모리 페이지가 원격 소켓에 할당되는 경우
• 최상의 경우 = 모든 VM 메모리 페이지가 로컬 소켓에 할당되는 경우
• 인터리브 할당(I) = VM의 메모리 페이지를 항상 두 소켓에 인터리브 방식으로 할당

워크로드 특성

• milc, GemsFDTD: 메모리 사용량이 적은 다른 워크로드와 캐시를 공유함으로써 성능 향상의 가능성
  • 공유 캐시의 최상의 경우에도 좋은 NUMA 정책은 특히 메모리 집약적인 워크로드의 성능을 향상시킬 수 있다.
• hmmer, namd: LLC에 고용량을 요구하지 않기 때문에 개선 효과X
• NUMA 선호도를 최적화할 수 없는 경우, 인터리브 메모리 할당은 NUMA에 대한 최악의 경우를 피하기 위한 대안이 될 수 있음

결과적으로, 소규모 클러스터에서도 VM 스케줄링으로 인한 성능 편차가 클 수 있다.

퍼블릭 클라우드에서는 일관된 성능을 지원하는 것이 중요한데, 대규모 클라우드 시스템에서는 다양한 사용자가 클라우드 시스템을 공유하게 되므로 노드 간 VM 캐시 동작의 이질성이 크다. 따라서 메모리 인식 클라우드 수준 스케줄링은 이러한 캐시 동작의 이질성을 활용하여 최악의 스케줄링을 피하고 공유 캐시 및 NUMA 선호도의 효율성을 잠재적으로 개선할 수 있다.

Method

• 각 컴퓨팅 노드: 모니터는 하드웨어 성능 모니터링 카운터로 LLC 미스를 확인하고, 주기적으로 VM별 LLC 미스 및 NUMA 선호도 정보를 클라우드 스케줄러로 전송한다. = 각 VM의 캐시 동작 수집
• 클라우드 스케줄러: 모든 노드의 VM 상태 정보를 기반으로 글로벌 스케줄링 결정을 내린다. 만약 마이그레이션을 통해 클라우드 시스템에서 전체 캐시 미스와 평균 메모리 접근 레이턴시를 줄일 수 있는 경우, VM을 마이그레이션한다.
  • 캐시 인식 스케줄러: 공유 캐시에 대한 경합만 고려하고 NUMA 효과는 무시 => 그룹화가 NUMA 선호도를 위반할 수 있더라도 전체 클라우드 시스템에서 전체 LLC 누락을 최소화하기 위해 VM을 그룹화한다.
    • 로컬 단계: 각 컴퓨팅 노드의 VM을 그룹화하여 노드의 공유 캐시 도메인(일반적으로 소켓)으로 스케줄링한다. (물리적 노드 간 VM 마이그레이션은 네트워크 대역폭과 컴퓨팅 성능을 소모하므로 먼저 노드 내에서 VM 스케줄링을 최적화하여 이러한 VM 마이그레이션을 최소화하려고 시도) => 로컬 단계에서는 각 노드의 VM을 LLC 미스별로 정렬한 다음 각 LLC가 균일한 미스를 갖도록 그룹화한다. 모든 과정은 과정은 모든 VM이 공유 캐시 도메인 그룹에 할당될 때까지 계속된다. 
    • 글로벌 단계: 클라우드 스케줄러가 클라우드 시스템의 모든 노드에서 LLC 누락이 발생하지 않도록 VM을 재분배하려고 시도 => 클라우드 시스템에서 LLC 미스 수가 가장 많은 노드와 가장 적은 노드 두 개를 찾고, 두 노드에서 LLC 미스 차이가 임계값보다 큰 경우 두 VM은 실시간 마이그레이션을 통해 교체한다.
  • NUMA 인식 스케줄러: 캐시 인식 스케줄러를 확장하여 NUMA 선호도를 고려한다. (로컬 스케줄링이 VM의 NUMA 선호도를 잠재적으로 깨뜨릴 수 있으므로 글로벌 스케줄링만 제공) 
    • 글로벌 단계: 클라우드 시스템에서 LLC 미스 수가 가장 많은 소켓과 가장 적은 소켓 두 개를 선택 후, 두 개의 소켓 중에서 LLC 미스 횟수가 가장 많고 가장 적은 두 개의 VM이 각각 선택하여 두 개의 VM을 교체한다. 이때, 소켓 교환을 통해 메모리 페이지를 포함한 VM이 이동하더라도 NUMA 선호도는 계속 유지한다.
      • 성능 상 오버헤드를 줄이기 위해, 물리적 노드 내에서 VM에 속한 전체 페이지를 마이그레이션하는 대신, VM이 자주 액세스하는 핫 페이지만 다른 소켓으로 마이그레이션하는 방법을 생각해 볼 수 있다.

제안된 메모리 인식 스케줄러의 장점은 VM에 대한 사전 지식 없이 온라인으로 측정된 VM의 정보만 사용한다는 것이다.

처음에는 각 노드의 CPU 및 메모리 가용성만 고려하여 컴퓨팅 노드에 VM을 배치하지만, VM의 캐시 동작을 동적으로 식별하고 메모리 동작을 개선하기 위해 위치를 재조정한다.

Experiment

제안된 스케줄러를 별도의 클라우드 관리자 노드에서 실행하도록 구현했고, 각 컴퓨팅 노드는 Xen 하이퍼바이저로 가상화되었다.

SPECcpu 2006 애플리케이션을 사용하여 제안한 스케줄러를 평가했다.

• VM 마이그레이션의 오버헤드에도 불구하고, 2개의 메모리와 2개의 CPU 바운드 애플리케이션으로 구성된 WL1에서는 전체 성능이 17% 향상
• 캐시 인식 스케줄링: 많은 수의 LLC 미스를 발생시키는 메모리 바운드 애플리케이션(milc, GemsFDTD)의 성능을 크게 개선하는 반면, 다른 두 애플리케이션(hmmer, namd)의 성능은 약간 저하시킨다.
  • hmmer와 namd는 캐시 용량에 크게 민감하지 않지만 메모리 집약적인 애플리케이션과 LLC를 공유해서 성능이 저하됨
• NUMA 인식 스케줄러: 캐시 인식 스케줄러에 비해 전체 성능이 약간 향상되었다. 초기 설계에서 로컬 스케줄링을 제거하고 글로벌 스케줄링에만 의존하여 NUMA 친화성을 유지하므로 클라우드 시스템은 VM 배치를 천천히 조정하게 되며, VM 메모리를 다른 물리적 노드로 복사하는 데 CPU 리소스를 소비한다. VM의 핫 페이지만 단일 노드 내의 다른 소켓으로 마이그레이션하는 로컬 NUMA 인식 스케줄링의 경우에는 NUMA 선호도를 유지하기 위해 불필요한 글로벌 VM 마이그레이션을 줄일 수 있다.

• WL6를 제외하고는 비슷한 추세를 보여준다 => WL6는 모두 CPU 바운드 애플리케이션으로 구성되므로 메모리 인식 스케줄링의 이점을 누릴 수 없기 때문

Discussion

본 논문에서는 VM의 동작에 대한 사전 지식이 필요하지 않은 메모리 인식 클라우드 스케줄링 기법을 제안하고 평가했다.

• VM 라이브 마이그레이션이 마이크로 아키텍처 리소스 경합을 완화하는 데에도 사용될 수 있을 것이다.

💡 요약
- abstract: 모바일 디바이스에 서비스형 컴퓨팅 오프로딩을 제공하여 이러한 격차를 해소하는 COSMOS 시스템의 설계와 구현에 관한 연구
- introduction: 모바일 디바이스에서 연산 오프로드를 위해 컴퓨팅 리소스를 요구 방식과 클라우드 제공업체의 리소스 제공 방식이 일치하지 않고, 모바일 디바이스가 오프로딩을 사용할 경우 무선네트워크를 사용하는데 이러한 경우 오프로딩 성능의 저하, 높은 비용이 발생한다는 문제점이 있다.
- related works: 데이터센터의 전력 소비 비용을 최소화하는 데 초점, 가변적인 네트워크 등은 고려되지 않았다.
- method: 상용 클라우드 서비스 제공업체로부터 컴퓨팅 리소스를 동적으로 확보하여 모바일 사용자의 컴퓨팅 오프로드 수요에 할당한다. 최적화 문제를 제시하고 리소스 관리 메커니즘, 위험 제어 메커니즘, 작업 할당 알고리즘을 포함한 COSMOS 의사 결정의 세 가지 구성 요소를 제안한다.
- experiment: 스마트폰/태블릿에서 Amazon EC2로 오프로딩하는 시스템을 평가한 결과, 기존 오프로딩 시스템에 비해 금전적 비용을 크게 절감하는 것으로 나타났다.
- conclusion & discussion: 

Introduction

오프로딩은 컴퓨팅 자원 및 계산 속도의 한계를 극복하기 위해, 모바일 애플리케이션의 연산 집약적인 부분을 클라우드 컴퓨팅 리소스로 전송하여 성능을 개선하고, 에너지 소비를 줄이는 프로세스이다.

• 모바일 디바이스의 컴퓨팅 리소스 요구 방식과 클라우드 제공업체의 리소스 제공 방식이 일치하지 않아 오프로딩 성능이 저하되고 금전적 비용이 높아질 수 있다.
  • 연산 오프로딩에 적합한 이상적인 컴퓨팅 리소스는 요청 시 즉시 사용할 수 있어야 하며 실행 후 신속하게 해제되어야
  • 클라우드 리소스는 설정 시간이 길고 장기간 임대된다
• 모바일 기기가 서비스 비용이 높은 무선 네트워크를 통해 클라우드 리소스에 접근
  • 3G 네트워크는 상대적으로 대역폭이 낮아 연산 오프로딩을 위한 통신 지연이 길어짐
  • WiFi 네트워크는 대역폭이 높고, 무료로 사용할 수 있지만 커버리지가 제한되어 있어 클라우드에 간헐적으로 연결

따라서 본 논문에서는 모바일 장치에 컴퓨팅 오프로딩을 서비스로 제공하는 COSMOS 시스템을 제안한다. 

• 상용 클라우드 서비스 제공업체로부터 컴퓨팅 리소스를 동적으로 확보하여 모바일 사용자의 컴퓨팅 오프로드 수요에 할당
• 계산 오프로딩에 적합한 리소스를 선택하고 오프로딩 요청에 따라 컴퓨팅 리소스를 적응적으로 유지하는 리소스 관리 메커니즘
• 오프로딩 결정을 내릴 때 수익과 위험을 적절히 평가하는 위험 관리 메커니즘
• 제한된 제어 오버헤드로 클라우드 리소스에 오프로딩 작업을 적절히 할당하는 작업 할당 알고리즘

Background

2.1.1. Computation Offloading

연산 오프로딩 시스템 = 클라이언트 컴포넌트(모바일 디바이스에서 실행) + 서버 컴포넌트(클라우드에서 실행)

• 클라이언트 컴포넌트
  • 모바일 디바이스의 네트워크 성능을 모니터링하고 예측
  • 모바일 디바이스와 클라우드 양쪽에서 입출력 데이터 요구 사항과 실행 시간 측면에서 모바일 애플리케이션의 실행 요구 사항을 추적하고 예측
  • 클라이언트 컴포넌트는 이 정보를 사용하여 계산의 일부분을 클라우드에서 실행하도록 선택하여 총 실행 시간을 최소화
• 서버 컴포넌트
  • 오프로드된 부분을 수신한 후 즉시 실행 및 결과값을 클라이언트 컴포넌트에 반환

일반적으로는 통신 비용을 손해보는 대신 계산적 이득을 얻지만,

불안정한 네트워크 연결과 불충분한 클라우드 리소스 환경에서는 통신 비용이 증가하고 계산 이득 또한 낮아질 수 있다

2.1.2. Cloud Computation Resources

클라우드 컴퓨팅 리소스는 일반적으로 가상 머신(VM) 인스턴스 형태로 제공되며, VM에 OS를 설치하고 시작해야하기 때문에 이 과정에서 지연이 발생한다. VM 인스턴스는 일반적으로 시간 단위로 임대된다.

Related Work

• cyber foraging, cloudlet 등
• 데이터센터의 전력 소비 비용을 최소화하는 데 초점
• MAUI, CloneCloud, ThinkAir: 애플리케이션에서 컴퓨팅 집약적인 부분을 식별하거나 서버 측 지원을 통해 병렬 작업 오프로딩을 활성화하여 모바일 디바이스 전용 컴퓨팅 오프로딩을 활성화하는 방법에 중점

차별점

• 가변적인 네트워크 연결 조건을 처리
• 성능과 금전적 비용을 고려하면서 오프로딩 요구와 클라우드 컴퓨팅 리소스 간의 격차를 해소시킨다.

Method

본 연구에서 COSMOS 시스템은 네트워크 연결, 프로그램 실행 및 리소스 경합의 불확실성을 고려하면서 오프로딩 결정과 작업 할당을 최적화하는 것을 목표로 한다.

• COSMOS Master: 클라우드 리소스를 관리하고 모바일 디바이스와 통신
• COSMOS Server: 오프로드된 작업을 실행하고 대기열에 있는 작업의 실행 시간을 예측
• COSMOS Client: 모바일 애플리케이션을 모니터링하고 컴퓨팅 집약적인 작업을 식별하며, 연산 속도 향상과 통신 지연 예측을 기반으로 오프로드 여부를 결정

작업이 오프로드되면 활성 COSMOS 서버에 할당되고 기한 내에 결과를 받지 못하면 로컬 워커에서 작업이 실행된다.

• Cloud resource management: 비용을 최소화하면서 오프로딩 속도를 높이기 위해 시간 경과에 따라 임대할 가상 머신(VM) 인스턴스의 수와 유형을 결정
  • resource selection: 
    • Mi:  VM 인스턴스 유형 선택
    • Ti: COSMOS 서버를 시작 및 중지하는 시기 선택
    • 프로세서 코어 수 & CPU 주파수 & 각 VM 인스턴스의 가격을 고려하여 선택: COSMOS는 일정 수준의 속도 향상을 보장하면서 오프로딩 비용을 절감하는 것을 목표로 하므로, CPU 주파수가 가장 강력한 VM 인스턴스의 1 - δ보다 큰 가장 비용이 적게 드는 VM 인스턴스를 선택한다고 하자 => 가능한 최대 1 - δ 이상의 속도 향상을 달성
  • server scheduling: 서버 스케줄링은 VM 인스턴스의 사용 비용과 오프로딩 성능의 균형을 맞추는 핵심 메커니즘
    • COSMOS Master는 주기적으로 오프로딩 요청 수와 COSMOS 서버의 워크로드를 수집 => 워크로드가 너무 많으면 새 서버를 켜고, 더 이상 오프로딩 요청을 처리할 필요가 없으면 서버를 끈다.
    • COSMOS Master는 오프로드된 연산 작업의 현재 도착률과 서비스 시간을 계산하여 원하는 오프로드 성능을 달성하는 데 필요한 최소 COSMOS 서버 수를 추정하여 활성 서버 수 조정
    • COSMOS 서버가 처리할 수 있는 최대 도착 속도(λs)를 추정하기 위해 Kingman의 공식을 사용; λs = c / [μ(1 - δ)]
      • input: 필요한 속도 향상(즉, 최대 속도 향상의 1-δ), 시스템의 최대 응답 시간(μ(1-δ)보다 작아야 함)
      • c: 서버 수, μ: 서버의 서비스 속도
      • λs = 단일 서버가 δ 및 μ로 지정된 성능 요구 사항을 충족하면서 처리할 수 있는 초당 오프로딩 요청 수
• Offloading decision: 네트워크 연결 및 리소스 경합과 같은 불확실성을 고려하여 컴퓨팅 작업을 모바일 기기에서 VM 인스턴스로 오프로드할지 아니면 로컬에서 실행할지를 결정
  • Offloading Controller: connectivity/execution predictor의 정보를 사용하여 오프로딩 서비스의 잠재적 이점을 추정
    • greedy 전략: 오프로드 가능한 작업이 시작될 때마다 오프로드 컨트롤러는 해당 작업을 오프로드하는 것이 유리한지 여부를 결정 => 만약 잘못된 결정이 내려지면 새로운 정보를 바탕으로 전략 조정
    • 예측된 로컬 실행 시간이 오프로드 응답 시간보다 긴 경우에 오프로드하는 것이 유리하다.
  • Risk-Controlled Offloading Decision: 모바일 환경의 불확실성 때문에 위험 제어 매커니즘 필요
    • 오프로딩의 수익과 위험을 동시에 고려하는 위험 조정 수익 접근 방식을 사용
    • 위험 조정 수익률이 특정 임계값을 초과하면 작업이 클라우드로 오프로드되고, 그렇지 않으면 로컬에서 실행 => 시스템은 새로운 정보(연결상태 등)가 입수되면 수익률과 리스크를 재평가하고 그에 따라 결정을 조정
• Task allocation: 계산 작업이 오프로드되는 경우 사용 가능한 모든 인스턴스 중에서 VM 인스턴스를 선택하는 작업이 포함되며, 각 모바일 기기에서 독립적으로 결정하고 이전 작업 결정 및 리소스 공유를 고려
  • 모바일 디바이스가 작업을 COSMOS 서버로 오프로드하려면 일단 작업을 어느 서버로 보낼지 결정해야한다.
    • 서버를 결정하기 위한 세 가지 휴리스틱 방법이 있다:
    • 1. COSMOS 마스터가 글로벌 대기열을 유지하여 오프로딩 요청을 직접 수락하고 COSMOS 서버에 유휴 코어가 있을 때 태스크 할당 = 서버 활용도가 높아야 하지만 COSMOS 마스터를 연결하는 네트워크가 병목 현상이 발생 가능
    • 2. COSMOS 클라이언트가 COSMOS 서버 집합의 워크로드를 쿼리하여 워크로드가 낮은 서버를 무작위로 선택하여 태스크 할당 = 작업이 COSMOS 서버로 직접 전송되지만 엄청난 제어 트래픽을 유발 & 추가 대기 시간 발생
    • 3. COSMOS 마스터가 각 COSMOS 클라이언트에 활성 COSMOS 서버 셋을 제공하고 모든 COSMOS 서버의 평균 워크로드를 알려준다. << COSMOS는 리소스 관리 메커니즘으로 인해 제어 오버헤드가 최소화되고 성능이 좋은 세 번째 방법을 사용

Experiment

• COSMOS 서버: Android-x86 AMI(32bit OS)를 사용하여 Android x86 및 Amazon EC2 인스턴스에서 구현되었다.
• COSMOS 마스터: Ubuntu 12.04 EC2 인스턴스에서 실행되며, Amazon EC2 API 도구를 사용하여 COSMOS 서버를 관리
• COSMOS 클라이언트: 와이파이 및 3G 연결이 가능한 안드로이드 기기에서 실행되며, 자바 리플렉션 기술을 사용하여 계산 작업의 오프로딩을 지원한다.

속도 향상과 비용이라는 두 가지 메트릭을 사용하여 COSMOS를 평가한다. 

• 클론클라우드: 각 모바일 디바이스가 클라우드에 항상 켜져 있는 서버를 가지고 있는 기본 오프로딩 시스템, 안정적인 네트워크 연결을 가정한다.
• 오라클: 오프로딩 결정을 내리는 데 필요한 모든 연결 및 실행 프로파일 정보를 정확하게 알고 있다고 가정한다. (오프로딩 이점에 대한 상한선)
• COSMOS(OP): 리소스 관리를 위한 간단한 전략, 즉 피크 요청에 대해 활성 COSMOS 서버의 수를 오버프로비저닝하는 COSMOS의 변형 => 단, 피크 요청의 수를 사전에 정확하게 예측한다고 가정한다.

세 시스템 모두 비슷한 속도 향상2(a)을 달성하지만, COSMOS의 총 비용2(b)은 CloneCloud 및 COSMOS(OP)보다 훨씬 낮다.

그림 2(c)에서 활성 디바이스 수(파란색 점선)와 활성 COSMOS 서버 수(빨간색 선)를 그래프로 표시하여 COSMOS가 비용을 절감하는 방법을 설명한다 => COSMOS는 오프로딩 요청의 도착률에 따라 활성 COSMOS 서버의 수를 적응적으로 변경함으로써 오프로딩 요청이 적을 때는 일부 COSMOS 서버를 꺼서 비용을 절감한다.

• COSMOS: 오프로딩 요청의 도착 속도에 따라 활성 COSMOS 서버의 수를 적응적으로 변경하여 비용을 절감
• COSMOS(OP): 하루 종일 3대의 COSMOS 서버를 활성화하는 데 더 많은 비용을 지출
• CloneCloud: 약간의 속도 향상 효과만 있을 뿐 COSMOS보다 훨씬 더 많은 비용을 지출

내 Wi-Fi, 실외 Wi-Fi, 실외 3G와 같은 다양한 네트워크 환경에서 COSMOS가 얼마나 잘 작동하는지 테스트하려고 하는데, 동적인 모바일 환경에서는 오프로드 가능한 작업을 호출할 때마다 인터넷 품질이 다르기 때문에 비교가 매우 어렵다. 따라서 공정한 비교를 위해 실험실 컴퓨터를 실행해서 다른 클라우드 리소스로부터의 간섭을 제거한다. 이를 통해 인터넷 속도나 동시에 실행 중인 다른 클라우드 서비스와의 리소스 경합과 같은 외부 요인으로 인한 편견이나 불공정한 장단점 없이 다양한 조건에서 COSMOS가 얼마나 잘 작동하는지 비교할 수 있다.

• COSMOS는 성능이 뛰어나며 오라클과 비슷한 성능을 달성하는 동시에, 잘못된 오프로딩 결정 횟수를 줄임으로써 클론 클라우드보다 뛰어난 성능을 발휘한다.
• 클라우드로 계산을 오프로드하면 실내 WiFi 시나리오에서는 약 80%의 경우에서 모바일 애플리케이션에 이점이 있지만, 실외 3G 시나리오에서는 대역폭이 낮고 지연이 길기 때문에 최대 30%의 경우만 이점이 있다

그 다음은, 오프로드 요청 강도가 COSMOS의 성능에 미치는 영향을 분석한다.

• 시뮬레이션을 사용하여 다른 설정은 변경하지 않고 도착 속도(요청이 발생하는 빈도)를 초당 0.1에서 최대 초당 0.4까지 다양하게 변경 => 비용 절감을 위해 클라우드 리소스 공유가 중요한 낮은 도착률에서 COSMOS가 CloneCloud라는 다른 시스템보다 더 낮은 비용과 더 빠른 속도를 달성
  • COSMOS와 COSMOS(OP) 모두 도착률이 낮을수록 비용이 낮아지는 반면, CloneCloud는 비용이 일정 = 비용 절감에 있어 클라우드 리소스 공유가 중요하다
  • 도착률이 매우 높은 경우(0.4)에는 COSMOS(OP)가 CloneCloud보다 더 높은 속도를 보인다.
  • 모든 실험에서 COSMOS의 속도 향상은 CloneCloud와 COSMOS(OP)의 속도 향상과 유사하다.
• 오프로딩 요청의 수에 따라 비용과 속도 사이에 약간의 트레이드오프가 있을 수 있지만, COSMOS는 CloneCloud와 같은 다른 시스템에 비해 매우 저렴한 비용으로 고성능 계산 오프로딩을 제공할 수 있다

오프로딩 결정을 내리기 위해 COSMOS 클라이언트는 연결 예측과 실행 예측에 의존하여 오프로딩된 작업이 처리를 완료하고 결과를 반환하는 데 필요한 시간(응답 시간)을 추정하게 되는데, 만약 예측에 오류가 있으면 응답 시간이 잘못 예측되어 잘못된 오프로드 결정과 성능 저하로 이어질 수 있다. 이러한 예측 오류에 비해 COSMOS 성능이 얼마나 견고한지 알아보자

• 예측 오차가 증가함에 따라 COSMOS 성능이 약간 저하되지만, 심각한 오차가 있더라도 대부분 오프로딩 요청에 대해 COSMOS는 여전히 높은 속도 향상을 달성한다.  => 오프로딩 이득이 높을수록 예측 오류에 대한 견고성이 더 높다

Discussion

어느 환경에서 실험했는지, 시나리오도 굉장히 자세해서 좋았다. (왜 이런 실험을 했는지도 잘 나와있음)

그리고 어떠한 결과값을 보여 주기 위해서 어떻게 실험 설계를 해야하는지 잘 설명이 되어있어서 배울점이 많았다.

시뮬레이션 뿐만 아니라 실제 트레이스를 가지고 실험 결과를 보여줘서 더 신뢰성이 있었다.

💡 요약
- abstract: Hadoop, MPI 등 여러 다양한 클러스터 컴퓨팅 프레임워크 간에 리소스를 공유할 수 있는 플랫폼에 관한 연구
- introduction: 모든 애플리케이션에 최적화된 단일 프레임워크는 없기 때문에, 단일 클러스터에서 여러 프레임워크를 실행하여 활용도를 극대화하고 프레임워크 간에 데이터를 공유하고자 하는데 효율적으로 공유하기 어렵다는 문제점이 있다.
- related works: 
  * HPC 스케줄러(예: 토크, LSF, 썬 그리드 엔진): 비탄력적인 작업(예: mpi)을 위한 세분화된 공유
  * 가상 머신 클라우드: HPC와 유사한 coarse-grained 공유
  * 콘도르: 매치메이킹에 기반한 중앙 집중식 스케줄러
  * 병렬 작업: 차세대 하둡
    * 애플리케이션별 마스터를 갖도록 하둡 재설계
    * 또한 맵리듀스가 아닌 작업도 지원하는 것을 목표
    * 리소스 요청 언어와 지역 환경설정에 기반한 비매핑 작업 지원 목표
- method: Mesos는 각 프레임워크에 제공할 리소스 수를 결정하고, 프레임워크는 어떤 리소스를 수락할지, 어떤 계산을 실행할지 결정한다. zookeeper를 사용하여 master 장애를 조치할 수 있으며, hadoop/mpi/torque에 연결할 수 있다. 
- experiment: 다양한 프레임워크 간에 클러스터를 공유할 때 거의 최적의 데이터 로컬리티를 달성할 수 있고, 50,000개(에뮬레이트된) 노드로 확장할 수 있으며, 장애에 대한 복원력이 뛰어난 것으로 나타남
- conclusion & discussion: Mesos는 세분화된 방식으로 리소스를 공유하므로 프레임워크가 각 머신에 저장된 데이터를 번갈아 읽음으로써 데이터 로컬리티를 달성할 수 있다

Introduction

클러스터 컴퓨팅 프레임워크는 상용 서버 클러스터에서 프로그래밍을 간소화하고 데이터 집약적인 과학 애플리케이션을 실행하는 데 사용 된다. 모든 애플리케이션에 대해 최적화된 프레임워크는 없기 때문에, 사람들은 동일 클러스터 내에서 여러 프레임워크를 실행하고 그들간에 데이터가 공유되길 원한다.

클러스터를 공유하는 두 가지 일반적인 방법:

• 클러스터를 정적으로 분할 후, 파티션 당 하나의 프레임워크 실행
• 각 프레임워크에 VM 할당

그러나 이러한 방법들은 프레임워크 간에 세분화된 공유를 수행할 수 있는 방법이 없기 때문에 프레임워크 간에 클러스터와 데이터를 효율적으로 공유하기가 어렵다.

따라서 본 논문에서는 프레임워크에 클러스터 리소스 접근을 위한 공통 인터페이스를 제공하여 다양한 클러스터 컴퓨팅 프레임워크 간 세분화 된 공유를 가능하게 하는 fine-grained 리소스 공유 계층 Mesos를 제안한다. 즉, Mesos는 여러 클러스터 컴퓨팅 프레임워크 간에 세분화된 공유를 제공하여 MPI 및 MapReduce Online과 같은 다양한 프레임워크를 사용할 수 있도록 하는 것을 목표로 한다.

Mesos는 프레임워크 요구 사항, 리소스 가용성, 조직 정책을 입력으로 받아 모든 작업에 대한 글로벌 스케줄을 계산하는 중앙 집중식 스케줄러를 구현하는 대신, resource offer 이라는 추상화를 통해 스케줄링에 대한 제어를 프레임워크에 위임한다. 

• resource offer: 프레임워크가 작업을 실행하기 위해 클러스터 노드에 할당할 수 있는 리소스를 캡슐화

Related Work

• Hpc schedulers(torque, lsf, sun grid engine): 특수 하드웨어로 클러스터를 관리하며, 여기서 작업은 모놀리식이며 수명 기간 동안 리소스 요구 사항이 변경되지 않는다. 중앙 집중식 스케줄링을 사용하며 사용자가 작업 제출 시 필요한 리소스를 선언해야 하므로 클러스터가 세분화되어 할당된다. 
  • Mesos는 작업 및 프레임워크 수준에서 세분화된 공유를 통해 배치를 제어할 수 있으므로 작업이 클러스터 전체에 분산된 데이터에 액세스하고 동적으로 확장 및 축소할 수 있다.
• 가상 머신 클라우드(Amazon EC2, Eucalyptus): 애플리케이션을 격리하고 낮은 수준의 추상화를 제공하는 것을 목표로 하지만, 가상 머신 클라우드는 상대적으로 세분화된 할당 모델을 사용하므로 리소스 활용과 데이터 공유의 효율성이 떨어진다. 또한, VM의 크기를 초과하여 작업 배치를 지정할 수 없다.
  • Mesos는 프레임워크별로 매우 선택적인 작업 배치를 허용
• Quincy: DAG 기반 프로그래밍을 위해 중앙 집중식 스케줄링 알고리즘을 사용하는 Dryad용 스케줄러
  • Mesos는 여러 클러스터 컴퓨팅 프레임워크를 지원하기 위해 리소스 오퍼의 저수준 추상화를 제공
• Condor: 리소스 사양 언어를 사용하여 노드와 작업을 매칭하는 클러스터 관리자, 단 프레임워크에 유연하진 않다.

Method

Mesos는 다양한 프레임워크가 클러스터를 효율적으로 공유할 수 있도록 확장 가능하고 복원력 있는 코어를 제공하는 것을 목표로 하기 때문에, 프레임워크 간에 리소스를 효율적으로 공유할 수 있는 최소한의 인터페이스를 정의하고, 그렇지 않은 경우 작업 스케줄링 및 실행 제어를 프레임워크에 위임한다.

• slave: 각 클러스터 노드에서 실행됨 = launches and isolates executors
• framework: salve에서 작업 실행
  • scheduler:  마스터에 등록하여 리소스를 제공받음, 제공된 리소스 중 어떤 리소스를 사용할지 선택 = framework-specific scheduling
  • job: 프레임워크의 작업을 실행하기 위해 슬레이브 노드에서 실행되는 실행자 프로세스
  • 제약 조건을 충족하지 않는 리소스를 거부하고 제약 조건을 충족하는 리소스를 기다릴 수 있다 (필터링 기능)
• master: slave 데몬 관리 = pick framework to offer resources to
  • resource offer(slave에 있는 free 리소스)를 사용하여 프레임워크 간 세분화 된 공유 구현
  • 각 프레임워크에 제공할 리소스 수를 결정

1. master가 slave로부터 사용 가능한 리소스에 대한 리포트를 수신
2. master가 할당 모듈을 호출하여 특정 프레임워크에 사용 가능한 모든 리소스 제공 (resource offer를 프레임워크로 전달)
3. 프레임워크 스케줄러가 slave에서 실행 할 작업에 대한 정보로 응답
4. master가 프레임워크의 실행자에게 할당하기 위해 작업을 slave로 전송

Mesos의 리소스 할당 모듈은 공정한 공유를 수행하거나, 리소스 할당에 대한 엄격한 우선 순위를 구현할 수 있다.

일반적으로 대부분의 작업이 짧다는 가정 하에 리소스가 작업이 완료 후 재할당 되는데, 만약 클러스터가 긴 작업으로 가득 차면 할당 모듈이 어느 작업이든 kill 할 수도 있다. (단, Mesos는 작업을 종료하기 전에 프레임워크에 유예 기간을 제공)

이러한 경우에는 상호 의존적인 작업이 종료되는 것을 방지하기 위해, 할당 모듈은 프레임워크가 작업 손실 없이 보유할 수 있는 리소스의 양을 지정하고, 프레임워크는 API 호출을 통해 보장된 할당을 읽을 수 있다.

Mesos의 리소스 격리 정책에 대해 살펴보자면, 동일한 서버에서 실행되는 서로 다른 프레임워크의 서로 다른 작업을 서로 격리하여 간섭을 방지할 수 있다. 이러한 메커니즘은 플랫폼에 따라 다르므로 플러그형 격리 모듈을 통해 운영체제 격리 매커니즘을 지원한다.

특히 Mesos는 현재 Linux 컨테이너 및 Solaris 프로젝트와 같은 OS 컨테이너 기술을 사용하여 프로세스 트리의 CPU, 메모리, 네트워크 대역폭 및 I/O 사용량을 제한할 수 있다.

=> 격리 없이 컨테이너(프로세스)를 사용하는 Hadoop보다 개선됨

Mesos는 내결함성(fault tolerant)을 제공하기 위해 모든 프레임워크가 의존하는 master를 내결함성으로 만드는 것이 중요하다. 즉, 마스터에 장애가 발생하더라도 새로운 마스터가 슬레이브와 프레임워크 스케줄러가 보유한 정보로부터 마스터의 상태를 재구성할 수 있도록 할 수 있어야 한다.

• master의 상태: 활성 슬레이브, 활성 프레임워크, 실행 중인 작업 목록 등으로 정의

또한, 분산 시스템에서 리더 또는 코디네이터 역할을 할 단일 노드를 선택하기 위해 ZooKeeper가 사용된다.(여러 master가 hot-stanby 구성으로 실행되고, 그 중 하나가 언제든지 활성 마스터로 선출) 

• hot-standby: 시스템의 여러 인스턴스가 동시에 실행되지만 주어진 시간에 하나의 인스턴스만 활성화된다. 다른 인스턴스는 대기 상태에 있으며 활성 인스턴스에 장애가 발생하거나 사용할 수 없게 되면 이를 대신한다. => master 중 하나에 장애가 발생하거나 유지보수를 위해 다운되더라도 Mesos 클러스터에서 리소스를 관리하고 작업을 예약할 수 있는 활성 마스터가 항상 존재

• callbacks: 프레임워크가 구현해야 하는 함수
• actions: 프레임워크가 호출 할 수 있는 작업

프레임워크의 워크로드는 탄력성 & 작업 시간 분포 두 가지로 특징지어질 수 있다.

• Hadoop 및 Dryad: 탄력적인 프레임워크, 필요에 따라 리소스를 확장 및 축소 가능 = 탄력적 프레임워크
• MPI: 고정된 양의 리소스가 필요하며 동적으로 확장할 수 없다 = 경직적(rigid) 프레임워크
• 작업 시간: 동종분포 vs 이질분포 / 상수형 vs 지수형

리소스는 두 가지 유형으로 구분되는데, 프레임워크에서 요청하는 필수 리소스의 양은 보장된 점유율을 초과하지 않는 것으로 가정한다. => 프레임워크가 필수 리소스가 확보되기를 기다리면서 데드락에 걸리지 않게 된다.

• 필수 리소스: 프레임워크가 실행하기 위해 반드시 확보해야 하는 리소스
• 선호 리소스: 프레임워크가 해당 리소스를 사용하여 "더 나은" 성능을 발휘하지만 다른 동등한 리소스를 사용하여 실행할 수도 있는 경우

또한 모든 작업은 동일한 리소스 요구량을 가지고, "슬롯"이라고 하는 동일한 머신 슬라이스에서 실행되며, 각 프레임워크는 단일 작업을 실행한다고 가정한다.

위 환경에 Mesos를 적용한 경우,  작업 지속 시간이 일정한 탄력적 프레임워크의 성능이 가장 우수하고, 작업 지속 시간이 기하급수적으로 증가하는 rigid 프레임워크의 성능이 가장 나쁘다.

• framework ramp-up time: 프레임워크가 선호하는 슬롯을 모두 확보하는 데 걸리는 시간
  • 작업 지속 시간이 일정하면 모든 슬롯이 T 간격 동안 사용 가능해지므로 프레임워크가 k 슬롯을 획득하는 데 최대 T 시간이 걸리지만 작업 지속 시간이 기하급수적으로 증가하면 예상되는 램프업 시간은 T ln k만큼 길어질 수 있다
• 작업 완료 시간: 작업 기간 분포가 다른 여러 프레임워크의 작업에 대한 예상 완료 시간
  • 탄력적 작업의 예상 완료 시간은 최대 (1 + β)T이며, 이는 모든 슬롯이 한 번에 완료될 때 작업 완료 시간의 T 이내이다.
  • 리지드 작업은 일정한 작업 기간의 경우 비슷한 완료 시간을 달성
  • 작업 지속 시간이 기하급수적으로 길어질 때는 훨씬 더 긴 완료 시간, 즉 (ln k + β)T
• 시스템 활용률: 사용되는 프레임워크 유형에 따라 시스템 활용률이 달라진다.
  • 탄력적 작업은 할당된 슬롯을 받는 즉시 모든 슬롯을 완전히 사용하므로 해당 작업에 대한 수요가 무한대인 경우 전체 활용도가 높아진다
  • 리지드 프레임워크는 전체 할당을 받을 때까지 작업을 시작할 수 없기 때문에 활용도가 약간 떨어지며, 램프업 시간 동안 리소스가 낭비된다

만약 프레임워크마다 선호하는 노드가 다르며, 시간이 지남에 따라 선호도가 변경된다고 한다면 어떻게 될까?

• 일부 프레임워크가 선호하는 슬롯을 모두 할당받을 수 없는 경우 = 가중치 공정 할당 정책을 사용할 수 있으며, 추첨 스케줄링이 이러한 할당을 달성하는 데 도움이 될 수 있다. 즉, 스케줄러는 각 프레임워크의 선호도를 알 수 없지만 추첨 스케줄링은 의도한 할당에 비례하는 확률로 프레임워크에 슬롯을 제공할 수 있다.

작업 기간이 짧은 프레임워크가 일부 작업이 다른 작업보다 훨씬 긴 이질적인(혼합된) 작업 기간 분포의 영향을 받게 되는데 어떻게 해야할까?

• 태스크에 리소스를 무작위로 할당하는 것이 잘 작동할 수 있다
• 또한 최대 작업 기간을 해당 리소스에 연결하여 짧은 작업을 위해 각 노드에서 리소스를 예약하는 할당 정책을 허용하는 Mesos의 확장도 제안 = HPC 클러스터에서 짧은 작업을 위한 별도의 대기열을 두는 것과 유사 = 컴퓨팅 리소스를 할당할 때 짧은 작업이 긴 작업보다 우선순위를 갖도록 

Experiment

본 챕터에서는 Mesos가 AWS EC2(4CPU, 15GB RAM)에서 시스템이 4개의 워크로드 간 리소스를 공유하는 방식을 평가했다.

- Facebook의 워크로드에 따라 소규모 작업과 대규모 작업을 혼합하여 실행하는 Hadoop 인스턴스 (텍스트 검색/단순 선택/집계/조인의 네 가지 유형의 쿼리로 구성되며, 데이터 필터링(CPU-intensive) 및 데이터 그룹화(I/O-intensive)와 같은 다양한 작업 포함)
- 대규모 배치 작업 세트를 실행하는 Hadoop 인스턴스 (IO-intensive)

- 머신 러닝 작업을 실행하는 Spark (CPU-intensive, 그러나 각 노드에서 입력 데이터를 캐싱하는 이점이 있고, 각 반복마다 작업을 실행하는 모든 노드에 업데이트된 매개변수를 브로드캐스트해야 한다)
- MPI 작업을 실행하는 Torque (CPU-intensive)

=> fair sharing, 96 노드의 Mesos 클러스터에서 4개의 프레임워크로 워크로드를 실행 VS 클러스터의 정적 파티션(24 노드) 비교

• 다른 프레임워크의 수요가 낮은 기간 동안 Mesos를 통해 각 프레임워크가 확장될 수 있다

• Hadoop/Spark: 글로벌 수요가 허용하는 경우 Mesos를 활용하여 클러스터의 1/4 이상으로 확장하고, 결과적으로 작업을 더 빠르게 완료할 수 있다
• Torque: Mesos에서 거의 유사한 할당과 작업 기간을 달성하며, 더 오래 걸리기도 함 => 부분적으로 Torque가 각 작업을 시작하기 전에 Mesos에서 24개의 작업을 실행할 때까지 기다려야하기 때문
• Hadoop mix: 가장 큰 이득을 보는 프레임워크로, 거의 항상 실행할 작업이 있고 다른 프레임워크의 수요 부족을 메워준다
• 규모가 작은 작업일수록 새로운 리소스를 제안 받기까지 지연이 생기므로 Mesos에서 성능이 더 나쁘다

단, Mesos의 오버헤드는 실험 결과 4%미만으로 거의 없었다.

• 정적 파티셔닝: Hadoop 인스턴스가 파티션 외부의 노드에서 데이터를 가져와야 하므로 데이터 로컬리티(18%)가 매우 낮다
• Mesos: 지연 스케줄링 없이도 데이터 로컬리티가 향상 => 각 Hadoop 인스턴스는 클러스터의 더 많은 노드에서 작업을 수행하므로(노드당 4개의 작업) 로컬로 더 많은 블록에 액세스할 수 있기 때문
  • 지연 스케줄링: Mesos는 프레임워크에 리소스를 즉시 할당하는 대신 리소스를 제공하기 전에 일정 시간 동안 기다림으로써 여러 프레임워크가 리소스 요구 사항을 표현한 다음 그에 따라 리소스를 제공 = 성능 향상

• 99개의 Amazon EC2 노드에서 최대 50,000개의 슬레이브 데몬을 실행하여 대규모 클러스터 실험
• 클러스터 전체에서 실행되는 프레임워크를 사용하여 작업을 지속적으로 실행한 결과, 50,000개의 노드에서도 오버헤드가 1초 미만으로 관찰 됨 = 데이터 센터 워크로드의 평균 작업 및 작업 길이보다 훨씬 작다
• EC2의 가상화 환경은 슬레이브가 5만 개를 넘어서는 확장성에 제한 => 50,000개의 슬레이브에서 마스터가 초당 100,000개의 패킷(인+아웃)을 처리하기 때문이며, 이는 현재 EC2에서 달성할 수 있는 한계이다. 슬레이브 노드가 더 많아지면 네트워크 혼잡 및 기타 요인으로 성능이 저하될 수 있다.

Discussion

Mesos 스케줄링 시스템을 통해 프레임워크는 어떤 오퍼를 수락할지 선택할 수 있으며, 프레임워크가 짧은 작업을 사용하고, 탄력적으로 확장하며, 알려지지 않은 리소스를 수락하지 않도록 하는 장점이 있다. 그러나 분산형 스케줄링은 파편화, 상호 의존적인 프레임워크 제약, 프레임워크의 복잡성 증가 등 중앙 집중식 스케줄링에 비해 한계가 있을 수 있다

• 클러스터 환경에서의 분산 스케줄링 접근 방식의 한계
  • 작업의 리소스 요구 사항이 이질적인 경우 중앙 집중식 스케줄러와 마찬가지로 빈 패킹을 최적화하지 못할 수 있다
  • 리소스 요구량이 많은 프레임워크가 리소스 요구량이 적은 작업으로 클러스터가 채워질 경우 고갈될 수 있다
  • 상호 의존적인 프레임워크 제약으로 인해 클러스터의 단일 전역 할당만 잘 수행되는 시나리오를 구성하기 어려울 수 있다. (단, 이러한 시나리오는 실제로는 드물다)
  • 리소스 오퍼를 사용하면 프레임워크 스케줄링이 더 복잡해질 수 있지만, 기존 프레임워크의 많은 스케줄링 정책은 온라인 알고리즘이며 리소스 오퍼를 통해 쉽게 구현할 수 있다

Mesos이 효율적인 이유는:

1. 프레임워크가 특정 리소스를 거부할지 여부를 지정하는 필터를 마스터에 제공함으로써 거부 프로세스를 단축할 수 있다.
2. Mesos는 프레임워크에 제공되는 리소스를 클러스터 할당에 포함시켜 프레임워크가 오퍼에 신속하게 응답하고 사용할 수 없는 리소스를 필터링하도록 인센티브를 부여
3. Mesos는 프레임워크가 응답하는 데 너무 오래 걸리는 경우 오퍼를 취소하고 다른 프레임워크에 리소스를 다시 제공

특히 프레임워크가 탄력적으로 확장 및 축소할 수 있고, 작업 지속 시간이 균일하며, 프레임워크가 모든 노드를 동일하게 선호할 때 더 효율적이다.

https://github.com/apache/mesos

💡 요약
- abstract: Facebook의 사진 서비스 워크로드를 캐싱 계층(브라우저 캐시, 엣지 캐시, 서버 캐시 등)마다 분석 및 캐시 알고리즘 성능 평가에 관한 연구
- introduction: 소셜 네트워크의 인기로 인터넷 포털에서 제작되는 미디어 콘텐츠의 양이 늘어남에 따라, 이를 저장하기 위한 대용량 볼륨을 저장하고 전송하는 스택의 효율성이 문제가 되고 있다.
- related works: 
  * 네트워크 트레이스 분석 측면
    * peer-to-peer 네트워크가 인터넷 트래픽의 주를 이루던 시기에 수행
    * "aggregated" 네트워크 트래픽을 모니터링하여 얻은 데이터를 분석하여 광범위한 통계를 산출하지만, 특정 애플리케이션 속성에 대한 인사이트는 제한적이었다.
    * Coral CDN의 5년치 시스템 로그를 운영 속성과 아키텍쳐의 측면에서 조사하여 그 동작을 연구
  * 백엔드 스토리지 측면
    * 웹 캐싱과 관련하여 Zipf의 법칙의 영향을 조사한 연구: 인기도 분포가 인구 규모에 따라 캐시 적중률을 대수적으로 증가
    * 미디어 콘텐츠에 대한 접근은 고전적인 Zipf 분포에 비해 머리와 꼬리 부분이 왜곡되어 있는 경우가 많다
- method: Facebook이 제어하는 스택의 모든 계층을 계측하고 그 결과 이벤트 스트림을 샘플링하여 트래픽 패턴, 캐시 액세스 패턴, 클라이언트 및 서버의 지리적 위치를 연구하고 콘텐츠의 속성과 액세스 간의 상관관계를 탐색
- experiment: 매우 활동적인 클라이언트의 경우 브라우저 캐시 크기를 늘리고 덜 활동적인 클라이언트의 경우 로컬 사진 크기 조정을 활성화하여 클라이언트 성능을 개선할 수 있다.
  * 브라우저 캐시, 엣지 캐시, 오리진 캐시가 총 트래픽의 90%를 처리
  * 가장 인기 있는 0.03%의 콘텐츠의 경우 캐시 적중률이 100%에 가까움
- conclusion & discussion: 본 연구는 계층별 캐시 효율성을 정량화함으로써 향후 콘텐츠 저장 및 전송 시스템의 설계 결정을 내리는데 인사이트를 확보할 수 있는 연구, 인터넷 이미지 서비스 인프라 전체를 대규모로 조사한 최초의 연구로서 의미가 있다.

Introduction

소셜 네트워크의 등장으로 인터넷 포털에 저장되는 사용자 생성 콘텐츠(특히 미디어 콘텐츠)가 크게 증가하면서 소셜 네트워크 제공업체를 위한 대용량 바이너리 객체를 저장하고 전송하는 효율적인 시스템이 중요해졌다. 본 논문에서는 클라이언트 브라우저에서 Facebook의 Haystack 스토리지 서버에 이르는 전체 Facebook 사진 서비스 스택을 살펴보고, 각 계층의 성능과 여러 시스템 계층 간의 상호 작용을 살펴본다.

• 실험에 사용된 캐시 계층: 
  • 소셜 네트워크 웹 사이트에 접속하는 모든 데스크톱과 노트북에서 실행되는 클라이언트 브라우저: I/O가 제한된 백엔드 헤이스택 서버를 위한 트래픽 보호를 위해
    • 일반적으로 브라우저 캐시는 인메모리 해시 테이블을 사용하여 캐시 내 존재 여부 확인
    • LRU 알고리즘
    • miss: 브라우저는 HTTP 요청을 인터넷으로 보내고 fetch 경로에 따라 해당 요청이 Akamai CDN/Facebook Edge 전송 여부가 결정됨(2) => 사진 파일의 URL은 웹 서버의 고유한 사진 식별자/이미지의 표시 크기/각 캐시 계층에서 실패한 요청이 다음에 전달될 위치를 지정하는 fetch 경로가 초함되어있어 서버 스택 전반의 트래픽 분산을 제어할 수 있다.
  • 지리적으로 분산된 지점에 배포된 모든 엣지 캐시 호스트: 엣지 캐시의 주요 목표는 엣지와 오리진 데이터센터 간의 대역폭을 줄이기 위해
    • 최종 사용자와 가까운 접속 지점(PoP)에서 실행되도록
    • 미국 전역의 약 9개의 엣지 캐시가 분산되어 독립적으로 작동 => 동부 지역의 엣지 캐시가 서부 지역의 오리진 캐시 서버에 데이터를 요청해야 하는 경우도 있어 지연시간 증가할 수 있다
    • FIFO 알고리즘
    • 각 엣지 캐시에는 저장된 사진에 대한 메타데이터를 보관하는 인메모리 해시 테이블과 실제 사진을 저장하는 대용량의 플래시 메모리가 있다
    • hit: 플래시 메모리에서 사진을 검색하여 클라이언트 브라우저로 반환
    • miss: facebook origin cache에서 사진을 가져와 edge cache에 삽입(3)
  • 미국 데이터 센터의 origin cache: I/O가 제한된 백엔드 헤이스택 서버를 위한 트래픽 보호를 위해
    • 사진의 고유 ID를 기반으로 해시 매핑을 사용하여 에지 캐시에서 오리진 캐시에 있는 서버로 라우팅
    • 각 오리진 캐시 서버에는 저장된 사진에 대한 메타데이터를 보관하는 인메모리 해시 테이블과 실제 사진을 저장하는 대용량 플래시 메모리가 있다
    • FIFO 알고리즘
    • 스토리지 서버와 함께 위치하기 때문에 로컬 헤이스택 서버에서 이미지를 검색할 수 있는 경우가 많다(4)
  • 미국 데이터 센터의 백엔드 서버(Haystack)
    • compact blob representation 을 사용하여 log structured 볼륨에 보관되는 큰 세그먼트 이미지로 저장
    • 시스템은 사진 볼륨 ID와 오프셋을 메모리에 보관하고, 원하는 데이터를 검색하기 위해 한 번의 검색과 한 번의 디스크 읽기를 수행하도록 설계되어있다. (I/O를 최소화)
    • 사진이 Facebook에 처음 업로드되면 알려진 몇 가지 일반적인 크기로 크기가 조정되고, 각 크기에 맞는 사본이 백엔드 Haystack 머신에 저장됨(캐싱 인프라는 변형되고 잘린 사진을 모두 별도의 개체로 취급)

Related Work

• 콘텐츠 전송, 저장 및 웹 호스팅과 관련된 서비스에대한 웹 액세스 패턴을 조사한 연구
  • 워싱턴 대학 - 인터넷사이에 캡쳐한 네트워크 트레이스를 사용하여 네 가지 인터넷 콘텐츠 전송 매커니즘의 특성 비교 => peer-to-peer 네트워크가 인터넷 트래픽의 주를 이루던 시기에 수행된 한계점
  • 이후 워싱턴 대학 캠퍼스 트레이스에서 나타난 미디어 인기도 분포를 기존 웹 트래픽과 비교
• 콘텐츠 전송 네트워크(CDN)에서의 플래시 크라우드 현상에 관한 연구
  • 집계된 네트워크 트래픽을 모니터링하여 얻은 데이터에 중점 => aggregated 데이터를 분석한 것이므로, 관찰된 현상을 일으킨 애플리케이션 속성에 대한 인사이트는 제한적으로만 얻을 수 있다.
  • Coral CDN의 5년치 시스템 로그를 조사하여 그 동작을 연구
• 백엔드 스토리지 서버에 관한 연구
• 웹 워크로드 모델링에 관한 연구
  • 웹 자체의 진화에 따른 워크로드 변화를 평가할 정도로 장기간에 걸쳐 웹 트래픽을 모니터링
  • Zipf의 법칙의 영향을 조사하여 Zipf와 유사한 인기도 분포가 인구 규모에 따라 캐시 적중률을 대수적으로 증가시키고 다른 효과도 발생시킨다는 것을 보여줌
  • 미디어 콘텐츠에 대한 액세스는 고전적인 Zipf 분포에 비해 머리와 꼬리가 상당히 왜곡되어 있는 경우가 많다고 주장

기존 연구와의 차별점
- 본 논문은 페이스북의 워크로드에 대한 최초의 체계적인 연구로, CDN의 대규모 네트워크 트래픽 통계에만 집중했던 기존 연구와 차별화된다.
- 대규모 블롭 트래픽에 집중하여 다양한 이슈를 다루고 체계적인 분석과 인사이트를 제공
- 서버의 로깅 정보를 분석하고 캐싱 정책이 페이스북 인프라의 부하를 줄이는 방법을 탐구

Method

Facebook의 사진 서비스 인프라를 계측하여 한 달간 분산 로깅 서비스인 Scribe를 이용하여 트레이스 샘플링하여 수집

• 사진 ID에 대한 결정론적 테스트를 통해 선택된 일부 사진 하위 집합에 초점을 맞춘 샘플링 방식
• 트레이스의 편향 정도를 정량화하기 위해 두 개의 개별 데이터 셋으로 다운샘플링했으며, 각 데이터 셋은 원본 사진Id의 10%

Experiment

7,720만 건의 브라우저 요청 중 브라우저 캐시(65.5%), 엣지 캐시(20.0%), 오리진 캐시(4.6%), 백엔드(9.9%)

• % of traffic served: 서비스 또는 시스템의 특정 요소가 처리하는 총 트래픽의 백분율을 나타내는 지표 = Hits/전체
• hit ratio: 캐시의 효율성을 측정하는 데 사용되는 메트릭 중 하나로, 데이터가 요청되어 이미 캐시에 저장되어 있을 때 얼마나 빨리 검색할 수 있는지를 나타내는 지표 = Hits/Photo requests

각 사진에 대한 반복 요청 횟수를 추적함으로써 해당 객체의 인기도를 정량화할 수 있다. (Haystack-저장된 공통 크기의 사진을 하나의 개체로 간주/others-크기가 조정된 각 변형 사진을 기본 사진과는 별개의 개체로 취급)

• 일반적으로 웹 트래픽은 Zipfian 분포를 따르는데, 스택의 깊이가 깊어질수록(Haystack으로 갈수록) 양쪽 끝(가장 인기 있는 개체 & 가장 인기 없는 개체) 그래프가 평탄해진다 = Zipf계수 감소 = 일부 오브젝트가 이전 레이어에서보다 인기 있던 개체는 덜 인기있어지고, 인기없던 개체는 더 인기 있다 = Haystack으로 갈수록 인기도의 편향성이 적게 나타난다

• X축: 브라우저에서 정렬된 특정 사진 블롭의 순위
• Y축: 동일한 사진 개체에 대한 Edge/Origin/Haystack 레이어에서의 순위
• 인기도 분포는 모든 레이어에서 대략 Zipfian과 비슷하나, 특히 Edge 레이어에서 상위 100개 사진의 경우 순위가 많이 바뀐다
• 트래픽은 브라우저캐시(요청 수 많음)->엣지캐시->헤이스택(요청 수 적음)에 도달하면서 캐싱 레이어에서 요청을 처리하므로 인기있는 이미지에 대한 요청수가 꾸준히 감소한다 = 스트림의 캐싱 가능량이 점차 줄어든다 = Haystack으로 갈수록 Zipf 계수가 작아지는 이유 

그 다음으로는 인기도와 캐시 Hit과의 관계를 살펴본다

• (a) 1주일간 각 계층에서 처리한 클라이언트 요청에 대한 트래픽 점유율
• (b) 각 계층이 처리하는 트래픽을 이미지 인기도 그룹으로 분류
  • 브라우저 캐시, 엣지 캐시가 가장 인기 있는 10만 개의 이미지(그룹 A-E)에 대한 요청의 89% 이상을 처리
  • 인기가 떨어질수록(그룹 F, G) 캐시에 상주할 가능성이 낮아져 더 높은 비율의 요청이 Haystack 백엔드에서 충족
  • 오리진 캐시는 특히 엣지 캐시에 유지될 만큼 인기가 높지 않은 중간 인기 그룹(D, E, F)의 블롭에 효과적이다
  • 브라우저 캐시 적중률이 B그룹<C그룹인 이유? 일부 사진 그룹에 특정 클라이언트의 요청 수가 많은 이유는 해당 사진이 바이럴 되면서 동시에 많은 사람이 액세스하기 때문 => 고객이 바이럴 콘텐츠를 재방문할 가능성은 낮다
  • 엣지 캐시와 브라우저 캐시가 이미지 카테고리를 서비스할 때 서로를 보완적으로 작동한다(그룹 A-C 요청의 90% 처리)
• (c) 인기 있는 사진과 인기 없는 사진의 캐시 레이어별 적중률
  • 인기 있는 사진은 많은 사용자가 자주 액세스하므로 공유 캐시(엣지, 오리진 캐시)에 해당 사진이 있을 가능성이 높다
    
  • 인기 없는 사진은 공유 캐시에 존재하지 않을 수 있지만 한 사용자의 트래픽만 표시되는 개별 브라우저 캐시에는 여전히 남아있을 수 있다

엣지 캐시->오리진 캐시 데이터 센터로 전송되는 요청 트래픽의 지리적 패턴을 알아보자

• Facebook의 라우팅 정책은 지연 시간, 엣지 캐시 용량, ISP 피어링 비용을 기반으로 하기 때문에 물리적 위치를 반드시 반영하진 않을 수 있다 = 지리적으로 가까운 도시에서 요청의 대부분을 수신하지만, 가장 많은 요청이 반드시 가장 가까운 이웃 도시로 전달되는 것은 아님
• San Jose, D.C. 엣지 캐시는 피어링 품질이 우수하여 멀리 떨어져 있는 클라이언트의 경우에도 다른 엣지 캐시에 비해 우수

• 오리진 캐시: 엣지 캐시에 누락이 발생할 때마다 해당 사진의 일관된 해시값을 기반으로 데이터 센터(오리진 캐시)에 연락
• 각 엣지 캐시를 대신하여 각 데이터 센터가 처리하는 트래픽의 비율은 거의 일정하다 = 에지 캐시가 요청된 사진을 찾지 못하면 해당 사진의 일관된 해시값을 기반으로 데이터 센터에 요청한다.
• 즉, 오리진 캐시 서버는 지역이 아닌 콘텐츠에 기반하여 동작한다. 

데이터 센터에 요청이 이루어지면 최적의 속도를 위해 요청이 해당 데이터 센터 내에 유지되는 것이 이상적이지만 

오리진 캐시 서버가 Miss인 경우 Facebook 백엔드 서버에서 사진을 가져올 수 있는데, 이 프로세스는 네트워크 지연 및 기타 요인으로 인해 시간이 오래 걸릴 수 있다. 이러한 경우에는 서버는 원격 대안을 선택한다.

• 원격 대안: 이미지의 로컬 복제본이 오프라인 상태이거나 과부하 상태인 경우, 오리진 캐시 서버는 다른 데이터 센터에 있는 해당 이미지의 다른 복사본을 선택한다. 즉, Facebook의 광범위하게 분산된 스토리지 계층에 저장된 동일한 사진의 다른 사본을 말한다.

브라우저, 엣지, 오리진 캐시의 성능 및 효과를 각각 살펴보자면,

브라우저 캐시

한 달동안 브라우저 캐시 트레이스 중 초반 25%를 사용하여 캐시를 채운 후, 나머지 75%로 Hit ratio를 평가한다.

• 활동성이 낮은 그룹(1-10건 요청)은 39.2%의 Hit ratio이지만, 활동성이 높은 그룹(1K-10K건 요청)은 92.9%의 Hit ratio를 보였다. = 활동성이 높은 클라이언트는 활동성이 낮은 클라이언트보다 반복 콘텐츠에 액세스할 가능성이 높다

엣지 캐시

본 연구에서는 엣지 캐시에서 다양한 캐시 크기와 캐시 알고리즘을 시뮬레이션하여 Hit ratio를 개선할 수 있는지 가능성을 조사했다. 마찬가지로, 한 달동안 엣지 캐시 트레이스 중 초반 25%를 사용하여 캐시를 채운 후, 나머지 75%로 Hit ratio를 평가한다.

• 브라우저 캐시에 비해 무한 캐시(상한선)가 높다 = 개선의 여지가 많다는 가능성 제시

• (a) LRU, Clairvoyant, S4LRU 등의 정교한 알고리즘이 현재의 FIFO 알고리즘에 비해 상당히 높은 Hit rate를 보여준다. 그리고 이러한 개선은 각각 다운스트림 요청 감소로 이어진다.
• (b) LFU의 경우는 엣지에서 일부 트래픽을 보호할 수는 있지만 대역폭 소비를 증가시키기 때문에 Facebook에 개선 효과가 없다 = LFU는 오브젝트 적중률과 다운스트림 요청 감소 측면에서는 성능이 우수할 수 있지만, 바이트 적중률 측면에서는 현재 캐싱 알고리즘(FIFO)보다 성능이 떨어지며, 이는 오리진과 엣지 캐시 간에 더 많은 데이터를 전송해야 한다
  • Facebook의 경우 엣지 캐시의 주요 목표는 트래픽 보호가 아니라 대역폭 감소임 
• (c) 협업형 엣지 캐시: 모든 에지 캐시를 하나의 논리적 캐시로 결합하는 가상의 캐시로, 사진을 한 번만 저장하도록 하여 더 많은 사진을 저장할 수 있는 여분의 공간이 남는다.
  • 현재의 모든 엣지 캐시를 하나의 논리적 캐시로 결합하는 것이 여러 개의 개별 캐시를 사용하는 것보다 더 효율적인지 확인해보기 위한 실험 => 더 효율적인 수 있지만, 피어링 비용과 지연 시간 증가로 인해 궁극적으로 경제적이지는 않을 수도 있다
• 변곡점: 캐시 크기를 이 지점 이상으로 늘려도 적중률이 크게 개선되지 않으며, 오히려 오버헤드 증가로 인해 수익이 감소하거나 성능이 저하될 수 있음
  • 캐시 크기를 늘리는 것도 적중률을 개선하는 효과적인 방법이나 적절한 캐시 크기를 선택해야 한다. 

오리진 캐시

• s4lru 알고리즘이 최상의 결과를 나타낸다.

Discussion

일단 이미지 개체이기때문에 수정이 별로 일어나지 않아서 캐시의 효과가 더 극대화 된 것이 아닐까 하는 생각이 든다.

트레이스를 추출한 후 어떤 그래프를 그려야 하는지, 그리고 어떻게 그래프를 해석했는지에 대한 내용이 많이 도움 되었다.

그리고 워크로드 패턴, 트래픽 분포, 지리적 시스템 등 여러가지 관점에서 워크로드를 분석하는 것을 어떻게 시스템 설계에 사용하면 좋을지 인사이트를 제공해주는 연구였다.

💡 요약
- abstract: 딥러닝 모델을 학습하는 컨테이너의 리소스 사용량을 분석하는 방법에 관한 연구
- introduction: 딥 러닝 클라우드 서비스에 컨테이너를 배치할 때, 동적으로 배치 시 최적의 리소스 요구량을 자동으로 예측하기 어렵다. 
- related works: 
- method: 모니터링을 통해 서로 다른 DL 모델을 학습하는 컨테이너의 반복되는 패턴과 리소스 사용의 유사성을 관찰하여, 반복 패턴을 스케줄러 또는 리소스 오토스케일러에서 활용한다.
- experiment: 통계 기반 사후 대응 대책과 비교했을 때, CPU 및 메모리 할당을 최대 30% 줄일 수 있었다.
- conclusion & discussion: 리소스 사용 메트릭에서 컨테이너 변화를 측정하고, 리소스 수요를 추정하여 딥 러닝 워크로드에 대한 컨테이너 자동 확장 정택을 고안하는 메커니즘을 구축했다. 

Introduction

기존 고성능 컴퓨팅 환경에서는 특정 학습 작업마다 전용 머신을 리소스 요구량에 맞는 서버를 설정(프로비저닝)했다면, 

IBM DLaaS 또는 Google Cloud AI Platform, Kubeflow 등의 클라우드의 네이티브 머신러닝 서비스는 동일한 머신에 여러 개의 컨테이너를 함께 배치할 수 있는데, 만약 각 컨테이너에 고정된 양의 리소스를 할당하면 리소스가 과도하게 할당될 수 있다. 왜냐하면 각 컨테이너마다 필요한 리소스양이 다를 수 있기 때문이다.

각 컨테이너에 리소스를 동적으로 프로비저닝하려면 과소 프로비저닝 및 서비스 품질(QoS) 저하 방지를 위한 사전 예방적 정책이 필요하다. 모든 컨테이너는 서로 다른 모델에 대한 트레이닝을 실행한다고 가정하면, 보편적으로 알맞은 정책은 찾기 어려울 것이다. 또한, 복잡하고 변화하는 리소스 요구량은 기존의 시계열 알고리즘(ARIMA, ARMA 등)만으로는 모델링하기 어렵다. 

본 논문에서는 Conditional Restricted Boltzmann Machine을 사용하여 리소스 사용량의 다변량 시계열을 인코딩하고, 비지도 클러스터링 방법을 적용하여 컨테이너의 리소스 변화량을 자동으로 발견할 것을 제안했다. 

• DL 워크로드와 같은 무작위적이고 복잡한 패턴의 burst 및 spike를 학습함으로써 패턴을 발견할 수 있다.
• 트리와 그래프를 사용하여 컨테이너에서 학습한 모든 단계 시퀀스를 기반으로 컨테이너 작동 단계를 모델링한다.

Backgrounds

Autoscaling: 실제 사용량이 정점에 도달하기 전 미래의 리소스 수요 촉증을 사전에 예측하고 이에 대비할 수 있다.

ex) AWS Autoscaling 동작 원리

Related Works

• 과거 리소스 사용량의 통계적 특징을 기반으로 시계열 ML 기법을 사용하여 애플리케이션 리소스 수요를 예측하는 데 중점을 두었다. => 워크로드의 애플리케이션에 초점을 맞추고 예측모델을 선택하여 범용적인 워크로드에 적용하기에는 어려움이 있었다.
• 리소스 사용에 대한 패턴을 발견하고 애플리케이션을 분류하기 위해 워크로드를 모델링한 연구 => 패턴을 식별하기 위해 DL 모델을 학습하는 여러 컨테이너에서 관찰되는 리소스 사용 데이터가 필요하다. 
• 워크로드 모델링의 경우 기존에는 작업의 도착이 리소스의 수요를 결정한다고 가정하며, 추세와 계절성을 포함한 시간 의존적 구조를 잘 포착하는 ARMA 및 ARIMA 모델을 사용했다. => DL 학습 중 리소스 사용량이 급증하는 패턴을 포착하기 어렵다.
• 분산 DL 학습에는 네트워킹 리소스가 중요한 부분을 차지하므로, 학습 태스크의 배치를 최적화 하기 위해 다양한 토폴로지 기반 정책을 적용했다. 기존에는 코드에 수동으로 라벨을 지정하거나, 해당 DL 아키텍처의 일부를 식별하도록 했다. => 클라우드 사용자들은 DL 모델이나 특정 구성에 대한 정보를 공유하기 꺼릴 수 있으며, 훈련 세션마다 서로 다른 유형의 데이터와 모델을 사용하므로 사용자 및 실행에 따라 다양한 정책을 적용하기 어렵다. 

주요 클라우드 서비스 제공업체의 ML 플랫폼(IBM WML, Amazon Sagemaker, Microsoft Azure ML, Google Cloud AI Platform 등)과 클라우드 네이티브 머신 러닝을 위한 오픈 소스 솔루션(Kubeflow, FfDL 등)에 대한 공개 문서를 보면, 위 플랫폼 대부분이 컨테이너화된 클라우드 네이티브 환경에서 모델 학습 워크로드를 목표로 한다는 것을 알 수 있다.

만약 모든 DL 작업의 최대 사용량만큼 컨테이너에 리소스를 할당하면, 클러스터의 할당 가능한 리소스가 빠르게 고갈될 수 있으며 실제 사용량에 비해 낭비될 수 있다. 따라서 ML 워크로드의 리소스 사용 패턴을 이해하고, 컨테이너를 동적으로 자동 확장함으로써 전반적인 리소스 효율성을 개선하는 것이 중요하다.

Method

1. 컨테이너 리소스 사용량(CPU와 메모리) 수집
2. Conditional Restricted Boltzmann Machine에서 컨테이너 리소스 사용량 메트릭을 인코딩
   • Conditional Restricted Boltzmann Machine: 신경망의 일종으로, 다차원 데이터를 특징 벡터로 인코딩함으로써, 시계열 패턴 분석을 유용하게 한다. 유사한 패턴은 유사한 인코딩 결과값을 가진다.
3. k-means 과 같은 클러스터링 방법을 사용하여 유사한 동작을 phase 별로 그룹화한다.
   • Memory load - Intensive CPU - Memory unload
   • 컨테이너가 어떤 동작을 하는지, 얼마나 많은 리소스가 필요한지, 어떤 순서로 리소스를 소비하는지 분석
4. 컨테이너의 전체 수명 주기를 일련의 phase로 표현하며, 이를 트리 또는 그래프로 모델링하여 컨테이너가 수행하는 동작의 유형과 필요한 리소스의 양을 파악한다.
   • 동적 리소스 할당 정책: 특정 기간동안 애플리케이션 사용량을 미리 파악하여 리소스 할당 => 리소스 사용량을 예측하는 데 효과적일 수 있지만 갑작스러운 변경이나 예기치 않은 수요 급증을 고려하지 못할 수 있다.
   • 적응형 리소스 할당 정책: 이전 시간대를 기준으로 관찰된 수요에 따라 리소스 할당 => 갑작스러운 변화에 더 잘 대응하고 예기치 않은 수요 급증을 더 잘 처리할 수 있지만, 이 접근 방식은 반응형 특성으로 인해 새 리소스를 프로비저닝할 때 지연이 발생
   • phase 기반 리소스 할당 정책: 현재 단계에 대해 검색하고, 통계를 사용하여 리소스 할당 => 각 단계의 통계 정보를 기반으로 리소스 프로비저닝을 동적으로 조정할 수 있으며, 컨테이너 요구사항의 약 95%를 충족함

본 논문에서는 실험을 통해 5000개의 DL 애플리케이션의 리소스 요구량이 약 6개의 형태의 클러스터로 나뉨을 관찰할 수 있었다.

Experiments

내부 연구자로부터 제공된 IBM DLaaS 서비스를 제공하는 클러스터에서 DL 모델을 학습하는 컨테이너 리소스 사용량 메트릭 5000개를 사용하고, 테스트 및 모델링 프로세스에는 500개의 컨테이너 트레이스를 사용했다. 평가 결과, 컨테이너를 실행하는 동안 phase를 감지함으로써 리소스 프로비저닝을 동적으로 조정하여, 단순한 적응형 정책보다 더 나은 리소스 활용도를 달성할 수 있는 것으로 나타났다.

• Conditional Restricted Boltzmann Machine: CRBM 모델 훈련은 아키텍쳐와 숨겨진 유닛 수가 미리 정의된 일반 신경망 훈련과 유사하다. 
• Clustering Behaviors: 리소스의 사용 패턴을 sliding time window 단위로 클러스터링 함으로써 리소스 사용 패턴에 대한 유사성을 학습할 수 있다. 단순성을 위해 k-means를 사용하며, 본 논문에서는 k=5가 최적임을 확인했다.

• Phase Information: 각 execution에 대해 phase sequence를 생성하여, phase별로 리소스 사용의 추세와 다양한 변동성을 관찰했다. => 특히, 워밍업 단계의 리소스 사용량은 변동성이 높아 충분한 메트릭 데이터가 확보될 때까지 매커니즘이 패턴을 식별하기 어렵다.
  
  1. CPU와 메모리를 안정적으로 사용하는 단계
  2. 메모리 로딩 및 언로딩 단계
  3. 워밍 업 단계
  4. CPU 스파이크와 함께, 메모리 사용량이 점진적으로 증가하는 단계
  5. 메모리를 집중적으로 사용하지만, CPU 사용량이 가변적인 단계

4.2 Phase 기반 리소스 할당

• ground.truth: 모든 컨테이너의 실제 리소스 사용량
• current.step.max 및 current.step.rules(maximum 및 stat.rulesfor current.step): 오라클이 향후 기간의 리소스 사용량을 미리 알고 있는 경우, 적용할 두가지 리소스 할당 정책 => 선험적 지식에 의존하기 때문에 비실용적
  • current.step.max: 향후 최대 사용량에 따라 프로비저닝
  • current.step.rules: 평균 제곱 표준편차를 더한 값에 따라 프로비저닝
• prev.step.max 및 prev.step.rules: 이전 주기에서 관찰된 정보(사후 지식)을 사용하여 다음 주기를 프로비저닝 하며, 현재 패턴이 다음 자동 확장 주기에서도 계속될 것으로 예상한다.
• phase.rule: 프로비저닝 주기 직전의 단계를 감지하고, 해당 단계의 리소스 사용량 정보를 얻은 후, 다음 주기에 그에 따라 리소스를 프로비저닝

4.3 동작 예측 가능성

아래 그림과 같이, 확률 그래프에서 위상 시퀀스를 표현하기 위해 각각의 고유한 위상을 노드로, 위상 간의 전환을 전환 확률을 나타내는 속성을 가진 방향이 지정된 에지로 모델링한다.

Discussion

GPU도 사용하는 딥러닝 태스크겠지..? GPU도 함께 리소스 클러스터링을 하면 좋을 것 같다.

컨테이너에서 트레이스를 뽑는 방법에 대해 조금 더 조사해봐야겠다.

- https://github.com/amrabed/strace-docker

- Why strace doesn't work in Docker