30억 개 벡터 쿼리하기

- 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로의 압축이 정확도 면에서 허용 가능한지 - 일회성 프로젝트인지, 생성에 얼마나 시간이 주어지는지 - 기술적 솔루션 자체보다 요구사항을 정확히 정의하는 것이 가장 어려운 과제