OpenSearch에서 수십억 규모 검색을 위한 적합한 k-NN 알고리즘을 선택하기

조직에서 자연어 처리(NLP) 시스템, 추천 엔진이나 검색 기반 시스템과 같은 머신 러닝(ML) 애플리케이션을 만들려고 할 때, 일정 수준 이상의 단계에서 k-Nearest Neighbor(k-NN) 검색을 쓰게 됩니다. 하지만 데이터 포인트가 수억 개에서 수십억 개까지 늘어나면, k-NN 검색 시스템을 확장하는 게 정말 큰 난제가 될 수 있습니다. 이럴 때 Approximate k-Nearest Neighbor (ANN) 검색을 적용하면 이 문제를 잘 해결할 수 있습니다.

k-NN의 문제는 점(벡터) 집합과 쿼리가 주어지면 집합에서 쿼리에 가장 가까운 점 k개를 찾는 것으로, 다른 ML 기법에 비해 비교적 간단합니다. 집합의 각 벡터에 대해 쿼리로 부터의 거리를 계산하고 그 과정에서 상위 k를 추적하는 접근 방식 또한 쉽게 이해실수 있습니다.

이러한 접근 방식의 문제점은 확장이 어렵다는 것입니다. 런타임 검색 복잡도는 O(Nlogk)이며, 여기서 N은 벡터의 수이고 k는 가장 가까운 이웃의 수입니다. 집합에 수천 개의 벡터가 포함되어 있을 때는 눈에 띄지 않을 수 있지만, 크기가 수백만 개로 늘어나면 눈에 띄게 달라집니다. 일부 exact k-NN 알고리즘을 사용하면 검색 속도를 높일 수 있지만, 더 높은 차원에서는 대략적인(Approximate) 비교방식의 알고리즘과 비슷한 성능을 보이는 경향이 있습니다.

ANN 검색이 여기서 등장합니다. k-NN 문제에 대한 몇 가지 제약 조건을 조금 완화하면, 실제 검색 시 걸리는 시간을 줄일 수 있습니다.

색인이 더 오래 걸리도록 허용합니다.
검색 시 더 많은 공간을 사용할 수 있도록 허용합니다.
검색이 벡터의 집합에서 k-NN의 근사값을 반환하도록 허용합니다.

이를 위해 여러 가지 알고리즘을 활용할 수 있습니다.

OpenSearch는 손쉽게 데이터를 수집, 검색, 시각화 및 분석할 수 있는 오픈소스 커뮤니티 중심의 Apache 2.0 라이선스 검색 및 분석 엔진입니다. OpenSearch k-NN 플러그인은 OpenSearch 클러스터 내에서 k-NN 알고리즘 중 일부를 사용할 수 있는 기능을 제공합니다. 이 글에서는 지원되는 다양한 알고리즘에 대해 분석하고 실험을 통해 이들 간의 장단점을 살펴보겠습니다.

Hierarchical Navigable Small Worlds(HNSW) 알고리즘

Hierarchical Navigable Small Worlds algorithm (HNSW) 알고리즘은 ANN 검색에 가장 많이 사용되는 알고리즘 중 하나입니다. k-NN 플러그인이 최초로 지원한 알고리즘으로, nmslib 유사도 검색 라이브러리에서 매우 효율적으로 사용됩니다. 쿼리 지연 시간과 recall 지수의 균형이 가장 뛰어나며 별도의 모델 학습 과정이 필요하지 않습니다. 이 알고리즘의 핵심 아이디어는 서로 가까운 인덱스 벡터를 연결하는 엣지(edges)가 있는 계층형 그래프를 구축하는 것입니다. 그런 다음 검색 시 이 그래프를 부분적으로 탐색하여 쿼리 벡터에 가장 가까운 이웃을 찾습니다. 쿼리의 가장 가까운 이웃을 향해 탐색을 진행하기 위해 알고리즘은 항상 쿼리 벡터에 가장 가까운 후보를 다음 목적지로 지정하여 방문합니다.

하지만 어떤 벡터에서 탐색을 시작해야 할까요? 그냥 임의의 벡터를 선택할 수도 있지만, 인덱스가 큰 경우 쿼리의 실제 가장 가까운 이웃과 매우 멀리 떨어져 있어 결과가 좋지 않을 수 있습니다. 일반적으로 쿼리 벡터에 가장 가까운 벡터를 선택하기 위해 알고리즘은 하나의 그래프가 아니라 그래프의 계층 구조를 구축합니다. 모든 벡터가 맨 아래 계층에 추가되고, 그 벡터의 임의의 하위 집합이 그 위 계층에 추가되고, 그 하위 집합이 그 위 계층에 추가되는 식으로 추상화된 계층이 만들어집니다.

검색 중에는 최상위 계층의 임의의 벡터에서 시작하여 그래프를 부분적으로 탐색하여 해당 계층에서 쿼리 벡터에 가장 가까운 지점을 찾은 다음 바로 아래 계층의 벡터를 탐색의 시작점으로 사용합니다. 최하위 계층에 도달할 때까지 이 과정을 반복합니다. 맨 아래 계층에서는 순회를 수행하지만 이번에는 가장 가까운 이웃을 검색하는 대신 도중에 방문한 k-nearest neighbors를 추적합니다.

다음 그림은 위에 설명한 프로세스를 보여줍니다(논문 Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs 를 참고하였습니다).

OpenSearch의 HNSW 알고리즘에 대해 세 가지 매개 변수를 조정할 수 있습니다.

m – 벡터가 그래프에서 얻을 수 있는 최대 엣지의 수입니다. 이 값이 클수록 그래프에서 더 많은 메모리를 사용하지만 검색시 근사치가 더 좋아질 수 있습니다.
ef_search – 탐색 중에 방문할 후보 노드의 대기열 크기입니다. 노드를 방문하면 해당 노드의 이웃 노드가 향후 방문할 대기열에 추가됩니다. 이 큐가 비어 있으면 탐색이 종료됩니다. 값이 클수록 검색 대기 시간은 증가하지만 검색시 근사치가 더 좋아질 수 있습니다.
ef_construction – ef_search와 매우 유사합니다. 노드가 그래프에 삽입될 때 알고리즘은 새 노드를 쿼리 벡터로 삼아 그래프를 쿼리하여 해당 노드의 m개의 에지를 찾습니다. 이 매개변수는 이 탐색을 위한 후보 대기열 크기를 제어합니다. 값이 클수록 인덱스 대기 시간은 증가하지만 더 나은 검색시 근사치를 제공할 수 있습니다.

HNSW에 대하여 더 자세한 내용을 알고싶으시다면 논문 ‘Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.’을 참조하세요.

메모리 사용량

HNSW는 짧은 지연 시간으로 매우 우수한 ANN 검색을 제공하지만, 많은 양의 메모리를 소모할 수 있습니다. 각 HNSW 그래프는 약 1.1 * (4 * d + 8 * m) * num_vectors 바이트의 메모리를 사용합니다.

d 는 벡터의 크기를 의미합니다.
m 은 계층에서 각 노드가 가지게 되는 엣지의 수를 제어하는 파라미터 입니다.
num_vectors 는 인덱스에 있는 벡터의 수 입니다.

특히 상용 워크로드를 실행할 때 내구성과 가용성을 보장하기 위해 OpenSearch 인덱스에는 복제본 샤드를 하나 이상 보유하는 것이 좋습니다. 따라서 메모리 요구 사항은 (1 + 복제본 샤드의 수)를 곱합니다. 데이터 크기가 각각 128개의 차원으로 구성된 1,000,000,000(10억) 개의 벡터이고 m이 기본값인 16으로 설정된 2개의 샤드를 가진 인덱스의 경우, 필요한 예상 메모리 양은 다음과 같습니다.

1.1 * (4 * 128 + 8 * 16) * 1,000,000,000 * 2 = 1,408 GB

예를 들어 벡터의 크기를 512로 늘리고 차원이 높은 벡터에 권장되는 m을 100으로 늘리면 일부 사용 사례에는 약 6TB의 총 메모리가 필요할 수 있습니다.

OpenSearch를 사용하면 이 메모리 요구 사항을 처리하기 위해 언제든지 클러스터를 수평적으로 확장할 수 있습니다. 하지만 이 경우 인프라 비용이 증가한다는 단점이 있습니다. 확장이 적절하지 않은 경우에는 k-NN 시스템의 메모리 공간을 줄이는 옵션을 모색해야 합니다. 다행히도 이를 위해 사용할 수 있는 알고리즘이 있습니다.

Inverted File System(IVF) 알고리즘

인덱스 벡터를 버킷 집합으로 분리한 다음, 검색 시간을 줄이기 위해 이러한 버킷의 하위 집합만 검색하는 다른 접근 방식을 고려해 볼수 있습니다. 높은 수준에서 보면, 이것이 바로 Inverted File System(IVF) ANN 알고리즘이 하는 일입니다. OpenSearch 1.2에서는 k-NN 플러그인에 Faiss의 IVF 구현을 위한 지원이 도입되었습니다. Faiss는 고밀도 벡터의 효율적인 유사도 검색과 클러스터링을 위한 Meta의 오픈 소스 라이브러리입니다.

그러나 벡터를 무작위로 여러 버킷으로 분할하고 그 하위 집합만 검색하면 근사치가 떨어집니다. IVF 알고리즘은 보다 효율적인 접근 방식을 사용합니다. 먼저, 색인을 시작하기 전에 각 버킷에 대표 벡터를 할당합니다. 벡터가 색인되면 가장 가까운 대표 벡터를 가진 버킷에 벡터가 추가됩니다. 이렇게 하면 서로 더 가까운 벡터는 대략적으로 같은 버킷이나 가까운 버킷에 배치됩니다.

IVF 알고리즘에서 버킷의 대표 벡터를 결정하려면 학습이 필요합니다. 학습은 훈련 데이터 세트에 대해 k-Means(평균) 클러스터링이 실행되며, 여기서 생성된 중심이 대표 벡터가 됩니다. 다음 다이어그램은 이 과정을 보여줍니다.

IVF 알고리즘에 대해 두 가지 매개 변수를 조정할 수 있습니다.

nlist – 생성할 버킷의 수입니다. 버킷이 많을수록 훈련 시간이 길어지지만 검색을 보다 세밀하게하여 품질을 향상시킬 수 있습니다.
nprobes – 검색할 버킷의 수입니다. 이 매개변수는 매우 간단합니다. 검색하는 버킷이 많을수록 검색 시간이 더 오래 걸리지만 벡터간 근사치가 더 정확해집니다.

메모리 사용량

일반적으로 IVF는 인덱싱된 각 벡터에 대해 엣지 집합을 저장할 필요가 없으므로 HNSW보다 적은 메모리를 필요로 합니다.

IVF에는 대략 다음과 같은 양의 메모리가 필요합니다.

1.1 * (((4 * dimension) * num_vectors) + (4 * nlist * dimension)) bytes

복제 계층이 하나이고 128차원 벡터가 1,000,000,000(10억) 개 있는 HNSW과 비교하여, 같은 데이터의 nlist가 4096인 IVF 알고리즘은 대략 1.1 * (((4 * 128) * 2,000,000,000) + (4 * 4096 * 128)) bytes = 1126 GB 가 소요됩니다.

num_vectors가 2,000,000,000인 이유는 (1 + 복제본 샤드의 수)로 1,000,000,000 * 2 를 해 주었기 때문입니다.

그러나 이러한 절감 효과에는 대가가 따릅니다. HNSW 알고리즘은 쿼리 지연 시간 대비 근사치 정확도 사이에서 더 나은 균형을 제공하기 때문입니다.

Product quantization(PQ) 벡터 압축

HNSW와 IVF를 사용하여 가장 가까운 이웃 검색 속도를 높일 수 있지만, 상당한 양의 메모리를 소모할 수 있습니다. 10억 개의 벡터 규모에 도달하면 인덱스 구조를 지원하기 위해 수천 GB의 메모리가 필요해지기 시작합니다. 벡터의 수나 벡터의 차원을 확장함에 따라 이 요구 사항은 계속 증가합니다. k-NN 인덱스에서 보다 적은 공간을 사용할 수 있는 방법이 있을까요?

정답은 ‘예’입니다! 실제로 벡터에 필요한 메모리 양을 줄이는 방법에는 여러 가지가 있습니다. 임베딩 모델을 변경하여 더 작은 벡터를 생성하거나 주성분 분석(PCA)과 같은 기술을 적용하여 벡터의 차원을 줄일 수 있습니다. 또 다른 접근 방식은 양자화를 사용하는 것입니다. 벡터 양자화의 일반적인 개념은 연속적인 값을 가진 큰 벡터 공간을 불연속적인 값을 가진 작은 공간에 매핑하는 것입니다. 벡터를 더 작은 공간에 매핑하면 표현하는 데 더 적은 비트가 필요합니다. 그러나 더 작은 입력 공간에 매핑할 때 벡터에 대한 일부 정보가 손실된다는 대가가 따릅니다.

Product quantization(PQ)는 k-NN 검색 분야에서 매우 널리 사용되는 양자화 기법입니다. 가장 가까운 이웃 검색을 위해 ANN 알고리즘과 함께 사용할 수 있습니다. IVF와 함께, k-NN 플러그인은 OpenSearch 1.2에서 Faiss의 PQ 구현에 대한 지원을 추가했습니다.

PQ의 주요 개념은 하나의 벡터를 여러 개의 하위 벡터로 나누고 그 하위 벡터를 고정된 비트 수로 독립적으로 인코딩하는 것입니다. 원본 벡터가 분할되는 하위 벡터의 수는 매개변수 m에 의해 제어되며, 각 하위 벡터를 인코딩할 비트 수는 매개변수 code_size에 의해 제어됩니다. 인코딩이 완료되면 벡터는 대략 m * code_size 비트 수로 압축됩니다. 따라서 1024차원 벡터 100,000개 집합이 있다고 가정해 보겠습니다. m = 8, code_size = 8인 경우 PQ는 각 벡터를 128차원의 하위 벡터 8개로 나누고 각 하위 벡터를 8비트로 인코딩합니다.

인코딩에 사용되는 값은 훈련 단계에서 생성됩니다. 훈련 중에 각 하위 벡터 파티션에 대해 2 code_size 항목이 포함된 테이블이 생성됩니다. 다음으로, 훈련 데이터의 해당 하위 벡터 파티션에 대해 2 code_size의 k 값을 사용하는 k-Means 클러스터링이 실행됩니다. 여기서 생성된 중심은 파티션의 테이블에 항목으로 추가됩니다.

모든 테이블이 생성되면 각 하위 벡터를 파티션의 테이블에서 가장 가까운 벡터의 ID 로 대체하여 벡터를 인코딩합니다. code_size = 8인 예제에서는 테이블에 28개의 요소가 있기 때문에 ID를 저장하는 데 8비트만 필요합니다. 따라서 dimension = 1024, m = 8을 사용하면 하나의 벡터의 총 크기(32비트 부동 소수점 데이터 유형을 사용한다고 가정)가 4,096바이트에서 약 8바이트로 줄어듭니다!

벡터를 해독하려면 저장된 ID를 사용해 각 파티션의 테이블에서 벡터를 검색하여 대략적인 버전의 벡터를 재구성할 수 있습니다. 그런 다음 쿼리 벡터에서 재구성된 벡터까지의 거리를 계산하여 k-NN 검색에 사용할 수 있습니다. (실제로는 k-NN 검색의 이 프로세스 속도를 높이기 위해 ADC와 같은 추가 최적화 기법이 사용된다는 점에 주목할 필요가 있습니다)

메모리 사용량

앞서 언급했듯이 PQ는 각 벡터를 대략 m * code_size 비트에 각 벡터에 대한 약간의 오버헤드를 더한 값으로 인코딩합니다.

이를 IVF와 결합하면 다음과 같이 인덱스 크기를 추정할 수 있습니다.

1.1 * ((((code_size/8) * m + overhead_per_vector) * num_vectors) + (4 * nlist * dimension) + (2 ^code_size * 4 * dimension) bytes

10억 개의 벡터, dimension = 128, m = 8, code_size = 8, nlist = 4096을 사용하면 총 메모리 사용량은 70GB로 추정됩니다.

1.1 * ((((8 / 8) * 8 + 24) * 1,000,000,000) + (4 * 4096 * 128) + (2^8 * 4 * 128)) * 2 = 70 GB.

OpenSearch에서 k-NN 실행

먼저 OpenSearch 클러스터를 설정하고 실행 중인지 확인하세요. 지침은 클러스터 구성을 참조하세요. Amazon OpenSearch Service를 사용하면 보다 손쉽게 AWS 관리형 OpenSearch 클러스터를 구성할 수 있습니다.

실험을 시작하기 전에 OpenSearch에서 k-NN 워크로드를 실행하는 방법을 살펴보겠습니다. 먼저 인덱스를 생성해야 합니다. 인덱스는 쉽게 검색할 수 있는 방식으로 문서 집합을 가지고 있습니다. k-NN의 경우, 인덱스의 ‘mappings’을 통해 어떤 알고리즘을 사용하고 어떤 매개변수를 사용할 것인지를 OpenSearch에 알려줄 수 있습니다. 여기서는 HNSW를 검색 알고리즘으로 사용하는 인덱스를 생성합니다.

PUT my-hnsw-index
{
  "settings": {
    "index": {
      "knn": true,
      "number_of_shards": 10,
      "number_of_replicas": 1
    }
  },
  "mappings": {
    "properties": {
      "my_vector": {
        "type": "knn_vector",
        "dimension": 4,
        "method": {
          "name": "hnsw",
          "space_type": "l2",
          "engine": "nmslib",
          "parameters": {
            "ef_construction": 128,
            "m": 24
          }
        }
      }
    }
  }
}

설정에서 knn 쿼리 유형으로 인덱스를 검색할 수 있도록 settings.index.knn을 true로 활성화해야 합니다(이에 대해서는 나중에 자세히 설명합니다). 또한 샤드 수와 각 샤드가 가질 복제본 수도 설정합니다. 인덱스는 샤드 모음으로 구성됩니다. 샤딩은 OpenSearch가 클러스터의 여러 노드에 인덱스를 분산하는 방식입니다. 샤드에 대한 자세한 내용은 Amazon OpenSearch Service 도메인 크기 조정을 참조하세요.

’mappings’에서, 벡터 데이터를 저장하기 위해 knn_vector 타입의 my_vector라는 필드를 구성합니다. 또한 nmslib를 engine으로 전달하여 OpenSearch가 nmslib의 HNSW 알고리즘을 사용하도록 구성하였습니다. space_type은 l2로 설정합니다. space_type은 두 벡터 사이의 거리를 계산하는 데 사용되는 함수를 결정합니다. l2는 유클리드 거리를 나타냅니다. OpenSearch는 코사인 유사도 및 백터 내적, 멘해튼 거리(L1) 함수도 지원합니다.

인덱스가 생성되면 테스트를 위한 더미 데이터를 색인 합니다.

POST _bulk
{ "index": { "_index": "my-hnsw-index", "_id": "1" } }
{ "my_vector": [1.5, 2.5, 3.5, 4.5], "price": 12.2 }
{ "index": { "_index": "my-hnsw-index", "_id": "2" } }
{ "my_vector": [2.5, 3.5, 4.5, 5.5], "price": 7.1 } 
{ "index": { "_index": "my-hnsw-index", "_id": "3" } }
{ "my_vector": [3.5, 4.5, 5.5, 6.5], "price": 12.9 } 
{ "index": { "_index": "my-hnsw-index", "_id": "4" } }
{ "my_vector": [5.5, 6.5, 7.5, 8.5], "price": 1.2 } 
{ "index": { "_index": "my-hnsw-index", "_id": "5" } }
{ "my_vector": [4.5, 5.5, 6.5, 9.5], "price": 3.7 } 
{ "index": { "_index": "my-hnsw-index", "_id": "6" } }
{ "my_vector": [1.5, 5.5, 4.5, 6.4], "price": 10.3 }
{ "index": { "_index": "my-hnsw-index", "_id": "7" } }
{ "my_vector": [2.5, 3.5, 5.6, 6.7], "price": 5.5 }
{ "index": { "_index": "my-hnsw-index", "_id": "8" } }
{ "my_vector": [4.5, 5.5, 6.7, 3.7], "price": 4.4 }
{ "index": { "_index": "my-hnsw-index", "_id": "9" } }
{ "my_vector": [1.5, 5.5, 4.5, 6.4], "price": 8.9 }

색인이 완료되면 검색이 가능합니다.

GET my-hnsw-index/_search
{
  "size": 2,
  "query": {
    "knn": {
      "my_vector": {
        "vector": [2, 3, 5, 6],
        "k": 2
      }
    }
  }
}

IVF 또는 PQ를 사용한다면 인덱스를 생성하는 것은 조금 다릅니다. IVF알고리즘은 학습이 필요하기 때문에 인덱스를 만들기 전에 먼저 training API를 사용하여 모델을 만들어야 합니다.

POST /_plugins/_knn/models/my_ivfpq_model/_train
{
  "training_index": "train-index",
  "training_field": "train-field",
  "dimension": 128,
  "description": "My model description",
  "method": {
      "name":"ivf",
      "engine":"faiss",
      "parameters":{
        "encoder":{
            "name":"pq",
            "parameters":{
                "code_size": 8,
                "m": 8
            }
        }
      }
  }
}

training_index와 training_field는 학습 데이터가 저장되는 위치를 지정합니다. 학습 데이터의 유일한 요구 사항은 모델에 원하는 것과 동일한 차원을 가진 knn_vector 필드가 있어야 한다는 것입니다. 이 method는 검색에 사용해야 하는 알고리즘을 정의합니다.

학습이 등록되면 백그라운드에서 실행됩니다. 학습이 완료되었는지 확인하려면 GET model API로 상태를 확인할 수 있습니다.

GET /_plugins/_knn/models/my_ivfpq_model?filter_path=model_id,state
{
  "model_id" : "my_ivfpq_model",
  "state" : "created"
}

모델이 생성이 완료 되었다면 이 모델을 사용하는 인덱스를 만들 수 있습니다.

PUT /my-hnsw-index
{
  "settings" : {
    "index.knn": true,
    "number_of_shards" : 10,
    "number_of_replicas" : 1
  },
  "mappings": {
    "properties": {
      "my_vector": {
        "type": "knn_vector",
        "model_id": "my_ivfpq_model"
      }
    }
  }
}

인덱스가 생성된 후에는 HNSW에서와 마찬가지로 인덱스에 문서를 색인하고 검색할 수 있습니다.

실험

몇 가지 실험을 통해 이러한 알고리즘이 실제로 어떻게 작동하는지, 그리고 어떤 장단점이 있는지 알아봅시다. PQ를 사용하는 HNSW와 IVF 인덱스를 비교해보겠습니다. 이 실험에서는 검색 정확도, 쿼리 지연 시간 및 메모리 소비를 확인해 보고자 합니다. 이러한 트레이드 오프는 주로 대규모에서 관찰되기 때문에 128차원의 10억 개의 벡터가 포함된 BIGANN 데이터 세트를 사용합니다. 이 데이터 세트에는 유클리드 거리를 기준으로 쿼리를 가장 가까운 100개의 벡터에 매핑하는 10,000개의 테스트 데이터 쿼리도 포함되어 있습니다.

구체적으로 다음과 같은 검색 메트릭을 계산합니다.

Latency p99 (ms), Latency p90 (ms), Latency p50 (ms) – 밀리초 단위의 다양한 사분위수에서의 쿼리 지연 시간입니다.
recall@10 – 플러그인이 반환한 10개 결과에서 발견된 상위 10개 기준값 이웃의 비율입니다.
Native memory consumption (GB) – 쿼리하는 동안 플러그인에서 사용한 메모리 양입니다.

한 가지 주목할 점은 BIGANN 데이터 세트는 부호가 없는 정수를 데이터 유형으로 사용한다는 것입니다. knn_vector 필드는 부호가 없는 정수를 지원하지 않으므로 데이터가 자동으로 부동 소수점으로 변환됩니다.

실험을 실행하려면 다음 단계를 수행하세요.

OpenSearch 벤치마크 프레임워크를 사용하여 데이터 세트를 클러스터로 수집합니다(코드는 GitHub에서 찾을 수 있습니다).
수집이 완료되면, warmup API를 사용해 검색 워크로드를 위해 클러스터를 준비합니다.
클러스터에 대해 10,000개의 테스트 쿼리를 10회 실행하고 집계된 결과를 수집합니다.

쿼리는 성능을 개선하기 위해 벡터가 아닌 문서 ID만 반환합니다(이에 대한 코드는 GitHub에서 찾을 수 있습니다).

매개변수 선택

실험을 실행할 때 까다로운 점 중 하나는 매개변수를 선택하는 것입니다. 모든 매개변수를 테스트하기에는 너무 다양한 조합의 매개변수가 있습니다. 그래서 HNSW와 IVFPQ에 대해 세 가지 구성을 만들기로 결정했습니다.

검색 지연 시간 및 메모리 최적화.
리콜 최적화.
그 중간 어딘가에 위치.

각 최적화 전략에 대해 두 가지 구성을 선택했습니다.

HNSW의 경우 원하는 절충점을 달성하기 위해 m, ef_construction 및 ef_search 매개 변수를 조정할 수 있습니다.

m – 그래프에서 노드가 가질 수 있는 최대 엣지 수를 제어합니다. 각 노드가 모든 엣지를 저장해야 하므로 이 값을 늘리면 메모리 사용량이 증가하지만 그래프의 연결성이 증가하여 리콜이 향상됩니다.
ef_construction – 그래프에 노드를 추가할 때 에지에 대한 후보 대기열의 크기를 제어합니다. 이 값을 높이면 고려할 후보의 수가 증가하여 인덱스 지연 시간이 증가합니다. 하지만 더 많은 후보를 고려하게 되므로 그래프의 품질이 향상되어 검색 시 더 나은 리콜로 이어질 수 있습니다.
ef_search – ef_construction과 마찬가지로, 검색 중 그래프 탐색을 위한 후보 대기열의 크기를 제어합니다. 이 값을 높이면 검색 대기 시간이 길어지지만 회상률도 향상됩니다.

일반적으로 다음 표에 자세히 설명된 대로 매개변수를 점진적으로 늘리는 구성을 선택했습니다.


Config ID	최적화 전략	m	ef_construction	ef_search
hnsw1	메모리 및 검색 지연 시간 최적화	8	32	32
hnsw2	메모리 및 검색 지연 시간 최적화	16	32	32
hnsw3	지연 시간, 메모리 및 리콜 간의 균형	16	128	128
hnsw4	지연 시간, 메모리 및 리콜 간의 균형	32	256	256
hnsw5	리콜 최적화	32	512	512
hnsw6	리콜 최적화	64	512	512

IVF의 경우 두 가지 매개변수를 조정할 수 있습니다.

nlist – 벡터를 분할할 버킷의 수 입니다.. 이 매개변수에 대한 권장 값은 인덱스의 벡터 수에 따른 함수입니다. 한 가지 명심해야 할 것은 Lucene 세그먼트에 매핑되는 Faiss 인덱스가 있다는 것입니다. 샤드당 여러 개의 Lucene 세그먼트가 있고 OpenSearch 인덱스당 여러 개의 샤드가 있습니다. 추정을 위해 샤드당 100개의 세그먼트와 24개의 샤드가 있다고 가정했으므로, Faiss 인덱스당 약 42만 개의 벡터가 있다고 가정했습니다. 이 실험에서 nlist의 값은 4096이라 추정하고 일정하게 유지했습니다.
nprobes – 검색하는 nlist 버킷의 수입니다.. 값이 높을수록 일반적으로 검색 대기 시간이 길어지는 대신 리콜률이 향상됩니다.

PQ의 경우 두 가지 매개변수를 조정할 수 있습니다.

m – 벡터를 분할할 파티션의 수를 제어합니다. 이 값이 클수록 인코딩이 원본에 더 가까워지지만 메모리 사용량이 증가합니다.
code_size – 서브 벡터를 인코딩할 비트 수를 제어합니다. 이 값이 클수록 인코딩이 원본에 더 가까워지지만 메모리 사용량이 증가합니다. 최대값은 8이므로 모든 실험에서 8로 일정하게 유지했습니다.

다음 표에는 우리의 전략이 요약되어 있습니다.


Config ID	최적화 전략	nprobes	m (num_sub_vectors)
ivfpq1	메모리 및 검색 지연 시간 최적화	8	8
ivfpq2	메모리 및 검색 지연 시간 최적화	16	8
ivfpq3	지연 시간, 메모리 및 리콜 간의 균형	32	16
ivfpq4	지연 시간, 메모리 및 리콜 간의 균형	64	32
ivfpq5	리콜 최적화	128	16
ivfpq6	리콜 최적화	128	32

또한 IVFPQ에 사용할 훈련 데이터의 양을 파악해야 합니다. 일반적으로 Faiss 는 k-Means 학습을 포함하는 구성 요소에 대해 30,000~256,000개의 학습 벡터를 권장합니다. 이 구성의 경우, k-Means의 최대 k는 nlist 매개변수에서 4096입니다. 이 공식에 따르면 권장되는 훈련 세트 크기는 122,880개에서 1,048,576개의 벡터이므로 100만 개의 벡터로 결정했습니다. 학습 데이터는 인덱스 벡터 데이터 세트에서 가져옵니다.

마지막으로 인덱스 구성의 경우 샤드 수를 선택해야 합니다. OpenSearch의 경우 샤드 크기를 10~50GB 사이로 유지하는 것을 권장합니다. 이번 실험에서는 HNSW의 경우 64개의 샤드, IVFPQ의 경우 42개의 샤드가 적당하다고 판단했습니다. 두 인덱스 구성 모두 하나의 복제본으로 구성되었습니다.

클러스터 구성

이 실험을 실행하기 위해 OpenSearch 1.3 버전을 사용하는 Amazon OpenSearch Service를 사용해 클러스터를 생성했습니다. 메모리 크기와 비용 사이에서 적절한 절충점을 제공하는 r5 인스턴스 제품군을 사용하기로 결정했습니다.

노드 수는 노드당 알고리즘에 사용할 수 있는 메모리 양과 알고리즘에 필요한 총 메모리 양에 따라 달라집니다. 일반적으로 노드와 메모리가 많을수록 성능이 향상되지만, 이 실험에서는 비용을 최소화하고자 합니다. 노드당 사용 가능한 메모리 양은 아래의 매개 변수를 사용하여 memory_available = (node_memory - jvm_size) * circuit_breaker_limit 수식 으로 계산됩니다.

node_memory – 인스턴스의 총 메모리 입니다.
jvm_size – OpenSearch JVM 힘 크기입니다. 32GB로 설정합니다.
circuit_breaker_limit – 회로 차단기의 기본 메모리 사용량 임계값입니다. 0.5로 설정합니다.

HNSW와 IVFPQ는 메모리 요구 사항이 다르기 때문에 각 알고리즘에 필요한 메모리 양을 추정하고 그에 따라 필요한 노드 수를 결정합니다.

HNSW 알고리즘은 m = 64 인 경우 이전 섹션의 공식을 사용하여 필요한 총 메모리는 약 2,252GB입니다. 따라서 r5.12xlarge(메모리 384GB)의 경우 memory_available은 176GB이고 필요한 총 노드 수는 약 12개이며, 안정성을 위해 반올림하여 16개로 계산합니다.

IVFPQ 알고리즘은 더 적은 메모리를 필요로 하기 때문에 더 작은 인스턴스 유형인 128GB 메모리를 가진 r5.4xlarge 인스턴스를 사용할 수 있습니다. 따라서 알고리즘의 memory_available 은 48GB입니다. m = 64 인 경우 예상 알고리즘 메모리 소비량은 총 193GB이고 필요한 노드 수는 총 4개이며, 안정성을 위해 반올림하여 6개로 계산합니다.

두 클러스터 모두 전용 리더 노드로 c5.2xlarge 인스턴스 유형을 사용합니다. 이렇게 하면 클러스터의 안정성이 향상됩니다.

AWS 비용 계산기에 따르면 이 사용 사례의 경우 HNSW 클러스터의 시간당 비용은 시간당 약 $75이며, IVFPQ 클러스터의 비용은 시간당 약 $11입니다. 이는 결과를 비교할 때 기억해야 할 중요한 사항입니다.

또한 이러한 벤치마크는 인스턴스 유형과 메모리 크기가 동일한 Amazon Elastic Compute Cloud(Amazon EC2)를 사용하여 사용자 정의 인프라를 통해 실행할 수 있다는 점에 유의하세요.

결과

아래의 표에는 실험 결과가 요약되어 있습니다.


Test ID	p50 Query latency (ms)	p90 Query latency (ms)	p99 Query latency (ms)	Recall@10	Native memory consumption (GB)
hnsw1	9.1	11	16.9	0.84	1182
hnsw2	11	12.1	17.8	0.93	1305
hnsw3	23.1	27.1	32.2	0.99	1306
hnsw4	54.1	68.3	80.2	0.99	1555
hnsw5	83.4	100.6	114.7	0.99	1555
hnsw6	103.7	131.8	151.7	0.99	2055


Test ID	p50 Query latency (ms)	p90 Query latency (ms)	p99 Query latency (ms)	Recall@10	Native memory consumption (GB)
ivfpq1	74.9	100.5	106.4	0.17	68
ivfpq2	78.5	104.6	110.2	0.18	68
ivfpq3	87.8	107	122	0.39	83
ivfpq4	117.2	131.1	151.8	0.61	114
ivfpq5	128.3	174.1	195.7	0.4	83
ivfpq6	163	196.5	228.9	0.61	114

예상할 수 있듯이, 더 많은 리소스를 사용하는 HNSW 클러스터는 쿼리 대기 시간이 짧고 리콜 지수가 더 좋습니다. 그러나 IVFPQ 인덱스는 훨씬 적은 메모리를 사용합니다.

HNSW의 경우, 매개 변수를 늘리면 실제로 지연 시간을 희생하는 대신 더 나은 리콜 지수를 얻을 수 있습니다. IVFPQ의 경우 m을 늘리는 것이 리콜 지수 향상에 가장 큰 영향을 미칩니다. nproves 를 늘리면 리콜 지수는 약간 향상되지만 지연 시간이 크게 증가합니다.

결론

이 게시물에서는 OpenSearch 내에서 대규모(10억 개 이상의 데이터 포인트)로 Approximate k-NN(ANN) 검색을 수행하는 데 사용되는 다양한 알고리즘과 기법을 다루었습니다. 이전 벤치마크 섹션에서 살펴본 것처럼, 모든 메트릭을 한 번에 최적화하는 완벽한 알고리즘이나 접근 방식은 존재하지 않습니다. HNSW, IVF, PQ는 각각 k-NN 워크로드에서 서로 다른 메트릭을 최적화할 수 있게 해줍니다. 사용할 k-NN 알고리즘을 선택할 때는 먼저 사용 사례의 요구 사항(ANN 검색이 얼마나 정확해야 하는가? 얼마나 빨라야 하나요? 인프라 예산은 얼마인가?) 요구 사항을 파악한 다음 이를 충족하도록 알고리즘 구성을 조정하시기 바랍니다.

저희가 사용한 벤치마킹 코드 베이스는 GitHub에서 살펴볼 수 있습니다. Approximate k-NN 검색의 지침에 따라 지금 바로 Approximate k-NN 검색을 시작할 수도 있습니다. OpenSearch 클러스터를 위한 관리형 솔루션을 찾고 계신다면 Amazon OpenSearch Service를 확인해 보세요.

AWS 기술 블로그

OpenSearch에서 수십억 규모 검색을 위한 적합한 k-NN 알고리즘을 선택하기

Hierarchical Navigable Small Worlds(HNSW) 알고리즘

메모리 사용량

Inverted File System(IVF) 알고리즘

메모리 사용량

Product quantization(PQ) 벡터 압축

메모리 사용량

OpenSearch에서 k-NN 실행

실험

매개변수 선택

클러스터 구성

결과

결론

주요 링크 모음

팔로우하기