Smart Routing at Scale: How Spotify’s XDS Control Plane Cut 75%... Yannick Epstein & Anya Hristova

This talk focuses on how Spotify decreased its cross-zone traffic costs by 75% using an XDS control plane and a zone-aware routing algorithm. The speakers, Ana Christoa and Yanikai, discuss their initial challenges with service discovery systems and the costs associated with cross-zone traffic, emphasizing the need to optimize routing without sacrificing reliability. They detail the transition from a DNS-like service discovery to a dynamic control plane that incorporates load balancing policies based on zone locality. By implementing a new methodology that considers real-time load reports from clients, they enhance their routing decisions, ultimately increasing efficiency and reducing costs. The session also touches upon the development of a dynamic capacity model to better manage service loads and respond to evolving traffic patterns.

Good afternoon, CubeCon. Oh, this is exciting. Hi. Um, thank you for coming. Hello. Thank you for joining us on a late afternoon. I assume if you're here today, you're probably running workloads in multiple availability zones. And you've maybe looked at your cloud bill and thought, what is Corzone? Why is it so expensive? My name is Ana Christoa. I'm Yanikai >> and today we're going to tell you

how we cut our cross zone eress by 75% using our XDS control plane. We're going to go through the problem. We're going to go through uh one of the optimizations we made initially with DNS. We're then going to talk about the zoneware routing algorithm that we implemented, the heristics behind it with XDS. Um, we're going to go through the system architecture and some key optimizations that we

implemented as well as stories from production. So, what maybe didn't go so well? Um, and how could we improve the algorithm. So, let's dig in. Um, I hope you've all heard of Spotify, but if you haven't, it's an audio streaming company, 180 markets. I'm not going to go through each of those numbers, but I hope that what they convey is the scale at which we operate and

that is a multi-reion multiszone infrastructure where routing decisions make a big difference. So to start with the fundamentals, what is a zone? A zone um an availability zone is an isolated physical location inside a region. And zones have purpose. Their purpose is to provide high availability and resiliency. So if one zone goes down, your service will keep serving through the other zones. To put things in perspective,

one zone has multiple pots, one region has um multiple zones and then you get Spotify um multiple regions, multiple zones, all connected by more than two million nodes in a mesh. And at that point you might be thinking, we get it. Spotify is big. Um, but there is a point to it. As it turns out, crozone traffic costs money and it might not be a lot per

per request, but imagine at that scale, you have service A calling service B, calling service C and D. And each of those could cross a zone. Um, intuitively, and you know that accumulates, and the money quickly builds up. Intuitively, you might think, well, we could keep we could keep requests within the same zone, but that kills the purpose of zones because it compromises your reliability. And so,

it quickly becomes an optimization challenge. How can we keep as much traffic as possible within the same zone without compromising our reliability and keeping high availability? We're going to start with the solution back in the day when we first saw the problem when we were using DNS's service discovery. So our service discovery system was called Nameless. And Nameless was a lot like a phone book. It could

give you IPs. It could give you a flat list of IPs, but it didn't give you more information than that. Just like a phone book, it doesn't give you the time zone or if uh the line is busy. And so if we take an example, a playlist client would like to call a metadata service. It should do a DNS lookup to nameless. It would get a flat

list of IPs. And then the client will try to choose an IP with our custom load balancer called ELS. ELS stands for expected latency selector. And as the name suggests, it tries to choose based on the lat on the expected latencies of those IPs. As it turns out though, latencies between zones and within the zones are very similar. So ELS was kind of blind to zones. Um

we evaluated a few solutions but the most optimal one we found was to give zono data to your ls and you could do that by using a gc uh tool called orca. So it's open request cost aggregator. It allows the server to send uh the client some data and in our case that is a zone. So ELS with TLS we could now configure a zono bias and

that zonob bias acted like a synthetic penalty for crosszone traffic. So what ELS saw was that um request that IPs on different zone rather than the client are going to take more time and so it would choose the current zone. But maybe you see the problem with that and I'm going to use an analogy. So, if you're at the concert hall and you'd like to go to

the bar, you're going to choose the shortest line, but what you don't know is that everybody else around you chose exactly the same shortest line. So, a locally optimal solution became globally suboptimal. We had to be careful about how we configure that bias so that we don't overload the zone that we're sending the request to. And so, that solution had a limitation. We managed to achieve down

from 70% crozone traffic, we managed to go down to 40%. And if you're interested in the solution, check out this talk by my colleague Yanik and Alex Mitch from CubeCon 2024. Um, highly recommend. we had to think globally. Local decisions were not enough. And this is where the paradigm shift came in. DNS acted as a phone book. Exs now acts as a live dispatcher. It sees every

note in the mesh and could make a decision based on that. What is XS? It was first introduced for envoy proxies. It is now a CNCF standard. Um, and the power of XDS comes from its built-in API allows typed resource discovery. The two types we're going to talk about today is EDS, the endpoints discovery service and the cluster discovery service. So EDS allows you to group endpoints

based on locality and weight. So a locality would be uh a region, a zone, a subzone and then you could give it weight. So certainly you could say in zone A I want to send that much traffic that percent I want to send 30% to zone A. Um and to kind of emphasize the power that is what we needed at that time. So that's what we chose.

But with endpoints you could if you depending what your component can compute you could give CDS any key value pair. Um if you think about then CDS when the client connects to the control plane we're going to push a load balancing policy which is weighted round robin. The client is going to use that uh that load balancing policy in order to pick a zone based on the

weight. It's then going to pass the selection of an endpoint to ELS which is our leaf load balancer. And so suddenly we had a two-level routing. The control plane could decide the zone and then the leaf load balancer can pick the endpoint for you. It is you know it's a global solution that allowed us to do what Yanick is going to talk about next. But if you're

more interested about um this the XDS and how we implemented it, you could check out another CubeCon talk from last year uh by our colleague Eric Lingbot and Eric Amano. So we have this powerful tool. We can push weight. We can push localities. But how do we calculate the weights? So I'm going to pass it on to Yanik to tell you more about that. >> Yes, thank

you so much. Um so I'm going to talk a bit about how we actually configure those weights in the control plane and therefore get zonware routing. So let's think about the problem right. So what we are trying to do is we are trying to send as much traffic same zone as we can right because we don't want any cross zone traffic. So let's look at the typical

example right so we have a bunch of clients they are distributed across zones and we have a bunch of servers they are distributed across zones as well and the distributions don't match that's pretty normal right because clients and service servers are different services after all right so what would we tell clients in zone A for example in order to get as little cross traffic as possible well

naively we would just tell them send everything same zone problem solved right uh well not quite If we would do that in this case, 40% of the clients, they would send all their traffic to 25% of the servers. That's a classic overload, right? So, we would just degrade a zone just to get no uh crossone traffic. Not the best trade-off. Um, so there must be an alternative,

right? And there's work that already exists in the open source space, especially in the envoy community. So they have an algorithm and it can be summarized as fill local and spill the rest. So let's walk through what anyone would do u in this case with the algorithm. So it would look at the zone and now think like what percentage of traffic can I move to the same

zone. And if you think about it, let's say every client produces one request per second and every server instance can handle one request per second. Well, then if you have 40% of the clients in zone A, you have maybe 40 requests per second and 25 requests per second can be served by the servers in the same zone. So you can keep 62.5% in the same zone without

overloading the servers. But then the servers are full like they won't have more capacity. So you have some leftover traffic that envoy calls spillover. It's 37.5%. So let's see how we can distribute that. We will see that in a second. But first, let's move on on getting more same zone traffic. Let's look at clients in zone B. Right? Seems they are only 40% of the clients in

zone B, but 50% of the servers. So, everything fits same zone. Nice. Uh, but we actually do have even some leftover capacity. We might use that later to handle the spillover. So, let's look at the last zone, right? Zone C. Uh, we have 20% of the clients here and 25% of the servers. So we can again keep everything same zone and we have some leftover. So let's

see what can we do with spillover now that we have basically maximized same zone traffic. Well we have some zones that have some leftover capacity. So uh if you do the math you will find that 37.5% of 40% of the traffic that comes uh that originates from zone A that's 50% of the total traffic and we still have 50% of the total capacity across zones. That's not

a coincidence. That's by design. So how would we distribute the 50%? Well, proportional to the residual capacity in each zone. And what you get is like a clean assignment. Um so zone A keeps 62.5% local and the rest you spill to the zones according to their size. Um so in total and huristic in this case would achieve 84 85% same zone traffic and spill some of the

traffic and that's actually optimal. So let's think about this a bit more formal. Um so if you look at invoice horistic it really tries to do the following. It minimizes crossone traffic by not overloading any zone. And it makes two assumptions to do this. The first assumption is that the actual distribution of capacity is equal to how servers are distributed across zones. So it looks as host

counts right. It does the same also for clients. So it looks as host counts and says oh clients are distributed in this way then also the traffic must be distributed in this way. Uh and if those two assumptions hold true you can prove the following. First you can prove that no zone is overloaded. Right? This is intuitively clear I think. First you try to push as much

traffic same zone as possible without overloading it. And then you have some leftover and you only use the leftover capacity for the leftover traffic. Right? So you're not ever going to create an overload. And even better, the horistic is also optimal. So because you're first assigning all the same zone traffic, you can't define an assignment that has more same zone traffic than the one you already picked.

Uh so those are very nice mathematical foundations. Uh but there's these two assumptions. So let's discuss them a bit. First assumption was that how the server instances are distributed is equal to how the capacity is actually distributed. Um I would say this is pretty reasonable, right? given that server instances they usually run the same code they run the same docker image they have the same configuration they

run on the same hardware so why would they be different right so but we will get back to that but let's first assume this is reasonable but let's look at the second assumption so uh in any complex service network I would claim especially the one at Spotify we do have very different clients calling the server uh so let's consider a simple example so let's say you have

one service a it produces is about 50 requests per second per instance and then you have one service C scaled maybe more vertically than the service A and therefore maybe producing 2,000 requests per second per instance. So if you look at the whole distribution and you look at the actual traffic distribution you get very very different distributions. So I would say in any reasonable complex service network

where you have very different clients calling your service your upstream uh you are not go going to run a good horistic if you rely on the host code distribution. So what can we do like we didn't feel comfortable with this but we like the mathematical foundations of the envoy horistic. Uh so it turns out if you run an XCS control plane right you get something for free

called load reports. Um those can be they are supported in both envoy and proxy sgpc which is awesome and what you can do you can just collect what every client in your mesh is producing in terms of load and if you collect this and aggregate this you can actually calculate the traffic distribution so you don't need to make the assumptions about how yeah well clients are distributed

this way then it's traffic distributed this way you can just say oh yeah traffic is distributed this way now I can run zoneware routing and I have these nice foundational properties of the algorithm and I'm getting an optimal assignment. Uh but of course if you have a 2 million node mesh, right, collecting all these load reports, aggregating them, that's not very trivial. So I will pass it

back to Mia and she will walk you through how we designed the system to handle this at this scale. >> Perfect. Thank you, Yanik. >> Um how did we implement it? So before I go into load reports, let's get familiar with some of the components in our service discovery system. I already mentioned nameless. Nameless is a bit bigger than a DNS phone book. Now um so we

have shameless as the XS control plane. Shameless connects to the Kubernetes API in order to watch endpoint slices and store the endpoints in memory. We then also introduce Zonus. zoneless acts as a global aggregator and its main purpose is to answer how much traffic we are sending to each zone right now. And so what does a cycle look like? You have your playlist client. It will connect

to shameless as the XS control plane and it's going to start sending load reports via something called LRS, the load reporting service. It's something that you can enable on any XDS compatible client uh JBC client and it allows you to send as I mentioned load reports. So you could send the total number of requests, you could send uh successful requests, failed requests, invite requests, um probably other

things, I don't know. Um and so we'll send this loads to uh to the shameless instance that the client is connected to. Uh the shameless instance on the other side is going to get all the zono all the load reports from all the clients is connected and it's going to send them to zonus. Zoneless is then going to aggregate all the reports from different shameless instances and

it's going to send back an aggregated zonal load report. Shameless is going to use that report to calculate the weights based on Yanx algorithm and it's then going to calculate to construct the EDS response and push it back to the client. And so the client can now send based on that example 78%s to zone A, 15% to zone B, and 7% to zone C, which is pretty

cool. Um, two important things to note based on the architecture. Shameless is a zero downtime service. Um, it's a multi- instance, multi-reion service and if it goes down, clients can't talk to servers. So we can't have that. Zonus on the other hand uh is a singleton that runs on a beefyVM. Um the purpose zoneless is singleton uh is because it avoids the problem of so of having

to solve for distributed state but we could also afford to have it as a singleton because zonus doesn't have to be 100% downtime. If zonus goes down then we just go back to the previous way of zoneware routing. And so let's look at some key optimizations that we made. Something else that I probably missed to mention was um shameless QC CDS responses and pushes them to the

client every 10 seconds. So one of the key optimizations we made is to ash is to add a hash based suppression. So we would hash the ads response. We would compare it to the previous hash and if the hashes are identical, we are not going to put on the queue. So we avoid duplication. Another thing is a struggle or cancellation. So we would cancel all of the

previous tasks that have not been completed and this is to prevent memory pressure from degraded networks. And last but not least, we also implemented stalness uh steness guards. So if we have load reports that are stale, we prefer to just go back to fail fail open. So go back to the previous uh routing no zone awareness um rather than pushing incorrect routing to our system. When we

started implementing the system, we thought popsup might be a good approach. Um, it would solve for the distributed state. However, turns out that popsup is also expensive. So, if you want if you're solving for a solution related to cost reduction, you probably don't want to introduce cost into that. So, we went back to GRPC to well, we didn't go back. We chose GRPC birectional streaming and a

singleton in this in the face of zoneless. Um we also decided to do zoneless outside of shameless and that is again to just keep the reliability and resiliency of shameless and operational isolation. The key decision that we made once we build zoness was that we're going to fail open and that has been our guide through through the whole architecture. We already spoiled that we cut 75% of

our crowone traffic but maybe we could look at the results from a different perspective. This is from the perspective of one of our high volume services. We managed to reduce 82% of their cross zone eress their cost. Um this enable services to focus on their delivery and don't need to worry about cross zone costs anymore. Um which is pretty powerful. Not maybe not everything went so well

though. So I'm going to pass it on to Yanik to tell you what we had to improve. >> Yeah, thank you. Um as you might know yourself uh production sometimes writes its own stories and not everything goes as smooth as the theory uh proposes. So let's talk about some interesting stories. So remember the assumptions that I talked about right the first one we remove. We don't need

to assume anything about the traffic distribution because we measure it. But the second one we still it still stands right. So we're still assuming the host distribution of the server is equal to the capacity distribution. Well, let's look at it in an incident that happened um yeah a few months after we wrote out zonoware routing in production and nothing happened. But a few months later an incident

happened and this one is interesting. So we have a service pretty high volume about 300,000 requests per second in a single region and it ran only a few instances. So it was a pretty like pretty good service in terms of throughput. Um and for some very unimportant reason uh this service was severely zonally imbalanced. So usually you have the service is balanced across all this one wasn't.

So what happened is the service decided to scale up or the humanity schedu the HPA decided to scale up the service and the scheduleuler placed the new pot on a node in zone C. Well, zonware routing, uh, the nice fancy algorithm that it is says, "Oh, there's a new pot in zone C. Uh, it's one out of 10 pots, so it should get 10% of the traffic,

right?" Well, if you look at the pot, it was currently called starting. Uh, it didn't had any JIT optimizations yet. So, it received about 30,000 requests per second instantly. Uh, and it actually had probably close to zero capacity. Uh so the pot was overloaded and due to the nature of how the service was built the pot also never recovered. So it was constantly getting this amount of

traffic and it was always it was failing a bunch of requests stuff was timing out clients were cancelling their RPCs. Uh yeah that continued for like quite some time until the right team us was paged in the middle of the night and we disabled zonware routing uh and everyone was uh kind of happy. Um well, why did this happen? Uh is of course the question. So um

the incident happened because this new pot was slow, right? But that's not unusual. You often have slow pots, code starting ones or you have a pot that has a noisy neighbor. So it's already obvious that not all pots are equal capacity. So the assumption already had some loopholes. Um but yeah in this case uh the problem definitely was that the pot was added to a small zone.

So the leaf load balancer being instructed to send oh send all this traffic somewhere only had one pot to choose. So it sent all the traffic there. Um if you add a slow pot to like larger zone the leave load balancer has alternatives and if you design a good one uh you can probably route around the slow instance but in this case we couldn't. Uh so yeah

the problem here of course is that the thing the component that has decided to move the traffic to that zone is zonware routing. So we also need to fix zoner routing if we want to get rid of this problem. Um so yeah let's discuss what we did. So we did developed a new model to measure capacity. We call it the dynamic capacity model. A very nice marketing

term. Thank you AI. Um so uh the dynamic capacity model the idea is that it's a signal that is supposed to measure the real capacity of the zone not based on what we think it does but really what it can serve and it consists of two components. one we call a Q adjusted host count. And the idea of the Q adjusted cohost count is that well you

still look at host counts, right? But you watch for signals where the host counts don't actually uh are as good as they are. So uh what you get from load rewards for example is something called inflight requests. And if the inflight request of a zone with many hosts grows compared to the other zones, you know this zone is kind of struggling right now. So in this case

you can basically calculate um you can see the formulas on the slide if you upload it they are not contained here but in this case you can basically calculate oh this zone has actually less capacity. So this is a reactive signal. If you see the gradation the signal can act and it also works on the load report. So we already had the data. The second component is

more like a proactive signal for something like the incident that we saw. And the idea here is you don't trust new hosts right? You never trust new host. they could be bad hosts. Uh so the idea is instead of saying oh this new host is adding like plus one to the capacity of the zone you say it's only 5% of a new host and then if it

actually proves that it can successfully handle requests again successfully handled requests contained in the load reports you're giving the the host more confidence and you're starting to trust it more and then that's where you over time increase the recapacity. So this model uh sounded good on paper and we ran some experiments first. Uh so simple setup we have a client and a server both distributed across three

zones clients producing constant amount of RPS and server handling a constant amount of RPS. Um so in this model zone aware routing like with the static capacity it would say all traffic should go same zone. So the first experiment uh we did is we degraded the zone right? So we heavily throtted the server and reduced it throughput. Um and basically everything that was sent to that server

it would time out right. Um so that's what we saw in the static model like the clients in the throttled zone they were failing with 100% error rate. But the dynamic capacity model it recognized that the zone was struggling after one load reporting cycle. Moved the traffic to the other zones and only kept a small amount of probing traffic on the zone to check if it ever

recovered. that's contained in the model because you never set something to zero. Uh so yeah, we cut errors by 91% in this case. Same if we have like a zone that actually recovers. Not super interesting experiment, but we saw that the ramp was basically only slowly uh increasing the amount of traffic to the zone. And finally the slow starting one, which is basically the incident that we

saw. So we had a a new pot. It was slow starting getting throtted and eventually recovered. The dynamic model didn't produce any errors because it didn't trust the new host only sent small amount of traffic to it and then found the perfect threshold at which it was operating and then eventually once the uh host was hot and could serve more traffic it would move more traffic to

the zone with the host. So uh the nice part about this is we're not only handling the correlations but actually the both signals that we build they only act in critical situations such as scaling up rolling deployments or when the zone is actually degraded. So under healthy circumstances we are as good as the previous model. So we're not producing significantly more crossone traffic by doing this. We're

just improving uh the parts where we are not so great yet. Uh so to summarize we went from envoys great horistic very good mathematical foundation to doing small improvements to reduce the assumptions that envoice horistic makes and therefore we have a an algorithm running in production that we are very confident and like we wrote out the dynamic capacity model also in production and some services that previously

had incidents they they've been running smoothly since. So this allowed us to roll this out widely at Spotify and incorporate a bunch of learnings that we had on the way. Um so yeah uh this was our presentation. I hope you found it interesting. Thank you for listening. Please leave feedback with this code.