En Qumulo, construimos un sistema de archivos escalable. Como es de esperar, tenemos muchos "almacenes de valores clave" en nuestro sistema: por ejemplo, hay B-Trees distribuidos para componentes del sistema de archivos como directorios y extensiones. También hay varias tiendas de valores clave de configuración. Estas estructuras están construidas en nuestra arquitectura de tiendas protegidas distribuidas. Recientemente, mi equipo construyó un nuevo almacén distribuido de clave-valor para definir la composición del sistema de protección utilizado por nuestro sistema de archivos agrupados (QSFS).
Tiendas protegidas
En términos generales, QSFS se basa en una colección de tiendas protegidas (PStores). Los PStores proporcionan las propiedades que necesitamos para nuestro sistema de archivos: transaccionalidad, tolerancia a fallas (logradas a través de codificación de borrado o duplicación), recuperación de fallas, direccionamiento independiente del disco, lecturas y escrituras eficientes, etc. Los PStores están compuestos por bloques de datos en SSD y discos giratorios en múltiples nodos. Cómo logramos las propiedades ACID con PStores es un tema para otra publicación.
Estado del sistema de protección
El mapeo entre PStores y sus componentes de unidad constituyentes es fundamental para la confiabilidad y el rendimiento de nuestro sistema. Llamamos a esto el mapa PStore. Este mapa es normalmente estático; sin embargo, cambia durante la reprotección después de una falla del disco o nodo, después de la sustitución del disco, y cuando agregamos nodos al sistema. Además, el estado del sistema de protección incluye un número de transacción confirmado globalmente que se utiliza para controlar las transacciones. Este número normalmente se incrementa unas cuantas veces por segundo. El mapa Pstore, el número de generación y algunos otros bits de información conforman el estado del sistema de protección que debemos almacenar de manera confiable, distribuida, duradera y consistente.
Paxos V1
El sistema existente para almacenar el estado del sistema de protección que nos propusimos reemplazar era una colección de tiendas multi-Paxos. Cada nodo en el grupo realizó los deberes del aceptador de Paxos y del aprendiz de Paxos. Un proponente de Paxos vivía en los nodos 1 o 2 (líderes del quórum [1]). Este sistema tuvo una serie de problemas que esperábamos resolver con nuestro nuevo almacén de valor-clave:
- Los datos del aceptador y aprendiz de Paxos se almacenaron en unidades del sistema que eran menos confiables que los SSD que usamos para los bloques de PStore. Encontramos que incluso las cargas relativamente modestas generadas por la tienda Paxos llevaron a algunas fallas prematuras de estos dispositivos.
- El mapa de PStore se almacenó como un único valor de Paxos. Este valor podría ser muy grande dependiendo del tamaño del clúster. Aunque actualizamos cada PStore de forma independiente durante la reprotección (similar a las reconstrucciones de unidades), estas actualizaciones requieren el bloqueo y la escritura de todo el mapa. Esto dio como resultado cuellos de botella de rendimiento y un desgaste acelerado en las unidades de nuestro sistema.
- Debido a que Paxos V1 fue un sistema escrito al principio de la historia de Qumulo, no utilizó nuestros nuevos métodos y marcos de prueba. Como resultado, el código de prueba para Paxos V1 fue difícil de mantener y ampliar.
Una nueva tienda de valor-clave se concibe
Para resolver estos problemas, diseñamos un nuevo sistema donde Paxos desempeñó un papel disminuido. Una única instancia de Paxos múltiple almacena el conjunto de SSD que contienen almacenes de valores clave que contienen el estado del sistema de protección. Los datos de aceptador y alumno de Paxos se almacenan en el superbloque que vive en cada SSD. Cada SSD proporciona espacio para el conjunto completo de claves del sistema de protección que necesitamos almacenar en un conjunto de bloques denominado volumen KV. En cada quórum, leemos y escribimos a Paxos solo una vez. La identidad de los volúmenes N KV define el almacén duplicado de valores clave distribuidos (DKV). Escribir en el DKV es sencillo; escriba a todos los N espejos. La lectura se puede hacer desde cualquier espejo. Durante el inicio del quórum, debemos sincronizar uno de los volúmenes KV del último quórum con diferentes volúmenes KV N-1 en el nuevo quórum. La transaccionalidad simple es suficiente para este sistema. Un error durante la escritura puede provocar desacuerdos entre tiendas individuales. Seleccionamos el valor nuevo o el valor antiguo como fuente de sincronización, eliminando cualquier inconsistencia.
Nuestro sistema de quórum garantiza que las operaciones de clúster se ejecuten con la mayoría de los nodos conectados. Los errores de conexión hacen que el clúster reforme el quórum donde cada nodo participa en una secuencia de pasos coordinados por un líder. Las operaciones en línea ocurren en los quórumes típicamente de larga vida.
Paxos V2
Nuestro nuevo almacén de valor-clave distribuido aún dependería del protocolo Paxos para almacenar el conjunto de ID de unidades que componen el almacén DKV actual. La implementación de Paxos V2 fue sencilla ya que nuestras necesidades son modestas; obtenemos una garantía de un solo proponente de nuestro sistema de quórum, y tenemos requisitos de rendimiento modestos, ya que solo necesitamos leer y escribir una pequeña cantidad de datos de Paxos una vez por quórum.
Volúmenes KV
A continuación, necesitábamos una forma de identificar los bloques en un SSD que contendría el almacén de valores clave. Sabemos que los SSD pueden proporcionar el espacio para almacenar el DKV, pero tendríamos que lidiar con el aprovisionamiento en los clústeres existentes más adelante. En esta etapa del proyecto, creamos los bloques según sea necesario (pruebas) o confiamos en la disponibilidad de bloques en los clústeres recién creados.
Los bloques SSD necesarios fueron administrados por un volumen KV en cada SSD. El volumen proporcionó varias piezas importantes de funcionalidad:
- Marcación de la asignación. Al inicio, los volúmenes KV se unieron a otras estructuras en SSD que caminamos para determinar qué se asigna y qué es gratis. Los bloques de volumen están vinculados con bloques de árbol para permitir lecturas paralelas rápidas.
- Asignación de teclas desde la tecla de volumen a la dirección del bloque.
- Lectura y escritura de bloques de valores por tecla de volumen.
- Sincronización eficiente de volúmenes de un SSD a otro.
Dada una lista de bloques disponibles (una vez más, se garantiza que existe en este punto), una clase de constructor produciría el enlace en disco necesario y los objetos de volumen resultantes.
Tiendas KV
El almacén KV proporciona la asignación de claves a valores en la parte superior del volumen KV en un solo SSD. Los bloques en nuestro sistema son 4KiB en tamaño; determinamos que los valores de estado del sistema de protección nunca tendrían que ser tan grandes como 1KiB, por lo que almacenamos los valores de 4 por bloque de volumen. El espacio clave es lineal y no disperso. La modificación de valores involucra lectura-modificación-escritura, por lo que construimos una memoria caché de volumen simple para mejorar el rendimiento.
Los almacenes KV debían ser seguros para subprocesos, por lo que esta capa también tiene un bloqueo local de nodo. Dado que las claves tienen un alias a través de los bloques de valores de volumen, el hash del ID de bloque de volumen en un conjunto fijo de exclusión mutua. Las API de lectura y escritura tienen una clave única y variantes en masa.
Distribuidor KV Distribuido y Sincronización
Creamos una clase dkv_store simple compuesta por N instancias kv_store (para nuestros requisitos de tolerancia a fallas, N es actualmente 3). Las escrituras se reenvían en paralelo a cada miembro kv_store a través de RPC, y las lecturas se reenvían a cualquier tienda miembro. Esta es la primera parte del sistema que se expone a los usuarios (por ejemplo, a los componentes de estado del sistema de protección). Exponemos un espacio de claves que es un mapeo directo de las claves kv_store de los componentes. Más tarde, cuando introdujimos la fragmentación, esta asignación cambió.
La creación de una instancia de dkv_store es responsabilidad de una función de sincronización. Cuando comenzamos un nuevo quórum, la sincronización realiza estos pasos:
- Consultar nodos en línea para la lista de volúmenes KV en línea.
- Lea el conjunto de ID de volumen KV del quórum anterior de Paxos.
- Elija un volumen en línea del conjunto de quórum anterior para que sea la fuente.
- Replique desde el origen a los volúmenes de destino N-1 no utilizados en el quórum anterior.
- Almacena el nuevo conjunto de ID de volumen en Paxos.
La prueba de este componente fue crucial; construimos pruebas exhaustivas para cubrir una matriz de tamaño de clúster, nodos inactivos, discos inactivos y errores de progreso parciales. Dado que la sincronización demora el inicio del quórum y, por lo tanto, la disponibilidad del sistema de archivos, pasamos un tiempo optimizando y paralelizando este proceso para reducir su tiempo de ejecución a unos pocos segundos.
Actualizar
Hasta este momento, nos habíamos ocupado únicamente de nuevos clústeres. Para implementar nuestro nuevo sistema, necesitábamos manejar los clústeres existentes en los sitios de los clientes. Escribimos código para actualizar los datos del antiguo Paxos almacenar en el DKV. Esto tuvo dos fases: aprovisionamiento de volumen y traducción de datos.
En un clúster activo, los bloques SSD están en uso para una variedad de propósitos (por ejemplo, bloques de registro, árboles de bloques y caché de escritura de respuesta, por ejemplo). Podemos solicitar bloques pero solo mientras el sistema esté completamente en línea. Un agente hace que los bloques estén disponibles al migrar bloques en un PStore desde el SSD a su disco giratorio de respaldo. La primera parte de la actualización inicia un proceso en segundo plano en línea en todos los nodos para aprovisionar bloques de cada SSD. Recuerde que una vez que se construye un volumen en un SSD, los bloques se vinculan y asignan, lo que impide su uso para otras necesidades. A medida que se construye cada volumen, el proceso en segundo plano informa a un maestro de actualización que reside en el nodo líder. Una vez que todos los SSD tienen volúmenes, el maestro inicia un reinicio de quórum.
En el siguiente quórum, se hace cargo la segunda mitad de la actualización. Al darse cuenta de que todos los volúmenes están presentes pero no se define dkv_store en el nuevo Paxos, un proceso de traducción selecciona un conjunto arbitrario de volúmenes que definen un dkv_store. Luego, el proceso lee los datos antiguos de Paxos V1 y los escribe en el DKV. Luego, el proceso conserva el ID de volumen DKV establecido en Paxos V2. Cuando finalizamos el inicio del quórum, una corrección de estado del sistema de protección cambia de usar el almacenamiento antiguo al almacenamiento nuevo. Los inicios de quórum futuros pasan por el proceso de sincronización normal descrito anteriormente.