All right. Hello, everyone. Thank you for coming. Hope you're ready for this adventure.
Let's get started. I'm Nelson Vides. I'm a senior engineer at the Ensemble, and I work
on the NS infrastructure. I have that's the room. I'm also a manair Langanel Xireba Angelista
have been doing this to for most of my career. I also did some CE and stuff. I mean,
if you're wondering why the funny outfit, this is the Ensemble's Christmas sweater, but
really, if you're wondering the funny outfit, I've three weeks ago, I just broke my
collar bones, no boarding, and for that, I recommend everyone really to have a split keyword.
It's very helpful if you want to continue working. Anyway, let's get started. So I'm going
to talk about an Ensemble built on the NS open source, of course. First of all, it's coming
from 2012, and it has been in production for about 11 years. We host the Alfredo Tith
in the name server. The Alfredo Tith records for a lot of cool guys, for example, the
Linux Foundation, happy of that one. Of course, stability is important. I'm going to talk
about the problem when we went from zero. Zero means downtime. To no matter what, we don't
have downtime. And just using classical algorithms. First, the NS basics, I'm sure 99% of
people in the world know here, what you see, you know, let's get the end record of
first them.org, so I can connect to the website. I ask to the name server, to the root server,
say, hey, you know, no, I don't know, but I know the server that has not come as key, okay.
So I ask the one that has not come. No, I don't know it, but I won't, the one that has
first them not not org. Sorry. So I ask the other server, and the other server finally gives
me the address. What do you see in this thing? A lot of network traffic. And distributed.
What is the problem space? DNS on the attack. It's a prime target. A quarter of the
catastrophic worldwide goes to the NS infrastructure. Another quarter goes to TCP-C inflow
attacks. That those two is path. Why so much goes to the NS? If you shut down the NS,
you actually shut down everyone else because you cannot find it. So it also has a terrible
amplification factor. The query for fastened or a record is around 40 bytes plus minus. And
the answer is already around 80. And that's only for one, a record. Like if you put the
NSs and you have like four IP addresses and then you ask for TXT records and the ACTPS records,
you get mega-lice of answers for just 40 bytes. So it sucks. Another problem is UDP, no connection
handshake, so it's very easy to spoof. This is preventable, but it's expensive on routers,
so middleware don't want to do it. Unfortunately, it's expensive for performance-wise. And
also critical if the NS goes down, everyone else is on reachable, so it's actually down.
Three core challenges, congestion, overload, and thundering hurt. Thundering hurt is
probably one you wouldn't expect. I discovered in a benchmark.
congestion, so kills are full, overload, there's just way too many for the available resources. Thundering
hurt, you try to take decisions that synchronize, and that's not good.
If you want to leave this talk with one takeaway, it is this one, do not ever expose and
unbounded resource to the outside world. Otherwise, you're going to get dedos, and it's incredibly
easy. There is no such thing as an unbounded resource, memory, you can have a lot, but it's finite,
network, you can have a lot, but it's also finite, everything is finite. A couple of
theoretical foundations, so that you understand what is it that we're going to optimize.
I started mathematics, by the way, not computer sciences, a lot of no less transfer, but I have some
hobbies. Little slow. We want to get an idea of how long are we going to wait in a queue. We
mean you go to a shop and you're going to buy some, how they say cheese. And you see 10 people in
the queue, and each one of them gets served every two minutes. You can guess that you're going
to get out after 10 people for two minutes or 20 minutes, you will get served. So arrival rate,
or serving rate, is static at deployment time. It's your implementation divided by your hardware.
The moment you deploy, this is decided. So if you want low latency, you need short queues.
If you let the queue row, so the W, and Blanda is static, L will just go wherever it wants to go.
Another formula, the complicated Cs with squares and so on. That is basically something that you
cannot control. This is a data and the variability of utilization, you don't know how your clients
are going to make requests. How is again your implementation divided by your hardware? This is
what you can do in a given amount of time. So what is row? That's the important one. It's utilization.
This basically means that the fuller areas the queue is not only it takes longer to serve the last
one. It takes longer exponentially, not linearly, polinometallysory, not exponentially.
This means that if utilization is around half, the weight in time equals service time. But if
utilization is 0.9, let's say CPU utilization. Weight in time is 9 times. And if utilization
goes to 95%, then weight in time is 19x. So you want to optimize for not for higher nominal CPU usage,
but for lower Q latency. In DNS, it has very tight timeout. If you don't give a request after so long,
then people will retry, to late. So you get the idea of the problem with a queue and latency.
So let's now solve these problems. Congestion. Typically, in case you have a queue package
arriving over the network and the queue has a size, you can configure in your kernel. The kernel
has the queue, your program has queue. Let's say that the size is 4, you so it fits on the slide,
because you know, and you want to arrive. There is a package that has been waiting for,
it has a delay. There is a package that has been waiting for 4 milliseconds, another one for 6,
for 8, and then a new package arrives. Where do you put it? It's full. You are going to drop it.
Why are you dropping the new one? That is absolutely fresh. And not the last one that has been
waiting for a while. Maybe it's just about the timeout. This is the classic that the universal default
tail drop, if it doesn't fit, you just throw it away, but then keep in mind you're throwing the
freshest. Or even more complicated. Or more annoying. Imagine that. I'm going to remove the mouse.
Imagine that you just finished resolving a package that got stuck for a bit. So now the whole queue
is delayed a little bit. And then some package arrives. There has one millisecond and a new one arrives.
Where do you put it? You're going to drop it, but you have a bunch of packets here. Maybe one of them
is a better candidate. So by the time we drop the fresh one, there is some other package. That
probably were better candidates. The problem is bus of load and this is not a new problem. They're
used to be entire working groups on the Linux kernel and on networking internet groups. Large
buffers means less packet loss until they get full. And then it means high latency.
Backing when the internet was not so fast, we used to think that the big buffers make the internet
faster, but in reality, it's a latency. And now that we have this 10g, 100g, this incredibly large
throughput, big buffers means minutes of latency. So that's not how we do things anymore.
One solution is code. It's fantastic default in the Linux kernel since quite a while.
Very good for most mixed traffic. There is some special algorithms. If you only have TCP,
but otherwise, if you have every possible thing, code is very nice. Why is code all doing?
This is an example. I'm doing that long, as I said, about should be so free level anyway.
Imagine a new packet arrives and I have the socket and the time of arrival and then the
being is the binary. This is the stuff that I need to decode and compute and so on. And before
I compute the naive algorithms that I'm guilty myself of doing, it works, but it's very inefficient.
Let's imagine that my time on this one second. If this has been in the queue, when I pick it up,
it has been for more than one second then drop it. But what if it has been for 999 milliseconds?
But I may finish computations for sure. It's already past the timeout.
So do I drop it at 80% of the time at 50% of the timeout? How do I calculate this?
So this is something that code does, getting the current time on the time of arrival.
It calculates a different and it self-heels. How?
Codell, you can see it as a state machine, gets packages and checks if the soil
time that is, the time it has been waiting is below a target. Target is usually between 5 to 10% of
your configure timeout. So if we say one second, target is going to be from 50 to 100 milliseconds,
configurable. In my case, I configure a hundred. So 10% Linux kernel by default configure 5,
a parameter. 5 is usually very fine until you have a specific benchmark that tells you otherwise.
Next packet arrives below Soljorn, whatever, next one, next one, next one, next one.
On the moment you have the first packet above Soljorn time, it's 10%. It's not expired. It's fine.
You don't drop it yet. But now you start tracking. You go to first above.
If the next one is also above Soljorn time, and the next one and the next one.
Until the entire interval, that is your configure timeout, then codell says, this queue got stuck.
This is not one quick spike that you just born very fast. The queue got stuck.
So now you need to drop one packet. Considering that you still probably have packages around 51
milliseconds. So potentially you're dropping very early, this one. But effectively, you have a
queue that got stuck. At the end of the queue, you're going to have very late packages.
You drop that one and when you drop the next one,
it's going to work on a controller. So don't drop on the first spike. Wait for the congestion.
And now, how do you decide when to drop the next? It's not every time you see the above Soljorn,
remember Soljorn is very short. If Soljorn continues being above target, not in the next interval,
because that is too slow. Not dividing by count because it's way too aggressive. It grows way too fast.
But a square root of the number of packages that you have drops so far. And this grows relatively
slow at the beginning, because maybe it's your suspect, but eventually it's going to get very aggressive.
And with that, you control the problem of our congested queue. Second problem, overload.
Too many requests, limited resources. So I say nothing is infinite.
As a solution, queue week. That's another default for TCP, since God knows how long,
I don't remember 15, 10 years. I have here. 2006, yes. The idea is that TCP congestion controls the congestion window.
So it keeps track of when the last packet withdraws and then it sells heal.
Calculating how much packets can it really send that the receiver is going to receive.
It controls acceptance rates. What we want to control is acceptance rate. How many requests are
we going to accept in DNS? But we can use the same math. Find the capacity that tells you when we hit
congestion or when we escape the window in TCP is the case when we hit too much utilization.
So then we know that the queue is going to get a lot of latency. Back off, you see in a cubic formula
and recover very fast because it's a cubic formula. It's not a square root. It's a cubic. It's a
aggressive at the beginning. So it comes back to the more many detected the last failure very fast.
And at that point where the last failure was, then it's very slow.
Why cubic fast? Recovery is stable plateau and then careful growing.
We are going to use cubic to tell us the rate and with the rate we are going to decide how long to
sleep, how long to wait until we take the next packet from the network. The meantime the CPU
is basically calculating the responses to all the ones that are very right. The state machine for
cubic is something like this. CPU has a lot of utilization. Then if it says no, it's just continue
growing, continue growing, let more packages arrive until basically delay zero. That means
use all your power to take everything from the network. Until you see that the CPU is to congestion,
then congestion and cubic says rate multiplied by zero. That is 20% slow down. The default
in the Linux kernel is 30% slow down in my benchmarks 20% was better. And then this is our new
current rate. And we are going to grow on that rate. We use some limitations. So this doesn't
escape. You can read the detail later. The moment we hit a congestion, we say that this point,
the middle of the graph, that is where we are going to place the congestion moment. And we automatically
drop 20% behind here. And we are going to very quickly grow until we hit the congestion moment.
Then the moment where it was congested last time. If nothing happened there, we are going to
continue growing very slowly. Nothing happened if we just have more capacity. Like queries are
simpler this time. They take less resources. Then we are going to start growing super fast.
Until we hit a new congestion point, move the graph, move around the ground again.
Why it works? It finds capacity automatically. It is responsive that the maximum rate. So it
doesn't grow indefinitely. Because at some point, infinite rate means 0 and 20% of infinite
also means 0. So it is never going to tell me to delay. I need to put a maximum on the rate.
The last challenge is thunder in here. Now, these two algorithms are happening on a bunch of
threads. It is a thread that takes packages from the queue passes to another one through sols.
Like that, there is many threads. I am doing an Erlang. So these are processes. And I can have millions
of them. They are literally 233 machine words. So I run one kilobite. Really, a million of them is
one giga of RAM. So I can have a lot. It allows me to architect this thing. I can just one
takes packages from the queue passes from the network passes to another to the resolution. And then
they synchronize if they, you know, bug pressure. The problem is when you run, when I was running
this load test in a multithreaded server, all threads congestion, CPU is a global variable. And
suddenly all threads say, oh congestion, slow down. And then everyone's slow down. At the same time.
And then everyone recover at the same time. Because, you know, everyone got the same amount of sleep.
And the problem was that I could see how we were trying to like dedos our servers to like calculate
capacity. And then I'm seeing metrics and to my shock. I see that suddenly CPU is 30%.
What? Why is it so wasted? And it's cyclic. It goes to 30% and immediately again to 100% for a while
before it says 30%. And immediately I'm like, I'm wasting capacity. I could be answering a lot more
queries in time. Basically, I'm just telling to a world school everyone. I'm not working today.
I could work for some of them. So this was something that I know in me a lot when I saw it in the
merge marks. I work on this so hard. I was so excited. I was like, yeah, let's do it. Let's like,
you're going to see. And then I was like, okay, hold on. Let me, let me improve this.
So two rules. Never delay after that delay. Cubic says, well, well, to be see slow down. And
then you delay. You come back a millisecond later. And don't ask again, I wish still to be
see should I delay? Just work. When you come back from a delay, do your work. When you finish a work
thing as for delay again, I was guilty of this. I was like, oh, still busy. Okay, continuously
this was eventually synchronizing everyone and taking my CPU way too low. And another rule,
put some geeter. It's a classic. It's easy. And it works amazingly well. I haven't marked
this. No synchronization anymore. In my benchmark, I can see the 7.5% randomization. So if Cubic
says sleep for 100 milliseconds, then one thread is going to sleep for 93, another one for 107. And randomly,
I have as I say millions of threads. So the distribution gets very good. And another thing
was a third rule is how am I calculating the utilization? This is important one. That was one
that I actually had in my studies and completely forgot. I was not good at statistics. Only when I
grew up, I realized how important it was in high school. If my thread calculates utilization
at the moment, when it needs to decide congested or not, it's not sampling. I may ask that question
at that precise nanosecond when CPU got you a little bit free. Or you're a little bit more busy.
And if all your programs are top or fair, and so on, all of them are doing sampling. They're
just like every nanosecond making a question. And then it's moving the graph. That's something
that I was not doing. I was just asking the question on the spot. What I should have been doing
is it's moving the graph. So I have a different thread that just another grand process. I have
so many. That is calculating the times. Like in on a timeout is calculating the utilization
and running an exponential moving average. That is, the latest value is 30 percent. Everyone else is
70 percent. So every time I calculate a new value, I remember what was the last one. And smooth
and in out, this 30 percent is another parameter. Some people use 25. Some people use 40.
My case, I run a lot of trials. 30 did the job very well. Just one line of code.
Important theorem because I like them very much. In the quiz Shannon says that you have to sample
twice as often as they think you're measuring. A funny thing, you remember when you watch a movie
and a wheel is moving. And there is a moment when you have the impression that the wheel is moving
when the wheel moves very fast. That is because the wheel is moving faster than the frame rate
of the camera. Ideally, if the camera wants to capture sampling, it needs to move twice as fast as
the wheel. That's why that effect happens. So at the end, to recap, it works more or less like this.
Schedule authorization gets smoothened. It's feedback for both code and cubic, which create feedback
that I put back in the scheduler utilization. Results, they note, never dies. Most important thing.
Under any load, under any attack, we actually got the dose attack last Thursday. I was so excited about it.
Thank you. I was a finishing work. We're preparing something and suddenly I'm like,
wait, million notification. What's going on? And everybody was at the dose attack and it's like,
yes, just before fostering them. Awesome. So, not very open, be in die. Well, happens like before
I did all this work on my hardware. This was the queries per second that I could return and then
some improvement under normal load. But once you pass over load massively, it used to die.
This means downtime. This means somebody waking up in the middle of the night. That's not me anymore.
This means like customer trust, like queries are not resolving. This is like the worst case scenario.
This is nasty. It's also downtime means five minutes, ten minutes, an hour. This means,
like the gradient service. But some people still get requests. And nobody needs to run from the toilet
because oh my god, I have a request. I need to fix this. Fine. You can just, can go in three minutes is fine.
This also means it's self healing. Probably by the time you arrive to the computer from the alarm,
everything, which is what happened on Thursday. I arrived to the computer. Everybody's like,
what's happening? It's like nothing anymore. Cool. To recap, cubic for red limiting code for the
humanagement. To be honest, code was my favorite discovery, my unemployment in this was a lot of fun.
Signal is moving with exponential moving average and remember to sample frequent enough.
And it's so simple. We'll know this. Try it yourself. It's open source. This has the two
pull requests that implemented most of these important changes. Read the code, let or something from
it. People say that that langs syntax is ugly. I don't mind, but it's self readable and it's functional.
And that's it for me. Thank you very much.
Thank you, Nelson. We have a couple of minutes. Any questions?
Very, very good question. Thank you. Yes, of course. The question is if I account for TCPO only for
UDP, 99% of this work is in UDP because it's the workload we get, 99% of the traffic is on UDP.
In TCP, yes, also, but it's not that smart. It's for the future because, you know,
UDP was urgent. It's my backlog. It's probably on Monday. I'm going to start doing similar things
for TCP. We actually solved the loss of tax and the alert was for TCPO. It's also a question
on the server, because you can do the load loss. You got four, but yeah. I'm sure that evil
actor is going to watch this video and say, oh, that's how I'm going to attack Nelson now.
Yeah, on Monday, I will fix it.
Another question, maybe?
Yes, sure. Do you think that you are willing to know that stuff could be implemented for
as a type of like the routing of market security? Yes. Absolutely. So, question is if this kind of
QM mechanisms can be implemented for other kinds of services like routing, yes, totally. Actually,
they already are. The Linux kernel uses on the TCP stack in Codel, the same way is the default.
And there is, as I said, at the beginning, there is an alternative for TCPO only
traffic, then there is a slightly better flag that you can use inable on your production server,
but the default is Codel already. It's actually a fair QCodel, which is why I already do in
that land because I have millions of processes, but in Linux, it just opens a bunch of Qs and
like puts the traffic fairly between the Qs and each Q is running its own copy of Codel.
Just the same thing I'm doing with millions of threats. And with Linux, most routers should be doing the same.
OpenVRT does it, it's also a default. There was a big movement in the internet working group
something like 6 or 7 years ago to push all router manufacturers to make this a default,
because the default used to be big buffers, they'll drop. I explained at the beginning is, but
especially for really big capacity. So yes, it should even feed your
HTTP work server. Many of these lessons are not the end-specific. If you are serving requests
over HTTP, they are also like you also don't have infinite resources. And maybe the time out is
not a few milliseconds, maybe there are requests that are fine to be served ten minutes later,
but you still don't want to queue all of them because you're going to get deals. So you need to manage
the Q. Do we still have time for one more question? All right. Perfect. Thank you very much.