DISKANN

В крупномасштабных сценариях, где наборы данных могут включать миллиарды или даже триллионы векторов, стандартные методы индексирования в памяти (например, HNSW, IVF_FLAT) часто не успевают за скоростью из-за ограничений памяти. DISKANN предлагает дисковый подход, который решает эти проблемы, сохраняя высокую точность и скорость поиска, когда размер набора данных превышает объем доступной оперативной памяти.

Обзор

DISKANN сочетает в себе две ключевые технологии для эффективного векторного поиска:

• Vamana Graph - дисковый индекс на основе графа, который соединяет точки данных (или векторы) для эффективной навигации во время поиска.

• Product Quantization (PQ) - метод сжатия в памяти, который уменьшает размер векторов, позволяя быстро вычислять приблизительное расстояние между векторами.

Построение индексов

Граф Вамана

Граф Vamana занимает центральное место в дисковой стратегии DISKANN. Он может работать с очень большими наборами данных, поскольку ему не нужно полностью размещаться в памяти во время или после построения.

На следующем рисунке показано, как строится граф Vamana.

Diskann

1. Начальные случайные соединения: Каждая точка данных (вектор) представлена в виде узла в графе. Изначально эти узлы соединяются случайным образом, образуя плотную сеть. Обычно узел начинает иметь около 500 ребер (или связей) для обеспечения широкой связности.

2. Уточнение для повышения эффективности: Первоначальный случайный граф подвергается процессу оптимизации, чтобы сделать его более эффективным для поиска. Это включает в себя два ключевых этапа:

   • Обрезка лишних ребер: Алгоритм отбрасывает ненужные связи на основе расстояния между узлами. На этом этапе приоритет отдается более качественным ребрам.

     Параметр max_degree ограничивает максимальное количество ребер на узел. Более высокое значение max_degree приводит к увеличению плотности графа, что потенциально позволяет находить больше релевантных соседей (более высокий уровень запоминания), но также увеличивает объем памяти и время поиска.

   • Добавление стратегических кратчайших путей: Vamana вводит дальние ребра, соединяющие точки данных, которые находятся на большом расстоянии друг от друга в векторном пространстве. Эти ярлыки позволяют быстро перемещаться по графу, минуя промежуточные узлы и значительно ускоряя навигацию.

     Параметр search_list_size определяет широту процесса уточнения графа. Более высокий search_list_size расширяет поиск соседей во время построения и может повысить итоговую точность, но увеличивает время построения индекса.

Чтобы узнать больше о настройке параметров, обратитесь к разделу DISKANN params.

PQ

DISKANN использует PQ для сжатия высокоразмерных векторов в более мелкие представления(PQ-коды), которые хранятся в памяти для быстрого вычисления приблизительного расстояния.

Параметр pq_code_budget_gb_ratio управляет объемом памяти, выделенным для хранения этих PQ-кодов. Он представляет собой соотношение между общим размером векторов (в гигабайтах) и местом, выделенным для хранения PQ-кодов. Вы можете рассчитать фактический бюджет PQ-кодов (в гигабайтах) по этой формуле:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

где:

• vec_field_size_gb общий размер векторов (в гигабайтах).

• pq_code_budget_gb_ratio задаваемый пользователем коэффициент, представляющий собой долю общего объема данных, зарезервированную для PQ-кодов. Этот параметр позволяет найти компромисс между точностью поиска и ресурсами памяти. Дополнительные сведения о настройке параметров см. в разделе Конфигурации DISKANN.

Технические подробности о методе PQ см. в разделе IVF_PQ.

Процесс поиска

После того как индекс (граф Vamana на диске и коды PQ в памяти) построен, DISKANN выполняет поиск ANN следующим образом:

Дисканн 2

1. Запрос и точка входа: Вектор запроса задается для поиска ближайших соседей. DISKANN начинает работу с выбранной точки входа в граф Вамана, часто это узел, расположенный вблизи глобального центроида набора данных. Глобальный центроид представляет собой среднее значение всех векторов, что позволяет минимизировать расстояние обхода графа для поиска нужных соседей.

2. Поиск соседей: Алгоритм собирает потенциальных соседей-кандидатов (круги красного цвета на рисунке) с ребер текущего узла, используя коды PQ в памяти для аппроксимации расстояний между этими кандидатами и вектором запроса. Эти потенциальные соседи-кандидаты - узлы, непосредственно связанные с выбранной точкой входа через ребра в графе Vamana.

3. Выбор узлов для точного расчета расстояния: Из приблизительных результатов выбирается подмножество наиболее перспективных соседей (круги зеленого цвета на рисунке) для точной оценки расстояния по их исходным, несжатым векторам. Это требует считывания данных с диска, что может занять много времени. DISKANN использует два параметра для контроля этого тонкого баланса между точностью и скоростью:

   • beam_width_ratio: Коэффициент, который управляет широтой поиска, определяя, сколько соседей-кандидатов выбирается параллельно для изучения их соседей. Большее значение beam_width_ratio приводит к более широкому поиску, что потенциально ведет к повышению точности, но также увеличивает вычислительные затраты и объем дисковых операций ввода-вывода. Ширина луча, или количество выбранных узлов, определяется по формуле: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: Доля памяти, выделяемая для кэширования часто используемых дисковых данных. Такое кэширование позволяет минимизировать дисковый ввод-вывод и ускорить повторный поиск, поскольку данные уже находятся в памяти.

   Чтобы узнать больше о настройке параметров, обратитесь к разделу Конфигурации DISKANN.

4. Итеративное исследование: Поиск итеративно уточняет набор кандидатов, многократно выполняя приблизительные оценки (используя PQ), а затем точные проверки (используя исходные векторы с диска), пока не будет найдено достаточное количество соседей.

Включение DISKANN в Milvus

По умолчанию DISKANN в Milvus отключен, чтобы отдать предпочтение скорости индексов в памяти для наборов данных, которые удобно размещаются в оперативной памяти. Однако если вы работаете с большими массивами данных или хотите воспользоваться преимуществами масштабируемости DISKANN и оптимизации SSD, вы можете легко включить эту функцию.

Вот как включить DISKANN в Milvus:

1. Обновите файл конфигурации Milvus

   1. Найдите свой файл конфигурации Milvus. (Подробные сведения о поиске этого файла см. в документации Milvus по конфигурации).

   2. Найдите параметр queryNode.enableDisk и установите его значение на true:

       queryNode:
           enableDisk: true # Enables query nodes to load and search using the on-disk index
      

2. Оптимизация хранилища для DISKANN

Чтобы обеспечить наилучшую производительность DISKANN, рекомендуется хранить данные Milvus на быстром NVMe SSD. Вот как это сделать для автономного и кластерного развертывания Milvus:

• Milvus Standalone

  • Смонтируйте каталог данных Milvus на NVMe SSD в контейнере Milvus. Это можно сделать в файле docker-compose.yml или с помощью других инструментов управления контейнером.

  • Например, если ваш NVMe SSD смонтирован по адресу /mnt/nvme, вы должны обновить раздел volumesв файле docker-compose.yml следующим образом:

   volumes:
        - /mnt/nvme/volumes/milvus:/var/lib/milvus
  

• Кластер Milvus

  • Смонтируйте каталог данных Milvus на NVMe SSD в контейнерах QueryNode и IndexNode. Этого можно добиться с помощью настроек оркестровки контейнеров.

  • Монтируя данные на NVMe SSD в обоих типах узлов, вы обеспечиваете высокую скорость чтения и записи для операций поиска и индексирования.

После внесения этих изменений перезапустите экземпляр Milvus, чтобы настройки вступили в силу. Теперь Milvus будет использовать возможности DISKANN для работы с большими наборами данных, обеспечивая эффективный и масштабируемый векторный поиск.

Настройка DISKANN

Параметры, связанные с DISKANN, могут быть настроены только через конфигурационный файл Milvus (milvus.yaml):

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

Для получения подробной информации об описании параметров см. раздел DISKANN params.

Параметры DISKANN

Тонкая настройка параметров DISKANN позволяет адаптировать его поведение к конкретному набору данных и поисковой нагрузке, добиваясь правильного баланса между скоростью, точностью и использованием памяти.

Параметры построения индексов

Эти параметры влияют на то, как строится индекс DISKANN. Их настройка может повлиять на размер индекса, время построения и качество поиска.

	Параметр	Описание	Диапазон значений	Рекомендации по настройке
Vamana	MaxDegree	Управляет максимальным количеством связей (ребер), которые может иметь каждая точка данных в графе Vamana.	Тип: Integer Диапазон: [1, 512] Значение по умолчанию: 56	Более высокие значения создают более плотные графы, что потенциально повышает запоминаемость (поиск более релевантных результатов), но также увеличивает расход памяти и время построения. В большинстве случаев мы рекомендуем устанавливать значение в пределах этого диапазона: [10, 100].
	SearchListSize	При построении индекса этот параметр определяет размер пула кандидатов, используемого при поиске ближайших соседей для каждого узла. Для каждого узла, добавляемого в граф, алгоритм ведет список search_list_size лучших кандидатов, найденных на данный момент. Поиск соседей прекращается, когда этот список больше не может быть улучшен. Из этого пула кандидатов выбираются лучшие max_degree узлов для формирования конечных ребер.	Тип: Integer Диапазон: [1, int_max]. Значение по умолчанию: 100	Большее значение search_list_size увеличивает вероятность нахождения истинных ближайших соседей для каждого узла, что может привести к получению более качественного графа и улучшению эффективности поиска (recall). Однако за это приходится платить значительно большим временем построения индекса. Это значение всегда должно быть больше или равно max_degree.
	SearchCacheBudgetGBRatio	Контролирует объем памяти, выделяемой для кэширования часто используемых частей графа при построении индекса.	Тип: Плавающая величина Диапазон: [0.0, 0.3) Значение по умолчанию: 0.10	При большем значении выделяется больше памяти для кэширования, что значительно сокращает дисковый ввод-вывод, но потребляет больше системной памяти. Меньшее значение использует меньше памяти для кэширования, потенциально увеличивая потребность в обращении к диску. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Регулирует размер PQ-кодов (сжатых представлений точек данных) по сравнению с размером несжатых данных.	Тип: Плавающая величина Диапазон: (0.0, 0.25). Значение по умолчанию: 0.125	Более высокое соотношение приводит к более точным результатам поиска за счет выделения большей доли памяти для PQ-кодов, эффективно сохраняя больше информации об исходных векторах. Однако для этого требуется больше памяти, что ограничивает возможности работы с большими наборами данных. Более низкое соотношение уменьшает расход памяти, но потенциально приводит к снижению точности, так как меньшие PQ-коды сохраняют меньше информации. Этот подход подходит для сценариев, в которых ограничение памяти является проблемой, и потенциально позволяет индексировать большие наборы данных. В большинстве случаев мы рекомендуем устанавливать значение в этом диапазоне: (0.0625, 0.25).

Параметры поиска, специфичные для индекса

Эти параметры влияют на то, как DISKANN выполняет поиск. Их настройка может повлиять на скорость поиска, задержку и использование ресурсов.

	Параметр	Описание	Диапазон значений	Предложение по настройке
Vamana	BeamWidthRatio	Управляет степенью параллелизма при поиске, определяя максимальное количество параллельных запросов ввода-вывода с диска относительно количества доступных ядер процессора.	Тип: Float Диапазон: [1, max(128 / количество CPU, 16)]. Значение по умолчанию: 4.0	Более высокие значения увеличивают параллелизм, что может ускорить поиск в системах с мощными процессорами и SSD. Однако слишком высокое значение может привести к чрезмерной нагрузке на ресурсы. В большинстве случаев мы рекомендуем устанавливать значение в пределах этого диапазона: [1.0, 4.0].
	search_list	Во время поиска этот параметр определяет размер пула кандидатов, который алгоритм поддерживает при обходе графа. Большее значение увеличивает шансы найти истинных ближайших соседей (более высокий отзыв), но также увеличивает задержку поиска.	Тип: Integer Диапазон: [1, int_max]. Значение по умолчанию: 100	Для достижения хорошего баланса между производительностью и точностью рекомендуется установить это значение равным или немного большим, чем количество результатов, которые вы хотите получить (top_k).