Data cache using plural lists to indicate sequence of data storage
First Claim
1. a system for multi-threaded data caching comprising:
- a computer platform;
a data structure associated with the computer platform to store data;
a plurality of first utilization lists associated with the data structure, each of the plurality of first utilization lists containing utilization data associated with a portion of the data items stored within the data structure, the utilization data for each of the plurality of first utilization lists indicating a sequence in which the respective portions of associated data items are stored within the data structure;
a first indicator to indicate a selected one of the plurality of first utilization lists that will store the utilization data for the associated data item;
a second indicator to indicate a selected one of the plurality of first utilization lists; and
a cache controller associated with the data structure to delete data items from the data structure, the cache controller deleting a data item associated with utilization data in the selected one of the plurality of first utilization lists indicated by the second indicator.
2 Assignments
0 Petitions
Accused Products
Abstract
A cache system controls the insertion and deletion of data items using a plurality of utilization lists. When a data item is stored within the data cache, a corresponding data pointer, or other indicator, is stored within the utilization list in a manner indicative of the sequence in which data items were stored in the data cache. When a data item is subsequently retrieved from the data cache, the corresponding data pointer may be altered or moved to indicate that the data item has recently been retrieved. The data pointers corresponding to data items that have never been retrieved will indicate the sequence with which the data items were stored in the cache such that data items may be identified as least recently used (LRU) data items. The data pointers corresponding to data items that have been retrieved provide an indication of the sequence with which the data items have been retrieved such that the most recently retrieved data item is considered the most recently used (MRU) data item. The system controls the deletion of data items from the cache by deleting the LRU data items. A large number of utilization lists may operate independently to accommodate a large number of users. An entry pointer selects one of the utilization lists to store the data pointer corresponding to a data item stored within the cache. A deletion pointer selects one of the utilization lists. The system deletes the LRU data item based on the utilization list currently selected by the deletion pointer.
-
Citations
45 Claims
-
1. a system for multi-threaded data caching comprising:
-
a computer platform;
a data structure associated with the computer platform to store data;
a plurality of first utilization lists associated with the data structure, each of the plurality of first utilization lists containing utilization data associated with a portion of the data items stored within the data structure, the utilization data for each of the plurality of first utilization lists indicating a sequence in which the respective portions of associated data items are stored within the data structure;
a first indicator to indicate a selected one of the plurality of first utilization lists that will store the utilization data for the associated data item;
a second indicator to indicate a selected one of the plurality of first utilization lists; and
a cache controller associated with the data structure to delete data items from the data structure, the cache controller deleting a data item associated with utilization data in the selected one of the plurality of first utilization lists indicated by the second indicator. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
a second utilization list associated with the data structure and a predetermined one of the plurality of first utilization lists, the second utilization list containing a portion of the utilization data from the predetermined first utilization list, the portion of utilization data in the second utilization list indicating a sequence in which the portions of associated data items are retrieved from the data structure.
-
-
8. The system of claim 7 wherein the cache controller deletes a data item from the data structure based on the predetermined first utilization list and the second utilization list.
-
9. The system of claim 7 wherein the cache controller deletes a data item from the data structure based on the predetermined first utilization list, the cache controller deleting the data item corresponding to a least recently used (LRU) utilization data within the first utilization list.
-
10. The system of claim 9 wherein the cache controller deletes a data item from the data structure corresponding to a least recently used (LRU) utilization data within the second utilization list if the first utilization list contains no utilization data.
-
11. The system of claim 1 wherein the utilization data comprises a pointer to a location in the data structure where the corresponding data item is stored.
-
12. The system of claim 11 wherein the data item comprises a pointer to a location in a selected one of the plurality of utilization lists where the corresponding utilization data is stored.
-
13. A system for distributed data caching comprising:
-
a first computer platform;
a first data structure associated with the first computer platform to store data;
a plurality of remote computer platforms separate from the first computer platform and coupled to the first computer platform;
a remote data structure associated with each of the plurality of remote computer platforms to store data;
a plurality of first utilization lists associated respectively with the first data structure and each of the remote data structures, each first utilization list containing data associated with corresponding data items stored within the respective data structure, wherein the data contained in each first utilization list indicates a sequence in which the data items were stored within the respective data structure;
a plurality of second utilization lists associated respectively with the first data structure and each of the remote data structures, each second utilization list containing data associated with corresponding data items stored within the respective data structure, wherein the data contained in each second utilization list indicates a sequence in which the data items were retrieved from the respective data structure, and wherein utilization data in the second utilization list is removed from the first utilization list; and
a cache controller associated with the first data structure and each of the remote data structures, respectively, the cache controller deleting data items from the respective data structures. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A computer-readable media containing a plurality of computer instructions to cause one or more computers to:
-
designate a data structure associated with a computer platform to store data;
associate a plurality of first utilization lists with the data structure;
designate a selected one of the plurality of first utilization lists using a first indicator;
upon storage of a data item within the data structure, store utilization data associated with the stored data item in the first utilization list indicated by the first indicator, the utilization data indicating a sequence in which the corresponding data items are stored within the data structure;
designate a selected one of the plurality of first utilization lists using a second indicator; and
delete from the data structure a data item associated with utilization data in the first utilization list indicated by the second indicator. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
associate a second utilization list with the data structure and a predetermined one of the plurality of first utilization lists; and
upon retrieval of a data item, whose utilization data is present in the predetermined first utilization list, from the data structure, store corresponding utilization data in the second utilization list.
-
-
30. The computer-readable media of claim 29, further comprising computer instructions to remove the corresponding utilization data from the first utilization list upon retrieval of the data item whose utilization data is present in the predetermined first utilization list.
-
31. The computer-readable media of claim 29 wherein deleting a data item from the data structure is based on the predetermined first utilization list and the second utilization list.
-
32. The computer-readable media of claim 29 wherein deletion of a data item from the data structure is based on the predetermined first utilization list by deleting the data item corresponding to a least recently used (LRU) utilization data within the first utilization list indicated by the second indicator.
-
33. The computer-readable media of claim 32 wherein deletion of a data item comprises deleting a data item from the data structure corresponding to a least recently used (LRU) utilization data within the second utilization list if the first utilization list indicated by the second indicator contains no utilization data.
-
34. The computer-readable media of claim 24 wherein the utilization data comprises a pointer to a location in the data structure where the corresponding data item is stored and the act of deleting a data item uses the pointer.
-
35. A method of using a computer network for multi-threaded data caching comprising:
-
designating a data structure associated with a computer platform to store data;
associating a plurality of first utilization lists with the data structure;
designating a selected one of the plurality of first utilization lists using a first indicator;
upon storage of a data item within the data structure, storing utilization data associated with the stored data item in the first utilization list indicated by the first indicator, the utilization data indicating a sequence in which the corresponding data items are stored within the data structure;
designating a selected one of the plurality of first utilization lists using a second indicator; and
deleting from the data structure a data item associated with utilization data in the first utilization list indicated by the second indicator. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
associating a second utilization list with the data structure and a predetermined one of the plurality of first utilization lists; and
upon retrieval of a data item whose utilization data is present in the predetermined first utilization list, storing corresponding utilization data in the second utilization list.
-
-
41. The method of claim 40, further comprising removing the corresponding utilization data from the first utilization list upon retrieval of the data item whose utilization data is present in the predetermined first utilization list.
-
42. The method of claim 40 wherein deleting a data item from the data structure is based on the predetermined first utilization list and the second utilization list.
-
43. The method of claim 40 wherein deletion of a data item from the data structure is based on the predetermined first utilization list by deleting the data item corresponding to a least recently used (LRU) utilization data within the first utilization list selected by the second indicator.
-
44. The method of claim 43 wherein deletion of a data item comprises deleting a data item from the data structure corresponding to a least recently used (LRU) utilization data within the second utilization list if the first utilization list contains no utilization data.
-
45. The method of claim 35 wherein the utilization data comprises a pointer to allocation in the data structure where the corresponding data item is stored and the act of deleting a data item uses the pointer.
Specification