Providing an index for a data store

• US 20090037456A1
• Filed: 07/31/2007
• Published: 02/05/2009
• 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.
• Granted Patent: US 7,725,437 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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; and

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.

2. The method of claim 1, wherein providing the index that maps digests of chunks to pages comprises providing the index that maps subsets of the digests to pages.

3. The method of claim 2, further comprising:

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

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

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

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

5. The method of claim 2, further comprising:

providing at least one 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.

6. The method of claim 5, wherein the at least one collision data structure comprises a collision table stored in temporary storage and a collision journal stored in the persistent storage.

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

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

9. The method of claim 1, further comprising:

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

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.

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

11. The method of claim 10, further comprising:

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

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

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

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

15. The method of claim 14, further comprising:

maintaining the index in plural slices;

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

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

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

18. The method of claim 16, wherein the lookup data structure comprises a Bloom filter.

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

20. The method of claim 1, further comprising:

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

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

utilizing a second mechanism to determine, without accessing the index on 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.

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

22. The method of claim 21, further comprising:

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

maintaining slice objects in the temporary storage that correspond to the index slice files.

23. Instructions on a computer-usable storage medium that when executed cause a computer to:

store an index that maps digests of chunks to pages containing the chunks, wherein collections of the chunks correspond to respective files that are contained in a data store, wherein the index includes at least one first data structure in persistent storage and at least one second data structure in temporary storage; and

in response to a query to determine whether a given digest representing a chunk is present in the data store, access the at least one data structure to process the query.