공부 기록

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

Strace

리눅스에서는 시스템 콜 이벤트를 추적하고 기록하기 위해 strace 라는 툴을 제공한다.

strace [-ACdffhikqqrtttTvVwxxyyzZ] [-I n] [-b execve] [-e expr]... [-O overhead] [-S sortby] [-U columns] [-a column] [-o file] [-s strsize] [-X format] [-P path]... [-p pid]... [--seccomp-bpf] [--secontext[=format]] { -p pid | [-DDD] [-E var[=val]]... [-u username] command [args] }

strace -c [-dfwzZ] [-I n] [-b execve] [-e expr]... [-O overhead] [-S sortby] [-U columns] [-P path]... [-p pid]... [--seccomp-bpf] { -p pid | [-DDD] [-E var[=val]]... [-u username] command [args] }

strace는 지정된 명령어가 종료될 때까지 실행되며, 

프로세스가 호출하는 system call 과 프로세스가 수신하는 signal을 가로채서 기록한다.

• 트레이스의 각 줄에는 시스템 호출 이름(함수명)과 괄호 안의 argument 및 시스템 콜 실행 후의 반환값이 포함된다

open("/dev/null", O_RDONLY) = 3

• 오류가 발생하는 경우(일반적으로 반환값 -1)에는 errno symbol과 오류문자열이 기록된다

open("/foo/bar", O_RDONLY) = -1 ENOENT (No such file or directory)

• signal은 signal symbol 과 디코딩 된 siginfo 구조로 기록된다

sigsuspend([] <unfinished ...>
           --- SIGINT {si_signo=SIGINT, si_code=SI_USER, si_pid=...} ---
           +++ killed by SIGINT +++

• 만약 시스템 호출이 실행되는 동안 다른 스레드/프로세스에서 다른 호출이 실행되는 경우 이벤트 순서는 유지하되, 진행 중인 시스템 호출을 완료되지 않은 것으로 표시하고 호출이 반환되면 재개된 것으로 표시한다.

[pid 28772] select(4, [3], NULL, NULL, NULL <unfinished ...>
[pid 28779] clock_gettime(CLOCK_REALTIME, {tv_sec=1130322148, tv_nsec=3977000}) = 0
[pid 28772] <... select resumed> )      = 1 (in [3])

• 단, signal 전달에 의한 restartable 시스템 호출의 중단은 다르게 처리된다
  • 이 경우에는 커널이 시스템 호출을 종료하고, signal handler가 완료된 후 즉시 재실행되도록 준비된다

read(0, 0x7ffff72cf5cf, 1)              = ? ERESTARTSYS (To be restarted)
--- SIGALRM {si_signo=SIGALRM, si_code=SI_KERNEL} ---
rt_sigreturn({mask=[]})                 = 0
read(0, "", 1)                          = 0

• 알 수 없는 시스템 호출은 raw 상태로 기록되며, 알 수 없는 시스템 호출 번호는 16진수 형식으로 출력되며 앞에 syscall_ 접두사가 붙는다.

syscall_0xbad(0x1, 0x2, 0x3, 0x4, 0x5, 0x6) = -1 ENOSYS (Function not implemented)

options
-ttt: 절대 시간 기록, 마이크로 초 단위
-T: 시스템 호출에 소요된 시간, 각 시스템 호출의 시작과 끝 사이의 시간차를 기록, 디폴트는 마이크로 초 단위
-f: fork, vfork, clone 등의 시스템 콜의 결과로 현재 트레이싱 중인 프로세스에 의해 생성되는 자식 프로세스를 트레이싱한다. (만약 프로세스가 멀티스레드인 경우, 모든 스레드를 트레이싱)
-Z: 오류코드와 함께 반환된 시스템 콜만 기록
-z: 오류코드 없이 반환된 시스템 콜만 기록
-o: 트레이스 출력을 지정된 파일에 쓴다. 인수가 | 또는 !로 시작하면 나머지 인수는 커맨드로 취급되어, 모든 기록이 파이프로 전달된다. 이 옵션은 실행중인 프로그램의 리디렉션에 영향을 주지 않고, 디버깅 출력을 프로그램으로 파이프할 때 편하다.

Strace는 왜 컨테이너와 일반 프로세스에서 다르게 동작할까?

A containerized process uses system calls and needs permissions and privileges in just the same way that a regular process does. But containers give us some new ways to control how these permissions are assigned at runtime or during the container image build process, which will have a significant impact on security.

커널관점에서는 컨테이너 내에서 실행되는 프로세스 vs 호스트에서 실행되는 프로세스가 크게 다르지 않다.

결국 둘 다 단순히 생각하면 프로세스이고, 커널 영역을 공유한다. 따라서 syscall, kprobe, tracepoint 등의 커널 관련 이벤트로 프로세스를 트레이싱 하는 것은 동일 할 것이다.

따라서 strace로 컨테이너를 분석 할 때, 일반적으로 프로세스를 분석하는 것과 똑같이 하면 될 줄 알았다.

-rw-rw-r--  1 soyeon soyeon 1.8M  4월 27 16:13 squeezenet_docker.txt # 22091 lines
-rw-rw-r--  1 soyeon soyeon  19G  4월 27 10:51 squeezenet_real.txt # 223172114 lines

그런데 트레이스 사이즈가 너무 다르다;;

컨테이너와 호스트에서 실행되는 프로세스는 거의 비슷하지만,

사실은 컨테이너 워크로드에 자체 네임스페이스가 있어서 프로세스를 격리하게 된다.

즉, 컨테이너는 자체 루트 파일 시스템이 있고, binary/library는 서로 다른 mount namespace에 의해 격리된다

= 이벤트 추적 도구로부터 격리된다

그래서 트레이싱 툴이 작동할수도, 작동하지 않을수도 있다.

예를 들어 syncsnoop.bt는 잘 동작한다.

syncsnoop.bt
Attaching 7 probes...
Tracing sync syscalls... Hit Ctrl-C to end.
TIME      PID    COMM             EVENT
10:27:04  1229   auditd          tracepoint:syscalls:sys_enter_fsync
10:27:04  1229   auditd          tracepoint:syscalls:sys_enter_fsync
10:27:05  11459  fluent-bit       tracepoint:syscalls:sys_enter_fsync
10:27:05  11459  fluent-bit       tracepoint:syscalls:sys_enter_fsync
10:27:05  11459  fluent-bit       tracepoint:syscalls:sys_enter_fsync
10:27:05  11459  fluent-bit       tracepoint:syscalls:sys_enter_fsync
10:27:05  11459  fluent-bit       tracepoint:syscalls:sys_enter_fsync
.....

##################

cat /proc/1229/status | grep nspid -i
NSpid: 1229
cat /proc/11459/status | grep nspid -i
NSpid: 11459 1 # 기본 PID 네임스페이스: 11459, 자체 네임스페이스: 1

그런데 bpftrace 같은 경우에는 컨테이너 내부 바이너리 또는 .so 파일에 접근하여 uprobe를 주입할 수 없으므로 컨테이너 내부 애플리케이션은 제대로 된 트레이싱이 불가능하다.

• uprobe: 프로세스가 probe를 만났을 때 수행할 작업을 커널에 알려준다. probe는 파일과 연결되어 있으므로 해당 파일에서 코드를 실행하는 모든 프로세스에 영향을 미친다. 

// uprobe의 핵심 기능
#include <linux/uprobes.h>

int uprobe_register(struct inode *inode, loff_t offset, struct uprobe_consumer *uc);

//////////////////////////
    struct uprobe_consumer {
	int (*handler) (struct uprobe_consumer *self, struct pt_regs *regs);
	bool (*filter) (struct uprobe_consumer *self, struct task_struct *task);
	struct uprobe_consumer *next;
    };

strace도 비슷하다. 거기다가 도커는 seccomp-bpf을 사용하여 컨테이너 프로세스가 특정한 시스템 콜을 실행하지 못하도록 막는다. 

(기본 seccomp profile에서 허용되는 호출을 지정하는 허용 목록 작성)https://docs.docker.com/engine/security/seccomp/

그래서 만약 seccomp profile 옵션을 사용하지 않고 도커를 실행하고 싶다면 --security-opt seccomp=unconfined 을 도커를 실행할 때 추가해야한다.

근데 이렇게 하더라도 큰 변화는 없어서 더 찾아보니,,,

결론적으로 strace는 docker container의 동작을 빠짐없이 추적하기에는 적합하지 않은 도구였다.

strace는 프로그램이 실행하는 동안 호스트 운영 체제에 액세스하는 데 사용되는 시스템 콜을 추적할 수 있지만,

컨테이너가 호스트 운영 체제와 상호 작용하기 위해 사용하는 API 호출은 추적할 수 없다는 걸 알았다...

예를 들어,

- 컨테이너가 파일 시스템에 액세스하려면 open() 시스템 콜을 호출 -> strace 시스템 콜 추적 O

- 컨테이너가 Docker 네트워크를 통해 네트워크에 액세스할 때 docker_network_connect() API 호출 -> strace 시스템 콜 추적 X

strace는 API 호출을 추적할 수는 없다. (이러한 API 호출이 컨테이너의 네트워크 및 파일 시스템 드라이버에서 처리되기 때문)

네트워크 및 파일 시스템 드라이버는 컨테이너가 호스트 운영 체제와 상호 작용할 수 있도록 하는 소프트웨어인데,

strace는 드라이버가 호스트 운영 체제에 액세스하는 데 사용하는 시스템 콜을 추적할 수 있지만 드라이버 자체가 호스트 운영 체제에 액세스하는 방법은 추적할 수 없다.

💡 요약
- 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

💡 요약
- abstract: 대형 딥 뉴럴 네트워크 모델을 효율적으로 모델 병렬화 하는 방법에 관한 연구
- introduction: 큰 용량의 모델은 일반적으로 모델 병렬화하여 학습을 진행하는데, 범용적으로 효율적인 알고리즘을 적용하기 쉽지 않다는 문제가 있다.
- related works: 기존에 모델 병렬처리를 통해 네트워크를 서로 다른 계산 단위로 분할 후 이를 서로 다른 장치에 배치했는데, 낮은 하드웨어 활용률과 통신 병목 현상이 문제가 되었다. 이후, Single Program Multiple Data 및 파이프라인 병렬화가 제안되었는데, 병렬화된 각 행렬 곱셈의 결과값을 결합(AllReduce)하는데 사용되는 연산이 통신 오버헤드의 원인이 되었으며 특정 네트워크 아키텍쳐에 종속적이었다.
- method: Pipeline Model Parallelism(micro-batch) & Rematerialization
- experiment: 이미지 분류(AmoebaNet)과 기계번역(Transformer) 모델로 테스트 해 본 결과, Rematerialization 에 의해 단일 가속기에서도 메모리 요구량을 줄일 수 있었으며 모델 병렬화를 통해 모델을 확장할 수 있었다.
- conclusion & discussion: GPipe는 전체 미니 배치에 대해 단일 동기식 그라데이션 업데이트를 적용하기 전에, 마이크로 배치의 실행을 파이프라인화하는 Rematerialization과 결합한 새로운 파이프라인 병렬 처리를 도입했으며, 추가적인 통신 오버헤드가 없어 가속기 수에 따라 거의 선형적으로 확장할 수 있다. 단, 모델을 분할할 때 레이어의 파라미터가 불균형하게 분포하는 경우 가속기 수에 따라 완벽하게 선형 확장되지 않는다.

Introduction

딥 러닝이 발전하면서 모델의 파라미터 사이즈가 증가함에 따라 정확도가 비례하도록 개선되는 것을 관찰할 수 있었다.

하지만, 하드웨어적인 한계로 인해 큰 모델을 학습하는 것은 상당한 제약을 따른다. 

일반적으로 학습의 양이 많을 때, 분산 학습을 하게 되는데 두 가지 처리 방식이 있다.

• Model Parallelism: 모델의 자체의 크기가 커서 메모리가 부족할 때 사용한다. 각 디바이스는 모델의 일부분을 가지며, 결과값을 다른 디바이스에 넘겨주며 학습을 진행한다.
• Data Parallelism: 데이터 셋의 크기가 커서 메모리가 부족할때 주로 사용한다. 각 디바이스는 각각 전체 모델의 사본을 가지고 있으며, 분할된 데이터로 각자 학습 시킨 후 결과를 취합한다.

본 논문에서는 모델 병렬화에서 다루고 있는데 모델 병렬화는 효율적인 알고리즘을 구현하기 어렵고, 만약에 효율적인 알고리즘을 구현하더라도 특정 아키텍쳐나 태스크에 종속된다는 단점을 가진다. 또한, 예시 그림을 살펴보면 모델 병렬화는 데이터가 device1 -> (device2, device3) -> device4 으로 전달된다. 즉, 훈련 시 이전 레이어가 끝날때까지 기다려야 한다.

Method

GPipe는 각 레이어에서 일어나는 계산을 (1)파이프라이닝하여 병렬 처리하며, (2) Rematerialization을 활용하여 메모리 효율을 높인다.

## Pipeline Model Parallelism

모델 학습 시에는 각 레이어에서 forward propagation을 통해 loss를 계산하고, backward propagation에서 loss가 최소가 되도록 gradient를 구한다. 이 레이어를 각 디바이스에 나누면 그림 (b)와 같이 배치되는데, 앞쪽에서 결과값이 업데이트 될 때까지 기다려야하는 bubble time이 존재한다.

이 bubble time을 줄이기 위해서 본 논문에서는 그림 (c)와 같이 N개의 mini batch를 각각 M개의 동일한 micro batch로 나누어 학습을 진행한다. 그림 (c)를 보면 micro batch만 계산 후 결과값을 다음 레이어로 넘기기 때문에 다른 디바이스가 계산을 보다 빨리 시작할 수 있다. 

만약 네트워크에서 batch normalization이 이루어지는 경우, 각 계산은 micro-batch에 대한 통계를 사용하지만, evaluation을 위해 mini-batch 통계를 축적한다.. 그리고 장치 간 통신은 모든 micro-batch의 파티션 경계에서만 이루어진다. 이때, 디바이스간 데이터 전송 오버헤드가 있을 수 있지만, activation tensor만 전달하면 되기 때문에 통신 오버헤드는 무시할 수 있을만큼 작음을 관찰할 수 있었다.

bubble time은 O((K-1)/(M+K-1)) 으로 M>=4K일때 거의 무시할 수 있음을 실험을 통해 관찰할 수 있었다.

• K: partition 개수
• M: device 개수
• 이전 Layer의 계산이 끝날때까지 기다리지 않고도 backward pass 중 재 계산을 더 일찍 스케줄링 할 수 있기 때문

## Rematerialization

sequential layer 입력값을 제외하고 이후 back propagation에서 재사용 될 가능성이 있는 중간 계산 값들을 메모리에 store&load 하는 대신, 값을 일단 버리고 나중에 다시 필요할 때 재계산한다. 그 결과 메모리 요구량은 O(N*L) -> O(N+(L/K)*(N/M)) 으로 줄어든다.

• L: layer 갯수
• K: partition 갯수
• N: mini batch 갯수
• M: 디바이스 갯수
• N/M: micro batch 크기
• L/K: 파티션 당 레이어 수
• 메모리 요구량 = 그래디언트(bi)를 계산하는 데 상위 레이어 그래디언트(bi+1)와 캐시된 activation(fi(x))가 모두 필요

하지만 forward computation을 2번 계산 해야하기 때문에, 약 25% 정도 시간이 더 걸린다. 이 대기 시간을 더욱 줄이기 위해서 아래 그림과 같이 pipeline을 조정할 수 있다.

Experiment

• Naive-1: GPipe가 없는 sequential 한 버전
• Pipeline-k: k개의 가속기에 분할하여 학습
• AmoebaNet-D(L,D): cloud TPUv2s (8GB memory each)
  • L: 일반 셀 레이어 갯수
  • D: 필터 크기
  • 입력 이미지 크기 (224,224), 미니배치 크기 128
• Transformer-L: cloud TPUv3s (16GB memory each)
  • L개 layer, 각 레이어의 dimension 2048, feed-forward hidden dimensions 8192, attention heads 32 
  • 어휘 크기 32k, 시퀀스 길이 1024, 배치 크기 32

Rematerialization의 결과

- AmoebaNet: Gpipe는 back propagation과 batch splitting에 의해 중간에 계산되는 activation memory 요구량을 6.26GB->3.46GB(Peak Activation Memory)로 줄여 단일 가속기에서 318M 파라미터 모델을 구현할 수 있다.

- Transformer: 단일 가속기에서 2.7배 더 큰 모델을 훈련할 수 있다.

Model Parallelism의 결과

- AmoebaNet: 모델 병렬화를 통해 8개의 가속기에서 아메바넷을 18억개의 파라미터로 확장할 수 있었다. (약 25배)

- Transformer: 128개의 파티션으로 구성된 GPipe를 사용하면 839억개의 파라미터까지 확장할 수 있다 (약298배)

* AmoebaNet와 Transformer의 확장이 차이나는 이유는?

뉴럴 넷 모델의 경우 레이어마다 메모리 요구 사항 및 계산량이 불균형한 경우가 있는데, 이러한 경우에는 불완전한 파티셔닝 알고리즘으로 인해 부하 불균형이 발생할 수 있다. 표에서 살펴볼 수 있듯이, 마이크로 배치 수(K)가 많을수록 성능이 향상하며, 아메바넷은 모델 파라미터의 불균형한 분포로 인해 최대 모델 크기가 완벽하게 선형적으로 확장되지 않았다. 이는 아메바넷의 여러 레이어에 걸쳐 모델 파라미터가 불균형하게 분포되어 있기 때문이다. 트랜스포머 모델의 경우는 각 레이어의 파라미터 수와 입력 크기가 동일하기 때문에, 최대 모델 크기는 Transformer의 가속기 수에 따라 선형적으로 확장될 수 있었다.

이 표에서 관찰할 수 있는 것은, M이 상대적으로 작은 경우 대기 시간을 더 이상 무시할 수 없게 된다는 점이다. M=1이면 사실상 파이프라인 병렬화가 존재하지 않아 사용되는 가속기 수에 관계없이 비교적 일정한 처리량을 관찰할 수 있었다. (주어진 시간에 한 대의 장치만 계산=병렬화X)

Discussion

결론적으로 GPipe의 세 가지 핵심 속성은 아래와 같다

1) 효율성: 새로운 배치 분할 파이프라이닝 알고리즘을 사용하는 GPipe는 장치 수에 따라 거의 선형적인 속도 향상을 달성한다.

2) 유연성: GPipe는 모든 순차적 신경망을 지원한다.

3) 신뢰성: GPipe는 synchronous gradient descent을 활용하며, 파티션 수에 관계없이 일관된 훈련을 보장한다.

stochastic gradient descent - https://light-tree.tistory.com/133

RMSProp - https://box-world.tistory.com/69

카카오에서 TPU 대신 CUDA를 사용하는 pytorch용 gpipe를 구현해둔게 있어서 한번 보면 좋을 것 같음 - https://github.com/kakaobrain/torchgpipe

💡 요약
- abstract: "단일" 엣지 서버에서 애플리케이션의 실행 효율을 향상시키기 위한 연구
- introduction: 엣지 서버의 경우 리소스가 제한되어 있으며 다양한 물리 환경을 가지기 때문에 가벼운 컨테이너 가상화가 적합한데, 컨테이너 간 통신 및 데몬 프로세스에 의한 컨테이너 관리로 인해 상당한 CPU 리소스가 소모되는 문제가 있다.
- related work: 엣지 서버들과와 클라우드에서의 워크로드 스케줄링을 통해 태스크 실행 효율을 향상시키는 조사 & 베어메탈 기반 머신에서의 시나리오 조사 -> 단일 엣지 서버에서 컨테이너에 대한 효율 향상에 관한 연구는 없었음
- method: 공동 태스크 스케줄링 및 컨테이너화 기법을 제시
- experiment: 광범위한 시뮬레이션을 통해 평가한 결과, 비효율적인 컨테이너 운영을 줄이고 애플리케이션의 실행 효율을 60%까지 향상
- conclusion & discussion: JTSC 체계는 비효율적인 컨테이너 운영을 줄이고 다양한 요구사항을 충족하면서 애플리케이션의 실행 효율성을 향상시키는 것을 보였지만, 더 복잡한 시나리오에서 테스트 할 여지가 있다.

Introduction

엣지 서버의 경우 리소스가 제한되어 있으며 다양한 물리 환경을 가진다. 또한 지능형 교통, 비디오 분석, 증강 현실, 스마트 홈 등 다양한 애플리케이션을 지원하므로 소프트웨어 종속성 충돌을 피하기 위해 가상화가 좋은 방법이 될 수 있다. 

컨테이너는 가상화 기술의 한 종류로, 하나의 운영 체제 커널을 공유하면서 독립적인 파일 시스템과 환경을 갖는 프로세스를 격리하여 실행하는 기술이다. 이러한 컨테이너 기술을 엣지 환경에서 사용하는 경우,

• 경량화된 실행 환경: 컨테이너는 가상화 기술 중에서 가장 경량화된 기술이기 때문에, 엣지 디바이스와 같이 자원이 제한된 환경에서도 효율적으로 실행될 수 있다.
• 격리된 실행 환경: 컨테이너는 독립적인 파일 시스템과 환경을 갖기 때문에, 서로 다른 애플리케이션을 격리된 환경에서 실행할 수 있다. 이를 통해 애플리케이션 간의 상호작용을 방지하고, 보안성을 강화할 수 있다.
• 확장성: 컨테이너는 쉽게 생성, 복제, 이동, 삭제 등의 작업을 수행할 수 있기 때문에, 엣지 환경에서 애플리케이션을 확장하거나 축소하는 것이 용이하다.

가벼운 컨테이너 가상화를 통해 소프트웨어 의존성을 피할 수 있는는데, 컨테이너 간 통신 및 데몬 프로세스에 의한 컨테이너 관리로 인해 상당한 CPU 리소스가 소모되는 문제가 있다.

예비 실험을 통해 확인해 본 결과, (a) 컨테이너 간 통신의 경우 컨테이너 내 통신과 비슷한 전송 속도일때, CPU 사용률이 낮다. (b) 더 많은 태스크가 컨테이너에서 시작될 때, 데몬 프로세스가 더 많은 리소스를 소비한다.

컨테이너의 효율성을 개선하기 위해서는 두 가지가 있는데, 이 논문에서는 기존 컨테이너 시스템을 변경할 필요가 없는 후자의 방법을 택한다.

1. 커스터마이징 된 컨테이너를 통해 컨테이너 작업에 소모되는 CPU 리소스를 줄이는 방법

2. 비효율적인 컨테이너 작업의 사용량을 줄이는 방법

비효율적인 컨테이너 작업은 애플리케이션 작업의 스케줄링과 작업-컨테이너 간의 매핑 체계에 따라 달라지므로, 비효율적인 컨테이너 작업을 줄이기 위해서는 스케줄링과 컨테이너화를 함께 고려해야 한다.

예를 들어, 이미지 인식 애플리케이션 (a)는 (b)와 같은 다양한 작업으로 이루어져 있다. 각 작업을 컨테이너로 나눌 때, 오른쪽 방식이 왼쪽 방식에 비해 컨테이너 간 통신을 74%, 데몬 프로세스에서 사용하는 CPU 리소스를 29% 줄일 수 있다. 또한, 오른쪽 방식이 왼쪽 방식보다 작업 시간이 더 짧게 걸린다.

따라서 본 논문은 컨테이너 작업을 최적화 하기 위해 애플리케이션의 구성(태스크 간의 관계)을 나타내는 애플리케이션 모델을 구축하고, 태스크와 컨테이너에 의한 각각의 CPU 자원 사용률과 태스크의 실행 시간을 보여주는 실행 모델을 구축한다. 그리고 이러한 모델을 기반으로 공동 작업 스케줄링 및 컨테이너화(JTSC) 체계를 설계하고 있다.

논문이 기여한 바는 아래와 같다:

• 단일 엣지 서버에서 컨테이너 작업에 사용되는 CPU 리소스를 정량화하고, 작업 실행에 미치는 영향을 분석한다.
• 컨테이너화 프레임워크 및 알고리즘은 컨테이너화 체계와 작업 스케줄링을 결정함으로써, 컨테이너 작업량 및 애플리케이션의 실행 시간을 낮게 유지하도록 설계했다.

Backgrounds

2.1.1. 컨테이너

컨테이너와 가상 머신은 단일 리소스를 '가상화'하여 여러 리소스로 나타낼 수 있는 프로세스이다. 

가상 머신이 전체 머신을 하드웨어 계층까지 가상화하고, 컨테이너는 운영 체제 레벨 위의 소프트웨어 계층만 가상화한다.

따라서 컨테이너는 가상 머신에 비해 호스트와 OS 커널을 공유하기때문에 더 가볍다. 격리된 환경은 namespace와 cgroup이라는 두 가지 OS 매커니즘을 통해 제공된다.

• namespace: 호스트 이름과 도메인 이름, 파일 마운트 지점, 프로세스 간 통신(IPC) 관련 정보, 프로세스 ID(PID), 네트워크 스택, 사용자 등 서로 다른 컨테이너에 대한 리소스를 서로 격리된 상태로 유지한다.
• cgroup: 서로 다른 컨테이너의 프로세스에서 사용하는 시스템 리소스를 제한하고, 프로세스의 일시 중단/재개를 제어한다.

2.1.2. 데몬

데몬은 백그라운드 프로세스로 계속 실행되고, 종종 원격 프로세스에서 오는 주기적인 서비스 요청을 처리하기 위해 깨어나는 프로그램이다. 데몬 프로세스는 컨테이너의 시작 및 중지, 이미지 관리 등과 같은 컨테이너 관리 프레임워크에서 실행된다.

Containerd는 호스트에서 컨테이너의 수명 주기를 관리하는 컨테이너 런타임으로, 컨테이너를 생성, 시작, 중지 및 파괴한다. 또한 컨테이너 레지스트리에서 컨테이너 이미지를 가져오고, 스토리지를 마운트하고, 컨테이너에 대한 네트워킹을 활성화할 수 있다. Containerd 는 아래와 같이 구성되며, 각 구성 요소는 서로 협력하여 컨테이너 작업을 수행한다.

containerd는 대화식 사용자가 직접 제어하지 않고 백그라운드 프로세스로 실행되는 데몬으로, 위와 같은 작동 방식을 가진다.

2.1.3. 네트워크

서로 다른 컨테이너의 네임스페이스가 격리되어 있기 때문에, 공유 메모리를 통한 IPC는 서로 다른 컨테이너의 프로세스 간에 데이터를 전송하는 데 직접 사용할 수 없다. 따라서 Docker는 컨테이너 간 데이터 전송을 위해 서로 다른 네트워크 세그먼트를 연결하는 가상 스위치, 브리지를 사용한다.

데몬 프로세스가 초기화되면, 브리지 인스턴스가 시작되며, Veth(가상 이더넷)는 네임스페이스 사이의 터널 역할을 한다. Veth는 일반적으로 컨테이너에 하나, 브리지에 다른 하나 등 쌍으로 생성되는데, 그 결과 브리지와 연결된 Veth 디바이스가 있는 모든 컨테이너는 동일한 서브넷 내에 있게 되어 서로 데이터를 전송할 수 있게 된다. 이러한 브리지를 통한 데이터 전송은 데이터 패킹 및 언패킹 등의 절차가 필요하기 때문에 IPC에 비해 비효율적이라는 단점이 있다.

Preliminary Experiments

EXPERIMENTS ABOUT CONTAINER OPERATIONS

최신 컨테이너 관리 프레임워크 Docker와 일반적인 컴퓨팅 플랫폼인 X86 및 ARM 상에서 실험이 이루어졌다.

3.1. 컨테이너 간 통신

Netperf의 클라이언트와 서버를 두 개의 컨테이너(브리지를 통한 통신) 또는 동일한 컨테이너(IPC와 통신)에 배치하여 두 호스트간에 네트워크 대역폭을 측정한다. 클라이언트는 다양한 CPU 사용률(10~100%)을 가지며, 180초 동안 서버로 데이터 패킷을 계속 보낸다. 위 그래프에서 볼 수 있듯이, 브릿지 네트워크 또는 IPC의 전송 속도는 할당된 CPU 리소스에 따라 선형적으로 증가하며, 이는 전송 속도가 소모된 CPU 리소스의 양과 밀접하게 연관되어 있음을 나타낸다.

그리고 그림 5에 따르면, 네트워크 가상화 방식에 관계 없이, 데이터 전송 속도가 거의 동일한 것으로 나타났다.

3.2. 데몬 프로세스에 의한 컨테이너 관리

컨테이너 작업이 수행될 때 데몬 프로세스의 CPU 리소스 사용량을 기록하며 실험을 진행한다.

그림 6에서 볼 수 있듯이, 컨테이너 20개를 시작하기 위해 데몬 프로세스가 사용하는 CPU 리소스가 컨테이너 모니터링에 사용되는 리소스보다 훨씬 많다. 그 이유는 아래와 같다.

• 컨테이너 시작: 리소스 제한 설정, 네트워크 구성, 볼륨 마운트 등 많은 작업이 포함된다.
• 모니터링: 주기적으로 컨테이너의 상태만 확인하면 된다. 

위 예비 실험을 통해 컨테이너 간 통신이 컨테이너 내 통신보다 효율성이 떨어진다는 것을 알 수 있었다. 하지만, 서로 다른 컨테이너에 할당된 태스크 간의 데이터 전송을 위해서는 컨테이너 간 통신이 불가피하기 때문에 이러한 작업을 실행하는 경우, 데이터 전송 속도가 느려서 컨테이너가 없는 경우보다 실행 시간이 더 길어진다. 따라서 컨테이너화 방식을 신중하게 결정하여 컨테이너 간 통신량과 그에 따른 애플리케이션 실행 시간에 미치는 영향을 줄일 수 있도록 해야 한다.

컨테이너를 시작할 때 데몬 프로세스는 작업 실행을 위한 리소스를 선점하는 데 상당한 CPU 리소스를 소비하며, 애플리케이션의 총 컨테이너 시작 시간은 총 컨테이너 수와 각 컨테이너 시작 횟수라는 두 가지 요소에 따라 달라진다. 컨테이너 수는 컨테이너화 체계에 따라 결정되며, 컨테이너를 시작하는 횟수는 컨테이너에 있는 작업의 일정에 따라 달라진다. 따라서 컨테이너 애플리케이션을 최적화하기 위해서는 작업 스케줄링과 컨테이너화를 함께 고려하는 것이 필수적임을 알 수 있었다.

Methods

실험에 사용된 애플리케이션은 너무 단순하여 실제 애플리케이션을 대표하기에는 부족하기 때문에, 본 논문에서는 실험 결과를 일반적인 애플리케이션으로 확장하기 위해 애플리케이션 모델과 실행 모델이라는 두 가지 시스템 모델을 구축한다.

• 애플리케이션 모델: 일반적인 엣지 컴퓨팅 애플리케이션의 구성을 설명한다.
  • 일반적으로 애플리케이션은 표준 API로 연결된 여러 모듈로 구성되며, 이 모듈이 입력 데이터를 처리한 후 출력 데이터를 생성하는 과정을 태스크라고 한다. 태스크 간에는 종속성이 있으며, 고려해야 할 태스크 종속성에는 소프트웨어 종속성, 데이터 종속성, 커플링의 세 가지 유형이 있다.
    • 소프트웨어 종속성: 소프트웨어 구성 요소에 의존
    • 데이터 종속성: 한 작업이 다른 작업의 출력에 의존
    • 커플링: 전역 변수와 같은 공유 처리 구성 요소 등에 두 태스크가 상호 의존
  • 위 의존성에 기반하여, 결합 수준이 낮은 태스크는 태스크 오류의 영향 범위를 줄이기 위해 다른 컨테이너에 분산하는것이 좋으며, 의존성이 높은 태스크는 동일한 컨테이너에 실행하도록 한다.
• 실행 모델: 애플리케이션(태스크와 컨테이너 작업 모두 포함)의 CPU 리소스 사용률과 엣지 서버에서 태스크의 실행 시간을 나타낸다.
  • 실행중인 태스크의 라이프사이클은 크게 세 단계로 나눌 수 있다. 태스크가 blocked되면, 입력 데이터를 메모리에 캐싱하고 CPU 리소스를 사용하지 않는다. 태스크가 모든 데이터를 입력받고 난 후에는, 태스크는 다음에 실행될 수 있도록 스케줄링된다. 태스크가 완료되면, 출력 데이터는 즉시 하위 태스크로 전송되며, 데이터 전송 기간동안 CPU 리소스를 사용하게 된다. 
    • blocked: 일부 입력 데이터를 사용할 수 없거나 예약되지 않은 경우
    • running 
    • transmitting: 출력 데이터를 전송

즉, 비효율적인 작업의 양(상호 의존적인 작업)을 줄이고, 애플리케이션 실행 시간을 낮게 유지하기 위해 규칙을 설정한다.

• 컨테이너 간 통신은 비효율적이므로, 데이터 전송량이 많은 작업을 동일 컨테이너에 할당한다.
• 적절한 작업 스케줄링을 통해 컨테이너의 수를 줄임으로써, 컨테이너의 시작 횟수를 줄인다.
• 컨테이너 간 통신을 위해 두 태스크 사이에 CPU idle time을 활용한다.
  • idle time: 병렬 컴퓨팅에서는 1) 모든 상위 작업과 2) 동일한 프로세서에서 예약된 이전 작업이 완료되기 전에는 작업을 시작할 수 없기 때문에, 이 원칙에 따라 프로세서의 idle time이 존재한다. 이 idle time 동안 컨테이너 간 통신이 제대로 수행될 수 있다면 동일한 프로세서에서 후속 작업이 지연되지 않을 수 있다.
• 실행 기간에 큰 영향을 미치는 작업 중에는 컨테이너 간 통신을 피한다.

그리고 위 규칙을 따르는 공동 스케줄링 및 컨테이너화 체계를 제안한다. 

1. 먼저 할당된 프로세서에서 작업을 스케줄링하여 '초기 스케줄'을 얻는다.
   • 이 작업에서는 컨테이너 작업이 고려되지 않는다.
2. 비효율적인 작업을 줄이기 위해, 초기 스케줄을 기반으로 태스크를 컨테이너에 매핑한다.
   • 이 작업에서 컨테이너화 체계(태스크-컨테이너 간의 매핑)가 결정된다.
3. 컨테이너 간 통신으로 인해 작업의 실행 시간이 변경될 수 있으므로 초기 스케줄을 적용할 수 없다. 따라서 컨테이너화 체계에서 얻은 새로운 작업 실행 기간을 기반으로 작업 스케줄이 업데이트 된다.

Evaluation

본 논문에서는 실제 워크플로우를 사용하여 작업과 작업 간의 종속성으로 구성된 JTSC를 평가했다. 각 태스크는 데이터 처리를 위한 일정량의 CPU 리소스 계산량 대 컨테이너 간 통신 비율(0.1, 0.5, 1, 5, 10)을 가진다. 작업 간의 종속성은 행렬로 표현되었으며, 일부 요소는 종속성 충돌을 나타내기 위해 무한대로 설정되었다.

JTSC의 성능은 컨테이너 간 전송량, 컨테이너 시작 횟수, 특정 애플리케이션의 실행 기간, JTSC의 실행 시간 등 특정 메트릭을 기반으로 평가된다.

• CPF: critical path first algorithm
• STO: start timestamp order
• ICRO: Idle-time-to-communication ratio order algorithm
• Rand: randomly search for a feasible containerization scheme
• SFD: smallest ICP
• SFC: smallest CST
• SFE: smallest NED

본 논문에 따르면 컨테이너화 알고리즘마다 컨테이너 간 통신과 컨테이너 시작 횟수를 줄이는 측면에서 장단점이 있는 것으로 나타났다. 

• 통신 집약적인 작업에는 CPF와 ICRO가 더 나은 성능을 발휘한다.
• 컨테이너를 자주 시작하고 중지해야 하는 작업에는 STO가 더 나은 성능을 발휘한다.

서로 다른 성능을 강조하는 세 가지 컨테이너화 알고리즘이 포함된 JTSC 체계를 설계하여 애플리케이션의 작업 스케줄과 컨테이너화 체계를 결정했다. 그 결과 시뮬레이션을 통해 엣지 서버의 CPU 자원, 의존도 요구사항, 다양한 스케일의 애플리케이션, 다양한 초기 스케줄 등 다양한 조건에서 비효율적인 컨테이너 운영을 줄이고 애플리케이션의 실행 효율을 지속적으로 향상시킨다는 목표를 달성했다.

단, 본 논문에서 고려한 시나리오는 단일 엣지 서버에서 FaaS 애플리케이션만을 고려한 것이므로, 보다 복잡한 환경의 시나리오를 추가하는 것이 좋을 것으로 보인다. 예를 들어,

1) 이기종 연산 능력을 갖추고 무선 네트워크를 통해 연결된 여러 엣지 서버가 있는 엣지 컴퓨팅 시스템

2) 여러 애플리케이션을 동시에 고려

3) 작업의 워크플로우로 설명할 수 없는 애플리케이션 등

Discussion

애플리케이션의 워크플로우를 생성하는 것을 내가 직접 해서 연구에 적용해보기는 어려울 것 같다.

실험 방법 등이 좀 더 자세히 나왔으면 좋았을 것 같은데 조금 아쉽다.