Emc IP Holding Company LLC

Dell Products Inc.

Smriti Thakkar

Abhinav Duggal

Tony T Wong

Ramprasad N Chinthekindi

Rahul Nihalani

Pei Jie Sim

Yu Qiu

A system partitions files, including segments identified by fingerprints. into clusters. The system counts common fingerprints by counting fingerprints which correspond to both a file cluster and another file cluster. The system counts unique fingerprints by counting fingerprints which correspond to the file cluster and/or the other file cluster. The system uses the common and unique fingerprint counts to approximate the distance between the file cluster and the other file cluster. The system identifies the smallest of distances which are approximated between all file clusters. The system merges the file cluster and the other file cluster into a merged file cluster if the approximated distance is the smallest of distances. The system determines an index corresponding to the smallest and next smallest of distances. The system determines indexes which correspond to merges of all file clusters. The system uses the maximum of indexes to identify the optimal file clustering.

Optimal cluster selection in hierarchical clustering of files

One example method includes generating a fingerprint:tag dictionary that includes a group of fingerprints and a group of tags, and the fingerprint:tag dictionary identifies, for each fingerprint, the tag or tags which include that fingerprint, computing a similarity matrix based on the fingerprint:tag dictionary, and the similarity matrix identifies, for each pair of tags in the fingerprint:tag dictionary, a relative similarity of the tags in the pair to each other, running a clustering algorithm to identify groups of similar tags in the similarity matrix, and deduplicating, based on the groups of similar tags, respective data associated with the fingerprints.

Efficient dictionary data structure to find similar backup clients

One example method includes, beginning at a parent node of a data structure, calculating a first W-index for the parent node and a left child node, calculating a second W-index for the parent node and a right child node, when the first W-index exceeds a threshold λ, marking the left child node as a candidate to be included in a sub-cluster separate from a sub-cluster that includes the parent node, when the second W-index exceeds the threshold λ, marking the right child node as a candidate to be included in a sub-cluster separate from the sub-cluster that includes the parent node, and recursively calculating respective W-indices for all other parent nodes in the data structure until all child nodes of the data structure have been assigned to a sub-cluster.

Automatic sub-cluster selection algorithm for the hierarchical clustering of file objects

One example method includes receiving at a worker node, from each deduplication filesystem (DDFS) node in a group of DDFS nodes, respective parts of a fingerprint-file object dictionary, wherein each of the parts is created using a common fingerprint mask, merging, by the worker node, the parts, scanning the merged parts to update an intersection count between file objects stored at the DDFS nodes, generating, based on the scanning, an intersection matrix, and transferring the intersection matrix to a master node.

Map reduce approach to calculating similarity matrix using a dictionary data structure in DDFS scale out architecture

Embodiments are directed to a cost-aware object selection for cloud garbage collection that deletes completely dead objects and also selects low-live objects up to a carefully selected liveness threshold value. This threshold is dynamically chosen per cloud garbage collection cycle by balancing costs including egress, input/output operations (IOPs), storage cost of cleaning partial live objects, and the storage cost incurred by leaving behind dead data by not cleaning the object. The threshold value is dynamically calculated to accommodate different cost models for different cloud providers and also caters to different costs for different storage tiers.

Cost-aware garbage collection for cloud storage

A method, apparatus, and system for redistributing files in a multi-node storage system to improve global deduplication storage savings is disclosed. A plurality of file cluster candidates are generated for a plurality of files stored at a multi-node storage system comprising a plurality of data nodes. A similarity index is determined for each of the plurality of file cluster candidates based on similarity of the files comprised in the file cluster candidate. A ranked recipe list comprising a plurality of recipes is generated. Each recipe is associated with one of the plurality of file cluster candidates, comprises a destination data node for the associated file cluster candidate, and is associated with a deduplication space savings. At least some of the plurality of files are moved between the plurality of data nodes based on the recipes in the ranked recipe list to improve deduplication space savings in the multi-node storage system.

Growing community of inventors

San Jose, CA, United States of America

Smriti Thakkar