Evolución de la base de datos vectorial escalable en la nube Milvus

En este artículo, compartiremos el proceso de reflexión sobre cómo diseñamos la nueva arquitectura de clúster de la base de datos Milvus.

Objetivos de la base de datos vectorial Milvus

Cuando se nos ocurrió por primera vez la idea de la base de datos vectorial Milvus, queríamos construir una infraestructura de datos que pudiera ayudar a las personas a acelerar la adopción de la IA en sus organizaciones.

Hemos fijado dos objetivos cruciales para que el proyecto Milvus cumpla esta misión.

Facilidad de uso

La IA/ML es un área emergente en la que no dejan de aparecer nuevas tecnologías. La mayoría de los desarrolladores no están del todo familiarizados con las tecnologías y herramientas de rápido crecimiento de la IA. Los desarrolladores ya han consumido la mayor parte de sus energías buscando, entrenando y ajustando los modelos. Les resulta difícil dedicar esfuerzos adicionales a manejar las grandes cantidades de vectores de incrustación generados por los modelos. Por no hablar de que la manipulación de un gran volumen de datos es siempre una tarea muy difícil.

Por eso damos una prioridad muy alta a la "facilidad de uso", ya que podría reducir significativamente el coste de desarrollo.

Bajos costes de funcionamiento

Uno de los principales obstáculos de la IA en la producción es justificar el retorno de la inversión. Tendríamos más oportunidades de poner nuestras aplicaciones de IA en producción con costes de funcionamiento más bajos. Y ello permitiría elevar el margen de beneficios potenciales.

Principios de diseño de Milvus 2.0

En Milvus 1.0 dimos un primer paso hacia estos objetivos. Pero distaba mucho de ser suficiente, sobre todo en escalabilidad y disponibilidad. Entonces comenzamos el desarrollo de Milvus 2.0 para mejorar estos puntos. Los principios que hemos establecido para esta nueva versión incluyen:

• Apuntar a una alta escalabilidad y disponibilidad
• Basarse en infraestructuras y prácticas maduras en la nube
• Compromiso mínimo del rendimiento en la nube

En otras palabras, queremos que el clúster de base de datos Milvus sea nativo de la nube.

La evolución de los clústeres de bases de datos

La base de datos vectorial es una nueva especie de base de datos, ya que maneja nuevos tipos de datos (vectores). Pero sigue compartiendo los mismos retos que otras bases de datos, con algunos requisitos propios. En el resto de este artículo, me centraré en lo que hemos aprendido de las implementaciones de grupos de bases de datos existentes y en el proceso de reflexión de cómo diseñamos la nueva arquitectura del grupo Milvus.

Si está interesado en los detalles de implementación de los componentes de grupo de Milvus, manténgase al tanto de la documentación de Milvus. Publicaremos continuamente artículos técnicos en el repositorio GitHub de Milvus, en el sitio web de Milvus y en el blog de Milvus.

El clúster de base de datos ideal

"Apunta pequeño, falla pequeño".

Enumeremos primero las capacidades críticas que debe tener un clúster de base de datos ideal.

1. Concurrencia y ningún punto único de fallo: los usuarios conectados a diferentes miembros del grupo pueden tener acceso simultáneo de lectura/escritura a la misma pieza de datos.
2. Coherencia: los distintos miembros del grupo deben ver los mismos datos.
3. Escalabilidad: podemos añadir o eliminar miembros del grupo sobre la marcha.

Sinceramente, todas estas capacidades son difíciles de adquirir juntas. En las implementaciones modernas de grupos de bases de datos, la gente tiene que comprometer algunas de estas capacidades. La gente no espera un clúster de base de datos perfecto, siempre y cuando pueda encajar en los escenarios de los usuarios. Sin embargo, el clúster "todo compartido" estuvo en su día muy cerca de un clúster de base de datos ideal. Si queremos aprender algo, deberíamos empezar por aquí.

Las consideraciones clave de un clúster de base de datos

El clúster shared-everything tiene una historia más dilatada en comparación con otras implementaciones modernas. El grupo de compartición de datos Db2 y Oracle RAC son típicos clústeres de compartición de todo. Mucha gente piensa que compartir todo significa compartir discos. Es mucho más que eso.

Un clúster shared-everything sólo tiene un tipo de miembro de base de datos en el grupo. Los usuarios pueden conectarse a cualquiera de estos miembros simétricos para acceder a cualquier dato. ¿Qué es "todo" lo que hay que compartir para que esto funcione?

La secuencia de eventos en el grupo

En primer lugar, la secuencia de eventos del grupo es crucial para resolver los posibles conflictos causados por el acceso concurrente desde distintos miembros del grupo. Solemos utilizar el número de secuencia del registro de la base de datos para representar la secuencia de eventos. Al mismo tiempo, el número de secuencia del registro suele generarse a partir de la marca de tiempo.

Por lo tanto, el requisito de la secuencia de eventos de grupo es igual a la necesidad de un temporizador global. Si pudiéramos tener un reloj atómico para el grupo, sería fabuloso. Sin embargo, Milvus es un proyecto de software de código abierto, lo que significa que debemos confiar en los recursos comúnmente disponibles. Hasta la fecha, un reloj atómico sigue siendo una opción de primera calidad para las grandes empresas.

Hemos implementado el componente de sincronización horaria en el cluster de bases de datos Milvus 2.0. Puede encontrar el enlace en el apéndice.

Bloqueo global

La base de datos tiene un mecanismo de bloqueo para resolver los conflictos de acceso concurrentes, ya sean bloqueos optimistas o pesimistas. Del mismo modo, necesitamos un bloqueo global para resolver conflictos de acceso simultáneo entre diferentes miembros del grupo.

El bloqueo global implica que los distintos miembros del grupo tienen que hablar entre sí para negociar las solicitudes de bloqueo. Varios factores vitales influirían en la eficacia de este proceso de negociación de bloqueos globales:

• la velocidad de las conexiones entre sistemas
• el número de miembros del grupo que deben participar en el proceso de negociación
• La frecuencia de los conflictos de grupo

El tamaño típico de un grupo no supera los 100 miembros. Por ejemplo, Db2 DSG es de 32; Oracle RAC es de 100. Esos miembros del grupo se colocarán en una sala de servidores conectada con fibra óptica para minimizar la latencia de la transferencia. Por eso a veces se le llama clúster centralizado. Debido a la limitación del tamaño de los grupos, la gente elegirá servidores de gama alta (mainframes o miniordenadores, que tienen mucha más capacidad en CPU, memoria, canales de E/S, etc.) para formar los clústeres que comparten todo.

Esta presunción de hardware ha cambiado drásticamente en el entorno moderno de la nube. Hoy en día, los centros de datos en nube constan de salas de servidores de alta densidad repletas de (miles de) servidores X86 básicos con conexiones TCP/IP. Si nos basamos en estos servidores X86 para construir el clúster de base de datos, el tamaño del grupo debería aumentar a cientos (incluso miles) de máquinas. Y en algunos escenarios de negocio, querremos que estos cientos de máquinas X86 se repartan en diferentes regiones. Por lo tanto, implementar el bloqueo global puede que ya no merezca la pena, ya que el rendimiento del bloqueo global no será lo suficientemente bueno.

En Milvus 2.0, no vamos a implementar la función de bloqueo global. Por un lado, no hay actualización para los datos vectoriales. (Así que no tenemos que preocuparnos por los conflictos de múltiples escritores en la misma pieza de datos en el grupo Milvus con la disposición de fragmentación. Mientras tanto, podríamos utilizar MVCC (control de concurrencia multiversión, un método de control de concurrencia que evita el bloqueo) para resolver los conflictos entre lectores y escritores.

Por otro lado, el procesamiento de datos vectoriales consume mucha más memoria que el procesamiento de datos estructurados. Se busca una escalabilidad mucho mayor en las bases de datos vectoriales.

Caché de datos en memoria compartida

Podemos dividir brevemente el motor de una base de datos en dos partes: el motor de almacenamiento y el motor de cálculo. El motor de almacenamiento es responsable de dos tareas críticas:

• Escribir datos en el almacenamiento permanente con fines de durabilidad.
• Cargar datos desde el almacenamiento permanente a la caché de datos en memoria (también conocida como reserva de búferes); éste es el único lugar donde el motor informático accede a los datos.

En el escenario del clúster de base de datos, ¿qué ocurre si el miembro A ha actualizado los datos almacenados en caché en el miembro B? ¿Cómo podría saber el miembro B que sus datos en memoria han caducado? El clúster clásico "shared-everything" dispone de un mecanismo de invalidación cruzada de búferes para resolver este problema. El mecanismo de invalidación cruzada del búfer funcionará de forma similar al bloqueo global si mantenemos una fuerte consistencia entre los miembros del grupo. Como ya se ha dicho, esto no es práctico en el entorno moderno de la nube. Así que decidimos bajar el nivel de consistencia en el grupo Milvus escalable en la nube a un modo de consistencia eventual. De este modo, el mecanismo de invalidación cruzada del búfer en Milvus 2.0 puede ser un proceso asíncrono.

Almacenamiento compartido

El almacenamiento compartido es probablemente lo primero en lo que la gente pensaría cuando se habla de un grupo de bases de datos.

Las opciones de almacenamiento también han cambiado significativamente en los últimos años de evolución del almacenamiento en la nube. La red de almacenamiento conectado (SAN) era (y sigue siendo) la base de almacenamiento del grupo de almacenamiento compartido. Pero en el entorno de nube, no hay SAN. La base de datos tiene que utilizar el disco local conectado a las máquinas virtuales de la nube. Usar el disco local introduce el reto de la consistencia de los datos entre los miembros del grupo. Y también tenemos que preocuparnos por la alta disponibilidad de los miembros del grupo.

Entonces Snowflake hizo un gran modelo para las bases de datos en la nube utilizando el almacenamiento compartido en la nube (almacenamiento S3). También inspira a Milvus 2.0. Como ya hemos dicho, pretendemos confiar en una infraestructura en la nube madura. Pero antes de poder utilizar el almacenamiento compartido en la nube, tenemos que pensar en un par de cosas.

En primer lugar, el almacenamiento S3 es barato y fiable, pero no está diseñado para el acceso instantáneo R/W como los escenarios de bases de datos. Tenemos que crear los componentes de datos (que llamamos nodos de datos en Milvus 2.0) para unir la memoria local/disco y el almacenamiento S3. Hay algunos ejemplos (como Alluxio, JuiceFS, etc.) que podríamos aprender. La razón por la que no podemos integrar estos proyectos directamente es que nos centramos en una granularidad de datos diferente. Alluxio y JuiceFS están diseñados para conjuntos de datos o archivos POSIX, mientras que nosotros nos centramos en el nivel de registro de datos (vector).

Cuando los datos vectoriales se asientan en el almacenamiento S3, la respuesta para los metadatos es fácil: almacenarlos en ETCD. ¿Qué ocurre entonces con los datos de registro? En las implementaciones clásicas, el almacén de registro también se basa en SAN. Los archivos de registro de un miembro del grupo de base de datos se comparten dentro del clúster de base de datos para fines de recuperación de fallos. Así que esto no era un problema hasta que entramos en el entorno de la nube.

En el documento de Spanner, Google ilustró cómo implementaron la base de datos distribuida globalmente (grupo) con el algoritmo de consenso Paxos. Es necesario programar el grupo de bases de datos como un grupo de replicación de máquinas de estado. El redo log suele ser el "estado" que se replicará en todo el grupo.

La replicación de redo-log mediante algoritmos de consenso es una herramienta poderosa, y tiene ventajas sustanciales en algunos escenarios empresariales. Pero para la base de datos vectorial Milvus, no encontramos suficientes incentivos para crear un grupo de replicación de máquinas de estado en conjunto. Decidimos utilizar la cola/plataforma de mensajería en la nube (Apache Pulsar, Apache Kafka, etc.) como almacenamiento compartido en la nube alternativo para el almacén de registros. Al delegar el almacén de registros a la plataforma de mensajería, adquirimos los siguientes beneficios.

• El grupo está más orientado a eventos, lo que significa que muchos procesos pueden ser asíncronos. Mejora la escalabilidad.
• Los componentes están más libremente acoplados, por lo que es mucho más fácil realizar actualizaciones continuas en línea. Mejora la disponibilidad y la operatividad.

Volveremos sobre este tema más adelante.

Hasta aquí, hemos resumido las consideraciones cruciales del clúster de base de datos. Antes de pasar a la discusión sobre la arquitectura de Milvus 2.0, permítanme explicar cómo gestionamos los vectores en Milvus.

Gestión de datos y previsibilidad del rendimiento

Milvus almacena los vectores en colecciones. La "colección" es un concepto lógico, equivalente a una "tabla" en las bases de datos SQL. Una "colección" puede tener varios archivos físicos para guardar vectores. Un fichero físico es un "segmento". El "segmento" es un concepto físico, como un archivo tablespace en las bases de datos SQL. Cuando el volumen de datos es pequeño, podemos guardarlo todo en un único segmento/fichero físico. Pero hoy en día, nos enfrentamos constantemente a big data. Cuando hay varios segmentos/archivos físicos, ¿cómo debemos repartir los datos en diferentes particiones de datos?

Aunque los datos son lo primero antes que los índices, tenemos que almacenar los datos de la forma que prefiera el algoritmo de índices para que el acceso a los datos sea eficiente en la mayoría de los casos. Una estrategia muy utilizada en las bases de datos SQL es la partición por el rango de valores de la clave de partición. Normalmente se crea un índice agrupado para aplicar la clave de partición. En general, este es un enfoque decente para las bases de datos SQL. Los datos se almacenan en buena forma, optimizados para E/S (prefetch). Pero sigue habiendo defectos.

• Datos sesgados. Algunas de las particiones pueden tener muchos más datos que otras. La distribución de los datos del mundo real no es tan simple como el rango numérico.
• Puntos calientes de acceso. Es posible que algunas particiones de datos reciban más carga de trabajo.

Imaginemos que más carga de trabajo va a las particiones con más datos. Tenemos que reequilibrar los datos entre las particiones cuando se producen estas situaciones. (Este es el tedioso día a día de un DBA).

El índice agrupado para vectores

También podemos crear un índice agrupado para vectores (un índice de lista invertida). Pero no es el mismo caso que en las bases de datos SQL. Una vez construido el índice en las bases de datos SQL, es muy eficiente acceder a los datos a través del índice, con menos cálculos y menos operaciones de E/S. Pero para los datos vectoriales, habrá muchos más cálculos y operaciones de E/S, incluso con un índice. Por tanto, los defectos antes mencionados tendrán un impacto más grave en los clústeres de bases de datos vectoriales. Además, el coste de reequilibrar los vectores en los distintos segmentos es muy elevado debido al volumen de datos y a la complejidad computacional.

En Milvus, utilizamos la estrategia de partición por crecimiento. Cuando inyectamos datos en una colección de vectores, Milvus añadirá los nuevos vectores al último segmento de la colección. Milvus cerrará el segmento una vez que su tamaño sea lo suficientemente grande (el umbral es configurable) y construirá el índice para el segmento cerrado. Mientras tanto, se creará un nuevo segmento para almacenar los próximos datos. Esta estrategia simple es más equilibrada para el procesamiento vectorial.

La consulta vectorial es un proceso para buscar los candidatos más similares en la colección de vectores. Es un procedimiento típico de MapReduce. Por ejemplo, queremos buscar los 20 resultados más similares de una colección de vectores con diez segmentos. Podemos buscar los 20 mejores en cada uno de los segmentos y luego fusionar los 20 * 10 resultados en los 20 resultados finales. Dado que cada segmento tiene la misma cantidad de vectores y un índice similar, el tiempo de procesamiento en cada segmento es casi idéntico. Esto nos da la ventaja de la previsibilidad del rendimiento, que es esencial a la hora de planificar la escala de los clusters de bases de datos.

Nuevos paradigmas en Milvus 2.0

En Milvus 1.0, implementamos un grupo de fragmentación de lectura/escritura como la mayoría de las bases de datos SQL. Fue un buen intento de escalar el cluster de bases de datos Milvus. Pero los problemas también son bastante evidentes.

Base de datos Milvus 1.0

En Milvus 1.0, el nodo R/W tiene que ocuparse totalmente del último segmento, incluyendo la adición de vectores, la búsqueda en este segmento no indexado, la construcción del índice, etc. Dado que cada colección sólo tiene un escritor, éste está muy ocupado si los datos entran continuamente en el sistema. El rendimiento de la compartición de datos entre el nodo R/W y los nodos lectores también es un problema. Además, para el almacenamiento de datos compartidos debemos confiar en NFS (no es estable) o en el almacenamiento premium en la nube (demasiado caro).

Estos problemas existentes son difíciles de abordar en la arquitectura Milvus 1.0. Por lo tanto, hemos introducido nuevos paradigmas en el diseño de Milvus 2.0 para resolver estos problemas.

Arquitectura de Milvus

Modelo de actor

Existen dos modelos para programar sistemas de computación concurrente.

• Memoria compartida que implica control de concurrencia (bloqueo) y procesamiento síncrono.
• El modelo de actor (también conocido como paso de mensajes) significa procesamiento asíncrono y basado en mensajes.

También podemos aplicar estos dos modelos en clústeres de bases de datos distribuidas.

Como ya se ha dicho, la mayoría de las bases de datos distribuidas de alto perfil utilizan el mismo método: la replicación de registros de rehacer mediante algoritmos de consenso. Se trata de un procesamiento síncrono que utiliza algoritmos de consenso para construir una memoria compartida distribuida para los registros redo-log. Diferentes empresas y capitales de riesgo han invertido miles de millones de dólares en esta tecnología. No quise hacer comentarios al respecto hasta que empezamos a trabajar en Milvus 2.0. Mucha gente considera esta tecnología como la única forma de realizar sistemas de bases de datos distribuidos. Esto es molesto. Si no digo algo, la gente podría malinterpretar que fuimos imprudentes en el diseño de bases de datos distribuidas.

En los últimos años, la replicación Redo-log mediante algoritmos de consenso ha sido la tecnología de bases de datos más sobrevalorada. Hay dos cuestiones clave.

• La presunción de que la replicación redo-log es mejor es frágil.
• Los vendedores engañan a la gente sobre la capacidad de los algoritmos de consenso.

Supongamos que tenemos dos nodos de base de datos, el nodo de origen y el nodo de destino. Al principio, tienen la copia exacta de los datos. Tenemos algunas operaciones de cambio (sentencias SQL I/U/D) en el nodo de origen, y queremos mantener actualizado el nodo de destino. ¿Qué debemos hacer? La forma más sencilla es reproducir las operaciones en el nodo de destino. Pero no es la forma más eficiente.

Pensando en el coste de ejecución de una sentencia I/U/D, podemos dividirlo en las partes de preparación de la ejecución y de trabajo físico. La parte de preparación de la ejecución incluye el trabajo del analizador SQL, el optimizador SQL, etc. Independientemente del número de registros de datos que se vean afectados, se trata de un coste fijo. El coste de la parte de trabajo físico depende de cuántos registros de datos se vean afectados; es un coste flotante. La idea detrás de la replicación de redo-log es ahorrar el coste fijo en el nodo de destino; sólo replicamos el redo-log (el trabajo físico) en el nodo de destino.

El porcentaje de ahorro de costes es el recíproco del número de registros redo-log. Si una operación sólo afecta a un registro, debería ver un ahorro significativo con la replicación de redo-log. ¿Y si son 10.000 registros? Entonces deberíamos preocuparnos por la fiabilidad de la red. ¿Qué es más fiable, enviar la única operación o los 10.000 registros redo-log? ¿Qué tal un millón de registros? La replicación de redo-logs es estupenda en escenarios como sistemas de pago, sistemas de metadatos, etc. En estos escenarios, cada operación I/U/D de la base de datos sólo afecta a un pequeño número de registros (1 ó 2). Pero es difícil trabajar con cargas de trabajo intensivas en E/S, como los trabajos por lotes.

Los vendedores siempre afirman que los algoritmos de consenso podrían proporcionar una fuerte consistencia a los clusters de bases de datos. Pero la gente sólo utiliza algoritmos de consenso para replicar los registros redo-log. Los registros redo-log son consistentes en diferentes nodos, pero eso no significa que las vistas de datos en otros nodos sean consistentes tampoco. Tenemos que fusionar los registros redo-log en los registros reales de la tabla. Así que incluso con este procesamiento síncrono, sólo podemos obtener consistencia eventual en las vistas de datos.

Deberíamos utilizar la replicación de redo-log por algoritmos de consenso en los lugares apropiados. El sistema de metadatos (ETCD) y la plataforma de mensajería (por ejemplo, Apache Pulsar) utilizados en Milvus 2.0 han implementado algoritmos de consenso. Pero como dije antes, "para la base de datos vectorial Milvus, no encontramos suficientes incentivos para ser un grupo de replicación de máquinas de estado en conjunto".

En Milvus 2.0, utilizamos el modelo de actor para organizar los nodos trabajadores. Los nodos trabajadores están solos. Sólo hablan con la plataforma de mensajería, recibiendo órdenes y enviando resultados. Suena aburrido.

"¿Cuál es nuestro lema?" "Lo aburrido siempre es lo mejor" - El Guardaespaldas del Sicario (2017).

El modelo de actor es asíncrono. Es adecuado para la escalabilidad y la disponibilidad. Dado que los nodos trabajadores no se conocen entre sí, no hay impacto en otros nodos trabajadores si algunos de ellos se unen o se eliminan.

Separación de disponibilidad y durabilidad

En Milvus 2.0, reproducimos las operaciones en lugar de los registros, porque en la base de datos vectorial no hay mucha diferencia entre la repetición de operaciones y la repetición de registros. No tenemos la función Update ni la función Insert with Select. Y también es mucho más fácil hacer repetición de operaciones con el modelo actor.

Así, varios nodos trabajadores pueden ejecutar la misma operación desde la plataforma de mensajería según su responsabilidad. He mencionado antes que decidimos utilizar el almacenamiento en la nube S3 como la capa de almacenamiento compartido del clúster de base de datos Milvus. El almacenamiento S3 es muy fiable. Entonces, ¿es necesario que diferentes nodos trabajadores escriban los mismos datos en el almacenamiento compartido?

Por lo tanto, hemos diseñado tres funciones para los nodos trabajadores.

• El nodo de consulta mantiene una vista de datos en memoria de acuerdo con la asignación. El trabajo del nodo de consulta incluye realizar búsquedas vectoriales y mantener actualizados los datos en memoria. Pero no necesita escribir nada en el almacenamiento S3. Es el nodo más sensible a la memoria del grupo.
• El nodo de datos es responsable de escribir los nuevos datos en el almacenamiento S3. El nodo de datos no necesita mantener la vista de datos en memoria, por lo que la configuración de hardware del nodo de datos es bastante diferente de la del nodo de consulta.
• El nodo de índice construye índices para los segmentos cerrados por el nodo de datos cuando el tamaño de los segmentos alcanza el umbral. Este es el trabajo más intensivo en CPU del grupo.

Estos tres tipos de nodos representan distintos tipos de carga de trabajo. Pueden escalar independientemente. Lo llamamos separación de disponibilidad y durabilidad aprendida de la base de datos en la nube Microsoft Socrates.

El final, también el principio

Este artículo ha repasado varias decisiones de diseño de la base de datos vectorial Milvus 2.0. Vamos a resumir rápidamente esos puntos aquí.

• Hemos elegido la consistencia eventual para Milvus cluster 2.0.
• Hemos integrado los componentes maduros de la nube en Milvus 2.0 tanto como hemos podido. Hemos controlado los nuevos componentes introducidos por Milvus 2.0 en los entornos de producción de los usuarios.
• Siguiendo el modelo de actor y la separación de disponibilidad y durabilidad, Milvus 2.0 es fácil de escalar en el entorno de la nube.

Hasta ahora, hemos formado la espina dorsal de la base de datos Milvus 2.0 escalable en la nube, pero nuestro backlog contiene muchos requisitos de la comunidad Milvus que necesitan ser satisfechos. Si tiene la misma misión ("Construir más software de infraestructura de código abierto para acelerar la transformación de la IA"), bienvenido a unirse a la comunidad Milvus.

Milvus es un proyecto de graduación de la fundación LF AI & Data. ¡NO necesita firmar ningún CLA para Milvus!

Apéndice

Documento de diseño de Milvus

https://github.com/milvus-io/milvus/tree/master/docs/design_docs

• Sincronización temporal de Milvus

Implementación de Raft en C

Si sigues interesado en el algoritmo de consenso, te sugiero que consultes el proyecto de código abierto Gringofts de eBay. Es una implementación en C++ del algoritmo de consenso Raft (una variante de la familia Paxos). Mi amigo Jacky y Elvis (ex compañeros míos en Morgan Stanley) lo construyeron para el sistema de pagos en línea de eBay, que es precisamente uno de los escenarios más adecuados para esta tecnología.