Etiquetas

, ,

Para ir al grano y que no perdáis el tiempo los que no estéis interesados en esta frikada de optimización de consultas a base de datos [MySQL]: el código siguiente es el código SQL que selecciona y obtiene los datos de los enlaces que aparece en la portada del Menéame.

SELECT link_id AS id, link_author AS author, link_blog AS blog, /* muchas columnas adicionales del objeto */
	FROM links
	INNER JOIN users ON (user_id = link_author)
	LEFT JOIN (categories AS cat, categories AS meta) ON (cat.category_id = links.link_category AND meta.category_id = cat.category_parent)
	LEFT JOIN votes ON (link_date > @enabled_votes AND vote_type='links' AND vote_link_id = links.link_id AND vote_user_id = @user_id AND ( @user_id > 0  OR vote_ip_int = @ip_int ) )
	LEFT JOIN favorites ON (@user_id > 0 AND favorite_user_id =  @user_id and favorite_type = 'link' AND favorite_link_id = links.link_id)
	LEFT JOIN link_clicks AS clicks ON (clicks.id = links.link_id)
	INNER JOIN (SELECT link_id FROM links $from WHERE $where $order_by LIMIT $offset,$page_size) AS id USING (link_id)

Nota: Las variables que comienzan con $, como $from o $where son variables asignadas desde el PHP para definir las condiciones (publicadas o pendientes, ordenadas por fecha o por karma, etc). Las que comienzan con @, como @user_id o @ip_int, son variables de sesión del MySQL.

La pregunta es ¿por qué tan complicado? ¿por qué esos LEFT e INNER JOIN en vez de consultas más simples? Por eficiencia, y también comodidad, como intentaré explicar en este apunte. Creo que sería muy complicado encontrar una consulta más eficiente que la anterior para la base de datos del Menéame. Pero no ha sido una idea que se me ocurrió de un día para otro, ni siquiera en semanas. Fue la evolución y el resultado de 5 años de experiencia directa, a veces dolorsa, y de aprender muchas cosas en el proceso. Experimenté en carne propia la carencia que tenemos los programadores sobre la arquitectura y modo de trabajo de las bases de datos. Es un mundo completamente diferente, se necesitan miles de horas para dominarlo mínimamente [1], aunque tengas muchos años de experiencia como programador.

[1] Y así acabamos matando mosquitos a mosquetazos, i.e. recurriendo a soluciones “NoSql” sin siquiera darnos cuenta que mejor es la escopeta de al lado, que está bien probada.

Estructura de un enlace

Vamos a ver cuál es la estructura básica de un enlace:

Estructura de un enlace en Menéame

Además de la tabla links (línea 1-2) (tiene casi un millón de filas), para poder mostrar todos los datos hacen falta datos de otras 5 tablas:

  1. Usuario (azul) de la tabla users (línea 3). Es obligatorio (i.e. clave foránea). La tabla tiene más de 200.000 filas.
  2. Metacategoría (naranja) y categoría (marrón) (línea 4). En la tabla links se almacena la categoría obtenida (en este caso “política”) de la tabla categories. De la misma tabla se obtiene la metacategoría (actualidad). La categoría es obligatoria, salvo cuando el enlace está en proceso de edición inicial (cuando está siendo creado por el usuario). La tabla es pequeña, unas pocas decenas (pueden verse todas las entradas si se espande la lista en el signo “+” al lado de la palabra “todas” en la parte superior de la portada de Menéame).
  3. Voto del usuario actual (rojo) (línea 5). Se obtiene de la tabla votes, que tiene un índice compuesto: tipo, id de link, usuario [0 para anónimos, valor del voto [positivo o negativo] e IP desde la que se votó (almacenada en entero). El voto puede existir o no, para la gran mayoría de accesos no existe el voto (hay más o menos un millón de páginas impresas por día, que significa se muestran los datos de unos 10-12 millones de enlaces, pero sólo hay unos 50.000 votos a enlaces diarios). Los votos totales llegan a casi 100 millones, pero diariamente se “sumariza” esta tabla para mantenerla en unos 4 millones de filas ya que tiene varios “covering indices” que ocupan más espacio que los datos.
  4. Favorito (amarillo), de la tabla favorites (línea 6), indica si el  usuario actual marcó esa noticia como favorita. Esta tabla tiene algo más de 300.000 filas.
  5. Contador de clics (verde) al enlace, de la tabla link_clicks (línea 7). No todos los enlaces tienen una entrada correspondiente de clics, bien porque acaba de ser enviado y nadie ha hecho clic todavía, o porque es un enlace antiguo, cuando no existía todavía el contador.

Supongo que muchos ya os habéis dado cuenta más o menos las optimizaciones que se hicieron, pero falta por aclarar la necesidad (y ventaja) de usar las variables de sesión, y el porqué del INNER JOIN (línea 8) junto con ese sub-select. Ya entenderéis las razones más adelante.

Object-Relational Mapping

La arquitectura de Menéame comenzó como un Active Record (una tabla por objeto), luego evolucionó a algo más similar al patrón Object Relational Mapping para sus clases más importantes Link, CommentPost, User, etc. Cada una de estas clases implementa método de instancia read() y store() para leer y almacenar los datos de una instancia en la base de datos.

El acceso a la base de datos se hace a través de una pequeña (y muy eficiente) capa de abstracción que oculta detalles de la interfaz PHP con MySQL y sobre todo porque facilita mucho la programación ya que permite trabajar siempre con objetos, arrays y diccionarios (además de los más modernos iteradores, como veremos más adelante).

En las primeras versiones del Menéame en el read() se implementaba un SQL bastante obvio y sencillo para consultar a la base de datos. Por ejemplo el read() de la clase Link de hace unos 5 años (sí, ahora me avergüenzo de mi propio código, supongo que eso es bueno, aprendí mucho en estos años):

    function read($key='id') {
        global $db, $current_user;
        switch ($key)  {
            case 'id':
                $cond = "link_id = $this->id";
            // Otros case
            default:
                $cond = "link_id = $this->id";
        }
        if(($link = $db->get_row("SELECT links.*, UNIX_TIMESTAMP(link_date) as link_ts,  UNIX_TIMESTAMP(link_sent_date) as sent_ts, UNIX_TIMESTAMP(link_published_date) as published_ts, UNIX_TIMESTAMP(link_modified) as modified_ts, users.user_login, users.user_email, users.user_avatar, users.user_karma, users.user_level, users.user_adcode FROM links, users WHERE $cond AND user_id=link_author"))) {
            $this->id=$link->link_id;
            $this->author=$link->link_author;
            $this->username=$link->user_login;
            // Asignación de otros campos del objeto
            if ($this->category > 0) {
                $meta_info = $db->get_row("SELECT categories.category_name, categories.category_uri, meta.category_name as meta_name, meta.category_uri as meta_uri FROM categories, categories as meta  WHERE categories.category_id = $this->category AND meta.category_id = categories.category_parent");
                $this->category_name=$meta_info->category_name;
                $this->meta_name=$meta_info->meta_name;
                $this->meta_uri=$meta_info->meta_uri;
            }
            $this->read = true;
            return true;
        }
        $this->read = false;
        return false;
    }

Es evidente en el código anterior uno de los problemas: se hacen dos consultas diferentes (línea 10 y 16) a la base de datos para leer los datos (todavía incompletos) de una instancia de la clase Link. Nunca es buena idea hacer diferentes consultas, no sólo por la latencia de la red (el servidor de base de datos es remoto), sino también porque el parser y optimizador se tienen que ejecutar por cada consulta, y luego hay que pasar otra vez por la capa de control de concurrencia y transacciones. Optimizar esta parte fue sencillo, fue simplemente agregar un LEFT JOIN combinado con un INNER JOIN idéntico al de la línea 4 del SQL del primer código:

Pero eso no acaba allí. Hay todavía muchas más consultas adicionales que ahora ya no existen. El siguiente es el pseudocódigo (en realidad en Python, para aprovechar el resaltado de sintaxis de WordPress) para generar la portada de menéame (15 enlaces por página):

links = db.get_column("SELECT link_id FROM links WHERE link_status = 'published' ORDER BY link_date DESC LIMIT Y,Y")
for id in links:
    link = new Link
    link.read(id)
    link.print_summary()

Primero se obtienen en un array los IDs de los enlaces a mostrar, y luego en un bucle se lee cada enlace y se muestra sus datos (el que se ve en la captura de pantalla). La llamada a la función read() agrega una consulta adicional por cada enlace que se muestra (ya llevamos 15 más). Aún es peor, la función print_summary() tiene que verificar si el usuario había votado a la noticia (incluso si es usuario anónimo no registrado), si el usuario lo marcó como favorito, etc. Es decir, unas cuantas consultas más por cada enlace mostrado, lo que significa casi 80 consultas para la página principal, y sólo para información de los enlaces.

El MySQL no tenía demasiado problemas, teníamos una media de 1.500 consultas/segundo (unas 5.000 a 10.000 por segundo en horarios pico) con una consumo máximo de CPU del 40%. Pero empezamos a notar una latencia importante cuando se mostraba una noticia con un número importante de comentarios (se muestran has 100 comentarios por página). Esto ocurría porque la estructura era muy similar, para la página de comentarios se ejecutaba el siguiente código para mostrar los comentarios:

comments = db.get_column("SELECT comment_id FROM comments WHERE comment_link_id = LINK_ID ORDER BY comment_order ASC LIMIT X,Y")
for id in comments:
    comment = new Comment
    comment.read(id)
    comment.print_summary()

De nuevo, la función print_summary() tiene que hacer dos consultas adicionales (voto del usuario y si está marcado como favorito). Con 100 comentarios significaban 300 consultas… para mostrar sólo los comentarios. Era un problema que había que solucionar, y la solución es exactamente igual a la de los enlaces.

Convertir a una sóla consulta por instancia

La idea fue hacer una función de clase “factory” que unificase todas las consultas en una sólo, com los LEFT JOINS. Así definí una constante de clase con el SQL básico para recuperar los datos de la instancia (veréis que el SQL mostrado es el mismo que el mostrado en el primer SQL de este apunte):

// sql fields to build an object from mysql
	const SQL = " link_id as id, link_author as author, link_blog as blog, link_status as status, link_votes as votes, link_negatives as negatives, link_anonymous as anonymous, link_votes_avg as votes_avg, link_votes + link_anonymous as total_votes, link_comments as comments, link_karma as karma, link_randkey as randkey, link_category as category, link_url as url, link_uri as uri, link_url_title as title, link_title as title, link_tags as tags, link_content as content, UNIX_TIMESTAMP(link_date) as date,  UNIX_TIMESTAMP(link_sent_date) as sent_date, UNIX_TIMESTAMP(link_published_date) as published_date, UNIX_TIMESTAMP(link_modified) as modified, link_content_type as content_type, link_ip as ip, link_thumb_status as thumb_status, link_thumb_x as thumb_x, link_thumb_y as thumb_y, link_thumb as thumb, user_login as username, user_email as email, user_avatar as avatar, user_karma as user_karma, user_level as user_level, user_adcode, cat.category_name as category_name, cat.category_uri as category_uri, meta.category_id as meta_id, meta.category_name as meta_name, meta.category_uri as meta_uri, favorite_link_id as favorite, clicks.counter as clicks, votes.vote_value as voted FROM links
	INNER JOIN users on (user_id = link_author)
	LEFT JOIN (categories as cat, categories as meta) on (cat.category_id = links.link_category AND meta.category_id = cat.category_parent)
	LEFT JOIN votes ON (link_date > @enabled_votes and vote_type='links' and vote_link_id = links.link_id and vote_user_id = @user_id and ( @user_id > 0  OR vote_ip_int = @ip_int ) )
	LEFT JOIN favorites ON (@user_id > 0 and favorite_user_id =  @user_id and favorite_type = 'link' and favorite_link_id = links.link_id)
	LEFT JOIN link_clicks as clicks on (clicks.id = links.link_id) ";

Luego implementa la factory function Link::from_db() que retorna un instancia después de leer los datos de la base de datos con una sola consulta:

	static function from_db($id, $key = 'id') {
		global $db;

		if ($key == 'uri') {
			$id = $db->escape($id);
			$selector = " link_uri = '$id' ";
		} else {
			$id = intval($id);
			$selector = " link_id = $id ";
		}
		if(($object = $db->get_object("SELECT".Link::SQL."WHERE $selector", 'Link'))) {
			return $object;
		}
		return false;
	}

Supongo que está clara la idea, Link::SQL es una constante que puede ser usado en cualquier sitio (se usa en varios) y que define la consulta básica. Luego es responsabilidad del que la use de completarla con las condiciones necesarias en el “WHERE” (línea 12).

Pero había unos temas a tener en cuenta:

  • El control “rápido” de votos (i.e. para visualizar) es diferente para usuarios (por id de usuario) que para lo anónimos (por la IP).
  • Hacen falta los datos de código de usuario y/o de la dirección IP para hacer los controles anteriores.
  • No tiene sentido controlar el voto si los votos ya están cerrados, en estos casos, por eficiencia, es mejor no consultar a la tabla de votos.
  • No tiene sentido verificar en la tabla de favoritos si el usuario es anónimo (sólo los registrados puedes marca favoritos, por razones obvias).

Para solucionarlo de forma simple y elegante se usan las variables de instancia (@user_id, @ip_int y @enabled_votes). Estas variables se inicializan con un sólo “SET” casi al principio, en libs/login.php justo después de verificar si es usuario autentificado y que luego servirán para decenas de consultas:

$db->query("
    set @user_id = $this->user_id, @ip_int = ".$globals['user_ip_int'].
     ", @ip_int = ".$globals['user_ip_int'].
     ", @enabled_votes = date_sub(now(), interval ". intval($globals['time_enabled_votes']/3600). " hour)");

Si os fijáis como se usan y por su posición, las condiciones sobre estas variables “truncan” inmediatamente consultas innecesarias a otras tablas. Por ejemplo, en la línea 5 del código superior se evita la consulta a la tabla de votos si ya no están habilitados. En la línea 6 se evita la consulta a la tabla de favoritos si el usuario no está autentificado.

Con estas optimizaciones logramos reducir mucho el tiempo de latencia, y el número de consultas a la base de datos. Bajamos de más de 1.600/segundo a 1.200 por segundo. Ahora la función print_summary() ya no tiene que hacer consultas adicionales, todo ya está almacenado en la instancia al momento de su creación o lectura.

Iteradores

Pero todavía me quedaba algo pendiente que no sabía como encarar hasta hace pocos días que se me aclararon las ideas. Quería eliminar las consultas por cada objeto que se leía de la base de datos. Así, en vez de primero obtener los IDs de los enlaces que se mostrarán, y luego hacer la lectura por cada uno de ellos, quería implementar un iterador PHP que sea capaz de usar la misma constante Link::SQL (o Comment::SQL, Post::SQL)  para poder interar sobre cada objeto como si fuese una lista (similar a los cursores).

Es decir, quería hacer algo como:

$links = $db->object_iterator("SELECT ".Link::SQL."etc. etc.", "Link");
foreach ($links as $link) {
    $link->print_summary();
}

El objetivo era sencillo, minimizar aún más las consultas y latencia. El SQL para leer cada objeto ya es bastante complejo, lo que hace aumentar tiempo y consumo de CPU del servidor de base de datos (por las mismas razones que antes, el parser, el optimizador, etc.). Así implementé dos clases nuevas en la abstracción de la base de datos (pueden verse a partir de la línea 222 del fichero):

class ObjectIterator implements Iterator {...}

class QueryResult extends MySQLi_Result implements IteratorAggregate {...}

Con estas clases implementé el método object_iterator() de la clase RGDB (línea 127 del mismo fichero), que básicamente hace:

	if ($this->real_query($query)) {
		if ($is_select && $this->field_count) {
			return new QueryResult($this, $class);

Así, el código para obtener los enlaces del index.php –y que genera el código SQL del principio– se hace simplemente:

// We use a "INNER JOIN" in order to avoid "order by" with filesorting.
$links = $db->object_iterator("SELECT".Link::SQL."INNER JOIN (SELECT link_id FROM links $from WHERE $where $order_by LIMIT $offset,$page_size) as id USING (link_id)", "Link");
if ($links) {
	foreach($links as $link) {
		$link->print_summary();
	}
}

La pregunta del millón es ¿por qué ese INNER JOIN con un sub SELECT en vez de hacer algo más sencillo como?:

$links = $db->object_iterator("SELECT".Link::SQL."WHERE $where $order_by LIMIT $offset,$page_size", "Link");

La respuesta está en el comentario del código usado: para evitar el uso de “filesorting”, es decir que el MySQL ordene los resultados en memoria, en vez de obtenerlo directamente ordenados desde el índice.

Si recordáis el pseudocódigo de más arriba, antes se seleccionabas primero los IDs ya ordenados:

SELECT link_id FROM links WHERE link_status = 'published' ORDER BY link_date DESC LIMIT Y,Y

En este caso el MySQL usa el índice existente (link_status, link_date) para obtener los resultados ordenados directamente. Pero en esta consulta más compleja, con varios LEFT e INNER JOINs es incapaz de usar el mismo índice. La solución es “empotrar” la consulta anterior para que retorne ya los IDs ordenados, eso es exactamente lo que se hace en el sub SELECT. Con ello logramos enviar un sólo SQL para obtener todos los enlaces (y toda su información) para generar toda la página índice.

Super eficiente, y bonito ¿o no?

Resultados

  • Hemos logrado reducir el tiempo de generación de páginas notablemente. El tiempo de reloj completo para generar toda la página principal del Menéame es de media 0.02 seg, 0.03 seg con la compresión on-the-fly incluida. Antes llegaba a 2 décimas de segundo (con mucha más variabilidad, era más sensible a las latencias de la red de Amazon).
  • Las instancias web de Menéame son las “small”, con sistema de 32 bits. Pero son capaces de generar más de 200 páginas índices por segundo (entre 180 y 230 con el Apache Benchmark y con concurrencia > 5). Antes generaban hasta 40.
  • A pesar del aumento de tráfico de las últimas semanas (+10% en enero respecto a diciembre), el consumo de CPU del servidor de base de datos raramente llega al 30% (antes superaba el 40% durante horas pico).
  • El número de consultas a la base de datos se redujo notablemente. Antes nos daba una media de 1.600, luego 1.200, ahora estamos (después de haber reiniciado por actualización de seguridad hace pocos días) a 833 por segundo:
    Uptime: 5 days 17 hours 49 min 45 sec
    Threads: 6  Questions: 413714009  Slow queries: 1885 Opens: 1045  Flush tables: 1
    Open tables: 837  Queries per second avg: 833.789

Moraleja

Seguramente te pasa como a mi: creía conocer a esas bestias serviles de base de datos relacionales. Lo más probable es que a menos que tengas años de experiencia en caso complejos, no tengas idea de cómo obtener los mejores resultados. Así que la próxima vez, antes de proponer usar una solución “NoSQL” para tu “proyectito” porque una relacional no aguantaría, piénsalo un millón de veces y lee algunos libros imprescindibles [por ejemplo 1 ó 2]. Posiblemente no estés haciendo lo mejor, y seguro, no, segurísimo, que con una NoSql no podrás tener un código tan “elegante” y breve como:

$links = $db->object_iterator("...");
if ($links) {
	foreach($links as $link) {
		$link->print_summary();
	}
}

que sea capaz de hacer tantas cosas, y tan eficientemente (a pesar el PHP) a partir de una única consulta a la base de datos

Extra

Si usas un framework moderno, felicidades, ojalá hubiesen existido cuando comencé a programar el Menéame. Pero no te creas que generarán SQL y código muy eficientes y adaptados a tu problema. Si piensas que la base de datos, o los SQL, podrían ser un cuello de botella, asegúrate que el framework es lo suficientemente flexible para que puedas optimizar las consultas.

¡Ah! antes de olvidarme, si tu modelo de datos de un proyecto web requiere de JOINS de más de 5 ó 6 tablas, la estás cagando. Un programa web no tiene nada que ver con un programa de gestión (ni con los requerimientos y limitaciones que te dan en las clases de bases de datos de la universidad).

Dicho está. Luego no estés babees como crío cada vez que alguien dice “NoSql” [2].

[2] Por supuesto que tiene su utilidad y a veces son imprescindibles, sobre todo si necesitas distribuir una gran cantidad datos, con una “consistencia relativa” y bajas latencias. Pero en el mundo hay muy pocos proyectos con Facebook, Twitter o Tuenti. La probabilidad que el tuyo tenga requerimientos similares es muy bajo, y si lo usas perderás las ventajas de usar relacionales (ACID, etc.) y la potencia del SQL. Sobre estos temas hablé y di más detalles en un podcast de hace pocos meses: Especial SysAdmin en “Kernel Panic” con Ricardo Galli.