Netapp, Inc.

Hewlett Packard Enterprise Development LP

Praveen Killamsetti

Tomasz Barszczak

Rohini Raghuwanshi

Ammar Ekbote

Monil Sanghavi

Alok Sharma

Bipul Raj

Rajat Sharma

Bharadwaj Vellore Ramesh

Venkata Vijay Chaitanya Challapalli

Satbir Singh

Sudhanshu Gupta

Anirudha Kumar

Kumar Thangavelu

Ashish Shukla

Shishir Mondal

Subramaniam Periyagaram

Michael E Root

Naveen Bali

A computer implemented method may include: storing key-value pairs in an index in persistent storage, where indirect nodes of the index include pointers, where each pointer identifies an index portion and includes a generation identifier for the identified index portion, where the index comprises a plurality of snapshots associated with a plurality of generations; receiving a request to read data of a particular snapshot of the index, wherein the particular snapshot is associated with a particular generation of the plurality of generations; in response to the request, performing a traversal starting from a particular root node associated with the particular generation; and providing the requested data based on the traversal.

Generating snapshots of a key-value index

A computer implemented method may include: receiving write requests to add key-value pairs to an index; storing the key-value pairs in a buffer of an indirect node of the index; determining whether the buffer of the indirect node exceeds a threshold level; and in response to a determination that the buffer of the indirect node exceeds the threshold level, transferring the key-value pairs stored in the buffer of the indirect node to buffers of a plurality of child nodes, where each buffer of the plurality of child nodes is smaller than the buffer of the indirect node.

Key-value index with node buffers

Examples herein relate to re-synchronizing data between an upstream volume and a downstream volume, including by communicating data to the downstream volume, from a start point to an end point of the upstream volume, maintaining a first cursor to indicate data, from the start point to the first cursor, that has been communicated to and committed to persistent storage of the downstream volume, and maintaining a second cursor to indicate data, from the first cursor to the second cursor, that has been communicated to the downstream volume and buffered without yet being confirmed as committed to persistent storage of the downstream volume.

Data resynchronization

Examples described herein include receiving a first data write request from a host computing device, assigning a first identification to the first data write request, recording the first identification in in-flight data, transmitting the first data write request to a second storage array, receiving a first acknowledgement of the first data write request from the second storage array, and recording an indicator representing a group of acknowledgements. In some examples, the group of acknowledgements comprises the first acknowledgment.

Recordation of an indicator representing a group of acknowledgements of data write requests

According to examples, a system may include an upstream volume controller having: a processor and a non-transitory machine-readable storage medium. The storage medium may include instructions executable by the processor to freeze an upstream volume, the upstream volume being in a replication set with a downstream volume, receive a snapshot creation request, create a snapshot of the upstream volume, and send one of a snapshot permit message or a snapshot abort message to a downstream volume processor. The instructions may also be executable by the processor to unfreeze the upstream volume responsive to at least one of the sending of the one of the snapshot permit message or the snapshot abort message or expiration of a timeout corresponding to a maximum time period during which the upstream volume is to remain frozen.

Freeze a volume of a replication set and unfreeze the volume based on at least one of a snapshot permit message, a snapshot abort message, and expiration of a timeout

According to examples, an apparatus may include a processor and a non-transitory machine-readable storage medium comprising instructions executable by the processor to assign a first object identifier and a data identifier to a first volume, the first object identifier being assigned exclusively to the first volume. The instructions may also be executable by the processor to identify an identifier of a second volume, determined whether the identifier of the second volume matches the data identifier, and based on a determination that the identifier of the second volume matches the data identifier of the first volume, configure a replication relationship between the first volume and the second volume.

Assignment of a data identifier to first and second volumes

A system can efficiently removes ranges of entries from a flat sorted data structure that represent stale fingerprints As part of fingerprint verification during deduplication, the system performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. During the AIRC procedure, an inode associated with a data container is selected and the FBN tuple of each deleted data block in the file is sorted in a predefined FBN order. The AIRC procedure then identifies the most recent fingerprint associated with a deleted data block. The set of non-overlapping and latest CP ranges is then used to remove stale fingerprints associated with that deleted block from the fingerprint database. A single pass through the fingerprint database identifies the set of non-overlapping and latest CP ranges, thereby improving efficiency of the storage system.

Removing overlapping ranges from a flat sorted data structure

Techniques for using a bloom filter in deduplication are described herein. A change log comprising a plurality of data blocks may be received. Values associated with the data blocks may be hashed and compared with a bloom filter. The comparison with the bloom filter identifies data blocks from the change log as unique data blocks or potential duplicate data blocks. A bit by bit comparison of the potential duplicate data blocks and previous data blocks may be performed to determine if any of the potential duplicate data blocks are identical to any of previous data blocks. Such data blocks of the change log that are identified as being identical may be deduplicated.

Techniques for using a bloom filter in a duplication operation

A method performed in a network storage system, the method including receiving a plurality of data blocks at a secondary storage subsystem from a primary storage subsystem, generating a first log that includes a first plurality of entries, one entry for each of the data blocks, in which each entry of the first plurality of entries includes a name for a respective data block and a fingerprint of the respective data block, receiving metadata at the secondary storage subsystem from the primary storage subsystem, the metadata describing relationships between the plurality of blocks and a plurality of files, generating a second log that includes a second plurality of entries, and merging the first log with the second log to generate a change log.

Systems, methods, and computer program products providing change logging in a deduplication process

A storage server is coupled to a storage device that stores data blocks, and generates a fingerprint for each data block stored on the storage device. The storage server creates a master datastore and a plurality of datastore segments. The master datastore comprises an entry for each data block that is written to the storage device and a datastore segment comprises an entry for a new data block or a modified data block that is subsequently written to the storage device. The storage server merges the entries in the datastore segments with the entries in the master datastore in memory to free duplicate data blocks in the storage device. The storage server overwrites the master datastore with the entries in the plurality of datastore segments and the entries in the master datastore to create an updated master datastore in response to detecting that the number of datastore segments meets a threshold.

Segmented fingerprint datastore and scaling a fingerprint datastore in de-duplication environments

A storage server is coupled to a storage device that stores blocks of data, and generates a fingerprint for each data block stored on the storage device. The storage server creates a fingerprints datastore that is divided into a primary datastore and a secondary datastore. The primary datastore comprises a single entry for each unique fingerprint and the secondary datastore comprises an entry having an identical fingerprint as an entry in the primary datastore. The storage server merges entries in a changelog with the entries in the primary datastore to identify duplicate data blocks in the storage device and frees the identified duplicate data blocks in the storage device. The storage server stores the entries that correspond to the freed data blocks to a third datastore and overwrites the primary datastore with the entries from the merged data that correspond to the unique fingerprints to create an updated primary datastore.

Fingerprints datastore and stale fingerprint removal in de-duplication environments

A system and method efficiently removes ranges of entries from a flat sorted data structure, such as a fingerprint database, of a storage system. The ranges of entries represent fingerprints that have become stale, i.e., are not representative of current states of corresponding blocks in the file system, due to various file system operations such as, e.g., deletion of a data block without overwriting its contents. A deduplication module performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. The output from the AIRC procedure, i.e., the set of non-overlapping and latest CP ranges, is then used to remove stale fingerprints associated with that deleted block (as well as each other deleted data block) from the fingerprint database.

System and method for removing overlapping ranges from a flat sorted data structure

A method and apparatus for deduplication of files of a storage system is described. During a gathering phase, a file may be simultaneously processed by two or more threads to produce and store content identifiers for data blocks of the file. Each file may be sub-divided into multiple file sub-portions, each file sub-portion comprising a predetermined number of data blocks. A thread may be assigned to each sub-portion of a file for processing the data blocks. The currently assigned sub-portion for each thread may be recorded and used upon a system crash to restart each scanner thread at the currently assigned sub-portion to minimize the data blocks that are re-processed. The size of a file sub-portion may be predetermined based on the organization of inode data structures representing the files (e.g., based on the maximum number of pointers that an indirect block in the inode data structure may contain).

Processing data of a file using multiple threads during a deduplication gathering phase

In a method and apparatus for scalable deduplication, a data set is partitioned into multiple logical partitions, where each partition can be deduplicated independently. Each data block of the data set is assigned to exactly one partition, so that any two or more data blocks that are duplicates of each are always be assigned to the same logical partition. A hash algorithm generates a fingerprint of each data block in the volume, and the fingerprints are subsequently used to detect possible duplicate data blocks as part of deduplication. In addition, the fingerprints are used to ensure that duplicate data blocks are sent to the same logical partition, prior to deduplication. A portion of the fingerprint of each data block is used as a partition identifier to determine the partition to which the data block should be assigned. Once blocks are assigned to partitions, deduplication can be done on partitions independently.

Growing community of inventors

Sunnyvale, CA, United States of America

Praveen Killamsetti