Reference count propagation

• US 9,357,004 B2
• Filed: 08/06/2015
• Issued: 05/31/2016
• 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: Beaverson, Arthur J., Chitrapu, Kishore, Czerkowicz, John Michael, Manjanatha, Sowmya
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/819,479
• Publication Number:
  US 20160057217A1
• Time in Patent Office: 299 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• 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 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 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;

wherein ownership of object names are assigned to different nodes, each object name being assigned to a single owner node, and wherein the one node assigned ownership initiates an instance reconciliation for the object comprising;

the owner node receiving messages from all of the local nodes concerning the number of instances of the object at each respective node;

the owner node calculating a desired number and location of instances of the object across the networked nodes; and

the owner node instructing the other nodes to add or delete instances of the object according to the calculated number and location.

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

the owner node initiates a step of determining a global reference count GRC comprising a sum of the LRC'"'"'s across the networked nodes.

3. The medium of claim 2, wherein the GRC 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 GRC determining step includes:

implementing an eventual consistency network protocol among the nodes for deallocating instances.

5. The medium of claim 1, wherein:

the local object stores collectively comprise a namespace of the globally unique object names.

6. The medium of claim 5, wherein:

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.

7. The medium of claim 5, wherein:

a file system uses the local object stores collectively as a method to store all persistent data of the file system.

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

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

collections of file system objects also comprise objects of the object store, 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 derived from all of the objects of the file system, such that every object in the namespace file system is accessible through the root object.

9. The medium of claim 1, wherein:

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

10. The medium of claim 9, wherein:

the fingerprint comprises a hash of the object content.

11. The medium 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.

12. The medium of claim 1, wherein:

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

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

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

14. The medium of claim 1, wherein:

a storage system uses the local object stores collectively as a method to store all persistent data of the storage system.

15. The medium of claim 1 wherein:

the owner node calculates the desired number and location of instances of the object according to a service level agreement.