Reference count propagation
First Claim
1. A non-transitory computer-readable medium containing executable program instructions for performing a method comprising:
- in a plurality of networked nodes wherein each node has a local object store, the local object stores storing objects and sharing one or more objects, the objects having globally unique names across the networked nodes and wherein the object names do not change based upon where the objects are stored on the nodes;
maintaining, at each node, a Local Reference Count LRC of local references to object names, independent of any object instance stored in the local object store, the LRC being maintained as a signed integer, wherein adjustments are made to the LRC for each local new reference and dereference and a de-referencing of an object name can generate a negative LRC value;
wherein ownership of object names are assigned to different nodes, a range of object names being assigned to one of the network nodes and the node assigned ownership initiates a Global Reference Count GRC determining step for all or a subset of the range, the GRC determining step comprising;
the owner node providing a unique tag for an object for which a GRC is to be determined;
the nodes exchanging messages with the unique tag, whereby, the other nodes provide the owner node with their LRC for the object;
the owner node calculating the GRC as a sum of the LRCs received from the other nodes and the LRC of the owner node for the object; and
if the resulting GRC is zero the owner node sending a delete message with the unique tag to the other nodes.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods and systems are provided for tracking object instances stored on a plurality of network nodes, which tracking enables a global determination of when an object has no references across the networked nodes and can be safely de-allocated. According to one aspect of the invention, each node has a local object store for tracking and optionally storing objects on the node, and the local object stores collectively share the locally stored instances of the objects across the network. One or more applications, e.g., a file system and/or a storage system, use the local object stores for storing all persistent data of the application as objects.
-
Citations
15 Claims
-
1. A non-transitory computer-readable medium containing executable program instructions for performing a method comprising:
-
in a plurality of networked nodes wherein each node has a local object store, the local object stores storing objects and sharing one or more objects, the objects having globally unique names across the networked nodes and wherein the object names do not change based upon where the objects are stored on the nodes; maintaining, at each node, a Local Reference Count LRC of local references to object names, independent of any object instance stored in the local object store, the LRC being maintained as a signed integer, wherein adjustments are made to the LRC for each local new reference and dereference and a de-referencing of an object name can generate a negative LRC value; wherein ownership of object names are assigned to different nodes, a range of object names being assigned to one of the network nodes and the node assigned ownership initiates a Global Reference Count GRC determining step for all or a subset of the range, the GRC determining step comprising; the owner node providing a unique tag for an object for which a GRC is to be determined; the nodes exchanging messages with the unique tag, whereby, the other nodes provide the owner node with their LRC for the object; the owner node calculating the GRC as a sum of the LRCs received from the other nodes and the LRC of the owner node for the object; and if the resulting GRC is zero the owner node sending a delete message with the unique tag to the other nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. An apparatus comprising:
-
a plurality of networked nodes, each node having a local object store for storing objects on the respective node and the objects having globally unique names across the networked nodes, wherein the object names do not change based upon where the objects are stored on the nodes; the local object stores sharing one or more of the objects; an application using the local object stores for storing persistent data as objects, the application requiring a reference count for each object stored on the networked nodes comprising a number of independent paths across the plurality of nodes to the respective object; means for maintaining a local reference count LRC of references to object names on each node independent of any object instance stored in the local object store, the LRC being maintained as a signed integer; wherein adjustments are made to the LRC for each local new reference and dereference, wherein a de-referencing of an object name can generate a negative LRC value; and means for determining a Global Reference Count GRC for an object, wherein ownership of object names are assigned to different nodes, a range of object names being assigned to one of the network nodes, and the node assigned ownership is configured to cause the determining means to initiate a GRC determining step for all or a subset of the range, the GRC determining means and the nodes configured to implement GRC determining steps comprising; the owner node providing a unique tag for an object for which a GRC is to be determined; the nodes exchanging messages with the unique tag, whereby, the other nodes provide the owner node with their LRC for the object; the owner node calculating the GRC as a sum of the LRCs received from the other nodes and the LRC of the owner node for the object; and if the resulting GRC is zero the owner node sending a delete message with the unique tag to the other nodes.
-
Specification