Method, device and computer program product for cache management

Patent metadata

Field	Value
Publication number	US-11210228-B2
Application number	US-201916585607-A
Country	US
Kind code	B2
Filing date	Sep 27, 2019
Priority date	Oct 31, 2018
Publication date	Dec 28, 2021
Grant date	Dec 28, 2021

Abstract

Techniques perform cache management. Such techniques involve: obtaining a first cache page of the cache to be flushed, the first cache page being associated with a target storage block in a storage device; determining from the cache a set of target cache pages to be flushed, each of the set of target cache pages being associated with the target storage block; and writing data in the first cache page and data in each of the set of target cache pages into the target storage block simultaneously.

First claim

We claim:

1. A method of managing a cache, comprising:
maintaining a plurality of lists of cache pages to be flushed, the lists being associated with a respective plurality of processor cores;
obtaining, from the plurality of lists of cache pages to be flushed, a first cache page of the cache to be flushed, the first cache page being associated with a target storage block in a storage device;
determining from the plurality of lists of cache pages to be flushed a set of target cache pages to be flushed, each of the set of target cache pages being associated with the target storage block; and
writing data in the first cache page and data in each of the set of target cache pages into the target storage block simultaneously,
wherein:
the lists of cache pages to be flushed are per-core lists, and determining the set of target cache pages to be flushed from the per-core lists is a first aggregation;
the method further includes maintaining a hash bucket storing lists of cache pages to be flushed as respective buckets associated with respective different storage spaces of the storage device; and
determining the set of target cache pages to be flushed includes first determining whether a number of pages obtained from the first aggregation reaches a predetermined threshold, and when the number of pages fails to reach the predetermined threshold, executing a second aggregation using the hash bucket.

2. The method of claim 1 , wherein determining the set of target cache pages comprises:
determining, based on a specific cache page in the plurality of lists of cache pages to be flushed, a set of candidate lists of cache pages from the plurality of lists of cache pages to be flushed; and
determining, from the set of candidate lists of cache pages, at least one cache page associated with the target storage block as the set of target cache pages.

3. The method of claim 2 , wherein determining the set of candidate cache page lists comprises:
obtaining a second cache page with the earliest modification time in a first one of the plurality of lists of cache pages to be flushed;
determining whether the second cache page is associated with the target storage block; and
in response to determining that the second cache page is associated with the target storage block, adding the first list of cache pages to be flushed into the set of candidate lists of cache pages.

4. The method of claim 2 , wherein a list of cache pages to be flushed is a First Input First Output (FIFO) queue, and wherein the specific cache page is a starting cache page at a head of the FIFO queue, and
wherein determining the set of candidate lists of cache pages comprises determining one or more candidate lists of cache pages from the plurality of lists of cache pages to be flushed, the starting cache page of a candidate list of cache pages being associated with the target storage block.

5. The method of claim 4 , wherein determining the at least one cache page from the set of candidate lists of cache pages comprises:
determining relevance of cache pages in at least one candidate list with the target storage block sequentially in an order of the list until finding an unrelated cache page; and
adding cache pages associated with the target storage block into the set of target cache pages.

6. The method of claim 1 , further including use of a scheduling heap identifying respective earliest pages in the plurality of lists of cache pages to be flushed in an order of time, and wherein obtaining the first cache page includes obtaining a starting cache page from among the earliest pages according to the scheduling heap, the starting cache page having a cache page address identifying the target storage block.

7. The method of claim 6 , wherein the scheduling heap includes a plurality of nodes associated with respective different processor cores and with respective ones of the plurality of lists of cache pages to be flushed, the nodes being arranged according to timestamps of cache pages at heads of respective ones of the lists of cache pages to be flushed.

8. A device for managing a cache, comprising:
at least one processing unit; and
at least one memory coupled to the at least one processing unit and storing instructions for execution by the at least one processing unit, the instructions, when executed by the at least one processing unit, causing the device to perform acts comprising:
maintaining a plurality of lists of cache pages to be flushed, the lists being associated with a respective plurality of processor cores;
obtaining, from the plurality of lists of cache pages to be flushed, a first cache page of the cache to be flushed, the first cache page being associated with a target storage block in a storage device;
determining from the plurality of lists of cache pages to be flushed a set of target cache pages to be flushed, each of the set of target cache pages being associated with the target storage block; and
writing data in the first cache page and data in each of the set of target cache pages into the target storage block simultaneously,
wherein:
the lists of cache pages to be flushed are per-core lists, and determining the set of target cache pages to be flushed from the per-core lists is a first aggregation;
the method further includes maintaining a hash bucket storing lists of cache pages to be flushed as respective buckets associated with respective different storage spaces of the storage device; and
determining the set of target cache pages to be flushed includes first determining whether a number of pages obtained from the first aggregation reaches a predetermined threshold, and when the number of pages fails to reach the predetermined threshold, executing a second aggregation using the hash bucket.

9. The device of claim 8 , wherein determining the set of target cache pages comprises:
determining, based on a specific cache page in the plurality of lists of cache pages to be flushed, a set of candidate lists of cache pages from the plurality of lists of cache pages to be flushed; and
determining, from the set of candidate lists of cache pages, at least one cache page associated with the target storage block as the set of target cache pages.

10. The device of claim 9 , wherein determining the set of candidate cache page lists comprises:
obtaining a second cache page with the earliest modification time in a first one of the plurality of lists of cache pages to be flushed;
determining whether the second cache page is associated with the target storage block; and
in response to determining that the second cache page is associated with the target storage block, adding the first list of cache pages to be flushed into the set of candidate lists of cache pages.

11. The device of claim 9 , wherein a list of cache pages to be flushed is a First Input First Output (FIFO) queue, and wherein the specific cache page is a starting cache page at a head of the FIFO queue, and wherein determining the set of candidate lists of cache pages comprises determining one or more candidate lists of cache pages from the plurality of lists of cache pages to be flushed, the starting cache page of a candidate list of cache pages being associated with the target storage block.

12. The device of claim 11 , wherein determining the at least one cache page from the set of candidate lists of cache pages comprises:
determining relevance of cache pages in at least one candidate list with the target storage block sequentially in an order of the list until finding an unrelated cache page; and
adding cache pages associated with the target storage block into the set of target cache pages.

13. The devic

Assignees

• Emc Ip Holding Co Llc

Inventors

• Zhang Ming
• Lv Shuo

Classifications

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F12/0804 Primary

  with main memory updating (G06F12/0806 takes precedence) · CPC title