-
Jeff Dean의 30억 개 벡터 쿼리 문제 때문에, 최적의 map-reduce 솔루션을 직접 구현해 보는 과정을 다룬 기술 실험 기록
- 768차원 float32 벡터 30억 개와 1,000개 쿼리 벡터의 dot product를 계산하는 naive 구현에서 시작해, numpy 벡터화와 float32 변환으로 단계적 성능 개선 달성
- 3,000개 벡터 기준 naive 방식 약 2초에서 벡터화 후 0.01초, float32 적용 시 0.0045초까지 단축
- 30억 개 규모로 확장 시 결과 행렬이 약 8.6TB 메모리를 요구하여 OOM 문제 발생, 배치 처리·메모리 매핑·Rust/C 재작성·SimSIMD 같은 추가 최적화 필요
- 기술적 솔루션보다 요구사항 정의(반환 형태, 머신 스펙, 압축 허용 여부 등)가 더 어려운 핵심 과제임을 강조
문제의 출발점
-
Jeff Dean과 30억 개 벡터 쿼리 문제에 대한 교환을 보고, 최적의 map-reduce 솔루션을 직접 구현해 보려는 시도에서 시작
- 벡터는
n개 차원의 부동소수점 숫자 배열이며, 벡터 검색은 의미적으로 유사한 단어나 항목을 찾는 데 사용
- 검색, 추천, Cursor 같은 생성형 검색 애플리케이션에서 임베딩을 활용하는 일반적 패턴
Naive 구현
- 초기 가정: 30억 개 검색 대상(document) 벡터와 약 1,000개 쿼리 벡터, 모두 디스크에
.npy 형식으로 저장
- 벡터 차원은 768, 많은 유사도 기반 임베딩 쿼리 모델에서 사용하는 일반적 크기
- 각 쿼리 벡터를 문서 벡터 전체와 비교해 dot product를 계산하고 결과를 반환하는 이중 루프 방식
- 먼저 3,000개 벡터로 테스트한 결과, M2 MacBook에서 약 2초 소요 (30억 개보다 100만 배 적은 규모)
벡터화(Vectorized) 최적화
- numpy의 행렬 곱셈 연산(
vectors_file @ query_vectors.T)으로 이중 루프를 대체하는 벡터화 방식 적용
- 3,000개 벡터 기준 0.0107초로 대폭 개선
- 300만 개 벡터로 확장 시 12.85초 소요
float32 변환
- 데이터를
np.float32로 변환하여 추가 최적화 수행
- 3,000개 벡터 기준 0.0045초까지 단축
- 300만 개 벡터에서 약 13초이므로, 30억 개에서는 1,000배인 약 3,216분 소요 추정
성능 비교 요약
- Naive 방식(3,000 벡터): 1.9877초
- 벡터화 방식(3,000 벡터): 0.0107초
- 벡터화 방식(300만 벡터): 12.8491초
- float32 방식(3,000 벡터): 0.0045초
OOM 문제와 추가 최적화 방향
- 30억 개 객체를 float32(4바이트)로 처리할 때 필요한 메모리: 약 8.6TB, 실행 시 OOM 발생
- Jeff Dean이 제시한 방향의 추가 최적화 필요:
-
제너레이터와 배치 비교 연산으로 코드 변경
- 일정 연산마다 디스크에 기록하거나 메모리 매핑 사용
- Rust 또는 C로 시스템 레벨 최적화 코드 재작성
-
SimSIMD 같은 대규모 벡터 유사도 비교 전용 라이브러리 활용
요구사항 정의의 중요성
- 추가 최적화에 앞서 문제 자체의 불명확한 부분들을 발견:
- 단일 쿼리 벡터로 30억 개 전체를 한 번 조회 후 전체 결과 반환인지, top-k ANN 검색인지
- 원본 벡터도 함께 반환해야 하는지, 유사도 기준 재랭킹 필요 여부
- 1,000개 쿼리 벡터로 전체를 한 번 조회하는 것인지
- 벡터가 이미 메모리에 있는지, 디스크에서 하나씩 읽는지, 스트리밍 방식인지
- 로컬 실행인지, 머신 스펙은 무엇인지, GPU 사용 가능 여부
- 임베딩 크기가 결과의 표현과 입출력 벡터 크기에 미치는 영향
- float64에서 float32로의 압축이 정확도 면에서 허용 가능한지
- 일회성 프로젝트인지, 생성에 얼마나 시간이 주어지는지
- 기술적 솔루션 자체보다 요구사항을 정확히 정의하는 것이 가장 어려운 과제