RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF

이 논문은 eBPF 와 io_uring 기술을 활용하여 LSM-트리 기반 데이터베이스의 컴팩션 과정에서 발생하는 시스템 콜 오버헤드를 대폭 줄이고, RocksDB 대비 스루풋을 최대 75% 향상시키며 지연 시간을 40% 감소시킨 'RESYSTANCE'를 제안합니다.

핵심

🍽️ 비유: 고급 레스토랑의 주방 (데이터베이스)

데이터베이스는 거대한 레스토랑이고, LSM-Tree라는 기술은 이 레스토랑이 주문을 처리하는 방식입니다.

1. 메모리 (Memtable): 주방 앞쪽의 조리대입니다. 요리사 (사용자) 가 주문 (데이터 입력) 을 받으면 일단 조리대에 임시로 올려둡니다.
2. 디스크 (SSTable): 냉장고나 창고입니다. 조리대에 쌓인 주문들은 일정량이 모이면 한 번에 정리해서 창고로 옮겨야 합니다.
3. 컴팩션 (Compaction): 이 과정이 바로 창고 정리입니다. 여러 번 정리된 창고 자료들이 섞여 있으면 찾기 어렵고 공간도 비효율적이죠. 그래서 비슷한 자료들을 묶어서 다시 정리하는 작업입니다.

🚧 문제점: "지나친 행정 절차" (System Call)

기존의 방식 (RocksDB 등) 은 이 '창고 정리' 작업을 할 때 다음과 같은 비효율적인 과정을 거칩니다.

• 상황: 주방장 (데이터베이스 프로그램) 이 창고에서 책을 한 권 꺼내려면, 매번 창고 관리실 (커널/OS) 에 "이 책 좀 꺼내주세요"라고 요청해야 합니다.
• 문제: 창고 정리 작업은 수천, 수만 권의 책을 한 번에 정리해야 합니다. 그런데 **책 한 권씩 꺼낼 때마다 관리실과 주고받는 서류 작업 (시스템 호출)**을 반복하다 보니, 실제 책 정리 시간보다 서류 작업에 쓰는 시간이 더 길어집니다.
• 결과: NVMe SSD 라는 초고속 창고 (하드웨어) 가 있는데도, 서류 작업 (소프트웨어) 때문에 속도가 느려집니다.

💡 해결책: RESYSTANCE (저항)

이 논문은 이 문제를 해결하기 위해 RESYSTANCE를 제안합니다. 이름처럼 "시스템 호출이라는 관료주의에 저항한다"는 뜻입니다.

1. eBPF: "주방장에게 직접 권한을 부여하다"

기존에는 주방장이 창고 관리실 (OS) 에 요청해야 했지만, eBPF라는 기술을 이용해 주방장에게 직접 창고 관리실의 열쇠를 줍니다.

• 비유: 이제 주방장은 관리실의 허가 없이도, **주방 내부 (커널 공간)**에서 바로 창고 정리 작업을 할 수 있게 됩니다.
• 효과: "이 책 꺼내줘"라고 요청하는 서류 작업이 99% 사라집니다.

2. io_uring: "한 번에 여러 개 처리하는 컨베이어 벨트"

기존에는 한 번에 한 권씩 책을 꺼냈다면, io_uring은 한 번에 여러 권을 동시에 꺼내는 컨베이어 벨트를 도입합니다.

• 비유: 주방장이 창고 관리실에 "책 100 권 다 꺼내줘"라고 한 번에 요청하면, 관리실은 그걸 한 번에 처리해서 가져옵니다.
• 효과: 창고 정리 (컴팩션) 속도가 2 배 (50% 단축) 빨라집니다.

🚀 결과: 얼마나 빨라졌나요?

이 기술을 적용한 실험 결과, 다음과 같은 놀라운 변화가 있었습니다.

• 서류 작업 (시스템 호출): 99% 감소 (거의 사라짐)
• 정리 시간 (컴팩션): 50% 단축
• 레스토랑의 처리 능력 (처리량): 최대 75% 증가 (손님이 더 많이 들어와도 주문이 밀리지 않음)
• 대기 시간 (지연 시간): 40% 감소 (주문이 훨씬 빠르게 나옴)

🌟 핵심 요약

이 연구는 하드웨어를 바꾸지 않고, 소프트웨어의 '불필요한 절차'만 없애서 데이터를 훨씬 빠르게 처리하는 방법을 찾았습니다.

• 기존: "하드웨어가 느려서 속도가 안 나옵니다." (아님)
• 새로운 발견: "하드웨어는 빠른데, 소프트웨어가 너무 많은 서류 작업을 해서 속도가 느려졌습니다."
• 해결: eBPF와 io_uring을 이용해 그 서류 작업을 없애니, 숨겨져 있던 하드웨어의 진짜 성능이 발휘되었습니다.

마치 **고속도로 (하드웨어)**가 있는데, 휴게소에서 매번 교통카드를 찍는 절차 (소프트웨어) 때문에 차가 느리게 가는 상황을, **자동 통행료 징수 시스템 (RESYSTANCE)**으로 바꾸어 차가 멈추지 않고 달리게 만든 것과 같습니다.

기술 요약

1. 문제 정의 (Problem Definition)

• I/O 병목의 이동: NVMe SSD 와 같은 초고속 저장장치의 등장으로 하드웨어적 병목이 해결되면서, I/O 성능의 한계점이 하드웨어가 아닌 소프트웨어 스택 (OS 커널 및 시스템 콜) 으로 이동했습니다.
• LSM-tree 의 시스템 콜 과부하: RocksDB, LevelDB 등 LSM-tree 기반 NoSQL 데이터베이스는 메모리 (Memtable) 에 쓰기를 버퍼링하고 디스크 (SSTable) 로 푸시하며, 백그라운드에서 데이터를 병합 (Compaction) 하는 구조를 가집니다.
  • 핵심 문제: Compaction 과정은 수천 개의 SSTable 블록을 반복적으로 읽어야 하므로, 매 블록 읽기마다 pread() 시스템 콜이 발생합니다.
  • 성능 저하: 이러한 빈번한 시스템 콜 호출과 커널 - 사용자 공간 간의 컨텍스트 스위칭이 CPU 사이클을 낭비하고, 실제 디스크 I/O 성능을 활용하지 못하게 만드는 주요 병목이 됩니다.
• 기존 해결책의 한계:
  • 커널 바이패스 (Kernel Bypass, 예: SPDK): 시스템 콜을 완전히 제거하지만, 파일 시스템을 우회해야 하므로 기존 데이터베이스 아키텍처를 대폭 수정해야 하며 유지보수 비용이 높고 호환성 문제가 발생합니다.
  • 기존 커널 최적화: 커널 내부 로직을 수정하는 방식은 이식성이 낮고 안정성 리스크가 큽니다.

2. 제안 방법론 (Methodology: RESYSTANCE)

저자들은 eBPF (extended Berkeley Packet Filter) 와 io_uring 을 결합하여, LSM-tree 의 Compaction 로직 중 I/O 관련 핵심 부분을 커널 내부로 이동시키는 프레임워크 RESYSTANCE 를 제안합니다.

• 핵심 아이디어:

  1. eBPF 를 통한 커널 내 로직 실행: Compaction 의 핵심인 '데이터 블록 읽기'와 '병합 정렬 (Merge-sort)' 로직을 eBPF 프로그램으로 커널 공간에 주입합니다.
  2. io_uring 을 통한 비동기 I/O: 커널 내부에서 io_uring 을 사용하여 여러 데이터 블록을 비동기적으로 병렬로 읽습니다.
  3. 시스템 콜 제거: Compaction 과정 중 발생하는 수천 개의 pread() 시스템 콜을 제거하고, 커널 내부에서 직접 I/O 를 처리하여 사용자 - 커널 간 전환 (Transition) 을 최소화합니다.

• 아키텍처 세부 사항:

  • SST-Map: Compaction 에 필요한 SSTable 의 메타데이터 (블록 오프셋, 크기 등) 를 사용자 - 커널 공유 메모리에 매핑하여 eBPF 프로그램이 접근할 수 있도록 합니다.
  • 작동 흐름:
    1. Compaction Iterator 가 ReadNextKV 를 호출하면, RESYSTANCE 컨트롤러가 io_uring 을 통해 필요한 데이터 블록들을 커널 메모리에 비동기적으로 로드합니다.
    2. eBPF 프로그램이 로드된 데이터를 받아 Merge-sort 를 수행하고 결과를 커널 버퍼에 씁니다.
    3. 최종적으로 생성된 데이터는 기존 RocksDB 의 WriteKV 경로를 통해 디스크에 기록됩니다 (쓰기 작업은 시스템 콜 오버헤드가 상대적으로 적어 기존 방식을 유지).
  • 안정성 보장: eBPF 검증기 (Verifier) 를 수정하여 Compaction 로직에 필요한 커널 메모리 접근을 허용하되, 무한 루프나 잘못된 메모리 접근을 방지하는 안전 장치를 강화했습니다.

3. 주요 기여 (Key Contributions)

1. 병목 원인 규명: LSM-tree 기반 NoSQL 에서 Compaction 이 전체 시스템 콜의 99% 이상 (pread 위주) 을 차지하는 주요 성능 병목임을 정량적으로 분석했습니다.
2. RESYSTANCE 프레임워크 제안: 하드웨어 수정이나 LSM-tree 구조 변경 없이, eBPF 와 io_uring 만을 활용하여 Compaction 의 I/O 로직을 커널로 오프로딩하는 최초의 시스템을 구현했습니다.
3. 비침습적 최적화: 기존 데이터베이스 엔진 (RocksDB) 의 아키텍처를 변경하지 않고도, 커널 내부에서 Compaction 을 가속화하여 소프트웨어 스택 오버헤드를 획기적으로 줄였습니다.

4. 실험 결과 (Results)

RocksDB v10.1.3 을 기반으로 db bench, YCSB, Sysbench(OLTP) 워크로드를 통해 평가했습니다.

• 시스템 콜 감소: Compaction 중 시스템 콜 호출 횟수가 평균 99% 감소했습니다.
• Compaction 시간 단축: Compaction 실행 시간이 50% 단축되었습니다.
• 처리량 (Throughput) 향상:
  • Write-intensive (FillRandom): 최대 75% 의 처리량 향상.
  • Mixed OLTP (Read-Write): 22% 의 처리량 향상.
• 지연 시간 (Latency) 개선:
  • P99 쓰기 지연 시간이 최대 40% 감소했습니다.
  • Write Stall(쓰기 정지) 현상이 완화되어 읽기 성능도 안정화되었습니다.
• 기타 비교:
  • 기존 RocksDB 대비 성능이 우수하며, 커널 바이패스 방식인 SPDK 보다 파일 시스템 기능 (캐싱, 스케줄링 등) 을 유지하면서 더 나은 성능을 보여주었습니다.
  • eBPF 검증 오버헤드는 최소화되었으며, 선형 검색과 Min-heap 검색 알고리즘을 상황에 따라 선택하여 최적화했습니다.

5. 의의 및 결론 (Significance)

• 소프트웨어 스택 최적화의 새로운 패러다임: 하드웨어 가속기 (FPGA, GPU 등) 나 커널 바이패스 (SPDK) 와 같은 무거운 변경 없이, eBPF라는 현대적인 커널 기술을 활용하여 기존 데이터베이스의 성능 한계를 돌파할 수 있음을 증명했습니다.
• LSM-tree 의 잠재력 해방: LSM-tree 가 가진 높은 쓰기 성능을 저해하던 Compaction 과정의 소프트웨어적 비효율성을 제거함으로써, NVMe SSD 의 초고속 성능을 데이터베이스 레이어에서 온전히 활용할 수 있게 했습니다.
• 실용성: 기존 데이터베이스 엔진을 재설계하지 않고도 적용 가능하므로, 실제 산업 환경 (RDBMS, NoSQL 등) 에 도입하기 용이하며 유지보수 비용이 낮습니다.

요약하자면, RESYSTANCE는 LSM-tree 기반 데이터베이스의 Compaction 과정에서 발생하는 과도한 시스템 콜 오버헤드를 eBPF 와 io_uring 을 통해 해결함으로써, 하드웨어 변경 없이 소프트웨어 스택 최적만으로 극적인 성능 향상을 이끌어낸 획기적인 연구입니다.