Concepedia

Reclaiming space from duplicate files in a serverless distributed file system

John R. Douceur, Atul Adya, William J. Bolosky, Pál Simon, Marvin Theimer

2003 · 643 citations · 33 references

TL;DR

Farsite replicates each file across multiple desktop computers, consuming significant storage space that must be reclaimed where possible. The authors aim to reclaim space from incidental duplication so that it can be used for controlled file replication. Their approach uses convergent encryption to coalesce duplicate files into a single encrypted copy and a Self‑Arranging Lossy Associative Database (SALAD) to aggregate file content and location information in a decentralized, scalable, fault‑tolerant manner. Measurements of over 500 desktop file systems show that nearly half of the storage is occupied by duplicate files, and large‑scale simulations demonstrate that the proposed system is scalable, highly effective, and fault‑tolerant.

Abstract

The Farsite distributed file system provides availability by replicating each file onto multiple desktop computers. Since this replication consumes significant storage space, it is important to reclaim used space where possible. Measurement of over 500 desktop file systems shows that nearly half of all consumed space is occupied by duplicate files. We present a mechanism to reclaim space from this incidental duplication to make it available for controlled file replication. Our mechanism includes: (1) convergent encryption, which enables duplicate files to be coalesced into the space of a single file, even if the files are encrypted with different users' keys; and (2) SALAD, a Self-Arranging Lossy Associative Database for aggregating file content and location information in a decentralized, scalable, fault-tolerant manner. Large-scale simulation experiments show that the duplicate-file coalescing system is scalable, highly effective, and fault-tolerant.