REFERENCE COUNT PROPAGATION

• US 20130110894A1
• Filed: 12/21/2012
• Published: 05/02/2013
• Est. Priority Date: 05/13/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: SimpliVity Corporation (Hewlett-Packard Enterprise Company)
• Inventors: Chitrapu, Kishore, Czerkowicz, John Michael, Manjanatha, Sowmya, BEAVERSON, Arthur J.
• Granted Patent: US 8,898,195 B2
• Time in Patent Office: Days
• US Class Current: 707/827
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: H04L 67/1087 using cross-functional networking aspects

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.

Claims

1. A computer-readable medium containing executable program instructions for performing a method comprising:

in a plurality of networked nodes for sharing of stored 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 references to object names, independent of any object instance stored on the local node, the LRC being maintained as a signed integer,

wherein a de-referencing of an object name can generate a negative LRC value.

2. The medium of claim 1, wherein the method includes:

determining a global reference count GRC comprising a sum of the LRC'"'"'s.

3. The medium of claim 2, wherein the determining step includes:

identifying object instances for de-allocation when the GRC is determined to be zero.

4. The medium of claim 3, wherein the determining step includes:

implementing an eventual consistency network protocol among the nodes for determining if objects may be de-allocated.

5. The medium of claim 3, wherein the determining step includes:

assigning ownership of a range of object identifiers to one of the network nodes, wherein the one node initiates the determining step for all or a subset of the range.

6. The medium of claim 1, wherein the method step includes:

maintaining a local object store on each node, wherein the local object stores collectively comprise a namespace of the globally unique object names.

7. The medium of claim 6, wherein the method includes:

the local object store maintains a local mapping index of object name, LRC and a pointer to any physical object location where the object is stored on the local object store.

8. The medium of claim 1, wherein the method includes:

each object has an object fingerprint derived from the object'"'"'s content as its object name.

9. The medium of claim 8, wherein the method includes:

the fingerprint comprises a hash of the object content.

10. The medium of claim 6, wherein the method includes:

a file system using the object stores on one or a plurality of the nodes in a peer-to-peer network storage system collectively as a method to store all persistent data of the file system.

11. The medium of claim 10, wherein the method includes:

all file system data, metadata and files comprise objects of the object store(s), each object having an object fingerprint as its object name;

collections of file system objects also comprise objects of the object store(s), each collection comprising a mapping of a plurality of the file system objects and having its own object fingerprint derived from the contents of the collection, wherein a change to one or more objects of the collection changes the collection object fingerprint; and

a file system root object having a root object fingerprint, such that every object in the namespace file system is accessible through the root object.

12. The method of claim 1, wherein the method includes:

selecting, based on network or system performance or reliability, one or more of the nodes as location(s) for storing one or more instances of an object independent of the object name.

13. The medium of claim 1, wherein the method includes:

the sharing of the stored objects comprises communicating between nodes with regard to object names, LRCs and locations of stored objects.

14. The medium of claim 6, wherein the method includes:

when an application de-references an object name and an instance of the object is not stored on a local object store, the local object store generates an LRC of negative one.

15. The medium of claim 6, wherein the method includes:

a storage system using the object stores on one or a plurality of the nodes in a peer-to-peer network storage system collectively as a method to store all persistent data of the storage system.

16. A computer readable medium containing executable instructions for performing

a method of tracking references to data objects in a distributed peer-to-peer storage system operating on a plurality of networked nodes, the objects having globally unique names across the networked nodes, each node having a local object store for naming and storing objects on the local node, and the local object stores sharing the objects,

the method comprising:

determining, on each of a plurality of local nodes, one or more locations for storing an instance of a data object on the local node;

mapping, on each of a plurality of local nodes, the one or more locations of the stored instance on the local node to the object name, wherein the location does not change the object name; and

maintaining, on each of a plurality of local nodes, a local reference count LRC of references to object names, the value of the LRC comprising a sum of reference count adjustments for the object on the local node, wherein the LRC is independent of whether any instance of the referenced object is stored on the local node.

17. A computer readable medium containing executable program instructions for performing a method comprising:

for a plurality of networked nodes, each node having a local object store for storing objects on the respective node, the objects having globally unique names across the networked nodes;

the local object stores sharing one or more of the objects; and

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 references to the respective object;

maintaining a local reference count LRC of references to object names on each node, the value of the LRC comprising a sum of reference count adjustments on the local node, wherein the LRC is independent of any instance of the referenced object being stored in the local object store so as to allow a negative value of the LRC; and

determining a global reference count GRC comprising a sum of the LRCs.

18. The medium of claim 17, wherein:

the application comprises a file system or a storage system.

19. 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;

the local object stores sharing one or more of the objects; and

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 references to the respective object;

means for maintaining a local reference count LRC of references to object names on each node, the value of the LRC comprising a sum of reference count adjustments on the local node, wherein the LRC is independent of any instance of the referenced object being stored in the local object store so as to allow a negative value of the LRC; and

means for determining a global reference count GRC comprising a sum of the LRCs.

20. 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;

the local object stores sharing one or more of the objects; and

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 references to the respective object;

means for maintaining a local reference count LRC of references to object names on each node, the value of the LRC comprising a sum of reference count adjustments on the local node, wherein the LRC is independent of any instance of the referenced object being stored in the local object store so as to allow a negative value of the LRC; and

means for selecting, based on network or system performance or reliability, one or more of the local object stores as locations for storing object instances independent of the object name.