Onyx: Cost-Efficient Disk-Oblivious ANN Search

1. 문제 정의 (Problem Statement)

• 배경: AI 시스템 (검색, 추천, RAG 등) 에서 Approximate Nearest Neighbor (ANN) 검색은 민감한 데이터를 처리하며, 비용 효율성을 위해 제 3 자 인프라 (클라우드) 와 외부 SSD 를 사용하는 경우가 많습니다.
• 보안 위협: 데이터와 쿼리를 암호화하더라도, 신뢰할 수 없는 호스트 (Cloud Provider) 가 디스크 접근 패턴 (Disk Access Pattern) 을 관찰하면 쿼리 내용과 데이터셋을 유추하거나 복구할 수 있습니다 (Leakage-abuse attacks).
• 기존 솔루션의 한계:
  • TEE (Trusted Execution Environment) 만 사용: 인덱스를 모두 TEE 내부 메모리에 보관하면 비용이 매우 비쌉니다 (대규모 인덱스 처리 불가).
  • ORAM (Oblivious RAM) 만 사용: 기존 ORAM 기반 ANN 시스템 (예: Compass) 은 네트워크 환경에 최적화되어 있어, 이를 TEE 내부의 디스크 환경에 적용하면 높은 지연 시간 (Latency) 과 비효율적인 리소스 사용으로 인해 비용이 급증합니다.
  • 핵심 딜레마: 기존 설계는 ANN 계층에서는 접근 횟수를 줄이기 위해 대용량 블록을 가져오고, ORAM 계층에서는 대역폭을 줄이기 위해 세밀한 접근을 시도합니다. 이로 인해 대역폭 (Bandwidth) 과 접근 횟수 (Access Count) 두 가지 리소스 모두 비효율적으로 과사용됩니다.

2. 방법론 및 핵심 기여 (Methodology & Key Contributions)

저자들은 Onyx라는 새로운 시스템을 제안하며, ANN 과 ORAM 을 역발상적으로 재설계 (Inverting the design) 하여 디스크 환경에 최적화했습니다.

A. 설계 철학의 전환

• 기존: ANN 은 접근 횟수 최소화, ORAM 은 대역폭 최소화.
• Onyx:
  • ANN 계층: ANN 검색의 근사적 특성 (Approximation) 을 활용하여 대역폭 효율성을 극대화합니다 (작은 블록, 낮은 정밀도 표현 사용).
  • ORAM 계층: ORAM 에는 접근 횟수에 대한 이론적 하한선이 없으므로, 접근 횟수 최소화에 집중합니다.

B. 주요 구성 요소 (Co-designed Components)

1. Onyx-ANNS (Bandwidth-Efficient ANN Search)

   • 문제: 기존 DiskANN 은 탐색 (Traversal) 과 정제 (Refinement) 를 결합하여 큰 블록 (Full-precision vector) 을 읽음.
   • 해결: 탐색과 정제를 분리 (Decoupling) 하는 3 단계 전략을 도입합니다.
     1. 탐색 (Traversal): 메모리에 있는 저정밀도 힌트 (Htrv) 와 디스크에서 가져온 작은 크기 중간 표현 (Compact Pruning Hints, Hprn) 을 사용하여 후보를 필터링합니다. 이 단계에서는 전체 벡터를 읽지 않습니다.
     2. 정제 (Refinement): 필터링된 소수의 후보에 대해서만 디스크에서 Full-precision 벡터를 가져와 정확한 거리를 계산합니다.
   • 효과: 대역폭 사용량을 25 배 줄이면서, 접근 횟수는 515% 만 증가시킵니다.

2. Onyx-ORAM (Access-Count-Efficient ORAM)

   • 문제: 기존 Tree-based ORAM (RingORAM, PathORAM) 은 디스크 접근 횟수나 대역폭 중 하나에서 병목이 발생합니다.
   • 해결: 국소성 인식 (Locality-aware) 심층 트리 (Shallow Tree) 설계를 도입합니다.
     • 이진 트리 → d-ary 트리: 트리의 깊이를 줄여 접근 횟수를 감소시킵니다.
     • 로컬 메타데이터 저장: 버킷 메타데이터를 클라이언트 메모리에 저장하여 레벨별 메타데이터 읽기를 제거합니다.
     • 전체 버킷 읽기 (Full Bucket Reads): Eviction 시 개별 블록이 아닌 전체 버킷을 순차적으로 읽음으로써 접근 횟수를 획기적으로 줄입니다.
   • 효과: 접근 횟수는 2 배 감소, 대역폭은 4.6 배 감소하여 두 리소스 모두 최적화됩니다.

3. 실험 결과 (Evaluation Results)

저자들은 4 개의 데이터셋 (SIFT, MS-MARCO, WIKI, DEEP) 과 다양한 하드웨어 구성 (1~4 개 SSD) 에서 Onyx 를 평가했습니다.

• 비용 효율성 (Cost Efficiency):

  • 기존 최첨단 시스템 (Compass-in-TEE) 대비 1.7~9.9 배 낮은 비용을 달성했습니다.
  • 동일한 리소스 (1 vCPU, 1 SSD) 로 초당 70 건의 쿼리 (QPS) 를 처리하며, 12ms 의 지연 시간을 유지했습니다. (Compass-in-TEE 는 160ms 이상, 4 vCPU/8 SSD 필요)
  • 달러당 쿼리 수 (Queries/$) 는 800 만 건 이상을 달성했습니다.

• 성능 (Latency & Throughput):

  • Compass-in-TEE 대비 2.3~12.3 배 낮은 지연 시간과 2.3~12.2 배 높은 처리량을 보였습니다.
  • 디스크 최적화 베이스라인 (RingORAM/PathORAM + DiskANN) 대비도 2.5~9.5 배 성능 우위를 보였습니다.

• 코디자인의 중요성:

  • Onyx-ANNS 와 Onyx-ORAM 중 하나만 개선한 경우보다, 두 요소를 함께 최적화했을 때 성능이 극대화됨을 입증했습니다. (작은 벡터 데이터셋에서는 ORAM 최적화가, 큰 벡터 데이터셋에서는 ANN 대역폭 절감이 각각 중요하지만, 전체적으로는 둘 다 필수적입니다.)

4. 의의 및 결론 (Significance)

• 실용적인 프라이버시 보호: Onyx 는 TEE 와 외부 SSD 를 활용하여, 대규모 ANN 검색을 저비용 (Cost-Efficient) 으로 수행하면서도 쿼리 및 데이터 프라이버시를 강력하게 보호하는 첫 번째 실용적인 솔루션입니다.
• 리소스 활용의 혁신: ANN 과 ORAM 간의 상충 관계 (Trade-off) 를 재해석하여, 각 구성 요소가 가진 고유한 특성 (ANN 의 근사성, ORAM 의 접근 횟수 유연성) 을 상호 보완적으로 활용함으로써 성능과 비용의 균형을 달성했습니다.
• 실제 적용 가능성: 이 기술은 기업용 지식 베이스 (RAG), 개인화된 AI 에이전트 메모리 등 민감한 데이터를 다루는 클라우드 기반 AI 서비스의 상용화를 가능하게 하는 핵심 기술로 평가됩니다.

요약하자면, Onyx는 기존 ORAM 기반 ANN 검색의 비효율적인 리소스 사용을 해결하기 위해 ANN 과 ORAM 을 공동 설계 (Co-design) 함으로써, 높은 성능과 낮은 비용을 동시에 달성한 획기적인 시스템입니다.