Merkle tree reference counts

• US 8,457,018 B1
• Filed: 06/30/2009
• Issued: 06/04/2013
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Ruef, Richard, Everson, Kurt, Biester, William Carl, Dalmatov, Nickolay
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US12/459,473
• Time in Patent Office: 1,435 Days
• Field of Search: 370/256, 370/400
• US Class Current: 370/256
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14

Abstract

A method, article of manufacture, and apparatus for managing data commonality in a Merkle tree is disclosed. Reference counts are associated with a node in the Merkle tree. Data commonality is detected and the root of the detected data commonality is determined. If a node is the root node of the detected data commonality, the nodes reference count is incremented. When an object is deleted, the root node of the object is determined. The reference count of the node is decremented. If the count reaches zero, the node is removed from the Merkle tree, and its child nodes are decremented.

Claims

1. A method for managing data commonality in a storage system using a Merkle tree having nodes with associated reference counts, comprising:

deleting an object;

determining the blocks of the object, wherein the blocks include deduplicated data blocks, wherein the deduplicated data blocks are deduplicated by applying a hash function to create signatures and the created signatures are stored in a hash index;

determining a root node of the object based on the determined blocks, wherein the root node maps data commonality across multiple objects;

decrementing the reference count of the root node, wherein decrementing the reference count of the root node includes decrementing the reference count of the root node to zero;

removing the root node from the Merkle tree;

decrementing the reference count of a child node of the removed root node; and

removing the child node if the reference count of the decremented child node is zero; and

decrementing the reference count of a child of the removed child node.

2. A system for managing data commonality in a storage system using a Merkle tree having nodes with associated reference counts, comprising a processor configured to:

delete an object;

determine the blocks of the object, wherein the blocks include deduplicated data blocks, wherein the deduplicated data blocks are deduplicated by applying a hash function to create signatures and the created signatures are stored in a hash index;

determine a root node of the object based on the determined blocks, wherein the root node maps data commonality across multiple objects;

decrement the reference count of the root node, wherein decrement the reference count of the root node includes decrementing the reference count of the root node to zero;

remove the root node from the Merkle tree;

decrement the reference count of a child node of the removed root node;

remove the child node if the reference count of the decremented child node is zero; and

decrementing the reference count of a child of the removed child node.