Emc IP Holding Company LLC

Tony T Wong

Abhinav Duggal

Hemanth Satyanarayana

Smriti Thakkar

Ramprasad N Chinthekindi

Rahul Goyal

Rahul Nihalani

Pei Jie Sim

Joseph Jobi

Ranganathan Dhathri Purohith

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

Methods and systems for managing data in a distributed system are disclosed. The distributed system may include devices used by users (e.g., clients) and devices in which data is stored for future accessibility (e.g., storage providers). A data storage system may manage the data for the clients. To manage the data efficiently, the data storage system may perform an integrated process of both verifying that segments of files believed to be stored are actually stored and segments of files that no longer need to be stored are removed. The process may not be performed in real-time as files that no longer need to be stored are identified (e.g., as deletion requests are received). Rather, the integrated process may employ a garbage collection process where deletion conditions for segments are checked intermittently over time, and files are verified.

Method or apparatus to integrate physical file verification and garbage collection (GC) by tracking special segments

An intelligent method of scheduling garbage collection (GC) in a storage system. A GC scheduler obtains capacity utilization and ingest rate of the storage system and calculate therefrom a predicted capacity utilization. When the predicted capacity utilization reaches a threshold, the GC scheduler invokes GC, but otherwise skips GC until such time as predicted capacity utilization reaches the threshold. The ingest rage may be calculated by performing linear fit on past data ingest. The GC scheduler may calculate predicted capacity utilization periodically according to preset period. The GC scheduler may calculate the predicted capacity utilization to a future date beyond the next period. The future date may be at least as far as the next period plus total ingest time.

Intelligent scheduling for garbage collection

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.

Post-processing global deduplication algorithm for scaled-out deduplication file system

Systems and methods for verifying files in bulk in a file system. When files are represented by a segment tree, the levels of the segment trees are walked by level such that that multiple files are verified at the same time in order to identify missing segments. Then, a bottom up scan is performed using the missing segments to identify the files corresponding to the missing segments. The missing files can then be handled by the file system.

Bulk file verification

Embodiments for allocating and reclaiming memory using dynamic buffer allocation for a slab memory allocator. The method keeps track of a count of a total number of worker threads and a count of a total number of quiesced threads, and determines if there is any free slab memory. If there is no free slab memory, the method triggers an out of memory event and increments the count of the total number of quiesced threads. It reclaims all objects currently allocated in an object pool, and allocates a buffer of a next smaller size than an original buffer until a sufficient amount of slab memory is freed.

Slab memory allocator with dynamic buffer resizing

Embodiments for a mostly unique file selection process for a deduplication backup system are described. The process assigns tags to files. A tag serves as a hint about the similarity of files in a deduplication file system. It is expected that files from the same client machine will be assigned the same tag. The tag is the smallest unit of migration and serves as a hint of the similarity of the files. The MUFS process measures the uniqueness using a u-index that is a function of the total unique size of a tag relative to the total size of the tag. A load balancer then selects the most unique tags for migration to free the maximum space. It uses the u-index to measure the uniqueness percentage of a tag, so that tags with the highest u-index are selected for migration to free up maximum space on the source node.

Mostly unique file selection method for deduplication backup systems

Embodiments for a memory efficient perfect hashing for large records. A container ID set is divided into multiple fixed range sizes. These ranges are then mapped into perfect hash buckets until each bucket is filled to uniformly distribute the container IDs across different perfect hash buckets so that the number of CIDs in every perfect hash bucket is the same or nearly the same. Individual perfect hash functions are created for each perfect hash bucket. With container IDs as keys, the process maps n keys to n positions to reduce any extra memory overhead. The perfect hash function is implemented using a compress, hash, displace (CHD) algorithm using two levels of hash functions. The level 1 hash functions divides the keys into multiple internal buckets with a defined average number of keys per bucket. The CHD algorithm iteratively tries different level 2 hash variables to achieve collision-free mapping.

Memory efficient perfect hashing for large records

Embodiments for dynamically resizing buffers for a slab allocator process are described. The slab allocator informs the consumer that the memory buffer must be shrunk to a smaller size. A buffer allocation process dynamically reclaims portions of larger memory buffers to make room for a smaller allocation by shrinking data objects in larger slabs and returning slabs to reserve or free slab lists. Initially a large limit is set, and it is dynamically reduced once all the available memory is exhausted. This allows the slab allocator to adapt to the workload.

A perfect hash vector (PHVEC) is created to track segments in a deduplication file system. Files are represented by segment trees having hierarchical segment levels. Containers store the segments and fingerprints of segments. Upper-level segments are traversed to identify a first set of fingerprints of each level. These fingerprints correspond to segments that should be present. The first set of fingerprints are hashed and bits are set in the PHVEC corresponding to positions from the hashing. The containers are read to identify a second set of fingerprints. These fingerprints correspond to segments that are present. The second set of fingerprints are hashed and bits are cleared in the PHVEC corresponding to positions from the hashing. If a bit was set and not cleared, a determination is that there is at least one segment missing. If all bits set were also cleared, a determination is that no segments are missing.

Physical file verification

According to one embodiment, fingerprints of segment trees are scanned, each segment tree representing one of the files in a filesystem namespace. For each of the fingerprints representing a segment, setting a corresponding bit in a live reference vector (LRV) to indicate that the segment has been referenced by a file in the filesystem namespace. A file index mapping fingerprints to storage locations of segments is scanned, including, for each fingerprint found in the file index, setting a corresponding bit in a live index vector (LIV) to indicate that the fingerprint exists in the file index. The LR vector and the LI vector are compared to determine whether there is any mismatch. A garbage collection operation is performed in response to determining that the LR vector and the LI vector are matched.

Method and system for verifying files for garbage collection

Embodiments are directed to perfect physical garbage collection (PPGC) process that uses a NUMA-aware perfect hash vector. The process splits a perfect hash vector (PHVEC) into a number of perfect hash vectors, wherein the number corresponds to a number of nodes having a processing core and associated local memory, directs each perfect hash to a respective local memory of a node so that each perfect hash vector accesses only a local memory, and assigns fingerprints in the perfect hash vector to a respective node using a mask function. The process also performs a simultaneous creation of perfect hash vectors in a multi-threaded manner by scanning the Index once.

Growing community of inventors

Milpitas, CA, United States of America

Tony T Wong