DiskANN Explorer: Поиск векторов в масштабе миллиардов из SSD
DiskANN Хранит крошечную копию каждого вектора, сжатую с помощьюPQ, в папке RAM, а полные векторы и граф — на SSD. Поиск проходит по графу с помощью недорогих сравнений RAM, а затем переранжирует лучших кандидатов с помощью нескольких дорогостоящих операций чтения с диска.
Почему существует « DiskANN »: «стена памяти»
Один стандартный диск SSD легко вмещает всю информацию на дисковой стороне. Сторона RAM помещается в любой ноутбук. Без приёма PQ вам понадобился бы сервер с сотнями гигабайт RAM, чтобы хотя бы загрузить набор данных.
Стоимость на данный момент
PQ ≈ 1 µs, SSD ≈ 100 µs. Реальные числа зависят от аппаратного обеспечения.Статистика поиска
Как работает « DiskANN »
- Постройте граф « Vamana »: однослойный граф kNN (степень
R), оптимизированный для последовательной организации данных на диске. Никакой иерархии — только один большой граф. - Квантование и разделение хранилища: каждый вектор получает крошечный код « PQ » (например, 32 байта). Коды « PQ » хранятся на сайте RAM. Полные векторы и ребра графа хранятся на сайте SSD.
- «Beam-walk» с расстояниями « PQ »: начиная с фиксированной начальной точки (медоида), поддерживайте пул кандидатов размером
L. Извлекайте лучший элемент, расширяйте его соседей, оценивайте расстояния, используя только коды in-RAM PQ . Во время прохода не допускается дисковый ввод-вывод. - Переранжируйте финалистов с диска: расстояния до лучших элементов пула кандидатов были приблизительно оценены с помощью PQ. Считайте их полные векторы с диска и пересчитайте точные расстояния, чтобы скорректировать ранжирование.
- Возвращаемость top-K. Общий дисковый ввод-вывод = небольшое количество случайных чтений, обычно менее 20.
Торговля
- Почему это масштабируемо: RAM содержит только сжатые коды. Набор данных из 1 млрд векторов с 32-байтовыми кодами PQ занимает ~32 ГБ RAM — помещается на одной рабочей станции.
- Почему это работает медленнее, чем HNSW: SSD случайные чтения примерно в 100 раз медленнее, чем RAM. Даже при всего лишь ~10 чтениях задержка запроса в основном определяется диском.
- Почему этот метод по-прежнему превосходит метод « IVF_PQ » по показателю «recall»: этап повторного ранжирования устраняет ошибки квантования, которые не могут исправить методы, основанные исключительно на алгоритме « PQ ».
Ментальная модель: « PQ » —это недорогой тест типа «перспективно ли это соседство?». Чтение с диска — это дорогостоящая проверка типа «давайте я действительно это проверю». « DiskANN » выполняет большую часть своей работы с помощью этого недорогого теста.
Что такое « DiskANN »?
DiskANN — это основанный на графе индекс приближённого ближайшего соседа, разработанный для наборов данных, которые не помещаются в RAM. Он строит одноуровневый графVamana , организованный для эффективного доступа к диску, хранит в памяти крошечный код с квантованием по произведению (PQ) для каждого вектора и сохраняет векторы полной точности и ребра графа на SSD. Поиск осуществляется по графу с помощью недорогих сравнений in-RAM PQ и обращается к диску только для переранжирования небольшого числа финалистов.
В « Milvus » технология « DiskANN » обеспечивает работу опции индексации на диске: коллекции размером в миллиарды элементов становятся доступными для поиска на машинах с десятками — а не сотнями — гигабайт оперативной памяти ( RAM), в то время как этап повторного ранжирования на диске позволяет поддерживать показатель «recall» на уровне, близком к показателям графовых индексов в памяти.
Что регулируют ручки
R(степень графа, время сборки): максимальное количество ребер на узел в графе « Vamana ». Более высокое значение R обеспечивает лучшую связность и точность извлечения за счёт увеличения размера графа на диске и замедления сборки.L/search_list(время запроса): пул кандидатов, поддерживаемый во время лучевого поиска — основной регулятор баланса между точностью извлечения и задержкой, эквивалентный параметру ef в HNSW. Его значение должно быть не меньше вашего top-K.- Бюджет повторного ранжирования: количество финалистов, полные векторы которых загружаются из « SSD » для точного подсчёта баллов. Каждая такая операция представляет собой случайное чтение с диска, поэтому именно здесь возникает задержка запроса — а также именно здесь исправляются ошибки аппроксимации, связанные с « PQ ».
DiskANN vs HNSW vs IVF
Выбирайте « DiskANN », когда набор данных (или объем занимаемой памяти) превышает возможности « RAM »: он обслуживает запросы с высокой точностью поиска, используя лишь небольшую часть памяти, в обмен на задержку на уровне миллисекунд, обусловленную чтением из файлов « SSD ». Если всё комфортно помещается в памяти, « HNSW » отвечает быстрее. Если вам требуется быстрое построение индекса или умеренная экономия памяти без использования диска, варианты « IVF » занимают промежуточное положение.
Часто задаваемые вопросы
Когда следует использовать « DiskANN » вместо « HNSW »?
Когда ваши векторы больше не помещаются в « RAM » — или « RAM » для их хранения обходится дороже, чем вы готовы заплатить. Миллиард векторов с плавающей запятой и 768 измерениями требует ~3 ТБ памяти для « HNSW », но всего несколько десятков ГБ для « RAM » плюс « SSD » с « DiskANN ». Если набор данных комфортно помещается в памяти, « HNSW » остается вариантом с меньшей задержкой.
Какое оборудование требуется для работы с « DiskANN »?
Быстрая операция « NVMe » ( SSD ) является ключевым требованием, поскольку задержка запроса в основном обусловлена несколькими случайными операциями чтения с диска (каждая ~100 мкс). Требования к « RAM » ( ) скромны: примерно размер кодов « PQ » ( ) (например, 32–64 байта на вектор) плюс рабочие буферы.
Является ли « DiskANN » более медленным, чем индексы в памяти, такие как « HNSW »?
На один запрос — да, как правило, это низкие однозначные значения в миллисекундах по сравнению с долями миллисекунды для « HNSW » в памяти, поскольку каждое переранжирование с диска происходит примерно в 100 раз медленнее, чем доступ к « RAM ». Компромисс заключается в стоимости: « DiskANN » обрабатывает тот же набор данных с на порядок меньшим количеством операций « RAM », сохраняя при этом recall выше 90–95%.
Как « DiskANN » поддерживает высокий показатель «recall» несмотря на сжатие « PQ »?
PQ Коды используются только для управления прохождением графа, а не для вычисления окончательных оценок. Перед возвратом результатов функция ` DiskANN ` считывает векторы с полной точностью из списка лучших кандидатов из ` SSD ` и точно переранжирует их, исправляя ошибку квантования, которую не могут устранить чистые индексы на основе ` PQ`, такие как ` IVF_PQ `.
Узнайте больше: ознакомьтесь с документацией по «DiskANN » для получения информации о требованиях к настройке или просмотрите раздел «Index Explained» для получения полного руководства по принятию решений.
Продолжайте изучать
Исследование HNSW
Посмотрите, как шаг за шагом происходит поиск по многослойному графу — от «скачков по магистрали» до «локальных прогулок».
FLAT vs IVF
Сравнение методов перебора и кластерного поиска в табличном виде. Настройка параметра « nprobe » в режиме реального времени.
Лаборатория мер сходства
Перетащите точку запроса и переключайтесь между режимами « L2 », «Cosine» и « IP », чтобы увидеть, как меняется понятие «ближайший».