DISKANN

En escenarios a gran escala, donde los conjuntos de datos pueden incluir miles de millones o incluso billones de vectores, los métodos estándar de indexación en memoria (por ejemplo, HNSW, IVF_FLAT) a menudo no consiguen mantener el ritmo debido a las limitaciones de memoria. DISKANN ofrece un enfoque basado en disco que aborda estos retos manteniendo una alta precisión y velocidad de búsqueda cuando el tamaño del conjunto de datos supera la memoria RAM disponible.

Visión general

DISKANN combina dos técnicas clave para una búsqueda vectorial eficiente:

• Vamana Graph - Un índice basado en disco y en gráficos que conecta puntos de datos (o vectores) para una navegación eficiente durante la búsqueda.

• Cuantización de productos (PQ): método de compresión en memoria que reduce el tamaño de los vectores y permite calcular rápidamente distancias aproximadas entre vectores.

Construcción de índices

Gráfico Vamana

El grafo Vamana es fundamental en la estrategia basada en disco de DISKANN. Puede manejar conjuntos de datos muy grandes porque no necesita residir completamente en memoria durante o después de su construcción.

La siguiente figura muestra cómo se construye un grafo Vamana.

Diskann

1. Conexiones aleatorias iniciales: Cada punto de datos (vector) se representa como un nodo en el grafo. Estos nodos se conectan inicialmente de forma aleatoria, formando una red densa. Normalmente, un nodo comienza con unas 500 aristas (o conexiones) para una conectividad amplia.

2. Perfeccionamiento para aumentar la eficiencia: El grafo aleatorio inicial se somete a un proceso de optimización para hacerlo más eficiente para la búsqueda. Esto implica dos pasos clave:

   • Poda de aristas redundantes: El algoritmo descarta las conexiones innecesarias basándose en las distancias entre nodos. Este paso da prioridad a las aristas de mayor calidad.

     El parámetro max_degree restringe el número máximo de aristas por nodo. A mayor max_degree, el gráfico es más denso, lo que permite encontrar más vecinos relevantes (mayor recuperación), pero también aumenta el uso de memoria y el tiempo de búsqueda.

   • Añadir atajos estratégicos: Vamana introduce aristas de largo alcance que conectan puntos de datos alejados en el espacio vectorial. Estos atajos permiten que las búsquedas salten rápidamente a través del grafo, evitando los nodos intermedios y acelerando significativamente la navegación.

     El parámetro search_list_size determina la amplitud del proceso de refinamiento del grafo. Un valor más alto de search_list_size amplía la búsqueda de vecinos durante la construcción y puede mejorar la precisión final, pero aumenta el tiempo de construcción del índice.

Para obtener más información sobre el ajuste de parámetros, consulte Parámetros de DISKANN.

PQ

DISKANN utiliza PQ para comprimir vectores de alta dimensión en representaciones más pequeñas(códigos PQ), que se almacenan en memoria para cálculos rápidos de distancias aproximadas.

El parámetro pq_code_budget_gb_ratio gestiona el espacio de memoria dedicado a almacenar estos códigos PQ. Representa una relación entre el tamaño total de los vectores (en gigabytes) y el espacio asignado para almacenar los códigos PQ. Puede calcular el presupuesto real de códigos PQ (en gigabytes) con esta fórmula:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

donde

• vec_field_size_gb es el tamaño total de los vectores (en gigabytes).

• pq_code_budget_gb_ratio es una proporción definida por el usuario, que representa la fracción del tamaño total de los datos reservada para los códigos PQ. Este parámetro permite un equilibrio entre la precisión de la búsqueda y los recursos de memoria. Para más información sobre el ajuste de parámetros, consulte DISKANN configs.

Para más detalles técnicos sobre el método PQ subyacente, consulte IVF_PQ.

Proceso de búsqueda

Una vez construido el índice (el gráfico Vamana en disco y los códigos PQ en memoria), DISKANN realiza las búsquedas RNA de la siguiente manera:

Diskann 2

1. Consulta y punto de entrada: Se proporciona un vector de consulta para localizar a sus vecinos más cercanos. DISKANN parte de un punto de entrada seleccionado en el gráfico Vamana, a menudo un nodo cercano al centroide global del conjunto de datos. El centroide global representa la media de todos los vectores, lo que ayuda a minimizar la distancia transversal a través del grafo para encontrar los vecinos deseados.

2. Exploración de vecinos: El algoritmo reúne posibles vecinos candidatos (círculos en rojo en la figura) a partir de los bordes del nodo actual, aprovechando los códigos PQ en memoria para aproximar las distancias entre estos candidatos y el vector de consulta. Estos posibles vecinos candidatos son los nodos conectados directamente al punto de entrada seleccionado a través de aristas en el grafo Vamana.

3. Selección de nodos para el cálculo preciso de la distancia: A partir de los resultados aproximados, se selecciona un subconjunto de los vecinos más prometedores (círculos en verde en la figura) para realizar evaluaciones precisas de la distancia utilizando sus vectores originales sin comprimir. Para ello es necesario leer los datos del disco, lo que puede llevar mucho tiempo. DISKANN utiliza dos parámetros para controlar este delicado equilibrio entre precisión y velocidad:

   • beam_width_ratio: Un coeficiente que controla la amplitud de la búsqueda, determinando cuántos vecinos candidatos se seleccionan en paralelo para explorar sus vecinos. A mayor beam_width_ratio, la exploración es más amplia, lo que puede aumentar la precisión, pero también el coste computacional y la E/S del disco. La amplitud del haz, o el número de nodos seleccionados, se determina mediante la fórmula: Beam width = Number of CPU cores * beam_width_ratio.

   • search_cache_budget_gb_ratio: La proporción de memoria asignada para almacenar en caché los datos del disco a los que se accede con frecuencia. Este almacenamiento en caché ayuda a minimizar la E/S de disco, haciendo que las búsquedas repetidas sean más rápidas puesto que los datos ya están en memoria.

   Para saber más sobre el ajuste de parámetros, consulte DISKANN configs.

4. Exploración iterativa: La búsqueda refina iterativamente el conjunto de candidatos, realizando repetidamente evaluaciones aproximadas (utilizando PQ) seguidas de comprobaciones precisas (utilizando vectores originales del disco) hasta que se encuentra un número suficiente de vecinos.

Activar DISKANN en Milvus

Por defecto, DISKANN está desactivado en Milvus para dar prioridad a la velocidad de los índices en memoria para conjuntos de datos que caben cómodamente en RAM. Sin embargo, si está trabajando con conjuntos de datos masivos o desea aprovechar la escalabilidad de DISKANN y la optimización SSD, puede habilitarlo fácilmente.

He aquí cómo activar DISKANN en Milvus:

1. Actualice el archivo de configuración de Milvus

   1. Localice su archivo de configuración de Milvus. (Consulte la documentación de Milvus sobre Configuración para más detalles sobre cómo encontrar este archivo).

   2. Busque el parámetro queryNode.enableDisk y establezca su valor en true:

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

2. Optimizar el almacenamiento para DISKANN

Para asegurar el mejor rendimiento con DISKANN, se recomienda almacenar sus datos de Milvus en un SSD NVMe rápido. A continuación se explica cómo hacerlo para las implementaciones de Milvus Standalone y Cluster:

• Milvus Independiente

  • Monte el directorio de datos Milvus en un SSD NVMe dentro del contenedor Milvus. Puede hacerlo en el archivo docker-compose.yml o utilizando otras herramientas de gestión de contenedores.

  • Por ejemplo, si su SSD NVMe está montado en /mnt/nvme, debería actualizar la sección volumesde su docker-compose.yml de la siguiente manera:

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

• Cluster Milvus

  • Monte el directorio de datos Milvus en un SSD NVMe en los contenedores QueryNode e IndexNode. Puede lograr esto a través de su configuración de orquestación de contenedores.

  • Al montar los datos en un SSD NVMe en ambos tipos de nodo, se garantiza una velocidad rápida de lectura y escritura para las operaciones de búsqueda e indexación.

Una vez realizados estos cambios, reinicie su instancia de Milvus para que la configuración surta efecto. Ahora, Milvus aprovechará las capacidades de DISKANN para manejar grandes conjuntos de datos, ofreciendo una búsqueda vectorial eficiente y escalable.

Configurar DISKANN

Los parámetros relacionados con DISKANN sólo pueden configurarse a través de su archivo de configuración de 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 más detalles sobre las descripciones de los parámetros, consulte Parámetros de DISKANN.

Parámetros de DISKANN

El ajuste fino de los parámetros de DISKANN le permite adaptar su comportamiento a su conjunto de datos específico y a la carga de trabajo de búsqueda, logrando el equilibrio adecuado entre velocidad, precisión y uso de memoria.

Parámetros de creación de índices

Estos parámetros influyen en el modo en que se construye el índice DISKANN. Su ajuste puede afectar al tamaño del índice, al tiempo de construcción y a la calidad de la búsqueda.

	Parámetro	Descripción	Rango de valores	Sugerencia de ajuste
Vamana	MaxDegree	Controla el número máximo de conexiones (aristas) que puede tener cada punto de datos en el gráfico Vamana.	Tipo: Entero Rango: [1, 512] Valor por defecto: 56	Los valores más altos crean gráficos más densos, aumentando potencialmente la recuperación (encontrando resultados más relevantes) pero también incrementando el uso de memoria y el tiempo de construcción. En la mayoría de los casos, se recomienda establecer un valor dentro de este rango: [10, 100].
	SearchListSize	Durante la construcción del índice, este parámetro define el tamaño del grupo de candidatos utilizado cuando se buscan los vecinos más cercanos para cada nodo. Para cada nodo que se añade al grafo, el algoritmo mantiene una lista de los search_list_size mejores candidatos encontrados hasta el momento. La búsqueda de vecinos se detiene cuando esta lista ya no puede mejorarse. De esta lista final de candidatos, se seleccionan los mejores max_degree nodos para formar las aristas finales.	Tipo: Entero Rango: [1, int_max] Valor por defecto: 100	Un valor mayor de search_list_size aumenta la probabilidad de encontrar los verdaderos vecinos más cercanos de cada nodo, lo que puede dar lugar a un gráfico de mayor calidad y un mejor rendimiento de la búsqueda (recall). Sin embargo, esto tiene el coste de un tiempo de construcción del índice significativamente mayor. Debe fijarse siempre en un valor mayor o igual que max_degree.
	SearchCacheBudgetGBRatio	Controla la cantidad de memoria asignada para almacenar en caché las partes del gráfico a las que se accede con más frecuencia durante la construcción del índice.	Tipo: Float Rango: [0.0, 0.3) Valor por defecto: 0.10	Un valor más alto asigna más memoria a la caché, reduciendo significativamente la E/S de disco pero consumiendo más memoria del sistema. Un valor más bajo utiliza menos memoria para el almacenamiento en caché, aumentando potencialmente la necesidad de acceso al disco. En la mayoría de los casos, se recomienda establecer un valor dentro de este rango: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	Controla el tamaño de los códigos PQ (representaciones comprimidas de los puntos de datos) en comparación con el tamaño de los datos sin comprimir.	Tipo: Flotante Rango: (0.0, 0.25] Valor por defecto: 0.125	Una proporción más alta conduce a resultados de búsqueda más precisos al asignar una mayor proporción de memoria para los códigos PQ, almacenando efectivamente más información sobre los vectores originales. Sin embargo, esto requiere más memoria, lo que limita la capacidad para manejar grandes conjuntos de datos. Una proporción menor reduce el uso de memoria pero potencialmente sacrifica la precisión, ya que los códigos PQ más pequeños retienen menos información. Este enfoque es adecuado para situaciones en las que las limitaciones de memoria son un problema, ya que puede permitir la indexación de grandes conjuntos de datos. En la mayoría de los casos, se recomienda establecer un valor dentro de este intervalo: (0,0625, 0,25].

Parámetros de búsqueda específicos del índice

Estos parámetros influyen en el modo en que DISKANN realiza las búsquedas. Su ajuste puede influir en la velocidad de búsqueda, la latencia y el uso de recursos.

	Parámetro	Descripción	Rango de valores	Sugerencia de ajuste
Vamana	BeamWidthRatio	Controla el grado de paralelismo durante la búsqueda determinando el número máximo de peticiones de E/S de disco paralelas en relación con el número de núcleos de CPU disponibles.	Tipo: Float Rango: [1, max(128 / número de CPU, 16)] Valor por defecto: 4.0	Los valores más altos aumentan el paralelismo, lo que puede acelerar la búsqueda en sistemas con CPUs y SSDs potentes. En la mayoría de los casos, se recomienda establecer un valor dentro de este rango: [1.0, 4.0].
	search_list	Durante una operación de búsqueda, este parámetro determina el tamaño de la reserva de candidatos que el algoritmo mantiene mientras recorre el gráfico. Un valor mayor aumenta las posibilidades de encontrar a los verdaderos vecinos más cercanos (mayor recall), pero también aumenta la latencia de la búsqueda.	Tipo: Entero Rango: [1, int_max] Valor por defecto: 100	Para obtener un buen equilibrio entre rendimiento y precisión, se recomienda establecer este valor igual o ligeramente superior al número de resultados que desea recuperar (top_k).