Patent ID: 8825720
Filing Date: 2014-09-02
Classification: G06F

Abstract:
1. A method of processing data in a de-duplicated multi-controller file system, comprising: receiving a data stream; breaking the data stream into a set of continguous data segments; generating references for each of the set of continguous data segments; identifying a set of de-duplicated data segments from the set of contiguous data segments; organizing a hierarchical data structure representing the de-duplicated multi-controller file system in its entirety by a segment tree, wherein: 1) successive levels of references lead to the set of de-duplicated data segments; 2) the set of de-duplicated data segments form a bottom level of the hierarchical data structure; and 3) references referencing a bottom level data L0 segment are stored in a metadata L1 segment on a second-to-bottom level of the hierarchical data structure, such that L1 segments are parents to L0 segments; proportioning the set of de-duplicated data segments across a plurality of controllers based at least in part by limiting co-allocation of related L0 and L1 segments to a same controller; reclaiming memory using a mark-and-sweep garbage collection operation such that the single controller only marks local L0 segments previously co-allocated to a specified controller; wherein each node of the hierarchical data structure includes a portion for storing data and a portion for storing metadata of the data; and wherein each of the plurality of controllers do not share storage space with any of the other controllers in the plurality of controllers.