google

(Diciembre 2013) DIT/UPM Diseo de sistemas distribuidos: Google

Diseo de Sistemas Distribuidos: Google

Alejandro Alonso

Dpto. Ing. de Sistemas Telemticos

Sistemas Operativos Distribuidos

!1


Tabla de contenidos1. Introduccin al caso de estudio

2. Arquitectura global y principios de diseo

3. Paradigmas de comunicacin

4. Servicios de almacenamiento de datos y coordinacin

5. Servicios de computacin distribuida

6. Resumen

!2


1. Introduccin al caso de estudioPresentacin de la infraestructura de Google

Es uno de los sistemas distribuidos ms complejos en uso Su infraestructura ha satisfecho requisitos exigentes: escalabilidad, rendimiento, fiabilidad y carcter abierto

Objetivo: organizar la informacin global y hacerla til y accesible universalmente

Funciones bsicas de google: Motor de bsqueda: dada una consulta, retorna una lista ordenadas de referencias Proveedor de servicios en la nube: Ofrece un conjunto de aplicaciones y servicios en la nube

!3


Motor de bsquedaDada una consulta, devuelve una lista ordenada de los resultados ms relevantes

Aspectos: rastreo, indexacin, clasificacin y arquitectura

Rastreo (crawling): localizar y obtener los contenidos de la web: Googlebot

Lee recursivamente un pgina web, obteniendo los enlaces y planificando nuevas operaciones de rastreo La frecuencia de las visitas depende de cuanto cambia Actualmente emplea un sistema basado en una infraestructura (Percolator) que admite actualizacin incremental de grandes conjuntos de datos

!4


Motor de bsquedaIndexacin: produce un ndice invertido ordenado de los contenidos Web

Relaciona palabras o recursos documentales con las posiciones donde se encuentran en las pginas Tambin mantiene un ndice de enlaces: qu pginas apuntan a una pgina web

Clasificacin: Importancia relativa de las pginas (PageRank) Importancia: depende del nmero de enlaces que la apuntan Tambin considera:

la importancia de los sitios que apuntan la posicin del enlace, el tamao de su letra o si est en

maysculas proximidad de las palabras de la consulta

!5


Motor de bsqueda: arquitectura originalPara comparar con la arquitectura actual

!6


Servicios en la nubeComputacin en la nube

Conjunto de aplicaciones y servicios de almacenamiento y cmputo, basados en Internet Suficientes para la muchos usuarios, que les evita disponer de almacenamiento o aplicaciones locales

Aplicaciones Google como servicios Aplicaciones web: tratan de reemplazar al software tradicional Programas ofimticos, calendarios, herramientas de colaboracin, etc.

Plataforma Google como un servicio: APIs de sistemas distribuidos, para desarrollo de aplicaciones Google AppEngine: Ofrece su infraestructura de sistemas distribuidos como un servicio en la nube.

!7


Ejemplos de aplicaciones de Google

!8


2. Arquitectura global y principios de diseo: Modelo Fsico

Principio bsico: usar un gran nmero de PCs comunes, para construir un entorno efectivo de cmputo y almacenamiento distribuido

PC con 2 TB de disco y 16 GB de DRAM Versin adaptada del ncleo de Linux

La arquitectura es tolerante a fallos El software es el origen de fallos. 20 mquinas en medias se re-arrancan diariamente por fallos de software El hardware produce 1/10 de los fallos. Alrededor del 3% fallan al ao. Normalmente, discos y DRAM

!9


Arquitectura fsicaLos PCs se organizan en racks de entre 40-80

Tiene un switch ethernet para conectividad interna y externa

Los racks se organizan en clusters Son la unidad de gestin principal Contiene al menos 30 racks Dos switches para conectividad con el exterior: redundancia

Los clusters estn en centros de datos de Google

La capacidad total de almacenamiento: rack de 80 PCs, en un cluster de 30: 4,9 petabytes Alrededor de 200 clusters Cifras totales no divulgadas

!10


Arquitectura fsica

!11


Arquitectura fsica

!12


Arquitectura fsica

!13


Principios de diseo: Requisitos fundamentales

Escalabilidad Gestionar ms informacin Resolver ms consultas Obtener mejores resultados

Fiabilidad Requisitos exigentes de disponibilidad Mecanismos de deteccin, redundancia y tolerancia a fallos

Rendimiento Proporcionar respuesta rpida, aumenta las consultas Respuesta: depende de los tiempo entre extremos

Apertura (Openness): Facilitar el desarrollo de nuevas aplicaciones

!14


Infraestructura de Google

!15


Infraestructura de Google

!16


Principios de diseoSimplicidad:

El software hace una cosa y la hace bien APIs tan sencillas como sea posible

Rendimiento Cada milisegundo cuenta Estimacin del rendimiento de un diseo:

Tamao de mensajes, acceso a disco, acceso a mutex, etc.

Pruebas Pruebas exhaustivas al software Trazas y bitcoras

!17


3. Paradigmas de comunicacin: Invocacin remota

Protocol buffers: Se usa para almacenamiento e invocacin Proporciona un mecanismo para especificar y serializar datos Neutral respecto al lenguaje y a la plataforma Simple y muy eficiente

Los mensajes se describen mediante un lenguaje Conjuntos de campos enumerados con identificador nico Se indica el tipo de la informacin Etiquetas para caracterizar los campos:Requerido, opcional o repetido

!18


Invocacin remota

!19


Invocacin remotaLa especificacin se compila

Se genera cdigo para manipular los mensajes: Funciones: getters, setters, borrado y comprobar existencia de campos, toString

Para los campos repetidos: Son una especie de arrays Funciones: longitud, obtener valor, cambiar valor, aadir, aadir conjunto de valores, borrar.

Formato ms sencillo que XML Adaptado a las necesidades de Google

No considera interoperabilidad No es autodefinido: los mensajes no incluyen metadatos

Ms rpido y conciso

!20


Invocacin remotaPermite expresar servicios remotos

!

!

El compilador produce un interfaz abstractos y un suplente (stub) para hacer invocaciones remotas

Agnstico respecto al protocolo de RPC subyacente Interfaz abstracto: RpcChannel y RpcController

Slo un parmetro de entrada y uno de salida Facilita extensibilidad y evolucin del software Pone la complejidad en los datos, en lugar de en la interfaz

service SearchService { rpc Search (RequestType) returns (ResponseType)}

!21


Editor/SuscriptorDiseminacin de eventos rpidamente y con garanta de fiabilidad un gran nmero de receptores

El sistema est basado en temas Ms eficiente que si estuviera basado en contenidos, aunque tiene menos poder expresivo Un evento: cabecera, conjunto de palabras clave e informacin Suscripcin: indica un tema y un filtro sobre las palabras clave

Canales Se proporcionan canales asociados a temas Flujos de datos estticos, con alta transferencia de eventos (1Mbps) Si un canal genera poco flujo, se incluye en otro

!22


Editor/SuscriptorSe implementa como un conjunto de rboles

La raz es el tema Las hojas son los suscriptores Los filtros se aplican lo ms cerca de la raz posible

Fiabilidad: se mantienen rboles redundantes: Al menos dos por tema

Calidad de servicio: se fuerza un lmite por usuario y por tema.

!23


Resumen de decisiones de diseo

!24



!25


4. Servicios de almacenamiento de datos y coordinacin

Sistema de ficheros distribuido (GFS) Acceso a datos no estructurados Optimizados para el estilo de datos y accesos requeridos por Google

Chubby: Cerrojos distribuidos para coordinacin distribuida Almacenamiento de pequeas cantidades de datos

Bigtable: Acceso a datos estructurados, en forma de tablas, que pueden ser indexadas de varias formas, como por fila o columna Base de datos distribuida que no proporciona todos los operadores relacionales

!26


Sistema de ficheros Google: RequisitosEjecuta sobre la plataforma de Google

Debe supervisar su funcionamiento y detectar, tolerar y recuperarse de fallos

Optimizarse para el tipo de uso dentro de Google El nmero de ficheros no es muy grande. Lo es su tamao El acceso es normalmente secuencial:

Lecturas secuenciales Escrituras secuenciales, que aaden informacin al final del fichero

Acceso concurrente de lectura y escritura

Requisitos de la infraestructura Google Es importante el ancho de banda, ms que la velocidad de respuesta

!27


Sistema de ficheros Google: InterfazInterfaz de un sistema de ficheros convencional

Espacio de nombres jerrquico. Ficheros identificados por el camino donde se encuentran.

Operaciones comunes: crear, borrar, abrir, cerrar, leer, escribir.

Operaciones especiales: Snapshot: Mecanismo eficiente para copiar un fichero o una estructura de directorios Record Append : Mltiples clientes aaden informacin al final del fichero.

!28


Arquitectura de GFSAlmacenamiento en trozos (chunks) de 64MB

GFS relaciona ficheros con trozos

Cada grupo (cluster) de GFS tiene un maestro y varios servidores de trozos

El maestro gestiona los metadatos de los ficheros: Espacio de nombres, control de acceso, los trozos que lo forman

!29


Arquitectura de GFSLos trozos estn replicados (por defecto, tres veces)

El maestro gestiona las rplicas

Los metadatos se almacenan en una bitcora para recuperacin de fallos

No se guarda la localizacin de rplicas, se consultan los trozos

El maestro es nico, pero la bitcora de operaciones se almacena en mquinas remotas

El maestro centralizado tiene una visin global del sistema de ficheros y optimiza su funcionamiento

El maestro informa del trozo (incluidas rplicas) donde estn los datos requeridos y el cliente accede a ellos:

!30


Arquitectura de GFSEl tamao de los trozos

Reduce la necesidad de contactar con el maestro Reduce la cantidad de metadatos a gestionar

Problemas; est en desarrollo un maestro distribuido El maestro se convierte en un cuello de botella El tamao de los metadatos de un maestro aumenta, y no es posible mantenerlos en memoria

Cache en el cliente: limitada a los metadatos del trozo. Se reducen problemas de coherencia

Cache en el servidor, slo la que realiza Linux

Bitcora: Se almacenan gran cantidad de informacin, que se supervisa para detectar fallos

!31


Consistencia en GFS

Necesaria consistencia entre rplicas: Se relaja la coherencia y aumenta el rendimiento

Funcionamiento: Cuando recibe un peticin de un cliente, el maestro le indica un primario y las rplicas restantes El cliente manda datos a las rplicas, que los guardan en buffer Cuando las rplicas reconocen la recepcin de los datos, ordena al primario la escritura, impone el orden y lo aplica localmente Luego, ordena a las rplicas el mismo orden y mandan reconocimiento Si todos correctos, el primario informa del xito de la operacin. En caso contrario, se informa del fallo. Entonces se vuelve a realizar la operacin. Si persiste el fallo, puede haber incoherencias

!32


ChubbyProporciona cerrojos distribuidos para sincronizar actividades en un entorno de gran escala y asncrono

Proporciona un sistema de ficheros, con almacenamiento fiable de ficheros pequeos

Seleccionar un primario entre un conjunto de rplicas

Se usa como un servicio de nombres en Google

El consenso distribuido es su funcionalidad ms importante

Hincapi en fiabilidad y disponibilidad, frente a rendimiento

!33


ChubbyCada entidad/objeto con datos es un fichero

Espacio de nombres: /ls/chubby_cell/directorio/../fichero

Una entidad combina un fichero y un cerrojo Se detect la utilidad de aadir informacin al cerrojo

Las operaciones sobre ficheros Se transfiere el fichero completo Se realizan de forma atmica

Los cerrojos son informativos El sistema no bloquea el acceso a los datos asociados Los programadores deben usarlos de forma adecuada

!34


Interfaz de Chubby

!35


Funciones de ChubbyEleccin de un primario: eleccin sobre consenso

Los candidatos tratan de adquirir un cerrojo asociado a la eleccin El que tiene xito es el primero. Escribe en el fichero su identidad Seleccin de un primario, basada en servicio de consenso

Proporciona un servicio sencillo de eventos Pueden ser cambios en un fichero, manejador invlido, etc. Se ejecuta una funcin asncronamente (callback)

Otras caractersticas No permite mover un fichero, ni enlaces simblicos Mantiene pocos metadatos

!36


Arquitectura de ChubbyLos componentes fundamentales:

Cliente, que emplea una biblioteca para llamadas Una clula Chubby Se comunican mediante RPC

La clula Chubby Compuesta por cinco rplicas

Al menos tres deben estar operativas

Las rplicas se sitan en diferentes racks La clula suele estar en el mismo cluster Las rplicas mantienen copias de una BD sencilla

Contienen entidades chubby: cerrojos/ficheros Slo el maestro inicia operaciones de lectura/escritura de la BD Se emplea un protocolo de consenso

!37


Arquitectura de Chubby

!38


Arquitectura de ChubbyLos clientes buscan al maestro y le envan peticiones

Si el maestro cae, las rplicas eligen otro

Se establece una sesin entre el cliente y el maestro Se mantiene mientras ambos estn operativos (KeepAlive) La biblioteca copia localmente los ficheros usados

Consistencia: para hacer una mutacin de un fichero: Se bloquea la operacin, hasta invalidar todas las caches Las caches nunca se modifican directamente

!39


Consistencia entre las rplicasBasada en Paxos: familia de protocolos para consenso distribuido para sistemas asncronos

No es posible garantizar consistencia Puede que no termine

Caractersticas del entorno Las rplicas operan a diferente velocidad y pueden fallar Tienen acceso a almacenamiento estable y persistente, que sobrevive a los fallos Los mensajes, se pueden perder, reordenar o duplicar. Se envan sin corrupcin y se puede retrasar un tiempo arbitrario

Acuerdo: rplicas guardan el mismo valor en bitcoras La mayora de las rplicas funcionan el tiempo suficiente y con suficiente estabilidad de la red

!40


Consistencia entre las rplicasPropiedades de vivacidad:

Si hay una mayora estable de servidores, si uno del conjunto inicia una actualizacin, algunos miembros del mismo ejecutarn la operacin en algn momento Si un servidor s ejecuta una operacin y existe un conjunto de servidores con s y r, si no hay fallos, entonces r ejecutar la actualizacin

Caractersticas del algoritmo: El algoritmo debe elegir un coordinador, que puede fallar Los mensajes llevan el nmero de secuencia del coordinador t En la eleccin, se enva un nmero nico mayor que el observado: s | s mod n = ir y s es el menor valor > t

n: nmero de rplicas ir: identificador de la rplica, 0


Consistencia entre las rplicas

Caractersticas del algoritmo: Las rplicas responden: Prometen seguir a la rplica, pues no han observado un

nmero mayor Ack negativo, no votan por este coordinador e indican el

mayor nmero observado Coordinador: la rplica con ms promesas recibidas (quorum) El coordinador elige un valor y manda el valor al quorum Las rplicas aceptan el valor y mandan un ack Si la mayora de las rplicas aceptan, se enva confirma el valor Si no el coordinador abandona la propuesta y se inicia eleccin

Es necesario acuerdo en una secuencia de valores Multi-Paxos: se elige un coordinador para un conjunto de valores

!42



!43



!44



!45


BigtableSistema de almacenamiento distribuido para grandes volmenes de datos estructurados

Gestiona el almacenamiento tolerante a fallos, creacin, borrado y gestin de grandes tablas Google Analytics almacena informacin de enlaces visitados asociados con usuarios que visitan un sitio en una tabla (200TB) y resume la informacin analizada en otra (20TB)

Las bases de datos relacionales no sirven No proporcionan buen rendimiento y escalabilidad

Bigtable Sigue el modelo de tablas Con una interfaz muy sencilla, adaptada a las necesidades de Google

!46


Interfaz de BigtableAcceso indexado por fila, columna y marca de tiempo:

Filas: Identificadas por una clave, que es una tira de caracteres de hasta

64KB Ej. direccin de una web Ordenadas lexicogrficamente por la clave Filas relacionadas se almacenan juntas Los accesos a las filas son atmicos

Columnas: Nombre de columna: Nombre de familia:calificador Enfoque: pocas familias y muchas columnas Ej. informacin de la direccin de web: enlaces, lenguajes, etc

Marca de tiempo Una celda tiene varias versiones, indexadas con este parmetro Puede ser tiempo real o tiempo lgico

!47


Interfaz de Bigtable

!48


Interfaz de BigtableProporciona funciones, como

Creacin y borrado de tablas Creacin y borrado de familias de columnas Acceso a datos de una fila Escritura y borrado de datos de las celdas Mutaciones atmicas en filas, como acceso, escritura y borrado de datos Iteracin sobre familias de columnas, incluyendo el uso de expresiones regulares Asociar metadatos con tablas y familias de columnas, como listas de acceso

!49


Arquitectura de BigtableSe divide en tabletas, que son un conjunto de filas

Relaciona las tabletas con ficheros en GFS Garantiza equilibrado de la carga entre los servidores

Cluster: una instancia de Bigtable Almacena y gestiona un conjunto de tabletas Arquitectura similar a GFS: biblioteca, maestro y servidores de tabletas

!50


Almacenamiento de datos en BigtableEl almacenamiento de tablas en GFS:

La tabla se dividen en tabletas, por filas, con un tamao medio 100-200 MB Una tableta se representa mediante

conjunto de ficheros que almacenan datos en formato SSTable otras estructuras de almacenamiento para las bitcoras

Relacin entre tabletas y SSTables mediante ndice jerrquico

SSTable: mapa ordenado e inmutable de pares (clave, valor) operaciones para acceso y gestin eficiente incluye un ndice, que se carga en memoria inicialmente los cambios se escriben en una bitcora en GFS las lecturas se hacen combinando los datos en SSTable y en la

!51


Almacenamiento de datos en Bigtable

!52


Almacenamiento de datos en BigtableLa relacin entre tabletas y ficheros en memoria se gestiona en una estructura en rbol, donde se almacenan metadatos y la situacin de los datos de las tabletas

!53


Supervisin del funcionamientoUso interesante de Chubby:

Mantiene un directorio en Chubby con ficheros representado los servidores de tabletas Los servidores obtienen un cerrojo sobre el fichero Su existencia indica la correcta operacin del servidor Operacin del servidor de tableta

Los servidores supervisan su cerrojo. Si se pierde, se paran Intentan adquirir el cerrojo. Si el fichero se borra, terminan Si el servidor debe terminar, libera el cerrojo

Operacin del maestro El maestro consulta el valor del cerrojo peridicamente Si est liberado, entonces intenta adquirirlo Si tiene xito, el problema est en el servidor Borra el fichero y asigna la tableta a otro servidor

!54


Equilibrado de cargaEl maestro tiene una visin global del sistema

Servidores existentes, asignacin de tabletas del cluster Asigna tabletas a servidores, segn su carga

El maestro tiene otro cerrojo Si se pierde, el maestro se para El sistema sigue operando, aunque sin funciones de control Al crear un nuevo maestro:

Se asegura de que es el nico Recupera informacin de estado de los servidores

!55



!56


5. Servicios de computacin distribuida: MapReduce

Modelo sencillo de programacin para el desarrollo de aplicaciones paralelas y distribuidas

Fragmentacin de datos de entrada y anlisis y procesamiento de estos fragmentos en paralelo Oculta los detalles de este enfoque al programador

Interfaz de MapReduce: Basado en el siguiente patrn de funcionamiento:

Partir los datos de entrada en un conjunto de trozos (chunks) Procesamiento paralelo de los trozos y generacin de un resultado

intermedio Combinacin de los resultados intermedios

Expresin en forma de dos funciones: Map: Parte de un conjunto de pares (clave, valor) y genera un

conjunto intermedio de pares del mismo tipo

!57


Ejemplos del uso de MapReduce

!58


Arquitectura de MapReduceBiblioteca que permite al programador centrarse en las funciones Map y Reduce

Se crean un conjunto de trabajadores Un maestro para supervisar

!59


Tolerancia de FallosGarantiza el determinismo de las operaciones

El maestro comprueba si los trabajadores funcionan. Si fallo: Map: Se reprograma la operacin. Los resultados no estarn

disponibles, pues se escriben en almacenamiento local Reduce: Se comprueba si se complet. Entonces, se usan los datos

que estarn en GFS. En caso contrario, se vuelve a realizar

Las salidas de los trabajadores se escriben atmicamente

Gestin de trabajadores lentos Ocurre con cierta frecuencia (a veces problemas hardware) Cuanto se est completando una operacin, lanza trabajadores nuevos como respaldo a los lentos

!60


SawzallLenguaje de programacin interpretado para realizar anlisis de datos paralelos sobre grandes conjuntos de datos en entornos altamente distribuidos

Tamao de programas, menor que con MapReduce Esquema de cmputo dado y supone:

La ejecucin de filtros y agregadores es conmutativa respecto a los registros. Se pueden ejecutar en cualquier orden

Las operaciones de agregacin son asociativas

!61


SawzallSe proporcionan un conjunto de agregadores por defecto:

sumar, crear una coleccin, valor ms comn, etc

Ejemplo

count: table sum of int;total: table sum of float;!x: float = input;emit count



!63


6. ResumenGoogle proporciona un motor de bsqueda, aplicaciones y una plataforma de cmputo en la nube

Infraestructura Google Conjunto de componentes y modelo fsico para el desarrollo de aplicaciones en sistemas masivamente distribuidos Priman soluciones adaptadas a las necesidades de Google. Requisitos: escalabilidad, rendimiento, fiabilidad, apertura Entorno en continua evolucin

!64


BibliografaCoulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design, Edicin 5, Addison-Wesley 2012, captulo 21

Este captulo incluye referencias artculos originales de los desarrolladores de Google

!65

google

Documents