# US 2014/0156601 A1 · Systems and methods for hierarchical reference counting via sibling trees > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156601 A1 - Document ID: US20140156601A1 - Status: Published application - Kind: A1 - Application number: 14/085,656 - Filed: 2013-11-20 - Published: 2014-06-05 - Earliest claimed: 2012-02-21 - Assignees: NetApp, Inc. - Applicants: NetApp, Inc. - Inventors: John Strunk; Douglas Santry; Sriram Venketaraman; Vaijayanti Bharadwaj - Web page: https://patentgrep.com/patent/US20140156601A1 ## CPC - G06F 3/0641: {De-duplication techniques} - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)} - G06F 16/134: {Distributed indices} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems and methods for hierarchical reference counting via sibling trees are provided. The hierarchical data structure, together with its associated operations, can efficiently maintain reference counts and significantly reduce input/output (IO) operations compared to traditional techniques. The data structure presented here is applicable to any directed acyclic graph (DAG-type) structure where reference counts are used. Various embodiments of the present invention use a data structure to maintain a “sibling pointer” (pointing to the sibling node as a way to avoid reference count updates) and a “sibling count.” When nodes in the tree diverge, the sibling pointer and sibling count are updated as opposed to directly manipulating the reference counts of the children of the diverging nodes. Various other embodiments can use additional entries or fields that allow for improved efficiency and advantages. ## Claims ### Claim at position 1 1-28. (canceled) ### Claim 29 A method for freeing nodes, comprising: maintaining, in a network storage system, a hierarchical data structure representing data stored in the network storage system, the hierarchical data structure including multiple nodes, each selected node of the multiple nodes including a sibling count to indicate a number of nodes that have the selected node as a pre-image, and a sibling pointer to point to the pre-image; analyzing a sibling count of a first node to determine if the first node can be freed, the sibling count indicating a number of nodes that have the first node as a pre-image; and freeing, when the analysis of the sibling count indicates that the first node can be freed, the first node. ### Claim 30 (depends on 29) The method of claim 29, wherein each selected node of the multiple nodes includes a link count to indicate a number of direct references to the node. ### Claim 31 (depends on 30) The method of claim 30, further comprising: analyzing the link count of the first node to determine if the first node can be freed, the link count of the first node indicating a number of direct references to the first node. ### Claim 32 (depends on 30) The method of claim 30, further comprising: receiving a deduplication request; determining whether a first node is a duplicate of a second node; and decrementing the link count of the first node and incrementing the link count of the second node to indicate that a direct reference to the first node has been modified to be a direct reference to the second node. ### Claim 33 (depends on 29) The method of claim 29, wherein each selected node of the multiple nodes includes a forward pointer to point from a node that is a pre-image to a copy of the selected node. ### Claim 34 (depends on 33) The method of claim 33, further comprising: locating the first node based on the forward pointer of a second node, the forward pointer of the second node pointing to the first node to indicate that the second node is a pre-image of the first node. ### Claim 35 (depends on 29) The method of claim 29, wherein each selected node of the multiple nodes includes a delete count to indicate a number of child nodes of the node that no longer reference the node. ### Claim 36 (depends on 35) The method of claim 35, further comprising: analyzing the delete count of the first node to determine if the first node can be freed, the delete count of the first node indicating the number of the child nodes of the first node that no longer reference the first node. ### Claim 37 (depends on 35) The method of claim 35, wherein the delete count is associated with a child pointer that indicates a descendant child node. ### Claim 38 (depends on 29) The method of claim 29, wherein freeing the first node includes resolving pointers in a copy of the first node to directly indicate any descendant child nodes associated with the first node. ### Claim 39 A storage system comprising: a processor; a non-volatile storage medium; a network interface through which to receive read requests and write requests from multiple clients via a network; a storage interface through which to access the non-volatile storage medium; a storage manager component configured to organize and store data on the non-volatile storage medium in accordance with a data structure having multiple nodes, at least some nodes of the multiple nodes including a sibling count to indicate a number of nodes that have the node as a pre-image, and a sibling pointer to point to the pre-image, wherein the data structure enables the storage manager to analyze a sibling count of a first node to determine if the first node can be freed; and a reclamation module component configured to free the first node when the storage manager determines that the first node can be freed. ### Claim 40 (depends on 39) The storage system of claim 39, wherein at least some of the multiple nodes includes a link count to indicate a number of direct references to the node, and wherein the storage manager is further configured to analyze the link count of the first node to determine if the first node can be freed, the link count of the first node indicating a number of direct references to the first node. ### Claim 41 (depends on 39) The storage system of claim 39, wherein at least some nodes of the multiple nodes include a forward pointer to point from a node that is a pre-image to a copy of the node, and wherein the storage manager is further configured to locate the first node based on the forward pointer of a second node, the forward pointer of the second node indicating the first node to indicate that the second node is a pre-image of the first node. ### Claim 42 (depends on 39) The storage system of claim 39, wherein each selected node of the multiple nodes includes a delete count to indicate a number of siblings of the node that no longer reference the node, and wherein the storage manager is further configured to analyze the delete count of the first node to determine if the first node can be freed. ### Claim 43 (depends on 39) The storage system of claim 39, wherein the reclamation module component is further configured to resolve any pointers within the data structure when the first node has only a sibling count. ### Claim 44 (depends on 39) The storage system of claim 39, wherein the data structure includes other nodes, the other nodes including a leaf node that does not have a descendant node, and wherein the data structure does not include a sibling count or associate a sibling pointer with the leaf node. ### Claim 45 A computer-readable storage device storing computer executable instructions, comprising: instructions for maintaining, in a network storage system, a hierarchical data structure representing data stored in the network storage system, the hierarchical data structure including multiple nodes, each selected node of the multiple nodes including a sibling count to indicate a number of nodes that have the node as a pre-image, and a sibling pointer to indicate the pre-image; instructions for, in response to a pointer no longer referencing a first node that is a clone of a second node, analyzing the sibling count of the first node to determine if the first node can be freed, the sibling count indicating the number of the nodes that have the first node as a pre-image, the clone being a persistent and writeable point-in-time image of the second node; and instructions for freeing, when the analysis of the sibling count indicates that the first node can be freed, the first node. ### Claim 46 (depends on 45) The computer-readable storage device of claim 45, wherein the pointer no longer referencing the first node is associated with a file associated with the first node being deleted. ### Claim 47 (depends on 45) The computer-readable storage device of claim 45, wherein the hierarchical data structure includes multiple other nodes, each other node of the multiple other nodes not including a sibling count to indicate a number of nodes that have the other node as a pre-image, nor including a sibling pointer to point to the pre-image of the other node. ### Claim 48 (depends on 45) The computer-readable storage device of claim 45, wherein the second node includes a forward pointer pointing to the first node to indicate that the second node is a pre-image of the first node, the instructions further comprising: instructions for locating the first node based on the forward pointer of the second node.