Method to efficiently track I/O access history using efficient memory data structures
First Claim
1. A computer-implemented method for determining access patterns of data stored in a data processing system, the method comprising:
- responsive to receiving a request to access a first data block, recording in a first memory device an access indicator that indicates a first identifier, of the first data block, in association with a time period at which the first data block was accessed, wherein the access indicator is a bloom filter, and a plurality of functions of an identifier of a particular data block are used to identify a corresponding plurality of bit positions in an access bitmap, a value of each bit at the plurality of bit positions together indicating access of the particular data block;
generating a memory-efficient data structure (MEDS) based on a plurality of access indicators recorded in the first memory device, representing an access pattern corresponding to the time period during which the first data block was accessed;
compressing access information from the plurality of access indicators, wherein the MEDS occupies less storage space on a second memory device as compared to an amount of storage space that the plurality of access indicators occupy on the first memory device;
subsequently in response to a request for accessing a second data block, uncompressing the access information stored in the MEDS before applying a query function to a second identifier of the second data block, wherein the query function returns a value based on data stored in the MEDS to indicate whether the second data block is associated with an access pattern represented by the MEDS; and
Performing a storage management action based on the value returned by the query function, the storage management action including pre-fetching a data block, caching a data block, or evicting a data block, depending on the value returned by the query function.
10 Assignments
0 Petitions
Accused Products
Abstract
An embodiment is described in which a memory device stores a record of I/O accesses to data blocks. And each access record indicates which data block was accessed and during which time period the access occurred. A memory-efficient data structure (MEDS) may be generated and stored in a cache or storage device and the access data moved from the memory device into the MEDS. The MEDS represents blocks that were accessed during a particular time period. When a second data block is accessed, a query function is applied to the second block'"'"'s identifier to return a value based on data stored in the MEDS. The return value from the query function indicates whether the second data block was accessed during the particular time period associated with the MEDS. A storage management action is performed based on whether the second data block was accessed during the particular time period.
57 Citations
16 Claims
-
1. A computer-implemented method for determining access patterns of data stored in a data processing system, the method comprising:
-
responsive to receiving a request to access a first data block, recording in a first memory device an access indicator that indicates a first identifier, of the first data block, in association with a time period at which the first data block was accessed, wherein the access indicator is a bloom filter, and a plurality of functions of an identifier of a particular data block are used to identify a corresponding plurality of bit positions in an access bitmap, a value of each bit at the plurality of bit positions together indicating access of the particular data block; generating a memory-efficient data structure (MEDS) based on a plurality of access indicators recorded in the first memory device, representing an access pattern corresponding to the time period during which the first data block was accessed; compressing access information from the plurality of access indicators, wherein the MEDS occupies less storage space on a second memory device as compared to an amount of storage space that the plurality of access indicators occupy on the first memory device; subsequently in response to a request for accessing a second data block, uncompressing the access information stored in the MEDS before applying a query function to a second identifier of the second data block, wherein the query function returns a value based on data stored in the MEDS to indicate whether the second data block is associated with an access pattern represented by the MEDS; and Performing a storage management action based on the value returned by the query function, the storage management action including pre-fetching a data block, caching a data block, or evicting a data block, depending on the value returned by the query function. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A non-transitory computer-readable storage medium storing instructions for determining access patterns of data stored in a data processing system, the instructions that when executed by one or more processors, cause the one or more processors to:
-
record, responsive to receipt of a request to access a first data block, in a first memory device an access indicator that indicates a first identifier, of the first data block, in association with a time period at which the first data block was accessed, wherein the access indicator is a bloom filter, and a plurality of functions of an identifier of a particular data block are used to identify a corresponding plurality of bit positions in an access bitmap, a value of each bit at the plurality of bit positions together indicating access of the particular data block; generate a memory-efficient data structure (MEDS) based on a plurality of access indicators recorded in the first memory device, the MEDS representing an access pattern corresponding to the time period during which the first data block was accessed; compress access information from the plurality of access indicators, wherein the MEDS occupies less storage space on a second memory device as compared to an amount of storage space that the plurality of access indicators occupy on the first memory device; uncompress the access information stored in the MEDS before apply a query function, in response to a request for access to a second data block, to a second identifier of the second data block, wherein the query function returns based on data stored in the MEDS, an indication of whether the second data block was accessed during the time period associated with the MEDS; and Perform a storage management action based on the indication returned by the query function, the storage management action including pre-fetching a data block, caching a data block, or evicting a data block, depending on the value returned by the query function. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
Specification