INVALIDATION DATA AREA FOR CACHE

• US 20150378925A1
• Filed: 06/26/2014
• Published: 12/31/2015
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: HGST Netherlands B.V. (Western Digital Corporation)
• Inventors: MISRA, Pulkit
• Granted Patent: US 9,501,418 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements

Abstract

The present disclosure relates to caches, methods, and systems for using an invalidation data area. The cache can include a journal configured for tracking data blocks, and an invalidation data area configured for tracking invalidated data blocks associated with the data blocks tracked in the journal. The invalidation data area can be on a separate cache region from the journal. A method for invalidating a cache block can include determining a journal block tracking a memory address associated with a received write operation. The method can also include determining a mapped journal block based on the journal block and on an invalidation record. The method can also include determining whether write operations are outstanding. If so, the method can include aggregating the outstanding write operations and performing a single write operation based on the aggregated write operations.

Claims

1. A cache comprising:

a journal configured for tracking data blocks stored in the cache; and

an invalidation data area configured for tracking invalidated data blocks associated with the data blocks tracked in the journal, wherein the invalidation data area is on a separate region of the cache from the journal.

2. The cache of claim 1,

wherein the journal is configured for tracking metadata for the data blocks, and wherein the metadata comprises a memory address corresponding to the data block, and

wherein the invalidation data area is configured for tracking metadata associated with the invalidated data blocks, and wherein the associated metadata comprises a memory address corresponding to the invalidated data block.

3. The cache of claim 2,

wherein the journal is configured for tracking the data blocks using journal blocks, wherein the journal blocks are configured for storing the metadata for the data blocks;

and

wherein the invalidation data area is configured for tracking the metadata associated with the invalid data blocks using invalidation records and mapped journal blocks, wherein the mapped journal blocks are configured for storing the associated metadata for the invalid data blocks, and wherein the invalidation records are configured for storing the mapped journal blocks.

4. The cache of claim 3,

wherein the metadata tracked in the journal further comprises an index into a collection of metadata stored in each journal block, and

wherein the metadata tracked in the invalidation data area further comprises an index into a collection of metadata stored in each mapped journal block.

5. The cache of claim 3, wherein the cache is configured to determine an invalidation record number associated with an invalidation record in the invalidation data area based on a corresponding journal block number associated with a journal block.

6. The cache of claim 3, wherein the cache is configured to determine a mapped journal block number associated with a mapped journal block in the invalidation area based on a corresponding journal block number associated with a journal block.

7. The cache of claim 4, wherein the index tracked in the journal is selected to have the same value as the index tracked in the invalidation data area.

8. The cache of claim 1,

wherein the memory address tracked in the invalidation data area is truncated compared to the memory address tracked in the journal, and

wherein the truncation is determined based on at least one of a storage size of an underlying storage device being cached and an offset determined based on a memory address of a block in the underlying storage device.

9. A method for invalidating a block in a cache, the method comprising:

determining a journal block tracking a memory address associated with a received write operation, wherein the journal block is stored in a journal of the cache;

determining a mapped journal block based on the determined journal block and based further on an invalidation record, wherein the mapped journal block and the invalidation record are stored in an invalidation data area of the cache;

determining whether write operations are outstanding;

if write operations are outstanding,

aggregating the outstanding write operations and performing a single write operation based on the aggregated write operations; and

if write operations are not outstanding,

performing the received write operation.

10. The method of claim 9, wherein determining the mapped journal block comprises determining a mapped journal block number for the mapped journal block by:

determining an invalidation record number by dividing a journal block number associated with the determined journal block by a capacity of the invalidation record in the invalidation data area and computing a ceiling function of the result of the division, wherein the invalidation record number identifies the invalidation record; and

determining the mapped journal block number by computing a modulo operation of the journal block number with the capacity of the invalidation record.

11. The method of claim 9, wherein determining whether write operations are outstanding comprises retrieving a field from an in-RAM data structure corresponding to the invalidation record.

12. The method of claim 9, wherein aggregating the outstanding write operations comprises:

queuing subsequent write operations;

identifying write operations that operate on the same data block; and

determining the single write operation based on the write operations that operate on the same data block.

13. The method of claim 9, wherein the invalidation data area is on a separate region of the cache from the journal.

14. The method of claim 9,

wherein the cache comprises a content locality cache;

and

wherein the journal tracks at least one of associated data blocks and independent data blocks in the content locality cache.

15. A method for recovery of a cache, the method comprising:

determining an initial reconstruction of the cache based on a journal of the cache;

for each mapped journal block in an invalidation record in an invalidation data area of the cache,

determining whether a corresponding data block tracked in the journal is valid, based on the mapped journal block; and

if the corresponding data block is determined not to be valid, evicting the corresponding data block from the initial reconstruction of the cache.

16. The method of claim 15, wherein determining the initial reconstruction comprises recovering data blocks and metadata describing the data blocks, wherein the recovered data blocks and metadata are recovered from the journal.

17. The method of claim 15, wherein determining whether the corresponding data block tracked in the journal is valid comprises comparing metadata describing the corresponding data block tracked in the journal with metadata describing the corresponding data block tracked in the mapped journal block.

18. The method of claim 17, wherein comparing the metadata comprises comparing a first memory address and first index for the corresponding data block tracked in the journal with a second memory and second index tracked in the mapped journal block.

19. The method of claim 15, wherein the invalidation data area is on a separate region of the cache from the journal.

20. The method of claim 15,

wherein the cache comprises a content locality cache;

and

wherein the journal tracks at least one of associated data blocks and independent data blocks in the content locality cache.