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

• US 9,081,672 B1
• Filed: 05/30/2013
• Issued: 07/14/2015
• Est. Priority Date: 05/30/2013
• Status: Active Grant

• Current Assignee: Richard M. Nemes
• Original Assignee: Richard M. Nemes
• Inventors: Nemes, Richard Michael
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US13/906,191
• Time in Patent Office: 775 Days
• Field of Search: 707/206, 707/769, 709/102, 370/231
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement

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.

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.

2. The information storage and retrieval system according to claim 1 wherein the age-out software uses a local condition intrinsic to the hash table and the linked lists to dynamically determine the age-out time.

3. The information storage and retrieval system according to claim 2 wherein the local condition to dynamically determine age-out time is a linked list length that is used to choose a numerical factor by which a value measured in units of time is scaled.

4. The information storage and retrieval system according to claim 1 wherein the age-out software uses a global condition external to the hash table and the linked lists to dynamically determine the age-out time.

5. The information storage and retrieval system according to claim 4 wherein the global condition to dynamically determine the age-out time is a fraction of memory in the computer system available to store new data that is used to choose a numerical factor by which a value measured in units of time is scaled.

6. The information storage and retrieval system according to claim 4 wherein the global condition to dynamically determine the age-out time is a computer system load that is used to choose a numerical factor by which a value measured in units of time is scaled.

7. The information storage and retrieval system according to claim 1 wherein the software for determining the maximum chain length value computes a numerical value that varies monotonically nondecreasingly with the fraction of memory available to store new data.

8. The information storage and retrieval system according to claim 7 wherein the age-out software uses a linked list length to choose a numerical factor by which a value measured in units of time is scaled.

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.

10. The information storage and retrieval system according to claim 9 wherein the age-out means includes means for using linked list length to choose a numerical factor by which a value measured in units of time is scaled.

11. The information storage and retrieval system according to claim 9 further including means for setting a computer processor clock to operate at a frequency that conserves battery power when the garbage collector means executes.

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.

13. The method according to claim 12 further including the step of inserting a record into a linked list if the non-aged-out target record was not found when searching.

14. The method according to claim 13 wherein the step of dynamically determining the age-out time uses a local condition of the hashing system.

15. The method according to claim 14 wherein the local condition for dynamically determining the age-out time is length of the linked lists of the hashing system that is used to choose a numerical factor by which a value measured in units of time is scaled.

16. The method according to claim 13 wherein the step of dynamically determining the age-out time uses a global condition of the computer system.

17. The method according to claim 16 wherein the global condition for dynamically determining the age-out time is a fraction of memory available to store new data that is used to choose a numerical factor by which a value measured in units of time is scaled.

18. The method according to claim 16 wherein the global condition for dynamically determining the age-out time is a system load that is used to choose a numerical factor by which a value measured in units of time is scaled.

19. The method according to claim 12 wherein determining a maximum linked list length is computing a numerical value that varies monotonically nondecreasingly with the fraction of memory available to store new data.

20. The method according to claim 19 wherein dynamically determining an age-out time of records is using a length of the linked lists of the hashing system to choose a numerical factor by which a value measured in units of time is scaled.