Consistent hashing using exact matching with application to hardware load balancing

• US 9,391,884 B2
• Filed: 01/31/2014
• Issued: 07/12/2016
• Est. Priority Date: 01/31/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghobadi, Monia, Shraer, Alexander
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US14/169,776
• Publication Number:
  US 20150222532A1
• Time in Patent Office: 893 Days
• Field of Search: 370236-255, 370392-395, 370401-429, 709203-229
• US Class Current: 1/1
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 67/1004 Server selection for load balancing

Abstract

Aspects and implementations of the present disclosure are directed to a network device storing an address table. Each of the address table entries is assigned to a respective provisioned index value and an instance of a distributed service. The device is configured to add a new service instance to the address table by obtaining an assignable index value for the new service instance, identifying an assigned index value that is a companion index value to the obtained index value, dividing a packet source address set associated with the companion index value into first and second address subsets, and assigning the first address subset to the service instance entry in the address table associated with the assigned companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance.

Claims

1. A method of maintaining routing information for a distributed service provided by a plurality of service instances, comprising:

providing an address table including a set of entries, wherein;

the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of the distributed service; and

adding a new service instance to the address table by;

obtaining, by a network device controller, an assignable index value to assign to the new service instance by

     1) identifying an existing, unassigned, index value in the set of provisioned index values, or when no existing index values in the set of provisioned index values are unassigned, by

     2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value;

identifying, by the network device controller based on the obtained index value and the number of provisioned index values in the set of provisioned index values, an assigned index value that is a companion index value to the obtained index value, wherein the companion index value is associated with a packet source address set;

dividing, by the network device controller, the packet source address set associated with the companion index value into a first address subset and a second address subset; and

assigning, by the network device controller, the first address subset to the service instance entry in the address table associated with the companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance.

4. The method of claim 1, wherein the number of provisioned index values in the set of provisioned index values is a power of two.

5. The method of claim 4, wherein increasing the number of index values in the set of provisioned index values comprises doubling the number of provisioned index values.

6. The method of claim 4, wherein identifying a companion index value for a particular index value comprises adding, by the network device controller, half the number of provisioned index values in the set of provisioned index values to the particular index value, modulo the number of provisioned index values in the set of provisioned index values.

7. The method of claim 1, comprising generating the address table.

2. A method comprising:

providing an address table including a set of entries, wherein;

the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of the distributed service;

adding a new service instance to the address table by;

obtaining, by a network device controller, an assignable index value to assign to the new service instance by

     1) identifying an existing, unassigned, index value in the set of provisioned index values, or by

     2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value;

identifying, by the network device controller, an assigned index value that is a companion index value to the obtained index value, wherein the companion index value is associated with a packet source address set;

dividing, by the network device controller, the packet source address set associated with the companion index value into a first address subset and a second address subset; and

assigning, by the network device controller, the first address subset to the service instance entry in the address table associated with the companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance; and

removing a service instance from the address table by;

identifying, by the network device controller, a third address subset assigned to a service instance entry in the address table, associated with a first index value, for the service instance to be removed;

identifying, by the network device controller, a fourth address subset assigned to a service instance entry in the address table associated with a second index value that is a companion index value to the first index value;

assigning, by the network device controller, a combined address subset, comprising the third address subset and the fourth address subset, to the service instance entry in the address table associated with the second index value; and

clearing, by the network device controller, the service instance entry associated with the first index value from the table.

3. The method of claim 2, further comprising:

determining, by the network device controller, that the first index value is less than the second index value;

changing, by the network device controller, the association for the service instance entry in the address table, associated with the second index value, from an association with the second index value to an association with the first index value.

20. The method of claim 2, wherein the number of provisioned index values in the set of provisioned index values is a power of two, and wherein identifying a companion index value for a particular index value comprises adding, by the network device controller, half the number of provisioned index values in the set of provisioned index values to the particular index value, modulo the number of provisioned index values in the set of provisioned index values.

8. A network device controller comprising:

memory storing an address table including a set of entries, wherein the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of a distributed service provided by a plurality of service instances; and

at least one processor, the at least one processor configured to add a new service instance to the address table by performing the operations of;

obtaining an assignable index value to assign to the new service instance by

     1) identifying an existing, unassigned, index value in the set of provisioned index values, or when no existing index values in the set of provisioned index values are unassigned, by

     2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value;

identifying, based on the obtained index value and the number of provisioned index values in the set of provisioned index values, an assigned index value that is a companion index value to the obtained index value, wherein the companion index value is associated with a packet source address set;

dividing the packet source address set associated with the companion index value into a first address subset and a second address subset; and

assigning the first address subset to the service instance entry in the address table associated with the companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance.

11. The network device controller of claim 8, wherein the number of provisioned index values in the set of provisioned index values is a power of two.

12. The network device controller of claim 11, wherein increasing the number of index values in the set of provisioned index values comprises doubling the number of provisioned index values.

13. The network device controller of claim 11, wherein identifying a companion index value for a particular index value comprises adding half the number of provisioned index values in the set of provisioned index values to the particular index value, modulo the number of provisioned index values in the set of provisioned index values.

14. The network device controller of claim 8, wherein the at least one processor is further configured to generate the address table.

9. A network device controller comprising:

memory storing an address table including a set of entries, wherein the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of a distributed service provided by a plurality of service instances; and

at least one processor, the at least one processor configured to add a new service instance to the address table by performing the operations of;

obtaining an assignable index value to assign to the new service instance by

     1) identifying an existing, unassigned, index value in the set of provisioned index values, or by

     2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value;

identifying an assigned index value that is a companion index value to the obtained index value;

dividing a packet source address set associated with the companion index value into a first address subset and a second address subset; and

assigning the first address subset to the service instance entry in the address table associated with the companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance;

wherein the at least one processor is further configured to remove a service instance from the address table by performing the operations of;

identifying a third address subset assigned to a service instance entry in the address table, associated with a first index value, for the service instance to be removed;

identifying a fourth address subset assigned to a service instance entry in the address table associated with a second index value that is a companion index value to the first index value;

assigning a combined address subset, comprising the third address subset and the fourth address subset, to the service instance entry in the address table associated with the second index value; and

clearing the service instance entry associated with the first index value from the table.

10. The network device controller of claim 9, wherein the at least one processor is further configured to perform the operations of:

determining that the first index value is less than the second index value;

changing the association for the service instance entry in the address table, associated with the second index value, from an association with the second index value to an association with the first index value.

21. The network device controller of claim 9, wherein the number of provisioned index values in the set of provisioned index values is a power of two, and wherein identifying a companion index value for a particular index value comprises adding half the number of provisioned index values in the set of provisioned index values to the particular index value, modulo the number of provisioned index values in the set of provisioned index values.

15. Tangible computer readable media storing instructions which, when executed by one or more computing processors, cause the one or more computing processors to:

provide an address table including a set of entries, wherein;

the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of a distributed service;

add a new service instance to the address table by;

obtaining an assignable index value to assign to the new service instance by

     1) identifying an existing, unassigned, index value in the set of provisioned index values, or by

     2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value;

identifying an assigned index value that is a companion index value to the obtained index value;

dividing a packet source address set associated with the companion index value into a first address subset and a second address subset; and

assigning the first address subset to the service instance entry in the address table associated with the assigned companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance; and

remove a service instance from the address table by;

identifying a third address subset assigned to a service instance entry in the address table, associated with a first index value, for the service instance to be removed;

identifying a fourth address subset assigned to a service instance entry in the address table associated with a second index value that is a companion index value to the first index value;

assigning a combined address subset, comprising the third address subset and the fourth address subset, to the service instance entry in the address table associated with the second index value; and

clearing the service instance entry associated with the first index value from the table.

16. The computer readable media of claim 15, the instructions comprising instructions to cause the one or more processors to:

determine that the first index value is less than the second index value;

change the association for the service instance entry in the address table, associated with the second index value, from an association with the second index value to an association with the first index value.

17. The computer readable media of claim 15, wherein the number of provisioned index values in the set of provisioned index values is a power of two.

18. The computer readable media of claim 17, wherein increasing the number of index values in the set of provisioned index values comprises doubling the number of provisioned index values.

19. The computer readable media of claim 17, wherein identifying a companion index value for a particular index value comprises adding half the number of provisioned index values in the set of provisioned index values to the particular index value, modulo the number of provisioned index values in the set of provisioned index values.