Load balancing cooperating cache servers by shifting forwarded request

• US 6,438,652 B1
• Filed: 10/09/1998
• Issued: 08/20/2002
• Est. Priority Date: 10/09/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jordan, Kevin Michael, Wu, Kun-Lung, Yu, Philip Shi-Lung
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US09/169,223
• Publication Number:
  US 20020026560A1
• Time in Patent Office: 1,411 Days
• Field of Search: 711/118, 711/120, 711/124, 711/144, 711/147, 711/154, 709/219, 709/223, 709/225, 709/226, 709/203, 709/200, 709/201, 709/202
• US Class Current: 711/120
• CPC Class Codes: G06F 9/505 considering the load

Abstract

In a system including a collection of cooperating cache servers, such as proxy cache servers, a request can be forwarded to a cooperating cache server if the requested object cannot be found locally. An overload condition is detected if for example, due to reference skew, some objects are in high demand by all the clients and the cache servers that contain those hot objects become overloaded due to forwarded requests. In response, the load is balanced by shifting some or all of the forwarded requests from an overloaded cache server to a less loaded one. Both centralized and distributed load balancing environments are described.

Claims

1. A cache server load balancing system, comprising:

means for receiving forwarded requests which have been forwarded from one of a plurality of cooperating cache servers in response to a cache miss for an object on the cooperating cache server; and

shifting means for shifting one or more of said forwarded requests for the object between cooperating cache servers based on dynamically maintained server load conditions and forwarding frequency, said forwarding frequency comprising the number of times requests for the object have been forwarded.

2. The system of claim 1, said shifting means further comprising:

means for periodically monitoring the load condition on and the forwarding frequency to said cooperating cache servers; and

means for proactively shifting one or more subsequent forwarded requests for the cached object from between said cooperating cache servers, in response to said monitoring.

3. The system of claim 1, said shifting means further comprising means for checking the load condition and forwarding frequency, in response to the forwarded request.

4. The system of claim 1, wherein said shifting means comprises means for modifying an ownership for the object to a shared ownership between two or more of said cooperating cache servers.

5. The system of claim 4, further comprising merging said shared ownership in response to a change in the load condition.

6. The system of claim 1, further comprising means for locally monitoring the load condition on each cooperating cache server.

7. The system of claim 6, further comprising:

distributed load monitor means for maintaining a local load condition, the forwarding frequency and ownership information for cached objects on said each cooperating cache server.

8. The system of claim 7, further comprising:

means for said cooperating cache servers to periodically exchange and maintain one or more of;

the load condition information;

the forwarding frequency; and

the ownership information.

9. The system of claim 7, further comprising the steps of:

means for said cooperating cache servers to piggyback one or more of;

the load condition information;

the forwarding frequency; and

the ownership information;

with one or more of the forwarded requests and responses.

10. The system of claim 7, further comprising:

means for identifying a less loaded cooperating cache server; and

means for communicating one or more of;

a shift request; and

a copy of the cached object, to said less loaded cooperating cache server.

11. The system of claim 10, further comprising:

said less loaded cooperating cache server including means for receiving said shift request; and

said less loaded cooperating cache server including means for requesting a copy of the object from an originating object server, in response to said shift request.

12. The system of claim 10, wherein the copy is obtained via one or more of an intranet, WAN or Internet.

13. The system of claim 7, further comprising:

a local copy of a caching table on said each cooperating cache server; and

means for said cooperating cache servers to maintain the forwarding frequency and the ownership information based on the local copy of the caching table.

14. The system of claim 7, further comprising:

hash function means for hashing the object space into a number of hash buckets much larger than a total number of said cache servers and assigning said hash buckets to said each cooperating cache server for locating a copy of a locally missed object; and

said shifting means comprising means for moving one or more hash buckets from an overloaded server to a less loaded server, effectively changing the hash function so that forwarded requests will not go to said overloaded server.

15. The system of claim 14, further comprising:

means for modifying the ownership for the object to a shared ownership between at least two of said cooperating cache servers; and

means for said cooperating cache servers to forward subsequent object requests to one or more less loaded shared owners of the object.

16. The system of claim 15, further comprising:

means for detecting a decrease in the load condition for a shared object; and

means for merging the shared ownership, in response to the decrease in the load condition.

17. The system of claim 1, further comprising:

means for updating the forwarding frequency, in response to a forwarded request.

18. The system of claim 1, further comprising:

multicasting means for multicasting a shift request message to one or more of the other cooperating cache servers so that subsequent forward requests will be shifted.

19. The system of claim 1, wherein said shifting means for shifting one or more of said forwarded requests comprises means for communicating a copy of the object from an owning cache server to one or more of said cooperating cache servers.

20. The system of claim 1, further comprising,

means for calculating the load condition of each cache server in past intervals;

means for computing a mean load of all cache servers in past intervals; and

means for finding the cache servers that exceed a threshold above said mean load.

21. The system of claim 1, wherein the load condition of said cooperating cache server comprises a weighted sum of a count of said forwarded requests, and a count of direct requests to said cooperating cache server.

22. The system of claim 1, wherein said object is disposed at an object level and wherein each object may further be one of a plurality of objects in a partition of objects, said partition having a partition level further comprising means for maintaining cache information at one or more of:

the object level for each object; and

the partition level of a partition of objects.

23. The system of claim 22, wherein said cache information of said object level or said partition level, comprises the forwarding frequency associated with the object.

24. The system of claim 1, further comprising:

centralized logical load monitor means for maintaining the forwarding frequency and the load condition for said cooperating cache servers.

25. The system of claim 1, wherein said cooperating cache servers comprise cooperating proxy cache servers.

26. The system of claim 21, further comprising:

a logical directory server means for locating objects and forwarding requests for locally missed objects;

means for maintaining a caching table and a load table, coupled to said directory server;

cache server means for interrogating said directory server for object locations in other cache servers for a locally missed object; and

directory server means for load balancing requests among said cache servers by manipulating said caching table, in response to requests for object locations.

27. The system of claim 1, further comprising:

multicasting means on each cache server for multicasting to a list of cooperating cache servers to locate a copy of a locally missed object;

said shifting means comprising means for excluding overloaded cache servers from a subset of neighboring cache servers for multicasting.

28. A cache server load balancing method, comprising the steps of:

receiving forwarded requests which have been forwarded from one of a plurality of cooperating cache servers in response to a cache miss for an object on the cooperating cache server; and

shifting one or more of said forwarded requests for the object between cooperating cache servers based on dynamically maintained server load conditions and forwarding frequency, said forwarding frequency comprising the number of times requests for the object have been forwarded.

29. The method of claim 28, said shifting step further comprising the steps of:

periodically monitoring the load condition on and the forwarding frequency to an owning cache server; and

proactively shifting one or more subsequent forwarded requests for the cached object from the owning cache server to one or more of said cooperating cache servers, in response to said monitoring.

30. The method of claim 28, said shifting step further comprising the step of checking the load condition and forwarding frequency, in response to the forwarded request.

31. The method of claim 28, wherein said shifting comprises the step of modifying an ownership for the object to a shared ownership between two or more of said cooperating cache servers.

32. The method of claim 31, further comprising the step of merging said shared ownership in response to change in the load condition.

33. The method of claim 28, further comprising the step of locally monitoring the load on each cooperating cache server.

34. The method of claim 33, further comprising the step of:

a distributed load monitor monitoring and maintaining a local load condition, the forwarding frequency and ownership information for cached objects on said each cooperating cache server.

35. The method of claim 34, further comprising the steps of:

said cooperating cache servers periodically exchanging and maintaining one or more of;

the load condition information;

the forwarding frequency; and

the ownership information.

36. The method of claim 34, further comprising the steps of:

said cooperating cache servers exchanging by piggybacking one or more of;

the load condition information;

the forwarding frequency; and

the ownership information;

with one or more of the forwarded requests and responses.

37. The method of claim 28, further comprising the step of:

receiving a forwarded request and updating the forwarding frequency.

38. The method of claim 34, further comprising the steps of:

identifying a less loaded cooperating cache server; and

communicating one or more of;

a shift request; and

a copy of the cached object, to said less loaded cooperating cache server.

39. The method of claim 38, further comprising the steps of:

said less loaded cooperating cache server receiving said shift request; and

said less loaded cooperating cache server requesting a copy of the object from an originating object server, in response to said shift request.

40. The method of claim 38, wherein the copy is obtained via one or more of an intranet, WAN or Internet.

41. The method of claim 28, further comprising the step of multicasting a shift request message to one or more of the other cooperating cache servers so that subsequent forward requests will be shifted.

42. The method of claim 41, further comprising the step of:

the cooperating cache servers maintaining one of a local copy of a caching table and modifying a hash function; and

the cooperating cache servers modifying the ownership information by one of;

updating a local copy of a caching table; and

modifying a hash function.

43. The method of claim 42, further comprising the steps of:

modifying the ownership for the object to a shared ownership between at least two of said cooperating cache servers; and

said cooperating cache servers forwarding subsequent object requests to one or more less loaded shared owners of the object.

44. The method of claim 43, further comprising the steps of:

detecting a decrease in the load condition for a shared object; and

merging the shared ownership, in response to the decrease in the load condition.

45. The method of claim 28, wherein said shifting one or more of said forwarded requests comprises the steps of:

communicating a copy of the object from an owning cache server to one or more of said cooperating cache servers; and

said cooperating cache server receiving and caching the copy of the object.

46. The method of claim 28, further comprising the steps of,

calculating the load condition of each cache server in past intervals;

computing a mean load of all cache servers in past intervals; and

finding the cache servers that exceed a threshold above said mean load.

47. The method of claim 28, wherein the load condition of said cooperating cache server can be a weighted sum of a count of said forwarded requests, and a count of direct requests to said cooperating cache server.

48. The method of claim 28, wherein said object is disposed at an object level and wherein each object may further be one of a plurality of objects in a partition of objects, said partition having a partition level further comprising the step of maintaining cache information at one or more of:

the object level for each object; and

the partition level of a partition of objects.

49. The method of claim 48, wherein said cache information of said object level or said partition level comprises the forwarding frequency associated with the object.

50. The method of claim 49, further comprising the step of:

a distributed load monitor monitoring and locally maintaining load conditions, forwarding frequency and ownership information for cached objects on each cache server.

51. The method of claim 50, further comprising the steps of:

said cooperating cache servers periodically exchanging one or more of the load condition, the forwarding frequency and the ownership information.

52. The method of claim 49, further comprising the steps of:

said cooperating cache servers exchanging by piggybacking one or more of;

the load condition;

the forwarding frequency; and

the ownership information;

with one or more of the forwarded requests and responses.

53. In a collection of cooperating cache servers, where each cache server can receive direct requests and forwarded requests, and upon a cache miss, a request can be forwarded to an owning cache server caching said object, a load balancing method comprising the steps of,

monitoring a dynamically maintained load condition and a forwarding frequency for said cooperating cache servers, said forwarding frequency comprising the number of times requests for the object have been forwarded;

and

shifting one or more forwarded requests, which have already been forwarded, from one cooperating cache server to a second cooperating cache server based on a change in the load condition and the forwarding frequency.

54. The method of claim 53, wherein said step of monitoring the load condition comprises the steps of,

calculating the load condition of each cache server in past intervals;

computing a mean load of all cache servers in past intervals; and

finding those cache servers that exceed a threshold above said mean load.

55. The method of claim 53, wherein said shifting step can be performed in response to one or more of:

said forwarded requests from said cooperating cache servers; and

periodically monitoring the load condition and the forwarding frequency.

56. The method of claim 53, further comprising the step of a centralized logical load monitor maintaining the forwarding frequency and the load condition for the cooperating cache servers.

57. The method of claim 53, wherein the load condition of said cache server can be a weighted sum of:

a count of forwarded requests; and

a count of direct requests to said cache server.

58. The method of claim 53, further comprising the step of maintaining cache information at each object level or at a partition of objects level.

59. The method of claim 58, wherein said cache information of the object level or the partition level comprises the forwarding frequency of requests through said load monitor to said object.

60. The method of claim 53, wherein said cooperating cache servers comprise cooperating proxy cache servers.

61. The method of claim 53, further comprising the steps of:

a logical directory server maintaining a caching table and a load table;

said cache servers interrogating said directory server for object locations in other cache servers for a locally missed object; and

said directory server load balancing requests among said cache servers by manipulating said caching table, in response to requests for object locations.

62. The method of claim 56, further comprising the steps of:

each cache server multicasting to a list of cooperating cache servers to locate a copy of a locally missed object; and

said shifting step comprising the step of excluding overloaded cache servers from a subset of neighboring cache servers for multicasting.

63. A program storage device readable by a machine, tangibly executable a program of instructions executable by the machine to perform method steps for cache server load balancing, said method steps comprising:

receiving forwarded requests which have been forwarded from one of a plurality of cooperating cache servers in response to a cache miss for an object on the cooperating. cache server; and

shifting one or more of said forwarded requests for the object between cooperating cache servers based on dynamically maintained server load conditions and forwarding frequency, said forwarding frequency comprising the number of times requests for the object have been forwarded.

64. The program storage device of claim 63, said shifting step further comprising the steps of:

periodically monitoring the load condition on and the forwarding frequency to an owning cache server; and

proactively shifting one or more subsequent forwarded requests for the cached object from the owning cache server to one or more of said cooperating cache servers, in response to said monitoring.

65. The program storage device of claim 63, said shifting step further comprising the step of checking the load condition and forwarding frequency, in response to the forwarded request.

66. The program storage device of claim 63, wherein said shifting comprises the step of modifying an ownership for the object to a shared ownership between two or more of said cooperating cache servers.

67. The program storage device of claim 66, further comprising the step of merging said shared ownership in response to change in the load condition.

68. The program storage device of claim 63, further comprising the step of locally monitoring the load on each cooperating cache server.

69. The program storage device of claim 68, further comprising the step of:

a distributed load monitor monitoring and maintaining a local load condition, the forwarding frequency and ownership information for cached objects on said each cooperating cache server.

70. The program storage device of claim 69, further comprising the steps of:

said cooperating cache servers periodically exchanging and maintaining one or more of;

the load condition information;

the forwarding frequency; and

the ownership information.

71. The program storage device of claim 69, further comprising the steps of:

said cooperating cache servers exchanging by piggybacking one or more of;

the load condition information;

the forwarding frequency; and

the ownership information;

with one or more of the forwarded requests and responses.

72. The program storage device of claim 69, further comprising the steps of:

identifying a less loaded cooperating cache server; and

communicating one or more of;

a shift request; and

a copy of the cached object, to said less loaded cooperating cache server.

73. The program storage device of claim 72, further comprising the steps of:

said less loaded cooperating cache server receiving said shift request; and

said less loaded cooperating cache server requesting a copy of the object from an originating object server, in response to said shift request.

74. The program storage device of claim 72, wherein the copy is obtained via one or more of an intranet, WAN or Internet.

75. The program storage device of claim 63, further comprising the step of:

receiving a forwarded request and updating the forwarding frequency.

76. The program storage device of claim 75, further comprising the step of:

multicasting a shift request message to one or more of the other cooperating cache servers so that subsequent forward requests will be shifted.

77. The program storage device of claim 76, further comprising the step of:

the cooperating cache servers maintaining one of;

a local copy of a caching table; and

a hash function; and

the cooperating cache servers modifying the ownership information by one of;

updating the local copy of a caching table; and

modifying a hash function.

78. The program storage device of claim 77, further comprising the steps of:

modifying the ownership for the object to a shared ownership between at least two of said cooperating cache servers; and

said cooperating cache servers forwarding subsequent object requests to one or more less loaded shared owners of the object.

79. The program storage device of claim 78, further comprising the steps of:

detecting a decrease in the load condition for a shared object; and

merging the shared ownership, in response to the decrease in the load condition.

80. The program storage device of claim 63, wherein said shifting one or more of said forwarded requests comprises the steps of:

communicating a copy of the object from an owning cache server to one or more of said cooperating cache servers; and

said cooperating cache server receiving and caching the copy of the object.

81. The program storage device of claim 63, further comprising the steps of,

calculating the load condition of each cache server in past intervals;

computing a mean load of all cache servers in past intervals; and

finding the cache servers that exceed a threshold above said mean load.

82. The program storage device of claim 63, wherein the load condition of said cooperating cache server can be a weighted sum of a count of said forwarded requests, and a count of direct requests to said cooperating cache server.

83. The program storage device claim 63, wherein said object is disposed at an object level and wherein each object may further be one of a plurality of objects in a partition of objects, said partition having a partition level further comprising the step of maintaining cache information at one or more of:

the object level for each object; and

the partition level of a partition of objects.

84. The program storage device of claim 83, wherein said cache information of said object level or said partition level, comprises the forwarding frequency associated with the object.

85. The program storage device of claim 84, further comprising the step of:

a distributed load monitor monitoring and locally maintaining load conditions, forwarding frequency and ownership information for cached objects on each cache server.

86. The program storage device of claim 85, further comprising the steps of:

said cooperating cache servers periodically exchanging one or more of the load condition, the forwarding frequency and the ownership information.

87. The program storage device of claim 84, further comprising the steps of:

said cooperating cache servers exchanging by piggybacking one or more of;

the load condition;

the forwarding frequency; and

the ownership information;

with one or more of the forwarded requests and responses.

88. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for cache server load balancing in a collection of cooperating cache servers, where each cache server can receive direct requests and forwarded requests, and upon a cache miss, a request can be forwarded to a cooperating cache server caching said object, said method steps comprising:

monitoring a load condition and a forwarding frequency for said cooperating cache servers; and

shifting one or more forwarded requests from one cooperating cache server to a second cooperating cache server based on a change in the load condition and the forwarding frequency.

89. The program storage device of claim 88, wherein said step of monitoring the load condition comprises the steps of,

calculating the load condition of each cache server in past intervals;

computing a mean load of all proxy cache servers in past intervals; and

finding those proxy cache servers that exceed a threshold above said mean load.

90. The program storage device of claim 88, wherein said shifting step can be performed in response to one or more of:

said forwarded requests from said cooperating cache servers; and

periodically monitoring the load condition and the forwarding frequency.

91. The program storage device of claim 88, further comprising the step of a centralized logical load monitor maintaining the forwarding frequency and the load condition for the cooperating cache servers.

92. The program storage device of claim 91, further comprising the steps of:

each cache server multicasting to a list of cooperating cache servers to locate a copy of a locally missed object; and

said shifting step comprising the step of excluding overloaded cache servers from a subset of neighboring cache servers for multicasting.

93. The program storage device of claim 88, wherein the load condition of said cache server can be a weighted sum of:

a count of forwarded requests; and

a count of direct requests to said cache server.

94. The program storage device of claim 88, wherein said object is disposed at an object level and wherein each object may further be one of a plurality of objects in a partition of objects, said partition having a partition level further comprising the step of maintaining cache information at the object level for each object;

and the partition level of a partition of objects.

95. The program storage device of claim 88, wherein said cache information of the object level or the partition level comprises the forwarding frequency of requests through said load monitor to said object.

96. The program storage device of claim 88, wherein said cooperating cache servers comprise cooperating proxy cache servers.

97. The program storage device of claim 88, further comprising the steps of:

maintaining a caching table and a load table;

receiving requests for object locations in other cache servers for a locally missed object; and

load balancing requests among said cache servers by manipulating said caching table, in response to said requests for object locations.