Calculation of the degree of participation of a server in a cluster using half-life decay

• US 20090132695A1
• Filed: 11/19/2007
• Published: 05/21/2009
• Est. Priority Date: 11/19/2007
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Surtani, Manik Ram, Greene, Jason Thomas
• Granted Patent: US 7,716,328 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

A method and apparatus for calculating a degree of participation of a server in a group of servers is disclosed. In one embodiment, a memory stores timestamps for each access to the server. A processor weights the timestamps to treat more recent accesses as more important than older accesses, wherein older accesses decay in importance exponentially using a half-life constant.

Claims

1. A computer-implemented method for calculating a degree of participation of a cache node of a cluster of cache nodes in a tree-based structure, the method comprising:

maintaining a log of timestamps for each access to the cache node; and

weighting the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

2. The computer-implemented method of claim 1 wherein the degree of participation is a function of a total number of accesses to the cache node.

3. The computer-implemented method of claim 2 further comprising:

storing, for each cache node in the cluster, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), wherein Dp and Dt are calculated and stored to minimize the number of elements in At.

4. The computer-implemented method of claim 3 further comprising:

computing the degree of participation (Dp) with Dp=Dp×

(½

̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds.

5. The computer-implemented method of claim 4 further comprising:

emptying the list of At collected after computing the degree of participation Dp.

6. A computer-implemented method for calculating a degree of participation of a server in a group of servers, the method comprising:

maintaining a log of timestamps for each access to the server; and

weighting the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

7. The computer-implemented method of claim 6 wherein the degree of participation is a function of a total number of accesses to the server.

8. The computer-implemented method of claim 7 further comprising:

storing, for each server in the group, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), wherein Dp and Dt are calculated and stored to minimize the number of elements in At.

9. The computer-implemented method of claim 8 further comprising:

computing the degree of participation (Dp) with Dp=Dp×

(½

̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds.

10. The computer-implemented method of claim 9 further comprising:

emptying the list of At collected after computing the degree of participation Dp.

11. An article of manufacture comprising:

a machine-accessible storage medium including data that, when accessed by a machine, cause the machine to perform a method for calculating a degree of participation of a cache node of a cluster of cache nodes in a tree-based structure, the method comprising;

maintaining a log of timestamps for each access to the cache node; and

weighting the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

12. The article of manufacture of claim 11 wherein the degree of participation is a function of a total number of accesses to the cache node.

13. The article of manufacture of claim 12 wherein the method further comprises:

storing, for each cache node in the cluster, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), wherein Dp and Dt are calculated and stored to minimize the number of elements in At.

14. The article of manufacture of claim 13 wherein the method further comprises:

computing the degree of participation (Dp) with Dp=Dp×

(½

̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds.

15. The article of manufacture of claim 14 wherein the method further comprises:

emptying the list of At collected after computing the degree of participation Dp.

16. An article of manufacture comprising:

a machine-accessible storage medium including data that, when accessed by a machine, cause the machine to perform a method for calculating a degree of participation of a server in a group of servers, the method comprising;

maintaining a log of timestamps for each access to the server; and

weighting the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

17. The article of manufacture of claim 16 wherein the degree of participation is a function of a total number of accesses to the server.

18. The article of manufacture of claim 17 wherein the method further comprises:

storing, for each server in the group, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), wherein Dp and Dt are calculated and stored to minimize the number of elements in At.

19. The article of manufacture of claim 18 wherein the method further comprises:

computing the degree of participation (Dp) with Dp=Dp×

(½

̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds.

20. The article of manufacture of claim 19 wherein the method further comprises:

emptying the list of At collected after computing the degree of participation Dp.

21. An apparatus for calculating a degree of participation of a cache node of a cluster of cache nodes in a tree-based structure, the apparatus comprising:

a memory configured to store a log of timestamps for each access to the cache node; and

a processor coupled to the memory, the processor configured to weight the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

22. The computer-implemented method of claim 21 wherein the memory is configured to store, for each cache node in the cluster, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), Dp and Dt are calculated and stored to minimize the number of elements in At,

wherein the processor is configured to compute the degree of participation (Dp) with Dp=Dp×

({circumflex over (1)}{circumflex over (/)}{circumflex over (2)}̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds, and to empty the list of At collected after computing the degree of participation Dp.

23. An apparatus for calculating a degree of participation of a server in a group of servers, the apparatus comprising:

a memory configured to store a log of timestamps for each access to the server; and

a processor coupled to the memory, the memory configured to weight the timestamps to treat recent accesses with priority over older accesses, wherein older accesses decay in priority exponentially using a half-life constant.

24. The apparatus of claim 23 wherein the memory is configured to store, for each server in the group, a degree of participation (Dp), a timestamp of when the degree of participation was calculated (Dt), a list of timestamps when the group was accessed (At), a half-life decay constant (H), Dp and Dt are calculated and stored to minimize the number of elements in At,

wherein the processor is configured to compute the degree of participation (Dp) with Dp=Dp×

({circumflex over (1)}{circumflex over (/)}{circumflex over (2)}̂

((Tc−

At)/H)), wherein Tc is the current time in milliseconds, and to empty the list of At collected after computing the degree of participation Dp.