O^3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading

이 논문은 컴퓨팅 노드의 메모리 제약과 느린 플러시 문제를 해결하기 위해 분산 메모리를 활용한 3 단계 오프로딩 (메모리 테이블, 플러시, 컴팩션) 과 샤드 수준 최적화, 적응형 읽기 위임 메커니즘을 도입한 새로운 LSM-KVS 아키텍처인 O3-LSM 을 제안하며, 이를 통해 기존 시스템 대비 쓰기 및 읽기 처리량과 지연 시간 측면에서 획기적인 성능 개선을 달성함을 보여줍니다.

핵심

O3-LSM: 클라우드 데이터 저장을 위한 '스마트 물류 시스템'

이 논문은 클라우드 환경에서 데이터를 저장하고 관리하는 기술 (LSM-KVS) 의 성능을 획기적으로 개선한 O3-LSM이라는 새로운 시스템을 소개합니다.

기존의 방식은 마치 작은 창고 (컴퓨터) 에서 물건을 쌓아두다가, 창고가 꽉 차면 바로 트럭 (네트워크) 을 타고 먼 곳의 대형 창고 (저장소) 로 보내는 방식이었습니다. 하지만 이 방식에는 두 가지 큰 문제가 있었습니다.

1. 작은 창고가 너무 빨리 꽉 찬다: 데이터를 빠르게 받아주려면 임시 창고 (메모리) 가 커야 하는데, 클라우드 컴퓨터는 메모리가 작습니다.
2. 트럭이 너무 느리다: 임시 창고에서 대형 창고로 물건을 옮기는 과정 (네트워크 전송) 이 느리고, 트럭이 막히면 전체 작업이 멈춥니다.

O3-LSM 은 이 문제를 해결하기 위해 세 가지 층 (Layer) 으로 이루어진 혁신적인 물류 시스템을 제안합니다.

---

🏗️ O3-LSM 의 핵심 아이디어: 3 단계 오프로딩 (Three-Layer Offloading)

O3-LSM 은 데이터를 보낼 때 바로 먼 곳으로 보내지 않고, 중간에 **공유된 거대한 임시 창고 (분산 메모리, DM)**를 활용합니다. 이를 통해 다음과 같은 3 단계를 거칩니다.

1 단계: 스마트한 임시 창고 확장 (Memtable Offloading)

• 비유: 기존에는 작은 책상 (컴퓨터 메모리) 위에 서류를 쌓다가 꽉 차면 바로 택배로 보냈습니다. O3-LSM 은 책상 옆에 **공유된 거대한 선반 (분산 메모리)**을 설치합니다.
• 혁신: 서류를 선반으로 옮길 때, 기존 방식은 서류를 뜯어서 다시 정리해야 했지만 (포인터 재구성), O3-LSM 은 서류를 통째로, 그리고 정리된 그대로 선반에 올립니다.
• 효과: 서류를 옮기는 시간이 획기적으로 줄어들고, 책상이 꽉 차서 작업이 멈추는 현상 (Write Stall) 을 방지합니다.

2 단계: 협력하는 물류 팀 (Collaborative Flush Offloading)

• 비유: 서류를 선반에서 대형 창고로 보내는 '배송' 작업을 원래 책상 주인이 혼자 해야 했습니다. 하지만 책상 주인은 바빠서 배송이 느려졌습니다.
• 혁신: O3-LSM 은 전체 물류 센터의 직원들 (다른 컴퓨터나 메모리 노드) 이 협력하게 합니다. "누가 지금 비어있고 배송이 빠르냐?"를 실시간으로 확인하여, 가장 적합한 직원이 서류를 가져가서 대형 창고로 보냅니다.
• 효과: 특정 컴퓨터의 부하를 분산시켜, 배송이 막히지 않고 항상 빠르게 처리됩니다.

3 단계: 조각조각 나누어 보내기 (Shard-Level Optimization)

• 비유: 100kg 짜리 무거운 상자를 한 번에 트럭에 싣는 대신, 작은 상자 (조각) 로 나누어 여러 트럭이 동시에 싣고 가는 방식입니다.
• 혁신: 큰 데이터 덩어리를 작은 조각 (Shard) 으로 잘게 나누어, 여러 노드가 동시에 전송하고 정리합니다. 이렇게 하면 나중에 대형 창고에서 정렬하는 과정 (Compaction) 도 여러 명이 동시에 할 수 있어 훨씬 빨라집니다.
• 효과: 데이터가 쌓여 생기는 병목 현상을 없애고, 전체 처리 속도가 비약적으로 상승합니다.

---

🚀 읽기 속도도 빠르게: "스마트 검색" (Cache-Enhanced Read Delegation)

데이터를 찾을 때도 똑똑한 전략을 씁니다.

• 기존 방식: 먼 곳 (분산 메모리) 에 있는 서류를 찾으려면, 서류함의 모든 칸을 하나씩 열어봐야 해서 시간이 오래 걸립니다.
• O3-LSM 방식:
  1. 핫한 자료는 바로 찾음: 자주 찾는 자료는 책상 위에 작은 **색인 카드 (캐시)**를 만들어두고, 바로 찾아냅니다.
  2. 안 찾는 자료는 전문가에게 맡김: 색인 카드에 없으면, 먼 곳의 **전문가 (분산 메모리 서버)**에게 "이 서류 찾아줘"라고 요청합니다. 전문가가 찾아서 결과를 보내면, 그 결과를 다시 색인 카드에 기록해 둡니다.
• 효과: 불필요한 이동 횟수를 줄여, 데이터를 찾는 속도가 매우 빨라집니다.

---

📊 실제 성과: 얼마나 빨라졌을까?

이 시스템을 실험해 보니 기존 방식들 (Disaggregated-RocksDB 등) 과 비교해 다음과 같은 놀라운 결과를 얻었습니다.

• 쓰기 속도 (Write): 최대 4.5 배 빨라졌습니다. (데이터를 저장하는 속도가 4 배 이상 향상)
• 읽기 속도 (Read): 최대 1.8 배 빨라졌습니다.
• 범위 검색 (Range Query): 최대 5.2 배 빨라졌습니다.
• 지연 시간 (Latency): 작업이 멈추거나 느려지는 현상이 76% 감소했습니다.

💡 결론

O3-LSM 은 클라우드 데이터 저장소를 위해 작은 컴퓨터의 메모리 부족 문제를 해결하고, 데이터 이동의 비효율성을 없애는 획기적인 기술입니다. 마치 물류 시스템을 완전히 재설계하여, 트럭이 막히지 않고 창고가 꽉 차도 계속 물건을 받아낼 수 있게 만든 것과 같습니다.

이 기술은 클라우드 서비스의 속도와 안정성을 높여, 우리가 사용하는 모든 앱과 서비스의 성능을 개선하는 데 기여할 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

분리형 데이터센터 (Disaggregated Data Centers, DDC) 환경에서 LSM-KVS(Log-Structured Merge-tree-based Key-Value Stores) 는 컴퓨팅 노드 (CN) 와 분리된 스토리지 (DS) 에 데이터를 저장하며, 기존에는 컴팩션 (Compaction) 오프로딩을 통해 네트워크 I/O 를 줄이는 최적화가 이루어졌습니다. 하지만 기존 접근 방식은 다음과 같은 근본적인 한계로 인해 쓰기 성능이 심각하게 저하됩니다.

1. 제한된 쓰기 버퍼 메모리: CN 의 메모리 용량이 제한되어 있어, 많은 수의 LSM 인스턴스를 호스팅할 경우 쓰기 버퍼 (Memtable) 공간이 빠르게 부족해집니다.
2. 느린 플러시 (Flush) 및 병목 현상: Memtable 이 가득 차면 DS 로 데이터를 플러시해야 하는데, 이 과정에서 네트워크 I/O 지연과 CN 내의 다른 작업 (WAL, 컴팩션 등) 과의 경쟁으로 인해 플러시가 지연됩니다.
3. L0 컴팩션 병목: 플러시가 지연되거나 L0 레벨의 SST 파일이 과도하게 쌓이면, L0 컴팩션이 순차적으로 수행되어야 하므로 쓰기 스로틀링 (Slowdown) 이나 정지 (Stall) 가 발생합니다.
4. 분리형 메모리 (DM) 활용의 난제: RDMA 기반의 분리형 메모리 (DM) 를 쓰기 버퍼로 확장하는 것은 유망해 보이지만, 다음과 같은 새로운 문제가 발생합니다.
   • 비효율적인 전송 및 재구성: 기존 Memtable(스킵리스트 기반) 을 DM 로 전송하면 포인터가 무효화되어 DM 에서 재구축해야 하므로 오버헤드가 큽니다.
   • 플러시 지연: DM 에 있는 Memtable 을 DS 로 플러시하려면 다시 CN 으로 가져와야 하므로 추가적인 네트워크 왕복이 발생합니다.
   • 검색 성능 저하: DM 에 있는 Memtable 을 읽을 때 RDMA 를 통한 다중 접근으로 인해 지연 시간이 크게 증가합니다.

2. 제안된 방법론 (Methodology: O3-LSM)

저자들은 O3-LSM을 제안하며, 이는 분리형 메모리 (DM) 를 활용하여 Memtable 오프로딩, 플러시 오프로딩, 컴팩션 오프로딩의 3 층 (Three-Layer) 구조를 구현합니다. 이를 위해 4 가지 핵심 혁신 기술을 도입했습니다.

가. DM-Optimized Memtable (DM 최적화 Memtable)

• 문제 해결: 기존 포인터 기반의 스킵리스트를 DM 로 전송할 때 발생하는 재구축 오버헤드를 제거합니다.
• 기술: Memtable 을 **인덱스 블록 (Index Block)**과 **KV 블록 (KV Block)**으로 분리합니다.
  • KV Block: KV 쌍을 연속적인 메모리에 순차적으로 저장하며 포인터가 없습니다. 따라서 DM 로 전송 시 포인터 재구성이 필요 없이 데이터만 복사하면 됩니다.
  • Index Block: 스킵리스트의 포인터만 포함하며, KV Block 내의 오프셋 (Offset) 을 가리킵니다. DM 에서는 KV Block 의 시작 주소만 알면 오프셋을 보정하여 포인터를 수정할 수 있습니다.
• 효과: DM 로의 전송 비용이 대폭 감소하고, DM 에서 직접 검색이 가능해집니다.

나. 협업형 플러시 오프로딩 (Collaborative Flush Offloading)

• 문제 해결: DM 에 있는 Memtable 을 DS 로 플러시할 때 소유한 CN 으로 다시 가져와야 하는 비효율과 I/O 경쟁을 해결합니다.
• 기술: 플러시 제어 평면 (Control Plane) 과 실행 평면 (Execution Plane) 을 분리합니다.
  • 플러시 스케줄러: 모든 CN 과 DM 노드의 리소스 (CPU, I/O, 대기열) 를 모니터링합니다.
  • 실행 모드: 플러시 작업을 소유한 CN(Local), DM 노드 자체 (In-DM), 또는 다른 CN(Remote-CN) 에서 수행할 수 있도록 동적으로 할당합니다.
  • 프로토콜: 준비 (Prepare), 할당 (Assign), 실행 (Execute), 완료 (Finalizing) 의 4 단계 프로토콜을 통해 원자성 (Atomicity) 을 보장하며, 실패 시 재시도합니다.
• 효과: 플러시 작업을 클러스터 전체의 유휴 리소스로 분산시켜 병목 현상을 제거하고 처리량을 극대화합니다.

다. 비동기 샤딩 (Asynchronous Sharding)

• 문제 해결: 대용량 Memtable 을 한 번에 전송/플러시할 때 발생하는 네트워크 폭주와 L0 컴팩션 병목을 해결합니다.
• 기술: Memtable 을 키 범위 (Key-range) 에 따라 여러 개의 **샤드 (Shard)**로 분할합니다.
  • 비동기 전송: 각 샤드 블록을 독립적으로 DM 로 전송합니다.
  • 샤드 단위 플러시: 서로 다른 Memtable 에서 동일한 키 범위를 가진 샤드 블록들을 그룹화하여 하나의 플러시 작업으로 병합합니다. 이는 L0 컴팩션을 플러시 단계에서 미리 수행하는 효과를 냅니다.
• 효과: L0 레벨의 중첩된 SST 파일 수를 줄여 L0 컴팩션 부하를 감소시키고, 병렬 처리를 극대화합니다.

라. 캐시 강화 읽기 위임 (Cache-Enhanced Read Delegation)

• 문제 해결: DM 에 있는 Memtable 을 읽을 때 발생하는 높은 지연 시간을 해결합니다.
• 기술:
  • 로컬 키 - 오프셋 캐시: CN 에 핫 (Hot) 한 키와 DM 의 메모리 오프셋을 매핑하는 작은 캐시를 유지합니다. 캐시 히트 시 RDMA_READ(One-sided) 로 직접 데이터를 가져옵니다.
  • 읽기 위임 (Read Delegation): 캐시 미스 시, DM 노드의 CPU 를 활용하여 검색을 수행하도록 위임합니다 (RDMA_SEND/Two-sided). DM 에서 검색 결과를 반환받아 CN 으로 전송합니다.
  • Bloom Filter: DM 의 샤드 블록에 대한 Bloom Filter 를 로컬에 캐싱하여 불필요한 원격 검색을 줄입니다.
• 효과: 읽기 지연 시간을 크게 단축하고, 불필요한 네트워크 왕복을 최소화합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 아키텍처: 분리형 스토리지 환경에서 DM 을 쓰기 버퍼 확장으로 활용하는 최초의 LSM-KVS 아키텍처 (O3-LSM) 를 제안했습니다.
2. 3 층 오프로딩: 기존 컴팩션 오프로딩에 더해 Memtable 오프로딩과 플러시 오프로딩을 통합하여 전체적인 쓰기/읽기 성능을 극대화했습니다.
3. DM 친화적 데이터 구조: 포인터 재구성이 불필요한 새로운 Memtable 구조 (Index/Data 분리) 를 설계하여 DM 전송 오버헤드를 제거했습니다.
4. 지능형 스케줄링: 리소스 상태에 따라 플러시 작업을 동적으로 할당하는 협업형 스케줄러를 구현하여 클러스터 전체의 효율성을 높였습니다.

4. 실험 결과 (Results)

RocksDB v8.2.0 기반의 프로토타입을 CloudLab 환경에서 평가하였으며, 기존 시스템 (Disaggregated-RocksDB, CaaS-LSM, Nova-LSM) 과 비교했습니다.

• 쓰기 성능 (Random Write):
  • 처리량 (Throughput) 이 4.5 배 향상되었습니다.
  • P99 지연 시간은 최대 60% 감소했습니다.
• 읽기 성능 (Random Read):
  • 처리량이 1.8 배 향상되었습니다.
  • P99 지연 시간은 최대 69% 감소했습니다.
• 범위 쿼리 (Range Query):
  • 처리량이 5.2 배 향상되었습니다.
• 혼합 워크로드 (Mixed 50/50):
  • 처리량이 3 배 향상되었으며, P99 지연 시간은 76% 감소했습니다.
• 실제 애플리케이션 (Kvrocks):
  • Redis 호환 KVS 인 Kvrocks 에서 3.4 배의 처리량 향상과 **54%**의 지연 시간 감소를 달성했습니다.
• 확장성: CN 과 DM 노드를 추가할 때 선형적인 성능 향상을 보였으며, 공유 DM 풀을 통해 쓰기 정지 (Write Stall) 를 92.2% 감소시켰습니다.

5. 의의 및 결론 (Significance)

O3-LSM 은 분리형 데이터센터 환경에서 LSM-KVS 의 가장 큰 병목인 '메모리 부족'과 '느린 플러시' 문제를 해결하기 위해 분리형 메모리 (DM) 를 효과적으로 통합한 획기적인 솔루션입니다.

• 성능 최적화: 단순히 메모리를 확장하는 것을 넘어, 데이터 구조와 플러시 전략을 DM 환경에 맞춰 재설계함으로써 성능 저하를 방지하고 오히려 기존 로컬 환경보다 우수한 성능을 달성했습니다.
• 자원 효율성: 컴퓨팅, 메모리, 스토리지를 분리된 리소스 풀로 관리하면서도, 협업형 스케줄링을 통해 전체 클러스터의 리소스 활용도를 극대화했습니다.
• 실용성: RocksDB 와 같은 표준 엔진에 적용 가능하며, Kvrocks 와 같은 실제 대규모 분산 시스템에서도 검증되었습니다.

이 연구는 분리형 아키텍처 하에서 LSM 기반 키 - 값 저장소의 성능 한계를 극복하고, 차세대 클라우드 스토리지 시스템의 표준 아키텍처로 자리 잡을 수 있는 중요한 이정표가 됩니다.