5 problemas difíciles de búsqueda de vectores y cómo los resolvimos en Apache Cassandra

La búsqueda de vectores es un componente crítico de las herramientas de IA generativa debido a cómo la generación aumentada de recuperación (RAG) LLAMARADA ayuda a los LLM a incorporar información actualizada y personalizada evitando alucinaciones . Al mismo tiempo, la búsqueda de vectores es una característica, no un producto: necesita consultar los vectores en relación con el resto de sus datos, no de forma aislada, y no debería necesitar crear una canalización para sincronizar el resto de sus datos. datos con un almacén de vectores para hacer eso.

2023 ha visto una explosión en productos y proyectos de búsqueda de vectores, lo que hace que seleccionar entre ellos sea un esfuerzo serio. Mientras investiga las opciones, deberá considerar los siguientes problemas difíciles y los diferentes enfoques para resolverlos. Aquí, lo guiaré a través de estos desafíos y describiré cómo DataStax los abordó para nuestra implementación de búsqueda vectorial para DataStax Astra DB y Apache Cassandra.

Descripción general del contenido

• La maldición de la dimensionalidad
• Problema 1: ampliación horizontal
• Problema 2: recolección eficiente de basura
• Barra lateral: cargas de trabajo de aplicaciones en la nube
• Problema 3: concurrencia
• Problema 4: uso eficaz del disco
• Problema 5: componibilidad
• Envolver

La maldición de la dimensionalidad

En el centro de estos difíciles problemas se encuentra lo que los investigadores llaman “ la maldición de la dimensionalidad .” Lo que esto significa en la práctica es que los algoritmos que funcionan para la búsqueda de vectores exactos en espacios 2D o 3D, como árboles kd , se desmorona cuando llegas a decenas, centenas o miles de dimensiones en tus vectores. El resultado es que no existe un atajo para la búsqueda de similitud exacta con vectores de alta dimensión; Para obtener resultados en tiempo logarítmico, necesitamos utilizar algoritmos de vecino más cercano aproximado (ANN), que conllevan desafíos en las siguientes áreas.

Problema 1: ampliación horizontal

Muchos algoritmos de búsqueda vectorial se diseñaron para conjuntos de datos que caben en la memoria de una sola máquina, y este sigue siendo el único escenario probado por ann-puntos de referencia . (¡Ann-benchmarks restringe aún más sus pruebas a un solo núcleo!) Esto podría estar bien para un trabajo académico de un millón de documentos o filas, pero han pasado muchos años desde que eso podría considerarse representativo de las cargas de trabajo del mundo real.

Al igual que con cualquier otro dominio, el escalamiento horizontal requiere replicación y partición, así como subsistemas para manejar el reemplazo de réplicas inactivas, repararlas después de una partición de red, etc.

Esto fue fácil para nosotros: la replicación escalada es el pan de cada día de Cassandra, y combinar eso con el nuevo SAI (Indexación adjunta de almacenamiento) de Cassandra-5.0 – ver CEP-7 por cómo funciona y la documentación de la EFS para saber cómo usarlo) brindó a nuestra implementación de búsqueda vectorial poderosas capacidades de escalamiento horizontal de manera efectiva y gratuita.

Problema 2: recolección eficiente de basura

Por "recolección de basura" me refiero a eliminar información obsoleta del índice: limpiar filas eliminadas y tratar con filas cuyo valor del vector indexado ha cambiado. Puede que no parezca que valga la pena mencionarlo (ha sido un problema más o menos resuelto durante cuarenta años en el mundo de las bases de datos relacionales), pero los índices vectoriales son únicos.

El problema clave es que todos los algoritmos que conocemos que proporcionan búsquedas de baja latencia y resultados de alta recuperación se basan en gráficos. Hay muchos otros algoritmos de indexación de vectores disponibles: FAISS implementa muchos de ellos, pero todos son demasiado lentos para construir, demasiado lentos para buscar u ofrecen un recuerdo demasiado bajo (¡y a veces los tres!) para ser una solución de propósito general. Es por eso que todas las bases de datos de vectores de producción que conozco utilizan un índice basado en gráficos, el más simple de los cuales es HNSW. Los gráficos jerárquicos navegables de Small World fueron introducido por Yury Malkov et al en 2016 ; El documento es bastante legible y lo recomiendo ampliamente. Más sobre HNSW a continuación.

El desafío con los índices de gráficos es que no se puede simplemente extraer el nodo antiguo (asociado a un vector) cuando cambia una fila o un documento; Si hace eso más de un puñado de veces, su gráfico ya no podrá cumplir su propósito de dirigir BFS (búsqueda en amplitud) hacia áreas de mayor similitud con un vector de consulta.

Por lo tanto, necesitará reconstruir sus índices en algún momento para realizar esta recolección de basura, pero ¿cuándo y cómo lo organiza? Si siempre reconstruye todo cuando se realizan cambios, aumentará enormemente las escrituras físicas realizadas; esto se llama amplificación de escritura. Por otro lado, si nunca reconstruye, hará un trabajo adicional filtrando filas obsoletas en el momento de la consulta ("amplificación de lectura").

Este es otro espacio problemático en el que Cassandra ha estado trabajando durante años. Dado que los índices SAI están adjuntos al ciclo de vida del almacenamiento principal, también participan en Cassandra. compactación , que aumenta logarítmicamente las unidades de almacenamiento para proporcionar un equilibrio saludable entre lecturas y escrituras.

Barra lateral: cargas de trabajo de aplicaciones en la nube

DataStax Astra DB se basa en Apache Cassandra para proporcionar una plataforma para cargas de trabajo de aplicaciones en la nube.

Eso significa cargas de trabajo que son:

• De miles a millones de solicitudes masivamente simultáneas por segundo, generalmente para recuperar solo unas pocas filas cada una. Esta es la razón por la que no podría ejecutar Netflix en Snowflake, incluso si pudiera permitírselo: Snowflake y sistemas analíticos similares están diseñados para manejar solo unas pocas solicitudes simultáneas que se ejecutan cada una durante muchos segundos a minutos o incluso más.

  
  

• Más grande que la memoria Si su conjunto de datos cabe en la memoria de una sola máquina, casi no importa qué herramientas utilice. Sqlite, MongoDB, MySQL: todos funcionarán bien. Las cosas se vuelven más desafiantes cuando ese no es el caso, y la mala noticia es que las incrustaciones de vectores suelen ser de varios KB, o alrededor de un orden de magnitud más grandes que los documentos de bases de datos típicos, por lo que llegará a un tamaño mayor que la memoria con relativa rapidez.

  
  

• Principal de la aplicación Si no le importa si pierde sus datos, ya sea porque no son tan importantes o porque puede reconstruirlos a partir de la fuente de registro real, entonces, de nuevo, no importa qué herramientas utilice. Las bases de datos como Cassandra y Astra DB están diseñadas para mantener sus datos disponibles y duraderos pase lo que pase.

Problema 3: concurrencia

Mencioné anteriormente que el conocido ann-puntos de referencia La comparación limita todos los algoritmos a un solo núcleo. Si bien esto nivela el campo de juego, también perjudica a quienes pueden aprovechar la principal fuente de mejora del hardware en las últimas dos décadas.

Un problema relacionado es que ann-benchmarks solo realiza un tipo de operación a la vez: primero, crea el índice y luego lo consulta. Tratar con actualizaciones intercaladas con búsquedas es opcional y probablemente incluso una desventaja; Si sabe que no necesita lidiar con actualizaciones, puede hacer muchas suposiciones simplificadoras que se ven bien en puntos de referencia artificiales.

Si le interesa poder realizar múltiples operaciones simultáneas con su índice o actualizarlo una vez creado, entonces necesita profundizar un poco más para comprender cómo funciona y qué compensaciones implica.

Primero, todas las bases de datos vectoriales de propósito general que conozco utilizan índices basados en gráficos. Esto se debe a que puede comenzar a consultar el índice de un gráfico tan pronto como se inserta el primer vector. La mayoría de las otras opciones requieren que usted cree el índice completo antes de consultarlo o al menos haga un escaneo preliminar de los datos para conocer algunas propiedades estadísticas.

Sin embargo, todavía hay detalles de implementación importantes incluso dentro de la categoría de índice de gráficos. Por ejemplo, al principio pensamos que podríamos ahorrar tiempo utilizando la implementación del índice HNSW de Lucene, como lo hacen MongoDB Elastic y Solr. Pero rápidamente aprendimos que Lucene solo ofrece construcción de índices no concurrentes y de un solo subproceso. Es decir, no puede consultarlo mientras se está construyendo (¡lo cual debería ser una de las razones principales para usar esta estructura de datos!) ni permitir que varios subprocesos lo creen simultáneamente.

El artículo de HNSW sugiere que un enfoque de bloqueo detallado puede funcionar, pero lo hicimos mejor y creamos un índice sin bloqueo. Esto es de código abierto en JVector .

JVector escala las actualizaciones simultáneas linealmente a al menos 32 subprocesos. Este gráfico tiene una escala logarítmica en los ejes x e y, lo que muestra que duplicar el número de subprocesos reduce a la mitad el tiempo de construcción.

Más importante aún, la simultaneidad sin bloqueo de JVector beneficia cargas de trabajo más realistas al combinar búsquedas con actualizaciones. Aquí hay una comparación del rendimiento de Astra DB (usando JVector) en comparación con Pinecone en diferentes conjuntos de datos. Si bien Astra DB es aproximadamente un 10% más rápido que Pinecone para un conjunto de datos estáticos, es entre 8 y 15 veces más rápido y al mismo tiempo indexa nuevos datos. Elegimos el mejor nivel de pod disponible con Pinecone (tipo de pod: p2 y tamaño de pod: x8, con 2 pods por réplica) según sus recomendaciones para un mayor rendimiento y una menor latencia. Pinecone no revela a qué recursos físicos corresponde esto. En el lado de Astra DB, elegimos el modelo de implementación PAYG predeterminado y no tuvimos que preocuparnos por elegir los recursos, ya que no tiene servidor. Las pruebas se realizaron utilizando NoSQLBench .

Astra DB hace esto manteniendo una mayor recuperación y precisión también ( F1 es una combinación de recuperación y precisión ) :

Problema 4: uso eficaz del disco

Empezamos con el Algoritmo de indexación de gráficos HNSW porque es rápido para crear el índice, rápido para consultar, muy preciso y sencillo de implementar. Sin embargo, tiene un inconveniente bien conocido: requiere mucha memoria.

Un índice HNSW es una serie de capas, donde cada capa por encima de la capa base tiene aproximadamente un 10% de nodos que la anterior. Esto permite que las capas superiores actúen como una lista de omisión, lo que permite que la búsqueda se concentre en el vecindario correcto de la capa inferior que contiene todos los vectores.

Sin embargo, este diseño significa que (al igual que con todos los índices de gráficos) no puede salirse con la suya diciendo "La caché del disco nos salvará", porque, a diferencia de las cargas de trabajo de consultas de bases de datos normales, cada vector en el gráfico tiene casi la misma probabilidad de siendo relevante para una búsqueda. (La excepción son las capas superiores, que podemos almacenar en caché, y lo hacemos).

Así es como se veía un perfil de servicio de un conjunto de datos vectoriales de 100 millones de fragmentos de artículos de Wikipedia (aproximadamente 120 GB en disco) en mi escritorio con 64 GB de RAM, cuando usábamos Lucene:

Cassandra pasa casi todo su tiempo esperando leer vectores del disco.

Para resolver este problema, implementamos un algoritmo más avanzado llamado DiskANN y lo liberamos como un motor de búsqueda vectorial integrado independiente. JVector . (Específicamente, JVector implementa la versión incremental de DiskANN descrita en el FreshDiskANN paper.) Brevemente, DiskANN utiliza un gráfico de un solo nivel con bordes más largos que HNSW y un diseño optimizado de vectores y vecinos para reducir las IOPS del disco y mantiene una representación comprimida de los vectores en la memoria para acelerar los cálculos de similitud. Esto da como resultado triplicar el rendimiento de la carga de trabajo de Wikipedia.

Así es como se ve HNSW frente a DiskANN en un escenario puramente integrado sin componentes cliente/servidor. Esto mide la velocidad de búsqueda en el conjunto de datos Deep100M en Lucene (HNSW) y JVector (DiskANN). El índice de Lucene es de 55 GB, incluido el índice y los vectores sin formato. El índice JVector es de 64 GB. La búsqueda se realizó en mi MacBook de 24 GB, que tiene aproximadamente un tercio de la memoria que se necesitaría para mantener el índice en la RAM.

Problema 5: componibilidad

La componibilidad en el contexto de los sistemas de bases de datos se refiere a la capacidad de integrar sin problemas varias características y capacidades de manera coherente. Esto es particularmente significativo cuando se habla de la integración de una nueva categoría de capacidad, como la búsqueda vectorial. Las aplicaciones que no sean de juguete siempre requerirán tanto el clásico CRUD características de la base de datos, así como la nueva búsqueda de vectores.

Considere lo simple chatbot de IA Aplicación de muestra para Astra DB. Se trata de una aplicación RAG tan pura como la que encontrará, que utiliza la búsqueda vectorial para presentar la documentación adecuada al LLM para responder a las preguntas de los usuarios. Sin embargo, incluso una demostración simple como esta todavía necesita realizar consultas "normales" y no vectoriales a Astra DB para recuperar el historial de conversaciones, que también debe incluirse con cada solicitud al LLM para que pueda "recordar" lo que ya se ha hecho. lugar tomado. Entonces las consultas clave incluyen:

1. Encuentre los documentos (o fragmentos de documentos) más relevantes para la pregunta del usuario
2. Recuperar los últimos veinte mensajes de la conversación del usuario.

En un caso de uso más realista, uno de nuestros ingenieros de soluciones trabajó recientemente con una empresa en Asia que quería agregar búsqueda semántica a su catálogo de productos, pero también quería habilitar la coincidencia basada en términos. Por ejemplo, si el usuario busca [válvula de bola “roja”], entonces quiere restringir la búsqueda a elementos cuya descripción coincida con el término “rojo”, sin importar cuán semánticamente similares sean las incrustaciones de vectores. La nueva consulta clave entonces (además de la funcionalidad clásica como administración de sesiones, historial de pedidos y actualizaciones del carrito de compras) es la siguiente: restringir los productos a aquellos que contengan todos los términos citados, luego encontrar los más similares a la búsqueda del usuario.

Este segundo ejemplo deja claro que las aplicaciones no sólo necesitan tanto la funcionalidad de consulta clásica como la búsqueda vectorial, sino que a menudo necesitan poder utilizar elementos de cada una en la misma consulta.

El estado actual del arte en este joven campo es tratar de hacer lo que llamo consultas clásicas en una base de datos “normal”, consultas vectoriales en una base de datos vectorial y luego unir las dos de manera ad hoc cuando ambas estén disponibles. requerido al mismo tiempo. Esto es propenso a errores, lento y costoso; su única virtud es que puedes hacerlo funcionar hasta que tengas una mejor solución.

En Astra DB, hemos creado (y hemos abierto el código abierto) esa mejor solución, además de Cassandra SAI. Debido a que SAI permite crear tipos de índices personalizados que están todos vinculados al ciclo de vida estable y de compactación de Cassandra, es sencillo para Astra DB permitir a los desarrolladores mezclar y combinar predicados booleanos, búsquedas basadas en términos y búsquedas vectoriales, sin gastos generales de gestionar y sincronizar sistemas separados. Esto brinda a los desarrolladores que crean aplicaciones de IA generativa capacidades de consulta más sofisticadas que impulsan una mayor productividad y un tiempo de comercialización más rápido.

Envolver

Los motores de búsqueda de vectores son una nueva característica importante de la base de datos con múltiples desafíos arquitectónicos, incluido el escalamiento horizontal, la recolección de basura, la concurrencia, el uso efectivo del disco y la componibilidad. Creo que al crear la búsqueda vectorial para Astra DB hemos podido aprovechar las capacidades de Cassandra para ofrecer la mejor experiencia de su clase a los desarrolladores de aplicaciones de IA generativa. Obtenga más información sobre Astra DB aquí , o si desea conocer de cerca los algoritmos de búsqueda vectorial, consulte JVector .

- Por Jonathan Ellis, DataStax