CS Archive

Making Kernel Bypass Practical for the Cloud with Junction

Authors: Joshua Fried, Gohar Irfan Chaudhry, Enrique Saurez†, Esha Choukse†, Íñigo Goiri†, Sameh Elnikety‡, Rodrigo Fonseca†, Adam Belay

Groups: MIT CSAIL, Azure Research - Systems, Microsoft Research

Keywords: Kernel bypass system

#1 Motivations

1-1. Security

  클라우드의 인스턴스들은 악성 코드를 실행할 수 있기 때문에 커널과 인스턴스 간의 isolation이 중요하다. 버그는 주로 시스템 콜이나 VM exit과 같은 동작을 통해서 호스트 커널에 접근한다. 현대의 커널은 광범위한 공격 표면을 가지고 있으며, 수백만 줄의 코드를 실행할 수 있고, 일시적 실행 공격이 코드에 취약점을 노출할 수 있다. 이는 클라우든 개발자에게 보안 위험성을 제시한다.

  현대의 Kernel bypass system은 보통 isolation을 지원하지 않고 root로 실행되어야 한다. 따라서 클라우드에서 isolation을 적용하기 위해서는 가상 머신과 같은 다른 메커니즘에 의존하게 된다. 하지만 이러한 방법은 TLB 미스, VM 비용, 게스트 커널에 의한 메모리 비용과 같은 오버헤드를 증가시킨다.

1-2. Density

 기존 커널 바이패스 시스템은 spinning core 및 dedicated core를 사용하기 때문에 제한된 수의 인스턴스만 제공한다. 코어 할당 속도를 증가시킨 새로운 방식의 ÇPU 스케줄링 기법을 사용하는 Caladan과 같은 state-of-art는 tail latency를 소모하는 busy spinning 문제를 해결하였으나 여전히 scheduling core가 dedicated core에 귀속된다는 문제가 있다.

  현대의 NIC은 수천 개의 큐를 관리할 수 있지만, 하나의 머신에서 많은 인스턴스를 실행시키기 위해 수천 개의 큐를 사용하는 것은 여전히 어려운 일이다. 각 수신 큐가 worst-case burst 상황에서 패킷을 모두 수신할 수 있을만큼의 충분한 버퍼를 할당해야 한다. 따라서 고정된 버퍼 메모리는 density에 안 좋은 영향을 미칠 수 있다. 

1-3. Compatibility

  기존 커널 바이패스 시스템은 개발자에게 응용의 수정을 요구한다. 따라서 state-of-art kernel bypass system (eRPC, Demikernel, Caladan)은 C 또는 C++로 구현된 비교적 간단한 응용만 지원하며, 실제 serverless function으로 자주 사용되는 Node나 Python과 같은 언어는 복잡한 OS dependency와 언어 라이브러리가 필요하다는 점에서 차이가 크다.

#2 Junction 

  Junction은 하나의 머신에서 몇 천개의 인스턴스를 처리할 수 있는 것을 목표로 설계되었다. 인스턴스는 하나의 isolated 컨테이너로 하나 또는 여러 어플리케이션의 바이너리를 실행하며, 호스트의 커널 입장에서 컨테이너는 고정된 개수의 kThread로 이루어진 싱글 프로세스(kProc)이다. 스레드는 중앙 스케줄러에 의해 스케줄링 되며, 인스턴스는 공유 주소 공간을 통해 여러 바이너리를 실행할 수 있다. 인스턴스의 바이너리들은 사용자 공간 프로세스 추상화인 uProc를 통해 실행된다.

  Junction 커널은 각 컨테이너 내부에서 호스트 커널과 별개로 복사본이 동작하며, uProc와 주소 공간을 공유한다. Junction 커널은 응용의 시스템 콜을 처리하고, kernel bypass hardware를 사용하여 OS 추상화(스레딩, 네트워킹, 파일 시스템, 시그널 등)을 user-level에서 제공한다. Junction 커널은 Linux의 시스템 콜 인터페이스를 제공하기 때문에 코드 수정이 필요없다. OS 함수를 사용자 공간으로 옮기는 것은 컨텍스트 스위치에 대한 오버헤드 감소로 인하여 성능 향상으로 이어지며, 신뢰할 수 없는 프로그램이 호스트 커널 코드의 작은 부분에만 접근 가능하기 때문에 보안에도 좋다.

• Networking and Communication

  기존 커널 바이패스 시스템처럼 Junction 인스턴스는 스레드 당 하나의 NIC send/recv queue pair가 제공된다. 이는 동시성 제어 없이도 NIC에게 동시 접근을 가능하게 하기 때문에 성능 향상으로 이어진다. Junction 커널은 고성능 TCP/IP와 UDP 네트워크 스택을 제공한다. 같은 인스턴스 내의 응용들은 표준 IPC 프리미티브를 사용하여 소통하고, 같은 호스트 내 다른 인스턴스에 존재하는 응용들은 NIC을 통해 loopback 네트워킹을 사용하여 소통한다.

• Threading

  Junction 커널은 uThread와 kThread 간의 균형을 맞추기 위해 work stealing 기법을 사용하는 고성능 사용자 공간 스레딩 라이브러리를 제공한다. uThread는 응용의 스레드로 사용되며, 네트워크 프로토콜 프로세싱과 같은 작업에도 사용한다. kThread는 패킷이나 타임아웃과 같은 로컬 큐를 폴링하는 스케줄링이나 uThread를 폴링하는 동작을 수행한다.

• Core Scheduling

  스케줄러는 dedicated core에서 동작하며, 각 인스턴스에 언제 어떻게 코어를 할당할지를 결정하는 제어 신호를 폴링하는 마이크로커널 방식으로 운영된다. 인스턴스가 유휴 상태일 때는 코어를 사용하지 않다가, 작업량이 증가하면 필요에 따라 하나 이상의 코어를 할당된 코어 내에서 사용한다. 스케줄러는 공유 메모리를 통해 각 인스턴스의 스레드와 네트워크 큐의 타이머 및 큐잉 딜레이를 모니터링 하며, 코어를 할당할 때는 유휴 상태의 kThread를 선택하여 해당 인스턴스에 고정시킨다.

  스케줄러는 특정 코어에서 실행 중인 uThread가 할당된 시간을 초과하였을 때 사용자 인터럽트(UIPI)를 보내어 스레딩 라이브러리의 fine-grained time slicing을 구현한다. 이는 uThread가 패킷을 시간 순서로 처리할 수 있게 보장하며, 서비스 시간의 분산이 큰 경우 tail latency를 줄이는 데 도움을 준다. 최적화를 위해 인터럽트는 대기 중인 패킷이나 실행 가능한 스레드가 있을 때만 전송된다.

2-1. Security

  기존의 커널 바이패스 시스템들은 호스트 커널과 응용의 분리를 위해 가상 머신을 사용하였으나 가상화 기법은 여전히 호스트 커널의 많은 부분을 사용하고 있다. Junction은 Junction 커널 복사본을 각 인스턴스에서 실행하여 버그 노출의 위험성을 인스턴스 내부로 최소화 하였으며, kernel bypass hardware를 통해 제공하여 커널 의존성을 최소화 하였다.

• Isolation mechanisms: 리눅스 프로세스인 kProc를 통해 isolation을 제공하며, seccomp을 이용하여 시스템 콜을 제한한다. 

• Allowed system calls: Junction은 아래의 11개 system call을 호출한다.

• Page cache: Juction은 초기에 공격 표면을 최소화하기 위해 인메모리 파일 시스템이나 네트워크 파일 시스템을 사용하여 인스턴스가 커널 파일 시스템에 접근하지 못 하도록 하는 것을 고려하였다. 하지만 서로 다른 프로세스들이 같은 디스크 블록에 동시 접근이 가능하도록 하는 페이지 캐시 접근 제어를 할 수 있는 계층이 호스트 커널 밖에 없어 density를 달성하기 위해 제한적인 접근을 허용하였다. 

2-2. Density 

  Junction은 높은 네트워크 처리량과 낮은 지연 시간을 제공하면서 하나의 머신에서 여러 인스턴스를 실행할 수 있도록 하는 것을 목표로 한다. 하지만 이는 하나의 머신에서 여러 인스턴스가 많은 수의 NIC 수신 큐를 사용하여 발생하는 문제 (버퍼 메모리 소모, 스케줄링 오버헤드)를 해결해야 한다.

• Minimizing Buffer Memory Consumption

  기존 커널 바이패스 시스템은 패킷을 수신하기 위해 큰 메모리 풀을 할당하여 관리한다. 이 메모리 풀은 NIC이 직접 접근이 가능하기 때문에 커널의 스왑을 방지하기 위해 고정되어야 한다. 패킷 버퍼의 사이즈는 패킷 드랍을 방지하기 위해 연결의 수나 딜레이, RTT와 같은 요소를 고려하여 사이즈를 정하며, 각 수신 큐는 해당 사이즈 만큼의 버퍼를 보유하여야 한다. 또한 가변적인 패킷 사이즈를 지원하기 위해 버퍼의 사이즈는 MTU 크기인데, 이는 작은 패킷의 경우에 프래그멘테이션을 초래한다.

  Junction은 다음과 같은 방법으로 두 문제를 해결하였다. 첫번째로 인스턴스의 공유 버퍼 큐를 사용하여 각 수신 큐마다 패킷 버퍼를 따로 등록하지 않도록 하여 메모리 소모를 감소시켰다. 두번째로 패킷을 버퍼 내에 연속적으로 위치하도록 하여 프레그멘테이션을 방지하고, 작은 패킷의 메모리 소모를 MTU에서 256B로 줄였다.

• Scalable Queue Polling

 기존 커널 바이패스 시스템은 스케줄러가 각 인스턴스의 수신 큐의 큐잉 딜레이와 스레드 런큐, 타이머를 모니터링 하여 코어 재할당 메커니즘을 수행한다. Junction이 목표하는 많은 인스턴스가 존재하는 상황에서 모든 인스턴스를 모니터링 하는 것은 오버헤드가 너무 크고 스케줄러의 캐시 오염이 발생하기 때문에 폴링하는 메커니즘의 최적화가 필요하다. Junction은 스케줄러가 유휴 인스턴스는 폴링하지 않으면서 타이머와 네트워크 패킷 수신 큐를 확인할 수 있도록 하는 방식으로 최적화하고자 한다.

  Junction은 NIC feature를 이용하여 유휴 인스턴스를 폴링하지 않고도 패킷 수신을 확인할 수 있도록 하였다. 이를 위해 이벤트 큐와 전용 도어벨을 할당하여 스케줄러가 유휴 수신 큐를 확인할 때마다 현재 헤드 포인터 인덱스를 표시하고 도어벨에 기록함으로써 이벤트 큐를 활성화한다. 활성화 된 이벤트 큐에 패킷이 도착하였을 때 NIC은 이벤트 큐에 직접 이벤트를 기록하고 큐를 비활성화 시킨다. 이러한 방식으로 스케줄러는 유휴 수신 큐에 패킷이 도착하였을 때 즉각적으로 반응할 수 있게 된다. 이 NIC feature 기능은 Mellanox NIC에서만 지원하는 단점이 있다.

  타이머는 TCP 세그먼트가 재전송이나 RPC 실패를 감지하는 역할을 하기 때문에 데이터 센터 워크로드에 매우 중요하다. 인스턴스가 최소한의 딜레이로 활성화되는 것을 보장하기 위해 Junction의 스케줄러는 16us 레벨의 timer wheel을 구현하였다. Timer wheel은 스케줄러가 만료될 타이머의 인스턴스를 무시할 수 있도록 하여 활성화 된 인스턴스만 모니터링 할 수 있도록 한다.

  추가적으로 스케줄러가 사용하는 구조체를 최적화 하여 인스턴스가 최소한의 캐시 라인만 사용하도록 하며, 활성화 인스턴스가 필요한 상태와 유휴 인스턴스가 필요한 상태를 분리하여 false sharing을 방지하였다. 이런 최적화들은 중앙 스케줄러가 가지는 확장성 병목을 극복하고 스케줄러가 몇 천 개의 인스턴스를 지연 시간 이슈 없이 관리할 수 있도록 한다.

2-3. Compatibility

  Junction에 의하면 다양한 응용을 실행할 수 있도록 리눅스 인터페이스를 충분히 구현한 팀의 수가 아주 적다고 한다. 따라서 클라우드 응용들은 특정 런타임에 의존하여 동작하며 시스템 콜을 직접적으로 사용하지는 않는다. 따라서 Junction에서는 런타임이 호출하는 시스템 콜을 구현하여 런타임 위에 동작하는 클라우드 응용들을 수정 없이도 실행할 수 있도록 하는 것을 목표로 한다.

• Adpating OS Features to Kernel Bypass

  Junction 커널은 인스턴스 내에 ELF 로더를 포함하여 시작 시 자동으로 첫 번째 uProc를 로드하며, 시스템 콜을 통해 추가 uProc를 로드 할 수 있다. 하지만 Junction은 인스턴스 내의 주소 공간만 사용하는 단일 주소 공간 OS이므로 새로운 uProc를 생성하기 위해 fork()를 사용할 수 없기 때문에 대신 vfork()를 사용한다. vfork()는 새로운 주소 공간의 생성을 execve()가 호출될 때까지 지연시키는 fork()의 최적화된 버전이다. Junction은 vfork() + execve() 시퀀스를 가로채어, 새로운 주소 공간을 생성하는 대신 기존 주소 공간에서 빈 위치를 찾아 프로그램 이미지을 로드하여 하나의 인스턴스에서 여러 uProc를 지원할 수 있게 된다.

  Threading. 최근 user-level 스레딩이 성능 향상으로 인해 주목 받고 있다. Junction은 호스트 커널을 경유하지 않고 스레딩 작업을 사용자 영역으로 이동함으로써 기존 바이너리에게 성능 향상을 제공한다. Junction은 각 kThread 마다 별도의 uThread 실행 큐를 유지하고, 패킷 도착, 타임아웃, 시그널 및 기타 이벤트를 이용하여 uThread를 깨운다. 이를 구현하기 위해 Jucnction은 glibc 라이브러리를 일부 수정하여 스레딩 라이브러리를 사용자 공간에서 구현하였다.

  Signals. UIPI로 사용자 영역에서 신호 처리

• Performance Optimizations

  Junction은 응용이 로드되면, ELF 로더를 glibc로 대체한다. 모든 시스템 콜은 glibc를 통해 실행되기 때문에 이 방식은 효율적이다. 수정된 라이브러리는 시스템 콜이 발생하면 Junction을 호출한다.

  이 방식의 핵심은 각 시스템 콜이 함수 호출처럼 취급된다는 것이다. 이것은 성능 상에서 효율적이다. 결과적으로 리눅스 커널과 다르게, Junction 커널은 최적화되어 컴파일 된다. 이것은 ...

A Cache-Coherent Interface to the NIC

Authors: Henry N.Schuh, Henry M.Levy, Arvind Krishnamurthy, Luigi Rizzo, Brent E.stephens, David Culler, Samira Khan 

Groups: Google, Uni of Washington, Uni of Virginia, Uni of Utah

Keywords: PCIe, NIC, Interface, Cache-Coherent

#1 Motivations

1-1. PCIe overheads

  호스트는 디바이스의 메모리에 직접적으로 read/write 연산을 수행하기 위해 일반적으로 MMIO를 이용한다. MMIO를 이용할 때에는 보통 uncacheable(UC) 또는 write-combining(WC) 메모리 타입을 이용하여 데이터를 전달한다. UC와 WC 메모리는 모두 캐싱이 불가능하기 때문에 MMIO read/write 연산은 PCIe 트랜잭션을 기다려야 하고, 이는 높은 지연시간을 발생시킨다. 또한 MMIO load 같은 연산에서 발생하는 PCIe 폴링 CPU 연산은 오버헤드가 크다.

  단방향 소통이 가능한 MMIO store는 연속된 데이터에 대한 요청을 하나씩 처리하기 때문에 처리량 저하가 너무 크다. 이는 WC 사이즈에 따른 처리량 변화를 통해 확인할 수 있다. 이를 확인하기 위해 논문에서는 WC MMIO와 WC-mapped local DRAM, write-back DRAM의 성능을 비교하였다. WC data path는 4KB 이상의 크기에서 캐싱과 유사한 처리량을 보여주었다. 

  지연시간 측면에서도 WC의 제한된 사이즈에 의한 오버헤드가 발생한다. WC가 가득 찬 상황에서 새로운 store 연산을 요청하려면, 요청은 WC의 플러시를 기다려야 한다. WC 플러시 오버헤드를 측정하기 위해 논문에서는 n개의 store에 연산에 대한 latency를 측정하였다. 실험의 결과를 보면 24개의 store를 수행하기 전까지는 지연 시간이 0과 가깝지만, 그 이후부터는 연산이 많아지는 만큼 오버헤드가 늘어난다.

  정리하면 PCIe 통신의 오버헤드는 다음과 같다.

• PCIe는 cache-coherent interconnect가 아니기 때문에 일관성을 유지하기 위해 PCIe 트랜잭션이 필요하다.
• PCIe 연산의 높은 지연시간 때문에 연산 횟수를 줄이는 것이 저지연 패킷 통신에 중요하다.
• PCIe를 통해 데이터와 메타데이터를 전달하는 것은 CPU의 관점에서 오버헤드가 크다.

1-2. PCIe NIC Interface Design

  PCIe 오버헤드로 인해 PCIe 인터페이스는 아래와 같은 설계를 통해 지연 시간을 희생하면서 CPU 효율성과 처리량을 우선시한다.

• CPU 오버헤드를 줄이기 위해 패킷 버퍼와 디스크립터를 로컬 메모리에 유지하고 패킷 송수신은 PCIe를 통해 NIC으로 전달
• 디스크립터를 배칭을 통해 전달하여 지연시간은 높지만 CPU 효율성을 증가
• 동기화가 보장되지 않는 PCIe 버퍼 동기화를 호스트가 관리

#2 CC-NIC

2-1. Coherent interconnects

  UPI나 CXL 같은 coherent interconnect들은 CPU의 메모리 데이터패스와 긴밀하게 융합되어 있는데, 이들은 주로 DRAM와 캐시들의 접근을 다룬다. 캐시 일관성 프로토콜은 메모리에 접근할 때 캐시 라인을 캐시에 전송하고, 캐시 간의 공유 상태를 관리하는 역할을 한다. 프로토콜은 writer가 write 전 캐시에 대한 제어를 얻어 원격 캐시에 대한 복사를 방지한다. 그리고 여러 캐시에 reader의 접근을 공유하고 캐시 라인은 캐시 간에 공유된다. 

  캐시 일관성 추상화는 PCIe read/write 인터페이스의 제한과 상관없이 새로운 형태의 시그널과 데이터 구조를 공유한다. 프로토콜은 PCIe MMIO와 다르게 메모리 데이터 패스와 캐시 계층을 합치고, MMIO와 DMA의 트레이드오프를 피하는 인터페이스를 제공한다. 하지만 캐시 간의 데이터 전송은 여러 가지 요소에 의해 영향을 받는다. 이러한 요소는 데이터 전송에 소요되는 시간뿐만 아니라 메모리 컨트롤러와의 통신, 프로토콜에서 사용되는 부가적인 메타데이터의 처리 등이 있다. 또한, 캐시 라인의 상태와 전반적인 캐싱 동작을 조작하는 데는 제한적인 수단이 있으며, 이러한 제한적인 조작은 캐시 일관성 및 전송 성능에 영향을 줄 수 있다.

2-2. Metadata structures

• How can we take advantage of cache coherence to reduce software overhead?

    캐시 일관성 프로토콜은 기존 하드웨어 메커니즘과 다르게 캐시의 상태를 바꿈으로써 시그널을 전달할 수 있다. 이것은 헤드테일 인덱스 레지스터를 이용하는 오버헤드를 제거할 수 있다. 따라서 CC-NIC은 디스크립터 내에 inlined signal 플래그를 둠으로써 신호를 전달한다. 이는 소켓 캐시 간의 캐시 라인을 전송하는 지연 시간을 제거한다.

• What is the ideal data path for metadata transfer?

메모리 각 계층에서 캐시 일관성 프로토콜을 사용하였을 때의 지연시간을 측정한 결과는 아래 그림과 같다. 로컬 메모리 접근 지연시간에 비해 원격 메모리에 접근하는 지연 시간이 2배 정도 오래 걸리며, homed on local memory가 home on remote memory보다 조금 더 높은 지연시간을 보인다.

  CC-NIC은 이러한 특징을 이용하여 TX 디스크립터 링은 host-homed이고, RX 디스크립터 링은 NIC-home로 유지하는 방식으로 metadata structure를 write-home memory에 위치시킨다. 

• How does memory layout affect metadata?

  asdasd

• How do we optimize for both latency-sensitive and high-bandwidth regimes?

  인라인 시그널을 통해 호스트와 NIC은 디스크립터 링 메모리를 직접적으로 폴링 할 수 있다. 하지만 이는 디스크립터가 64B 캐시라인보다 작기 때문에 64B 캐시라인 단위로 디스크립터를 읽는 오버헤드가 발생한다. 따라서 이를 해결하기 위해 CC-NIC은 16B 디스크립터를 4개씩 캐시 라인으로 구현함으로써 지연시간과 대역폭 오버헤드를 해결하였다.

2-3. Data accesses

• How should we write packet data?

  패킷을 캐시에 쓸 때와 DRAM에 쓸 때의 성능을 비교하기 위해 streaming write microbenchmark를 수행하였다. 실험은 패킷을 캐시에 쓴 후 1MB씩 reader가 인라인 시그널을 통해 패킷을 처리하는 것과 DRAM에 쓴 후 1MB씩 처리하였을 때의 처리량을 비교하였다. 아래 그림에서 알 수 있다시피 결과는 캐시에 쓰는 것이 DRAM보다 성능이 좋았기 때문에 CC-NIC에서는 캐시에 패킷 데이터를 쓴다.

• How can we minimize coherence protocol overhead for data transfer?

  asdf

• Where shold data be homed?

  asdf

• How can we maximize cache locality for packets?

  asdf

2-4. Buffer management

  asdasd

내용 추가 예정

Reconfiguring RDMA-based Memory Disggregation via CXL

Authors: Zhonghua Wang, Yixing Guo, Kai Lu, Jiguang Wan, Daohui Wang, Ting Yao, Huatao Wu

Groups: Huazhong University, Huawei Cloud

Keywords: Memory Disaggregation, RDMA, CXL

#1 Motivations

1-1. RDMA-based memory disaggregation

  데이터를 관리하는 기법에 따라 RDMA 기반의 메모리 분리는 두 종류로 나뉜다. 페이지 기반의 기법에서는 가상 메모리 메커니즘을 이용하여 페이지 폴트가 발생하였을 때 로컬 메모리와 원격 메모리 페이지를 스와핑함으로써 원격 메모리 상의 페이지를 로컬 메모리로 캐싱한다. 이 방법은 응용의 수정 없이 적용이 가능하다는 장점이 있다. 오브젝트 기반의 기법에서는 메모리 관리를 조금 더 세밀한 단위(객체)로 하며 객체의 시맨틱을 이용하여 컴퓨팅 리소스를 최적화 한다. 하지만 RDMA 기법은 다음과 같은 단점들이 있다.

• High latency: 로컬 메모리와 비교하여 20배 이상 느린 지연시간을 제공한다.
• High overhead: 페이지 기반서는 페이지 폴트 오버헤드를 동반하고, 오브젝트 기반에서는 코드 수정이 필요하다는 단점이 있다.

1-2. CXL-based memory disaggregation

  CXL 기반의 메모리 분리는 캐시 일관성을 보장하는 공유 메모리 풀을 제공하며, 캐시 라인 접근이 가능하게 한다. 이는 응용의 수정이 필요 없으며 낮은 지연시간과 좋은 확장성을 보인다. 그러나 CXL 기반의 메모리 분리는 다음과 같은 단점을 가진다.

• Physical distance limitation: CXL 디바이스는 PCIe를 기반으로 하기 때문에 랙 레벨에서의 결합으로 제한되며, 이는 대규모 데이터센터에 바로 적용되기 어렵다.

1-3. Hybrid memory disaggregation

  따라서 논문에서는 CXL의 물리적 한계를 보완하고 RDMA의 높은 지연시산과 오버헤드를 보완하기 위해 RDMA와 CXL 기법을 결합하여 하이브리드로 동작하는 새로운 기법을 제안한다. 로컬 랙에서는 CXL의 장점을 이용하여 낮은 지연시간을 보이며, 서로 다른 랙을 RDMA를 통해 연결하여 확장성을 보장한다. 

#2 Design

2-1. Archtiecture

  Rcmp 랙은 응용을 위한 여러 개의 컴퓨팅 노드와 CXL, 컴퓨팅 노드의 요청을 처리하기 위한 데몬으로 이루어져 있다. 메모리 노드를 두지 않고 데몬을 통해 요청을 처리하는 구조는 컴퓨팅 노드와 메모리 노드가 분리된 구조에서 발생하는 메모리 일관성을 유지 오버헤드를 없애는 장점이 있다. 그리고 컴퓨팅 노드의 요청에서 발생하는 블로킹을 없애기 동적으로 데몬의 수를 늘릴 수 있다. 랙의 컴퓨팅 노드는 CXL을 통해 메모리 풀을 할당하고, 서로 다른 랙의 컴퓨팅 노드들은 RDMA를 통해 연결된다. 

  Rcmp는 서로 다른 랙에 존재하는 메모리들을 관리하기 위해 전역 메모리 주소를 사용하며, Metadata Server(MS)를 통해 전역 주소 할당 및 메타데이터 관리를 수행한다. MS는 페이지 단위로 메모리를 할당하며, 전역 주소는 페이지의 id와 CXL 메모리의 페이지 오프셋으로 이루어져 있다. Rcmp는 2개의 해시 테이블을 이용하여 주소 매핑을 관리한다. MS의 page directory는 페이지 id와 랙 id의 매핑을 관리하고, 데몬의 page table은 페이지 id와 페이지 오프셋의 매핑을 관리한다. 메모리 공간은 크게 3가지로 CXL 메모리와 컴퓨팅 노드의 로컬 메모리, 데몬으로 다음과 같은 역할을 한다.

• CN: Local page hotness와 local page table 메타데이터를 캐싱
• Daemon: Local page table과 원격 메모리의 hotness를 저장, MS의 page directory와 remote page table을 캐싱
• CXL: 큰 캐시 일관성 보장 공유 메모리 공간과 컴퓨팅 노드에게 제공되는 메모리 공간

2-2. Workflow

  컴퓨팅 노드의 응용이 메모리 풀에 접근하는 것은 다음의 플로우를 따른다. 

1. 페이지가 로컬 메모리의 page table에서 발견된다면, load/store 명령어를 통해 CXL 메모리 페이지에 직접 접근 
2. 로컬 메모리에서 페이지를 찾지 못 하면, MS의 page directory를 참조하여 페이지가 존재하는 랙을 조회 
3. 페이지가 로컬 랙에 존재하면, 로컬 데몬의 page table을 통해 해당 페이지의 오프셋을 얻은 후 CXL 메모리 노드에 접근 
4. 페이지가 원격 랙에 존재하면, 원격 데몬에게 요청하여 원격 page table을 통해 해당 페이지의 오프셋을 얻어 RDMA를 통해 CXL 메모리 페이지에 접근 (이때 접근하는 페이지가 hot page인 경우, 스왑 메커니즘을 트리거)

#3 Rcmp

  데몬은 랙의 중앙화된 관리 노드로 CXL 및 RDMA 요청 뿐만 아니라 페이지 스와핑, 슬랩 할당 관리, CXL 메모리를 관리하는 역할을 한다. 데몬은 각 랙에 하나 이상 실행되며 컴퓨팅 노드와 같이 취급된다. 또한 Rcmp의 모든 컴포넌트는 user-level에서 구현되어 컨텍스트 스위치 오버헤드가 없다.

3-1. Intra-rack communication

  로컬 랙과 원격 랙에 접근하는 지연 시간의 차이가 커, 블로킹으로 인한 성능 하락을 초래할 수 있다. 이를 해결하기 위해 Rcmp는 각각의 상황에 맞추어 두 가지 링버퍼를 사용한다. 로컬 랙의 접근을 관리하기 위한 링버퍼는 CXL에 접근하는 지연 시간은 매우 짧아 블로킹이 발생하지 않기 때문에 일반적인 링버퍼를 사용한다. 따라서 컴퓨팅 노드의 모든 스레드가 공유하는 하나의 링버퍼를 유지한다.

  원격 랙에 접근하기 위한 링 버퍼는 동시성 보장을 위해 두 개의 링버퍼로 이루어져 있다. 첫 번째 링버퍼는 폴링을 위한 링버퍼로 메시지 메타데이터와 메시지 데이터를 보관하는 두 번째 링버퍼를 가리키는 포인터를 저장한다. 폴링 버퍼의 데이터는 고정된 크기의 데이터 규격을 가지며, 데이터 버퍼의 요청이 하나 완료되면 하나의 폴링 버퍼 요청을 추가할 수 있다. 그리고 데몬은 메시지를 처리하기 위해 폴링 버퍼를 폴링 한다. 폴링 버퍼는 lock-free KFIFO 큐를 이용하여 구현하였으며, 데이터 버퍼는 일반적인 링버퍼를 통해 구현하였다.

3-2. Hot-page identification and Swapping

  Rcmp는 원격 랙 접근 오버헤드를 줄이기 위해, hot page를 로컬에 위치시키려 한다.

• Hot-page identification

  Rcmp는 read/write 연산의 횟수, last time 세 가지 팩터로 hotness를 측정한다. 먼저 페이지에 접근할 때 Δt를 측정하는데, 이는 현재 시간으로부터 마지막으로 read 연산을 수행한 시간을 뺀 것이다. 만약 Δt가 valid lifetime threshold T를 넘어가면, 해당 페이지에 대한 hotness는 만료되고 현재 read/write 연산의 횟수가 0으로 초기화된다. 페이지의 hotness는 아래의 공식을 통해 계산한다. hotness가 threshold H를 넘어가면 페이지가 hot하다고 판단하며, (Curr/Curw)가 threshold Rrw를 넘어가면 read hot이라고 판단한다.

α × (Curr + Curw ) + 1
α = e−λΔt, where λ is a decay constant

• Hot-page Swapping and Caching

  Rcmp는 기존 페이지 기반의 메커니즘이 페이지 폴트를 이용하여 스왑 매커니즘을 수행한 것과 다르게 user-level swap mechanism을 사용한다. Rcmp의 hot 페이지 스왑 알고리즘을 아래의 절차를 따른다.

1. R1의 스왑 요청이 MS의 FIFO 큐에 큐잉된다.
2. R1은 스왑 될 free page를 선택한다. Free page가 없다면, cold page를 선택한다. Cold page도 없다면, 6단계로 넘어간다.
3. R2는 스왑될 페이지들의 hotness를 R1의 hotness와 비교한다. R2의 hotness가 더 높으면 swap을 거부한다. Read hot인 경우에는 R1의 CXL에 캐싱한다. 캐싱된 페이지는 read-only이며, write 될 때 삭제된다.
4. R2의 스왑될 페이지의 metadata에 대해 disable 하고 page table을 업데이트한다.
5. Hot page를 one-sided RDMA를 통해 스왑 한다.
6. R1의 page table을 업데이트하고, MS의 요청을 dequeue 한다.

3-3. RRPC

  Rcmp에서 진행한 RPC와 hybrid(RPC + one-sided RDMA)의 throughput 비교 실험에서 512B를 기준으로, 데이터의 사이즈가 512B보다 작을 때는 hybrid 방식보다 RPC의 처리량이 더욱 높은 것으로 나타났다. 

이런 특성을 이용하여 Rcmp에서는 데이터의 사이즈를 기준으로 전송 방식을 바꿔가며 communication을 수행하여 throughput을 올리는 framework를 제시하였다. 데이터 사이즈에 따른 전송 방식은 아래와 같다.

• Pure RPC mode: 512B보다 작은 데이터의 communication에 사용 (데이터 요청 -> 데이터 반환)
• RPC and one-sided mode: unstructred big data의 communication에 사용 (주소 요청 -> 사이즈 전달 -> RDMA read)
• RPC zero-copy mode: structured big data의 communication에 사용 (데이터 요청 -> RDMA write)

Achieving Microsecond-Scale Resource Fungibility with Logical Process

Authors: Zhenyuan Ruan,  Seo Jin Park, Marcos K. Aguilera, Adam Belay, Malte Schwarzkopf

Groups: MIT, VMware Research, Brown Univerisity

Keywords: 

Datacenter, Resource Fungibility

#1 Motivation

1-1. Resource Fungibility

  현재의 클라우드 시스템에서 인스턴스를 할당하는 방식에는 Resource Fungibility 오버헤드가 있다. 클라우드 컴퓨팅에서 사용자는 고정된 크기(코어의 수, 메모리 등)의 인스턴스를 요청하고, Provider는 bin-pakcing 알고리즘에 의하여 해당 인스턴스를 할당 가능한 서버에 할당한다. 사용자 입장에서 인스턴스의 크기는 고정되어 있기 때문에 실제 어플리케이션의 자원 사용량과는 다르며 남는 자원들은 대부분 유휴 상태로 존재한다. Provider는 낭비된 자원을 활용하여 다른 인스턴스에 할당하여 자원을 효율적으로 사용하려고 한다. 하지만 이러한 방식은 시스템에 간헐적으로 과부하가 발생하여 성능 저하가 발생할 수 있으며, 이는 지연 시간에 민감한 워크로드에 특히 문제가 된다. 이와 같은 문제의 이유는 인스턴스를 할당하는 단위가 너무 크기 때문이다. 따라서 클라우드의 효율적인 디자인은 disruption을 피하고 자원을 작은 단위로 빠르게 재할당 할 수 있어야 한다. 

  본 논문에서는 resource fungibility를 해결하기 위해 논리 프로세스라는 개념을 제안한다. 논리 프로세스는 논리 디스크의 개념에서 착안한 방식으로 proclet이라는 단위로 논리 프로세스를 결합하지만 물리 자원들은 여러 머신에 걸쳐 분배하는 개념을 말한다. Proclets으로 분리된 프로세스는 fine-grained이기 때문에 자원을 비효율적으로 할당하는 비율이 적으며, 전체 프로세스를 마이그레이션 하는 것에 비해 마이그레이션이 매우 빠르다.

1-2. Alternative approaches

  논리 프로세스와 비교하여 fungibility를 해결할 수 있는 다른 방식들은 다음과 같은 단점들을 가진다.

• Migrate VM, containers, or process: 마이그레이션이 느리다.
  • Process abstraction: 마이그레이션 문제를 해결 했으나 공유 메모리의 캐시 일관성 오버헤드가 있다.
  • PGAS: 캐시 일관성 오버헤드를 해결 했으나 병렬 어플리케이션에만 적용 가능하다.
• Distributed object, microservices, and serverless funtions: coarse-grained instance 오버헤드, RPC 오버헤드가 있다.
  • Parallel programming frameworks: 데이터가 정적으로 위치해야 한다.
• Far memory system: 원격 메모리가 cold일 때만 효율적이다. (stateless or read-only service에서 효율적임)

#2 The Logical Process Abstraction

  Proclet은 하나의 힙과 공유 메모리를 통해 힙에 동시 접근할 수 있는 여러 스레드로 이루어져 있다. 힙 메모리는 직접적으로 공유되는 것이 아닌 논리 객체에 대한 포인터를 힙에 저장하고 있는 루트를 통해 공유된다. 이러한 방식은 개발자가 object-oriented 방식을 통해 proclet을 개발할 수 있도록 한다.

  논리 프로세스가 할당된 머신의 수는 이용가능 한 수의 머신의 수에 따라 계속해서 바뀌며, 각 머신들은 각각의 런타임에 의하여 논리 프로세스를 처리한다. 런타임은 proclets 간의 location-trasparent communication을 제공하며 외에도 추가로 resource pressure detection, proclets migration between machines, and failures handling 기능을 제공한다.

  논리 프로세스를 개발하는 것은 UNIX 프로세스를 개발하는 것과 같으며 차이점은 2가지가 존재한다. 첫째로 개발자는 상태를 proclet 단위로 분리해야 하고, 두번째로 proclet API를 사용하여야 한다.

2-1. Address spaces and Cache coherence

  논리 프로세스는 마이그레이션 후 swizzling 없이도 머신 간의 포인터를 유효하게 사용하기 위해 각 머신에 동일한 주소 공간 레이아웃을 사용한다. 그리고 런타임 인스턴스가 초기화 및 새로운 proclet 생성 시 레이아웃의 동기화를 유지하는 역할을 한다.

  위 그림은 주소 공간 레이아웃의 예제이다. Read-only 코드와 데이터 세그먼트는 모든 머신에 매핑되어 있다. 그렇기 때문에 모든 머신은 binary-compatible 해야 한다. Read-only 데이터는 정적 배열, 테이블, proclet의 인풋과 같은 데이터를 저장하는 역할을 한다. 반면에 proclet의 힙은 실행 중 하나의 머신에서만 매핑되며, 다른 프로세스는 접근할 수 없다. 이는 머신 간 캐시 일관성을 보장해야 하는 공유 메모리 구조보다 효율적이다. 이 구조에서 데이터를 교환하기 위해서는 같은 머신 내에서는 function call 외부에서는 RPC call을 이용한다. 또한 메모리를 공유하지 않기 때문에 fault isolation이 가능하다.

2-2. Programming Model

  개발자는 proclet root class를 통해 어플리케이션을 작성하여야 한다. 기존의 오브젝트 기반 프로그래밍처럼 각 클래스는 메소드와 필드를 정의하며, 메소드 구현은 어플리케이션의 로직을 구현하고 API를 통해 proclet을 호출할 수 있다. 필드는 proclet 내부의 상태를 정의하며 정적 및 동적 모두 할당할 수 있다.

   논리 프로세스는 main proclet에서부터 시작한다. main proclet은 make_proclet 함수를 통해 다른 proclet을 생성할 수 있다(line 10~11). proclet은 원격 메소드 호출 및 클로저를 통해 소통할 수 있다. 메소드 호출에서는 다른 proclet의 root proclet의 메소드를 Run() 함수 또는 RunAsyunc() 함수를 이용하여 호출한다(line 13 and 17~18). 클로저에서는 proclet을 function shipping을 통해 구현하고, 다른 proclet의 루트 객체에 함수를 ship한다(line 15). 또한 원격 런타임이 로컬 런타임과 동일한 proclet의 메소드나 클로저를 실행할 수 있기 때문에 val를 보호하기 위한 뮤텍스 mu 또한 필요하다(line 5).

  논리 프로세스는 POSIX나 I/O abstraction이 아닌 런타임이 제공하는 abstraction을 사용하여 I/O를 수행한다. 이를 통해 proclet이 머신에 독립적이며, TCP 상태와 같은 로컬 커널 상태를 전달하지 않고도 머신 간의 마이그레이션이 가능하다. 런타임이 TCP 연결을 유지하기 때문에 논리 프로세스의 특정 proclet과의 연결이 가능하다.

2-3. Porting Applications to Logical Processes

  상태를 fine-grained 유닛으로 분리할 수 있는 어플리케이션들은 각각의 상태가 proclet으로 변환되는 방식으로 모두 논리 프로세스로 포팅이 가능하다. 이러한 특징은 이미 microservice나 FaaS와 같이 상태를 분리한 클라우드 어플리케이션에 적합하다.

  논리 프로세스를 proclet으로 나눌 때 granularity와 scope 두 가지를 고려해야 한다. Proclet의 사이즈가 너무 크면 resource fungibility가 다시 발생하며, 사이즈가 너무 작으면 통신 오버헤드가 크다. 실험적인 결과를 통해 수 MiB 상태 크기를 가지는 proclets이 가장 잘 동작하였다. Proclet에 어떤 기능을 구현할 지도 중요한 문제인데 한 가지 방법으로는 하나의 proclet을 모듈이나 mircoservice, 패키지와 같은 논리적 함수 유닛으로 분리하는 functional splitting이 있고, 다른 방법으로는 함수 유닛의 크기가 일반적인 proclet의 크기보다 크기 때문에 이를 분리하는 sharding이 있다.

2-4 Fault Tolerance

  Proclet은 복사를 통해 fault tolerance를 허용한다. 복사된 proclet은 원본 proclet의 힙을 복사하여 유지하며, 이 백업은 런타임에 의해 다른 머신에 같은 가상 주소로 위치하게 된다. 백업 힙을 동기화 상태로 유지하기 위해, 런타임은 원본 proclet의 호출 요청을 정렬하여 복사 proclet에 전달한다. 복사 지연 시간을 줄이기 위해 원본 proclet과 백업 proclet이 중복 실행되지만 원본 proclet은 복사 작업이 완료되어야 호출을 완료한다. 시스템이 원본 proclet의 장애를 감지하면, atomic 하게  proclet의 백업을 발생 시킨다. 또한 동일한 힙을 유지하기 위해, proclet을 일시 중지하여 새로운 백업을 추가하고, 새로운 proclet에서 백업 레플리카로 힙을 복사한다.

#3 Nu Runtime System

  Nu 런타임은 논리 프로세스 추상화를 제공하며 Linux 환경에서 동작한다. Caladan 위에 Nu를 구현하였는데 그 이유는 Caladan이 work-stealing 방식으로 낮은 지연 시간의 user-level threading 패키지와 kernel-bypass, user-level TCP/IP를 제공하기 때문이다. 예를 들어, 스레드가 블락되어 있을 때 Caladan이 낮은 오버헤드로 컨텍스트 스위칭을 잘한다.

  Nu는 Caladan에 10,000줄가량의 C++ 코드를 추가하여 구현되었으며, 이는 infrastructure 간의 효율적인 통신과 여러 힙을 처리하기 위한 새로운 메모리 관리 방법, 최적화된 proclet 마이그레이션 시스템, proclet의 위치를 트래킹 하는 컨트롤러를 포함한다.

3-1. Serialization and Communication

  Nu는 원격 호출을 정렬하기 위해 cereal을 사용한다. Cereal은 대부분의 STL type을 지원하는 binary serialization을 제공하며, 포인터와 참조에 대한 직접 접근을 금지한다. Nu는 cereald을 수정하여 함수와 proclet 포인터를 정렬한다. Nu는 코드 일반화가 필요한 RPC와 대조적으로 원격 호출을 정렬화하기 위해 컴파일 시 C++ 템플릿을 사용한다. 따라서 개발자는 boilerplate 없이 원격 메소드를 호출할 수 있으며, 정적 타입 검사까지 제공한다.

  ??

3-2. Memory Management

  Nu는 proclet의 힙을 관리하기 위해 확장성을 위한 코어 당 캐시와 멀티코어 메모리 할당자를 포함하는 커스텀 slab allocator를 사용한다. C++에서 custom new()가 사용가능한 점을 이용하여 메모리 할당자를 구현하였다. Nu는 각 스레드가 어떤 프로클릿과 연관되어 있는지 추적하고 할당을 올바른 힙으로 유도한다.

3-3. Migration

  Proclet을 마이그레이션 하기 위해 런타임은 migration flag를 설정한다. 그다음 proclet을 실행 중인 스레드를 정지하고 레지스터의 상태를 저장한다. 그런 다음 proclet의 data(힙, 스택, 레지스터 상태)를 새로운 목적지로 전달한다. 마지막으로 런타임은 migration flag를 초기화하고 컨트롤러에 proclet의 위치를 업데이트한다.

  Nu는 migration datapath를 최적화하였는데, 먼저 TCP throughput을 개선하기 위해 parallel connedction과 jumbo frame을 사용하였다. 기존에 병목점이었던 linux mmap을 pre-zero freed page로 수정하여 라인 당 100 GbE의 throughput을 달성하였으며, 이전의 frame allocator를 재사용하기 위해 mremap을 수행하였다.

  Nu는 어떤 proclet을 옮겨야 하고 어디로 옮겨야 할지 정하는 확장 가능한 마이그레이션 정책을 제공한다. CPU load나 cache pressure, memory capacity, memory bandwidth 등과 같은 요소들을 고려할 수 있으며 proclet의 locality를 향상하기 위해 동시에 고려할 수 있다.

  Nu의 마이그레이션이 충분히 빠르기 때문에 단순한 정책도 잘 동작한다. 특히 자원이 부족한 상황에서 어떤 자원을 소모할지 예측하는 정교한 알고리즘을 사용하지 않고 단순히 마이그레이션 시켜도 성능이 잘 나온다. 마이그레이션이 언제 필요한 지 정하기 위해 모니터링 스레드가 계속해서 자원의 소모량을 측정한다. 

  Nu는 resource pressure가 없어질 때까지 한 번에 하나의 proclet을 마이그레이션 한다. 어떤 proclet을 마이그레이션 할 지 결정하기 위해 Nu는 아래의 식을 사용한다. 

  RESOURCE_USE는 proclet의 자원 소모량을 나타내고, MIGRATION_TIME은 해당 proclet의 힙 사이즈를 고려한 마이그레이션 시간을 나타낸다. 이 식은 resource pressure 완화 속도를 극대화하고 Nu가 응답 속도를 최적화한다. 런타임은 이 속도를 추정하기 위해 실시간으로 메트릭을 수집한다. 마이그레이션 대상을 결정하기 위해 Nu는 전역 클러스터 컨트롤러에 쿼리 하고, 컨트롤러는 서버 간의 리소스 사용량을 모니터링하고 가능한 대상을 반환한다.

3-4. Controller

  Nu는 proclet placement나 가상 주소 공간 할당과 같은 클러스터 간의 결정 및 proclet의 위치나 자원 사용량과 같은 정보를 트래킹을 위한 컨트롤러가 있다. 컨트롤러가 중앙 처리 방식을 띄지만 프라이머리 백업 복제나 단순 리커버리와 같은 방식으로 높은 이용가능성을 보인다.

  컨트롤러는 주기적으로 서버의 이용 가능한 자원을 측정하며, 이것을 이용하여 proclet의 생성 및 마이그레이션 위치를 정한다. proclet은 중복되지 않는 가상 주소 공간을 사용하여야 한다. 따라서 Nu는 가상 주소 공간을 4GB의 세그먼트 배열로 나누어 proclet의 힙 공간을 확보해 둔다. 컨트롤러는 할당된 세그먼트와 할당되지 않은 세그먼트 리스트를 유지하여, proclet을 할당할 때 로컬 런타임에게 할당되지 않은 세그먼트를 전달한다.

  컨트롤러는 각 proclet의 시작 논리 주소로부터 위치를 유지하고, 각 런타임은 proclet이 최근 접근한 캐시를 유지한다. 이것은 컨트롤러를 임계영역에서 제거함으로써 컨트롤러와의 통신을 위한 메소드 호출을 제거한다. Proclet을 마이그레이션 할 때, 컨트롤러는 매핑을 업데이트한다. 이로 인해 캐시가 오래되어 로컬 런타임에서 잘못된 시스템으로 메서드 호출을 보낼 수 있다. 이것이 발생하면 원격 머신은 에러를 반환하게 되는데, 로컬 머신은 해당 캐시 엔트리를 invalidating 하고 새로운 머신을 찾음으로써 에러를 처리한다.

3-5. Replication

  Nu에서는 프라이머리를 백업하기 위해 연산을 복제본에 포워딩하고 있다. 이때 서브 연산이 발생하는 경우, 프라이머리와 복제본 두 곳에서 연산이 발생할 수 있기 때문에 유의하여야 하는데, Nu는 RIFL의 복제 감지를 이용하여 이를 해결하였다. 각 proclet 간의 호출에서 서브 연산이 발생하면 프라이머리가 서브 연산의 결과를 복제본에 전달하는 방식으로 복제본은 서브 연산을 재실행하지 않고 결과를 재사용한다.

  컨트롤러가 실패된 프라이머리를 감지하면, 복제본이 새로운 프라이머리가 되도록 하고 위치 매핑을 새로운 프라이머리로 업데이트한다. 하지만 런타임은 오래된 프라이머리를 가지고 있게 되는데, 이를 epoch-based 방식으로 해결한다.

Transparent Page Placement for CXL-Enabled Tiered Memory

Authors: Hasan AI Maruf, Hao Wang, Abhishek Dhanotia, etc

Groups: Univ of Michigan, NVIDIA, Meta

Keywords: Memory management, CXL, Dense storage

#1 Background

1-1. Memory

  최근 데이터센터에서는 저지연 서비스를 제공하기 위해 in-memory computation이 표준이 되고 있다. 이러한 경향은 메모리의 수요를 계속해서 증진시키고 있으며, 데이터센터에서 메모리의 cost와 power가 계속해서 증가하고 있는 이유이다. 현재의 아키텍쳐에서 메모리 서브시스템은 CPU와 완전히 독립되어 있으며, 이는 아래 제약사항들을 초래하며 효율적인 메모리 계층 구조 설계를 제한한다. 

• Support a single generation of memory
• Memory capacity comes at power of two granularity which limits finer grain memory capacity sizing
• Limited bandwidth vs capacity points per DRAM generation which forces higer memory capacity in order to get more bandwidth

1-2. CXL

  CXL은 PCIe를 통해 디바이스와 CPU가 소통하는 구조로 기존의 DRAM과는 다르게 heterogenous 한 구성이 가능하다. PCIe를 통해 연결되기 때문에 bandwidth가 socket bandwidth에 제한되지 않으며, PCIe의 발전에 따라 더욱 증가할 가능성이 있다. 또한, latency도 기존 RDMA 방식과 비교하여 NUMA latency와 비슷하며 50~100ns 밖에 차이 나지 않는다.

#2 Chameleon

  TPP는 메모리를 CXL을 활용한 메모리 계층 구조를 통해 cold page를 낮은 단계의 메모리에 할당하고 hot page를 메모리에 할당하여 애플리케이션의 성능을 향상하고자 한다. 이를 위해서 데이터센터 어플리케이션에 메모리 티어 시스템을 적용하기 위해 메모리 패턴을 파악하고 메모리 페이지 타입에 따른 메모리 티어 오프로딩 정량화가 필요하다. TPP는 자체 성능 분석 툴인 Chameleon을 개발하여 각 워크로드들의 특성을 파악하였다. (Chameleon에 대한 설명은 생략하고 실험을 통한 인사이트를 살펴보겠음)

2-2. The needs of tiered memory system

  워크로드들은 시스템 메모리 전체 용량의 95~98%를 할당하지만 많은 양의 메모리를 cold 상태로 가지고있고, 짧은 주기 안에서 전체 메모리의 22~80%만 사용한다. 또한 anonymous page를 자주 접근하며, file page는 cold한 특정이 있었다. 이러한 특성은 메모리 계층화 구조를 통해 cold memory를 더 낮은 티어의 메모리로 옮겨감으로써 메모리를 더욱 효과적으로 사용할 수 있음을 기대할 수 있다. 

2-3. Smart page placement mechanism

  어플리케이션들은 실행 시간 동안에 특정 패턴을 계속해서 유지하려는 특성이 있으며, Smart page placement mechanism은 결정을 내릴 때 page type을 아는 것이 성능에 중요한 영향을 끼칠 것이다. 특히, anoymous page의 memory utilization이 상승하게 되면, 어플리케이션의 전체 throughput이 상승하게 되는 효과를 볼 수 있다.

요약하자면, 위의 그림 2의 실험을 통해 논문에서는 cold page가 메모리에 많이 존재함을 강조함으로써 tier memory system의 필요성을 강조한다. 그리고 그림 3의 실험을 통해 어플리케이션은 보통 일정한 패턴을 띄며, 이것을 이용하는 page placement mechanism이 성능을 상승시킬 것이라 한다. 그 주장에 뒷받침되는 실험으로 그림 4를 통해 anonymous page들의 memory utilization이 상승할수록 어플리케이션의 throughput이 상승하는 것을 보여주고 있다.

#3 TPP

  효율적인 page placement mechanism을 위해 TPP는 다음과 같은 목표를 지향한다.

• Hot page를 fast memory tier에 위치시키도록 함 => latency 최소화
• CXL node에 page를 할당하는 것을 최소화 => page promotion/demotion 오버헤드 최소화
• 응용의 sensitivity에 따른 page type에 맞는 메모리 티어에 page 할당 => cold page의 로컬 메모리 pollution 최소화

3-1. Design

• Implementation

  Application-transparent한 page placement algorithm은 user space, kernel space 모두 위치할 수 있다. User space에서 구현하려면, Chameleon 같은 툴을 사용하여 page temperature를 측정하고, NUMA migration을 통해 page placement algorithm을 구현해야 한다. 하지만 이런 방식은 user space에서 page list와 history management를 관리하고 있어야 하는 점과 컨텍스트 스위칭이 발생한다는 점에서 오버헤드가 크다. 따라서 TPP는 kernel space에서 구현되었다.

• Page temperature detection

  Page temperature를 측정하는 방법은 PEBS, Page Poisoning, NUMA Balancing과 같은 방법들이 있다. PEBS는 kernel-space에서 측정할 수 있으나 CPU vendor에 따라 사용하지 못 하기도 하며, temperature를 user-space에 전달해야하고, kernel에 상시로 동작하기에는 오버헤드가 크다는 단점이 있다.

  따라서 TPP는 sampling 방식을 사용하였는데, Sampling을 통해 page temperature를 측정하는 방식은 hot/cold page를 찾기에는 적합하나, page가 evict될 때 page accessed bit를 clear하고 TLB entry를 flush 해야하는 오버헤드가 크다. 이러한 문제를 해결하기 위해 Thermostat에서 채택한 방식인 2MB granularity의 huge-page로 sampling을 진행하였다.

• CXL-memory abstraction

  state-of-art 연구에서는 cold page를 보관하기 위해 swap space를 이용하였으며, swap-based mechanism을 활용하여 cold page를 찾았다. 하지만 swap mechanism을 이용할 경우 major page fault가 발생하며, CXL의 cache-line granularity를 활용하지 못 한다는 측면에서 TPP는 CXL 메모리를 swap device로 사용하지 않았다.

 하지만 swap space 기반의 feedback-driven reclamation은 효율적이며 TPP와는 독립적으로 동작할 수 있기 때문에 TPP와 같이 동작한다. 따라서 TPP의 구조에서 TMO는 user-space에서 memory reclamation을 동작하며, TPP는 kernel-space에서 page placement를 동작한다.

3-2. Decoupling Allocation and Reclamation

  커널은 메모리 관리를 위해 min, low, high 3가지 워터마크를 사용한다. NUMA 노드의 free page 수가 high 워터마크를 넘어가게 되면, 커널은 메모리가 부족하다고 판단하고 low 워터마크까지 page reclamation을 진행하게 된다. 이때 메모리 노드에 대한 새로운 페이지 할당 요청이 들어오면, 커널이 high 워터마크 아래까지 page reclamation을 완료하기 전까진 페이지 할당은 중지된다. 새로운 페이지 할당 요청이 많은 상황에서는 page reclamation이 page allocation보다 느리기 때문에 메모리 노드 공간 확보에 실패하여 응용의 성능이 많이 하락하게 된다.

  TPP에서는 multi-NUMA 시스템 상황에서 미리 free memory headroom을 확보하여 allocation burst를 모두 로컬 메모리에 할당하려 하며, CXL node에 있는 hot page도 local memory로 잘 가져올 수 있도록 한다. 이를 위해 TPP는 demotion, allocation 두 가지 워터마크로 allocation과 reclamation의 동작을 분리시켰다. 백그라운드 프로세스는 free page의 수가 demotion 워터마크 아래가 될 때까지 page reclamation을 비동기적으로 수행하며, 이 때 page allocation 요청은 free page 수가 allocation 워터마크 아래이면 수행 가능하다. (추가로 워터마크는 user-space process로 분석을 통해 동적으로 조절이 가능하다.)

3-3. Page Type-Aware Allocation

  Production 응용은 보통 초기 구동 단계에서 많은 파일 I/O를 수행하고, 드물게 접근하는 파일 캐시를 생성한다. Cold 파일 캐시는 로컬 노드에 위치하게 되고, 비활성 파일 캐시로 인해 로컬 메모리 노드가 점유되면 비활성화된 파일 캐시가 나중에 다시 promotion 되어야 하는 오버헤드가 있다. 이러한 불필요한 페이지 이동을 해결하기 위해 TPP는 CXL 노드에 캐시를 할당하고, 응용에서 생성된 페이지 캐시는 초기에 CXL 노드에 할당한다. 이후 페이지 캐시가 promotion candidates로 선택될만큼 충분히 hot 해진 경우 로컬 노드로 promotion 된다.

3-4. Migration for Lightweight Reclamation

  새로운 페이지를 할당하려 할 때 free page가 부족하면 커널은 CXL-node에서 새로운 페이지를 할당한다. reclamation이 느릴 수록 CXL 노드에 새로 할당되는 수가 많아지며, 이것은 응용의 성능을 하락시키는 요소가 된다. 하지만 TPP는 커널의 LRU-based mechanism을 통해 reclamation-candidates를 찾고 CXL node로 비동기적으로 이동시키는 방법으로 이 문제를 해결하였다. 또한 swap mechanism과 다르게 CXL node의 cold page는 여전히 in-memory page이기 때문에 page fault handling 오버헤드가 없다. 만약 CXL 노드의 메모리가 부족하여 demotion이 실패하면, 기존 커널의 로직으로 다시 돌아가게 된다.

3-5. Page Promotion for CXL-Node

  로컬 메모리가 pressure 되는 상황에서 새로운 페이지의 할당은 CXL 메모리에서 이루어지게 된다. 게다가 demoted된 page 또한 재접근을 통해 로컬 메모리로 다시 promote되기도 한다. 효율적인 promotion 알고리즘이 없으면 hot page는 계속해서 CXL node로 demote되고 이는 결국 응용의 성능 저하로 나타나게 된다.

  NUMA Balancing 구조에서 커널은 프로세스의 메모리 접근 패턴을 분석하기 위해 일정 용량을 샘플링한다. CPU가 샘플링 된 페이지에 접근하면 (NUMA hint fault), minor page fault가 발생하게 된다. 그리고 remote CPU가 접근하게 되면 해당 page를 remote node로 promote하게 된다. 하지만 로컬 hot page를 다른 노드로 옮기는 것은 합리적이지 않으며, 로컬 hot page 샘플링으로 인하여 발생하는 NUMA hint fault는 오버헤드가 크기 때문에 TPP에서는 CXL 노드에서만 샘플링을 수행한다.

   CXL 노드에서 발생하는 NUMA hint fault는 CXL 노드에 있는 페이지를 로컬 노드로 promote 하도록 한다. 하지만 재접근 비율이 낮거나 cold page를 로컬 노드로 가져오는 경우에 이것은 또 성능 하락으로 이어질 수 있는 여지가 있기 때문에 TPP에서는 active list에 존재하는 페이지의 경우에만 로컬 노드로 가져오게 되고, inactive list에 존재하는 페이지는 active list로 가져오도록 하여 promote traffic을 줄였다.

CXL-Based Memory Pooling Systems for Cloud Platforms

Authors: Huaicheng Li, Danel S. Berger, Lisa Hsu, etc

Groups: Carnegie Mellon University, Microsoft Azure, Intel, Stone, Google

Keywords: Memory Disaggregation, CXL, Memory Pooling, ML

#1 Background

  논문에서는 클라우드 환경에서 성능과 비용의 중요 요소인 메인 메모리에 대한 stranded memory와 untouched memory 문제를 지적하며, 이를 CXL을 활용한 메모리 풀링으로 해결하고자 한다.

1-1. Stranded and untouched memory

  기존의 가상 머신의 자원 할당 방식은 서버의 메모리를 가상 머신의 NUMA 노드에 정적으로 할당하는 방식이었다. 이런 방식은 두 가지 메모리 낭비를 초래하였다.

• Stranded Memory(남는 메모리): 서버의 CPU는 가상 머신에 모두 할당되었지만 아직 할당되지 않고 남아있는 서버의 메모리
• Untouched Memory(미사용 메모리): 가상 머신에 할당된 메모리 중에서 가상 머신이 실제로 사용하지 않고 남아 있는 메모리

1-2. CXL

  Compute Express Link(CXL)은 CPU와 여러 디바이스(가속기, 메모리 등) 간의 메모리 공유를 위한 프로토콜을 제공하는 고성능 인터페이스이다. PCIe 5.0 interface에서 flexbus를 제공하는 CPU에 한하여 사용이 가능하며, CXL.cache 프로토콜을 통해 캐시 일관성까지 제공한다.

  최근 메모리 분리 연구와 관련하여 기존의 RDMA 방식과 다르게 CXL은 PCIe를 사용하여 latency 이득이 매우 크기 때문에 CXL을 사용하려는 움직임이 많으며, 해당 논문에서도 CXL을 통한 메모리 분리를 이용하여 memory stranding 문제를 해결하려 한다. 

#2. Motivation Experiments

  아래에서부터는 Microsoft Azure에서 실시한 memory stranding 및 untouched memory 측정 및 관련 워크로드 성능, CXL latency 등을 분석해 볼 것이다. 그리고 이를 통해, POND의 설계 방향을 이해할 수 있다.

2-1. Memory stranding

  그림 3은 호스트 가상 머신에 스케줄링된 코어 별 stranded DRAM bucket의 분포 측정의 snapshot이다. 파란 선은 stranded memory 비율의 평균값을 나타내며, 85% 이상의 코어가 가상머신에 할당되면 평균값이 10%까지 증가하게 된다. 또한, 95% percentile에서 최댓값이 35%까지 증가하는 모습을 보인다.

  그림 4는 VM-to-server 트레이스를 분석하여, 풀링을 통해 절약할 수 있는 DRAM의 양을 나타낸 것이다. Pool size는 같은 DRAM이 접근할 수 있는 CPU 소켓을 뜻하며, pool size가 커질수록 풀링을 통해 절약할 수 있는 DRAM의 양이 적어진다. 하지만 이 부분은 메모리 풀의 사이즈가 커지면 감소하는데, 아래 그림에서 10%의 메모리 풀을 제공하였을 때 32개의 소켓으로는 12%의 DRAM을 save 할 수 있으나 64개의 소켓에서는 13%의 DRAM을 save 할 수 있다.

  위의 실험들을 요약하면, 서버에서 가상 머신에 할당되는 코어의 수가 많아질수록 stranded memory의 비율을 늘어나며 이는 최대 35%까지 달한다. 하지만 실험적인 분석에서 메모리 풀을 통해 DRAM을 save 할 수 있는 결과가 나왔는데, 50% 메모리 풀을 제공할 때 32개의 소켓에서 12%까지 DRAM을 save 할 수 있었다. 이 사실을 바탕으로 POND에서는 CXL memory pool을 stranded memory 및 untouched memory을 위해 제공하여 DRAM의 효율을 증가시키려 한다.

2-2. Workload sesitivity

  CXL은 로컬 DRAM보다 접근 latency가 느리기 때문에 이에 따른 워크로드의 성능 저하가 있을 수 있다. 이를 관찰하기 위해 Azure에서는 158개의 워크로드에 대해 CXL latency가 로컬 DRAM보다 182% 느릴 때, 222% 느릴 때로 가정하여 실험을 진행하였다. 아래 그림 5에서 보이다시피, latency가 182% 증가하였을 때 latency에 민감하지 않은 워크로드는 성능 저하가 없기도 한 반면, 민감한 워크로드의 경우 25% 이상 성능이 감소하기도 한다. 

위 실험을 통해 latency에 민감하지 않은 워크로드에 대해 CXL 메모리 풀을 활용하여 자원 효율을 높이는 설계가 가능함을 확인할 수 있다.

#3 POND

3-1. Control plane layer

  POND는 아래 그림 6에서처럼 두 가지 역할을 한다. 풀 메모리를 얼마나 사용할 지 예측하고 할당하는 VM scheduler와 가상 머신의 성능을 계속해서 파악하고, 이에 따라 CXL 메모리 풀의 양을 조절하는 QoS Monitor 두 가지가 있다.

• Prediction and VM scheduling
  • A1: VM request arrives.
  • A2: Queries model for a local memory prediction.
  • A3: Informs PM about needs.
  • A4: Memory onlining and allocating.
  • A5: Informs Hypervisor to start VM.

• QoS Monitoring
  • B1: Queries hypervisor and hardware performance counters &
          Uses an ML model of latency sensitivity.
  • B2: If performance impact exceeds the PDM, ask Mitigate Manager to trigger a memory reconfiguration.
  • B3: Do memory reconfiguration. (after reconfiguration, VM uses only local memory)

3-2. Prediction models

• Prediction for VM scheduling

(추가 예정)

• QoS Monitoring

(추가 예정)

3-3. Software layer

  Software layer에서 하는 주요한 역할은 풀 메모리의 할당 및 해제, 프레그멘테이션 방지, 풀 메모리 가상 머신에게 전달 그리고 opaque 가상 머신을 위한 Telemetry이다. 

• Pool memory ownership

   풀 메모리 할당은 호스트 드라이버에게 인터럽트를 트리거시켜 드라이버가 hot-plugged 될 범위의 주소를 읽도록 한다. 이후 드라이버는 OS의 Memory Manager가 해당 메모리 슬라이스를 online으로 요청하도록 하고, EMC가 호스트의 메모리 슬라이스에 대한 접근 권한을 부여한다. 풀 메모리 할당 해제는 호스트가 메모리 슬라이스를 offlining 후 EMC에서 메모리 슬라이스의 권한을 해제하여 완료한다.

  POND는 가상 머신이 시작되거나 종료될 때 발생하는 프레그멘테이션을 방지하기 위해 메모리 슬라이스가 1GB 단위로 가상 머신에 할당되며, 다른 호스트에게 재할당되기 전에 free 및 offline 상태로 보관함으로써 프레그멘테이션을 방지한다. 그러나 호스트나 드라이버가 풀 메모리를 할당하여 프레그멘테이션을 유발할 수 있기 때문에, 하이퍼바이저만 사용 가능한 메모리 파티션을 할당하고, 호스트와 드라이버는 호스트 로컬 메모리 파티션에서 메모리를 할당하여 호스트나 드라이버에 의한 프레그멘테이션을 방지한다.

  이러한 최적화들을 통해, 1GB 메모리 슬라이스를 offlining 하는 데에 10~100ms 소모되고, onlining은 1us 소모된다. 이때 메모리 onlining은 충분히 빠르기 때문에 가상 머신을 시작하는 데에 있어 block이 되지 않지만, offlining은 너무 느리기 때문에 critical path에서 발생하면 안 된다. 따라서 POND는 항상 할당되지 않은 풀 메모리를 보관하는 버퍼를 유지하여 이를 해결하였다.

• Exposing pool memory to VMs

  NUMA-local 메모리와 풀 메모리를 사용하는 가상 머신은 풀 메모리를 zNUMA 노드로 취급한다. 그래서 가상 머신을 시작할 때 cpu 항목이 없는 메모리 블록을 추가하여 zNUMA 노드를 생성하며, zNUMA 노드의 크기가 untouched memory의 크기와 같으면 가상 머신은  로컬 메모리에서만 동작하게 된다.

• Reconfiguration of memory allocation

  가속기와의 호환성을 유지하기 위해 로컬 및 풀 메모리 매핑은 일반적으로 가상 머신의 lifetime 동안 static mapping 상태를 유지한다. 그러나 가상 머신의 메모리 할당이 최적이 아닐 때, POND는 메모리 할당을 재정의 한다. 호스트에 로컬 메모리를 사용할 수 있는 경우, 가속기를 사용하지 않도록 설정하고 가상 머신의 모든 메모리를 로컬 메모리로 복사한 다음 가속기를 다시 사용하도록 설정한다. 이를 통해 로컬 및 풀 메모리 할당을 초기화하며, 풀 메모리 1GB마다 약 50ms가 소요된다.

• Telemetry for opaque VMs

  POND는 두 가지 유형의 가상 머신 Telemetry를 측정한다. 첫째로, Pond는 메모리 성능과 관련된 하드웨어 카운터를 수집하기 위해 PMU(Performance Measurement Unit)를 사용하고, 분석을 위해 TMA(Top-down Method for Analysis)를 사용한다. 그리고 하이퍼바이저를 수정하여 메트릭을 개별 가상 머신에 연관시키고 가상 머신 카운터 샘플을 분산 데이터베이스에 기록한다. 모든 코어 PMU 메트릭은 간단한 하드웨어 카운터를 사용하여 오버헤드를 유발하지 않는다.

  둘째로, 가상 머신의 untouched memory page를 추적하기 위해 하이퍼바이저 Telemetry를 사용한다. 게스트에 할당된 메모리를 추적하는 기존 카운터를 사용하며, 이는 사용된 메모리를 과대 평가하는 경향이 있다. 그리고 하이퍼바이저 페이지 테이블에서 액세스 비트를 스캔하여 untouched memory page를 찾는다. POND는 untouched memory page만 찾기 때문에 페이지 테이블의 액세스 비트를 자주 리셋할 필요가 없으며, 이는 오버헤드를 최소화한다.

3-4. Hardware layer

  Pond는 여러 호스트에게 공유되는 메모리 풀을 제공하며, 여러 포트를 통해 풀 내의 호스트에게 각각의 캐시 일관성 도메인과 별도의 하이퍼 바이저를 제공한다. 또한 호스트 간의 명시적인 소유권 모델을 통해 호스트의 독립적인 메모리 풀을 보장한다. 호스트는 처음에 제공 받은 풀 메모리를 offline으로 취급하다가 호스트의 수요에 따라 1GB 메모리 슬라이스를 동적으로 할당하며, 각 슬라이스는 주어진 시간에 하나의 호스트에게 할당된다. EMC는 캐시라인의 슬라이스 요청자와 소유자가 일치하는지 여부를 검사하여 슬라이스를 동적으로 할당하며, 액세스가 허용되지 않으면 메모리 오류가 발생한다.

  CXL의 지연 시간은 CXL 포트, CXL retimer 및 CXL 스위치 지연 시간이 대부분이며, 아래 그림 7과 같다. (CXL retimer는 각 방향에 지연 시간을 추가하여 CXL/PCIe 신호 무결성을 유지하고 사용되는 장치이다.)

출처

- 그림 1: https://pmem.io/blog/2022/01/disaggregated-memory-in-pursuit-of-scale-and-efficiency/

- 그림 2: CXL specification

- 그림 3, 4, 5: POND - NSDI'23