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

• US 9,690,699 B1
• Filed: 06/08/2015
• Issued: 06/27/2017
• 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
• Application Number:
  US14/733,648
• Time in Patent Office: 750 Days
• 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. A computer-implemented method for storing and retrieving data in a computer system'"'"'s memory, at least some of the data aging-out, the method comprising executing on a computer processor the steps of:

determining an age-out time of data,

identifying an initial location in the memory,

searching memory for non-aged-out data with a matching key,

identifying at least some aged-out data using the age-out time while searching for the non-aged-out data,

determining a maximum number of data items so as to enable an auxiliary parallel global background garbage collector to select at least one portion of the memory containing an excessive number of data items in light of the maximum number of data items,

accessing at least some of the selected portions of the memory using the garbage collector, which executes asynchronously as a separate thread with respect to searching for non-aged-out data with a matching key,

identifying the aged-out data using the garbage collector when a memory portion is accessed by the garbage collector.

2. The method according to claim 1 wherein the step of determining the age-out time uses a local condition of the computer memory.

3. The method according to claim 2 wherein the local condition for determining the age-out time is the amount of data contained in a portion of the memory.

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

5. The method according to claim 4 wherein the global condition for determining the age-out time is the amount of memory available to store new data.

6. The method according to claim 4 wherein the global condition for determining the age-out time is a system load.

7. The method according to claim 1 wherein the step of determining a maximum number of data items includes computing a numerical value that varies monotonically nondecreasingly with the amount of memory available to store new data.

8. The method according to claim 7 wherein determining the age-out time uses the amount of data contained in a portion of the memory.

9. A computer-implemented method for pruning data in a computer system'"'"'s memory, at least some of the data aging-out, the method comprising executing on a computer processor the steps of:

searching memory for non-aged-out data without using an auxiliary parallel global background garbage collector,

determining a maximum number of data items for an auxiliary parallel global background garbage collector that executes asynchronously as a separate thread with respect to searching for non-aged-out data, to select at least one portion of the memory for identifying aged-out data contained therein,

accessing at least some of the selected memory portions containing an excessive number of data items in light of the maximum number of data items using the garbage collector,

identifying aged-out data using the garbage collector when a memory portion is accessed by the garbage collector.

10. The method according to claim 9 further including the step of determining an age-out time of data, the age-out time used by the garbage collector when identifying aged-out data.

11. The method according to claim 9 further including the step of setting a computer processor clock to operate at a frequency that conserves battery power when the garbage collector executes.

12. A computer-implemented method for storing and retrieving information records in a computer system'"'"'s memory organized as at least one linked list, at least some of the records stored in memory aging-out, the method comprising executing on a computer processor the steps of:

determining an age-out time of records,

searching a linked list for a non-aged-out target record with a matching key,

identifying at least some of the aged-out records using the age-out time while searching for the target record,

determining a maximum linked list length so as to enable an auxiliary parallel global background garbage collector, which executes asynchronously as a separate thread with respect to searching for a non-aged-out target record with a matching key, to select at least one linked list 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,

identifying aged-out records using the garbage collector when a linked list is accessed by the garbage collector.

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 is not found when searching.

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

15. The method according to claim 14 wherein the local condition for determining the age-out time is linked list length.

16. The method according to claim 13 wherein the step of 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 determining the age-out time is the amount of memory available to store new data.

18. The method according to claim 16 wherein the global condition for determining the age-out time is a system load.

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

20. The method according to claim 19 wherein determining the age-out time uses a linked list length.