Алгоритми сортування великих даних у розподілених системах на прикладі MapReduce

Abstract

У тезах розглянуто проблему сортування даних, обсяг яких перевищує оперативну пам'ять одного комп'ютера. Проаналізовано класичні алгоритми сортування та показано обмеження їхнього застосування в контексті Big Data. Основну увагу приділено моделі MapReduce, яка є стандартом де-факто для розподіленої обробки даних. Детально описано фазу "Shuffle and Sort" як ключовий механізм, що гарантує впорядкованість даних. Наведено таблицю порівняння підходів до сортування та зроблено висновки щодо ефективності розподіленого підходу.

The thesis examines the problem of sorting data volumes that exceed the RAM capacity of a single machine. Classical sorting algorithms are analyzed, and the limitations of their application in the context of Big Data are shown. The focus is on the MapReduce model, which is the de facto standard for distributed data processing. The "Shuffle and Sort" phase is described in detail as a key mechanism that guarantees data ordering. A comparative table of sorting approaches is provided, and conclusions regarding the efficiency of the distributed approach are drawn.