Data cache using plural lists to indicate sequence of data storage

• US 6,449,695 B1
• Filed: 05/27/1999
• Issued: 09/10/2002
• Est. Priority Date: 05/27/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bereznyi, Alexandre, Katariya, Sanjeev
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/321,301
• Time in Patent Office: 1,202 Days
• Field of Search: 711/118, 711/129, 711/130, 711/132, 711/133, 711/134, 711/136, 711/144
• US Class Current: 711/134
• 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/9574 of access to content, e.g. by caching

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.

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.

2. The system of claim 1 wherein the cache controller deletes data items in a sequence in which the corresponding utilization data is entered into the selected first utilization list indicated by the first indicator, the data item being designated as a least recently used (LRU) data item in the selected first utilization list indicated by the second indicator being deleted from the data structure.

3. The system of claim 1 wherein the first and second indicators indicate different selected ones of the plurality of first utilization lists.

4. The system of claim 1 wherein the cache controller alters the first indicator following storage of a data item to indicate a different selected one of the plurality of first utilization lists.

5. The system of claim 1 wherein the cache controller alters the second indicator following deletion of a data item to indicate a different selected one of the plurality of first utilization lists.

6. The system of claim 1 for use in a multi-threaded environment in which the data structure is responsive to a predetermined plural number of processing threads which store data items in the data structure and which retrieve data items from the data structure, the plurality of first utilization lists being greater in number than the predetermined number of processing threads.

7. The system of claim 1, further comprising:

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.

14. The system of claim 13 wherein the cache controllers delete data items from the respective data structures based on the first and second utilization lists associated with the respective data structures.

15. The system of claim 13 wherein the cache controllers delete data items from the respective data structures based on the first utilization list, the cache controller deleting data items corresponding to a least recently used (LRU) utilization data within the first utilization list.

16. The system of claim 15 wherein the cache controllers delete data items from the respective data structures corresponding to a least recently used (LRU) utilization data within the second utilization list if the first utilization list contains no utilization data.

17. The system or claim 13, further comprising a plurality of third utilization lists associated respectively with the first data structure and each of the remote data structures, the third utilization list containing utilization data associated with corresponding data items stored within the respective data structure, the third utilization list data indicating a sequence in which the data items whose utilization data is contained within the respective second utilization list were retrieved from the respective data structure wherein utilization data in the third utilization list is removed from the second utilization list.

18. The system of claim 13 wherein first utilization data is entered into the respective first utilization list when the corresponding first data item is initially stored in the respective data structure.

19. The system of claim 13 wherein second utilization data is entered into the respective first utilization list when the corresponding second data item is initially stored in the respective data structure, the first utilization data being altered to indicate a time of storage of the corresponding first data item earlier than the corresponding second data item.

20. The system of claim 13 wherein the utilization data is stored in a sequence indicative of the a time of storage of the corresponding data item.

21. The system of claim 13 wherein the cache controller executes a first retrieve command to retrieve a corresponding first data item from a selected one of the data structures, the utilization data corresponding to the retrieved first data item being placed on the second utilization list associated with the selected data structure and being removed from the first utilization list.

22. The system of claim 21 wherein the cache controller executes a second retrieve command to retrieve a corresponding second data item from the selected data structure, second utilization data corresponding to the retrieved second data item being placed on the second utilization list associated with the selected data structure and being removed from the first utilization list, the first utilization data being altered to indicate a time of retrieval of the corresponding first data item earlier than the corresponding second data item.

23. The system of claim 13 wherein the utilization data comprises a pointer to a location in the respective data structure where the corresponding data item is stored.

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.

25. The computer-readable media of claim 24 wherein deletion of a data item is based on a sequence in which the corresponding utilization data is entered into the first utilization list indicated by the first indicator, the data item being designated as a least recently used (LRU) data item in the first utilization list indicated by the second indicator being deleted from the data structure.

26. The computer-readable media of claim 24 wherein the first and second indicators indicate different selected ones of the first utilization lists.

27. The computer-readable media of claim 24, further comprising computer instructions to alter the first indicator following storage of the data item to designate a different selected one of the plurality to first utilization lists.

28. The computer-readable media of claim 24, further comprising computer instructions to alter the second indicator following deletion of the data item to designate a different selected one of the plurality of first utilization lists.

29. The computer-readable media of claim 24, further comprising a plurality of computer instructions to:

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.

36. The method of claim 35 wherein deletion of a data item is based on a sequence in which the corresponding utilization data is entered into the first utilization list selected using the first indicator, the data item being designated as a least recently used (LRU) data item in the first utilization list indicated by the second indicator being deleted from the data structure.

37. The method of claim 35 wherein the first and second indicators indicate different selected ones of the first utilization lists.

38. The method of claim 35, further comprising altering the first indicator following storage of the data item to designate a different selected one of the plurality of first utilization lists.

39. The method of claim 35, further comprising altering the second indicator following deletion of the data item to designate a different selected one of the plurality of first utilization lists.

40. The method of claim 35, further comprising:

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.