Skipper: loadbalancer algorithms

[szuecs]

• #536 implemented a loadbalancer feature with only roundrobin algorithm.
• After #556 we should have a solid code base to easily implement different algorithms per route.

We want to have some other algorithms being possible and able to choose per route (for example from ingress). Algorithm ideas we could support:

• [x] random
• [x] consistent hashing (supports sticky sessions across one TCP/IP connection)
• [ ] roundrobin with slow ramp up https://github.com/zalando/skipper/issues/1207
• [ ] least requests https://blog.envoyproxy.io/examining-load-balancing-algorithms-with-envoy-1be643ea121c
• [ ] [jump consistent hashing](https://arxiv.org/pdf/1406.2294.pdf)
• [ ] [consistent hashing with bounded loads](https://arxiv.org/abs/1608.01350)
• [ ] [ketama consistent hashing](https://github.com/RJ/ketama)
• [x] least of N choices (N=2 is a good choice maglev and Dropbox https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf https://brooker.co.za/blog/2012/01/17/two-random.html)
• [ ] LRU (adds memory usage)
• [ ] closest (by ip on the local node)
• [ ] fastest response (maybe complicated to do, because metrics lookup required)
• [ ] [Maglev](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf) (if possible)
• [ ] Weighted round robin
• [ ] [deterministic aperture](https://twitter.github.io/finagle/guide/ApertureLoadBalancers.html#deterministic-aperture) pdf slides SREcon19, important add randomness: https://blog.twitter.com/engineering/en_us/topics/infrastructure/2019/daperture-load-balancer.html

least of N choices background

Data to compare to select the least of N choices (https://medium.com/netflix-techblog/netflix-edge-load-balancing-695308b5548c):

1. Client Health: rolling percentage of connection-related errors for that server.
2. Server Utilization: most recent score provided by that server.
3. Client Utilization: current number of inflight requests to that server from this load balancer.

[ruiaraujo]

Weighted round robin would also be a good alternative, where the weight is dependent of the size of the nodes.

[szuecs]

@ruiaraujo can you elaborate on how to pass the data you need from nodes to the load balancer?

[ruiaraujo]

Could be something like a weight on each target.

Use case
I deploy my application using Spot of multiple sizes. My apps reacts and takes advantage of the added CPUs.

I have Skipper as LB where the route has the meta information on each node relative size and the roundRobin would take advantage of this information to generate the right amount of load for each target.

I have no idea how this would look and how it should be specified.

[szuecs]

I think a simpler algorithm that could have a similar effect is the best (least) of N choices, but we would need to have data per backend in lbcontext for the lb algorithm.

[szuecs]

@ruiaraujo I added your suggestion to the list

[ardaguclu]

I would like to work on "least requests". Because round robin does not uniformly distribute traffic between nodes especially if long active connections exist. Do you have any concern or objection before that? @szuecs

[szuecs]

As discussed in slack there is https://github.com/zalando/skipper/pull/1507 that you can test or also check the code to make a new PR, if you like.