contrato de paralelización

El modelo de programación PACT ( contrato de paralelización ) es una generalización del modelo de programación MapReduce y utiliza funciones de segundo orden para realizar cálculos concurrentes en grandes conjuntos de datos ( petabytes ) en paralelo.

Descripción general

De forma similar a MapReduce, PACT gestiona y ejecuta código de usuario arbitrario. Sin embargo, PACT generaliza un par de conceptos de MapReduce:

Funciones de segundo orden: PACT ofrece más funciones de segundo orden. Actualmente, admite cinco funciones de segundo orden denominadas Contratos de Entrada . Este conjunto podría ampliarse en el futuro.
Estructura del programa: PACT permite la composición de grafos de flujo de datos acíclicos arbitrarios. En cambio, los programas MapReduce tienen una estructura estática (Map -> Reduce).
Modelo de datos: El modelo de datos de PACT consiste en registros con un número arbitrario de campos de tipos arbitrarios. Los pares clave-valor de MapReduce pueden considerarse como registros con dos campos.

Apache Flink , una plataforma de procesamiento de datos paralelos de código abierto, ha implementado PACT . Flink permite a los usuarios especificar funciones de usuario mediante anotaciones.

Visión lógica

Los contratos de paralelización (PACT) son operadores de procesamiento de datos en un flujo de datos. Por lo tanto, un PACT tiene una o más entradas de datos y una o más salidas. Un PACT consta de dos componentes:

Contrato de insumos
Función de usuario
Anotaciones de código de usuario

La siguiente figura muestra cómo funcionan conjuntamente estos componentes. Los contratos de entrada dividen los datos de entrada en subconjuntos que se pueden procesar de forma independiente. El código del usuario se ejecuta para cada uno de estos subconjuntos independientes. Todas las llamadas se pueden ejecutar en paralelo, ya que los subconjuntos son independientes.

Opcionalmente, el código del usuario puede anotarse con información adicional. Estas anotaciones revelan información sobre el comportamiento de la función de usuario de caja negra. El compilador PACT puede utilizar esta información para obtener planes de ejecución más eficientes. Sin embargo, si bien la ausencia de una anotación no modifica el resultado de la ejecución, un contrato de salida incorrecto produce resultados erróneos.

A continuación se presentan y analizan los contratos de entrada y las anotaciones compatibles actualmente.

Contratos de insumos

Los contratos de entrada dividen los datos de entrada de un PACT en subconjuntos procesables de forma independiente que se entregan a la función de usuario del PACT. Los contratos de entrada varían en la cantidad de entradas de datos y en la forma en que se generan los subconjuntos independientes.

Formalmente, los contratos de entrada son funciones de segundo orden con una función de primer orden (el código del usuario), uno o más conjuntos de entrada y uno o más campos clave por entrada como parámetros. La función de primer orden se llama una o varias veces con subconjuntos del conjunto o conjuntos de entrada. Dado que las funciones de primer orden no tienen efectos secundarios, cada llamada es independiente de las demás y todas pueden ejecutarse en paralelo.

Las funciones de segundo orden map() y reduce() del modelo de programación MapReduce son contratos de entrada en el contexto del modelo de programación PACT.

MAPA

El contrato de entrada de Map funciona de la misma manera que en MapReduce. Tiene una única entrada y asigna cada registro de entrada a su propio subconjunto. Por lo tanto, todos los registros se procesan de forma independiente.

REDUCIR

El contrato de entrada de reducción tiene la misma semántica que la función de reducción en MapReduce. Tiene una única entrada y agrupa todos los registros que tienen campos clave idénticos. Cada uno de estos grupos se pasa como un todo al código del usuario y este lo procesa (véase la figura a continuación). El modelo de programación PACT también admite combinadores opcionales, por ejemplo, para agregaciones parciales.

CRUZ

El contrato de entrada cruzada funciona con dos entradas. Construye el producto cartesiano de los registros de ambas entradas. Cada elemento del producto cartesiano (par de registros) se entrega al código del usuario.

FÓSFORO

El contrato de coincidencia de entradas trabaja con dos entradas. De ambas, busca los registros que coinciden en sus campos clave y que provienen de entradas diferentes. Por lo tanto, se asemeja a una unión por igualdad, donde las claves de ambas entradas son los atributos que se utilizan para la unión. Cada par de registros coincidentes se entrega al código del usuario.

COGRUPO

El contrato de entrada CoGroup también funciona con dos entradas. Puede considerarse como una operación Reduce con dos entradas. En cada entrada, los registros se agrupan por clave (como lo hace Reduce) y se entregan al código de usuario. A diferencia de Match, también se llama al código de usuario para una clave si solo una entrada tiene un par con ella.

Modelo de datos del registro de pacto

A diferencia de MapReduce, PACT utiliza un modelo de datos más genérico ( registro Pact ) para transferir datos entre funciones. El registro Pact puede considerarse una tupla con un esquema libre. La interpretación de los campos de un registro depende de la función del usuario. Un par clave/valor (como en MapReduce) es un caso especial de ese registro con solo dos campos (la clave y el valor).

Para los contratos de entrada que operan sobre claves (como //Reduce//, //Match// o //CoGroup//), se especifica qué combinación de los campos del registro compone la clave. Se puede utilizar una combinación arbitraria de campos. Consulte el Ejemplo de consulta para ver cómo se pueden escribir programas que definen contratos //Reduce// y //Match// en uno o más campos para mover datos entre campos de forma mínima.

El registro puede estar incompleto, es decir, puede contener campos con valores nulos. Es válido generar un registro donde, por ejemplo, solo se completen los campos 2 y 5. Los campos 1, 3 y 4 se interpretan como nulos. Sin embargo, los campos que un contrato utiliza como claves no pueden ser nulos, o se generará una excepción.

Anotaciones de código de usuario

En el modelo de programación PACT, las anotaciones en el código del usuario son opcionales. Permiten al desarrollador especificar ciertos comportamientos de su código para el optimizador. Este puede utilizar dicha información para obtener planes de ejecución más eficientes. Sin embargo, la ausencia de una anotación válida en el código del usuario no afectará la corrección del resultado. Por otro lado, las anotaciones no válidas podrían generar resultados erróneos. A continuación, se muestra el conjunto actual de contratos de salida disponibles.

Campos constantes

La anotación Campos Constantes marca los campos que no se modifican mediante la función de código del usuario. Tenga en cuenta que, para cada registro de entrada, un campo constante no puede cambiar su contenido ni su posición en ningún registro de salida. En el caso de funciones binarias de segundo orden como Cross, Match y CoGroup, el usuario puede especificar una anotación por entrada.

Campos constantes excepto

La anotación «Campos constantes excepto» es inversa a la anotación «Campos constantes». Anota todos los campos que podrían ser modificados por la función de usuario anotada; por lo tanto, el optimizador considera como constante cualquier campo no anotado. ¡Esta anotación debe usarse con mucha precaución! Nuevamente, para funciones binarias de segundo orden (Cross, Match, CoGroup), se puede definir una anotación por entrada. Tenga en cuenta que se puede usar la anotación «Campos constantes excepto» o la anotación «Campos constantes excepto» para una entrada.

Programas PACT

Los programas PACT se construyen como grafos de flujo de datos que constan de fuentes de datos, PACT y sumideros de datos. Una o más fuentes de datos leen archivos que contienen los datos de entrada y generan registros a partir de ellos. Estos registros son procesados por uno o más PACT, cada uno compuesto por un contrato de entrada, código de usuario y anotaciones de código opcionales. Finalmente, los resultados se escriben en archivos de salida mediante uno o más sumideros de datos. A diferencia del modelo de programación MapReduce, un programa PACT puede ser arbitrariamente complejo y no tiene una estructura fija.

La figura siguiente muestra un programa PACT con dos fuentes de datos, cuatro PACT y un sumidero de datos. Cada fuente de datos lee datos de una ubicación específica en el sistema de archivos. Ambas fuentes envían los datos a sus respectivos PACT con contratos de entrada de mapeo. El código de usuario no se muestra en la figura. La salida de ambos PACT de mapeo se dirige a un PACT con un contrato de entrada de coincidencia. El último PACT tiene un contrato de entrada de reducción y envía su resultado al sumidero de datos.

Wiki:pactProgram.png?nolink&600

Ventajas de PACT sobre MapReduce

El modelo de programación PACT fomenta un estilo de programación más modular . Si bien el número de funciones de usuario suele ser mayor, estas son más específicas y se centran en problemas concretos. Por lo tanto, se evita la interconexión de funcionalidades, común en los trabajos de MapReduce.
Las tareas de análisis de datos pueden expresarse como flujos de datos sencillos, especialmente cuando se requieren múltiples entradas.
PACT tiene un modelo de datos basado en registros, lo que reduce la necesidad de especificar tipos de datos personalizados, ya que no todos los elementos de datos necesitan agruparse en un único tipo de valor.
PACT elimina con frecuencia la necesidad de estructuras auxiliares, como la caché distribuida , que "rompen" el modelo de programación paralela .
Las operaciones de organización de datos, como la creación de un producto cartesiano o la combinación de registros con claves iguales, las realiza el sistema en tiempo de ejecución. En MapReduce, este tipo de funcionalidad, a menudo necesaria, debe ser proporcionada por el desarrollador del código de usuario.
Los PACT especifican la paralelización de datos de forma declarativa, lo que otorga al sistema varios grados de libertad. Estos grados de libertad son un requisito previo importante para la optimización automática. El compilador de PACT enumera diferentes estrategias de ejecución y elige la que requiere la menor cantidad estimada de datos a enviar. En cambio, Hadoop ejecuta los trabajos de MapReduce siempre con la misma estrategia.

Referencias

«Nephele/PACTs: Un modelo de programación y un marco de ejecución para el procesamiento analítico a escala web» —artículo de D. Battré, S. Ewen, F. Hueske, O. Kao, V. Markl y D. Warneke de la TU Berlín , publicado en las Actas de ACM SoCC 2010. El artículo presenta el modelo de programación PACT, una generalización de MapReduce, desarrollado en el proyecto de investigación Stratosphere .
"MapReduce y PACT: Comparación de modelos de programación paralela de datos" —artículo de A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp y D. Warneke de la TU Berlín , publicado en las Actas de BTW 2011.

Lecturas adicionales

Un marco para la ejecución paralela de datos distribuidos en el sistema de flujo de trabajo científico Kepler.

Enlaces externos

Página principal del proyecto Stratosphere
Presentación de diapositivas sobre la estratosfera
Videoconferencia sobre programación de flujo de datos en paralelo