Distributed database system using master server to generate lookup tables for load distribution

• US 7,984,183 B2
• Filed: 12/17/2008
• Issued: 07/19/2011
• Est. Priority Date: 12/17/2007
• Status: Active Grant

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Inventors: Andersen, Frank-Uwe, Duelli, Michael, Neitzert, Gerald, Oechsner, Simon, Scheidl, Wolfgang, Hoβfeld, Tobias, Tutschku, Kurt, Tran-Gia, Phuoc
• Primary Examiner(s): LUU, LE HIEN
• Application Number:
  US12/337,231
• Publication Number:
  US 20090157684A1
• Time in Patent Office: 944 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241, 709/242, 709/243, 709/244, 709/225, 709/226, 707/770, 370/392
• US Class Current: 709/244
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/4523 using lightweight directory access protocol [LDAP]
• 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/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer

Abstract

A state change in a network comprising a master server among a plurality of servers is determined, at the master server, a first lookup table is calculated, said first lookup table indicating respective partitions of a second lookup table distributed among active servers of said plurality of servers, the calculated first lookup table is distributed to each active server, and based on the first lookup table, at the master server, a modified partition of the second lookup table is generated.

Claims

1. A method comprising:

determining a state change in a network comprising a master server among a plurality of servers;

calculating, at the master server, a first lookup table, said first lookup table indicating respective partitions of a second lookup table distributed among active servers of said plurality of servers;

distributing the calculated first lookup table to each active server; and

based on the first lookup table, generating, at the master server, a modified partition of the second lookup table.

2. The method of claim 1, wherein

calculating the first lookup table comprises:

allocating partitions of the second lookup table to active servers, wherein

respective partitions of the second lookup table allocated to each active server equal each other in terms of size, wherein the size is defined by a difference between a start address value and an end address value, or differ from each other in terms of size

in proportion to a respective processing capacity of each of said active servers, or

in such a manner that a processing load for each of the active servers equals each other.

3. The method according to claim 2,

wherein the first lookup table comprises at least a pair of data, wherein each pair of data comprises

an address of an active server and

an address partition representing a partition of the second lookup table and defined by a start address value and an end address value, and further comprises mapping information between the first lookup table after and before the detected state change.

4. The method according to claim 3, wherein the number of data pairs contained in the first lookup table depends on the number of active servers.

5. The method according to claim 2, wherein the allocating comprises

re-dividing an address space that is formed by a plurality of address partitions of the second lookup table managed by the respective active servers, among a number of the active servers after a detected state change, thereby obtaining a respective modified partition of the second lookup table for each active server.

6. The method according to claim 5, wherein the re-dividing comprises

shifting at least one of the start address value and the end address value of the partition of at least one active server by a respective address shift amount.

7. The method according to claim 6, further comprising validating the address shift amount after re-dividing.

8. The method of claim 1, further comprising:

collecting first acknowledgements at the master server from each active server indicating that generating modified partitions of the second lookup table at each active server is completed,

issuing a lock command to each active server in the network upon collecting the first acknowledgements; and

collecting second acknowledgements from each active server indicating that it is locked, wherein writing operations are prohibited when a server is locked.

9. The method of claim 8, further comprising:

issuing a switch command to each active server in the network upon collecting the second acknowledgements, and

collecting third acknowledgements from each active server indicating that each said server switches to its respective first lookup table and the respective modified partition of the second look up table.

10. The method of claim 9, further comprising:

issuing an unlock command to each active server in the network upon collecting the third acknowledgements.

11. The method according to claim 1, wherein the state change in the network pertains to at least one of the following:

a change in a state of at least one server,

removal of a server from the plurality of servers constituting the network, and

addition of a server to the plurality of servers constituting the network.

12. The method of claim 1, wherein determining a state change in a network comprises:

starting a timer upon determination of the state change; and

checking the state again upon expiry of the timer,

wherein the state change is confirmed if the state when the timer starts is the same as after expiry of the timer.

13. The method according to claim 1, wherein the generating is based on the calculated first lookup table, and based on at least one partition of the second lookup table respectively allocated to at least one server among the plurality of servers prior to a detected state change in the network.

14. A method, comprising:

receiving, at an active server among a plurality of servers, a first look up table indicating respective partitions of a second lookup table distributed among the plurality of servers;

generating, at the active server, a modified partition of the second lookup table based on the first lookup table.

15. The method according to claim 14, comprising

sending a first acknowledgement to a master server upon completion of generating the modified partition of the second lookup table.

16. The method of claim 15, comprising:

receiving a lock command, and locking the active server responsive thereto;

upon receiving the lock command, completing on-going writing operations; and

upon completion of the on-going writing operations, sending a second acknowledgement indicating that the active server is locked to the master server, wherein writing operations are prohibited when the active server is locked.

17. The method of claim 16, further comprising:

receiving a switch command;

upon receipt of the switch command, switching to the received first lookup table and the generated modified partition of the second lookup table, and upon completion of the switching, sending a third acknowledgement to the master server.

18. The method according to claim 14, wherein the generating is based on the received first lookup table, and based on at least one partition of the second lookup table respectively allocated to at least one server among the plurality of servers prior to a state change.

19. A server, comprising:

an interfacing unit; and

a processor configured to

determine a state change in a network comprising the server as a master server among a plurality of servers,

calculate a first lookup table, said first lookup table indicating respective partitions of a second lookup table distributed among active servers of said plurality of servers,

distribute the calculated first lookup table to each active server via said interfacing unit, and

based on the first lookup table generate a modified partition of the second lookup table.

20. The server of claim 19, wherein the processor for calculating the first lookup table, is configured to

allocate partitions of the second lookup table to active servers, wherein

respective partitions of the second lookup table allocated to each active server equal each other in terms of size, wherein the size is defined by a difference between a start address value and an end address value, or

differ from each other in terms of size

in proportion to a respective processing capacity of each of said active servers, or

in such a manner that a processing load for each of the active servers equals each other.

21. The server according to claim 20, wherein the first lookup table comprises at least a pair of data, wherein each pair of data comprises

an address of an active server and

an address partition representing a partition of the second lookup table and defined by a start address value and an end address value, and further comprises mapping information between the first lookup table after and before the detected state change.

22. The server according to claim 21, wherein the number of data pairs contained in the first lookup table depends on the number of active servers.

23. The server according to claim 20, wherein the processor, for allocating partitions of the second lookup table to active servers, is configured to:

re-divide an address space that is formed by the plurality of address partitions of the second lookup table managed by the respective active servers, among a number of the active servers after a detected state change, thereby obtaining a respective modified partition of the second lookup table for each active server.

24. The server according to claim 23, wherein the processor for re-dividing the address space, is configured to:

shift at least one of the start address value and the end address value of the partition of at least one active server by a respective address shift amount.

25. The server according to claim 24, wherein the processor is further configured to validate the address shift amount after re-dividing.

26. The server of claim 19, wherein the processor is further configured to:

collect first acknowledgements, via said interfacing unit, from each active server indicating that generating modified partitions of the second lookup table at each active servers is completed,

issue a lock command to each active server in the network via said interfacing unit upon collecting the first acknowledgements, and

collect, via said interfacing unit, second acknowledgements from each active server indicating that it is locked, wherein writing operations are prohibited when a server is locked.

27. The server of claim 26, the processor further configured to:

issue a switch command to each active server in the network via said interfacing unit upon collecting the second acknowledgements, and

collect, via said interfacing unit, third acknowledgements from each active server indicating that each said server switches to the first lookup table and the modified partition of the second look up table.

28. The server of claim 27, wherein the processor is further configured to:

issue an unlock command to each active server in the network via said interfacing unit upon collecting the third acknowledgements.

29. The server according to claim 19, wherein the state change in the network pertains to at least one of the following:

a change in a state of at least one server,

removal of a server from the plurality of servers constituting the network, and

addition of a server to the plurality of servers constituting the network.

30. The server of claim 19, wherein the processor for determining a state change in the network, is configured to:

start a timer upon determination of the state change; and

check the state again upon expiry of the timer, wherein the processor is configured to confirm the state change if the state when the timer starts is the same as after expiry of the timer.

31. The server according to claim 19, wherein the processor is configured to generate the modified partition of the second lookup table based on the calculated first lookup table, and based on at least one partition of the second lookup table respectively allocated to at least one server among the plurality of servers prior to a detected state change in the network.

32. A server, comprising:

an interfacing unit configured to receive a first look up table indicating respective partitions of a second lookup table distributed among a plurality of servers including the server as an active server; and

a processor configured to generate a modified partition of the second lookup table based on the first lookup table.

33. The server according to claim 32, wherein the processor is configured to cause the interfacing unit to send a first acknowledgement to a master server upon completion of generating the modified partition of the second lookup table.

34. The server of claim 33, wherein

the interfacing unit is configured to receive a lock command,

upon receiving the lock command, the processor is configured to lock the server responsive thereto and to complete on-going writing operations, and upon completion of the on-going writing operations, to cause the interfacing unit to send a second acknowledgement to the master server indicating that the active server is locked, wherein writing operations are prohibited when the active server is locked.

35. The server of claim 34, wherein

the interfacing unit is configured to receive a switch command,

the processor is configured to switch, upon receipt of the switch command, to the received first lookup table and the generated modified partition of the second lookup table, and upon completion of the switching, to cause the interfacing unit to send a third acknowledgement to the master server.

36. The server according to claim 32, wherein the processor is configured to generate the modified partition of the second lookup table based on the received first lookup table, and based on at least one partition of the second lookup table respectively allocated to at least one server among the plurality of servers prior to a state change.

37. A system comprising:

(a) a server comprising;

an interfacing unit; and

a processor configured to

determine a state change in a network comprising the server as a master server among a plurality of servers,

calculate a first lookup table, said first lookup table indicating respective partitions of a second lookup table distributed among active servers of said plurality of servers,

distribute the calculated first lookup table to each active server via said interfacing unit, and

based on the first lookup table generate a modified partition of the second lookup table; and

(b) at least one server comprising;

an interfacing unit configured to receive a first look up table indicating respective partitions of a second lookup table distributed among a plurality of servers including the server as an active server; and

a processor configured to generate a modified partition of the second lookup table based on the first lookup table.

38. A computer program embodied on a computer readable storage medium comprising processor implementable instructions for performing the following method steps:

determining a state change in a network comprising a master server among a plurality of servers;

calculating, at the master server, a first lookup table, said first lookup table indicating respective partitions of a second lookup table distributed among active servers of said plurality of servers;

distributing the calculated first lookup table to each active server; and

based on the first lookup table, generating, at the master server, a modified partition of the second lookup table.