System and method for maintaining a shared cache look-up table

• US 5,864,854 A
• Filed: 01/05/1996
• Issued: 01/26/1999
• Est. Priority Date: 01/05/1996
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Boyle, Douglas B.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/583,334
• Time in Patent Office: 1,117 Days
• Field of Search: 395/610, 395/865, 395/872, 395/800.28, 711/206, 711/141, 711/144, 711/133, 711/121, 711/159, 364/242.94, 364/243.41, 707/2, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

An information system and method for reducing workload load on servers in an information system network. The system defines a group of interconnected clients which have associated cache memories. The system maintains a shared group cache look-up table for the group having entries which identify data items cached by the clients within the group and identify the clients at which the data items are cached. Each client in the group has access to the group cache look-up table, and any client or group can cache any data item. The system can include a hierarchy of groups, with each group having a group cache look-up table. The group cache look-up tables minimize requests for data items outside the groups and greatly minimize the service load on servers having popular data items.

Claims

1. A method of retrieving data items in an information system, the method comprising:

defining a group of interconnected clients within the information system, wherein the clients have cache memories;

maintaining a group cache look-up table for the group comprising entries of data identifiers which identify data items cached by the clients within the group and client identifiers which identify each client at which each of the identified data items are cached;

initiating a data item request with one of the clients within the group;

directing the data item request to the group cache look-up table; and

retrieving the requested data item from the associated cache memory of any of the clients identified by the client identifiers if the requested data item has an associated data identifier entry in the group cache look-up table.

2. The method of claim 1 wherein:

the step of defining a group comprises defining a first level group of interconnected information appliances;

the step of maintaining a group cache look-up table comprises maintaining a first level group cache look-up table in which the client identifiers identify the information appliances within the first level group at which the data items are cached;

the step of initiating comprises initiating a data item request with one of the information appliances within the first level group;

the step of directing comprises directing the data item request to the first level group cache look-up table; and

the step of retrieving comprises retrieving the requested data item from the associated cache memory of any one of the information appliances identified by the client identifier if the data item has an associated data identifier entry in the first level group cache look-up table.

3. The method of claim 2 and further comprising:

storing the requested data item in the cache memory of the information appliance initiating the data item request; and

updating the entry in the first level group cache table associated with the requested data item to add a client identifier which identifies the information appliance initiating the data item request.

4. The method of claim 2 wherein the information system comprises a server and the method further comprises:

directing the data item request to the server if the requested data item has no associated data identifier entry in the first level group cache look-up table.

5. The method of claim 2 wherein the information appliances within the first level group have associated local cache look-up tables comprising local data identifier entries identifying data items cached in the associated cache memories and wherein the method further comprises:

directing the data item request to the local cache look-up table associated with the information appliance initiating the data item request;

retrieving the requested data item from the cache memory associated with the information appliance initiating the request if the data item has an associated data identifier entry in the local cache look-up table; and

directing the data item request to the first level group cache look-up table if the data item has no local data identifier entry in the local cache look-up table.

6. The method of claim 2 and further comprising distributing the first level group look-up table among the information appliances within the first level group, with each information appliance having part of the first level group look-up table.

7. The method of claim 2 and further comprising maintaining a copy of the first level group cache look-up table in the cache memory of each information appliance in the first level group.

8. The method of claim 2 and further comprising:

defining a plurality of first level groups of interconnected information appliances;

maintaining a corresponding first level group cache look-up table for each of the plurality of first level groups;

defining a second level group comprising a set of the first level groups; and

maintaining a second level group cache look-up table for the second level group.

9. The method of claim 8 wherein the step of maintaining a second level group cache look-up table comprises:

maintaining entries of second level data identifiers which identify data items cached within the second level group; and

maintaining second level client identifier entries which identify the first level groups in the set within which the data items are cached.

10. The method of claim 8 and further comprising distributing the second level group cache look-up table among a plurality of the information appliances within the set of first level groups.

11. The method of claim 8 wherein one of the information appliances in the second level group comprises a server and wherein:

the step of maintaining a second level group cache look-up table comprises maintaining the second level group cache look-up table on the server.

12. The method of claim 8 wherein the step of defining a second level group comprises defining a plurality of second level groups and wherein the method further comprises:

defining a third level group comprising a set of the second level groups; and

maintaining a third level group cache look-up table for the third level group.

13. The method of claim 8 where the step of defining a plurality of first level groups comprises including at least one of the information appliances in more than one first level group.

14. A data storage media storing a computer program adapted to program the group of information appliances to execute the method of claim 2.

15. The method of claim 1 wherein the group comprises a server and the step of maintaining a group cache look-up table comprises maintaining the group cache look-up table on the server.

16. The method of claim 1 wherein:

the step of defining a group comprises defining first and second groups of interconnected clients, wherein at least one of the interconnected clients is a member of both the first and second groups; and

the step of maintaining a group cache look-up table comprises maintaining first and second group cache look-up tables for the first and second groups, respectively.

17. The method of claim 1 wherein maintaining a group cache look-up table comprises maintaining a data valid field associated with each data identifier.

18. The method of claim 1 wherein maintaining a group cache look-up table comprises maintaining a replication count field associated with each client identifier entry which indicates a count of copies of the associated data item in the identified client.

19. The method of claim 1 wherein:

the step of defining a group comprises defining a plurality of first level groups of clients and defining a second level group of clients, wherein at least one of the clients in the second level group comprises one of the first level groups.

20. The method of claim 1 and further comprising:

maintaining a data item retrieval efficiency table for each client in the group, wherein each efficiency table comprises an efficiency indicator corresponding to each of the other clients in the group, which indicates efficiency of retrieving data items from the client to which the efficiency indicator corresponds.

21. The method of claim 20 and further comprising:

initiating a data item request with one of the clients within the group;

directing the data item request to the group cache look-up table; and

retrieving the requested data item from the client identified by the client identifier that has the highest efficiency indicator as compared to the efficiency indicators of the other clients identified by the client identifier if the data item has an associated data identifier in the group cache look-up table.

22. An information system comprising:

a plurality of clients having cache memory for caching data items;

an interconnect which interconnects the plurality of clients;

means for defining a group within the plurality of interconnected clients;

means for maintaining a group cache look-up table for the group which identifies data items cached by the clients within the group and identifies the clients at which each of the data items are cached; and

means for directing a data item request to the group cache look-up table and for retrieving the requested data item from any of the clients identified by the group cache look-up table as caching the requested data item.

23. The information system of claim 22 wherein the plurality of clients comprises a plurality of information appliances.

24. The information system of claim 22 wherein:

at least one client within the group comprises a group of interconnected information appliances having a group cache look-up table which identifies data items cached by the information appliances.

25. The information system of claim 22 wherein:

at least one of the plurality of clients comprises an information appliance having a local cache memory; and

the information appliance comprises a local cache look-up table having local data identifier entries identifying data items cached in the local cache memory.

26. The information system of claim 22 wherein:

the group cache table is distributed among the clients within the group.

27. A computer program having program code means for storing and retrieving data items in an information system comprising a plurality of client data processing systems having cache memories and interconnected by a communications link, the computer program comprising:

first program code means, in a first of the plurality of client data processing systems, for defining a group of the plurality of client data processing systems;

second program code means, in the first client data processing system, for maintaining at least a portion of a group cache look-up table for the group comprising entries of data identifiers which identify data items cached by the client data processing systems within the group and client identifiers which identify the client data processing systems at which the associated data items are cached;

third program code means, in the first client data processing system, for initiating a data item request;

fourth program code means, in the first client data processing system, for directing the data item request to the group cache look-up table; and

fifth program code means, in the first client data processing system, for retrieving the requested data item from the cache memory of at least one of the client data processing systems identified by the client identifier if the data item has an associated data identifier entry in the group cache look-up table.