Load balancing

Static

Round robin

• Weighted round robin

  • Cons: It may result same node being picked during several consecutive requests.

• Smooth weighted round robin

  1. For each node, currentWeight = currentWeight + weight

  2. Pick the max currentWeight node as target node

  3. Change target node currentWeight = currentWeight - sum(weight)

Random

• When compared with round robin, the later could be more smooth. Because random-number based could make several consecutive requests landing in one node.

Consistent hashing

• Normal hashing algorithm

  • Cons: Too many items to migrate during resharding

• Consistent hashing

  • Cons: Uneven load during scale up/down

• Consistent hashing with virtual nodes

  • The interval between nodes could be uneven, but the load will be even.

Pros

• If local cache is enabled on servers, then consistent hashing could reduce the inconsistency.

  • Using UserID as key, if request 1 for user ID comes to server 1, then request for this user will always land on this node. It will result in better consistency when compared with round robin, etc.

  • However, it could not completely resolve the inconsistency. For example, when cluster scales up, the old request could land on old node and new request could land on new node.

Complexity analysis

• Assume the total number of data M, the total number of nodes N

• Read/write complexity increases from O(1）to O(lgn) When compared with traditional hashing because consistent hashing read/write steps are as follow:

  1. Convert hashkey into 32 bit int number. O(1)

  2. Use binary search to find the corresponding node. O(lgn)

• Data migration complexity decreases from O(m) to O(m/N).

References

• Data distributed in multiDC: https://www.onsip.com/voip-resources/voip-fundamentals/intro-to-cassandra-and-networktopologystrategy

• Consistent hashing in Cassandra documentation: https://cassandra.apache.org/doc/latest/architecture/dynamo.html

Based on metric numbers

• Least num of connection

• Least num of ongoing requests

• Fastest response time

How to collect metrics

• Client report to metric collector

Cons

• These approaches don't take the request itself into consideration.

• For example, using the lease num of connection. There might not be that many requests but each request could be pretty big.

Dynamic