METHODS AND SYSTEMS FOR LOAD BALANCING BASED ON DATA SHARD LEADER

• US 20170024453A1
• Filed: 07/20/2015
• Published: 01/26/2017
• Est. Priority Date: 07/20/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kumar, Abhishek, Rameshan, Kamalkrishna, Singh, Harmanpreet, Raja, Moiz
• Granted Patent: US 10,091,087 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Disclosed are systems, methods, and computer-readable storage media for load balance resources amongst computing nodes. Various embodiments of the present technology can be used to, prior to assigning a first data shard included in a first cluster of data shards as a leader of the first cluster of data shards, determine whether a first computing node storing the first data shard also stores a second data shard designated as a leader of a second cluster of data shards, yielding a determination, and when the determination indicates that the first computing node stores the second data shard designated as the leader of the second cluster of data shards, designate the first data shard as non-electable to be the leader of the first cluster of data shards and electing an alternate data shard included in the first cluster of data shards as the leader of the first cluster of data shards.

Claims

1. A method comprising:

prior to assigning a first data shard included in a first cluster of data shards as a leader of the first cluster of data shards, determining whether a first computing node storing the first data shard also stores a second data shard designated as a leader of a second cluster of data shards, yielding a determination; and

when the determination indicates that the first computing node stores the second data shard designated as the leader of the second cluster of data shards, designating the first data shard as non-electable to be the leader of the first cluster of data shards and electing an alternate data shard included in the first cluster of data shards as the leader of the first cluster of data shards.

2. The method of claim 1, further comprising:

when the determination indicates that the first computing node does not store the second data shard designated as the leader of the second cluster of data shards, assigning the first data shard as the leader of the first cluster of data shards.

3. The method of claim 1, wherein the leader of the first cluster of data shards orchestrates replication of data amongst the first cluster of data shards and the leader of the second cluster of data shards orchestrates replication of data amongst the second cluster of data shards.

4. The method of claim 1, further comprising:

prior to determining whether the first computing nodes stores the second data shared designated as the leader of the second cluster of data shards, electing the first data shard as the leader of the first cluster of data shards.

5. The method of claim 4, further comprising:

prior to electing the first data shard as the leader of the first cluster of data shards, determining that the first data shard is designated as eligible to be the leader of the first cluster of data shards.

6. The method of claim 1, further comprising:

while the first data shard is designated as non-electable to be the leader of the first cluster of data shards, determining whether a resource weightage for the first computing node meets or exceeds a threshold resource weightage, yielding a second determination; and

when the second determination indicates that the resource weightage for the first computing node does not meet or exceed the threshold resource weightage, designating the first data shard as electable to be the leader of the first cluster.

7. The method of claim 1, further comprising:

after electing the alternate data shard as the leader of the first cluster of data shards, determining whether a second computing node storing the alternate data shard includes a third data shard designated as a leader of a third cluster of data shards, yielding a second determination; and

upon a determination that the second computing node does not include the third data shard designated as the leader of the third cluster of data shards, assigning the alternate data shard as the leader of the first cluster of data shards.

8. A controller comprising:

one or more computer processors; and

a memory storing instructions that, when executed by the one or more computer processors, cause the controller to;

prior to assigning a first data shard included in a first cluster of data shards as a leader of the first cluster of data shards, determine whether a first computing node storing the first data shard also stores a second data shard designated as a leader of a second cluster of data shards, yielding a determination; and

when the determination indicates that the first computing node stores the second data shard designated as the leader of the second cluster of data shards, designate the first data shard as non-electable to be the leader of the first cluster of data shards and elect an alternate data shard included in the first cluster of data shards as the leader of the first cluster of data shards.

9. The controller of claim 8, wherein the instructions further cause the controller to:

when the determination indicates that the first computing node does not store the second data shard designated as the leader of the second cluster of data shards, assign the first data shard as the leader of the first cluster of data shards.

10. The controller of claim 8, wherein the leader of the first cluster of data shards orchestrates replication of data amongst the first cluster of data shards and the leader of the second cluster of data shards orchestrates replication of data amongst the second cluster of data shards.

11. The controller of claim 8, wherein the instructions further cause the controller to:

prior to determining whether the first computing nodes stores the second data shared designated as the leader of the second cluster of data shards, elect the first data shard as the leader of the first cluster of data shards.

12. The controller of claim 11, wherein the instructions further cause the controller to:

prior to electing the first data shard as the leader of the first cluster of data shards, determine that the first data shard is designated as eligible to be the leader of the first cluster of data shards.

13. The controller of claim 8, wherein the instructions further cause the controller to:

while the first data shard is designated as non-electable to be the leader of the first cluster of data shards, determine whether a resource weightage for the first computing node meets or exceeds a threshold resource weightage, yielding a second determination; and

when the second determination indicates that the resource weightage for the first computing node does not meet or exceed the threshold resource weightage, designate the first data shard as electable to be the leader of the first cluster.

14. The controller of claim 8, wherein the instructions further cause the controller to:

after electing the alternate data shard as the leader of the first cluster of data shards, determine whether a second computing node storing the alternate data shard includes a third data shard designated as a leader of a third cluster of data shards, yielding a second determination; and

upon a determination that the second computing node does not include the third data shard designated as the leader of the third cluster of data shards, assign the alternate data shard as the leader of the first cluster of data shards.

15. A non-transitory computer-readable medium storing instructions that, when executed by one or more computer processors of a controller, cause the controller to:

prior to assigning a first data shard included in a first cluster of data shards as a leader of the first cluster of data shards, determine whether a first computing node storing the first data shard also stores a second data shard designated as a leader of a second cluster of data shards, yielding a determination; and

when the determination indicates that the first computing node stores the second data shard designated as the leader of the second cluster of data shards, designate the first data shard as non-electable to be the leader of the first cluster of data shards and elect an alternate data shard included in the first cluster of data shards as the leader of the first cluster of data shards.

16. The non-transitory computer-readable of claim 15, wherein the instructions further cause the controller to:

when the determination indicates that the first computing node does not store the second data shard designated as the leader of the second cluster of data shards, assign the first data shard as the leader of the first cluster of data shards.

17. The non-transitory computer-readable of claim 15, wherein the leader of the first cluster of data shards orchestrates replication of data amongst the first cluster of data shards and the leader of the second cluster of data shards orchestrates replication of data amongst the second cluster of data shards.

18. The non-transitory computer-readable of claim 15, wherein the instructions further cause the controller to:

prior to determining whether the first computing nodes stores the second data shared designated as the leader of the second cluster of data shards, elect the first data shard as the leader of the first cluster of data shards; and

prior to electing the first data shard as the leader of the first cluster of data shards, determine that the first data shard is designated as eligible to be the leader of the first cluster of data shards.

19. The non-transitory computer-readable of claim 15, wherein the instructions further cause the controller to:

while the first data shard is designated as non-electable to be the leader of the first cluster of data shards, determine whether a resource weightage for the first computing node meets or exceeds a threshold resource weightage, yielding a second determination; and

when the second determination indicates that the resource weightage for the first computing node does not meet or exceed the threshold resource weightage, designate the first data shard as electable to be the leader of the first cluster.

20. The non-transitory computer-readable of claim 15, wherein the instructions further cause the controller to:

after electing the alternate data shard as the leader of the first cluster of data shards, determine whether a second computing node storing the alternate data shard includes a third data shard designated as a leader of a third cluster of data shards, yielding a second determination; and

upon a determination that the second computing node does not include the third data shard designated as the leader of the third cluster of data shards, assign the alternate data shard as the leader of the first cluster of data shards.