Scheduling Techniques for Effective System Reconfiguration in Distributed Storage Systems

In this paper, we present a new algorithm for disk reconfiguration in the context of Vespa, a scalable platform developed by Yahoo! Technologies Norway for storing, retrieving, processing and searching large amounts large amounts of data. The corresponding scheduling problem is closely related to independent tasks scheduling on heterogeneous platforms, when communication costs are taken into account, and when each task can only be processed on a prescribed set of processors. We prove how to derive from a linear programming formulation in rational numbers an approximation algorithm whose approximation ratio is close to 1 in the condition of use o/Vespa. By performing an extensive set of simulations using SIMGRID, we also show the proposed algorithm is in fact optimal under Vespa conditions of use.