Storing nodes representing respective chunks of files in a data store

• US 7,856,437 B2
• Filed: 07/31/2007
• Issued: 12/21/2010
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kirshenbaum, Evan R.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): BUCKINGHAM, KELLYE DEE
• Application Number:
  US11/888,092
• Publication Number:
  US 20090037500A1
• Time in Patent Office: 1,239 Days
• Field of Search: 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31

Abstract

To provide a data store, nodes representing respective chunks of files are stored in a predefined structure that defines relationships among the nodes, where the files are divided into the chunks. The nodes are collected into plural groups stored in persistent storage, where some of the nodes are collected into a particular one of the groups according to a locality relationship of the some of the nodes.

Claims

1. A method executed by a computer of providing a data store, comprising:

storing, by the computer, nodes representing respective chunks of files in a predefined structure that defines relationships among the nodes, wherein the files are divided into the chunks;

collecting, by the computer, the nodes into plural groups stored in persistent storage, wherein some of the nodes are collected into a particular one of the groups according to a locality relationship of the some of the nodes, wherein each of the groups has a header portion and a data portion, the data portion containing payload data of respective chunks associated with the corresponding group, and the header portion containing hashes of the chunks associated with the corresponding group, wherein each of the hashes is calculated by applying a hash function on content of a corresponding one of the chunks in the corresponding group;

associating location indications with the nodes, wherein the location indication of a first one of the nodes includes a pending indication to indicate that the first node has not yet been written to a group in the persistent storage, and wherein the location indication of a second one of the nodes includes an indication of a group in the persistent storage that the second node is part of; and

loading one or more of the groups from the persistent storage into temporary storage to enable read operations with respect to chunks of files,

wherein the groups comprise pages in the persistent storage, wherein loading the one or more of the pages into the temporary storage comprises loading the respective one or more header portions of the one or more pages into the temporary storage without loading the respective one or more data portions.

2. The method of claim 1, further comprising:

defining a criterion regarding a maximum amount of a resource that can be consumed by pages loaded in the temporary storage; and

selecting one or more pages to unload from the temporary storage if the maximum number is exceeded.

3. The method of claim 2, wherein selecting one or more pages to unload comprises selecting the one or more pages according to recency of activity of the pages.

4. The method of claim 1, wherein storing the nodes representing respective chunks of files in the predefined structure comprises storing the nodes representing respective chunks of files in a hash-based directed acyclic graph structure (HDAG).

5. The method of claim 1, wherein collecting the some of the nodes according to the locality relationship of the some of the nodes into the particular group comprises collecting the some of the nodes into the particular group according to parent, child, and sibling relationships of the some of the nodes.

6. The method of claim 1, wherein collecting the some of the nodes into the particular group further comprises collecting the some of the nodes into the particular group according to a completeness criterion, wherein the completeness criterion causes nodes that have complete children nodes to be loaded into a same group.

7. The method of claim 6, wherein the predefined structure comprises a graph structure of the nodes, the method further comprising:

identifying which of the nodes are complete, wherein a given node is complete if the given node roots a subgraph in the graph structure where all nodes of the subgraph are present in the data store.

8. The method of claim 7, wherein at least some of the groups contain just complete nodes and at least one other of the groups contains incomplete nodes that are not complete, the method further comprising:

associating a data structure with the at least one other group to indicate nodes of the at least one other group that are later discovered to be complete.

9. The method of claim 1, further comprising:

storing a node cache in temporary storage, wherein the node cache provides a map from digests representing corresponding chunks to respective nodes, wherein each of the digests contains a respective one of the hashes of the corresponding chunk.

10. The method of claim 9, further comprising:

maintaining entries in the node cache for nodes so long as one or more other entities of the data store hold references to the nodes in the node cache.

11. The method of claim 10, wherein one or more entities of the data store that hold references to the nodes in the node cache comprise at least one of:

a parent node that holds a reference to a child node;

a group loaded in the temporary storage;

a pending node set that contains nodes that are pending to be written to a group in the persistent storage;

a miss cache that contains nodes discovered to be not in the data store;

a banned list that contains nodes that have been banned from the data store;

an index that maps nodes to groups; and

nodes that are incomplete such that the incomplete nodes refer to hole nodes that keep the incomplete nodes from being complete.

12. The method of claim 1,

wherein the location indications associated with corresponding other ones of the nodes include:

a pending indication, to indicate that the corresponding node has not yet been written to a group in the persistent storage;

a missing indication, to indicate that a digest associated with the corresponding node is known not to exist in the data store, wherein the digest includes the hash of the corresponding node;

an unknown indication, to indicate that the data store does not know whether the corresponding node is in a group or missing;

a banned indication, to indicate that the corresponding node is not allowed to be in the data store; and

an indication of a group in the persistent storage that the corresponding node is part of.

13. The method of claim 12, further comprising:

determining that a particular node is missing in the data store; and

associating the particular node with a missing location.

14. The method of claim 13, further comprising:

storing a miss cache to identify n nodes most recently discovered to be missing, wherein n is a predefined number.

15. The method of claim 1, further comprising:

receiving a request from a client to store a particular chunk;

determining a digest of the particular chunk by applying the hash function on content of the particular chunk;

determining if a node corresponding to the digest of the particular chunk is in the data store; and

in response to determining that a node corresponding to the digest of the particular chunk is not in the data store, adding the node corresponding to the digest of the particular chunk to a pending set.

16. The method of claim 1, further comprising:

receiving a request from a client to retrieve a chunk, wherein the request contains a digest of the chunk to be retrieved, the digest derived by applying the hash function on content of the requested chunk; and

responding to the request with one of;

(1) a chunk corresponding to the digest in the request if the data store contains the requested chunk; and

(2) an indication that the data store does not contain the requested chunk if the data store does not contain the requested chunk.

17. The method of claim 1, further comprising:

receiving a query request from a client regarding whether the data store contains a complete graph rooted at a particular node, wherein the query request contains a digest of the particular node; and

responding to the query request with an indication of whether or not the data store contains the complete graph rooted at the particular node.

23. The method of claim 1, wherein the header portion of the particular group further contains hashes referencing nodes not part of the particular group that have a predefined relationship to at least one of the nodes in the particular group.

24. The method of claim 23, wherein the predefined relationship is a child relationship, and wherein the hashes referencing nodes not part of the particular group include hashes to children nodes of the at least one node in the particular group.

18. A method executed by a data storage system to provide a data store, comprising:

providing, in the data store, a graph structure that specifies relationships among nodes representing chunks of files, the nodes containing digests of the chunks, wherein plural chunks make up a particular one of the files;

collecting, by at least one processor, some of the nodes into pages stored in persistent storage, wherein a particular one of the pages has a header portion and a data portion, the data portion containing payload data of respective chunks associated with the particular page, and the header portion containing first references to nodes in the particular page and second references to nodes that are not part of the particular page but are children of at least one node of the particular page, wherein collecting the some of the nodes into pages is according to a first algorithm that;

searches for a larger one of subgraphs of nodes that have not yet been written to a given page; and

writes at least some of the nodes of the larger one of the subgraphs to the given page; and

loading one or more of the pages from the persistent storage into temporary storage to enable read operations with respect to chunks of files, wherein loading the one or more pages comprises loading respective one or more header portions of the one or more pages into the temporary storage without loading respective one or more data portions.

19. The method of claim 18, further comprising:

receiving, from a requester, a chunk that represents a portion of a file;

computing a digest of the received chunk by applying a hash function on content of the received chunk;

determining whether a node corresponding to the digest is present in the data store; and

in response to determining that the node corresponding to the digest is not present in the data store, performing a procedure to add the node corresponding to the digest to the data store.

20. The method of claim 18, further comprising:

delaying performance of the first algorithm until the data store is in a less busy state; and

before performing the first algorithm, performing a second algorithm to write nodes to pages, wherein the second algorithm provides a different level of locality than the first algorithm.

25. The method of claim 18, wherein the first references and second references comprise respective digests computed based on applying a hash function to content of respective chunks.

21. A computer-readable storage medium storing instructions that when executed cause a computer to:

store nodes representing respective chunks of files in a predefined structure that defines relationships among the nodes, wherein the files are divided into the chunks; and

collect the nodes into plural pages stored in persistent storage, wherein some of the nodes are collected into a particular one of the pages according to a locality relationship of the some of the nodes, wherein each of the pages has a header portion and a data portion, the data portion containing payload data of respective chunks associated with the corresponding page, and the header portion containing hashes of the chunks associated with the corresponding page, wherein each of the hashes is calculated by applying a hash function on content of a corresponding one of the chunks in the corresponding page;

associate location indications with the nodes, wherein the location indication of a first one of the nodes includes a pending indication to indicate that the first node has not yet been written to a page in the persistent storage, and wherein the location indication of a second one of the nodes includes an indication of a page in the persistent storage that the second node is part of; and

load one or more of the pages from the persistent storage into temporary storage to enable read operations with respect to chunks of files, wherein loading the one or more of the pages into the temporary storage comprises loading the respective one or more header portions of the one or more pages into the temporary storage without loading the respective one or more data portions.

22. The computer-readable storage medium of claim 21, wherein collecting the some of the nodes into the particular page further comprises collecting the some of the nodes into the particular page according to a completeness criterion, wherein the completeness criterion causes nodes that have complete children nodes to be loaded into a same page.

26. The computer-readable storage medium of claim 21, wherein the header portion of the particular page further contains hashes referencing nodes not part of the particular page that have a predefined relationship to at least one of the nodes in the particular page.

27. The computer-readable storage medium of claim 26, wherein the predefined relationship is a child relationship, and wherein the hashes referencing nodes not part of the particular page include hashes to children nodes of the at least one node in the particular page.