Patent ID: 8694554

Claim:
A system, comprising: a plurality of data storage systems; a processor configured to: break a data stream or a data block into a plurality of segments that includes at least a first segment; compute a tag for the first segment, wherein the tag comprises a summary feature set, a sketch, a hash or a fingerprint for at least a portion of the first segment; send the tag to each data storage system of at least a subset of the plurality of data storage systems, wherein a data storage system of the at least the subset of the plurality of data storage systems that receives the tag determines, based at least in part on the tag, whether the data storage system of the at least the subset of the plurality of data storage systems contains at least one segment that is similar to the first segment or at least one subsegment that is identical to a subsegment of the first segment; receive an indication from each data storage system that includes a measure of at least one of: a number of similar segments stored at each data storage system, a number of identical subsegments stored at each data storage system, or a total number of segments stored at each data storage system; select a specific data storage system of the at least the subset of the plurality of the data storage systems to store the first segment based at least in part on the indication; determine whether a portion of the first segment that is smaller than the first segment is a duplicate of a portion of a second segment stored at the specific data storage system; and store the first segment at least in part by storing a representation of the duplicate portion of the first segment; and a memory coupled to the processor and configured to provide the processor with instructions.