DISKANN

Em cenários de grande escala, onde os conjuntos de dados podem incluir biliões ou mesmo triliões de vectores, os métodos padrão de indexação na memória (por exemplo, HNSW, IVF_FLAT) muitas vezes não conseguem acompanhar o ritmo devido a limitações de memória. O DISKANN oferece uma abordagem baseada em disco que aborda esses desafios, mantendo alta precisão e velocidade de pesquisa quando o tamanho do conjunto de dados excede a RAM disponível.

Visão geral

O DISKANN combina duas técnicas fundamentais para uma pesquisa vetorial eficiente:

• Gráfico Vamana - Um índice baseado em disco e em gráficos que liga pontos de dados (ou vectores) para uma navegação eficiente durante a pesquisa.

• Quantização de produtos (PQ) - Um método de compressão na memória que reduz o tamanho dos vectores, permitindo cálculos rápidos de distância aproximada entre vectores.

Construção de índices

Gráfico Vamana

O gráfico Vamana é fundamental para a estratégia baseada em disco da DISKANN. Pode lidar com conjuntos de dados muito grandes porque não precisa de residir totalmente na memória durante ou após a construção.

A figura seguinte mostra como é construído um gráfico Vamana.

Diskann

1. Ligações aleatórias iniciais: Cada ponto de dados (vetor) é representado como um nó no grafo. Estes nós são inicialmente ligados de forma aleatória, formando uma rede densa. Normalmente, um nó começa com cerca de 500 arestas (ou ligações) para uma conetividade alargada.

2. Refinamento para eficiência: O grafo aleatório inicial é submetido a um processo de otimização para o tornar mais eficiente para a pesquisa. Isso envolve duas etapas principais:

   • Poda de arestas redundantes: O algoritmo elimina ligações desnecessárias com base nas distâncias entre nós. Este passo dá prioridade a arestas de maior qualidade.

     O parâmetro max_degree restringe o número máximo de arestas por nó. Um max_degree mais elevado resulta num gráfico mais denso, podendo encontrar vizinhos mais relevantes (maior recordação), mas também aumenta a utilização da memória e o tempo de pesquisa.

   • Adicionar atalhos estratégicos: O Vamana introduz arestas de longo alcance, ligando pontos de dados que estão muito afastados no espaço vetorial. Estes atalhos permitem que as pesquisas saltem rapidamente através do gráfico, contornando nós intermédios e acelerando significativamente a navegação.

     O parâmetro search_list_size determina a amplitude do processo de refinamento do gráfico. Um search_list_size mais elevado alarga a pesquisa de vizinhos durante a construção e pode melhorar a precisão final, mas aumenta o tempo de construção do índice.

Para saber mais sobre a afinação de parâmetros, consulte Parâmetros DISKANN.

PQ

DISKANN utiliza PQ para comprimir vectores de alta dimensão em representações mais pequenas(códigos PQ), que são armazenadas na memória para cálculos rápidos de distância aproximada.

O parâmetro pq_code_budget_gb_ratio gere o espaço de memória dedicado ao armazenamento destes códigos PQ. Representa um rácio entre o tamanho total dos vectores (em gigabytes) e o espaço atribuído para armazenar os códigos PQ. Pode calcular o orçamento real do código PQ (em gigabytes) com esta fórmula:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

onde:

• vec_field_size_gb é o tamanho total dos vectores (em gigabytes).

• pq_code_budget_gb_ratio é um rácio definido pelo utilizador, que representa a fração do tamanho total dos dados reservada para os códigos PQ. Este parâmetro permite um compromisso entre a precisão da pesquisa e os recursos de memória. Para obter mais informações sobre o ajuste de parâmetros, consulte Configurações do DISKANN.

Para obter pormenores técnicos sobre o método PQ subjacente, consulte IVF_PQ.

Processo de pesquisa

Uma vez construído o índice (o gráfico Vamana no disco e os códigos PQ na memória), o DISKANN efectua pesquisas ANN da seguinte forma:

Diskann 2

1. Consulta e ponto de entrada: É fornecido um vetor de consulta para localizar os seus vizinhos mais próximos. O DISKANN começa a partir de um ponto de entrada selecionado no gráfico Vamana, frequentemente um nó próximo do centróide global do conjunto de dados. O centróide global representa a média de todos os vectores, o que ajuda a minimizar a distância de deslocação através do grafo para encontrar os vizinhos desejados.

2. Exploração de vizinhança: O algoritmo reúne potenciais candidatos a vizinhos (círculos a vermelho na figura) a partir das arestas do nó atual, utilizando códigos PQ na memória para aproximar as distâncias entre estes candidatos e o vetor de consulta. Estes potenciais candidatos a vizinhos são os nós diretamente ligados ao ponto de entrada selecionado através de arestas no gráfico Vamana.

3. Seleção de nós para o cálculo exato da distância: A partir dos resultados aproximados, um subconjunto dos vizinhos mais promissores (círculos a verde na figura) é selecionado para avaliações precisas da distância utilizando os seus vectores originais não comprimidos. Isto requer a leitura de dados do disco, o que pode ser demorado. O DISKANN utiliza dois parâmetros para controlar este delicado equilíbrio entre precisão e velocidade:

   • beam_width_ratio: Uma ração que controla a amplitude da pesquisa, determinando quantos vizinhos candidatos são selecionados em paralelo para explorar os seus vizinhos. Um beam_width_ratio maior resulta numa exploração mais ampla, potencialmente conduzindo a uma maior precisão, mas também aumentando o custo computacional e a E/S do disco. A largura do feixe, ou o número de nós selecionados, é determinada utilizando a fórmula: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: A proporção de memória atribuída para armazenar em cache os dados do disco frequentemente acedidos. Este armazenamento em cache ajuda a minimizar a E/S do disco, tornando as pesquisas repetidas mais rápidas, uma vez que os dados já estão na memória.

   Para saber mais sobre a afinação de parâmetros, consulte Configurações do DISKANN.

4. Exploração iterativa: A pesquisa refina iterativamente o conjunto de candidatos, efectuando repetidamente avaliações aproximadas (utilizando PQ) seguidas de verificações precisas (utilizando vectores originais do disco) até ser encontrado um número suficiente de vizinhos.

Ativar DISKANN em Milvus

Por padrão, DISKANN é desativado no Milvus para priorizar a velocidade dos índices na memória para conjuntos de dados que cabem confortavelmente na RAM. No entanto, se estiver a trabalhar com conjuntos de dados maciços ou quiser tirar partido da escalabilidade do DISKANN e da otimização de SSD, pode activá-lo facilmente.

Veja como habilitar o DISKANN no Milvus:

1. Atualizar o arquivo de configuração do Milvus

   1. Localize o arquivo de configuração do Milvus. (Consulte a documentação do Milvus em Configuration para obter detalhes sobre como encontrar esse arquivo).

   2. Encontre o parâmetro queryNode.enableDisk e defina seu valor para true:

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

2. Otimizar o armazenamento para DISKANN

Para garantir o melhor desempenho com o DISKANN, é recomendável armazenar os dados do Milvus num SSD NVMe rápido. Veja como fazer isso para implantações do Milvus Standalone e do Cluster:

• Milvus Standalone

  • Monte o diretório de dados do Milvus em um SSD NVMe dentro do contêiner do Milvus. Isso pode ser feito no arquivo docker-compose.yml ou usando outras ferramentas de gerenciamento de contêineres.

  • Por exemplo, se o seu SSD NVMe estiver montado em /mnt/nvme, atualize a secção volumesdo seu docker-compose.yml da seguinte forma:

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

• Cluster Milvus

  • Monte o diretório de dados do Milvus em um SSD NVMe nos contêineres QueryNode e IndexNode. Isso pode ser feito por meio da configuração da orquestração de contêineres.

  • Ao montar os dados em um SSD NVMe em ambos os tipos de nó, você garante velocidades rápidas de leitura e gravação para operações de pesquisa e indexação.

Depois de fazer essas alterações, reinicie a instância do Milvus para que as configurações tenham efeito. Agora, o Milvus aproveitará os recursos do DISKANN para lidar com grandes conjuntos de dados, fornecendo pesquisa vetorial eficiente e escalonável.

Configurar DISKANN

Os parâmetros relacionados com DISKANN só podem ser configurados através do seu ficheiro de configuração do 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

Para obter detalhes sobre as descrições dos parâmetros, consulte Parâmetros DISKANN.

Parâmetros DISKANN

O ajuste fino dos parâmetros do DISKANN permite-lhe adaptar o seu comportamento ao seu conjunto de dados específico e à carga de trabalho de pesquisa, atingindo o equilíbrio correto entre velocidade, precisão e utilização de memória.

Parâmetros de criação de índices

Estes parâmetros influenciam a forma como o índice DISKANN é construído. Ajustá-los pode afetar o tamanho do índice, o tempo de construção e a qualidade da pesquisa.

	Parâmetro	Descrição	Valor Intervalo	Sugestão de ajuste
Vamana	MaxDegree	Controla o número máximo de conexões (bordas) que cada ponto de dados pode ter no gráfico Vamana.	Tipo: Integer Intervalo: [1, 512] Valor padrão: 56	Valores mais altos criam gráficos mais densos, potencialmente aumentando a recuperação (encontrando resultados mais relevantes), mas também aumentando o uso de memória e o tempo de construção. Na maioria dos casos, recomendamos que você defina um valor dentro deste intervalo: [10, 100].
	SearchListSize	Durante a construção do índice, este parâmetro define o tamanho do conjunto de candidatos usado na pesquisa dos vizinhos mais próximos de cada nó. Para cada nó que está sendo adicionado ao gráfico, o algoritmo mantém uma lista dos search_list_size melhores candidatos encontrados até o momento. A procura de vizinhos pára quando esta lista já não pode ser melhorada. A partir deste conjunto final de candidatos, os max_degree melhores nós são selecionados para formar as arestas finais.	Tipo: Integer Range: [1, int_max] Valor predefinido: 100	Um search_list_size maior aumenta a probabilidade de encontrar os verdadeiros vizinhos mais próximos de cada nó, o que pode levar a um gráfico de maior qualidade e a um melhor desempenho de pesquisa (recuperação). No entanto, isto tem o custo de um tempo de construção do índice significativamente mais longo. Deve ser sempre definido para um valor maior ou igual a max_degree.
	SearchCacheBudgetGBRatio	Controla a quantidade de memória alocada para armazenar em cache as partes frequentemente acedidas do gráfico durante a construção do índice.	Tipo: Float Intervalo: [0.0, 0.3) Valor padrão: 0.10	Um valor mais alto aloca mais memória para o cache, reduzindo significativamente a E/S do disco, mas consumindo mais memória do sistema. Um valor mais baixo utiliza menos memória para armazenamento em cache, aumentando potencialmente a necessidade de acesso ao disco. Na maioria dos casos, recomendamos que defina um valor dentro deste intervalo: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Controla o tamanho dos códigos PQ (representações comprimidas de pontos de dados) em comparação com o tamanho dos dados não comprimidos.	Tipo: Float Intervalo: (0,0, 0,25) Valor predefinido: 0.125	Um rácio mais elevado conduz a resultados de pesquisa mais precisos ao atribuir uma maior proporção de memória para códigos PQ, armazenando efetivamente mais informações sobre os vectores originais. Um rácio mais baixo reduz a utilização de memória mas sacrifica potencialmente a precisão, uma vez que os códigos PQ mais pequenos retêm menos informação. Esta abordagem é adequada para cenários em que as restrições de memória são uma preocupação, permitindo potencialmente a indexação de conjuntos de dados maiores. Na maioria dos casos, recomendamos que defina um valor dentro deste intervalo: (0,0625, 0,25]

Parâmetros de pesquisa específicos do índice

Estes parâmetros influenciam a forma como o DISKANN efectua as pesquisas. Ajustá-los pode afetar a velocidade da pesquisa, a latência e o uso de recursos.

	Parâmetro	Descrição do parâmetro	Intervalo de valores	Sugestão de ajuste
Vamana	BeamWidthRatio	Controla o grau de paralelismo durante a pesquisa, determinando o número máximo de solicitações de E/S de disco paralelas em relação ao número de núcleos de CPU disponíveis.	Tipo: Float Intervalo: [1, max(128 / número da CPU, 16)] Valor padrão: 4.0	Valores mais altos aumentam o paralelismo, o que pode acelerar a pesquisa em sistemas com CPUs e SSDs potentes. Na maioria dos casos, recomendamos que você defina um valor dentro deste intervalo: [1.0, 4.0].
	search_list	Durante uma operação de pesquisa, esse parâmetro determina o tamanho do pool de candidatos que o algoritmo mantém à medida que percorre o gráfico. Um valor maior aumenta as hipóteses de encontrar os verdadeiros vizinhos mais próximos (maior recuperação), mas também aumenta a latência da pesquisa.	Tipo: Integer Intervalo: [1, int_max] Valor predefinido: 100	Para obter um bom equilíbrio entre desempenho e exatidão, recomenda-se que este valor seja igual ou ligeiramente superior ao número de resultados que pretende obter (top_k).