Merkle tree reference counts
First Claim
Patent Images
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.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
2 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.
-
Specification