CPU-efficient cache replacment with two-phase eviction

A non-transitory computer readable medium comprising instructions to be executed in a processor of a computer system, the instructions when executed in the processor cause the computer system to carry out a method of managing a cache of a computer system using a cache data structure that includes a cold queue, a ghost queue, and a hot queue, the hot queue configured as a ring buffer that includes a plurality of storage locations, wherein each of the storage locations has at least two bits associated with the storage location, the at least two bits indicating a status of contents within the storage location of the hot queue, the method comprising:

• receiving a first input/output (I/O) operation comprising a first location identifier of a first data item within the computer system;
• determining that the first location identifier is stored within the ghost queue of the cache data structure;
• upon determining that the first location identifier is stored within the ghost queue, (a) mapping the first location identifier to a first mapping data of the first data item, and (b) scanning the ring buffer of the hot queue, and for each storage location of the ring buffer scanned:
• determining a value of the at least two bits of the storage location;
• in response to the value of the at least two bits indicating a cache hit:
• (a) modifying the value of the at least two bits, and (b) setting a page fault bit to TRUE, wherein the page fault bit is located within a page table entry pointing to a memory page to which the first location identifier resolves, wherein the page table entry is an entry within a page table stored within the computer system;
• and
• the value of the at least two bits indicating that the storage location is available for addition of new data, choosing the storage location, and adding the first location identifier and the first mapping data to the chosen storage location of the hot queue.

A computer system comprising:

• a cache;
• a cache data structure comprising a cold queue, a ghost, queue, and a hot queue, the hot queue configured as a ring buffer that includes a plurality of storage locations, wherein each of the storage locations has at least two bits associated with the storage location, the at least two bits indicating a status of contents within the storage location of the hot queue;
• and
• a processor, wherein the processor is programmed to carry out a method managing the cache of the computer system, the method comprising:
• receiving a first input/output (I/O) operation comprising a first location identifier of a first data item within the computer system;
• determining that the first location identifier is stored within the ghost queue of the cache data structure;
• upon determining that the first location identifier is stored within the ghost queue,(a) mapping the first location identifier to a first mapping data of the first data item, and (b) scanning the ring buffer of the hot queue, and for each storage location of the ring buffer scanned:
• determining a value of the at least two bits of the storage location;
• in response to the value of the at least two bits indicating a cache hit:
• (a) modifying the value of the at least two bits, and (b) setting a page fault bit to TRUE, wherein the page fault bit is located within a page table entry pointing to a memory page to which the first location identifier resolves, wherein the page table entry is an entry within a page table stored within the computer system;
• and
• in response to the value of the at least two bits indicating that the storage location is available for addition of new data, choosing the storage location and adding the first location identifier and the first mapping data to the chosen storage location of the hot queue.