Scalable cache

• US 6,490,615 B1
• Filed: 11/20/1998
• Issued: 12/03/2002
• Est. Priority Date: 11/20/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levy-Abegnoli, Eric Michel, Song, Junehwa, Iyengar, Arun Kwangil, Dias, Daniel Manuel
• Primary Examiner(s): Dinh, Dung C.
• Assistant Examiner(s): EDELMAN, BRADLEY E
• Application Number:
  US09/196,944
• Time in Patent Office: 1,474 Days
• Field of Search: 709/217, 709/219, 709/230, 709/203, 709/226
• US Class Current: 709/219
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols

Abstract

Requests for objects are received from one or more clients in a system comprised of a plurality of nodes. One of the requests is sent from one of the clients. The request is received from a first node of said plurality of nodes by a second node of said plurality of nodes. A requested object is returned from the second node of the plurality of nodes using one of a plurality of protocols. The method may be applied to a scalable and highly available cache array. The cache array may enhance the performance and throughput of Web servers connected to a network such as the Internet. A network dispatcher may send requests to a cache node of a cache array. The cache node selected by the network dispatcher may either serve the request, handoff the request to another cache node of a cache array, or communicate via one of a variety of protocols with another cache node of the cache array to cooperatively serve the request. A network dispatcher, operating in a special mode, may also function as a content based router. Thus, it is also possible for a network dispatcher to route requests using a combination of content-based and non-content-based routing in order to further improve system performance.

Claims

1. In a system adapted to receive request for objects from one or more clients, said system comprised of a plurality of cache nodes, a method for retrieving a requested object of said objects, said method comprising the steps of:

(a) sending one of said requests from one of said clients;

(b) receiving said request at a network dispatcher;

(c) forwarding said request from said network dispatcher to a cache node, selected by said network dispatcher, of a cache array, wherein one cache node of said cache array is a primary owner of said requested object; and

(d) returning said requested object from a servicing cache node of said cache array using one of a plurality of protocols, wherein said one of the plurality of protocols is selected by the cache array based on the size of said requested object.

2. The method of claim 1, wherein said one node receives said request from said one of said clients.

3. The method of claim 1, wherein said one node receives said request from another of said plurality of nodes.

4. The method of claim 1, wherein in response to the size of said requested object being less than a predetermined size the requested object is returned from another cache node to said one node and subsequently from said one node to said one of said clients.

5. The method of claim 4, wherein said requested object is returned from said one node to at least a further node of said plurality of nodes before being returned to said one of said clients.

6. The method of claim 1, wherein in response to the size of said requested object being greater than a predetermined size the requested object is returned from another cache node to said one of said clients without first passing through said one node.

7. The method of claim 6, wherein said requested object is returned from said another node to at least a further node of said plurality of nodes before being returned to said one of said clients.

8. The method of claim 1, wherein one of said plurality of nodes functions as a back-end server.

9. The method of claim 8, further comprising the step of sending said request to the back-end server in response to said cache array not having a cached copy of said requested object.

10. The method of claim 1, further comprising the step of partitioning the ownership of one of said objects across one of said plurality of nodes.

11. The method of claim 10, wherein another node is said primary owner of said requested object and is selected as the servicing node.

12. The method of claim 10, wherein any one of said objects has at most one owner.

13. The method of claim 10, wherein any one of said objects has multiple owners.

14. The method of claim 1, wherein the one of the plurality of protocols is one of HTTP (HyperText Transfer Protocol), UDP (User Datagram Protocol), and Handoff interface.

15. The method of claim 1, wherein one of said plurality of nodes functions as a back-end server.

16. The method of claim 15, further comprising the step of sending said request to the back-end server in response to said cache array not having a cached copy of said requested object.

17. A method of retrieving a requested object, said method comprising the steps of:

(a) transmitting a request for the requested object to a cache array comprising a plurality of caches including a first cache and having a single cache image;

(b) determining whether the first cache corresponds to the requested object;

(c) identifying a second cache in the cache array corresponding to the requested object; and

(d) retrieving the requested object via the second cache using one of a plurality of protocols, wherein said one of the plurality of protocols is selected by the cache array based on the size of said requested object.

18. The method according to claim 17, wherein the requested object is retrieved by transmitting the requested object from the second cache to the first cache and from the first cache to a client.

19. The method according to claim 17, wherein the request for the requested object is forwarded from the first cache to the second cache.

20. The method according to claim 19, wherein the requested object is retrieved by transmitting the requested object from the second cache to a client.

21. The method according to claim 20, further comprising the steps of:

determining whether the requested object is not stored in the second cache; and

retrieving the requested object from a server associated with the second cache.

22. The method according to claim 17, wherein steps (c) and (d) are performed if in step (b) it is determined that the first cache does not correspond to the requested object.

23. The method according to claim 17, wherein the one of the plurality of protocols is one of HTTP (HyperText Transfer Protocol), UDP (User Datagram Protocol), and Handoff interface.

24. A method of retrieving a target object of a plurality of objects, the target object requested by a client, said method comprising the steps of:

(a) assigning each of the plurality of objects to at least one of a plurality of nodes;

(b) assigning at least one of a plurality of caches to each of the plurality of nodes;

(c) transmitting a request for the target object to a first node of the plurality of nodes;

(d) determining if the target object is assigned to the first node; and

(e) if the target object is not assigned to the first node

(i) transmitting the request to a second node of the plurality of nodes, the target object being assigned to the second node, and

(ii) retrieving the target object from a cache of the plurality of caches assigned to the second node if the target object is stored in the cache assigned to the second node using one of a plurality of protocols, wherein said one of the plurality of protocols is selected by the cache array based on the size of said requested object.

25. The method according to claim 24, wherein step (ii) is performed by communicating via at least one of the plurality of protocols.

26. The method according to claim 25, further comprising the step of if the target object is not assigned to the first node and if the size of the target object is smaller than a predetermined object size, transmitting the target object from the second node to the first node, and transmitting the target object from the first node to the client.

27. The method according to claim 25, further comprising the step of if the target object is not assigned to the first node and if the size of the target object is larger than a predetermined object size, transmitting the target object from the second node to the client.

28. The method according to claim 25, wherein a first protocol of the plurality of protocols is executed between the first node and the second node, and a second protocol of the plurality of protocols is executed between the first node and the client.

29. The method according to claim 25, wherein a first protocol of the plurality of protocols is executed between the second node and the client.

30. The method according to claim 24, further comprising the step of

if the target object is assigned to the first node, retrieving the target object from a cache of the plurality of caches assigned to the first node if the target object is stored in the cache assigned to the first node.

31. The method according to claim 30, further comprising the step of

retrieving the target object from a server corresponding to the first node if the target object is not stored in the cache assigned to the first node.

32. The method according to claim 24, wherein step (e) the target object is retrieved from a server corresponding to the second node if the target object is not stored in the cache assigned to the second node.

33. An article of manufacture comprising a computer usable medium having computer readable code means embodied therein for receiving a request for an object, said system comprised of a plurality of cache nodes, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

(a) sending one of said requests from one of said clients;

(b) receiving said request at a network dispatcher;

(c) forwarding said request from said network dispatcher to a cache node, selected by said network dispatcher, of a cache array, wherein one cache node of said cache array is a primary owner of said requested object; and

(d) returning said requested object from a servicing cache node of said cache array using one of a plurality of protocols, wherein said one of the plurality of protocols is selected by the cache array based on the size of said requested object.

34. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for retrieving a requested object of a plurality of objects in a system adapted to receive requests for said objects from one or more clients, said system comprised of a plurality of cache nodes, said method steps comprising:

(a) sending one of said requests from one of said clients;

(b) receiving said request at a network dispatcher;

(c) forwarding said request from said network dispatcher to a cache node, selected by said network dispatcher, of a cache array, wherein one cache node of said cache array is a primary owner of said requested object; and

(d) returning said requested object from a servicing cache node of said cache array using one of a plurality of protocols, wherein said one of the plurality of protocols is selected by the cache array based on the size of said requested object.