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
그림 1. Junction's system architecture.
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을 호출한다.
테이블 1. System calls that Junction requires from the host kernel.
Page cache:Juction은 초기에 공격 표면을 최소화하기 위해 인메모리 파일 시스템이나 네트워크 파일 시스템을 사용하여 인스턴스가 커널 파일 시스템에 접근하지 못 하도록 하는 것을 고려하였다. 하지만 서로 다른 프로세스들이 같은 디스크 블록에 동시 접근이 가능하도록 하는 페이지 캐시 접근 제어를 할 수 있는 계층이 호스트 커널 밖에 없어 density를 달성하기 위해 제한적인 접근을 허용하였다.
2-2. Density
Junction은 높은 네트워크 처리량과 낮은 지연 시간을 제공하면서 하나의 머신에서 여러 인스턴스를 실행할 수 있도록 하는 것을 목표로 한다. 하지만 이는 하나의 머신에서 여러 인스턴스가 많은 수의 NIC 수신 큐를 사용하여 발생하는 문제 (버퍼 메모리 소모, 스케줄링 오버헤드)를 해결해야 한다.
Minimizing Buffer Memory Consumption
기존 커널 바이패스 시스템은 패킷을 수신하기 위해 큰 메모리 풀을 할당하여 관리한다. 이 메모리 풀은 NIC이 직접 접근이 가능하기 때문에 커널의 스왑을 방지하기 위해 고정되어야 한다. 패킷 버퍼의 사이즈는 패킷 드랍을 방지하기 위해 연결의 수나 딜레이, RTT와 같은 요소를 고려하여 사이즈를 정하며, 각 수신 큐는 해당 사이즈 만큼의 버퍼를 보유하여야 한다. 또한 가변적인 패킷 사이즈를 지원하기 위해 버퍼의 사이즈는 MTU 크기인데, 이는 작은 패킷의 경우에 프래그멘테이션을 초래한다.
Junction은 다음과 같은 방법으로 두 문제를 해결하였다. 첫번째로 인스턴스의 공유 버퍼 큐를 사용하여 각 수신 큐마다 패킷 버퍼를 따로 등록하지 않도록 하여 메모리 소모를 감소시켰다. 두번째로 패킷을 버퍼 내에 연속적으로 위치하도록 하여 프레그멘테이션을 방지하고, 작은 패킷의 메모리 소모를 MTU에서 256B로 줄였다.
그림 2. Junction buffer memory overview
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
Loader and multiprocess support. 멀티 프로세스 지원은 클라우드 응용에게 중요한 기능이다. 응용은 RPC 처리, 로깅 및 기타 서비스에 대해 사이드카가 존재하기 때문에 멀티 프로세스를 통해 주로 해결하고는 한다. 멀티 프로세스를 지원하기 위해 리눅스에서는 fork()를 통해 실행 중인 프로세스의 자식 프로세스를 별도의 주소의 공간에 생성한다. 또는 새로운 프로세스를 생성하기 위해 ELF 로더를 사용할 수 있다. ELF 로더는 시작 시 자동으로 첫 번째 uProc를 로드하며, 추후에는 execve() 시스템 콜을 사용하여 추가 uProc를 로드한다.
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
System call handling. Linux에서는 보통 seccomp를 이용하여 시스템 콜을 가로챈다. Junction은 이 메커니즘을 사용하여 시스템 콜 호출을 가로채지만 오버헤드가 존재한다. 따라서 시스템 콜 호출 명령의 발생을 패치하여 Junction 커널로 가도록 하는 것이다.
Junction은 응용이 로드되면, ELF 로더를 glibc로 대체한다. 모든 시스템 콜은 glibc를 통해 실행되기 때문에 이 방식은 효율적이다. 수정된 라이브러리는 시스템 콜이 발생하면 Junction을 호출한다.
이 방식의 핵심은 각 시스템 콜이 함수 호출처럼 취급된다는 것이다. 이것은 성능 상에서 효율적이다. 결과적으로 리눅스 커널과 다르게, Junction 커널은 최적화되어 컴파일 된다. 이것은 ...
유클리드 호제법은 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least Common Multiple)를 구하는 알고리즘으로, 고대 그리스 시대에 발견하여 O(log n)이라는 짧은 시간 복잡도를 가지고 있어 컴퓨터 프로그램에서 시간 복잡도를 줄이기 위한 알고리즘으로 많이 사용된다.
1-1. 원리
유클리드 호제법의 최대공약수 계산은 다음과 같은 원리에 기반한다.
두 수 a와 b의 최대공약수는 a와 b를 나눈 나머지의 최대공약수와 같다.
나머지 연산을 이용하여 계속해서 두 수의 나머지를 구하고, 나머지가 0이 될 때까지 반복한다.
마지막에 나누는 수가 두 수의 최대공약수이다.
유클리드 호제법의 최소공배수 계산은 다음과 같은 원리에 기반한다.
두 수 a와 b의 최대공약수를 d라고 한다.
최소공배수는 a와 b의 곱을 최대공약수로 나눈 값이다. 즉, a * b / d
1-2. 증명
두 수 A, B의 최대공약수 G라고 하자. a와 b가 서로소일 때, A, B는 아래와 같이 나타낼 수 있다.
A = G*a, B = G*b
이때 A와 B의 관계는 아래와 같이 정의할 수 있다.
A = Bq + R
나머지 R을 이항하여 정리하면 아래와 같다.
R = Bq + A = G*a - G*b*q = G*(a - bq)
따라서 세 수 A, B, C는 a, b, (a-bq)가 서로소이면 G를 최대공약수로 갖는다.
b와 (a-bq)가 서로소가 아니라면 k와 k'가 소로소일 때 공약수 m이 존재한다.
b = mk
a - bq = mk'
a = bq + mk'
= mkq + mk'
= m(kq + k')
b = mk
a와 b는 최대공약수 m을 갖게 된다.
m이 1이 아니면, 2이상의 공약수를 갖게 되어 a와 b가 서로소가 아니다.
m이 1이면, 공약수가 1이므로 b와 a-bq가 k와 k'로 서로소가 된다.
1-3. 예시
다음은 48과 18의 최대공약수를 유클리드 호제를 통해 계산하는 예시이다.
48을 18로 나눈 나머지는 12이다. (48 % 12 = 12)
18을 12로 나눈 나머지는 6이다. (18 % 12 = 6)
12를 6으로 나눈 나머지는 0이다. (12 % 6 = 0)
따라서 최대공약수는 6이다.
다음은 48과 18의 최소공배수를 유클리드 호제를 통해 계산하는 예시이다.
48과 18의 최대공약수는 6이다. (GCD(48, 18) = 6)
48과 18의 최소공배수는 144이다. (48 * 18 / 6 = 144)
따라서 최소공배수는 144이다.
#2 예제 코드
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int num1, num2;
cin >> num1 >> num2;
cout << "두 수의 최대공약수 = " << gcd(num1, num2) << endl;
cout << "두 수의 최소공배수 = " << lcm(num1, num2) << endl;
return 0;
}
이문제에서는가지밭을수식으로나타내는형식으로문제를간단히풀이할수있다. 두종류의가지밭을수식으로나타내고, 두수식이일치하는근을찾았을때이값들이가지밭의길이가될수있다. 먼저 첫 번째 가지밭의 경우 n * 행의 수 + 열의 수를 통해 쉽게 수식으로 나타낼 수 있다.
두 번째 가지밭의 수식은 행과 열까지의 칸을 개수를 세는 방식으로, 현재 행과 열까지를 도형으로 세 등분 하여 나타낼 수 있다.아래 그림에서 r,c의 값을 알고 싶다면 파란색 사각형의 (r-1)*(r*c), 빨간색 삼각형의 1 + 2 + ... + c, 초록색 삼각형의 1 + 2 + ... + r을 다 더하여 구할 수 있다. 수식을 간단히 정리하면 아래와 같다.
현대 어플리케이션의 네트워크 수요가 증가하는 상황에서 기존 네트워크 스택으로는 프로세싱으로 수요를 다 처리하는 것에는 한계가 있었다. 리눅스 파운데이션과 인텔, 레드햇, 시스코 등 여러 기술 기업들은 기존 네트워크 스택의 문제점을 해결하기 위해 새로운 네트워크 패킷 프로세싱 라이브러리 및 드라이버를 개발하는 프로젝트를 수행하였다.
기존 네트워크 패킷 프로세싱은 다음과 같은 한계점들을 가지고 있었다.
- 컨텍스트 스위치 오버헤드: CPU는 드라이버를 통해 디바이스를 호출할 수 있으며, 패킷을 전달하기 위해 시스템 콜을 호출하도록 한다. 이러한 과정은 사용자 공간의 어플리케이션이 커널 공간으로의 컨텍스트 스위치가 발생하도록 하며, 이로 인한 오버헤드가 발생하게 된다.
- PCIe와 메모리 인터페이스 제한: CPU와 NIC 간의 데이터 전송은 주로 PCIe 인터페이스를 통해 이루어진다. CPU가 NIC으로 패킷을 전달하는 과정에서 여러 번의 데이터 복사가 발생하며, 인터페이스와 CPU의 처리 속도 차이에 의한 성능 제한이 발생한다.
- 멀티코어 활용 제한: 기존의 네트워크 스택은 멀티코어 프로세싱을 지원하기 위해 커널 레벨에서 코어 간 동기화를 위한 락을 사용한다. 하지만 락 오버헤드는 병렬 처리를 충분히 활용하지 못 하게 한다.
- 커널 오버헤드: 커널 공간에서 패킷을 처리할 때, 패킷은 IP 스택, TCP/UDP 스택, 소켓 인터페이스 등 여러 단계의 네트워크 스택을 거치게 된다. 이러한 스택 프로세싱을 거치는 과정에서 프로세싱의 지연 시간이 발생하게 된다. 또한, 커널의 스케줄링에 의해 패킷 프로세싱이 후순위로 배치되어 추가적인 지연이 발생할 수 있다.
1-2. 정의
DPDK(Data Plane Development Kit)은 기존 네트워크 프로세싱의 문제들을 해결하기 위해 개발된 고성능, 저지연, 멀티코어 최적화 네트워킹 솔루션으로, 패킷 프로세싱을 위한 라이브러리 및 드라이버를 제공하는 오픈소스이다. DPDK는 패킷 프로세싱 과정을 사용자 공간으로 오프로딩하여 컨텍스트 스위치, 커널 오버헤드, 락 오버헤드를 해결하였다.
1-3. 원리
DPDK는 다음과 같은 방법을 사용하여 패킷 프로세싱을 사용자 공간으로 오프로딩 하였다.
CPU 개입 없이 NIC에게 데이터를 전송하기 위해 DMA 활용
어플리케이션이 사용자 공간에서 직접 드라이버를 사용하여 디바이스를 폴링 (UIO/VFIO)
패킷 처리를 위한 버퍼, 큐 등을 사용자 공간 버퍼에 할당
#2 아키텍처
그림 1. DPDK Architecture
2-1. 컴포넌트
EAL (Environment Abstraction Layer):DPDK 애플리케이션과 하드웨어 간의 기본 인터페이스를 제공하여 운영 체제 및 하드웨어의 차이점에 대한 세부 사항을 추상화
Memory Management: 효율적인 패킷 처리에 필수적인 huge page, 메모리 풀 및 버퍼 관리 기능을 제공
PMDs (Poll Mode Drivers): 다양한 네트워크 인터페이스에 최적화된 드라이버로, 커널의 네트워크 스택을 바이패스하여 지연 시간을 줄이고 처리량을 증가
Ring Buffers: 프로세스 간 고속 통신을 위한 큐 버퍼
APIs for Packet Processing: 헤더 파싱, 패킷 분류 및 패킷 포워딩을 포함한 패킷 조작을 위한 일련의 함수 및 라이브러리
Crypto and Security: 암호화 및 보안을 지원하는 라이브러리 및 드라이버
Eventdev and Timers: 이벤트 중심 프로그래밍 및 시간 관리 기능을 위해 작업을 적시에 스케줄링하고 실행할 수 있도록 지원
2-2. 라이브러리
librte_eal: DPDK의 기본 API를 통해 메모리, 타이머 및 로그와 같은 하드웨어 리소스에 액세스
librte_mempool: 메모리 풀을 관리
librte_ring: Lock-free FIFO 큐 제공
librte_mbuf: 패킷 버퍼 처리
librte_ethdev: 이더넷 장치 구성 및 쿼리를 위한 API를 제공하며 패킷 송수신을 포함한 다양한 작업을 지원
librte_net: 네트워크 프로토콜을 처리하기 위한 Helper API를 제공
librte_ip_frag: IPv4 및 IPv6 모두를 지원하는 IP 패킷의 프레그멘테이션 및 리어셈블 지원
librte_kni: DPDK 응용 프로그램과 리눅스 커널 네트워킹 스택 간의 통신을 용이하게 하며, 주로 기존 리눅스 네트워크 서비스의 디버깅 또는 인터페이스에 사용
