A joint dedupe-fountain coded archival storage

Abstract

An erasure-coded archival file storage system is presented using a chunk-based deduplication mechanism and fountain codes for space/time efficient operation. Unlike traditional archival storage, this proposal considers the deduplication operation together with correction coding in order to provide a reliable storage solution. The building blocks of deduplication and fountain coding processes are judiciously interleaved to present two novel ideas, reducing memory footprint with weaker hashing and dealing with the increased collisions using correction coding, and applying unequal error protection to deduplicated chunks for increased availability. The combination of these two novel ideas made the performance of the proposed system stand out. For example, it is shown to outperform one of the replication-based as well as RAID data protection schemes. The proposed system also addresses some of the fundamental challenges of today's low-cost deduplicated data storage systems such as hash collisions, disk bottleneck and RAM overflow problems, securing savings up to 90% regular RAM use.