Granted Patent B2

US 12,468,636 · App. 17/669,131 · Granted Nov 11, 2025

Inventors: Stuart John Inglis (Cambridge, NZ); Cameron Ray Simmonds (Cambridge, NZ); Dmitry Lapik (Cambridge, NZ); Sheridan John Lambert (Cambridge, NZ)

Assignee: Daedalus Cloud LLC

G06F12/123G06F12/0802G06F2212/7201

Abstract

Claims (67)

1 . A method comprising:

receiving a request to write first data to a persistent storage device, the request comprising a first logical block addressing (LBA) value;

writing the first data to a first cache line of a cache;

updating a mapping between the first LBA value and the first cache line;

receiving a subsequent request to write second data to the persistent storage device, the subsequent request comprising the first LBA value;

determining that the first LBA value exists in the mapping;

determining a dirty cache line corresponding to the first LBA value;

updating the corresponding dirty cache line to the second data of the subsequent request;

pushing the corresponding dirty cache line onto an end of a least recently used (LRU) queue of cache lines, wherein the LRU queue maintains an order in which respective cache lines were written to the LRU queue without retaining an age of each of the cache lines;

reporting the second data as having been written to the persistent storage device;

determining that third data is to be evicted from the cache;

evicting the third data from the cache;

popping a second cache line from a head of the LRU queue;

attempting to write the third data at the second cache line to the persistent storage device; and

if the write of the third data at the second cache line to the persistent storage device fails, adding the second cache line back to the head of the LRU queue for a re-attempt at eviction.

2 . The method of claim 1 , wherein pushing the corresponding dirty cache line onto the end of the LRU queue of cache lines comprises:

removing the first cache line corresponding to the first LBA value from the LRU queue; and

pushing the first cache line corresponding to the first LBA value onto the end of the LRU queue.

3 . The method of claim 1 , further comprising:

receiving a request to read fourth data from the persistent storage device;

determining that the fourth data is in the cache; and

providing the fourth data from the cache.

4 . The method of claim 3 , wherein the request to read the fourth data comprises a second LBA value, and wherein determining that the fourth data is in the cache comprises determining that the second LBA value is in a mapping between LBA values and cache lines.

5 . The method of claim 4 , wherein providing the fourth data from the cache comprises providing the fourth data from a third cache line corresponding to the second LBA value in the mapping between LBA values and cache lines.

6 . The method of claim 1 , further comprising marking the second cache line as clean after the third data has been successfully written to the persistent storage device.

7 . The method of claim 1 , wherein determining that the third data is to be evicted from the cache comprises determining that the cache is below a threshold clean capacity.

8 . The method of claim 1 , further comprising after writing the first data to the first cache line of the cache, marking the first cache line as dirty.

9 . A system comprising:

one or more processors; and

a memory storing instructions which, when executed by the one or more processors, cause the system to:

receive a request to write first data to a persistent storage device, the request comprising a first logical block addressing (LBA) value;

write the first data to a first cache line of a cache;

update a mapping between the first LBA value and the first cache line;

receive a subsequent request to write second data to the persistent storage device, the subsequent request comprising the first LBA value;

determine that the first LBA value exists in the mapping;

determine a dirty cache line corresponding to the first LBA value;

update the corresponding dirty cache line to the second data of the subsequent request;

push the corresponding dirty cache line onto an end of a least recently used (LRU) queue of cache lines, wherein the LRU queue maintains an order in which respective cache lines were written to the LRU queue without retaining an age of each of the cache lines;

report the second data as having been written to the persistent storage device;

determine that third data is to be evicted from the cache;

evict the third data from the cache;

pop a second cache line from a head of the LRU queue;

attempt to write the third data at the second cache line to the persistent storage device; and

if the write of the third data at the second cache line to the persistent storage device fails, add the second cache line back to the head of the LRU queue for a re-attempt at eviction.

10 . The system of claim 9 , wherein the instructions further cause the system to:

receive a request to read fourth data from the persistent storage device;

determine that the fourth data is in the cache; and

provide the fourth data from the cache.

11 . The system of claim 10 , wherein the request to read the fourth data comprises a second LBA value, and wherein the instructions further cause the system to determine that the fourth data is in the cache by causing the system to determine that the second LBA value is in a mapping between LBA values and cache lines.

12 . The system of claim 9 , wherein the instructions further cause the system to:

mark the second cache line as clean after the third data has been successfully written to the persistent storage device.

13 . The system of claim 12 , wherein the instructions further cause the system to determine that the third data is to be evicted from the cache by causing the system to determine that the cache is below a threshold clean capacity.

14 . A non-transitory computer readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

receiving a request to write first data to a persistent storage device, the request comprising a first logical block addressing (LBA) value;

writing the first data to a first cache line of a cache;

updating a mapping between the first LBA value and the first cache line;

receiving a subsequent request to write second data to the persistent storage device, the subsequent request comprising the first LBA value;

determining that the first LBA value exists in the mapping;

determining a dirty cache line corresponding to the first LBA value;

updating the corresponding dirty cache line to the second data of the subsequent request;

pushing the corresponding dirty cache line onto an end of a least recently used (LRU) queue of cache lines, wherein the LRU queue maintains an order in which respective cache lines were written to the LRU queue without retaining an age of each of the cache lines;

reporting the second data as having been written to the persistent storage device;

determine that third data is to be evicted from the cache;

evict the third data from the cache;

pop a second cache line from a head of the LRU queue;

attempt to write the third data at the second cache line to the persistent storage device; and

if the write of the third data at the second cache line to the persistent storage device fails, add the second cache line back to the head of the LRU queue for a re-attempt at eviction.

Assignments (5)

Continuity (2)

References Cited (19)