Vector Search deep dive #1 (KNN indexing)

이전 포스팅에서 Vector Search의 오버뷰를 정리했다. 이번에는 저장된 벡터들을 어떤식으로 저장하고 검색하는지 알아보자

 

 

Vector Store

일정한 차원의 벡터 데이터들을 효과적으로 저장하고, 검색하기 위해서는 기존의 DB와는 다른 자료구조로 저장해야 하기에, 별도의 검색엔진이 필요하다.

 

벡터를 지원하는 검색엔진으로는 faiss, nmslib, lucene가 있는데, 이런 엔진을 기반으로 기존 RDB, Document DB에서 벡터 필드를 사용할 수 있다.

 

각각의 DB마다 지원하는 엔진, 지원하는 벡터 차원등이 모두 다르니 필요에 따라 솔루션을 선택한다. 

DB 선택 이슈

 

논문 정보를 저장할 vector db를 선정한다. · Issue #10 · SWM-Thlee/linked-paper-search

 

KNN

K-nearest-neighbor 즉 k개의 인접한 노드들을 찾는 알고리즘이다. 

벡터 공간상에서 인접한(nearest) 노드를 찾는 알고리즘인데, 인접함의 기준은 Euclidean distance, Cosian similarity 등으로 설정하게 된다. 정확히 쿼리와 인접한 top K를 추출해야 하기에 노드의 수와 차원이 증가하면 연산량이 크게 증가한다.

 

쿼리와 인접한 노드들을 검색하기 위해 걸리는 시간은 다음과 같다.

 

O(N⋅D+Nlogk)

• N : 노드의 개수
• D : 벡터의 차원
• Nlogk : k개의 최근접 이웃을 선택하는데 드는 시간

작은 차원과 노드에서는 exact knn을 사용해도 상관없지만, 실시간 대용량 검색 서비스를 제공한다면, 다른 방법을 고려해야 한다.

 

ANN (HNSW)

ANN은 approximate nearest neighbor으로 knn보다 정확도와 인덱싱 속도를 포기하고, 검색 속도를 올린 방법이다.

 

HNSW는 다중 레이어 그래프 구조를 통해 노드간의 인접 노드를 미리 저장하여, 검색시에 해당 자료구조를 통해 빠른 검색을 제공한다.

 

검색 방법

1. 노드가 가장 적은 레이어에서 시작하여 쿼리의 nearest neighbor을 찾음
2. 다음 레이어에서 이전 레이어의 노드를 entry로 마찬가지로 이웃을 찾음
3. 2번 과정을 반복하며 layer 0까지 도달
4. Layer 0에서는 ef (Exploration Factor) 파라미터에 따라 더 넓은 범위의 노드를 탐색후 top K 추출

파라미터

그래프 생성 및 탐색에 필요한 주요 파라미터

파라미터	설명
M	각 노드당 최대 연결 수
ef_construction	그래프 구축 시 고려할 이웃 후보군 수 (값이 클수록 인덱싱 속도가 느려짐)
ef	탐색 시 고려할 이웃 후보군 수 (값이 클수록 정확도가 높아짐)

 

OpenSearch 기준으로 인덱스를 생성할 때, 그래프 생성과 탐색에 필요한 파라미터를 지정하는데, 추후 변경 불가 (필요시 reindex)

"method": {
  "name":"hnsw",
  "engine":"faiss",
  "parameters":{
    "ef_construction": 256,
    "m": 8
  }
}

 

성능

단계	시간 복잡도	공간 복잡도(메모리)
인덱싱	O(N * logN)	O(N*M)
검색	O(logN)	O(ef)

 

필요 리소스

그래프 정보를 저장하기 위한 메모리가 필요하게 되는데, 벡터 한개 당 예상 리소스는 아래와 같다.

1.1 * (4 * dimension + 8 * M)

 

예를 들어, D = 1024, M = 16에서 벡터 2백만개라면,

1.1 * (4 * 1024 + 8 * 16) * 2,000,000 ~= 9.2928GB

 

인덱싱에 필요한 메모리를 잘 계산해서 인스턴스 리소스 측정 필요하다.

 

OpenSearch의 과도한 메모리 압박 시, circuit breaker 발생

이슈

OpenSearch indexing KNN circuit breaker 발생 · Issue #31 · SWM-Thlee/linked-paper-search

 

만약 인스턴스 메모리가 한정된 상황이라면 disk에 저장하는 방법도 있음

PUT my-vector-index
{
  "settings" : {
    "index": {
      "knn": true
    }
  },
  "mappings": {
    "properties": {
      "my_vector_field": {
        "type": "knn_vector",
        "dimension": 8,
        "space_type": "innerproduct",
        "data_type": "float",
        "mode": "on_disk" // default는 메모리
      }
    }
  }
}

 

레퍼런스

https://arxiv.org/abs/1603.09320

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

https://aws.amazon.com/ko/blogs/big-data/choose-the-k-nn-algorithm-for-your-billion-scale-use-case-with-opensearch/

Choose the k-NN algorithm for your billion-scale use case with OpenSearch | Amazon Web Services

https://opensearch.org/docs/latest/search-plugins/knn/knn-index/

k-NN index