language-agnostic mapreduce

language agnostic - ¿Qué es Map/Reduce?



hbase (6)

Escucho mucho sobre map / reduce, especialmente en el contexto del sistema de cómputo masivamente paralelo de Google. ¿Qué es exactamente?

Del resumen de la página de publicación de investigación MapReduce de Google:

MapReduce es un modelo de programación y una implementación asociada para procesar y generar grandes conjuntos de datos. Los usuarios especifican una función de mapa que procesa un par de clave / valor para generar un conjunto de pares de clave / valor intermedios, y una función de reducción que combina todos los valores intermedios asociados con la misma clave intermedia.

La ventaja de MapReduce es que el procesamiento se puede realizar en paralelo en múltiples nodos de procesamiento (servidores múltiples) por lo que es un sistema que puede escalar muy bien.

Como está basado en el modelo de programación funcional , el map y reduce pasos reducidos, cada uno no tiene ningún efecto secundario (el estado y los resultados de cada subsección de un proceso de map no dependen de otro), por lo que el conjunto de datos que se mapea y reduce puede cada uno debe estar separado sobre múltiples nodos de procesamiento.

Joel''s Can Your Programming Language Hacer esto? La pieza analiza cómo entender la programación funcional era esencial en Google para llegar a MapReduce, que impulsa su motor de búsqueda. Es una lectura muy buena si no está familiarizado con la programación funcional y cómo permite el código escalable.

Ver también: Wikipedia: MapReduce

Pregunta relacionada: explique mapreduce simplemente

Después de frustrarme al máximo con waffley muy largos o con publicaciones vagas muy breves del blog, finalmente descubrí este muy buen documento conciso y riguroso .

Luego seguí adelante y lo hice más conciso traduciéndolo a Scala, donde proporcioné el caso más simple en el que un usuario simplemente especifica el map y reduce partes de la aplicación. En Hadoop / Spark, estrictamente hablando, se emplea un modelo de programación más complejo que requiere que el usuario especifique explícitamente 4 funciones más descritas aquí: http://en.wikipedia.org/wiki/MapReduce#Dataflow

import scalaz.syntax.id._ trait MapReduceModel { type MultiSet[T] = Iterable[T] // `map` must be a pure function def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)]) (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = data.flatMap(map) def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] = mappedData.groupBy(_._1).mapValues(_.map(_._2)) // `reduce` must be a monoid def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]) (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] = shuffledData.flatMap(reduce).map(_._2) def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)]) (map: ((K1, V1)) => MultiSet[(K2, V2)]) (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] = mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce) } // Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster // Furthermore, the splitting here won''t enforce any kind of balance and is quite unnecessary anyway as one would expect // it to already be splitted on HDFS - i.e. the filename would constitute K1 // The shuffle phase will also be parallelized, and use the same partition as the map phase. abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel { def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]] override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)]) (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = { val groupedByKey = data.groupBy(_._1).map(_._2) groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1)) .par.flatMap(_.map(map)).flatten.toList } override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]) (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] = shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _))) .par.flatMap(_.map(reduce)) .flatten.map(_._2).toList }

El mapa es un método JS nativo que se puede aplicar a una matriz. Crea una nueva matriz como resultado de alguna función asignada a cada elemento en la matriz original. Por lo tanto, si asignó una función (elemento) {elemento de retorno * 2;}, devolverá una nueva matriz con cada elemento duplicado. La matriz original no se modificará.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map

Reducir es un método JS nativo que también se puede aplicar a una matriz. Aplica una función a una matriz y tiene un valor de salida inicial llamado acumulador. Pasa por cada elemento de la matriz, aplica una función y los reduce a un único valor (que comienza como acumulador). Es útil porque puede tener cualquier salida que desee, solo tiene que comenzar con ese tipo de acumulador. Entonces, si quisiera reducir algo a un objeto, comenzaría con un acumulador {}.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce?v=a

El mapa es una función que aplica otra función a todos los elementos en una lista, para producir otra lista con todos los valores de retorno. (Otra forma de decir "aplicar f a x" es "llamar f, pasarlo x". Por lo tanto, a veces suena mejor decir "aplicar" en lugar de "llamar").

Así es como el mapa probablemente está escrito en C # (se llama Select y está en la biblioteca estándar):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func) { foreach (T item in list) yield return func(item); }

Como eres un tipo Java, ya Joel Spolsky le gusta contar MENTIRAS INJUSTA sobre lo malo que es Java (en realidad, no está mintiendo, es horrible, pero estoy tratando de ganarte), aquí está mi muy duro intento de una versión de Java (no tengo compilador de Java, y recuerdo vagamente la versión 1.1 de Java):

// represents a function that takes one arg and returns a result public interface IFunctor { object invoke(object arg); } public static object[] map(object[] list, IFunctor func) { object[] returnValues = new object[list.length]; for (int n = 0; n < list.length; n++) returnValues[n] = func.invoke(list[n]); return returnValues; }

Estoy seguro de que esto se puede mejorar de mil maneras. Pero es la idea básica.

Reducir es una función que convierte todos los elementos en una lista en un solo valor. Para hacer esto, necesita tener otra función func que convierta dos elementos en un solo valor. Funcionaría dando los dos primeros elementos a func . Entonces el resultado de eso junto con el tercer artículo. Luego, el resultado de eso con el cuarto artículo, y así sucesivamente hasta que todos los artículos se hayan ido y nos quede un solo valor.

En C # reduce se llama Aggregate y está de nuevo en la biblioteca estándar. Voy a saltar directamente a una versión de Java:

// represents a function that takes two args and returns a result public interface IBinaryFunctor { object invoke(object arg1, object arg2); } public static object reduce(object[] list, IBinaryFunctor func) { if (list.length == 0) return null; // or throw something? if (list.length == 1) return list[0]; // just return the only item object returnValue = func.invoke(list[0], list[1]); for (int n = 1; n < list.length; n++) returnValue = func.invoke(returnValue, list[n]); return returnValue; }

Estas versiones de Java necesitan genéricos que les agreguen, pero no sé cómo hacerlo en Java. Pero debería poder pasarles clases internas anónimas para proporcionar los funtores:

string[] names = getLotsOfNames(); string commaSeparatedNames = (string)reduce(names, new IBinaryFunctor { public object invoke(object arg1, object arg2) { return ((string)arg1) + ", " + ((string)arg2); } }

Es de esperar que los genéricos se deshagan de los moldes. El equivalente de tipo seguro en C # es:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

¿Por qué es esto "genial"? Maneras simples de dividir cálculos más grandes en piezas más pequeñas, para que puedan volver a juntarse de diferentes maneras, siempre son geniales. La forma en que Google aplica esta idea es la paralelización, ya que tanto el mapa como la reducción se pueden compartir en varias computadoras.

Pero el requisito clave NO es que su lenguaje pueda tratar las funciones como valores. Cualquier lenguaje OO puede hacer eso. El requisito real para la paralelización es que las funciones poco func que pasa para mapear y reducir no deben usar ni actualizar ningún estado. Deben devolver un valor que depende únicamente de los argumentos que se les pasan. De lo contrario, los resultados se arruinarán por completo cuando trates de ejecutar todo en paralelo.