SPFresh: Incremental In-Place Update for Billion-Scale Vector Search
https://dl.acm.org/doi/10.1145/3600006.3613166
https://sosp2023.mpi-sws.org/program.html >> Data and databases
summary
SPFresh는 ANNS 시스템에서 리얼타임 벡터 인덱스 업데이트가 가능한 효율적 방법이다. ANNS 방식을 사용하는 대규모 벡터 데이터셋에서 지속적으로 데이터가 업데이트될 때 기존 시스템이 가지는 한계를 해결하기 위해 제안되었다.
기존 시스템들은 업데이트에 드는 cost를 줄이기 위해 secondary index를 사용하였기 때문에 main index에 주기적으로 merge해준다는 측면에서는 효율적이었으나 secondary index의 규모가 커질수록 검색의 latency가 증가하고 accuracy가 감소한다는 단점과 새로운 벡터가 삽입되거나 기존 벡터가 삭제될 때 인덱스의 품질을 유지하기 위해서 global rebuild에 의존해야하는 한계가 있었다. global rebuild를 진행하면 검색 서비스를 유지하는 비용보다 전체를 rebuild 하는 비용이 더 클만큼 리소스 소모가 심했다.
온라인 검색 서비스는 낮은 latency와 높은 accuracy를 요구하기 때문에 읽기 성능을 희생하면서까지 쓰기 성능을 최적화하는 해당 방식이 적합하지 않았다. 그래서 제안된 SPFresh는 Lightweight Incremental RE balancing 프로토콜이라 작은 크기의 벡터 업데이트가 발생했을 때 global rebuild를 택하지 않고 필요한 최소한의 벡터만 local에서 재할당하는 방식으로 인덱스의 품질을 유지하였다.
SPFresh는 이미 잘 분할된 상태에서 일어나는 작은 업데이트가 본인이 속한 파티션과 근처 파티션에만 영향을 준다는 점을 기반으로 작동하기 때문에 대부분의 업데이트가 local에서 발생한 것임을 이용해서 전체를 rebalancing하기 위한 비용들을 줄일 수 있다.
파티션 크기 분포를 고르게 유지하기 위해서 split과 merge를 점차적으로 수행하며 Nearest Partition Assignment 규칙을 기반으로 재할당이 필요한 최소한의 벡터 집합만 정의하게 된다. 또한 구현과정에서 update 과정과 rebalance 과정을 분리하여 검색 서비스의 FG 과정에 부담을 주지 않을 수 있도록 파이프라인화하고 각 단계를 멀티 스레드로 실행되도록 해서 NVMe SSD의 성능을 활용하고자 하였다. userspace storage engine을 구현해서 기존 커널 스택을 bypass하고 파티션을 읽고 쓰는 과정을 최적화하였다.
strengths
- rebalancing 발생 비율 실험적 증명 : 이미 잘 분할된 고품질 인덱스라면 작은 규모인 local update만 일어날 것이라는 LIRE의 핵심 아이디어를 논리적으로만 설명한 것이 아니라 전체 insert 중에서 rebalancing을 일으킨 비율이 0.4%임을 실험으로 설명하였다. trigger된 경우에서도 평균적으로 5094개 벡터를 평가해서 79개만 실제 reassign 되었음을 확인했다. 실험을 통해 insert 중 몇 퍼센트가 rebalancing을 일으켰는지와 trigger된 경우에도 얼마나 작은 범위에서 발생하는지 locality 측면을 함께 명확하게 증명하였다.
- 기존 시스템 한계 해결에 대해 장기간 실험을 통한 증명 : 기존 시스템이 가진 global rebuild에 대해 의존해서 발생하는 문제(리소스 소모가 크다, 성능이 불안정하다)를 필요한 최소한의 벡터만 local에서 재할당하는 방식으로 해결하였다. 이에 대해 단기간이 아니라 100일동안 하루 1억 개의 벡터 업데이트가 일어나도록 시뮬레이션하여 장기간 실제 서비스 레벨의 워크로드에서 안정적으로 낮은 latency와 높은 accuracy를 유지했음을 실험적으로 증명하였다.
- in place update : SPFresh는 새로운 인덱스를 따로 만들어서 교체하지 않고 기존의 인덱스를 유지하면서 필요한 부분만 점차 수정해나가는 in place 방식을 사용한다. 이를 통해서 검색 서비스가 중단되지 않고 실시간 업데이트를 지원해준다는 점은 실제 서비스 환경에서 아주 큰 장점일 것이다.
weaknesses
- 전제에 대한 의존 : LIRE는 이미 잘 분할된 고품질 인덱스라는 전제를 기반으로 작동한다. 초기 파티셔닝 품질이 낮거나 초반부터 이미 skewed 상태인 것처럼 전제와 다른 예외 상황에 대한 언급이 부족하다.
- 새로 만드는 replica로 인한 오버헤드 : 업데이트 처리 과정에서 append 방식으로 새 replica를 생성하고 기존 replica는 나중에 garbage collection을 통해서 정리하는 방식으로 동작한다. 논문에서는 전체 벡터의 86%가 하나 이상의 replica를 가지고 있고 평균 5.47개를 가지고 있다고 언급한다. 장기적인 관점에서 봤을 때 디스크를 차지하는 양이나 garbage collection의 비용을 정량적으로 분석하지 않았다. 실험 결과를 보면 foreground latency나 처리량은 안정적으로 좋은 성능임을 증명했지만 replica가 늘어나는 방식은 장기적으로는 디스크 사용량을 높일 수 있고 GC 과정에서 리소스 소모가 더 발생할 수도 있다. 논문에서는 이 부분을 정량적으로 깊게 다루지 않았기 때문에 실제 현실에서 적용하기 위해서는 얼마나 효율적으로 관리될지 조금 더 확인해볼 필요가 있다.
- 특정 환경에 대한 최적화 : billion scale 디스크 기반 인덱스를 제안하는 것을 목표로 하였고 SPDK와 성능이 좋은 NVMe를 활용하였다. 논문 목표에 적합한 환경 설정으로 보이지만 SPDK와 NVMe 각각의 요소가 SPFresh에 기여하는 정도를 분리해서 보여주는 실험이 있으면 더 좋을 것으로 판단된다.
detailed comment
SPFresh는 대규모 벡터 서치 시스템에서 일어나는 freshness 문제에 집중하였다. global rebuild로 인해 secondary index가 커질수록 리소스를 더 많이 소모하고 성능이 악화되었던 기존 시스템들의 문제를 효과적으로 해결하였다. 작은 규모의 업데이트는 가까운 지역에만 영향을 준다는 아이디어를 실험적으로 입증하였고 전체 insert 중 rebalancing 비율과 실제 재할당된 개수를 확인하여 locality 기반으로 설계한 것이 효과적임을 입증하였다. 100일동안 하루 1억 개 insert가 일어나는 실질적이고 장기적인 워크로드로 시뮬레이션해서 실제 서비스 레벨에서도 안정적으로 높은 성능을 보인다는 것을 입증한 점 또한 인상적이었다.