Providing an index for a data store

• US 7,725,437 B2
• Filed: 07/31/2007
• Issued: 05/25/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., Suermondt, Henri J., Lillibridge, Mark D.
• Primary Examiner(s): Fleurantin; Jean Bolte
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US11/888,154
• Publication Number:
  US 20090037456A1
• Time in Patent Office: 1,029 Days
• Field of Search: 707/1, 707/10, 707100-102, 707/640, 707650-652
• US Class Current: 707/640
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31

Abstract

Chunks are stored in a data store, where respective collections of chunks form respective files. An index that maps digests of chunks to pages containing information to recreate the chunks is provided, where the index is stored in persistent storage.

Claims

1. A method executed by a computer, comprising:

storing chunks in a data store, wherein respective collections of chunks form respective files;

providing an index that maps subsets of digests of chunks to pages containing information for recreating the chunks, wherein the index is stored in a persistent storage;

maintaining the index in plural slice files in the persistent storage;

mapping, by the computer, a first portion of a given one of the digest subsets to one of the plural slice files; and

mapping, by the computer, a second portion of the given one of the digest subsets to one of plural rows of the one slice file.

2. The method of claim 1, wherein each of the plural rows includes plural slots, at least one of the plural slots of a given row containing a check block, the method further comprising:

matching a third portion of the given one of the digest subsets to the check block of one of the at least one of the plural slots.

3. The method of claim 1, further comprising:

providing plural slice objects in temporary storage to represent the corresponding slice files; and

associating at least one cache with at least one of the slice objects, wherein the at least one cache is stored in the temporary storage and initially contains a copy of at least a portion of the corresponding slice file.

4. The method of claim 3, further comprising:

updating the at least one cache in response to receiving a new node that is to be added to the corresponding slice file, wherein the at least one cache is updated without updating the corresponding slice file.

5. The method of claim 4, further comprising:

waiting for a predetermined event before updating the corresponding slice file with updated content of the at least one cache.

6. The method of claim 5, wherein updating the corresponding slice file comprises sequentially writing content of the at least one cache to the corresponding slice file.

7. The method of claim 5, further comprising updating plural slice files with different content of plural caches in sequence.

8. The method of claim 1, further comprising:

storing, in the persistent storage, indications of which of the pages have nodes that have not been written to the index on the persistent storage; and

in response to system restart, reading the indications to load the pages associated with the indications from the persistent storage to enable update of the index with the pages associated with the indications.

9. The method of claim 8, further comprising:

removing the indication associated with a given page after all of the slices have been updated to the persistent storage at least once following the storing of the indication associated with the given page.

10. The method of claim 1, further comprising:

associating at least one cache with the index, wherein the cache is stored in a temporary storage;

associating at least one overflow table with the index, wherein the overflow table stores information of nodes that are associated with full entries of the index; and

associating at least one Bloom filter with the index.

11. A method executed by a computer, comprising:

storing chunks in a data store, wherein respective collections of chunks form respective files;

providing an index that maps subsets of digests of chunks to pages containing information for recreating the chunks, wherein the index is stored in a persistent storage, wherein a subset of each of the digests is less than an entirety of the corresponding digest; and

providing, by the computer, a collision data structure that contains entries for certain nodes that are to be written to the persistent storage, wherein the certain nodes are associated with subsets of the digests that match subsets already in the index.

12. The method of claim 11, wherein the collision data structure comprises one or both of a collision table stored in temporary storage and a collision journal stored in the persistent storage.

13. The method of claim 11, wherein the index is stored in at least one data structure having plural rows, the method further comprising:

in attempting to write information relating to a given node to a corresponding one of the rows of the index, if the corresponding row is detected to be full, then writing the information relating to the given node to at least one overflow data structure.

14. The method of claim 13, wherein writing the information relating to the given node to the at least one overflow data structure comprises writing the information relating to the given node to an overflow table in temporary storage and an overflow journal in the persistent storage.

15. The method of claim 11, further comprising:

storing the index in plural slice files in the persistent storage;

providing plural slice objects in a temporary storage to represent the corresponding slice files; and

associating at least one lookup data structure with at least one of the slice objects; and

updating the at least one lookup data structure in response to receiving a node to be added to the corresponding slice file.

16. The method of claim 15, further comprising:

in response to a query to determine if a given node exists in the data store, accessing the at least one lookup data structure.

17. The method of claim 15, wherein the lookup data structure comprises a Bloom filter.

18. A method executed by a computer, comprising:

storing chunks in a data store, wherein respective collections of chunks form respective files;

providing an index that maps digests of chunks to pages containing information for recreating the chunks, wherein the index is stored in a persistent storage;

receiving a query to determine if a plurality of nodes exist in the data store;

utilizing a first mechanism in the computer to determine, without accessing the index in the persistent storage, that each of a first subset of the plurality of nodes is not in the data store;

utilizing a second mechanism in the computer to determine, without accessing the index in the persistent storage, a corresponding page possibly associated with each of a second subset of the plurality of nodes;

ensuring that a particular page possibly associated with a particular node in the second subset is loaded;

indicating, based on the ensuring, that the particular node does not exist in the data store; and

only for a third subset of the plurality of nodes whose existence in the data store is still unknown, utilizing the index on the persistent storage to determine whether each of the third subset of nodes exists in the data store.

19. A method executed in a computer, comprising:

providing, in a data store, an index that maps digests of chunks to pages containing the chunks, wherein collections of chunks form respective files;

in response to a first query to determine whether a first digest representing a first chunk is present in the data store, loading one of the pages from persistent storage to temporary storage;

according to updated information in the temporary storage resulting from loading of the one page, providing a response to a second query to determine whether a second digest representing a second chunk is in the data store;

storing the index as plural index slice files in a persistent storage;

mapping a first portion of a given one of the digests to a particular one of the index slice files; and

mapping a second portion of the given digest to one of plural rows of the particular index slice file.

20. A computer-readable storage medium storing instructions that upon execution cause a computer to:

store chunks in a data store, wherein respective collections of chunks form respective files;

provide an index that maps subsets of digests of chunks to pages containing information for recreating the chunks, wherein the index is stored in a persistent storage;

maintain the index in plural slice files in the persistent storage; and

map a first portion of a given one of the digest subsets to one of the plural slice files; and

map a second portion of the given one of the digest subsets to one of plural rows of the one slice file.