22 marzo, 2009

Cómo FriendFeed usa MySQL para almacenar datos sin esquema

Traducido de How FriendFeed uses MySQL to store schema-less data del blog de Bret Taylor

Fondo


Utilizamos MySQL para almacenar todos los datos en FriendFeed. Nuestra base de datos ha crecido mucho conforme lo ha hecho nuestra base de usuarios. Ahora guardamos más de 250 millones de entradas y un montón de otros datos, desde comentarios y gustos hasta listas de amistades.

Conforme ha crecido nuestra base de datos, hemos intentado tratar iterativamente con los problemas de escalado que comporta un crecimiento rápido. Hicimos lo típico, como utilizar esclavos de lectura y memcache para incrementar nuestro rendimiento en lectura o fragmentar (sharding) nuestra base de datos para mejorar el rendimiento en escritura. En cualquier caso, conforme crecíamos, escalar nuestras características para acomodar más tráfico resulto ser mucho menos problemático que añadir nuevas características.

En particular, hacer cambios en el esquema o añadir índices a una base de datos con más de 10 - 20 millones de registros bloquea la base de datos completamente durante horas. Eliminar viejos índices lleva el mismo tiempo, pero no eliminarla daña el rendimiento ya que la base de datos continuará leyendo y escribiendo esos bloques sin usar en cada INSERT, desalojando otros bloques importantes fuera de la memoria. Hay procedimientos operacionales complejos que se pueden hacer para sortear estos problemas (como crear un nuevo índice en un esclavo y entonces intercambiar maestro y esclavo), pero esos procedimientos son tan propensos a errores y tan pesados, que implícitamente nos disuadieron para añadir nuevas características que requiriesen cambios en los esquemas o índices. Ya que nuestras bases de datos están todas fuertemente fragmentadas, las características relacionales de MySQL como JOIN nunca nos han resultado útiles, por lo que decidimos mirar fuera del reino de las bases de datos relacionales (RDBMS).

Hay muchos proyectos diseñados para abordar el problema almacenando los datos con esquemas flexibles y construir nuevos índices al vuelo (p.e. CouchDB). En cualquier caso, ninguno de ellos parece lo suficientemente utilizado por sitios grandes como para inspirar confianza. En los tests que leímos y que llevamos a cabo nosotros mismos, ninguno de los proyectos eran estables o lo suficientemente probados en casos reales para nuestras necesidades (mira este algo desfasado artículo sobre CouchDB, como ejemplo). MySQL funciona. No corrompe los datos. La replicación funciona. Ya comprendimos sus limitaciones. Nos gusta MySQL para almacenar, pero no los patrones de uso relacionales (RDBMS).

Tras algo de deliberación, decidimos implementar un sistema de almacenamiento "sin esquemas" sobre MySQL en lugar de usar un sistema de almacenamiento totalmente nuevo. Este artículo intenta describir en líneas generales los detalles del sistema. Somos curiosos sobre cómo otros grandes sitios han abordado estos problemas, y pensamos que algo del trabajo de diseño que hemos realizado podría ser útil a otros desarrolladores.

Visión General


Nuesto almacén de datos guarda bolsas de propiedades sin esquema (p.e. como objetos JSON o diccionarios de Python). La única propiedad requerida para las entidades almacenadas es un id, un UUID de 16 bytes. El resto de la entidad es opaca en cuanto a lo que incumbe al almacén de datos. Podemos cambiar el "esquema" almacenando simplemente nuevas propiedades.

Indizamos datos en estas entidades almacenando los índices en tablas separadas de MySQL. Si queremos indizar tres propiedades en cada entidad, tendremos tres tablas MySQL - una por cada índice. Si queremos dejar de usar un índice, dejamos de escribir en esa tabla desde nuestro código y, opcionalmente, eliminamos la tabla de MySQL. Si queremos un nuevo índice, creamos una nueva tabla MySQL para ese índice y ejecutamos un proceso para poblar asíncronamente ese índice sin perturbar nuestro servicio activo.

Como resultado, terminamos teniendo más tablas que antes, pero añadir y eliminar índices resulta fácil. Tenemos un proceso fuertemente optimizado que puebla nuevos índices (al que llamamos "El Limpiador") de forma que rellena nuevos índices rápidamente sin perturbar el funcionamiento del sitio. Podemos almacenar nuevas propiedades e indizarlas en un mismo día en lugar de tener que hacerlo a lo largo de una semana, y no necesitamos intercambiar maestros y esclavos de MySQL ni hacer otras operaciones delicadas.

Detalles


En MySQL nuestras entidades se almacenan en una tabla similar a la siguiente:

CREATE TABLE entities (
    added_id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    id BINARY(16) NOT NULL,
    updated TIMESTAMP NOT NULL,
    body MEDIUMBLOB,
    UNIQUE KEY (id),
    KEY (updated)
) ENGINE=InnoDB;

La columna added_id está presente porque innoDB almacena los registros de datos físicamente usando el orden de la clave primaria. La clave primaria AUTO_INCREMENT fuerza a que las nuevas entidades se escriban secuencialmente en disco después de las entidades antiguas, lo que ayuda a la lectura y escritura locales (las nuevas entidades tienden a ser leídas más frecuentemente que las viejas entidades ya que las páginas de FriendFeed siguen un orden cronológico inverso). Los cuerpos de las entidades se guardan usando compresión zlib sobre diccionarios Python.

Los índices son almacenados en tablas separadas. Para crear un nuevo índice, creamos una nueva tabla que almacene los atributos que queremos indizar en todos los fragmentos de nuestra base de datos. Por ejemplo, una entidad típica en FriendFeed podría parecerse a esto:

{
    "id": "71f0c4d2291844cca2df6f486e96e37c",
    "user_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
    "feed_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
    "title": "We just launched a new backend system for FriendFeed!",
    "link": "http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
    "published": 1235697046,
    "updated": 1235697046,
}

Queremos indizar el atributo user_id de estas entidades de forma que podamos generar una página con todas las entidades que un usuario dado ha publicado. Nuestra tabla de índice podría parecerse a esto:

CREATE TABLE index_user_id (
    user_id BINARY(16) NOT NULL,
    entity_id BINARY(16) NOT NULL UNIQUE,
    PRIMARY KEY (user_id, entity_id)
) ENGINE=InnoDB;

Nuestro almacén de datos mantiene automáticamente los índices por nuestra parte, por lo que para iniciar una instancia de nuestro almacén de datos que guarde las entidades como la estructura superior con los índices dados, se escribiría lo siguiente (en Python):

user_id_index = friendfeed.datastore.Index(
    table="index_user_id", properties=["user_id"], shard_on="user_id")
datastore = friendfeed.datastore.DataStore(
    mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
    indexes=[user_id_index])

new_entity = {
    "id": binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"),
    "user_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
    "feed_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
    "title": u"We just launched a new backend system for FriendFeed!",
    "link": u"http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
    "published": 1235697046,
    "updated": 1235697046,
}
datastore.put(new_entity)
entity = datastore.get(binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"))
entity = user_id_index.get_all(datastore, user_id=binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"))

La clase Index de arriba busca la propiedad user_id en todas las entidades y automáticamente mantiene el índice en la tabla index_user_id. Ya que nuestra base de datos está fragmentada, el argumento shard_on se utiliza para determinar qué fragmento contiene al índice (en este caso sería entity["user_id"] % num_shards).

Puedes realizar una consulta sobre índice usando una instancia de índice (ver user_id_index.get_all arriba). El código del almacén de datos hace el "join" entre la tabla index_user_id y la tabla entities en Python, consultando primero las tablas index_user_id en todos los fragmentos para obtener una lista de los IDs de entidades y entonces extrayendo los IDs de esas entidades de la tabla de entities.

Para añadir un nuevo índice, p.e. en la propiedad link, crearíamos la siguiente tabla:

CREATE TABLE index_link (
    link VARCHAR(735) NOT NULL,
    entity_id BINARY(16) NOT NULL UNIQUE,
    PRIMARY KEY (link, entity_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Cambiaríamos nuestro código de inicialización para incluir este nuevo índice:

user_id_index = friendfeed.datastore.Index(
    table="index_user_id", properties=["user_id"], shard_on="user_id")
link_index = friendfeed.datastore.Index(
    table="index_link", properties=["link"], shard_on="link")
datastore = friendfeed.datastore.DataStore(
    mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
    indexes=[user_id_index, link_index])

Y podríamos popular el índice asíncronamente (incluso mientras se sirve tráfico en vivo) con:

/rundatastorecleaner.py --index=index_link

Consistencia y atomicidad


Ya que nuestra base de datos está fragmentada, y los índices para cualquier entidad pueden ser almacenados en diferentes fragmentos de las mismas entidades, la consistencia es un asunto a resolver. ¿Qué pasa si el proceso termina inesperadamente antes de haber escrito a todas las tablas índice?

Construir un protocolo de transacciones resultaba atractivo para los ingenieros más ambiciosos de FriendFeed, pero deseábamos mantener el sistema lo más simple posible. Decidimos relajar restricciones de forma que:

  • La bolsa de propiedades almacenada en la tabla entities es canónica
  • Los índices podrían no reflejar el estado actual.

Consecuentemente, escribimos una nueva entidad en la base de datos siguiendo los siguientes pasos:

  1. Escribe la entidad en la tabla entities usando las propiedades ACID de InnoDB
  2. Escribir índices para todas las tablas índice en todos los fragmentos

Cuando leemos de las tablas de índice, ya sabemos que podrían no ser precisas (p.e. podrían reflejar los antiguos valores si la escritura no ha terminado el paso 2). Para asegurar que no devolvemos entidades inválidas basadas en las restricciones anteriores, usamos tablas índice para determinar qué entidades leer, pero reaplicamos los filtros de la consulta por nuestra cuenta en lugar de confiar en la integridad de los índices:

  1. Lee la entity_id de todas las tablas índice basadas en la consulta
  2. Lee las entidades de la tabla entities a partir de los IDs obtenidos de las entidades
  3. Filtra (en Python) todas las entidades que no coincidan con las condiciones de la consulta basándose en los valores reales de las propiedades

Para asegurar que los índices no se pierden a perpetuidad y que las inconsistencias son corregidas eventualmente, el proceso "limpiador" que mencioné antes se ejecuta contínuamente sobre la tabla de entidades, escribiendo índices perdidos y limpiando los índices viejos e inválidos. Primero limpia entidades actualizadas recientemente, de forma que las inconsistencias en los índices se corrigen bastante rápidamente en la práctica (en un par de segundos).

Rendimiento


Hemos optimizado un poco nuestros índices primarios en este nuevo sistema, y estamos bastante complacidos con los resultados. Aquí hay un gráfico de la latencia de visión de páginas de FriendFeed durante el mes pasado (lanzamos el nuevo sistema hace un par de días, lo que explica la dramática caída):



En particular, la latencia de nuestro sistema es ahora remarcablemente estable, incluso durante las horas punta de mitad del día. Aquí hay un gráfico de la latencia de visión de páginas de FriendFeed de las últimas 24 horas:



Compárese con la de hace una semana:



El sistema ha sido realmente fácil de implementar. Ya hemos cambiado los índices un par de veces desde que desplegamos el sistema, y hemos empezado a convertir algunas de nuestras mayores tablas MySQL para utilizar este nuevo esquema de forma que podamos cambiar su estructura con más libertad en el futuro.

Publicar un comentario en la entrada

Últimos links en indiza.com