Methods and apparatus for information storage and retrieval using a caching technique with external-chain hashing and dynamic resource-dependent data shedding

Abstract

A method and apparatus for performing storage and retrieval in an information storage system cache is disclosed that uses the hashing technique with the external chaining method for collision resolution. In order to prevent performance deterioration due to an unrestrained growth in the length of chains, an on-the-fly record removal technique is combined with background chain-pruning processes that continually trim long chains to keep chain lengths at an acceptable equilibrium without triggering abrupt, disruptive action at the time the system senses that it is stressed. More specifically, each insertion, retrieval, or deletion of a record is an occasion to rid an entire linked list of its records that have aged out. Additionally, concurrent background processes continually navigate the hash table, trimming those chains that are deemed excessively long. The aggressiveness of chain-pruning varies dynamically as the local and global state of the system fluctuates, pruning more when chains are long and the system is heavily loaded, and pruning less when chains are short and the system load is light.