Methods and apparatus for information storage and retrieval using a caching technique with external-chain hashing and dynamic resource-dependent data shedding
First Claim
1. An information storage and retrieval system, the system comprising:
- A hash table stored in computer memory having locations containing pointers to heads of linked lists of records having same hash addresses,age-out software that dynamically determines an age-out time for the records stored in the system,search software that uses a hashing function to map a search key to a corresponding location in the hash table and searches the linked list associated with the corresponding location for a non-aged-out target record with matching key while identifying at least some aged-out records encountered in the linked list in the process of searching for the non-aged-out target record using the age-out time,auxiliary parallel global background garbage collector software that executes asynchronously as a separate thread with respect to the search software and accesses at least some of the linked lists whose length is greater than a maximum chain length value and identifies at least some of the aged-out records in those lists not as part of searching for the non-aged-out target record, wherein the garbage collector software includes software for determining the maximum chain length value, andsynchronization software that uses a semaphore to provide exclusive access to the hash table location and its associated linked list.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. An information storage and retrieval system, the system comprising:
-
A hash table stored in computer memory having locations containing pointers to heads of linked lists of records having same hash addresses, age-out software that dynamically determines an age-out time for the records stored in the system, search software that uses a hashing function to map a search key to a corresponding location in the hash table and searches the linked list associated with the corresponding location for a non-aged-out target record with matching key while identifying at least some aged-out records encountered in the linked list in the process of searching for the non-aged-out target record using the age-out time, auxiliary parallel global background garbage collector software that executes asynchronously as a separate thread with respect to the search software and accesses at least some of the linked lists whose length is greater than a maximum chain length value and identifies at least some of the aged-out records in those lists not as part of searching for the non-aged-out target record, wherein the garbage collector software includes software for determining the maximum chain length value, and synchronization software that uses a semaphore to provide exclusive access to the hash table location and its associated linked list. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An information storage and retrieval system, the system comprising:
-
means for storing in computer memory pointers to heads of linked lists of records having same hash addresses, age-out means for dynamically determining an age-out time for the records stored in the system, search means, using hashing function means for mapping a search key to a corresponding hash table location, for searching the linked list associated with the corresponding location to locate a non-aged-out target record with matching key while identifying, using the age-out time, at least some aged-out records encountered in the linked list in the process of locating the non-aged-out target record, auxiliary parallel global background garbage collector means that executes asynchronously as a separate thread with respect to the search means for accessing at least some of the linked lists whose length is greater than a maximum chain length value and identifying at least some of the aged-out records in those lists not as part of locating the non-aged-out target record, wherein the garbage collector means uses means for determining the maximum chain length value, and synchronization means for exclusively accessing the hash table location and its associated linked list. - View Dependent Claims (10, 11)
-
-
12. A method for storing and retrieving information records in computer memory organized as linked lists in a hashing system that uses external chaining, at least some of the records stored in memory aging-out, the method comprising the steps of:
-
dynamically determining an age-out time of records, identifying the desired linked list in the hashing system based on a key, searching the desired linked list for a non-aged-out target record with matching key, identifying at least some of the aged-out records using the age-out time while searching the desired linked list for the non-aged-out target record, determining a maximum linked list length for an auxiliary parallel global background garbage collector to select linked lists for identifying aged-out records, accessing at least some of the linked lists whose length is excessive in light of the maximum linked list length using the garbage collector that executes asynchronously as a separate thread with respect to searching the desired linked list for a non-aged-out target record with matching key, identifying at least some of the aged-out records using the garbage collector when the linked lists are accessed by the garbage collector, and synchronizing to provide exclusive access to hash table locations and associated linked lists using a semaphore. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification