Milvus는 쿼리 작업을 어떻게 스케줄링하나요
이 글에서는 Milvus가 쿼리 작업을 스케줄링하는 방법을 논의합니다. 또한 Milvus 스케줄링 구현을 위한 문제, 해결책, 향후 방향에 대해서도 이야기합니다.
배경
Managing Data in Massive-Scale Vector Search Engine에서 알 수 있듯이, 벡터 유사도 검색은 고차원 공간에서 두 벡터 간의 거리로 구현됩니다. 벡터 검색의 목표는 대상 벡터에 가장 가까운 K개의 벡터를 찾는 것입니다.
벡터 거리를 측정하는 방법은 유클리드 거리와 같이 다양합니다:
유클리드 거리.
여기서 x와 y는 두 벡터입니다. n은 벡터의 차원입니다.
데이터셋에서 K개의 가장 가까운 벡터를 찾기 위해서는 검색 대상인 데이터셋의 모든 벡터와 대상 벡터 사이의 유클리드 거리를 계산해야 합니다. 그런 다음 벡터를 거리순으로 정렬하여 K개의 가장 가까운 벡터를 얻습니다. 계산 작업량은 데이터셋의 크기에 정비례합니다. 데이터셋이 클수록 쿼리에 더 많은 계산 작업이 필요합니다. 그래프 처리에 특화된 GPU는 필요한 연산 능력을 제공할 수 있는 많은 코어를 가지고 있습니다. 따라서 Milvus 구현 중에는 멀티 GPU 지원도 고려됩니다.
기본 개념
데이터 블록（TableFile）
대규모 데이터 검색 지원을 개선하기 위해 Milvus의 데이터 저장소를 최적화했습니다. Milvus는 테이블의 데이터를 크기별로 여러 데이터 블록으로 분할합니다. 벡터 검색 중에 Milvus는 각 데이터 블록에서 벡터를 검색하고 결과를 병합합니다. 하나의 벡터 검색 작업은 N개의 독립적인 벡터 검색 작업(N은 데이터 블록의 수)과 N-1개의 결과 병합 작업으로 구성됩니다.
작업 큐（TaskTable）
각 Resource에는 해당 Resource에 속한 작업을 기록하는 작업 배열이 있습니다. 각 작업은 Start, Loading, Loaded, Executing, Executed를 포함한 다양한 상태를 가집니다. 컴퓨팅 장치의 Loader와 Executor는 동일한 작업 큐를 공유합니다.
쿼리 스케줄링
쿼리 스케줄링.
- Milvus 서버가 시작되면, Milvus는
server_config.yaml구성 파일의gpu_resource_config매개변수를 통해 해당 GpuResource를 실행합니다. DiskResource와 CpuResource는 여전히server_config.yaml에서 편집할 수 없습니다. GpuResource는search_resources와build_index_resources의 조합이며, 다음 예시에서는{gpu0, gpu1}로 지칭됩니다:
샘플 코드.
예시.
- Milvus가 요청을 수신합니다. 테이블 메타데이터는 외부 데이터베이스에 저장되며, 단일 호스트의 경우 SQLite 또는 MySQl이고 분산 환경의 경우 MySQL입니다. 검색 요청을 수신한 후 Milvus는 테이블이 존재하는지와 차원이 일치하는지 검증합니다. 그런 다음 Milvus는 테이블의 TableFile 목록을 읽습니다.
Milvus가 tablefile 목록을 읽습니다.
- Milvus가 SearchTask를 생성합니다. 각 TableFile의 계산은 독립적으로 수행되므로 Milvus는 각 TableFile에 대해 SearchTask를 생성합니다. 작업 스케줄링의 기본 단위로서 SearchTask는 대상 벡터, 검색 매개변수, TableFile의 파일 이름을 포함합니다.
테이블 파일 목록 작업 생성기.
- Milvus가 컴퓨팅 장치를 선택합니다. SearchTask가 계산을 수행하는 장치는 각 장치의 예상 완료 시간에 따라 결정됩니다. 예상 완료 시간은 현재 시간과 계산이 완료될 것으로 예상되는 시간 사이의 예상 간격을 나타냅니다.
예를 들어 SearchTask의 데이터 블록이 CPU 메모리에 로드되면, 다음 SearchTask는 CPU 연산 작업 큐에서 대기하고 GPU 연산 작업 큐는 유휴 상태입니다. CPU의 예상 완료 시간은 이전 SearchTask와 현재 SearchTask의 예상 시간 비용의 합과 같습니다. GPU의 예상 완료 시간은 데이터 블록이 GPU에 로드되는 시간과 현재 SearchTask의 예상 시간 비용의 합과 같습니다. Resource에서 SearchTask의 예상 완료 시간은 해당 Resource에 있는 모든 SearchTask의 평균 실행 시간과 같습니다. 그런 다음 Milvus는 예상 완료 시간이 가장 짧은 장치를 선택하고 SearchTask를 해당 장치에 할당합니다.
여기서는 GPU1의 예상 완료 시간이 더 짧다고 가정합니다.
GPU1 shorter estimated completion time.
Milvus는 SearchTask를 DiskResource의 작업 큐에 추가합니다.
Milvus는 SearchTask를 CpuResource의 작업 큐로 이동합니다. CpuResource의 로딩 스레드는 작업 큐에서 각 작업을 순차적으로 로드합니다. CpuResource는 해당 데이터 블록을 CPU 메모리로 읽어옵니다.
Milvus는 SearchTask를 GpuResource로 이동합니다. GpuResource의 로딩 스레드는 CPU 메모리에서 GPU 메모리로 데이터를 복사합니다. GpuResource는 해당 데이터 블록을 GPU 메모리로 읽어옵니다.
Milvus는 GpuResource에서 SearchTask를 실행합니다. SearchTask의 결과는 비교적 작기 때문에, 결과는 CPU 메모리로 직접 반환됩니다.
Scheduler.
- Milvus는 SearchTask의 결과를 전체 검색 결과에 병합합니다.
Milvus merges search task results.
모든 SearchTask가 완료되면, Milvus는 전체 검색 결과를 클라이언트에 반환합니다.
인덱스 구축
인덱스 구축은 병합 과정을 제외하면 기본적으로 검색 과정과 동일합니다. 이에 대해서는 자세히 다루지 않겠습니다.
성능 최적화
캐시
앞서 언급했듯이, 데이터 블록은 연산 전에 CPU 메모리나 GPU 메모리와 같은 해당 저장 장치에 로드되어야 합니다. 반복적인 데이터 로딩을 방지하기 위해 Milvus는 LRU (Least Recently Used) 캐시를 도입합니다. 캐시가 가득 차면 새 데이터 블록이 오래된 데이터 블록을 밀어냅니다. 현재 메모리 크기를 기준으로 구성 파일을 통해 캐시 크기를 사용자 지정할 수 있습니다. 데이터 로딩 시간을 효과적으로 절약하고 검색 성능을 향상시키기 위해 검색 데이터를 저장할 큰 캐시를 권장합니다.
데이터 로딩과 연산의 중첩
캐시만으로는 더 나은 검색 성능에 대한 요구를 충족할 수 없습니다. 메모리가 부족하거나 데이터셋의 크기가 너무 클 때는 데이터를 다시 로드해야 합니다. 데이터 로딩이 검색 성능에 미치는 영향을 줄여야 합니다. 디스크에서 CPU 메모리로든 CPU 메모리에서 GPU 메모리로든 데이터 로딩은 IO 작업에 속하며 프로세서의 계산 작업은 거의 필요하지 않습니다. 따라서 더 나은 리소스 사용을 위해 데이터 로딩과 연산을 병렬로 수행하는 것을 고려합니다.
데이터 블록에 대한 연산을 3단계(디스크에서 CPU 메모리로 로딩, CPU 연산, 결과 병합) 또는 4단계(디스크에서 CPU 메모리로 로딩, CPU 메모리에서 GPU 메모리로 로딩, GPU 연산 및 결과 검색, 결과 병합)로 나눕니다. 3단계 연산을 예로 들면, 3단계를 담당하는 3개의 스레드를 실행하여 명령어 파이프라이닝처럼 작동하게 할 수 있습니다. 결과 집합은 대부분 작기 때문에 결과 병합에는 많은 시간이 걸리지 않습니다. 경우에 따라 데이터 로딩과 연산의 중첩은 검색 시간을 1/2로 줄일 수 있습니다.
Sequential overlapping load Milvus.
문제와 해결책
서로 다른 전송 속도
이전에는 Milvus가 멀티 GPU 작업 스케줄링에 Round Robin 전략을 사용했습니다. 이 전략은 우리의 4-GPU 서버에서 완벽하게 작동했으며 검색 성능은 4배 향상되었습니다. 그러나 우리의 2-GPU 호스트에서는 성능이 2배 향상되지 않았습니다. 몇 가지 실험을 수행한 결과, 한 GPU의 데이터 복사 속도는 11 GB/s였지만 다른 GPU의 경우 3 GB/s라는 것을 발견했습니다. 메인보드 문서를 참조한 후, 메인보드가 하나의 GPU에는 PCIe x16으로, 다른 GPU에는 PCIe x4로 연결되어 있음을 확인했습니다. 즉, 이러한 GPU들은 서로 다른 복사 속도를 가지고 있습니다. 이후 각 SearchTask에 대해 최적의 디바이스를 측정하기 위해 복사 시간을 추가했습니다.
향후 작업
복잡성이 증가한 하드웨어 환경
실제 조건에서는 하드웨어 환경이 더 복잡할 수 있습니다. 여러 CPU, NUMA 아키텍처의 메모리, NVLink 및 NVSwitch가 있는 하드웨어 환경에서는 CPU/GPU 간 통신이 많은 최적화 기회를 제공합니다.
쿼리 최적화
실험 중에 성능 향상을 위한 몇 가지 기회를 발견했습니다. 예를 들어, 서버가 동일한 테이블에 대한 여러 쿼리를 수신할 때, 특정 조건에서는 쿼리를 병합할 수 있습니다. 데이터 지역성을 활용함으로써 성능을 향상시킬 수 있습니다. 이러한 최적화는 향후 개발에서 구현될 예정입니다. 이제 우리는 단일 호스트, 멀티 GPU 시나리오에서 쿼리가 어떻게 스케줄링되고 수행되는지 이미 알고 있습니다. 앞으로의 글에서 Milvus의 더 많은 내부 메커니즘을 계속 소개하겠습니다.
계속 읽기
Announcing VDBBench 1.0: Open-Source VectorDB Benchmarking with Your Real-World Production Workloads
Discover VDBBench 1.0, an open-source tool for benchmarking vector databases with real-world production data, streaming ingestion, and concurrent workloads.
Our Journey to 35K+ GitHub Stars: The Real Story of Building Milvus from Scratch
Join us in celebrating Milvus, the vector database that hit 35.5K stars on GitHub. Discover our story and how we’re making AI solutions easier for developers.
Creating Collections in Zilliz Cloud Just Got Way Easier
We've enhanced the entire collection creation experience to bring advanced capabilities directly into the interface, making it faster and easier to build production-ready schemas without switching tools.