clase 2: gfs/hdfs & mapreduce/hadoopaidanhogan.com/teaching/gdd-2017/02/gdd2017-02.pdf1. parsear...
TRANSCRIPT
![Page 1: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/1.jpg)
GESTIÓN DE DATOS (MASIVOS)
DIPLOMADO DE DATOS 2017
Clase 2: GFS/HDFS & MapReduce/Hadoop
Aidan Hogan
![Page 2: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/2.jpg)
GESTIÓN DE DATOS MASIVOS
... COMO LO HACE GOOGLE ...
![Page 3: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/3.jpg)
Dentro de Google: 1997/98
![Page 4: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/4.jpg)
Dentro de Google: 2017
![Page 5: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/5.jpg)
Implementando la búsqueda de Google
¿Qué procesos y algoritmos necesita Google
para implementar su búsqueda de la Web?
Crawling1. Parsear enlaces de las páginas
2. Ordenar los enlaces para bajar
3. Bajar páginas, GOTO 1
Indexación1. Parsear keywords de las páginas
2. Indexear sus keywords
3. Administrar actualizaciones
Ranking1. ¿Cuán relevante es una página?
2. ¿Cuán importante es?
3. ¿Cuántos clics tiene?
...
![Page 6: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/6.jpg)
Implementando la búsqueda de Google
¿Qué procesos y algoritmos necesita Google
para implementar su búsqueda de la Web?
Crawling1. Parsear enlaces de las páginas
2. Ordenar los enlaces para bajar
3. Bajar páginas, GOTO 1
Indexación1. Parsear keywords de las páginas
2. Indexear sus keywords
3. Administrar actualizaciones
Ranking1. ¿Cuán relevante es una página?
2. ¿Cuán importante es?
3. ¿Cuántos clics tiene?
...
≈ 100 PB / día
≈ 2,000,000 Wiki / día
(2014, procesados)
![Page 7: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/7.jpg)
Implementando la búsqueda de Google
![Page 8: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/8.jpg)
Implementando la búsqueda de Google
¿Qué abstracciones distribuidas podemos
considerar para facilitar aplicaciones así?
Crawling1. Parsear enlaces de las páginas
2. Ordenar los enlaces para bajar
3. Bajar páginas, GOTO 1
Indexación1. Parsear keywords de las páginas
2. Indexear sus keywords
3. Administrar actualizaciones
Ranking1. ¿Cuán relevante es una página?
2. ¿Cuán importante es?
3. ¿Cuántos clics tiene?
...
• write(file f )
• read(file f )
• delete(file f )
• append(file f, data d) ... al menos para empezar
![Page 9: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/9.jpg)
GOOGLE FILE SYSTEM (GFS)(SISTEMA DE ARCHIVOS DE GOOGLE)
![Page 10: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/10.jpg)
Google File System (GFS): White-Paper
![Page 11: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/11.jpg)
Google File System
¿Qué es un sistema de archivos (un “file-system”)?
![Page 12: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/12.jpg)
Google File System
¿Qué es un sistema de archivos (un “file-system”)?
![Page 13: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/13.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
Google File System
¿Qué hace un sistema de archivos?
![Page 14: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/14.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
2. Organiza una estructura jerárquica de carpetas
• Guarda las carpetas y los archivos en una carpeta
Google File System
¿Qué hace un sistema de archivos?
![Page 15: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/15.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
2. Organiza una estructura jerárquica de carpetas
• Guarda las carpetas y los archivos en una carpeta
3. Guarda los meta datos de los archivos
• Tamaño de los archivos, fecha de creación
Google File System
¿Qué hace un sistema de archivos?
![Page 16: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/16.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
2. Organiza una estructura jerárquica de carpetas
• Guarda las carpetas y los archivos en una carpeta
3. Guarda los meta datos de los archivos
• Tamaño de los archivos, fecha de creación
4. Protege los archivos
• Propiedad, permisos, bloqueos de sincronización
Google File System
¿Qué hace un sistema de archivos?
![Page 17: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/17.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
2. Organiza una estructura jerárquica de carpetas
• Guarda las carpetas y los archivos en una carpeta
3. Guarda los meta datos de los archivos
• Tamaño de los archivos, fecha de creación
4. Protege los archivos
• Propiedad, permisos, bloqueos de sincronización
5. Proviene una interfaz para interactuar con archivos
• Crear, borrar, copiar, etc.
Google File System
¿Qué hace un sistema de archivos?
![Page 18: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/18.jpg)
Google File System
¿Qué hace el "Google File System"?
![Page 19: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/19.jpg)
1. Divide un archivo en bloques de almacenamiento
• Guarda la ubicación y secuencia de los bloques de un archivo
2. Organiza una estructura jerárquica de carpetas
• Guarda las carpetas y los archivos en una carpeta
3. Guarda los meta datos de los archivos
• Tamaño de los archivos, fecha de creación
4. Protege los archivos
• Propiedad, permisos, bloqueos de sincronización
5. Proviene una interfaz para interactuar con archivos
• Crear, borrar, copiar, etc.
Lo mismo, pero distribuido:
(y abstrae la distribución)
Google File System
¿Qué hace el "Google File System"?
![Page 20: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/20.jpg)
Google File System: Suposiciones
Archivos enormes
Archivos frecuentemente leídos o anexados
Concurrencia es importante
Fallas son frecuentes
"Streaming" es importante
![Page 21: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/21.jpg)
GFS: Arquitectura
Esclavos
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
Sistema de archivos (en memoria)
A1 B1 C1 D1 E1
Maestro
![Page 22: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/22.jpg)
GFS: Escritura
Esclavos
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
Sistema de archivos (en memoria)
A1 B1 C1 D1 E1
Maestroblue.txt
(150 MB: 3 bloques)
¿Cómo deberíamos proceder con la escritura?
![Page 23: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/23.jpg)
GFS: Escritura
Esclavos
1
1 12
2
2
3
3
3
1
1 122
2
Sistema de archivos (en memoria)/blue.txt [3 bloques]
1: {A1, C1, E1}2: {A1, B1, D1}3: {B1, D1, E1}/orange.txt [2 bloques]1: {B1, D1, E1}2: {A1, C1, E1}
A1 B1 C1 D1 E1
blue.txt
(150 MB: 3 bloques)
orange.txt
(100 MB: 2 bloques)
Maestro
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
![Page 24: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/24.jpg)
Sistema de archivos (en memoria)/blue.txt [3 bloques]
1: {A1, C1, E1}2: {A1, B1, D1}3: {B1, D1, E1}/orange.txt [2 bloques]1: {B1, D1, E1}2: {A1, C1, E1}
Sistema de archivos (en memoria)/blue.txt [3 bloques]
1: {A1, B1, E1}2: {A1, B1, D1}3: {B1, D1, E1}/orange.txt [2 bloques]1: {B1, D1, E1}2: {A1, D1, E1}
GFS: Tolerancia a fallos
1
1 12
2
2
3
3
3
1
1 122
2
A1 B1 D1 E1C1
1
2
Esclavos
blue.txt
(150 MB: 3 bloques)
orange.txt
(100 MB: 2 bloques)
Maestro
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
![Page 25: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/25.jpg)
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
GFS: Lecturas directas
Esclavos
1
1 12
2
2
3
3
3
1
1 122
2
Sistema de archivos (en memoria)/blue.txt [3 bloques]
1: {A1, C1, E1}2: {A1, B1, D1}3: {B1, D1, E1}/orange.txt [2 bloques]1: {B1, D1, E1}2: {A1, C1, E1}
A1 B1 C1 D1 E1
Maestro
Busco/blue.txt
1 2 3
![Page 26: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/26.jpg)
• 64 MB por bloque• Etiqueta de 64 bit para cada bloque• Suponer factor de replicación: 3
GFS: Replicas Primarias
Esclavos
1
1 12
2
2
3
3
3
1
1 122
2
Sistema de archivos (en memoria)/blue.txt [3 bloques]
1: {A1, C1, E1}2: {A1, B1, D1}3: {B1, D1, E1}/orange.txt [2 bloques]1: {B1, D1, E1}2: {A1, C1, E1}
A1 B1 C1 D1 E1
Maestro
2
Quiero cambiar el bloque 2 de /blue.txt
/blue.txt [3 chunks]2: {A1, B1, D1}
22 2
COMMIT
COMMIT COMMIT
ACK ACK
ACK
![Page 27: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/27.jpg)
GFS: Replicas Primarias
Cliente quiere modificar un archivo:
1. Cliente solicita réplicas (incl. la
primaria) al Maestro
2. Maestro retorna información de
la réplica al cliente
3. Cliente envía cambios del archivo
4. Cliente solicita ejecutar los
cambios a la réplica primaria
5. Primaria solicita ejecutar los
cambios a secundarias
6. Secundarias notifican a primaria
7. Primaria notifica al cliente Datos y Control desacoplados
Maestro asigna tarea a una de las réplicas: “réplica primaria”
![Page 28: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/28.jpg)
GFS: Conocimiento sobre Racks
![Page 29: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/29.jpg)
GFS: Conocimiento sobre Racks
Rack ASwitch
Rack BSwitch
Rack CSwitch
CoreSwitch
CoreSwitch
![Page 30: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/30.jpg)
GFS: Conocimiento sobre Racks
Rack ASwitch
Rack BSwitch
CoreSwitch
1
1
1
A1
A2
A3
A4
A5
B1
B2
B3
B4
B5
Archivos:/orange.txt
1: {A1, A4, B3}2: {A5, B1, B5}
2
22
Racks:A: {A1, A2, A3, A4, A5}B: {B1, B2, B3, B4, B5}
![Page 31: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/31.jpg)
GFS: Otras operaciones
Rebalanceo:
• Distribuir el almacenamiento equitativamente
Borrado:
• Renombrar el archivo con nombre de archivo oculto– Para recuperar, volver a renombrar a versión original
– Si no, será eliminado después de tres días
Monitoreo de réplicas obsoletas:
• Esclavo “muerto” reaparece con datos antiguos: maestro guardará información de la versión y reciclará bloques viejos
![Page 32: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/32.jpg)
GFS: ¿Debilidades?
¿Cuales son las debilidades principales del GFS?
Maestro es un único punto de falla• Usar replicación de hardware
• ¡Logs y checkpoints!
Meta-datos del nodo maestro se mantiene en memoria• Cada bloque sólo necesita 64 bytes en memoria
• Datos del bloque pueden ser consultados en cada esclavo
Maestro es un cuello de botella• Usar una máquina más poderosa
• Minimizar tráfico por nodo maestro
![Page 33: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/33.jpg)
Hadoop Distributed File System (HDFS)
• Versión open-source de GFS
– Esclavo = "Data node"
– Maestro = "Name node"
![Page 34: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/34.jpg)
Sistema de archivos distribuido ...
Crawling1. Parsear enlaces de las páginas
2. Ordenar los enlaces para bajar
3. Bajar páginas, GOTO 1
Indexación1. Parsear keywords de las páginas
2. Indexear sus keywords
3. Administrar actualizaciones
Ranking1. ¿Cuán relevante es una página?
2. ¿Cuán importante es?
3. ¿Cuántos clics tiene?
...
• write(file f )
• read(file f )
• delete(file f )
• append(file f, data d)
HDFS/GFS
¿Eso no más?
![Page 35: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/35.jpg)
Sistema de archivos distribuido ...
... es sólo un sistema de archivos.
![Page 36: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/36.jpg)
GOOGLE'S MAPREDUCE
![Page 37: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/37.jpg)
MapReduce: White-Paper
![Page 38: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/38.jpg)
Empecemos con una tarea simple
¿Cómo podemos hacer un conteo de palabras distribuido?
¿Contar partes en la memoria principal de cada máquina?
¿Pero si una parte no cabe en memoria (e.g., 4-gramas)?
¿Y cómo podemos hacer la unificación/suma de los conteos?
¿Contar partes usando el disco duro de cada máquina?
¿Y de nuevo, cómo podemos hacer la suma de los conteos?
![Page 39: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/39.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1
a-k r-zl-q
A1 B1 C1
EntradaDatos en GFS/HDFS
Partición
Ordenar / Contar
SalidaDatos en GFS/HDFS
¿Mejor método de partición?
![Page 40: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/40.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1
hash(w)%3==0 hash(w)%3==2hash(w)%3==1
A1 B1 C1
EntradaDatos en GFS/HDFS
Partición
Ordenar / Contar
SalidaDatos en GFS/HDFS
![Page 41: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/41.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1
hash(w)%3==0 hash(w)%3==2hash(w)%3==1
A1 B1 C1
EntradaDatos en GFS/HDFS
Partición
Ordenar / Contar
SalidaDatos en GFS/HDFS
¿Podemos abstraer un framework general de este ejemplo?
![Page 42: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/42.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1 EntradaDatos en GFS/HDFS
Partición
Ordenar / Contar
¿Cuál parte es general y cuál es específica al conteo?
![Page 43: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/43.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1 EntradaDatos en GFS/HDFS
Partición
Ordenar / Contar
¿Cuál parte es general y cuál es específica al conteo?
![Page 44: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/44.jpg)
MapReduce: Pseudocódigo de conteo de palabras
![Page 45: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/45.jpg)
MapReduce: La idea general
Pero ¿cómo se puede implementar (2) en un sistema distribuido?
1. Hacer una partición por la llave de map
2. Ordenar (en paralelo) por la llave de map
• Implícitamente agrupa por llave
3. Ejecutar reduce
![Page 46: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/46.jpg)
Conteo de palabras distribuido
1 23
A1 B1 C1
hash(w)%3==0 hash(w)%3==2hash(w)%3==1
A1 B1 C1
EntradaDatos en GFS/HDFS
Partición / Transmisión
Ordenamiento
SalidaDatos en GFS/HDFS
Map
Reduce
![Page 47: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/47.jpg)
MapReduce (en detalle)
1. Entrada: Lectura desde el cluster (GFS/HDFS)
– Representa el input en pares de la forma
– Cada tiene tipo y cada tiene tipo
2. Mapeo: Para cada par , genera 0-a-n pares
de la forma
– Cada tiene tipo y cada tiene tipo
– no tienen que ser relacionados
¿Qué hace Entrada en el caso de conteo de palabras?
¿Qué hace Mapeo en el caso de conteo de palabras?
![Page 48: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/48.jpg)
MapReduce (en detalle)
3. Partición: Define la asignación de cada llave del mapeo (y sus pares ) a una máquina (reductor) particular
4. Transmisión ("shuffle"): Los datos son trasladados desde los mapeadores a los reductores (usando GFS/HDFS)
5. Ordenamiento: Cada reductor ordena sus pares por usando una función de comparación (en particular, para agrupar los pares por )
¿Cómo podría funcionar Partición para conteo de palabras?
![Page 49: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/49.jpg)
MapReduce (en detalle)
6. Reducción: Toma todos los valores ... con
el mismo llave y produce 0-a-n pares
7. Salida: Escribe todos los pares de los
reductores a GFS/HDFS en la máquina local
donde se producen los pares
¿Cómo podría funcionar Reducción para conteo de palabras?
![Page 50: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/50.jpg)
1. Entrada
2. Mapeo
4. Transmisión (“Shuffle”)
5. Ordenamiento /
Agrupación
7. Salida
3. Partición / Ordenamiento
6. Reducción
MapReduce (en resumen)
![Page 51: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/51.jpg)
perro sed que
que decir que
la que sed
(0,perro sed que)
(13,que decir que)
(26,la que sed)
(perro,1)
(que,1)
(sed,1)
(decir,1)
(que,1)
(que,1)
(sed,1)
(que,1)
(la,1)
(perro,1)
(que,1)
(que,1)
(que,1)
(que,1)
(decir,1)
(sed,1)
(sed,1)
(la,1)
(decir,{1})
(sed,{1,1})
(que,{1,1,1,1})
(pero,{1})
(la,{1})
(perro,1)
(sed,1)
(que,1)
(que,1)
(decir,1)
(que,1)
(la,1)
(que,1)
(sed,1)
(decir,1)
(sed,2)
(perro,1)
(que,4)
(la,1)
(sed,1)
(decir,1)
(sed,1)
(perro,1)
(que,1)
(que,1)
(que,1)
(que,1)
(la,1)
Entrada MapeoPartición /
OrdenamientoTrans. Agrupación Reducción Salida
MapReduce: Conteo de Palabras
![Page 52: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/52.jpg)
MAPREDUCE:
UNA OPTIMIZACIÓN CON EL "COMBINER"
![Page 53: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/53.jpg)
perro sed que
que decir que
la que sed
(0,perro sed que)
(13,que decir que)
(26,la que sed)
(perro,1)
(que,1)
(sed,1)
(decir,1)
(que,1)
(que,1)
(sed,1)
(que,1)
(la,1)
(perro,1)
(que,1)
(que,1)
(que,1)
(que,1)
(decir,1)
(sed,1)
(sed,1)
(la,1)
(decir,{1})
(sed,{1,1})
(que,{1,1,1,1})
(pero,{1})
(la,{1})
(perro,1)
(sed,1)
(que,1)
(que,1)
(decir,1)
(que,1)
(la,1)
(que,1)
(sed,1)
(decir,1)
(sed,2)
(perro,1)
(que,4)
(la,1)
(sed,1)
(decir,1)
(sed,1)
(perro,1)
(que,1)
(que,1)
(que,1)
(que,1)
(la,1)
MapReduce: Conteo de Palabras
¿Hay algo que podríamos optimizar fácilmente aquí?
![Page 54: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/54.jpg)
1. Entrada
2. Mapeo
4. Transmisión (“Shuffle”)
5. Ordenamiento /
Agrupación
7. Salida
3. Partición / Ordenamiento
6. Reducción
MapReduce (con el "Combiner")
(“Combiner”)
![Page 55: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/55.jpg)
(perro,1)
(que,1)
(sed,1)
(decir,1)
(que,1)
(que,1)
(sed,1)
(que,1)
(la,1)
(perro,1)
(que,1)
(que,1)
(que,2)
(decir,1)
(sed,1)
(sed,1)
(la,1)
(decir,{1})
(sed,{1,1})
(que,{1,1,2})
(pero,{1})
(la,{1})
(perro,1)
(sed,1)
(que,1)
(que,1)
(decir,1)
(que,1)
(la,1)
(que,1)
(sed,1)
(decir,1)
(sed,2)
(perro,1)
(que,4)
(la,1)
(sed,1)
(decir,1)
(sed,1)
(perro,1)
(que,1)
(que,2)
(que,1)
(la,1)
MapeoPartición /
OrdenamientoTrans. Agrupación Reducción Salida
(sed,1)
(perro,1)
(que,1)
(decir,1)
(que,2)
(sed,1)
(que,1)
(la,1)
CombineEntrada
(0,perro sed que)
(13,que decir que)
(26,la que sed)
MapReduce (con el "Combiner")
![Page 56: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/56.jpg)
MapReduce (con el "Combiner")
• Se define el "combiner" como una reducción
• A menudo, se puede usar la reducción misma como un
combiner sin cambiar nada
![Page 57: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/57.jpg)
MapReduce (con el "Combiner")
¿Cuándo se puede usar un combiner?
1. Cuando se produzcan pares con el mismo tipo de llave/valor que
el mapeo (porque se mezclan ambos en la reducción)
2. Cuando la operación de reducción "#" sea
• conmutativa: a#b = b#a
• asociativa a#(b#c) = (a#b)#c = a#b#c
• es decir, cuando se puedan combinar los valores en
cualquier orden con cualquier combinación de
argumentos sin afectar el resultado final; por ejemplo:• +, ×, max, min, etc., están bien
• promedio no: p(a,p(b,c)) ≠ p(p(a,b),c) ≠ p(a,b,c)
![Page 58: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/58.jpg)
MAPREDUCE:
TAREAS MÁS COMPLEJAS
![Page 59: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/59.jpg)
Salida
Entrada
Ventas totales
¿Computar ventas totales por hora?
(Se asume que los precios no cambien)
![Page 60: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/60.jpg)
Entrada
Ventas totales
![Page 61: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/61.jpg)
Indicaciones
• A veces se necesitan varias tareas
– Cada tarea es un join/agrupación
– Se puede encadenar varias tareas así
• Se puede tener varios mapeos para una reducción
– Por ejemplo, para hacer un join sobre varios archivos
• Una reducción necesita al menos un mapeo
– Incluso si el mapeo simplemente "copia" cada par
– El mapeo inicia la partición/transmisión/ordenamiento
• Hay otras soluciones posibles:
– Por ejemplo, hacer el join de producto primero
![Page 62: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/62.jpg)
Entrada
Ventas totales
¿Se puede usar un combiner aquí?
![Page 63: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/63.jpg)
MAPREDUCE:
PROGRAMACIÓN
![Page 64: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/64.jpg)
MapReduce: Beneficios para los programadores
• Se encarga de la implementación a bajo nivel:
– Fácil manejo de inputs y outputs
– No es necesario el manejo de comunicación entre
máquinas
– No es necesario implementar ordenamiento y
agrupación
• Máquinas abstractas (transparencia):
– Tolerancia a fallas
– Ubicaciones físicas abstractas
– Agregar / remover máquinas
– Balanceo de carga
![Page 65: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/65.jpg)
Hadoop
• Implementación open source de MapReduce
• Basado en HDFS
![Page 66: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/66.jpg)
Preguntas?
![Page 67: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/67.jpg)
PROGRAMMING WITH HADOOP
(REFERENCE MATERIAL FOR LAB)
![Page 68: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/68.jpg)
1. Input/Output (cmd)
> hdfs dfs
![Page 69: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/69.jpg)
1. Input/Output (Java)Creates a file
system fordefault
configuration
Check if the file exists; if so
delete
Create file and write a
message
Open and readback
![Page 70: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/70.jpg)
1. Input (Java)
![Page 71: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/71.jpg)
2. MapMapper<InputKeyType,
InputValueType,MapKeyType,
MapValueType>
(input) key: file offset.(input) value: line of the file.context: handles output and
logging.
Emit output
![Page 72: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/72.jpg)
(Writable for values)
Same order
(not needed in therunning example)
![Page 73: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/73.jpg)
(WritableComparable for keys/values)
Needed for default partition function
Needed to sort keys
New Interface
Same as before
(not needed in therunning example)
![Page 74: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/74.jpg)
3. Partition
PartitionerInterface
(This happens to be the default partition method!)
(not needed in therunning example)
![Page 75: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/75.jpg)
4. Shuffle
![Page 76: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/76.jpg)
5. Sort/Comparison
Methods in WritableComparator
(not needed in therunning example)
![Page 77: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/77.jpg)
6. Reduce Reducer<MapKey, MapValue,OutputKey, OutputValue>
key: as emitted frommap
values: iterator overall values for that key
context for output
Write to output
![Page 78: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/78.jpg)
7. Output / Input (Java)Creates a file
system fordefault
configuration
Check if the file exists; if so
delete
Create file and write a
message
Open and readback
![Page 79: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/79.jpg)
7. Output (Java)
![Page 80: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/80.jpg)
Control Flow
Create a JobClient, a JobConfand pass it the main class
Set the type of map and output keys and values in
the configuration
Set input and output paths
Set the mapper class
Set the reducer class(and optionally “combiner”)
Run and wait for job to complete.
![Page 81: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/81.jpg)
More in Hadoop: Combiner
• Map-side “mini-reduction”
• Keeps a fixed-size buffer in memory
• Reduce within that buffer
– e.g., count words in buffer
– Lessens bandwidth needs
• In Hadoop: can simply use Reducer class
![Page 82: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/82.jpg)
More in Hadoop: Counters
Context has a group of mapsof counters
![Page 83: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/83.jpg)
More in Hadoop: Chaining Jobs
• Sometimes we need to chain jobs
• In Hadoop, can pass a set of Jobs to the client
• x.addDependingJob(y)
![Page 84: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/84.jpg)
More in Hadoop: Distributed Cache
• Some tasks need “global knowledge”
– For example, a white-list of conference venues and
journals that should be considered in the citation count
– Typically small
• Use a distributed cache:
– Makes data available locally to all nodes
– (Use sparingly!!)
![Page 85: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/85.jpg)
RECAP
![Page 86: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/86.jpg)
Distributed File Systems
• Google File System (GFS)
– Master and Chunkslaves
– Replicated pipelined writes
– Direct reads
– Minimising master traffic
– Fault-tolerance: self-healing
– Rack awareness
– Consistency and modifications
• Hadoop Distributed File System
– NameNode and DataNodes
![Page 87: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/87.jpg)
MapReduce
1. Input
2. Map
3. Partition
4. Shuffle
5. Comparison/Sort
6. Reduce
7. Output
![Page 88: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/88.jpg)
MapReduce/GFS Revision
• GFS: distributed file system
– Implemented as HDFS
• MapReduce: distributed processing framework
– Implemented as Hadoop
![Page 89: Clase 2: GFS/HDFS & MapReduce/Hadoopaidanhogan.com/teaching/gdd-2017/02/GdD2017-02.pdf1. Parsear enlaces de las páginas 2. Ordenar los enlaces para bajar 3. Bajar páginas, GOTO 1](https://reader033.vdocumento.com/reader033/viewer/2022060920/60ac186df0835e610377957f/html5/thumbnails/89.jpg)
Hadoop
• FileSystem
• Mapper<InputKey,InputValue,MapKey,MapValue>
• OutputCollector<OutputKey,OutputValue>
• Writable, WritableComparable<Key>
• Partitioner<KeyType,ValueType>
• Reducer<MapKey,MapValue,OutputKey,OutputValue>
• JobClient/JobConf
…