Client-side Load Balancing

[ejona86]

For the moment, all things client-side load balancing. Designs, requirements, etc. Can be split into separate issues as appropriate.

There is an internal load balancing design that needs to be made public. This is on @a11r's plate.

There is want to support ZooKeeper. It may need a different Channel implementation than the one necessary for the doc @a11r will share.

@louiscryan
@jhump
@mzhaom

[ejona86]

Consider supporting affinity, in addition to basic load balancing.

[ejona86]

Note that this includes a bit of Service Discovery, as the two are commonly interrelated.

[ejona86]

@zhangkun83

[dhendry]

Is there any active work being done on this or guesstimates on timelines for official support? Im in the process of throwing together a quick and dirty dynamic routing channel (backed by zk) which, if it works out, may be possible cleanup and contribute back to address this ticket.

[zhangkun83]

@a11r has a design doc (not finalized yet) for a general load-balancing solution across languages. The idea for now is to put all the complex algorithms in a stand-alone load-balancer. The client requests the load-balancer for a list of servers, and uses a dumb policy (e.g., round-robin) to distribute requests to these servers. I don't know when the design will be delivered.

[jhump]

I'd be very interested in seeing how this comes together. I have a more elaborate design that is based on what the abstractions look like in an existing protobuf-based RPC system. I can even share:

(Edit: fixed the link to a doc accessible outside of squareup.com)
https://docs.google.com/document/d/1epDtAQ56AkxJyhIhWP6nyMmUFJD2pLd4y5qakSJTXbk/edit#heading=h.ax3xfgj40nuq

There are some open issues that aren't solved in our existing systems -- mainly around managing dynamically sized connection pools. (Our current RPC system requires this be statically configured, but what we really want is something that is reactive and can add and close connections as needed based on desired levels of connection redundancy and traffic levels per connection.)

[zhangkun83]

@jhump: the design we have internally wants to put most of the server selection work in the gRPC-specific load-balancing server. The client would have minimal selection logic, e.g., round-robin. This is to prevent the duplicate work of implementing an algorithm in all languages. We have defined the protocols among the client, the server and the load-balancer. The design also defines a gRPC-specific service discovery protocol, which still needs work.

I feel we need a consensus over a general load-balancing solution before discussing any language-specific APIs or SPIs.

[jhump]

@zhangkun83 Interesting. When can you share more info about this solution? I'm curious about how all of the components interact and what capabilities you expect to support this way.

BTW, as soon as you provide a separate server that implements the logic, then it's not really an SPI so much as an actual implementation. I was under the impression that an SPI would be added to allow plugging in alternate implementations. I'm more interested in what those interfaces look like, because I already have my own implementation that I want to drop in. I guess we could switch to the approach and implementation you describe, but only if we don't lose any key features we already have in our existing system.

Going further, what you describe still fits fine with the interfaces I described in that doc. It just won't really need any "smarts" in any of the components, it won't have need for "backend metadata", and the ServiceDiscoverySystem interface can be implemented as a client of the GSLBs (and all of the "smarts" go there).

[zhangkun83]

@jhump Sorry for being silent for so long. I have some update for the design work from gRPC team. The service discovery (aka name resolution) functionality is now an independent part of the system, and LB relies on it. The work flow would be -

1. Application creates a top-level channel with a service name
2. The top-level channel uses a name resolver, passes the service name, and gets a list of addresses, a channel factory, and possibly other service configurations. The name resolver is plug-able, e.g., there will be DNSNameResolver, ZooKeeperNameResolver etc.
3. The top-level channel connects to a returned address, by creating an underlying channel with the returned channel factory. If connection fails, retry with next address in a round-robin manner.
4. Once connected to an address, the channel sends an LB request. Three cases:
   1. Server returns not-implemented error, because it's not LB-aware. The client then can start making normal RPCs on this connection.
   2. Server is a gRPC load-balancer and returns LB response. The following will be covered by the LB protocol, in which the load-balancer dictates what servers the client should send RPCs to.
   3. Server is not a gRPC load-balancer but is LB-ware, and it redirects the client to a load-balancer.

That's the basic idea. There will be an SPI for the name resolver. As for LB, the client-side logic and the server-side LB-awareness logic are fixed, while the load-balancer is open-ended, as long as it complies with the LB protocol.

There are still moving parts in the design, and we look forward to sharing the design when it's ready.

[mwitkow]

@zhangkun83 it's great to hear the grpc working on this :) Few questions from a curious bystander:

Re 3. How is the channel picked? Can it be picked at random so that even if the backend is not LB-aware 4.i. will provide some load spreading?

Re 4.ii Is this for the purpose of implementing an in-band LB, or just an LB "lease" protocol that will control where the client sends the RPCs to? Will this come only from the first server the client connects to?

Re 4.iii By LB-aware, does it mean that the gRPC server can provide rich metrics? E.g. a load factor that can be used by the in-client load-balancing policies such as weighted round-robin?

Are you planning to introduce any healthchecking, so that a non-healthy backend can be eliminated from the channel factory, even though the service discovery indicates its there?

[zhangkun83]

@mwitkow-io I am answering based on the current status of the design. Please note it's not finalized yet. We will publish it once we feel it's ready.

Re 3. How is the channel picked? Can it be picked at random so that even if the backend is not LB-aware 4.i. will provide some load spreading?

It's picked at random.

We will support a use case where name resolver returns just backend addresses, and the client does round-robin on them. 4.i. falls into this case.

Re 4.ii Is this for the purpose of implementing an in-band LB, or just an LB "lease" protocol that will control where the client sends the RPCs to? Will this come only from the first server the client connects to?

By "in-band LB", do you mean a proxy-like LB server? The LB server won't proxy traffic. Periodically the LB server sends the client a list of servers for the client to round-robin on. Through the server lists the LB server controls the order and frequency in which the client uses the servers. If there are multiple LB servers returned by name resolver, they are equivalent. The client will just stick to one LB server.

Re 4.iii By LB-aware, does it mean that the gRPC server can provide rich metrics? E.g. a load factor that can be used by the in-client load-balancing policies such as weighted round-robin?

LB-aware just means the server recognizes the LB protocol, so that even if the server is not an LB server, it can redirect the client to a real LB server. gRPC servers reports load information to LB servers. There won't be any in-client LB policies other than plain round-robin. Complex policies such as weighted round-robin is done by LB servers sending the client server lists where servers appear in the desired order and frequency. For example, by sending "A A B" to the client, the LB server makes the client split the load between server A and B by 66% and 33%.

Are you planning to introduce any healthchecking, so that a non-healthy backend can be eliminated from the channel factory, even though the service discovery indicates its there?

gRPC will have health checking support, which will be used by LB.