Ingeniería en Qumulo: creación de una tienda distribuida de valor clave

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.

Tiendas protegidas

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.

Tienda de valores-clave

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.

Volúmenes KV

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.

Tiendas KV

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 simple dkv_store compuesta de N instancias de kv_store (para nuestros requisitos de tolerancia a fallos, N actualmente es 3). Los escritos se reenvían en paralelo a cada miembro. kv_store via RPC, and reads are forwarded to any member store. This is the first part of the system that is exposed to users (e.g. to the protection system state components). We expose a keyspace that is a direct mapping of the components’ kv_store keys. Later, when we introduced sharding, this mapping changed.

Building a dkv_store instance is the responsibility of a synchronization function. When we start a new quorum, synchronization performs these steps:

  1. Query online nodes for the list of online KV volumes.
  2. Read the KV volume ID set from the previous quorum from Paxos.
  3. Pick an online volume from the previous quorum set to be the source.
  4. Replicate from the source to N-1 destination volumes unused in the previous quorum.
  5. Store the new set of volume IDs in Paxos.

Testing of this component was crucial; we built exhaustive tests to cover a matrix of cluster size, down nodes, down disks, and partial progress errors. Since synchronization delays quorum start and hence filesystem availability, we spent some time optimizing and parallelizing this process to reduce its runtime down to a few seconds.

Upgrade

Up until this point, we had been dealing with new clusters only. To deploy our new system, we needed to handle existing clusters at customer sites. We wrote code to upgrade the data from the old Paxos store to the DKV. There were two phases to this: volume provisioning and data translation.

On an active cluster, SSD blocks are in-use for a variety of purposes (e.g. logging blocks, block trees, and write-back cache, for example). We can request blocks but only while the system is fully online. An agent makes blocks available by migrating blocks in a PStore from the SSD to its backing spinning disk. The first part of the upgrade starts an online background process on all nodes to provision blocks from each SSD. Recall that once a volume is built on an SSD, the blocks are linked and allocated, preventing further use for other needs. As each volume is built, the background process informs an upgrade master residing on the leader node. Once all SSDs have volumes, the master initiates a quorum restart.

In the next quorum, the second half of upgrade takes over. Noticing that all volumes are present but no dkv_store is defined in the new Paxos, a translation process picks an arbitrary set of volumes defining a dkv_store. The process then reads the old data from Paxos V1 and writes it into the DKV. The process then persists the DKV volume ID set in Paxos V2. As we finish the quorum start, a protection system state shim switches from using the old storage to the new storage. Future quorum starts go through the normal synchronization process outlined above.

Share this post