PDF de programación - Sistema de ficheros GFS (Google File System) - Sistemas Distribuidos

Sistemas Distribuidos

Sistema de ficheros GFS
Sistema de ficheros GFS
(Google File System)
(Google File System)

Caldo de cultivo (≈2000)

• Almacenamiento de datos en Google siempre ha sido crítico
• ¿Usar SFP ya existente?

– NO: por características de plataforma y de aplicaciones previstas

• Plataforma basada en commodity HW

– Fallos HW/SW son norma y no excepción: Tolerancia a fallos SW
– No altas prestaciones pero gran paralelismo (>1000 nodos almacen.)

• 1 op. no es muy rápida pero se pueden hacer muchas en paralelo

• Perfil de aplicaciones previstas:

– Modo de operación batch (ancho de banda importa más que latencia)
– Millones de ficheros grandes (>100MB) y muy grandes (>1GB)
– Patrones de acceso típicos

• Escritor genera fichero completo inmutable
• Múltiples escritores añaden datos a un fichero en paralelo

– Con gran paralelismo, que no debe “estropear” el SF

Sistemas Distribuidos
2

Fernando Pérez Costoya

Por la especialización hacia el éxito

• ¿SFP especializado para aplicaciones/plataforma Google?
– Generalización de componentes clave en desarrollo informática
– Tensión entre especialización y generalización

• Google juega con ventaja

– Controla desarrollo de SFP y de aplicaciones
– SFP no ideado para usarse fuera de Google

• GFS → NFS (Not For Sale)

– Reparto de funcionalidad SFP y aplicaciones ajustable a discreción
– Puede imponer API, modelos coherencia,... “extraños”, no estándar

• Especialización: sí pero no demasiada

– Cobertura a mayoría de aplicaciones en Google
– Prueba de éxito: numerosos clones de libre distribución (Hadoop FS)

Sistemas Distribuidos
3

Fernando Pérez Costoya

Carga de trabajo prevista y API

• Perfil de aplicaciones previsto implica:

– Mayoría lecturas grandes (>1MB) y secuenciales
– Algunas lecturas pequeñas aleatorias
– Mayoría escrituras grandes (>1MB) y secuenciales

• Agregando datos y no sobrescribiendo (ficheros inmutables)

– Habitual escrituras pequeñas simultáneas al final del fichero
– Escrituras pequeñas aleatorias no previstas (pero soportadas)

• API, y modelo de coherencia, no estándar
– Afectará a productividad pero Google manda...
– Además de clásicas create, open, read, write, close y delete

• record append
• snapshot: Copia perezosa de fichero usando COW

Sistemas Distribuidos
4

Fernando Pérez Costoya

Una primera aproximación a GFS

• Receta para diseñar de una manera simple un nuevo SFP:

– Tomar como base un SF convencional (nodo maestro)
– Añadir: cada trozo de fichero almacenado en nodo distinto
• Nodo Linux convencional: trozo fichero GFS → fichero local
– Datos repartidos en discos: problema de fiabilidad → réplicas
– No usar caché en nodos cliente: no algoritmos de coherencia

• Carga típica de Google (≈read/write once) apoya esta simplificación
¡Único nodo maestro gestiona toda la información del SF!
– Ha primado sencillez sobre escalabilidad y tolerancia a fallos

•

• Con el tiempo lo pagaremos...

• Escalabilidad del SF: la del nodo maestro

– Minimizar trabajo y gasto de memoria de maestro
– Nodo maestro más potente y con más memoria
– ¡Ambas soluciones contrarias a la filosofía Google!

Sistemas Distribuidos
5

Fernando Pérez Costoya

Striping

• Trozos fichero repartidos entre nodos de almacenamiento (NA)
• Tamaño de trozo/chunk/stripe: ¡64MB!

– Respaldado por patrón típico de aplicaciones:

• Grandes ficheros accedidos con lecturas/escrituras grandes

• Ventajas:

– Clásicas: mejor aprovechamiento discos y red
– Escalabilidad del maestro:
• Menos gasto de memoria
• Menos trabajo

• Desventajas:

– Clásicas: relacionadas con fragmentación
– Menos paralelismo (fichero de 64MB en un único NA)

• Aunque fichero que representa chunk en NA puede tener tamaño justo

• Pero mayoría ficheros previstos son muy grandes

Sistemas Distribuidos
6

Fernando Pérez Costoya

El nodo maestro

• Gestiona el SF: todo excepto accesos a trozos en NA

– Además de información habitual de SF almacena:

• ChunkID de cada trozo de un fichero
• Datos asociados a ChunkID: localización actual de réplicas y nº versión

– Por escalabilidad, SF “peculiar”: en memoria y basado en prefijos

• SF en memoria

– Escalabilidad: bueno por rendimiento; malo por gasto de memoria
• Minimiza metainformación por fichero y por trozo (64 bits/trozo)
– Persistencia: log de ops. replicado con checkpoints periódicos

• checkpoints diseñados para poca sobrecarga y re-arranques rápidos

• SF basado en prefijos (similar a SO Sprite)
– No inodos, ni ficheros directorio, ni enlaces, ...
– Tabla hash: ruta → metadatos del fichero (usa compresión)

• Shadow master (maestro replicado): acceso sólo lectura a SF

Sistemas Distribuidos
7

Fernando Pérez Costoya

Lectura

1. C: fichero+nºtrozo→ M: ChunkID+versión+ubicación réplicas

C: guarda esa información hasta expiración o reapertura

•
• M: puede enviar información de trozos siguientes

2. C: Pide directamente trozo a réplica más cercana

• Minimiza intervención de maestro en operación de lectura

Sistemas Distribuidos
8

Fernando Pérez Costoya

Arquitectura + operación de lectura

Sistemas Distribuidos
9

The Google File System
Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung; SOSP ’03
Fernando Pérez Costoya

Escritura

•

•
1.

Debe mantener coherencia de réplicas (3 por defecto)
– Clientes deben leer misma información de réplicas
– Pero pueden estar mezclados datos de escrituras (no atómicas)
Uso de leases para controlar qué réplica actúa como primaria
(2) Igual que en lectura pero con info. propietario del lease
•

Si no lo hay, maestro lo selecciona en ese instante

3. Propagación de datos a réplicas (pipeline de datos)
4. Primaria: asigna orden a escritura, escribe y versión++
5. Secundaria: escribe siguiendo orden asignado por primario
6. Réplicas secundarias confirman escritura a primaria
7. Respuesta a cli.: error si falló alguna escritura → reintento
•

Escrituras multi-chunk no atómicas

Sistemas Distribuidos
10

Fernando Pérez Costoya

Operación de escritura

Sistemas Distribuidos
11

The Google File System
Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung; SOSP ’03
Fernando Pérez Costoya

Record append

• Agrega datos (registro) sin necesidad de sincronización
• Offset lo elige GFS
• Limitado a tamaños ≤ ¼ tamaño trozo
• Operación similar a escritura excepto en:

•

– Si registro no cabe en trozo, primaria/secundarias rellenan resto
Informan a cliente de que reintente en siguiente trozo
– Si cabe y no errores de escritura, similar a escritura
– Si error escritura en alguna réplica, cliente repite operación hasta OK

• Pero offset lo selecciona el primario

• Pero en cada reintento datos se escriben a continuación
• Contenido de réplicas distinto (escrituras erróneas, regs. duplicados)
• Sólo asegura que se ha escrito bien al menos una vez en cada réplica
¡Aplicación maneja huecos, registros erróneos y duplicados!

•

Sistemas Distribuidos
12

Fernando Pérez Costoya

Gestión de réplicas

• Maestro no mantiene info. persistente de ubicación de réplicas

– En arranque interroga a NA

• Maestro responsable de crear réplicas:

– Cuando se crea el trozo, política de ubicación guiada por
• Uso de discos y NA, y aspectos geográficos (rack-aware)

– Cuando nº réplicas debajo de umbral

• Por nodos caídos: Heartbeats entre maestro y NA con info. de estado
• Errores de disco: uso de checksums en NA

– Para equilibrar la carga entre NA

• Liberación de réplicas mediante garbage collection

– En Heartbeats maestro detecta réplicas huérfanas y obsoletas

Sistemas Distribuidos
13

Fernando Pérez Costoya

Finalmente se nos ha quedado pequeño

•

•

•

http://queue.acm.org/detail.cfm?id=1594206

Charla esclarecedora de Quinlan (Google) y McKusick (BSD)
–
Evolución de las necesidades
1. Almacenamiento de centenares TB a decenas de PB
2. Aumento proporcional de número de clientes
3. Nuevas aplicaciones que manejan ficheros pequeños
4. Nuevas aplicaciones donde latencia es importante
Problemas (relación directa/indirecta con maestro único)
1. Más metadatos en maestro: requiere más proceso y memoria
2. Maestro recibe más operaciones (open, close, ...)
3. Tamaño bloque (TB) menor (¿1MB?): más metadatos en maestro
4. GFS usa TB grande y agrupa todo tipo de ops. siempre que puede
– Además, tiempo de recuperación fallo maestro del orden de minutos

Sistemas Distribuidos
14

Fernando Pérez Costoya

GFS II/Colossus

• GFS entra en la era de los “múltiples maestros”

– Sharding de metadatos entre maestros
• GFS II/Colossus: reescritura completa
• Todavía poca información: se han filtrado aspectos adicionales

– Tamaño de bloque 1MB
– Tiempo de recuperación de pocos segundos
– Uso de códigos correctores vs. replicación
– Más especialización: soporte de Google Caffeine
• Diseñado para trabajar conjuntamente con Bigtable
• Almacenamiento de metadatos de Colossus en Bigtable

Sistemas Distribuidos
15

Fernando Pérez Costoya