On the Throughput Optimization in Large-scale Batch-processing Systems

• Published in: Performance evaluation 2020-12, Vol.144, p.102142, Article 102142
• Main Authors: Kar, Sounak, Rehrmann, Robin, Mukhopadhyay, Arpan, Alt, Bastian, Ciucu, Florin, Koeppl, Heinz, Binnig, Carsten, Rizk, Amr
• Format: Article
• Language: English
• Subjects: Batch queueing systems; Database systems; Mean-field analysis
• ISSN: 0166-5316; 1872-745X
• DOI: 10.1016/j.peva.2020.102142

We analyse a data-processing system with n clients producing jobs which are processed in batches by m parallel servers; the system throughput critically depends on the batch size and a corresponding sub-additive speedup function. In practice, throughput optimization relies on numerical searches for the optimal batch size, a process that can take up to multiple days in existing commercial systems. In this paper, we model the system in terms of a closed queueing network; a standard Markovian analysis yields the optimal throughput in ωn4 time. Our main contribution is a mean-field model of the system for the regime where the system size is large. We show that the mean-field model has a unique, globally attractive stationary point which can be found in closed form and which characterizes the asymptotic throughput of the system as a function of the batch size. Using this expression we find the asymptotically optimal throughput in O(1) time. Numerical settings from a large commercial system reveal that this asymptotic optimum is accurate in practical finite regimes.