[논문 리뷰] Electrode: eBPF 기능을 활용한 분산 프로토콜의 성능 향상
Published in
12 min readJan 4, 2024
- 이 글에서는 2023년 USENIX Symposium on NSDI(Networked Systems Design and Implementation)에 발표된 Electrode라는 논문에 대해서 소개합니다.
- 저자의 발표자료와 논문 원본은 https://www.usenix.org/conference/nsdi23/presentation/zhou 에서 확인 가능합니다.
Author
나동준 (https://www.linkedin.com/in/nadongjun/)
목차
- 개요
- 제안된 구조
- 결론
1. 개요
이 논문에서는 Linux 커널의 네트워킹 스택을 기반으로 동작되는 분산 프로토콜의 성능을 향상시키기 위해 eBPF(Extended Berkeley Packet Filter)를 활용한 Electrode에 대해 소개하고 있습니다. 먼저 논문에서 주장하는 내용들을 요약하여 설명하겠습니다.
Motivation:
- 표준 Linux 커널 네트워킹 스택은 CPU 스케일링의 부하 인식, 높은 호환성, 견고한 보안 및 격리 기능 등의 이점으로 알려져 있으며 이로 인해 대부분의 클라우드 환경에서는 Linux 커널을 활용하며 또한 고가용성과 확장성을 위해서 분산 시스템을 사용합니다.
- 그러나 high availability를 보장하기 위해 사용되는 분산 프로토콜의 성능은 사용자 공간과 커널 간의 교차, 커널 네트워킹 스택을 통한 데이터 전송 시 발생되는 지연시간으로 인해 성능이 저하됩니다.
Problems:
- [2]는 분산 시스템의 프로토콜 중 하나인 Paxos에서 발생되는 CPU time 성능 문제를 분석한 결과입니다. 그림에서 보이는 것 처럼 Context switching과 커널의 Network stack에서 주로 발생을 합니다.
- 따라서 분산 시스템에서 성능 향상을 위해서는 사용자 공간과 커널 간의 상호 작용 및 커널 네트워킹 스택을 통한 데이터 이동을 최소화 해야합니다.
Proposed method:
- 본 논문에서 저자들은 이러한 문제를 해결하기 위해서 사용자-커널 교차 및 커널 네트워킹 스택 트래버스에 의한 오버헤드 줄여 성능을 향상 시킨 방법을 제안합니다.
- eBPF 란 User-space에서 구현된 함수들을 커널 내 샌드박스 환경에서 동작하게 하여 커널의 수정 없이 프로그램을 Kernel-space에서 실행하는 기술을 제공합니다.
- 제공되는 주된 기능은다양한 커널 시스템 이벤트에 대한 hook을 제공하며, 이를 활용하여 커널의 동작을 추적하고 조작할 수 있습니다.
- 기존에는 Packet filtering, monitoring 용도로 사용됐지만 최근 논문들에서는 이를 기반으로 한 커널 레벨에서 스토리지, 네트워크 I/O를 감소시키는 연구들이 제안되고 있습니다.
Result:
- 제안된 구조를 기존 Multi-Paxos 프로토콜에 적용한 결과, 처리량이 최대 128.4% 향상되었으며 처리 시간은 41.7% 감소되었습니다.
2. 제안된 구조
해결해야 할 문제점: 사용자 공간과 커널 간의 상호 작용 및 커널 네트워킹 스택을 통한 데이터 이동 문제
- 제안된 구조를 살펴보기 전 기존 솔루션을 먼저 정리하였습니다. Kernel bypassing은 커널을 우회하여 네트워크 스택에 직접 액세스함으로써 위에서 언급한 오버헤드를 줄일 수 있습니다.
- 하지만 일반적인 운영체제의 기능을 사용하는것이 아니므로 안정성과 보안에 영향을 주는 trade-off가 발생하게 됩니다.
- 가상화된 시스템을 기반으로 한 클라우드에서 클라우드 서비스 제공업체는 가상머신의 네트워크 관리 및 보안 기능을 구현하지만 이 기능을 사용할 경우 이를 우회하여 직접적인 네트워크 접근을 허용하게 됩니다.
- 또한 Kernel bypassing은 특정 네트워크 스택과 하드웨어에 최적화되어 있으므로 기술적 호환성 문제가 발생합니다.
- 본 연구에서는 eBPF를 사용하여 어떤 작업이나 함수를 현재 운영체제의 커널로 이동시킵니다. User-space의 프로그램이나 커널 외부에서 수행되는 작업을 eBPF를 사용하여 커널 내에서 수행하도록 합니다.
- 또한 eBPF는 프로그램을 실행하기 전에 컴파일 시 정적인 분석과 여러 제한사항을 적용하여 안전성을 확보합니다. 이는 잘못된 코드나 악성 코드의 실행을 방지하고, 커널의 안정성을 유지하며 다양한 프로그램에 활용될 수 있습니다.
- eBPF의 기능 중 XDP를 사용하여 분산 시스템 노드들이 “패킷을 송수신” 이벤트가 발생할 때를 감지하여 User-Kernel 간 스위치 횟수 감소 및 Networking stack를 건너지 않고 패킷이 송수신 됩니다.
- XDP 에서 제공되는 기능은 다음과 같습니다.
- 1. XDP_DROP: 수신한 패킷을 삭제, 네트워크 스택에 도달하기 전에 최초의 RX(수신) 단계에서 수행
- 2. XDP_PASS: 패킷을 네트워크 스택으로 전달
- 3. XDP_TX: 패킷을 수신된 인터페이스로 재전송, 패킷이 수신된 NIC를 통해 다시 전송되며, 이때 패킷의 내용을 수정할 수 있습니다. 일반적으로 패킷을 수정하고 다시 NIC로 전송하는데 사용
- 4. XDP_REDIRECT: 패킷을 다른 인터페이스로 전달, 네트워크 스택을 무시하고 다른 네트워크 카드 로 패킷을 전달됨
Electrode
- Electrode는 여러 프로토콜 중 Paxos 합의 프로토콜의 최적화를 예를 들어서 적용하였으며 방법은 eBPF를 활용하여 성능에 영향을 주는 여러 작업(메세지 전파, 메세지 응답, 쿼럼 대기)을 커널에 오프로드(User-space -> Kernel space) 하는 것 입니다.
- 테이블에 설명된 것 처럼 3가지 함수가 제공되어 메세지 전파, 응답 대기, 쿼럼 체크를 수행합니다. 해당 함수들은 User-space의 함수들이며 eBPF와 상호작용 합니다.
Electrode offload #1: message broadcasting
- of context switching and stack traversing is linear to # of replicas
Electrode offload #2: fast acknowledging
- incurring twice the kernel latency on the critical path
- non-critical path로 이동시켜 성능 향상(follower들의 빠른 ack)을 목적으로 함
Electrode offload #3: waiting on quorum
- leader recv ACKs from all followers, each incurring kernel overhead
- Leader 노드의 효율적인 쿼럼 체크
Challenge
- 하지만 eBPF와 사용자 공간 간에 커널 안전성을 위한 공유 메모리가 없다는 문제점이 존재합니다. 이러한 설계는 일반적으로 eBPF의 안전성 및 격리를 유지하기 위한 것이며 이로 인해 State synchronization challenge가 발생하게 됩니다.
- 공유 메모리가 없는 경우 커널 레벨인 eBPF에서는 메시지에만 의존하므로 메시지의 도착 순서는 프로토콜 동작에 영향을 줍니다. 이러한 경우들을 non-critical path cases라고 하며 이를 해결하기 위해 아래와 같은 방법으로 eBPF를 적용하였습니다.
*non-critical path cases는 Multi-Paxos 프로토콜에서 상대적으로 중요하지 않은 특정 상황을 의미합니다. 이러한 상황은 주로 레플리카의 실패, 참여, 또는 메시지의 손실/재배열과 관련이 있습니다.
*critical path cases은 분산 프로토콜의 데이터 일관성 문제 등과 같은 치명적인 오류를 의미합니다.
eBPF 맵을 사용하여 ebpf_status, ebpf_view, 그리고 ebpf_seq라는 세 가지 변수를 유지하며, 이러한 변수들은 사용자 공간에서 Multi-Paxos 프로토콜에 의해 현재 프로토콜 상태를 반영합니다.
- 따라서 유저 레벨에서 처리해야만 하는 값인 경우 eBPF에서 유저 레벨로 패킷을 보냅니다. 이 과정에서는 view-change 및 state-transfer 중에는 eBPF가 hook에서 분리됩니다.
- Line 5:
ebpf_status가status_normal이 아닌 경우, 즉 프로토콜 상태가 정상이 아닌 경우에는 패킷을 버립니다. - Line 6:
msg_view가ebpf_view보다 작은 경우, 즉 메시지의 뷰가 현재 eBPF 프로그램이 관리하는 뷰보다 낮은 경우에는 패킷을 버립니다. - Line 7:
msg_view가ebpf_view보다 크거나, 또는msg_seq가ebpf_seq + 1보다 큰 경우, 즉 특정 Critical path의 상황에 해당하는 경우에는 패킷을 사용자 공간으로 전달하여 뷰 변경(view-change) 또는 상태 전송(state-transfer) 프로시저를 실행합니다. - Line 8:
msg_seq가ebpf_seq + 1보다 작은 경우, 즉msg_seq가 현재ebpf_seq보다 작은 경우에는 ACK를 응답합니다. 이는 타임아웃으로 인해 재전송된 준비(preparation) 메시지의 경우를 고려한 것입니다. - Line 10: 위의 조건을 통과한 경우, 즉
msg_seq가ebpf_seq + 1인 경우에는 로그에 패킷을 추가하고,ebpf_seq를 증가시킨 후 ACK를 응답합니다.
위의 코드 및 설명에 따르면, 해당 방식은 상태 동기화(State synchronization) 대한 해결책으로 사용되고 있습니다. Multi-Paxos 프로토콜은 분산 시스템에서 상태를 동기화하는 중요한 작업을 수행합니다. 이때 발생할 수 있는 다양한 상황에 대응하여 안정적이고 효율적인 상태 동기화를 달성하기 위해 위의 코드는 여러 기능과 메커니즘을 제공하고 있습니다.
위 상황들은 “non-critical path cases”이며 eBPF와 분리되어 작업됩니다. 코드에서 설명한 것과 같이 발생될 경우 eBPF가 커널에서 detach된 후 User-space에서 view-change 또는 state-transfer 절차를 실행합니다.
이후 ebpf_status, ebpf_view, ebpf_seq를 업데이트한 뒤 eBPF 를 다시 커널에 attach 합니다.
Summary
Replica Failures or Joins :
- 레플리카의 실패 또는 참여와 같은 상황에 대비하여 코드는 해당 패킷을 버리도록 지정합니다.
- 이 상황을 non-critical path으로 간주하는 이유는 레플리카에서 실패 또는 참여는 빈번하게 발생할 수 있으며 핵심 로직과는 직접적인 관련이 적기 때문입니다. 또한 분산 환경이므로 위 상황은 자동으로 복구가 가능합니다.
Lost/Reordered Messages :
- 메시지의 손실 또는 재배열과 같은 상황에 대한 처리로 패킷을 사용자 공간으로 전달하여 뷰 변경(view-change) 또는 상태 전송(state-transfer) 프로시저를 실행합니다.
Handling Retransmitted Preparation Messages :
- 메시지가 타임아웃으로 인해 재전송되었을 경우, 해당 상황에 대한 처리로 ACK를 응답합니다.
이러한 방식을 통해 Multi-Paxos 프로토콜에서 발생할 수 있는 다양한 한계의 일부를 해결하고 상태 동기화를 효과적으로 관리할 수 있습니다.
3. 결론
- Electrode는 커널 내 eBPF 기반 패킷 처리를 사용하여 분산 프로토콜의 성능을 향상시키며 리눅스 네트워킹 스택의 장점을 유지하며 분산 프로토콜의 성능의 핵심 동작인 브로드캐스팅, 응답 ,쿼럼 대기를 최적화합니다.
- Multi-Paxos 프로토콜에 Electrode를 적용하였을 때 최대 128.4% 높은 처리량과 41.7% 낮은 지연 시간을 달성하며 유의미한 성능 향상을 보였습니다.
- Electrode에서 eBPF 기반 최적화 설계는 표준 리눅스 네트워킹 스택 유지하며 성능을 높일 수 있다는 점에서 분산 시스템에서 최적화에 대한 새로운 관점을 알게되었습니다.
- 특히 eBPF는 이번 논문을 읽으며 처음 알게되었는데 커널 영역에서 코드를 실행하는 비교적 간단한 방법이 있고 모니터링 뿐만 아니라 여러 애플리케이션을 개발하는데 사용할 수 있다는 것이 흥미로웠습니다.
Appendix
Reference
[1–9] https://www.usenix.org/conference/nsdi23/presentation/zhou
