Method and apparatus for computer disk cache management

In a computer disk storage system having one or more direct access storage devices, a cache and a cache controller, a method for computer disk cache management comprising the steps of:

• determining, in response to a request received from an external source for a data block, whether said data block is contained within the cache by:
• producing an index into an array of pointers by hashing an identifier of said data block;
• traversing a doubly-linked list of headers pointed to by a pointer, said pointer being located in said array of pointers at an index position, and wherein each of said headers contains a valid indicator which indicates the presence of said block in the cache and a dirty indicator which indicates whether said block in the cache has been modified;
• and
• examining the indicator in each of said headers in the doubly-linked list until said block has been located or each of said headers has been examined;
• identifying, in the event of a cache miss, a victim cache line in the cache for replacement by:
• selecting a best victim from a heap having a plurality of nodes wherein each node identifies a possible victims and wherein said best victim is indicated by a first entry in the heap;
• reordering the heap after accessing a block in the cache, by performing a local reorganization such that the heap is in least-frequently-used order further subject to an age rule;
• and
• periodically checking the dirty indicator contained in the headers and flushing a cache line containing a dirty block to the direct access storage device.