Invalidation data area for cache

• US 10,445,242 B2
• Filed: 11/21/2016
• Issued: 10/15/2019
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Misra, Pulkit
• Primary Examiner(s): Cardwell, Eric
• Application Number:
  US15/357,155
• Publication Number:
  US 20170068623A1
• Time in Patent Office: 1,058 Days
• 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 method for invalidating a block in a cache, the method comprising:

determining a first journal block that is tracking a memory address associated with a received write operation, wherein the first journal block is stored in a journal of the cache, 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;

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

determining whether further write operations are outstanding after the received write operation;

when further write operations are outstanding,

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

when no further write operations are outstanding,

performing the received write operation.

2. The method of claim 1, wherein determining the second journal block comprises determining a mapped journal block number for the second journal block by:

determining an invalidation record number by dividing a journal block number associated with the first 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.

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

4. The method of claim 1, wherein aggregating the outstanding further write operations with the received write operation 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.

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

6. A system for invalidating a block in a cache, the system comprising:

a cache comprising a journal and an invalidation data area, wherein the cache comprises a content locality cache, and wherein the journal is configured to track at least one of associated data blocks and independent data blocks in the content locality cache; and

a means for;

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

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

determining whether further write operations are outstanding after the received write operation;

when further write operations are outstanding,

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

when no further write operations are outstanding,

performing the received write operation.

7. The system of claim 6, wherein determining the second journal block comprises determining a mapped journal block number for the second journal block by:

determining an invalidation record number by dividing a journal block number associated with the determined first 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.

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

9. The system of claim 6, wherein aggregating the outstanding further write operations with the received write operation 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.

10. The system of claim 6, wherein the invalidation data area is on a separate region of the cache from the journal.