[Database] Vector DB Milvus 공식 문서 정리

공식 문서를 보면서 공부한 내용을 정리합니다.

 

 

 

용어 정리

• PChannel : Topic에 저장
• VChannel : Collection의 Shard와 동일
• Collection : RDB의 Table과 유사하며 Entity를 저장하고 관리하는 역할을 수행
• Entity : 현실 세계에서의 객체를 나타내는 필드 그룹으로 구성된다. 각 Entity는 고유한 Primary key로 표시된다.
• Field : Entity를 구성하는 단위
• Log Broker : Playback(재생?)을 지원하는 Pub-Sub 시스템이다. 스트리밍 데이터 지속성, 안정적인 비동기 쿼리 실행, 이벤트 알림
• Log Sequence : Milvus에서 수집 상태를 변경하는 모든 작업을 기록
• Log Snapshot : Vector DB 데이터에 대한 업데이트 및 변경 사항을 기록하고 처리하는 Segment의 작은 단위인 바이너리 로그 파일이다. InsertBinlog, DeleteBinlog, DDLBinlog 3가지 유형의 binlog가 존재한다.
• Partition : Collection의 분할이다. Milvus는 수집 데이터를 물리적 저장소의 여러 부분을 나누는 것을 지원함
• Schema : 각 컬렉션에는 컬렉션의 모든 필드, automatic ID(Primary Key), 할당 활성화 및 컬렉션 설명을 정의하는 자체 컬렉션 스키마가 있다. 컬렉션 스키마에는 필드의 이름, 데이터 유형 및 기타 속성을 정의하는 필드 스키마도 포함
• Segment : 삽입된 데이터를 보관하기 위해 Milvus가 자동으로 생성한 데이터 파일이다. 컬렉션에는 여러 세그먼트가 있을 수 있고 세그먼트에는 여러 Entity가 있을 수 있다. 벡터 유사성 검색 중에 Milvus는 각 세그먼트를 스캔하고 검색 결과를 반환한다.

 

---

1.1. Vector DB를 왜 쓰는가?

유사한 벡터를 찾기 위해 벡터 데이터베이스를 활용할 수 있다. 이미지, 텍스트, PDF, 음성 등의 데이터들을 벡터 임베딩하여 벡터화하고 이를 기반으로 유사한 벡터를 찾을 수 있다.

• 상품과 평점 및 특징이 비슷한 상품을 검색한다.
• 입력으로 주어진 문서의 토픽과 감정이 비슷한 문서를 찾는다.
• 입력으로 주어진 이미지와 비슷한 이미지를 찾는다.

 

1.2. Milvus 특징

Milvus는 Vector만을 취급하는 특수 데이터베이스이며 과학 및 AI 애플리케이션을 위한 대규모 벡터 검색을 수행할 수 있도록 도와준다.

다음의 특징이 있다.

• 개발자 친화적 : Python, Java, Go, C++ 등 SDK와 Restful API 지원이 잘 되어 있다.
• 고급 쿼리 지원 : 속성 필터링 및 멀티 벡터 쿼리 등을 지원한다.
• 인덱스 : 벡터 검색을 빠르게 수행하기 위해 인덱싱이 필요하다.
• 동적 데이터 : LSM 기반의 구조를 채용해 벡터를 동적으로 관리한다. 즉 삽입, 삭제가 가능하도록 했으며 스냅샷 격리를 지원해 일관성 있는 실시간 검색을 가능하게 했다.

 

1.3. 시스템 디자인

 

Mulvus의 시스템은 쿼리 엔진, GPU 엔진, 저장소 3가지로 구분된다.

• 쿼리 프로세싱 : 벡터 쿼리, 속성 필터링, 멀티 벡터 쿼리 연산을 수행한다.
  • Entity : vector data & non-vector data
• 인덱싱 : Milvus에서는 IVF 계열의 인덱스와 HNSW와 같은 그래프 인덱스를 지원하고 있으며 앞으로 새로운 벡터 인덱스가 연구되더라도 쉽게 추가할 수 있도록 설계되어 있다.
  • IVF 인덱스 : 보로노이 다이어그램을 연상하게 하는 각 벡터들의 중심점을 선정하고 그 점들간의 구분선을 만든다.
• 동적 데이터 관리 : Entity data는 LSM Tree를 이용하여 저장/삭제 연산을 수행한다.
  • LSM Tree는 실시간으로 대량의 데이터를 저장하는데 용이
  • B-Tree는 읽기 중심의 연산을 처리하는데 용이
• 스토리지 관리 : 1개의 Entity는 1개 이상의 Vector 정보와 Attribute 정보를 가지고 있다.
  • Vector 정보는 연속적으로 저장
  • Attribute 정보는 Column-based 저장소를 사용한다. (데이터 압축 및 쿼리 효율성을 위해서임)
  • Apache Parquet와 유사한 방식으로 저장된다.
• Buffer Pool : Milvus는 쿼리에 필요한 데이터가 대부분 메모리에 상주해 있을 것이라고 가정한다.
  • 만약 이런 가정이 틀렸다면 LRU Cache buffer manager에 의존하여 데이터를 메모리로 가져온다.
• 멀티 스토리지 : Local File System, Amazon S3, HDFS를 포함한 다수의 스토리지 포맷을 지원한다.

 

1.4. CPU / GPU를 이용한 고성능 쿼리 구현

 

1.4.1. IVF Index

IVF(Inverted File Index) : 유사한 벡터 데이터를 찾기 위한 인덱스 자료구조이며 양자화(Quantization) 알고리즘이라고도 불린다.

 

IVF_FLAT 대략적인 동작 과정

1. Vector를 일정한 개수(M)으로 나눈다.
2. K-means clustering을 수행하여 검색의 범위 축소
3. 이 때 어떤 방식으로 인코딩 할지(양자화 할지)에 따라 종류가 나뉘게 된다.
   1. IVF_FLAT
   2. IVF_SQ8
   3. IVF_PQ
   4. …

 

입력값으로 주어진 벡터 쿼리가 어느 그룹에 속하는지만 효율적으로 찾을 수 있다면 인덱스는 완성된다.

단, 다이어그램에 애매하게 걸친 벡터가 존재할 수 있는데 이를 Edge Problem 이라고 부른다.

→ 그래서 IVF Index에서는 최대 몇개의 그룹을 탐색할건지 결정하는 nprobe 값을 파라미터로 결정해야 한다. 이 값을 결정하는데에 성능과 정확도 사이에 트레이드 오프가 존재한다.

 

→ 당연히 높은값을 쓸 수록 정확도는 올라가지만 더 많은 벡터들을 조회해야 하기에 성능이 떨어진다는 단점이 있다.

 

1.4.2. Cache-aware Optimization

IVF 계열의 인덱스를 사용하여 쿼리를 수행 시 주어진 M개의 쿼리를 어떻게 효율적으로 처리할지가 문제가 된다. 왜냐하면 실제 애플리케이션에서는 동시에 m개의 배치 쿼리를 던질 수 있기 때문에 빠르게 처리되어야 한다.

 

Milvus는 페이스북 Faiss를 포크한 프로젝트인데 Faiss에서는 대량의 캐시 미스가 발생하여 성능 비효율이 보인다고 진단했다.

 

Milvus에서 각 스레드는 일정한 크기 b=n/t 만큼의 데이터 벡터를 할당받고 각 쿼리는 L3 CPU Cache에 알맞도록 s 그룹으로 파티셔닝하여 병렬로 처리한다.

 

예를 들어 top-k 유사도 탐색은 각 쿼리 블록마다 병렬로 이루어지며 결과를 동기화하기 위한 오버헤드를 줄이기 위해 결과를 힙(Heap)에 저장한다.

 

 

Heap은 스레드마다 할당되며 각 쿼리의 결과가 스레드의 각 Heap에 전파되며 나중에 병합하여 top-k 유사도 결과를 도출한다.

이런 구조를 사용할 경우 m/(s*t)만큼만 전체 데이터 접근에 필요하므로 성능을 향상시킬 수 있다.

 

1.4.3. SIMD-aware Optimization

SIMD는 CPU 내에서 하나의 명령어로 다수의 데이터를 처리하는 것을 말한다.

 

원소의 개수가 N개일 경우 N만큼의 합 명령어가 필요하지만 SIMD를 사용하면 하나의 명령어로 벡터의 합을 병렬로 처리하도록 CPU 자체적으로 지원한다.

 

---

 

2. Milvus docs

주요 개념

• 구조화되지 않은 데이터
• 벡터 삽입(Embedding)
• 벡터 유사성 검색 : 가장 유사한 벡터를 찾는 프로세스

인덱스 유형

Milvus는 ANNS(Approximous Nearest Neighbors Search)를 사용한다.

• FLAT : FLAT은 수백만 규모의 소규모 데이터 세트에서 완벽하고 정확한 검색 결과를 찾는 시나리오에 가장 적합
• IVF_FLAT : 양자화 기반 인덱스이며 정확도와 쿼리 속도 간 이상적인 균형을 추구하는 시나리오에 가장 적합
• IVF_SQ8 : 양자화 기반 인덱스이며 리소스를 크게 줄이려는 시나리오에 적합
• IVF_PQ : 양자화 기반 인덱스이며 정확성을 희생하더라도 높은 쿼리 속도를 추구하는 시나리오에 적합
• HNSW : 그래프 기반 인덱스로 검색 효율성이 요구되는 시나리오에 가장 적합

유사성 측정 항목

Milvus에서는 유사성 메트릭을 사용하여 벡터 간의 유사성을 측정한다.

부동 소수 임베딩(Floating embedding)에 널리 쓰이는 측정 항목들

• Euclidean distance (L2) : 컴퓨터 비전 분야에서 사용
• Inner product (IP) : 자연어 처리(NLP)분야에서 사용
• Hamming : 자연어 처리(NLP)분야에서 사용
• Jaccard : 분자 유사성 검색 분야

 

2.1. Architecture

 

 

 

 

Access Layer

Stateless Proxy group으로 구성되었으며 사용자에 대한 엔드포인트를 제공한다.

DML과 Produce를 담당한다.

 

Coordinator Service

Worker node에 작업을 할당한다. 클러스터 토폴로지 관리, 로드 밸런싱, 타임스탬스 생성, 데이터 선언 및 데이터 관리

• Root Coordinator : DDL(데이터 정의 언어), DCL(데이터 제어 언어) 요청 처리 및 TSO 및 타임 티커 발행 관리
• Query Coordinator : 쿼리 노드에 대한 토폴로지 및 로드 밸런싱을 관리
• Data Coordinator : 데이터 노드의 토폴로지를 관리하고 메타데이터를 유지하며 플러시, 압축 및 기타 백그라운드 데이터 작업을 트리거

 

Worker Node

Coordinator 서비스의 지침을 따르고 Proxy에서 DML(데이터 조작 언어) 명령얼 실행하는 단순 실행자이며 Stateless component

• Query node : 로그 브로커를 컨슈밍하며 증분 로그 데이터를 가져온 뒤 segments로 합쳐서 변환한다. 그 후 Object data로부터 기록 데이터를 load하고 Vector와 Scala 데이터간 하이브리드 검색을 수행한다.
• Data node : 로그 브로커를 컨슈밍하며 증분 로그 데이터를 가져온 뒤 변이 요청을 처리하고 로그 데이터를 로그 스냅샷으로 압축하여 Object Storage에 저장한다.
• Index node : 인덱스를 구축한다. 메모리에 상주할 필요가 없으며 Serverless framework로 구현될 수 있음

 

Storage

• Meta Storage : collection schema, 노드 상태, 메시지 컨슈밍 체크포인트등과 같은 메타데이터의 스냅샷을 저장한다. Milvus에서는 Meta Storage로 ETCD를 선택하였으며 서비스 등록 및 상태 확인에도 ETCD를 사용한다.
• Object Storage : Log의 스냅샷 파일, Scala 및 Vector 데이터용 인덱스 파일, 중간 쿼리 결과를 저장한다.
• Log Broker : 스트리밍 데이터 지속성, 안정적인 비동기 쿼리 실행, 이벤트 알림 및 쿼리 결과 반환을 담당한다. 또한 Worker node가 시스템 고장에서 복구될 때 증분 데이터의 무결성 보장

 

 

2.2. Data Processing

Data Insertion

Milvus의 각 컬렉션에 대해 샤드 수를 지정할 수 있으며 각 샤드를 가상 채널(vchannel)에 해당한다.

 

 

Milvus는 로그 브로커의 각 vchannel에 물리적 채널(pchannel)을 할당하며 들어오는 모든 삽입/삭제 요청은 기본키의 해시값을 기반으로 샤드로 라우팅된다.

 

 

 

위 프로세스에는 DML 요청 검증, 로그 시퀀스 게시-구독, 스트리밍 로그에서 로그 스냅샷으로 변환, 로그 스냅샷 지속성 4가지 작업이 포함된다.

4가지 작업은 서로 분리되어 각 작업이 해당 노드 유형에 의해 처리되도록 한다.

 

 

 

Index building

 

Milvus의 Collection은 여러 Segment로 분할되며 Query node는 Segment별로 인덱스를 로드한다.

 

검색 요청이 도착하면 동시 검색(concurrent search)를 위해 모든 쿼리 노드에 브로드캐스팅되고 각 노드는 local segment를 잘라내고 기준을 충족하는 벡터를 검색하고 검색 결과를 반환한다.

 

쿼리 노드의 역할은 다음처럼 2가지만 담당한다.

• Query coordinator로부터 전달받은 명령을 기반으로 segment 파일들을 로드 및 해체한다.
• 로드된 local segment 내에서 검색을 수행한다. 그리고 proxy는 최종 결과를 클라이언트에 반환하는 역할을 수행한다.

 

 

Segment의 타입을 알아보자.

 

Segment는 증분 데이터용인 growing segment와 기록 데이터용인 sealed segment(봉인된 세그먼트)가 있다.

 

쿼리 노드는 vchannel을 구독하여 segment가 성장함에 따라 증분 데이터(최신 업데이트된 데이터)를 컨슈밍한다. growing segment가 미리 정의된 임계값에 도달하면 Data coordinator는 이를 Sealed(봉인)하고 index building이 시작된다.

 

그런 다음 Query coordinator에 의해 시작된 Handoff 작업은 증북 데이터를 기록 데이터로 바꾼다. Query coordinator는 메모리 사용량, CPU 오버헤드 및 Segment number에 따라 모든 쿼리 노드에 봉인된 Segment를 균등하게 배포한다.

 

 

2.3. Vector Index

In-Memory Index

NOTE : 벡터 필드는 하나의 인덱스 유형만 지원하며 인덱스 유형을 전환할 때 이전 인덱스는 자동으로 삭제된다.

• ANNS Vector Index : 대부분의 Vectror index 유형은 Approximous Nearest Neighbors Search 알고리즘을 사용한다.
  • 구현 방법에 따라 ANNS Index는 4가지 범주로 나눌 수 있다.
    • Tree-based index
    • Graph-based index
    • Hash-based index
    • Quantization-based index

Milvus에서 지원되는 인덱스는 3가지 범주로 나눌 수 있음

• 부동 소수점 임베딩을 위한 인덱스
  • FLAT : N/A
  • IVF_FLAT : 양자화 기반 인덱스
  • IVF_SQ8 : 양자화 기반 인덱스
  • IVF_PQ : 양자화 기반 인덱스
  • HNSW : 그래프 기반 인덱스
  • SCANN : 양자화 기반 인덱스
• 바이너리 임베딩을 위한 인덱스
  • BIN_FLAT : 양자화 기반 인덱스
  • BIN_IVF_FLAT : 양자화 기반 인덱스
• 희소 임베딩을 위한 인덱스
  • SPARSE_INVERTED_INDEX : 반전된 인덱스
  • SPARSE_WAND : 반전된 인덱스

GPU Index

높은 처리량, 낮은 대기 시간 및 높은 회수율 시나리오에서 검색 성능과 효율성을 가속화하기 위해 다양한 GPU 인덱스 유형을 지원한다.

 

 

 

종류

• GPU_CAGRA
• GPU_IVF_FLAT
• GPU_IVF_PQ
• GPU_BRUTE_FORCE

 

결론

현재 Milvus는 효율적인 검색 작업을 위해 모든 인덱스를 GPU 메모리에 로드한다. 로드할 수 있는 데이터 양은 GPU 메모리 크기에 따라 다르다.

• GPU_CAGRA : 메모리 사용량이 원본 벡터 데이터의 약 1.8배
• GPU_IVF_FLAT / GPU_BRUTE_FORCE : 원본 데이터 크기와 동일한 메모리가 필요
• GPU_IVF_PQ : 압축 매개변수 설정에 따라 더 작은 메모리 공간을 활용합니다.