Technical Report MSC-2022-42

TR#:MSC-2022-42
Class:MSC
Title: ILP Based Load Balancing in Deduplicated Storage Systems
Authors: Ariel Kolikant
Supervisors: Gala yadgar
PDFCurrently accessibly only within the Technion network
Abstract: Deduplication reduces the size of the data stored in large-scale storage systems by replacing duplicate data blocks with references to their unique copies. This creates dependencies between files that contain similar content and complicates the management of data in the system. In the work presented in this thesis, we have addressed the problem of data migration and load balancing, where files are remapped between different volumes because of system expansion or maintenance.

The challenge of determining which files and blocks to migrate has been studied extensively for systems without deduplication. In the context of deduplicated storage, however, only simplified migration scenarios were considered and those were not extended into the broader load balancing problem.

In our work we have formulated the general migration problem of deduplicated systems as an optimization problem whose objective is to minimize the system’s size while ensuring that the storage load is evenly distributed between the system’s volumes, and that the network traffic required for the migration does not exceed its allocation. We extended the migration problem to address the load balancing problem limitations.

We then created an algorithm based on the ILP formulation, to solve the migration problem. We then compared it’s results to two other algorithms solving the same generated migration and load balancing problem: the greedy algorithm and the clustering algorithm. Our ILP algorithm manages to consistently obtain the best solutions to the problem though it requires significantly larger execution times.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information
DisclaimerRecent theses may have not yet been approved by the Technion Senate, and are provided here for the purpose of fast dissemination of knowledge only. Final approval of the Technion Senate is needed for a thesis to be used for the partial fulfillment of the requirements for the degree of M.Sc. or Ph.D.

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2022/MSC/MSC-2022-42), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2022
To the main CS technical reports page

Computer science department, Technion
admin