Задача оптимизации размещения данных в распределённых системах

Эффективность работы распределённых вычислительных систем основывается на способе распределения потоков вычислительных задач и данных относительно ограниченного количества вычислительных ресурсов. Из-за постоянного увеличения объёма данных таким системам необходимо решать вопрос их хранения и обработки наиболее эффективным образом. Между тем современные распределённые вычислительные системы уделяют все больше внимания таким своим характеристикам, как распределение вычислительной нагрузки, построение эффективной структуры хранилища данных, а также оптимальное использование вычислительных мощностей. Оптимальное управление имеющимися у вычислительной системы ресурсами вынуждено балансировать между использованием ресурсов каждого отдельно взятого узла и потерей локальности хранения данных, связанной с их неизбежной фрагментацией. В данной статье мы сформируем задачу оптимизации размещения данных путём максимизации локальности их хранения, а также покажем, что данная задача является NP-полной. Далее мы рассмотрим полиномиальный по времени алгоритм, дающий результат, отличающийся от оптимального на фиксированную константу. Для доказательства эффективности предложенного алгоритма нами будет доказан ряд вспомогательных утверждений, а также подробно описана основная операция в работе алгоритма, за свою схожесть с процессом обмена участками хромосом в клетках названная кроссинговером.

The Problem of Data Placement in Distributed Systems

Distributed system effectiveness depends dramatically on the way it manages incoming tasks and data against limited computational resources that are at its disposal. Due to ever-inreasing amount of incoming data distributed systems are required to efficiently manage the way its storage and processing are being made. Nowadays the distributed system design is significantly flounced by the manner it leverages high load scenarios, provides data storage functionality and uses the underlying resources. An effective distributed system’s resource management has to balance trade-offs between single node resource consumption and the overall loss of data locality, that is inevitable due to data fragmentation. In this article we will formalize the problem of data placement by maximizing data storage locality in distributed data systems, which as it turns out is a NP-complete task. We will later describe a polynomial-time algorithm that is capable of providing us a solution that is within an additive constant from the optimal one.