Как работает DiskANN и когда он нужен?

Краткий тезис

DiskANN — это алгоритм приближённого поиска ближайших соседей (ANN), оптимизированный для хранения векторов на SSD (твёрдотельном накопителе) вместо оперативной памяти. Он строит графовую структуру Vamana, где вершины — векторы, а рёбра — связи между близкими соседями. Индексы (граф) хранятся в RAM, а сами векторы — на диске, что позволяет обрабатывать коллекции до миллиардов векторов при ограниченной памяти. DiskANN необходим, когда размер векторной базы данных превышает доступную RAM, а требования к точности поиска выше, чем к скорости.

1. Термин: ANN (Approximate Nearest Neighbor)

ANN — это класс алгоритмов, которые находят не точных, а «достаточно близких» соседей для заданного вектора-запроса. В отличие от точного k-NN (k ближайших соседей), ANN жертвует гарантированной полнотой ради скорости и/или экономии памяти. Основные семейства ANN: на основе деревьев (KD-дерево, VP-дерево), хеширования (LSH), квантования (IVF, PQ) и графов (HNSW, Vamana).

DiskANN относится к графовым методам и специально спроектирован для работы с данными, которые не помещаются в RAM.

2. Проблема: векторов больше, чем RAM

Современные RAG-системы и поисковые сервисы оперируют сотнями миллионов или миллиардами эмбеддингов. Каждый вектор (например, размерностью 768 или 1024) занимает несколько килобайт. Для 1 миллиарда векторов размерность 768 потребуется около 3 ТБ памяти (1e9 * 768 * 4 байта ≈ 3 ТБ). Даже сжатие (PQ) не всегда укладывается в RAM сервера.

Традиционные ANN-индексы (HNSW, IVF) хранят и векторы, и граф в RAM. Когда данные не влезают, приходится либо покупать дорогую память, либо жертвовать точностью/скоростью. DiskANN решает эту проблему, перемещая векторы на SSD, а в памяти оставляя только компактный граф.

3. Архитектура DiskANN

DiskANN использует три ключевые идеи:

3.1 Граф Vamana

Vamana — это направленный граф, где каждый узел (вектор) соединён с несколькими ближайшими соседями. Построение происходит итеративно: для каждого вектора выполняется поиск в текущем графе, и найденные соседи добавляются как рёбра. Параметр R (максимальная степень вершины) и L (размер списка кандидатов при поиске) контролируют компромисс между точностью и памятью. Vamana специально спроектирован для эффективного поиска на SSD: он минимизирует количество случайных чтений с диска.

3.2 Хранение векторов на SSD

Сами векторы хранятся в сжатом виде (обычно PQ — Product Quantization) на SSD. При поиске DiskANN считывает с диска только те векторы, которые оказались в кандидатах на финальном этапе. Это резко снижает потребление RAM: граф (индекс) занимает примерно 10–20% от размера исходных данных, а векторы — 0% RAM.

3.3 Индекс в памяти

Граф Vamana (списки смежности) и метаданные (смещения на диске) хранятся в RAM. Размер графа: для 1 миллиарда векторов со степенью R=64 потребуется около 1 млрд * 64 * 4 байта ≈ 256 ГБ — это всё ещё много, но в 10 раз меньше, чем хранить сами векторы. DiskANN позволяет дополнительно сжимать граф (например, обрезать рёбра).

4. Алгоритм поиска в DiskANN

Поиск выполняется в два этапа:

1. Жадный обход графа в RAM (без чтения векторов). Начиная со случайной точки, алгоритм переходит к соседям, которые ближе к запросу по расстоянию (обычно L2 или косинус). Для вычисления расстояния используются квантованные коды (PQ), которые хранятся в RAM вместе с графом. Это даёт приблизительную оценку, но не точное расстояние.

2. Уточнение кандидатов с SSD. После того как в RAM собран список top-k кандидатов (например, 100), DiskANN считывает с SSD полные векторы для этих кандидатов и пересчитывает точное расстояние. Финальный список top-k формируется уже по точным расстояниям.

Псевдокод поиска (упрощённо):

def diskann_search(query, index, k, beam_width):
    # 1. Инициализация: случайная точка
    candidate = index.random_start()
    visited = set()
    candidates = [(distance_pq(query, candidate), candidate)]
    
    # 2. Жадный поиск в графе (только PQ-расстояния)
    while candidates:
        dist, node = heapq.heappop(candidates)
        if node in visited:
            continue
        visited.add(node)
        for neighbor in index.graph[node]:
            if neighbor not in visited:
                d = distance_pq(query, neighbor)
                heapq.heappush(candidates, (d, neighbor))
        # Ограничение размера кучи
        if len(candidates) > beam_width:
            candidates = heapq.nsmallest(beam_width, candidates)
    
    # 3. Уточнение: читаем полные векторы с SSD
    full_candidates = []
    for node in visited[:beam_width]:
        full_vec = index.read_vector_from_ssd(node)
        full_candidates.append((distance_full(query, full_vec), node))
    full_candidates.sort()
    
    return [node for _, node in full_candidates[:k]]

5. Сравнение DiskANN с другими ANN-методами

Вывод DiskANN жертвует скоростью (из-за чтения с SSD) и простотой построения, но позволяет работать с коллекциями, которые не влезают в RAM, сохраняя высокую точность.

6. Когда нужен DiskANN?

DiskANN оправдан в следующих сценариях:

• Размер векторной базы > 100 млн (особенно > 1 млрд). Если данные умещаются в RAM, HNSW или IVF+PQ будут быстрее и проще.
• Точность важнее скорости. DiskANN даёт recall@10 > 0.95 при правильной настройке, что близко к HNSW, но медленнее в 2–5 раз.
• Ограниченный бюджет на RAM. Например, сервер с 64 ГБ RAM, а векторов на 1 ТБ. DiskANN позволит обслуживать такой объём без покупки дорогой памяти.
• Холодные данные (редко запрашиваемые). Если часть векторов редко ищется, SSD-хранение дешевле, чем держать всё в RAM.
• RAG-системы с миллиардами чанков. Крупные поисковые движки (Bing, Google) используют подобные подходы для индексации веб-страниц.

Когда не нужен

• Меньше 10 млн векторов — проще и быстрее использовать HNSW в RAM.
• Требуется latency < 1 мс — DiskANN не подойдёт из-за SSD-задержек.
• Частые инкрементальные обновления — DiskANN требует периодического перестроения индекса.

7. Ограничения и компромиссы

• Скорость поиска зависит от пропускной способности SSD (NVMe предпочтительнее SATA). При большом количестве конкурентных запросов может возникнуть IO-бутылочное горлышко.
• Построение индекса требует однократного прохода по всем данным и сортировки на диске. Для миллиарда векторов это может занять несколько часов.
• Точность зависит от качества квантования (PQ). Слишком агрессивное сжатие снижает recall.
• Не поддерживает произвольные метрики расстояния «из коробки» — только L2 и косинус (через нормализацию).
• Обновления (добавление новых векторов) возможны только пакетно: нужно перестроить индекс или использовать гибридные схемы (например, DiskANN + fresh RAM-индекс).

8. Интеграция с RAG-системами

В RAG-пайплайне DiskANN может использоваться как векторное хранилище для retrieval. Типичная архитектура:

1. Индексация: документы разбиваются на чанки, эмбеддинги вычисляются (например, OpenAI ada-002) и загружаются в DiskANN.
2. Поиск: при запросе пользователя эмбеддинг запроса подаётся в DiskANN, который возвращает top-k чанков.
3. Генерация: найденные чанки подаются в LLM для формирования ответа.

Пример использования библиотеки diskannpy (Python):

import diskannpy as dap
import numpy as np

# Создание индекса из numpy-массива (100 млн векторов размерности 768)
vectors = np.random.random((100_000_000, 768)).astype(np.float32)
dap.build_memory_index(
    data=vectors,
    distance_metric="l2",
    index_path="diskann_index",
    graph_degree=64,
    search_list_size=128,
    num_threads=32,
)

# Поиск
query = np.random.random((1, 768)).astype(np.float32)
indices, distances = dap.search(
    query=query,
    index_path="diskann_index",
    k=10,
    search_list_size=128,
    beam_width=4,
)

Для production-развёртывания часто используют SPTAG (Microsoft) или FAISS с поддержкой SSD (экспериментально). DiskANN также доступен в Azure Cognitive Search как один из алгоритмов.

9. Пет-проект для закрепления

Задача Сравнить производительность DiskANN и HNSW на синтетическом датасете из 10 млн векторов (размерность 128) при ограничении RAM в 2 ГБ.

Инструменты

• Python, numpy, diskannpy, faiss (для HNSW), psutil (мониторинг памяти).
• Датасет: sklearn.datasets.make_blobs или случайные векторы.

Шаги:

1. Сгенерировать 10 млн векторов размерностью 128 (float32). Размер в RAM: 10e6 * 128 * 4 ≈ 5.1 ГБ — больше лимита.
2. Построить индекс HNSW в FAISS с ограничением памяти (использовать faiss.IndexHNSWFlat). Замерить время построения и потребление RAM.
3. Построить индекс DiskANN с помощью diskannpy.build_memory_index (он будет хранить векторы на SSD, а граф в RAM). Замерить время и RAM.
4. Выполнить 1000 случайных запросов, замерить среднее время поиска и recall@10 (сравнивая с точным поиском через faiss.IndexFlatL2 на подвыборке).
5. Построить таблицу результатов.

Ожидаемый результат

• HNSW не сможет построиться из-за нехватки RAM (или будет использовать своп, что приведёт к падению скорости).
• DiskANN построится успешно, потребляя ~1–1.5 ГБ RAM (граф + метаданные).
• Время поиска DiskANN будет в 2–5 раз больше, чем HNSW на данных, помещающихся в RAM, но recall будет сопоставим (0.95+).

10. Связь с другими вопросами

11. Навигация

• Предыдущий: 227
• Следующий: 229
• Индекс: 00. Индекс разборов

Навигация

• Предыдущий: 227
• Следующий: 229
• Индекс: 00. Индекс разборов