Cloud Native Computing Foundation KubeCon + CloudNativeCon North America 2020 - Virtual, 4 Dec 2020

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Improving Network Efficiency with Topology Aware Routing - Rob Scott, Google

Description

Don’t miss out! Join us at our upcoming event: KubeCon + CloudNativeCon Europe 2021 Virtual from May 4–7, 2021. Learn more at https://kubecon.io. The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects.

Improving Network Efficiency with Topology Aware Routing - Rob Scott, Google

As Kubernetes clusters grew to span multiple zones and regions, it became clear that we needed to improve network routing. The initial kube-proxy implementation meant that all requests were equally likely to go to any endpoint, regardless of how far away it was. With topology aware routing, kube-proxy will attempt to keep network traffic within the same zone or region if there is sufficient capacity. This can have huge impacts on network efficiency, performance, and scalability. This talk will cover the evolution of topology aware routing in Kubernetes including the options that didn’t end up working. It will demonstrate how the current algorithm works, discuss the tradeoffs of the approach, and show the simulations that were run to develop the algorithm. Finally, this talk will provide some data showing the significant impacts this feature can have on Kubernetes networking.

https://sched.co/ekCN

A

Hey my name is rob scott and I get to work with a great team at google on kubernetes networking today. I want to talk with you about improving network efficiency with topology, aware routing, but before we get into that, I want to provide just a brief outline of how I want to structure today's talk.

A

First, I'm going to go through a little bit of background as far as how we got to where we are and then cover our first attempt at topology, aware routing and some of the limitations associated with that, then I want to explain our second attempt and what we're trying to do differently this time, as well as how that actually performs in real life, with the simulator simulating millions of different inputs and scenarios.

A

And finally, I want to provide a long-term vision for where we see this going in the months and years to come.

A

But before I go any further, I have to add some disclaimers topology aware routing is hard to get right. This talk attempts to show our thought process here and I'll be the first to say this approach is not perfect. We still have lots of areas for improvement, and things still could change, but I wanted to bring attention to the direction we're going and the improvements we're hoping to make here.

A

So, let's get into the background a little bit now, if you've used kubernetes recently, you've probably created a service or a pod or both, and if it's a new cluster, a relatively new kubernetes cluster, it probably has the endpoint slice controller running and that watches services and pods and creates endpoint slices based on those and those endpoint slices are just lists of pod ips for each service and couproxy watches those endpoint slices and configures iptables on each node.

A

So what does iptables look like here?

A

Iptables configuration that we're writing is very much based on probabilities, so I copied this little snippet from iptablesconfig on a node in one of my kubernetes clusters that had a two endpoint service and that just means a service with two pods behind it, and in this case we have two key lines here.

A

First, if you're targeting this service, there should be a 50 probability that you'll choose this specific service endpoint, so that 0.5 probability and second, if you don't choose that service endpoint continue down the list, and since you haven't chosen that endpoint, you should choose this second service endpoint. So each endpoint has a 50 chance of being chosen and you can see that same thing, scaled out to thousands or even a hundred thousand endpoints across different kubernetes clusters. We rely heavily on iptable's probabilities.

A

Now this works, but it does come along with some issues. Traffic is distributed randomly across all endpoints, regardless of where it actually originates from. So in a three zone. Cluster traffic is more likely to go to another zone than to stay in the zone it actually originated from, and every instance of coup proxy needs to keep track of every single endpoint in your cluster, which means the larger a cluster gets the more end points every instance of kubeproxy has to manage, which results in slower updates and even sometimes more latency.

A

We also have to work within some constraints here: coupe proxy doesn't handle requests directly. It just programs iptables or ipvs, and that's great in many cases it means, if there's some kind of problem with coop proxy. Your networking doesn't break immediately.

A

Instead, it just relies on whatever was already in iptables config or ipvs config, which is good because coup proxy is not perfect, but unfortunately it means we don't have visibility into request errors or timeouts, and it's really difficult to understand when an endpoint is overloaded and also coup proxy is deployed on each node in your cluster.

A

So any significant change could be expensive, so think about this, because it's running on every node in your cluster, any change to an endpoint anywhere in your cluster has to be sent out to every instance of crew proxy on every node. So if we're updating, endpoints more frequently that's expensive, similarly, more advanced logic increases cpu utilization again on each node, which is significant overhead to add on every single note in your cluster, so we have to be careful with any approach we take here. Okay. So with that background, let's talk about our first attempt.

A

We added a new alpha api field to services called topology keys. This allowed for endless flexibility.

A

You could specify arbitrary topology keys in any order and coup proxy would then filter endpoints based on those topology keys based on those labels, so any endpoints with matching values for those labels would be filtered in and everything else would be excluded from what couproxy considered on a given node a wild card character could then be used to indicate that if matching labels couldn't be found, traffic should be routed elsewhere.

A

So let's take some concrete examples here of this configuration first, if you wanted to require traffic stay in the same zone or region, your topology keys might look something like this, and if, instead in of requiring, you are fine with just preferring the traffic stay in the same zone or region, you would add that final wild card at the end of the field.

A

So this made sense it was a very powerful api, but it did come with some real limitations now. First off this was a relatively complex api and what most users wanted was very similar traffic should stay as close to where it originated from as possible, and unfortunately that really common use case was relatively difficult to communicate with this api and it required configuration on every single service and relatively significant and complex configuration.

A

Similarly, all the logic behind this functionality lived in coup proxy, and that meant that there was extra processing on each node, and it also meant that all endpoints still needed to be delivered to every node in the cluster. Even if that node was then going to filter those endpoints out.

A

It was also a relatively difficult api to implement, so, ideally, topology keys would be given more weight if they appeared first in the list, but this would be quite difficult to achieve safely, there's a very real potential that we could overload endpoints.

A

So, let's take an example where we have a lot of traffic originating from a zone, but only one endpoint to serve that traffic. It's easy to see if you had configured a service with prefer or even require zone.

A

That would be very difficult to avoid overload now.

A

You know at first we just did some basic filtering that matched any labels based on topology keys and that kind of worked, but we still had the same risk of overload and of course, if that wild card character was passed in, then we couldn't really do any filtering because well you could route traffic anywhere.

A

So our initial implementation was very basic and it was hard to get it quite right, especially because you could have so many potential combinations of configuration.

A

So, ideally, we would prioritize endpoints matching earlier labels in the list and we'd avoid overloading those endpoints we'd also avoid sending traffic nowhere. So as an example, we would avoid sending traffic to. You know no end points if there's no end points in the zone or region.

A

We want to avoid that situation where traffic has nowhere to go, and similarly we'd make that star character behave more like a wild card more like failover configuration instead of just removing filtering altogether, and although these all seem like great goals, they became quite difficult to achieve, especially with such a flexible api.

A

So with that background we said well, maybe we should try again and in our second attempt we wanted to identify three goals.

A

First, we wanted to build consensus around a small set of topology labels that would be clearly defined and officially supported.

A

We wanted to develop a simple approach that covered the most common use cases as automatically as possible, and finally, we wanted to only deliver the endpoints that each node would actually care about. Instead of continuing to deliver all endpoints to all instances of coup proxy, we thought this would make a very significant difference for both scalability and performance.

A

So because this is kubernetes each one of these goals had an associated cap.

A

So if you're interested in all the details associated with each one of these proposals, I highly recommend you get on github and go to the kubernetes enhancements repo and look up each one of these caps, I'm going to provide a decent overview of each of them in this talk, but I simply don't have enough time to provide the same level of detail that each one of these cats provides on their own.

A

For example, cap 2004 elite apology, aware routing kep hat describes a lot of the different algorithms we considered and provides diagrams to show exactly how they might work. I don't have enough time to cover every different algorithm we've considered, but I hope I still will be able to give a decent overview in this talk.

A

So with that said, let's talk about the first cap building consensus around a small set of topology labels.

A

Now in this cap we wanted to standardize on the following labels, one for region and one for zone, and we wanted to define region and zone as being hierarchical. This meant that zones could not be spread across multiple regions, but a region could contain multiple zones.

A

We also wanted to state that these labels should be considered immutable. This is a very big deal and something that should dramatically simplify any implementations working with these labels and finally, we've left open the door for a third or maybe even fourth key to be introduced in the future, but for right now we want to keep it very simple and straightforward.

A

Our second goal was likely the most significant one. It was to develop a simple approach that covers the most common use cases as automatically as possible, and an automated approach meant we needed a good algorithm, but not just a good algorithm, a good way of evaluating lots of potential algorithms. So we could actually understand what a good algorithm was and so rick chen an awesome.

A

Google intern developed an open source tool called kubernetes topology simulator, and this allowed us to plug in any number of algorithm and run against millions of inputs to see just how well or poorly it performed and we'll cover a little bit more about this topology simulate simulator later on.

A

But let's talk about the algorithm that we ended up deciding and, of course this algorithm can still change and can still be improved. I've tried to simplify this algorithm into just a couple sentences.

A

So once a service has enough endpoints subset those endpoint slices by zone. If a zone doesn't have enough, endpoints contribute some from a zone that does so. What does it mean for a service to have enough endpoints below a certain threshold? This approach results in a lot of churn and potential for overloaded endpoints.

A

Our testing showed that approximately three times the number of zones was a reasonable starting point here. So if you had three zones, approximately nine endpoints was a good starting point. Anything below that risk significant overload potential or significant churn. So as an example, if you have three endpoints and three zones, you could theoretically distribute them across those zones evenly, but what if one zone is slightly larger than the others, or what?

A

If all the traffic is coming from one zone instead of all the zones, you have significant risks of overlook and also, if there's any changes along the way.

A

You have significant risk of churn where everything has to change across all of these zones across all of these slices and that gets expensive, so at least initially we're proposing, starting once we have a little bit of room to work with, and not just precisely nine.

A

In the three zone cluster case, we need to add a little bit of padding, both above and below, to ensure that we're not constantly flapping back and forth between approaches. So as an example, the upper limit might be closer to 12 and the lower limit might be closer to 6. When we're switching between these approaches.

A

Now, once a service has enough endpoints, we want to subset the endpoint slices by zone, so we're introducing a new label that can be set on endpoint, slices and couproxy will be updated to read from this label and only care about endpoint slices for the specific zone and, of course, for backwards. Compatibility coup proxy will continue to watch and point slices that don't have this label at all, but we imagine going forward. The vast majority of endpoint slices will get a label like this.

A

That indicates which zone they're intended for so if a zone doesn't have enough endpoints, what do we mean by a zone not having enough endpoints?

A

Now, in this case, we're talking about the number of expected endpoints, which at least initially will be based on the proportion of cpu cores in a zone? So, let's take this example. We've got a cluster that has 12 total endpoints and we've got 6 total cpu cores three of those or half of those happen to live in zone a so. We expect half of the endpoints to also be delivered to zone a and similarly one third of the cores live in zone b.

A

So we expect one-third of the expected endpoints to also be in zone b, all the way down the list. So that's relatively straightforward. But what happens if this isn't the case? If there's a zone that doesn't have enough endpoints well to minimize churn we're only going to redistribute those endpoints once a threshold has been passed, we define an acceptable overload threshold, as maybe 25, and what does overload mean it, at least in this context, we're defining it as the amount of extra traffic some endpoints might receive.

A

So if we expected 10 endpoints in a zone- and we only had eight, that would mean each of those eight endpoints were 25 percent overloaded. They had, they could get 25 more traffic than might be expected if everything was evenly distributed.

A

Now, seven endpoints, on the other hand, would be below that threshold, because now each of those endpoints would be getting 43 percent more traffic than expected, which is something we're trying to avoid. So once we reach that level of difference, it's time to start redistributing endpoints before then we rely on kind of lazy rebalancing.

A

So when a new endpoint comes in, it's automatically delivered wherever it makes the most sense. uh Now, there's a lot more to this algorithm than I can explain in this talk. So if you're interested we've included a lot more diagrams and examples in the cap itself, but finally you may be trying to picture exactly how this might work. So I thought an example might be helpful here.

A

So in this case we've got nine total pods four in zone a and two in zone c. With our original approach, all of those pods would be bunched into a single endpoint slice, but with this automatic topology aware routing approach instead, what we're suggesting is that three endpoints go into a slice for zone a same with zone b and for zone c. We only have two endpoints from zone c that we can contribute, but we have an extra one. We can take from zone a so we do that.

A

So that's a very simplified way of how we imagine this kind of subsetting would work and, of course, as I mentioned, there's a lot more examples in the cap covering a large number of potential edge cases we could run into here.

A

And finally, we want to only deliver end points that are closest to each instance of coupe proxy, instead of delivering all endpoints everywhere.

A

So we've introduced two new labels, one for zone and one for region to indicate where an endpoint slice should be delivered and coup proxy will be updated to watch endpoint slices with those labels, and so it will specifically not pay any attention to end point slices labeled for another zone or for another region.

A

So in summary, there's three main things happening here: one two official topology labels zone and region are now well defined. Two endpoint slices can be delivered to zones or regions, and three users can opt into automatic topology aware routing on every service.

A

This will likely start as an annotation, but could be extended in the future, and maybe, if we're lucky we'll get this done well enough- that we could even default this to just being enabled and we wouldn't need any configuration at all.

A

So, with all that background, now that you understand how this approach works, it would be helpful to understand how our simulation actually scored this approach.

A

So to understand our score to understand our results, it's helpful to understand what we were evaluating algorithms on, so we gave a high weight to the percent of traffic that stayed in zone and that weight was 45 of the total score.

A

Next, we cared about overload the proportion of extra traffic that any single endpoint might expect to receive in a simulation so across our 39 million inputs that we tested every algorithm against our max overload got a 20 contribution to the total score. So our worst case scenario, you know of those 39 million inputs, the single worst endpoint of all those inputs that got the most overloaded.

A

We gave that a weight of 20 and then we also wanted to make sure that our average case was also quite low, so we uh also gave weight of 20 to our average overload.

A

And finally, we also cared about the proportion of new endpoint slices that would be required with this approach, so we gave a weight of 15 to that proportion. So our automatic approach actually scored reasonably well.

A

Here it managed to keep 84 percent of traffic in zone, which is significantly better than the original approach, which you would expect, because the original approach wasn't even trying to keep traffic in zone, but 84 we thought was quite good because all these inputs included a lot of edge cases, the kind of edge cases where you'd have hundreds of endpoints in one zone and only one in another zone, and so you end up with some really impressive results. Given those highly lopsided inputs.

A

What we observed when results were more balanced or more normal was significantly better than even this 84 percent and then next our overload our overload was quite good.

A

On average, it was around 1.7 percent, uh which we thought was a reasonable level of overload, and although it's not quite as good as the original, it still felt like a reasonable compromise to get to that very high level of end zone traffic and again overload performs significantly better uh when you aren't dealing with all these wild edge cases that we had in our inputs and finally, for extra slices.

A

uh The new automatic approach required approximately 37 percent, more endpoint slices than the original approach, but even still that did not seem like a significant issue and definitely seemed worth all the advantages that we got for keeping traffic in zone. So overall, our simulator gave this automatic approach an 87 percent score compared to a 73 score for the original approach.

A

So we recognize there's still room for improvement here, but we think what we have already is a significant significant step in the right direction, and with that I want to talk just a little bit about our long-term vision here, because really we're still in a pre-alpha stage, we're still very early in this process and we still could use feedback and we still could use a lot of work.

A

Our first priority is to get this into alpha and get some feedback we're hoping we'll hit that target in kubernetes 1.21. We also have a number of open questions you know. Obviously how can we improve this approach? If you have ideas, if you have feedback, don't hesitate, get in touch. Comment on the cap come to sig network, whatever it happens, to be we'd, love to hear what you're thinking and we're also interested in.

A

If we can use any kind of similar patterns for dns, but is there any additional configuration we need to provide for say power, users or advanced use cases, and on the other side, can we eventually make this good enough that we can just make this the default? And we won't need any configuration at all now, some longer term, bigger picture questions are: how can we implement topology aware routing with real time feedback?

A

This is really the goal. If we had real-time feedback, we could detect overloaded endpoints and route traffic elsewhere automatically. This is really something that would be great to include inside kubernetes, but it requires a lot of changes all the way up and down the stack and is a bigger project that will not be done, probably in the next uh couple release cycles, at least, but we're still thinking about it and we're trying to picture ways that we could actually achieve this.

A

And finally, can we do any of this redistribution of traffic without updating endpoint slices on each change, because right now we're highly reliant on updating endpoint slices to describe what crew proxy should do where a coup proxy should route traffic, which is fine, but it seems like there's, probably a bit more room to add local optimizations, maybe in cube proxy that could require less updates to endpoint slices.

A

So this is just a sampling of the things we're thinking about there's plenty more. Many of them are addressed in the caps. So if you're interested I'd, definitely encourage you to get involved, ask questions provide feedback, we'd love to hear from you. So thanks so much for coming. My name is rob scott. uh You can find me on slack, github, twitter, etc.

A

If you have any thoughts about how we can make this even better I'd love to hear from you thanks so much.