NSDI 2024 Yang Zhou, Xingyu Xiang, Matthew Kiley, Sowmya Dharanipragada, Minlan Yu
개요
Kernel networking stack에 적용하기 위한 Extensible kernel메커니즘을 eBPF로 구현하여서, XDP로는 표현할 수 없는 복잡한 Mechanisms을 커널에 구현할 수 있도록 하였다.
Motivation
CXL과 같은 Fast distributed in-memory transaction이 가능해지는 현재, Storage가 아닌 Networking stack에 Bottleneck이 옮겨가고 있다.
Impotance
기존에는 DPDK와 같은 Kernel stack bypass기법들이 사용되었으나, 그들은 Security, Isolation, Protection, Maintainability, Debuggability측면에서 문제가 있었다. 특히 DPDK과 같은 경우에는 Polling을 사용하기 때문에 CPU Utilization에서도 문제가 생긴다. 이를 위해서 Extensible kernel은 해결책이 될 수 있다.
이 논문은 Key-Value store를 통해서 User-level의 Policy engine과 Kernel-level의 Networking Engine이 Transation을하고 있는 상황을 상정하였다.
Challenge
Distributed system에서 Transation을 구현하기 위해서는 3개의 고려해야할 점이 있다. 1) Lock manager를 통해서 Lock획득 2) Key-values를 Key-value store에서 가져오고, Local update 수행 3) Key-value store update를 log manager에 통보후, Key-value local updates를 global로 반영. 그러나 Naive한 eBPF는 Constrained programming model이 있기 때문에, 위의 3개를 구현하는 것은 Challenging하다.
Main Idea
Transation과 관련된 Data structure를 다음 세개의 원칙에 따라서 재구성하였다.
- eBPF has limited scalability primitives: eBPF atomics를 통해서 lock sharing메커니즘을 구현
- eBPF cannot dynamically updates the memory: Set-associative cache를 사용해서 small key-value는 커널에, large key-value는 유저에 저장
- Log manager를 위해서 Efficient한 per-CPU log buffer를 구현
Design
- 자주 요청되는 경로를 커널로 오프로드 (작은 패킷)
- DINT는 빈번한 경로의 상태와 작업을 커널로 오프로드하여 커널 스택의 오버헤드를 피함
- 사용자 공간을 백업으로 활용 (큰 패킷)
- DINT는 드물게 발생하는 경로의 상태와 작업을 사용자 공간에서 처리
- DINT 사용자 수준 클라이언트는 UDP 소켓을 통해 커널에서 직접 처리할 수 없는 일부 트랜잭션 요청을 수신하고 처리
FaSST
이 논문은 Transation, 그중에서도 FaSST에 초점을 맞추었다. FaSST Transation알고리즘은 다음과 같이 작동한다. FaSST의 각각의 Transation은 set of keys to read (i.e., write-set), set of key-values to write (i.e., write-set) 그리고 Transaction cooredinator로 구성된다. (이해는 Fasst OSDI논문 읽어야 해서...). 핵심은 위와 같은 Transation알고리즘은 locking mechanisms, efficient key-value stores, and log manager가 필요하다는 사실이다.
Lock manager
Lock manager은 Handling multiple transaction clients concurrently access individual key-values하기 위해서 사용된다. 이를 위해서 eBPF의 한계인 Dynamic memory allocation과, spin lock and atomic operation only의 문제를 해결하기 위해서 다음의 방식을 제안하였다. 구체적으로 Read-write locking을 어떻게 구현하였는지는 논문을 참고.
- Lock sharing: Lock을 획득하기 위해서 Lock를 가져오기 위해서 Hash를 돌리는데, 만약 Hash collision이 발생할 경우, 무시하고 같은 hash값을 가지는 Lock을 가져오도록 하였다. 그러나, 이떄 Deadlock이 발생할 수 있다는 문제가 생겼다. 예를 들어서, 만약 두 오퍼레이션이 서로 의존적인데, 같은 hash값인 경우에 문제가 생긴다. 이경우에는 Lock manager가 two exclusive lock acquiring을 감지하여 위의 문제를 예방하였다.
- Atomic operation: 모든 lock구현은 BPF atomics를 이용하여서 구현하였음
Key-Value Store
key value store은 fixed-sized eBPF MAP을 이용하여서 구현하였다. Dynamic allocation이 안된다는 단점을 극복하기 위해서, 새롭게 Data structure를 정립하였다. 구체적인 구현은 논문 참고.
Log Manager
eBPF MAP을 사용하여서 circular log buffer를 구현하였다. 정확회는 BPF_MAP_TYPE_PERCPU_ARRAY를 이용하여서 구현하였다.
Evaluation
DPDK를 이용한 Caladian, Baseline인 Kernel UDP와 비교하여서 확연히 증가된 Scalability성능을 보였다.
Conclusion
DINT는 Distributed system의 핵심중 하나인 Transaction을 eBPF를 통해서 구현하는 방법을 탐색한 논문이다. eBPF로 Transaction기능을 Offloading하기 위해서 생길 수 있는 문제를 잘 정리하여서 탐색하였고, Promising한 Solution과 확실한 성능 증가를 보였다. eBPF의 수정을 가하지 않았기 때문에 바로 사용할 수 있는 엔지니어적인 가치가 큰 논문이다. 그러나, eBPF에는 DINT에서 제시하는 문제를 해결하기 위한 다양한 방법들이 이미 존재한다. BPF_ARENA는 Dynmaic allocation의 한계를 극복할 수 있으며, Log manager에서 HASH_MAP과 같은 기존의 eBPF기반 방식을 사용하지 않은 이유가 명확하지 않다. 또한 Try-lock기반의 Locking mechanisms은 추가적인 오버헤드를 가져올 것으로 생각된다 (Evaluation에서는 드러나지 않지만). 이러한 Mitigation efforts를 소개한다면 보다 더욱 Concrete한 논문이 될 수 있을 것이라 생각한다.