Patent ID: 8447938

Claim:
A method of backing up data stored in a deduplicated file system to disjoint media while maintaining a deduplicated state and referential locality, comprising: representing data files stored in a deduplicated filesystem as a bipartite graph of data chunks and file inodes, said representing such that a particular data chunk connected to a particular file inode in the bipartite graph represents that the particular data chunk is part of a file described by the particular file inode; partitioning the bipartite graph into a plurality of sub-graphs with no interconnectivity between the sub-graphs using a graph partitioning algorithm, said partitioning such that each sub-graph represents: a set of data chunks, and all file inodes that include data chunks in said set of data chunks; and storing the sets of data chunks and file inodes on storage media thereby backing up the file system, said storing such that all data chunks and file inodes represented by a single sub-graph are stored together on a single storage medium, and when the size of a particular set of data chunks and file inodes represented by a single sub-graph exceeds a single storage medium's storage capacity: identifying a subset of data chunks in said particular set to re-duplicate such that partitioning a new bipartite graph into a plurality of new sub-graphs representing said subset such that each new sub-graph represents a set of data chunks for at least one complete file object that does not exceed a single separate storage medium's storage capacity, and re-duplicating data chunks represented by the new sub-graphs, and storing the re-duplicated data chunks on at least one single separate storage medium such that all data chunks represented by a single sub-graph among the new sub-graphs are stored together on at least one single separate storage medium.