Context-based read-ahead for B+ tree data structures in a deduplication system

1. A computer-implemented method of performing deduplication backup operations of data maintained by a file system in a multi-layer deduplication backup system, comprising:

maintaining a read-ahead cache between a deduplication layer executing the deduplication backup operations in which only a single copy of each data object is stored, and a namespace layer storing a B+Tree data structure of files processed by the backup operations, wherein the B+Tree stores key-value pairs in a lowest level of a tree structure, the key-value pairs representing pointers that point to pages to be accessed in response to a backup operation;

receiving, from a user scan request requiring multiple synchronous responses by the file system to an I/O layer coupled between the deduplication layer and a storage layer containing storage devices, a data access instruction that specifies the pages to be accessed in a data store contained in the storage layer, wherein the read-ahead cache reads the pages from the I/O layer;

storing in the B+Tree, page numbers of pages following a first page of data and forming a linear set of data allowing batch processed, context-based data accesses by the backup system using both synchronous and asynchronous accesses of the data stored in the B+Tree, wherein the pages following the first page of data are catalogued by date and time of creation;

reading the first page of the pages synchronously with a scan operation performed on blocks of the files;

preparing a read-ahead context array using pointers of pointer and key pairs of the B+Tree, wherein the pointers point to respective leaf pages of the B+Tree, by loading pointers for pages after the first page based on a hint provided as user input and comprising an identification of specific subsequent pages after the first page, wherein the specific subsequent pages may not be sequential pages;

loading from the read-ahead context array, the read-ahead cache with a plurality of subsequent pages of the specific subsequent pages based on an indication of linear access based on temporal parameters, and an indication of a number of the plurality of subsequent pages after the first page as specified in the scan operation; and

reading, through I/O layer fetches, the plurality of subsequent pages asynchronously with the scan operation from the read-ahead cache, and as a single batch of pages, so as to require no waiting for acknowledgement from the I/O layer for each of the subsequent page reads in which the subsequent pages are not stored contiguously the storage devices and in which a B+Tree scan results in random reads for the deduplication backup operations.

2. The method of claim 1 wherein the read-ahead cache is configured to be of a defined size determined by the number of the plurality of subsequent pages, and wherein the read-ahead cache represents pre-fetch window for a context of the scan operation, and further wherein the indication of linear access corresponds to a respective date and time of creation for each page of the plurality of subsequent pages.

3. The method of claim 2 further comprising maintaining an array of the first and plurality of subsequent pages in the read-ahead cache in a rotating log manner.

4. The method of claim 2 wherein the read ahead context array comprises an array of page numbers prepared by loading pointers after a first scan leaf page of the B+Tree data structure.

5. The method of claim 4 wherein a number of pages obtained from the read ahead cache is equal to a read ahead window size.

6. The method of claim 5 wherein the multiple sequential pages are automatically catalogued based on a creation time and are indexed by the pointers loaded after the first scan leaf page.

7. The method of claim 4 wherein the B+Tree references data stored in the storage layer, and wherein the pages comprise a single copy of data objects stored in the data store.

8. A computer program product comprising a non-transitory computer usable medium having machine readable code embodied therein for performing deduplication backup operations of data maintained by a file system in a multi-layer deduplication backup system, by:

maintaining a read-ahead cache between a deduplication layer executing the deduplication backup operations, and a namespace layer storing a B+Tree data structure of files processed by the backup operations in which only a single copy of each data object is stored, wherein the B+Tree stores key-value pairs in a lowest level of a tree structure, the key-value pairs representing pointers that point to pages to be accessed in response to a backup operation;

receiving, from a user scan request requiring multiple synchronous responses by the file system to an I/O layer coupled between the deduplication layer and a storage layer containing storage devices, a data access instruction that specifies the pages to be accessed in a data store contained in the storage layer, wherein the read-ahead cache reads the pages from the I/O layer;

storing in the B+Tree, page numbers of pages following a first page of data and forming a linear set of data allowing batch processed, context-based data accesses by the backup system using both synchronous and asynchronous accesses of the data stored in the B+Tree, wherein the pages following the first page of data are catalogued by date and time of creation;

reading the first page of the pages synchronously with a scan operation performed on blocks of the files;

preparing a read-ahead context array using pointers of pointer and key pairs of the B+Tree, wherein the pointers point to respective leaf pages of the B+Tree, by loading pointers for pages after the first page based on a hint provided as user input and comprising an identification of specific subsequent pages after the first page, wherein the specific subsequent pages may not be sequential pages;

loading from the read-ahead context array, the read-ahead cache with a plurality of subsequent pages of the specific subsequent pages based on an indication of linear access based on temporal parameters, and an indication of a number of the plurality of subsequent pages after the first page as specified in the scan operation; and

reading, through I/O layer fetches, the plurality of subsequent pages asynchronously with the scan operation from the read-ahead cache, and as a single batch of pages, so as to require no waiting for acknowledgement from the I/O layer for each of the subsequent page reads in which the subsequent pages are not stored contiguously the storage devices and in which a B+Tree scan results in random reads for the deduplication backup operations.