A comparative study on parallelization of streaming top-k algorithms in Kafka

Continuous top-k query monitoring, which reports the k top-scored objects from data streams, is a challenging problem in modern streaming applications due to the high data rates that exceed the data stream infrastructure's capacity. Streaming top-k algorithms try to solve it by optimizing resources. We focus on some of them to select the ones to use for our comparative study. We choose an algorithm that sorts every window's elements and keeps the first ks as the top-k result; also, we select the MinTop-K algorithm, an excellent resource optimization example. We opt for Kafka as the distributed streaming platform where to implement them. Kafka is one of the most used distributed streaming platforms, so we want to understand if we can leverage it to implement streaming top-k algorithms. We develop both centralized and distributed algorithms using Kafka Streams and Processor APIs. Moreover, we want to understand if it is worth parallelizing streaming top-k algorithms and the relationship between the top-k parameter, k, and the KPI we measured. As KPI, we use the time needed to compute top-k results for a fixed amount of streaming data. To answer our questions, we perform a comparative study. We compare the centralized and distributed versions' KPI to understand if we can achieve better performance parallelizing the algorithms, playing with the parallelization degree. We compare the algorithm's execution with different top-k values to study the correlation between the chosen KPI and the k parameter. The results show considerable improvements in the distributed versions over the centralized ones in both algorithms. Moreover, we find out that large enough top-k values significantly influence the experiments' total time, showing exponential growth, while small k values almost do not influence the observed KPI. Our implementations exploit Kafka Streams and Processor API, candidating Kafka to be an excellent solution for continuous top-k query monitoring.

Il monitoraggio continuo delle query top-k, che riporta gli oggetti top-scored provenienti dai data stream, è un problema impegnativo nelle moderne applicazioni di streaming a causa delle elevate velocità di trasmissione dei dati che superano la capacità dell'infrastruttura. Gli algoritmi di streaming top-k cercano di risolverlo ottimizzando le risorse. Abbiamo selezionato un paio di questi algoritmi per il nostro studio comparativo. Abbiamo scelto un algoritmo che ordina gli elementi di ogni finestra e mantiene i primi k; inoltre, abbiamo selezionato l'algoritmo MinTop-K, un eccellente esempio di ottimizzazione delle risorse. Abbiamo optato per Kafka come piattaforma di streaming distribuito perché è una delle piattaforme di streaming distribuito più utilizzate, e abbiamo voluto capire se fosse possibile sfruttarla per implementare gli algoritmi di streaming top-k. Abbiamo sviluppato sia algoritmi centralizzati che paralleli utilizzando Kafka Streams e le Processor API. Inoltre, abbiamo considerato se valesse la pena di parallelizzare gli algoritmi di streaming top-k e la relazione tra il parametro top-k, k, e il KPI che abbiamo misurato. Come KPI, abbiamo utilizzato il tempo necessario per calcolare i top-k per una quantità fissa di dati in streaming. Per rispondere alle nostre domande, abbiamo eseguito uno studio comparativo. Abbiamo confrontato i KPI delle due versioni per capire se fosse possibile ottenere migliori prestazioni parallelizzando gli algoritmi, modificando il grado di parallelizzazione. Abbiamo confrontato l'esecuzione dell'algoritmo con diversi valori di k per studiare la correlazione tra il KPI scelto e il parametro k. I risultati hanno mostrato notevoli miglioramenti nelle versioni parallele rispetto a quelle centralizzate. Inoltre, abbiamo scoperto che valori di top-k abbastanza elevati influenzano significativamente il KPI misurato, mostrando una crescita esponenziale, mentre valori di k piccoli quasi non influenzano il KPI osservato. Le nostre implementazioni sfruttano Kafka Streams e le Processor API, candidando Kafka ad essere una soluzione eccellente per il monitoraggio continuo delle query top-k.