Disk cache management techniques using non-volatile storage

Claim 2

For use in a computer system having a hard disk and non-volatile write cache memory to reduce hard disk access operations, a method for using the non-volatile write cache memory more effectively, comprising the steps of: processing each of a plurality of requests to write a block of data to the hard disk by storing the block in the non-volatile write cache memory; repeatedly checking to determine a percentage of a plurality of blocks in the non-volatile write cache memory that have not been written to the hard disk, and deciding to purge data to the hard disk when the percentage of such blocks exceeds a preselected upper threshold limit; setting a purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit; leaving the puree request flag set when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; and clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below a preselected lower threshold limit; and if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, selecting at least one block from the non-volatile write cache memory, waiting until the hard disk is not busy with a plurality of read operations, and writing said selected block to the hard disk; whereby the number of actual hard disk write accesses needed is reduced by the use of multiple decision threshold limits and Wherein the steps of selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are initiated only when the purge request flag is set.

Claim 3

The method as defined in claim 1, and further comprising: repeatedly checking for a condition in which the non-volatile write cache memory is full of blocks that have not been written to the hard disk and, if the condition is found, immediately selecting at least one block from the non-volatile write cache memory, and writing each of the selected blocks to the hard disk, without waiting for the hard disk to become idle.

Claim 4

The method as defined in claim 1, wherein: the upper threshold limit is set between 90% and 95% of the capacity of the non-volatile write cache memory; and the lower threshold limit is set between 30% and 60% of the capacity of the non-volatile write cache memory.

Claim 5

The method as defined in claim 1, and further comprising: checking the non-volatile write cache memory at the time of each read request for the presence of at least one block of data that can be written to the hard disk at approximately the same time as data are read from the hard disk; and writing data and reading data in a single operation, to effect purging of the non-volatile write cache memory without an additional hard disk access.

Claim 6

The method as defined in claim 4, wherein the step of checking the non-volatile write cache memory includes: selecting all data blocks that need to be written to the hard disk and to the same hard disk track location as data blocks requested to be read from the hard disk.

Claim 7

The method as defined in claim 5, wherein the step of checking the non-volatile write cache memory further includes: selecting from the data blocks to be written to the same hard disk track those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 8

The method as defined in claim 4, wherein the step of checking the non-volatile write cache memory includes: selecting all data blocks that need to be written to the hard disk and to the same hard disk cylinder location as data blocks requested to be read from the hard disk.

Claim 9

The method as defined in claim 7, wherein the step of checking the non-volatile write cache memory further includes: selecting from the data blocks to be written to the same hard disk cylinder those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 10

For use in a computer system having a hard disk, a read cache memory and a non-volatile write cache memory to reduce hard disk access operations, a method for using the non-volatile write cache memory more effectively, comprising the steps of: processing each of a plurality of requests to read a block of data from the hard disk by first checking to determine if the requested block is already in non-volatile write cache memory, and performing a read disk access only if the requested block is not available in non-volatile write cache memory; processing each request to write a block of data to the hard disk by storing the block in the non-volatile write cache memory; repeatedly checking to determine a percentage of blocks in the non-volatile write cache memory that have not been written to the hard disk, and deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; setting a purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit; leaving the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, selecting at least one block from the non-volatile write cache memory, waiting until the hard disk is not busy with read operations, and writing the selected one of the blocks to the hard disk; whereby the hard disk write accesses needed are reduced in number by the use of multiple decision thresholds and wherein the steps of selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk are initiated only when the purge request flag is set.

Claim 11

For use in a computer system having a hard disk, a read cache memory and a non-volatile write cache memory to reduce hard disk access operations, a method for using the non-volatile write cache memory more effectively, comprising the steps of: processing each of a plurality of requests to read a block of data from the hard disk by first checking to determine if the requested block is already in non-volatile write cache memory, and performing a read disk access only if the requested block is not available in non-volatile write cache memory; processing each request to write a block of data to the hard disk by storing the block in the non-volatile write cache memory; repeatedly checking to determine a percentage of blocks in the non-volatile write cache memory that have not been written to the hard disk, and deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; setting a purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit; leaving the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, selecting at least one block from the non-volatile write cache memory, waiting until the hard disk is not busy with read operations, and writing the selected one of the blocks to the hard disk; whereby the hard disk write accesses needed are reduced in number by the use of multiple decision thresholds and wherein the steps of selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk are initiated only when the purge request flag is set.

Claim 12

The method as defined in claim 9, and further comprising: repeatedly checking for a condition in which the non-volatile write cache memory is full of blocks that have not been written to the hard disk and, if the condition is found, immediately selecting at least one block from the non-volatile write cache memory, and writing the selected one of the plurality of blocks to the hard disk, without the hard disk becoming idle.

Claim 13

The method as defined in claim 9, wherein: the upper threshold limit is set between 90% and 95% of the capacity of the non-volatile write cache memory; and the lower threshold limit is set between 30% and 60% of the capacity of the non-volatile write cache memory.

Claim 14

The method as defined in claim 9, and further comprising: at the time of each read request that cannot be satisfied from the read cache memory, checking the non-volatile write cache memory for the presence of at least one block of data that can be written to the hard disk at approximately the same time as data are read from the hard disk; and combining data writing and data reading into a single operation, to effect purging of the non-volatile write cache memory without an additional hard disk access.

Claim 15

The method as defined in claim 12, wherein the step of checking the non-volatile write cache memory includes: selecting all data blocks that need to be written to the hard disk and to the same hard disk track location as the data to be read form the hard disk.

Claim 16

The method as defined in claim 13, wherein the step of checking the non-volatile write cache memory further includes: selecting from the data blocks to be written to the same hard disk track those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 17

The method as defined in claim 12, wherein the step of checking the non-volatile write cache memory includes: selecting all data blocks that need be written to the hard disk and to the same hard disk cylinder location as the data to be read from the hard disk.

Claim 18

The method as defined in claim 15, wherein the step of checking the non-volatile write cache memory further includes: selecting from the data blocks to be written to the same hard disk cylinder those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 19

The method as defined in claim 9, wherein the step of determining if a requested block to be read from the hard disk is already in read cache memory includes: determining if the requested block is in the read cache memory and, if so, retrieving it from the read cache memory to satisfy the request; if the requested block is not in the read cache memory, determining if it is in the non-volatile write cache memory; if the requested block is in the non-volatile write cache memory and has been written to the hard disk, moving it to the read cache memory and satisfying the request; and if the requested block is in the non-volatile write cache memory and has not been written to the hard disk, copying it to the read cache memory and satisfying the request.

Claim 20

The method as defined in claim 9, wherein the step of determining if a requested block to be read from pard disk is already in read cache memory includes: determining if the requested block is in the read cache memory and, if so, retrieving it from the read cache memory to satisfy the request; if the requested block is not in the read cache memory, determining if it is in the non-volatile write cache memory; and if the requested block is in the non-volatile write cache memory, satisfying the request from the non-volatile write cache memory.

Claim 21

For use in a computer system having a hard disk and a single non-volatile cache memory to reduce disk access operations for both reads and writes, a method for using the non-volatile cache memory more effectively, comprising the steps of: processing each one of a plurality of requests to read a block of data from the hard disk by first checking to determine if the requested block is already in the non-volatile cache memory, and performing a read disk access only if the requested block is not available in non-volatile cache memory; processing each request to write a block of data to the hard disk by storing the block in the non-volatile cache memory; repeatedly checking the non-volatile cache memory to determine a percentage of "dirty" blocks, which have been written to the non-volatile cache memory but have not been written to the hard disk, and deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; setting a purge request flag when the percentage of dirty blocks exceeds the upper threshold limit; leaving the purge request flag set when the percentage of dirty blocks falls below the upper threshold limit; clearing the purge request flag when the percentage of dirty blocks falls below the lower threshold limit; and if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, selecting at least one dirty block from the non-volatile cache memory, waiting until the hard disk is not busy with read operations, and writing the selected dirty block to the hard disk; whereby the number of actual hard disk write accesses needed is reduced by the use of multiple decision thresholds and when the steps of selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are initiated only when the purge request flag is set.

Claim 22

For use in a computer system having a hard disk and a single non-volatile cache memory to reduce disk access operations for both reads and writes, a method for using the non-volatile cache memory more effectively, comprising the steps of: processing each one of a plurality of requests to read a block of data from the hard disk by first checking to determine if the requested block is already in the non-volatile cache memory, and performing a read disk access only if the requested block is not available in non-volatile cache memory; processing each request to write a block of data to the hard disk by storing the block in the non-volatile cache memory; repeatedly checking the non-volatile cache memory to determine a percentage of "dirty" blocks, which have been written to the non-volatile cache memory but have not been written to the hard disk, and deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; setting a purge request flag when the percentage of dirty blocks exceeds the upper threshold limit; leaving the purge request flag set when the percentage of dirty blocks falls below the upper threshold limit; clearing the purge request flag when the percentage of dirty blocks falls below the lower threshold limit; and if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, selecting at least one dirty block from the non-volatile cache memory, waiting until the hard disk is not busy with read operations, and writing the selected dirty block to the hard disk; whereby the number of actual hard disk write accesses needed is reduced by the use of multiple decision thresholds and when the steps of selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are initiated only when the purge request flag is set.

Claim 23

The method as defined in claim 19, and further comprising: repeatedly checking for a condition in which the non-volatile cache memory is totally full of dirty blocks and, if the condition is found, immediately selecting at least one dirty block from the non-volatile cache memory, and writing each of the selected dirty blocks to the hard disk.

Claim 24

The method as defined in claim 19, wherein: the upper threshold limit and the lower threshold limit are set dynamically based on hard disk access workloads.

Claim 25

The method as defined in claim 21, wherein: the upper threshold limit is determined from the ratio of the number of blocks written over a long interval to the total of the number of blocks written and the number of blocks read over the same interval; and the lower threshold limit is determined as a fixed fraction of the higher threshold limit.

Claim 26

The method as defined in claim 19, and further comprising: at the time of each read request to the non-volatile cache memory that cannot be satisfied, checking the non-volatile cache memory for the presence of at least one dirty block of data than can be written to the hard disk at approximately the same time as data are read from the hard disk; and combining data writing and data reading into a single operation, to effect purging of the non-volatile cache memory without an additional hard disk access.

Claim 27

The method as defined in claim 23, wherein the step of checking the non-volatile cache memory includes: selecting all dirty blocks that need to be written to the hard disk and to the same hard disk track location as the data to be read from the hard disk.

Claim 28

The method as defined in claim 24, wherein the step of checking the non-volatile cache memory further includes: selecting from the dirty blocks to be written to the same hard disk track those dirty blocks on the disk seek path to the data to be read from the hard disk, whereby the selected dirty blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 29

A method as defined in claim 23, wherein the step of checking the non-volatile cache memory includes: selecting all dirty blocks that need to be written to the hard disk and to the same hard disk cylinder location as the data to be read from the hard disk.

Claim 30

The method as defined in claim 26, wherein the step of checking the non-volatile cache memory further includes: selecting from the dirty blocks to be written to the same hard disk cylinder those dirty blocks on the disk seek path to the data to be read from the hard disk, whereby the selected dirty blocks can be written to the hard disk and with no additional hard disk rotation delay.

Claim 31

The method as defined in claim 19, and further comprising: detecting when the non-volatile cache memory is full and a read request or a write request must store an additional block in the non-volatile cache memory; selecting a candidate block for deletion from the non-volatile cache memory to make room for the additional block; and if the selected candidate block is dirty, marking the candidate block as a "target" for subsequent purging and selecting an alternative "clean" block, which has been written to the hard disk, for deletion from the non-volatile cache memory to make room for the additional block; and wherein the step of selecting at least one dirty block for purging is based at least in part on which blocks have been designated as "targets."

Claim 32

The method as defined in claim 28, wherein: the non-volatile cache memory consists of blocks chained together on the basis of which blocks are least recently used; the step of selecting a candidate block for deletion includes selecting the least recently used block; and the step of selecting an alternative clean candidate block for deletion includes selecting the least recently used clean block.

Claim 33

Hard disk controller apparatus for reducing disk accesses needed to satisfy a plurality of read and write requests to a hard disk, the apparatus comprising: a read cache memory for storing blocks of data read from the hard disk; a non-volatile write cache memory for storing blocks of data to be written to the hard disk; means for processing each request to write a block of data to the hard disk by storing the block in the non-volatile write cache memory; means for repeatedly checking to determine the a percentage of blocks in the non-volatile write cache memory that have not been written to the hard disk; means for deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; means for setting a purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit, and leaving the purge request flag set when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; means for clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and means operative if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, for selecting at least one block from the non-volatile write cache memory, then waiting until the hard disk is not busy with read operations, and writing each of the selected blocks to the hard disk; whereby the number of actual hard disk write accesses needed is reduced by the use of multiple decision thresholds and wherein the means for selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are operative only when the purge request flag is set.

Claim 34

Hard disk controller apparatus for reducing disk accesses needed to satisfy a plurality of read and write requests to a hard disk, the apparatus comprising: a read cache memory for storing blocks of data read from the hard disk; a non-volatile write cache memory for storing blocks of data to be written to the hard disk; means for processing each request to write a block of data to the hard disk by storing the block in the non-volatile write cache memory; means for repeatedly checking to determine the a percentage of blocks in the non-volatile write cache memory that have not been written to the hard disk; means for deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; means for setting a purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit, and leaving the purge request flag set when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; means for clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and means operative if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, for selecting at least one block from the non-volatile write cache memory, then waiting until the hard disk is not busy with read operations, and writing each of the selected blocks to the hard disk; whereby the number of actual hard disk write accesses needed is reduced by the use of multiple decision thresholds and wherein the means for selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are operative only when the purge request flag is set.

Claim 35

Apparatus as defined in claim 30, and further comprising: means for repeatedly checking for a condition in which the non-volatile write cache memory is totally full of blocks that have not been written to the hard disk and, if the condition is found, immediately selecting at least one block from the non-volatile write cache memory, and writing each of the selected blocks to the hard disk.

Claim 36

Apparatus as defined in claim 30, wherein: the upper threshold limit is set at between 90% and 95% of the capacity of the non-volatile write cache memory; and the lower threshold limit is set at between 30% and 60% of the capacity of the non-volatile write cache memory.

Claim 37

Apparatus as defined in claim 30, and further comprising: means operative at the time of each read request, for checking the non-volatile write cache memory for the presence of at least one block of data that can be written to the hard disk at approximately the same time as data are read from the hard disk; and means for combining data writing and data reading into a single operation, to effect purging of the non-volatile write cache memory without additional hard disk access.

Claim 38

Apparatus as defined in claim 33, wherein the means for checking the non-volatile write cache memory includes: means for selecting all data blocks that need to be written to the hard disk and to the same hard disk track location as the data to be read from the hard disk.

Claim 39

Apparatus as defined in claim 34, wherein the means for checking the non-volatile write cache memory further includes: means for selecting from the data blocks to be written to the same hard disk track those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 40

Apparatus as defined in claim 33, wherein the means for checking the non-volatile write cache memory includes: means for selecting all data blocks that need to be written to the hard disk and to the same hard disk cylinder location as the data to be read from the hard disk.

Claim 41

Apparatus as defined in claim 36, wherein the means for checking the non-volatile write cache memory further includes: means for selecting from the data blocks to be written to the same hard disk cylinder those data blocks on the disk seek path to the data to be read from the hard disk, whereby the selected data blocks can be written to the hard disk with no additional hard disk rotation delay.

Claim 42

Hard disk controller apparatus for reducing disk accesses needed to satisfy a plurality of read and write requests to a hard disk, the apparatus comprising; a single non-volatile cache memory for storing blocks of data read from, and to be written to, the hard disk; means for processing each request to read a block of data from the hard disk by first checking to determine if the requested block is already in the single non-volatile cache memory, and performing a read disk access only if the requested block is not available in single non-volatile cache memory; means for processing each request to write a block of data to the hard disk by storing the block in the single non-volatile cache memory; means for repeatedly checking to determine the proportion of blocks in the single non-volatile cache memory that have not been written to the hard disk; means for deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; means for setting purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit, and leaving the purge request flag set when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; means for clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and means operative if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, for selecting at least one block from the single non-volatile write cache memory, then waiting until the hard disk is not busy with read operations, and writing the selected blocks to the hard disk; whereby the number of actual disk write accesses needed is reduced by the use of multiple decision thresholds and wherein the means for selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are operative only when the purge request flag is set.

Claim 43

Hard disk controller apparatus for reducing disk accesses needed to satisfy a plurality of read and write requests to a hard disk, the apparatus comprising; a single non-volatile cache memory for storing blocks of data read from, and to be written to, the hard disk; means for processing each request to read a block of data from the hard disk by first checking to determine if the requested block is already in the single non-volatile cache memory, and performing a read disk access only if the requested block is not available in single non-volatile cache memory; means for processing each request to write a block of data to the hard disk by storing the block in the single non-volatile cache memory; means for repeatedly checking to determine the proportion of blocks in the single non-volatile cache memory that have not been written to the hard disk; means for deciding whether to purge data to the hard disk based on the percentage of such blocks as compared with a preselected upper threshold limit and a preselected lower threshold limit; means for setting purge request flag when the percentage of blocks that have not been written to the hard disk first exceeds the upper threshold limit, and leaving the purge request flag set when the percentage of blocks that have not been written to the hard disk falls below the upper threshold limit; means for clearing the purge request flag when the percentage of blocks that have not been written to the hard disk falls below the lower threshold limit; and means operative if the step of deciding whether to purge to the hard disk results in a decision to initiate purging, for selecting at least one block from the single non-volatile write cache memory, then waiting until the hard disk is not busy with read operations, and writing the selected blocks to the hard disk; whereby the number of actual disk write accesses needed is reduced by the use of multiple decision thresholds and wherein the means for selecting at least one block, waiting until the hard disk is not busy, and writing to the hard disk, are operative only when the purge request flag is set.

Claim 44

Apparatus as defined in claim 38, and further comprising: means for setting the upper threshold limit and the lower threshold limit dynamically based in hard disk access workloads.

Claim 45

Apparatus as defined in claim 39 wherein: the upper threshold limit is determined from the ratio of the number of blocks written over a long interval to the total of the number of blocks written and the number of blocks read over the same time interval; and the lower threshold limit is determined as a fixed fraction of the higher threshold limit.