Patent ID: 8005861

Claim:
A method for cluster storage comprising: receiving a data stream or a data block; breaking the data stream or the data block into segments, wherein breaking the data stream or the data block into segments is based at least in part on a value of a function calculated for a plurality of windows of bytes within the data stream or the data block; and for each segment from the data stream or the data block: selecting a cluster node, wherein the cluster node comprises an index that stores an indication of a set of segments stored on and managed by the cluster node, and wherein a cluster comprises a plurality of nodes, wherein each node comprises a data storage system that stores data by storing segments that are deduplicated; and determining whether a portion of the segment from the data stream or the data block smaller than the segment is a duplicate of a portion of a segment already managed by the cluster node; in the event that the portion of the segment from the data stream or the data block smaller than the segment is a duplicate of the portion of the segment already managed by the cluster node, storing a reference to the portion of the segment already managed by the cluster node that is used later to reconstruct the segment; and in the event that the portion of the segment from the data stream or the data block smaller than the segment is not a duplicate of the portion of the segment already managed by the cluster node, newly storing the portion of the segment and a reference to the newly stored portion of the segment that is used later to reconstruct the segment.