Dynamic Virtual Machine Scheduling in Clouds for Architectural Shared Resources

💡 요약
- 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. 라이브 마이그레이션: 

Live Migration

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 정책에 비해 성능 향상이 일어났음을 확인할 수 있다.

클러스터에 4개의 애플리케이션 유형이 혼합된 워크로드의 성능과 각 애플리케이션 유형에 대해 8개의 VM 인스턴스

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

• 가장 좋은 경우(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 애플리케이션을 사용하여 제안한 스케줄러를 평가했다.

 

최악의 경우(W-W)에 비해 개선된 성능

• 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 라이브 마이그레이션이 마이크로 아키텍처 리소스 경합을 완화하는 데에도 사용될 수 있을 것이다.