Processing theta-joins in streaming environments under the micro-batch model

Abstract

Join computations in stream requires support for state management since tuple pairs that would generate a result might arrive in distinct moments in the application. The solution offered by Stream Processing Systems (SPS) like Spark and Storm for state management are windows limited by time or size constraint. Published papers (LIN et al., 2015; ELSEIDY et al., 2014) offer support for storing tuples without time restriction in the record-at-a-time model. In this work, we propose a solution for computing joins in a stream environment under the micro-batch model with support for state management to theta-joins. The approach stores tuples and uses a broadcast shuffle to run the broadcast join algorithm, enumerating the cartesian product between streams and thus allowing arbitrary predicates. The model is implemented in Spark Streaming and uses RDDs as storages in main memory and Apache Kafka as message-queue for data input, besides using HDFS to store results. The methodology focuses on the scalability of the solution, using the synthetic benchmark TPC-H and the queries in a left-deep-tree model. The experiments investigate the execution time and resources like network and memory for a different number of nodes. The evaluation was executed in a cluster of virtual machines orchestrated by Kubernetes in Microsoft Azure. The results show a performance gain of 40% when we double the resources and high network usage as a consequence of Broadcast.

A computação de joins em streams requer o suporte de gerenciamento de estados, pois os pares de tuplas que geram um resultado podem chegar em momentos distintos na aplicação. A solução oferecida por Stream Service Providers como Spark e Storm para o gerenciamento de estados são janelas limitas por um intervalo de tempo ou tamanho. Trabalhos publicados (LIN et al., 2015; ELSEIDY et al., 2014) oferecem suporte a um armazenamento sem restrição de tempo no modelo de streams record-at-a-time. Nesse trabalho propõe-se uma solução para computar joins em stream sobre o modelo micro-batch com suporte a um gerenciamento de estados em memória para theta-joins. O método armazena tuplas e realiza um broadcast Shuffle para então utilizar o algoritmo broadcast join, enumerando o produto cartesiano entre streams e permitindo predicados arbitrários. O modelo foi prototipado sobre a API Spark Streaming e utiliza RDDs como armazenamento em memória principal e o Apache Kafka como message-queue (MQ) para entrada de dados, além do HDFS para armazenamento de resultados. A metodologia foca na escalabilidade da solução, utilizando o benchmark sintétipo TPC-H e queries no modelo left-deep-tree. Os experimentos investigam o tempo de execução e o uso de recursos como rede e memória para diferentes números de nós . A avaliação foi executada em um cluster de máquinas virtuais orquestrado pelo Kubernetes na Microsoft Azure. Os resultados mostram um ganho de desempenho de 40% ao dobrar recursos e um alto uso de rede como consequência do broadcast.