Keeping the Cloud Afloat with Deterministic Simulation Testing - Marcus Hodgson & Marek Siarkowicz

This talk discusses deterministic simulation testing and its application in the context of CD (Cluster Distributed) and Antithesis for testing Kubernetes scalability and API performance. The speaker outlines the historical challenges faced by the Kubernetes maintainers regarding correctness and reliability, particularly in an aging codebase. He introduces Antithesis, a powerful tool for testing, that enables efficient exploration of massive state spaces through deterministic environments. The session covers the integration between CD and Antithesis, including robustness testing and a case study of a complex correctness bug that was identified, debugged, and resolved. The approach not only improved the detection of bugs but also reinforced the foundation for future development on Kubernetes projects.

Yep. My name is Marcus. Uh, I work at Antithesis and we do software testing. >> And I'm Mark. I work at Google. I I'm a TL of SIG at CD and I work in Kubernetes scalability and API machinery performance. Cool. So today we're going to talk about deterministic simulation testing um, and how CD made use of antithesis to explore and test its massive state space. So what

are we going to cover? Um there going to be four main sections to this talk and we're going to go through them each one by one uh and try to get through them all in just 20 minutes. So for the first uh we're going to go over Etsy's history of correctness where Mark is going to talk about some of the uh challenges that he and the maintainers

had faced and what they had done to solve them. Uh then we're going to talk about antithesis. So what is it? How does it work? Uh why is testing with antithesis a super powerful way of testing? Uh third, we're going to go over the integration between the two. So how we put CD under test into antithesis. And lastly, we'll be going over a case study of a

really recent and tricky correctness bug. So we'll talk about how we found it, uh how we debugged it, and how we solved it. Yeah, a little bit context on the correctness. uh so HD is the source of truth for Kubernetes and any critical infrastructure information. So uh for us the reliability and correctness of it is the critical foundation of everything and that happens on this conference and

all the projects around it. So it's our number one priority but with 12 year old uh code base uh maintainer rotation and very hard to verify guarantees this became a real challenge to community to maintain um our guarantees uh for long period or over time. So uh during a 3.5 release around 3 four years ago we uh the maintainer rotation uh led to a lot of knowledge

un uh not being written led to it a lot of testing being missed which uh which allowed uh some bugs to slip in. So the the new maintainers that came in didn't have enough experience, couldn't validate and there was a lot of pressure to to to move on and um and develop uh the system forward. But unfortunately the reviewers were not experienced enough to catch each segment

and and all the bugs were very tricky. mean required multi-layered knowledge to from multiple parts of codebase to find um so to address that and take learnings the community built a robustness testing framework that was inspired by Jeepson and we used uh model based validation uh from mo like model testing uh to to validate the correctness. So we try to to define the properties of the system

and to use a simple map to represent HCD h and to validate uh how it behaves against a much simpler thing that we can understand and validate for correctness. So uh and this combined with watch guarantees allowed us to fully test the system. And thanks to that work, we managed to reproduce all of the 3.5 inconsistencies that were happening. And we even tracked some bugs to to

the 3.0 release, which was amazing discovery. But that unfortunately showed us that solving the problem is just the first step. You need to again maintain even more knowledge. Even more uh problems reappear. So uh first the verifying correctness is uh using model is an NP hard problem of tracing the history of all the events and this makes it really fragile and high maintenance. So we couldn't do

a lot of hard validation. We needed to like simplify a lot of things to to make it sustainable. uh sharing knowledge became also hard because still maintainers only maintainers could do a real debugging there. Even though we could find the bug to understand if it's a flake or not, you still uh it still required a lot of knowledge and uh the third thing was uh failure injection.

We had some tools to do it but adding anything new and understanding what kind of failure is a realistic failure in production systems was very hard like it was a reaching out to PhD students to get their projects to integrate I know disk failures. So um this was a d was a problem because we did community didn't have the knowledge to to evolve it further. So that's

why we reached out to the antasis. Cool. Uh so we learned that testing at CD is really hard. Uh it's distributed. Um there's a lack of expertise in debugging failures and its consistency model is a model based approach which is uh really costly and difficult to uh check for in the first place. So how does antithesis help with that? Um well it helps with debugging failures because

the antithesis environment is deterministic. So, we can always reproduce states that we've previously seen. Um, and we're able to really efficiently explore CD's massive state space. Um, okay. So, we've got two things here on the slide. Um, autonomous search. Some of you guys might be asking, well, what is that? Uh, it's just the term that we use to represent the way antithesis explores. So, it's going to

decide where to go, um, what scripts to run, what faults to run, and in what order, uh, what areas of code to focus more on. Uh and the second point, determinism. I mentioned this before, but the antithesis environment is a deterministic virtual machine. So, um it basically just if you do the same set of inputs, you'll always end up with the same state. And this is amazing

for debugging, but this is also really amazing for finding bugs in the first place. And I'll explain why in a in a bit. Okay, so I've always been a huge gamer. Um I absolutely love video games. Uh, when I was younger, my mom always used to tell me, "Marcus, you're playing way too many games." Um, I'm sorry, mom, but that's exactly why I joined Antithesis, because we

play a lot of video games. And so, here's an image of a section of level one of the NES game Mario. And if you were to play it yourself, your pathing might look something similar to this white line going across the screen. Um, so we taught antithesis to play Mario uh because just like complex distributed systems, Mario has a massive explorable state. So in this bottom image,

uh, we can see a lot of paths going across the level. Um, and this is all this is all antithesis running through the system all just overlaid on top of each other. So all we have to do is give antithesis a few hints. So what the inputs are. So up, down, left, right, ba, as well as uh Mario's XY coordinates and hit the level he's on, just

so we know he's making progress. Um, so this is a visual of the autonomous search that I mentioned in the previous slide. Um, antithesis is traversing this massive state space all on its own. And what we do for Mario, we do fortd. Uh, and if you're curious, yes, we do eventually beat Mario. And yes, we also have done a ton of other NES games. So we visualize

exploration with timelines. As time moves forward, the system state will progress. Uh here there are four timelines and they each start off by doing the same sequence of events. So maybe there's like the same clock event that happens and then there's the same power loss event that happens. So directly after where these green circles are, um the system states will be identical. And we'll just call this

system state A. And we can see that after they kind of go on and do their own things. This is inefficient because once we reach system state A in a single timeline, there's only one future. So if we wanted to know what other futures look like, we would have to refine system state A again in a new timeline. So this is a very similar image to the

previous slide, but this is what antithesis does instead. So we have these vertical lines connecting um the timelines together. So we can see like the timelines kind of split off from one another as we go from left to right or your left to right. Um and the most important thing I want you to take away from this slide is that we now have four futures of system

state A, not just one. And this is incredible because we don't have to start a new timeline from the beginning. Antis can just start from a place it's already been. So this is the power of determinism and since antithesis is deterministic it's able to reuse previous states as starting points and we absolutely take advantage of this while we are exploring and testing uh software because we target

the exploration energy around interesting states. So let's see if we scale this image up we get this uh this is the same stuff we had in the previous slide. So apply the same knowledge. We have those vertical lines that represent the the system moving through time and we have the uh or we have the horizont we have the the horizontal lines that represent the system moving through

time and the vertical lines connecting those timelines together. So this is a real 12-hour test of CD and there are hundreds of thousands of timelines all doing different stuff across each timeline. So, how does autonomous search uh decide when to do the uh like decide when to split these timelines into two? Well, we do this whenever we think a state is interesting. So, this can be something

like a new code edge we've never seen before or a new message that was outputed by the server that we've never seen. So, this feature is super important for finding really tricky bugs because when we get into a rare situation, we get to see many, many, many different futures of that rare situation. Okay, so we covered the two things. We learned that antithesis is this deterministic environment.

Um, it simulates what happens in the real world, but way worse and much more often. Uh, everything is reproducible, uh, even all the bugs we find. And this gets run in a staging environment before prod's history of correctness and a basics of how antithesis works. So what happens when you combine the two? Okay. Uh that's me. Uh so going forward. So yeah uh we HD community has

worked with anti antithesis over like started the integration for like a year ago. So we moved our uh robustness testing into the antithesis platform. Um we set up the free node clusters within a docker compose manifest. We did some special docker builds. uh um as instructed but most of the validation was just a lift and shift. We just took what was what we had and we just

run it in the new environment. Um the main difference is oncd side we have our own end to end framework that does the failure injection cluster setup and then collection. We just moved this we replaced this with docker compose um to to make the uh space exploration more guided. We have uh used our previous um the code markers for failure injection. We use them to guide expiration

by antithesis. Uh so we replaced something that before we just injected failure just before commit or flash to disk. We replaced with antithesis. Hey this is interesting. Uh for targeted uh faults we enabled many faults that were uh available in antsis. So we had networking partitions uh thread pauses process kills and CPU throttling which expanded what we had before which was manually written code that we did

on I know Linux process uh signals. Um so that allowed us to uh recently discover a old four-year-old bug incd that traced up to 3.5 release. So uh we call it a stale readback because it's uh happens in situation where one of the nodes uh should have observed a comet. There was a comet but it still reported an older version of the state. Um so incd as

a strongly consistent or strong uh system we guarantee by definition that every right you do you should be able to uh retrieve and all other other clients should do that. So we broke it here. Uh and this problem also traces back to 3.5 uh uh release that we had problems. It just stayed hidden for four years because it was so hacked hard to reproduce that we were

were not able to inject set of faults to do that and that was our like final boss on closing the chapter of CD correctness testing because we think now that we are able to find any bug that I mean we can generate or explore using antithesis and find find all the cases. Um yeah cool. Um so finding the bug in antithesis is when antithesis finds a new

set of inputs that lead to the bug happening. Um and initially this bug was extremely rare to come across. So we saw it once every 450 hours of real world time. Uh which is roughly once every 19 days. Uh I I did I did the math there. Um so once every 19 days we would uh see a new set of inputs that found the correctness bug. And

that's not a lot. So, it's also worth mentioning that this bug is probably much rarer in production um because antithesis is doing real world faults like partitioning the network between nodes um and killing containers at a much higher rate than you would see in production. So, the question now becomes how do we see it more often? Um how do we find the bug reliably in every test

rather than just finding it once every 19 days? Um, so we can do some really cool post test analysis. And this graph might be a little confusing, but I'm going to explain it in a second. So, um, on the x-axis we have time, and on the y-axis we have probability. We identified a single timeline that led to the correctness bug. So, we just chose that one timeline

that we knew would hit the correctness bug. and we forced antithesis to explore from from various points in that original timeline to the bug and we would just see how likely it was to rehit the bug again at those various points. So if we tried to explore from early on in the timeline, so on this left hand side of the graph, there was a nearly 0% chance

of us refining the bug. If we tried to explore from very late, so on the right side of this graph, there was nearly a 100% chance to find the bug. So the interesting states or events happen somewhere in the middle. and with all the information we just got from exploring at various points, we can correlate specific events to have a very um correlation to these spikes that

that make the probability jump really high. So we found that a container hang was very responsible for the first spike to 60%. And for that second spike that goes up to 100% we found that a network delay was really responsible for that. So we just tune antithesis to basically do these two faults at a much higher rate than we were originally doing. Um, so we just tuned

the setting there and just by doing that we found the bug roughly 20 times more often than we originally did. So now we can rei reliably find the bug um every day in the tests and how do we I guess debug and solve it from there. Yeah. So let's start the explanation by uh letting um or explaining you how uh read incd works. So HD uses raft

but also one of the um let's say flavors or modes of reads it uses so-called read index um option for for non-quarium reads. So we we avoid going through raft and like linearizing each read by having a special communication between members to to find out what is the latest read index. So an index of raft that we can use to to synchronize our um snapshot state. So

this starts when client send a request and the follower needs to make a decision. Hey is my state fresh enough? And doing just local check is not enough. We need to go to other members in the cluster including the leader to ask them what is the latest read index. that to to leader is still can can be faulty and can still make mistake. It doesn't mean that

it has the freshest state. Uh so leader to make sure that it is still a leader. It will doublech check other followers to with health checks to make sure that it still uh maintains the the quorum leadership and votes from all other members. So this is done by heartbeat. So a read index is passed from uh the request from follower to a heartbeat and then leader will

wait from confirmation with this exact same ID back. Based on that leader knows that when the read started it had a index 20 it was at the index 26. So and it was confirmed. So it will return the response to the follower which can wait until it catches up to the this index on its local storage and this then it can just read this what its local

state to the client. Uh this is further optimized by uh when there are multiple reads concurrent reads by not only tracing what is the um not only tracing what is like one read index how it's sent to by a heartbeat but making creating a queue of all uh read indexes that were observed by the leader and only sending a con heartbeat with a conf to confirm uh

with the newest read uh so that when it's confirmed it the whole queue is flashed so it will unlock all the readers um or or the read index requests uh by just taking like the confirming of the all the previous reads are confirmed based on the Q order. Uh so this this uh combination of those two behaviors uh had uh one limitation that it really didn't support

retries because um yeah the original didn't support retries. So we uh and that caused a read to be easily lost or time out if there was a leader change during a read. So 3.5 created a great feature called read index retries that allow a leader to to to uh on or a follower on a failed read from leader to repeat the request if there was a timeout

of half a second. So now we if the read failed because of network or the leader is no longer leader or it got passed or whatever happened to him the follower can retry the request and go through the normal path but this unfortunately causes a problem uh as we learned with the stale read. So the setup is the following. we have the same read index with um

um for read index one and and the heartbeat is sent to other members but in the meantime we we have both pause on the leader and if there is a network delay of the com communication of the heartbeat during this time there is a chance for a new read to happen and uh the read Q to be appended with the read uh second um read and this

becomes a problem because if the retry happens it will reorder the events on the leader. So instead of uh the previous state correct state was first was the first read then the second the retry of the read with the same index allowed us to wrap again the previous write under the um flashing of the heartbeat. So the first was first thing what was important was pausing to

cause the reorder on the leader and second uh the critical thing was uh if the second follower the network on the heartbeat if it's delayed it will allow the second the response from the first heartbeat to return much later after the reording happening happens on the litter. And this this allows us for a heartbeat on um on I index one to confirm a read uh with index

2 that never should have been Uh so to summarize um the trigger for the situation is both pausing of the thread of or the process and a network slowdown or delay. uh here an arbitrary delay and this can lead to reordering of the queue or within the queue of the leader so that the falsely um leading to false confirmation of uh of the read by a previous

heartbeat. As the result, the the note that's follower that sent the request will return the the data much earlier including the serve data because it will have a uh it will point to all the read index. Uh so the fix was very simple when we knew and understood and even triashed uh the the back and we have all the information it was as simple as prompting AI

to give us an answer. So we I mean we did that. Uh so the fix was just changing the retry to change ID to never duplicate. Um yeah and this leads us to the uh conclusion. So thanks to this work we are renewing the trust allows us to build more ambitious features like two node SD clusters allowed us uh the public reports that we have and are

available for you to read about how we tested and what are the results uh can allow us to grow the community. So anyone can join and read and help make ATCD the most stable system in fall CNCF. Um and the hope that uh I mean you can take from that the the antithesis is now uh free to use uh by any um any additional CNCF project. So

if you have your own project that you care about, please uh let let us know. We can help you get uh the same level of testing that we are doing. Cool. So, that's a thank you slide. Um, antithesis is at booth 888 and 889. So, if you have questions that we can't get to today, feel free to come there. Uh, there's a QR code to our website

and we also have a cool project demo tomorrow. Uh yes on the project pavilion there is a demo uh stage uh scheduled in the main yeah next to the all the booths uh there is a project pavilions where uh each CNCF project can make a demo showing their thing the thing that we will be showing is we didn't fit uh how we did the reproduction so if

you want to see the real details and how the debugging of uh this issue looked like please uh join us tomorrow on 12:30. Um thank you for listening and that's all from us. >> Any questions we can answer? >> Can you There is a mic on the on that side. >> Yep, there are mics on uh this side I guess. Yeah. >> Uh thank you for your

talk. Um how does it uh determine new inputs for the the system to find? Does it use like some fuzzing or some symbolic or conolic execution or >> Yeah. Yeah. So the question was how does antithesis determine or decide to do new inputs and explore the state space? Is that right? >> Cool. Um, so yes, we have a intelligent fuzzer. Uh, it's not just a regular fuzzer

because it's smart. And the reason it's smart is because it decides to explore more on those rare cases that I kind of went over. Um, so if we see a new message or a new code edge that we've hit, uh, or you signal to us via the SDK to focus on this area of code, um, whenever we get there, we will like do that splitting of the

timeline and just absolutely explore from that new like root state, I guess, is how I would explain it. >> Awesome. Thank you. >> Thanks. >> Hello. Uh, thanks for the presentation first. And how do you keep the problem state from basically exploding and how do you manage it? >> Uh the problem state as in >> like in terms of it it knows that it needs to explore

new space and basically extend the set of um possible >> movements. If I compare it to the Mario example, like how do you guide it to not basically move left, right, and just >> also apply to the CD example. >> Okay. So, so the question is like how do you um like in Mario for example, we had to tell antithesis that XY coordinates and level increasing was

a good thing so it could make progress. Are you asking like how we do that for a regular software system so that it knows to >> Exactly. >> Okay, great. Gotcha. Um, so we I I maybe Mark could speak on this more because he has uh these specific scripts that get run uh all the time in antithesis. So maybe we could talk about those which are the

um robustness tests and the Um let me think uh I mean we like on uh the robustness side we just like generate traffic to make sure that uh we explore the like we still like bound the space like if you're asking about like bound the space we try to not we don't try like arbitrary like history from production we try to focus or based on historic ical

cases of issues, we try to um prepare scenarios that abuse those and search those search spaces of I know this request has problematic, we need to add this like add more requests for this. So for example and this includes um we need to know what is not important. So like more keys like bigger database does is not like it's not important for correctness. So we just like

uh try to maintain the same number of keys but we still like if we had a case that we could would trigger like that would trigger we would just regressively add and expand the scenarios of like traffic generation. >> Yeah and maybe to add on to that in the current atc testing we basically have two scripts that we run that we run. one is the traffic script

that like has like how many operations we're going to do uh what keys to write to with what values uh what type of operation it is. So that gets that's going to get run and then the second part is the validation that will check through basically like a complete list of operations that was done from the first script and it'll run it through the modelbased validation for

uh correctness. So yeah, that that's we run those two and the the ordering of like the state space gets decided by like the I guess it would be like when requests are sent in the traffic script and what those requests are. >> Thanks. Of >> course.