On Exact and Approximate Policies for Linear Tape Scheduling in Data Centers

This paper investigates scheduling policies for file retrieval in linear storage devices, such as magnetic tapes. Tapes are the technology of choice for long-term storage in data centers due to their low cost per capacity, reliability, and data security. While scheduling problems associated with data retrieval in tapes are classical, existing works focus on more straightforward heuristic approaches due to limited computational times imposed by standard tape specifications. Our first contribution is a theoretical investigation of three standard policies, presenting their worst-case performance and special cases of practical relevance for which they are optimal. Next, we show that the problem is polynomially solvable via two interleaved recursive models, albeit with high computational complexity. We leverage our previous results to develop two new scheduling policies with constant-ratio performance and low computational cost. Finally, we investigate properties associated with the online variant of the problem, presenting a new constant-factor competitive algorithm. Our numerical analysis on synthetic and real-world tapes from an industry partner provides insights into dataset configurations where each policy is more effective, which is of relevance to data center managers. In particular, our new best-performing policy is practical for large datasets and significantly improves upon standard algorithms in the area.