STORING NODES REPRESENTING RESPECTIVE CHUNKS OF FILES IN A DATA STORE

• US 20110035376A1
• Filed: 10/25/2010
• Published: 02/10/2011
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Evan R. Kirshenbaum
• Inventors: KIRSHENBAUM, EVAN R.
• Granted Patent: US 8,463,787 B2
• Time in Patent Office: Days
• 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; and

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.

2. The method of claim 1, further comprising:

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

3. The method of claim 2, 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, the method 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.

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

5. 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).

6. 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.

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

8. The method of claim 7, 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.

9. The method of claim 8, 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.

10. 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.

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

12. The method of claim 11, further comprising:

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

associating the particular node with a missing location.

13. 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.

14. 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.

15. 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.

16. 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.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

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

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

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.