5가지 하드 벡터 검색 문제와 Apache Cassandra에서 이를 해결한 방법

벡터 검색은 검색 증강 생성(RAG)과 같은 방식으로 인해 생성적 AI 도구의 중요한 구성 요소입니다. 플레어 LLM이 환각을 피하면서 최신 맞춤형 정보를 통합하는 데 도움이 됩니다. . 동시에 벡터 검색은 제품이 아닌 기능입니다. 벡터는 분리되지 않고 나머지 데이터와 관련되어 있으므로 벡터를 쿼리해야 하며 나머지 데이터를 동기화하기 위해 파이프라인을 구축할 필요가 없습니다. 이를 위해 벡터 저장소를 사용하는 데이터입니다.

2023년에는 벡터 검색 제품과 프로젝트가 폭발적으로 증가하여 그중에서 선택하는 데 많은 노력이 필요했습니다. 옵션을 조사하면서 다음과 같은 어려운 문제와 이를 해결하기 위한 다양한 접근 방식을 고려해야 합니다. 여기에서는 이러한 문제를 안내하고 DataStax Astra DB 및 Apache Cassandra에 대한 벡터 검색 구현을 위해 DataStax가 이러한 문제를 어떻게 해결했는지 설명하겠습니다.

콘텐츠 개요

• 차원의 저주
• 문제 1: 확장
• 문제 2: 효율적인 가비지 수집
• 사이드바: 클라우드 애플리케이션 워크로드
• 문제 3: 동시성
• 문제 4: 디스크의 효과적인 활용
• 문제 5: 결합성
• 마무리

차원의 저주

이러한 어려운 문제의 핵심에는 연구자들이 " 차원의 저주 .” 이것이 실제로 의미하는 바는 다음과 같이 2차원 또는 3차원 공간에서 정확한 벡터 검색을 위해 작동하는 알고리즘이 있다는 것입니다. kd 나무 , 벡터의 차원이 10, 100, 1000에 도달하면 무너집니다. 결과적으로 고차원 벡터를 사용한 정확한 유사성 검색에 대한 지름길은 없습니다. 로그 시간 결과를 얻으려면 ANN(Approximous Nearest Neighbor) 알고리즘을 사용해야 하며, 이는 다음 영역에서 문제를 야기합니다.

문제 1: 확장

많은 벡터 검색 알고리즘은 단일 시스템의 메모리에 맞는 데이터 세트를 위해 설계되었으며 이는 여전히 테스트된 유일한 시나리오입니다. 앤 벤치마크 . (Ann-benchmarks는 테스트를 단일 코어로 더욱 제한합니다!) 이는 백만 개의 문서 또는 행에 대한 학술 작업에는 괜찮을 수 있지만 실제 작업 부하를 대표하는 것으로 간주될 수 있는 지 수년이 지났습니다.

다른 도메인과 마찬가지로 확장에는 복제와 파티셔닝이 모두 필요하며, 죽은 복제본 교체, 네트워크 파티션 후 복구 등을 처리하는 하위 시스템도 필요합니다.

이것은 우리에게 쉬운 일이었습니다. 확장 복제는 Cassandra의 기본 기능이며 이를 새로운 Cassandra-5.0 SAI(Storage-Attached Indexing – 참조)와 결합했습니다. CEP-7 그것이 어떻게 작동하는지, 그리고 SAI 문서 사용 방법)은 벡터 검색 구현에 강력한 확장 기능을 무료로 효과적으로 제공했습니다.

문제 2: 효율적인 가비지 수집

"가비지 수집"이란 인덱스에서 쓸모 없는 정보를 제거하는 것, 즉 삭제된 행을 정리하고 인덱스된 벡터 값이 변경된 행을 처리하는 것을 의미합니다. 이는 언급할 가치가 없어 보일 수도 있습니다. 이는 관계형 데이터베이스 세계에서 40년 동안 어느 정도 해결된 문제였지만 벡터 인덱스는 고유합니다.

핵심 문제 는 지연 시간이 짧은 검색과 재현율이 높은 결과를 모두 제공하는 우리가 알고 있는 모든 알고리즘이 그래프 기반이라는 것입니다. 사용할 수 있는 다른 벡터 인덱싱 알고리즘이 많이 있습니다. FAISS 그러나 이들 모두는 구축하기에는 너무 느리고 검색하기에는 너무 느리거나 범용 솔루션이 되기에는 너무 낮은(때로는 세 가지 모두!) 리콜을 제공합니다. 이것이 바로 제가 아는 모든 생산 벡터 데이터베이스가 그래프 기반 인덱스를 사용하는 이유입니다. 그 중 가장 간단한 것은 HNSW입니다. 계층적 탐색이 가능한 작은 세계 그래프는 다음과 같습니다. Yury Malkov 등이 2016년에 소개했습니다. ; 그 논문은 꽤 읽기가 쉬워서 적극 추천합니다. 아래에서 HNSW에 대해 자세히 알아보세요.

그래프 인덱스의 문제점은 행이나 문서가 변경될 때 이전(벡터 관련) 노드를 간단히 제거할 수 없다는 것입니다. 이 작업을 여러 번 수행하면 그래프는 쿼리 벡터와 더 유사한 영역으로 BFS(폭 우선 검색)를 지시하는 목적을 더 이상 수행할 수 없습니다.

따라서 이 가비지 수집을 수행하려면 어느 시점에서 인덱스를 다시 작성해야 합니다. 그런데 이를 언제, 어떻게 구성합니까? 변경 사항이 있을 때 항상 모든 것을 다시 빌드하면 수행되는 물리적 쓰기 작업이 엄청나게 늘어납니다. 이를 쓰기 증폭이라고 합니다. 반면에 다시 빌드하지 않으면 쿼리 시 사용되지 않는 행을 필터링하는 추가 작업("읽기 증폭")을 수행하게 됩니다.

이것은 Cassandra가 수년간 작업해온 또 다른 문제 영역입니다. SAI 인덱스는 메인 스토리지 수명주기에 연결되므로 Cassandra에도 참여합니다. 압축 , 이는 읽기와 쓰기 간의 적절한 균형을 제공하기 위해 저장 단위를 대수적으로 증가시킵니다.

사이드바: 클라우드 애플리케이션 워크로드

DataStax Astra DB는 Apache Cassandra를 기반으로 구축되어 클라우드 애플리케이션 워크로드를 위한 플랫폼을 제공합니다.

이는 다음과 같은 워크로드를 의미합니다.

• 초당 수천에서 수백만 개의 요청을 동시에 처리하며 일반적으로 각각 몇 행만 검색합니다. 이것이 감당할 수 있는 경우에도 Snowflake에서 Netflix를 실행할 수 없는 이유입니다. Snowflake 및 유사한 분석 시스템은 각각 몇 초에서 몇 분 또는 그 이상 실행되는 몇 개의 동시 요청만 처리하도록 설계되었습니다.

  
  

• 메모리보다 큼 데이터 세트가 단일 시스템의 메모리에 맞는 경우 어떤 도구를 사용하는지는 거의 중요하지 않습니다. Sqlite, MongoDB, MySQL – 모두 잘 작동합니다. 그렇지 않은 경우에는 상황이 더욱 어려워집니다. 나쁜 소식은 벡터 임베딩이 일반적으로 수 KB이거나 일반적인 데이터베이스 문서보다 크기가 더 크다는 것입니다. 따라서 비교적 빠르게 메모리보다 큰 용량에 도달하게 됩니다.

  
  

• 애플리케이션의 핵심 데이터가 그다지 중요하지 않거나 실제 기록 소스에서 다시 빌드할 수 있기 때문에 데이터가 손실되더라도 상관하지 않는다면 어떤 도구를 사용하는지는 중요하지 않습니다. Cassandra 및 Astra DB와 같은 데이터베이스는 무슨 일이 있어도 데이터의 가용성과 내구성을 유지하도록 구축되었습니다.

문제 3: 동시성

위에서도 언급했는데 그 유명한 앤 벤치마크 비교는 모든 알고리즘을 단일 코어로 제한합니다. 이는 공평한 경쟁의 장을 제공하는 동시에 지난 20년 동안 하드웨어 개선의 주요 원천을 활용할 수 있는 사람들에게 불리함을 주기도 합니다.

관련된 문제는 ann-benchmarks가 한 번에 한 가지 유형의 작업만 수행한다는 것입니다. 먼저 인덱스를 구축한 다음 쿼리합니다. 검색과 함께 인터리브된 업데이트를 처리하는 것은 선택 사항이며 심지어 장애가 될 수도 있습니다. 업데이트를 처리할 필요가 없다는 것을 알고 있다면 인공 벤치마크에서 좋아 보이는 단순화된 가정을 많이 만들 수 있습니다.

인덱스를 사용하여 여러 동시 작업을 수행하거나 인덱스가 구축된 후 업데이트하는 데 관심이 있는 경우 인덱스의 작동 방식과 관련된 장단점을 이해하기 위해 좀 더 자세히 살펴볼 필요가 있습니다.

첫째, 내가 아는 모든 범용 벡터 데이터베이스는 그래프 기반 인덱스를 사용합니다. 첫 번째 벡터가 삽입되자마자 그래프 인덱스 쿼리를 시작할 수 있기 때문입니다. 대부분의 다른 옵션에서는 쿼리하기 전에 전체 인덱스를 작성하거나 최소한 데이터의 예비 스캔을 수행하여 몇 가지 통계 속성을 알아내야 합니다.

그러나 그래프 인덱스 카테고리 내에도 여전히 중요한 구현 세부 사항이 있습니다. 예를 들어 처음에는 MongoDB Elastic과 Solr처럼 Lucene의 HNSW 인덱스 구현을 사용하면 시간을 절약할 수 있다고 생각했습니다. 그러나 우리는 Lucene이 단일 스레드, 비동시 인덱스 구성만 제공한다는 것을 빨리 알게 되었습니다. 즉, 빌드되는 동안 쿼리할 수 없으며(이 데이터 구조를 사용하는 주요 이유 중 하나여야 합니다!) 여러 스레드가 동시에 빌드하도록 허용할 수 없습니다.

HNSW 논문에서는 세분화된 잠금 접근 방식이 작동할 수 있다고 제안하지만 우리는 한 발 더 나아가 비차단 인덱스를 구축했습니다. 이것은 오픈 소스입니다. J벡터 .

JVector는 동시 업데이트를 최소 32개 스레드까지 선형적으로 확장합니다. 이 그래프는 x축과 y축 모두에서 로그 스케일링되어 스레드 수를 두 배로 늘리면 빌드 시간이 절반으로 줄어드는 것을 보여줍니다.

더 중요한 것은 JVector의 비차단 동시성이 검색과 업데이트를 혼합하여 보다 현실적인 작업 부하에 도움이 된다는 것입니다. 다음은 다양한 데이터 세트에서 Astra DB의 성능(JVector 사용)을 Pinecone과 비교한 것입니다. Astra DB는 정적 데이터 세트의 경우 Pinecone보다 약 10% 빠르지만 새 데이터를 인덱싱하는 동안에는 8배~15배 더 빠릅니다. 우리는 더 높은 처리량과 더 낮은 대기 시간에 대한 권장 사항을 기반으로 Pinecone(포드 유형: p2 및 포드 크기: x8, 복제본당 2개의 포드 포함)을 사용하여 사용 가능한 최상의 포드 계층을 선택했습니다. 솔방울은 이것이 어떤 물리적 자원에 해당하는지 공개하지 않습니다. Astra DB 측면에서는 기본 PAYG 배포 모델을 선택했으며 서버리스이므로 리소스 선택에 대해 걱정할 필요가 없었습니다. 테스트는 다음을 사용하여 수행되었습니다. NoSQL벤치 .

Astra DB는 더 높은 재현율과 정밀도를 유지하면서 이를 수행합니다( F1은 재현율과 정밀도의 조합입니다 ) :

문제 4: 디스크의 효과적인 활용

우리는 HNSW 그래프 인덱싱 알고리즘 인덱스 구축이 빠르고, 쿼리가 빠르고, 정확하고, 구현이 간단하기 때문입니다. 그러나 여기에는 잘 알려진 단점이 있습니다. 즉, 많은 메모리가 필요합니다.

HNSW 인덱스는 일련의 레이어로, 기본 레이어 위의 각 레이어는 이전 노드 수의 약 10%입니다. 이를 통해 상위 레이어가 건너뛰기 목록 역할을 할 수 있어 모든 벡터가 포함된 하위 레이어의 오른쪽 근처에 검색이 집중될 수 있습니다.

그러나 이 설계는 (모든 그래프 인덱스와 공통적으로) "디스크 캐시가 우리를 구할 것입니다"라고 말할 수 없다는 것을 의미합니다. 왜냐하면 일반적인 데이터베이스 쿼리 작업 부하와 달리 그래프의 모든 벡터는 거의 동일한 확률을 갖기 때문입니다. 검색과 관련이 있습니다. (예외는 캐시할 수 있고 수행할 수 있는 상위 레이어입니다.)

다음은 Lucene을 사용했을 때 64GB RAM이 장착된 데스크탑에서 Wikipedia 기사 청크(디스크의 약 120GB)로 구성된 100M 벡터 데이터 세트를 제공하는 프로필은 다음과 같습니다.

Cassandra는 디스크에서 벡터를 읽는 데 거의 모든 시간을 소비합니다.

이 문제를 해결하기 위해 우리는 DiskANN이라는 고급 알고리즘을 구현하고 이를 독립형 임베디드 벡터 검색 엔진으로 오픈소스화했습니다. J벡터 . (구체적으로 JVector는 다음에 설명된 DiskANN의 증분 버전을 구현합니다. FreshDiskANN 간단히 말해서, DiskANN은 HNSW보다 가장자리가 더 긴 단일 레벨 그래프와 벡터 및 이웃의 최적화된 레이아웃을 사용하여 디스크 IOPS를 줄이고 벡터의 압축된 표현을 메모리에 유지하여 유사성 계산 속도를 높입니다. 이로 인해 Wikipedia 작업 부하의 처리량이 3배로 늘어납니다.

클라이언트/서버 구성 요소가 없는 순수 임베디드 시나리오에서 HNSW와 DiskANN의 모습은 다음과 같습니다. 이는 Lucene(HNSW) 및 JVector(DiskANN)에서 Deep100M 데이터 세트를 검색하는 속도를 측정합니다. Lucene 인덱스는 인덱스와 원시 벡터를 포함하여 55GB입니다. JVector 인덱스는 64GB입니다. 검색은 RAM에 인덱스를 저장하는 데 필요한 메모리의 약 1/3 정도인 내 24GB MacBook에서 수행되었습니다.

문제 5: 결합성

데이터베이스 시스템의 맥락에서 결합 가능성은 다양한 기능과 기능을 일관된 방식으로 원활하게 통합하는 능력을 의미합니다. 이는 벡터 검색과 같은 새로운 범주의 기능 통합을 논의할 때 특히 중요합니다. 장난감이 아닌 애플리케이션에는 항상 클래식과 크루드 데이터베이스 기능과 새로운 벡터 검색이 추가되었습니다.

간단한 것을 고려하십시오 AI 챗봇 Astra DB용 샘플 애플리케이션입니다. 이것은 사용자 질문에 응답하기 위해 벡터 검색을 사용하여 LLM에 적절한 문서를 표시하는 순수한 RAG 응용 프로그램입니다. 그러나 이와 같은 간단한 데모라도 대화 기록을 검색하기 위해 Astra DB에 "정상", 벡터가 아닌 쿼리를 수행해야 합니다. 이는 이미 기록된 내용을 "기억"할 수 있도록 LLM에 대한 모든 요청에도 포함되어야 합니다. 촬영 장소. 따라서 주요 쿼리에는 다음이 포함됩니다.

1. 사용자의 질문과 가장 관련성이 높은 문서(또는 문서 조각)를 찾습니다.
2. 사용자 대화에서 마지막 20개의 메시지를 검색합니다.

보다 현실적인 사용 사례에서는 당사의 솔루션 엔지니어 중 한 명이 최근 제품 카탈로그에 의미 체계 검색을 추가하고 용어 기반 일치도 지원하고자 하는 아시아의 한 회사와 협력하고 있었습니다. 예를 들어, 사용자가 [“red” 볼 밸브]를 검색하는 경우 벡터 임베딩이 의미상 얼마나 유사하더라도 설명이 “red”라는 용어와 일치하는 항목으로 검색을 제한하려고 합니다. 세션 관리, 주문 내역, 장바구니 업데이트와 같은 기존 기능 외에 주요 새 쿼리는 다음과 같습니다. 인용된 용어가 모두 포함된 제품으로 제품을 제한한 다음 사용자 검색과 가장 유사한 항목을 찾습니다.

이 두 번째 예는 애플리케이션에 기존 쿼리 기능과 벡터 검색이 모두 필요할 뿐만 아니라 동일한 쿼리에서 각 요소를 사용할 수 있어야 하는 경우가 많다는 점을 분명히 보여줍니다.

이 신생 분야의 최신 기술은 내가 "일반" 데이터베이스에서 고전적인 쿼리, 벡터 데이터베이스에서 벡터 쿼리라고 부르는 작업을 수행한 다음 두 가지가 모두 가능할 때 임시 방식으로 두 가지를 함께 연결하는 것입니다. 동시에 필요합니다. 이는 오류가 발생하기 쉽고 느리며 비용이 많이 듭니다. 유일한 장점은 더 나은 솔루션이 나올 때까지 작동하게 할 수 있다는 것입니다.

Astra DB에서는 Cassandra SAI를 기반으로 더 나은 솔루션을 구축(오픈 소스)했습니다. SAI를 사용하면 Cassandra 안정 및 압축 수명 주기에 모두 연결된 사용자 정의 인덱스 유형을 생성할 수 있으므로 Astra DB는 개발자가 부울 조건자, 용어 기반 검색 및 벡터 검색을 오버헤드 없이 혼합하고 일치시킬 수 있도록 하는 것이 간단합니다. 별도의 시스템을 관리하고 동기화합니다. 이를 통해 생성적 AI 애플리케이션을 구축하는 개발자는 생산성을 높이고 출시 시간을 단축하는 보다 정교한 쿼리 기능을 얻을 수 있습니다.

마무리

벡터 검색 엔진은 확장, 가비지 수집, 동시성, 효과적인 디스크 사용 및 구성 가능성을 비롯한 여러 아키텍처 문제가 있는 중요한 새 데이터베이스 기능입니다. 저는 Astra DB용 벡터 검색을 구축하면서 Cassandra의 기능을 활용하여 생성 AI 애플리케이션 개발자에게 최고의 경험을 제공할 수 있었다고 믿습니다. 여기에서 Astra DB에 대해 자세히 알아보세요. , 또는 벡터 검색 알고리즘에 대해 자세히 알아보고 싶다면 다음을 확인하세요. J벡터 .

- 작성자: Jonathan Ellis, DataStax