Transcript
00:00:00How much could one byte really cost you?
00:00:02Well, a Cloudflare scale wasting a single byte per entry
00:00:04costs them more than 250 gigabytes of memory
00:00:06across their entire fleet,
00:00:08and recently they actually cut that per entry memory in half,
00:00:11freeing up 100 terabytes of memory.
00:00:13In this economy, that is a lot of money.
00:00:15They actually did this with five pretty simple changes
00:00:17to their caching system,
00:00:18and even made DNS faster at the same time,
00:00:21so let's dive in and see how they did this.
00:00:27Now, you may have heard of 1.1.1.1 before.
00:00:30It's Cloudflare's public DNS resolver,
00:00:32and it works by taking the domain that you want to go to,
00:00:34like betterstack.com,
00:00:35and finding out what the real IP for that domain actually is.
00:00:39Now, the thing actually doing this work,
00:00:40it's called Big Pineapple, and it's written in Rust,
00:00:42and as you can probably guess,
00:00:43it's an incredibly busy piece of software,
00:00:46storing over 250 billion DNS cache entries at any one time.
00:00:50This ensures that if someone wants to go to betterstack.com
00:00:52two seconds after someone else does,
00:00:53it doesn't have to walk the whole DNS hierarchy again,
00:00:56just keeps the answer in memory and serves it straight back.
00:00:59But as I mentioned in the intro,
00:01:01250 billion cache entries means that one wasted byte per entry
00:01:04costs some 250 gigabytes of RAM,
00:01:07and that's why these five changes had such a big impact.
00:01:10First up, we have the cost of capacity.
00:01:12Here's what a cache entry used to look like.
00:01:14Timestamp, time to live, hit counters,
00:01:16and then a bunch of vectors.
00:01:17A veck of answer of records,
00:01:18a veck of authority records,
00:01:20a veck of additional records,
00:01:21a veck of errors,
00:01:22and loads more.
00:01:23For those of you not familiar with Rust,
00:01:25a vector is just the go-to data type for a growable list,
00:01:27and it's also three things in memory.
00:01:29A pointer, a length, and a capacity.
00:01:31It's how much room is reserved for growth,
00:01:32so it doesn't have to reallocate every time you push to it.
00:01:35Which is very useful if the thing actually grows.
00:01:38But they looked at that real DNS cache entries,
00:01:40and they realized everything was just written to the cache,
00:01:42and never touched again.
00:01:44It was only being read,
00:01:45so these vectors never actually grew.
00:01:47That means there's over-allocated heap space,
00:01:49just sitting there wasted.
00:01:50There's a vector with capacity for eight items,
00:01:52but only five stored,
00:01:53leaves three slots unused,
00:01:55and the capacity field itself is a use size,
00:01:57which is eight bytes of memory,
00:01:58which for them is just not needed.
00:02:00Now the fix for this was incredibly simple.
00:02:02Just swap a vex for a box,
00:02:04as a box's size is fixed at the size it was created at,
00:02:07so it doesn't need a capacity field,
00:02:08and it also stores exactly what's there.
00:02:10It doesn't need to allocate spare future capacity.
00:02:13They also realized they could apply this exact same saving
00:02:15to the string fields as well,
00:02:16as they're essentially just a vector of U8s,
00:02:18so that text can grow or shrink,
00:02:20but if you don't need it to,
00:02:21you can just use a box string slice,
00:02:23aka this string is not going to change.
00:02:26In total then, on a cache entry,
00:02:27there were eight vex and string fields,
00:02:29so replacing them with a box saved eight bytes per field,
00:02:31and 64 bytes per entry,
00:02:33also eliminating the excess heap space
00:02:35that a vex reserves for future growth,
00:02:36meaning that the combined savings added up to over 15 terabytes
00:02:39when scaled to 250 billion cache entries.
00:02:42All of that from a simple data type change.
00:02:45For our next change though,
00:02:46they actually looked at some of those lists,
00:02:48and just asked, do we even need them?
00:02:50A DNS response contains three entries,
00:02:52answer, authority, and additional,
00:02:54and as we saw earlier,
00:02:55these were cached as they came,
00:02:57three separate lists,
00:02:58and even though we removed the capacity field in change one,
00:03:01each list is still a pointer and a length,
00:03:03so eight bytes plus eight bytes times three,
00:03:05which is 48 bytes in total,
00:03:07and three separate heap allocations.
00:03:09But when they looked at how these lists
00:03:10were actually being used,
00:03:12they realized that they were always read together,
00:03:13always written together,
00:03:14and they're always in the exact same order.
00:03:16So instead of three lists,
00:03:17they could treat it as one list with two dividers in it.
00:03:20So the three lists become one list of records,
00:03:22plus two small offsets that say answers end here,
00:03:25and authority ends here,
00:03:26and since the DNS response is never going to have four billion records,
00:03:29a 16-bit unsigned integer will suffice for the offsets,
00:03:33which is just two bytes each.
00:03:34This means that in total,
00:03:35they replaced two full 16-byte headers with two 2-byte numbers,
00:03:39so 28 bytes saved per entry,
00:03:41and this also lets Rust remove some extra spacing between fields,
00:03:44making the struct smaller than just the removed fields themselves.
00:03:47They even took this concept further,
00:03:49and merged several Boolean fields into a single bit flag.
00:03:52Moving on to change number three,
00:03:53what if we stop saying the same name twice?
00:03:55Every DNS record carries an owner,
00:03:57which is just the domain name that that record belongs to.
00:04:00So when you query betterstack.com and you get your records back,
00:04:03each one has betterstack.com written on it.
00:04:05But that information is kind of redundant.
00:04:08You're the one that asked the question,
00:04:09so it already knows the domain name.
00:04:11And Cloudflare was actually storing that query domain as the cache key already,
00:04:14so why do they need to store it again as the owner?
00:04:17Well, they don't.
00:04:17So Cloudflare simply changed this field to an optional box name,
00:04:20where if the owner matches the query,
00:04:22you store none,
00:04:23but if it is genuinely different,
00:04:24which it can be in a few cases like CNAMEChains,
00:04:27you store the owner like before.
00:04:29By doing this, for the normal cases where they match,
00:04:32they save a whole heap allocation per record,
00:04:34so this saving was simply a case of looking at what data they had in their cache
00:04:37and realizing there were duplicated values.
00:04:39For saving number four, we have the 144 by IP address.
00:04:43Their record data was a Rust enum of A records, 4A records, text,
00:04:47SVCB, and NAPTR, one type covering all of them.
00:04:51But here's the problem with enums.
00:04:52They're always as big as their largest variant.
00:04:54Every value of that type takes up the same amount of space,
00:04:57whether it needs it or not.
00:04:58In that case, NAPTR is the biggest value, taking up 136 bytes,
00:05:03and when you add the tag and the padding to the enum, it comes out 144 bytes.
00:05:07If you then compare that to what an A record needs, which is just a simple IPv4 address,
00:05:12that would only need four bytes.
00:05:13This means every A record in that cache was sitting in a 144 byte box,
00:05:17using just four of them,
00:05:19and A and 4A records are the bulk of the real traffic.
00:05:22In Cloudflare's own benchmark mix, it's 56% A records, 25% 4A, so the majority of the cache was just padding.
00:05:29The fix for this was our trusted box.
00:05:32They boxed the big variants and left A and 4A inline, because that's small and common,
00:05:36so now text, SVCB, and NAPTR are behind a pointer,
00:05:40so the enum only has to be as big as the biggest one left, which is that 16 byte IPv6 address.
00:05:45In total then, for an A or 4A record, that's 120 bytes saved each.
00:05:50But this change does actually have a trade-off.
00:05:52When you box a variant, its data goes from sitting inside a cache entry,
00:05:55to sitting in its own region of the heap somewhere else entirely,
00:05:58and that buys you two new costs.
00:06:00The first one is the allocator.
00:06:02Cloudflare uses Gemalock, and Gemalock doesn't hand you the exact number of bytes you ask for,
00:06:06it groups allocations into fixed-sized bins and rounds you up to the nearest one.
00:06:10So a text record that asks for 32 bytes lands in a 32-by bin and wastes nothing,
00:06:15but an MX record asks for 40, gets rounded up to 48 bytes, and quietly loses you 8 bytes.
00:06:21The second cost is locality.
00:06:22Before boxing, all of the record data for an entry sat in one contiguous block of memory,
00:06:27and after boxing, each one lives somewhere else, and reading it means following a pointer,
00:06:31and if that pointer lands far away from the rest of the entry,
00:06:34your CPU has to go and fetch an entirely new cache line just to read it.
00:06:37So while boxing did fix the padding problem, it created a problem of its own,
00:06:41and this is when Cloudflare thought, what if we don't store them as Rust types at all?
00:06:45Well, that's change number five.
00:06:46Cloudflare described this as a middle ground, keep the rest of the cache entry as normal structured
00:06:50fields, but take the record data itself and store it as raw bytes.
00:06:54So instead of an enum or a box per record, the whole entry gets one single box U8 array,
00:07:00with each record written as a 2-byte length prefix, followed by its data.
00:07:03This undoes both of the costs that we just talked about.
00:07:06All those separate boxed allocations collapse into one allocation for all the record data,
00:07:10so there's no per record rounding up to a Gemalock bin anymore,
00:07:13and it's all packed contiguously again, so you can get back that cache locality that boxing took away.
00:07:18And as an added bonus, it makes lookups faster as well.
00:07:21Previously, on every cache it, you had a parsed record sitting in memory,
00:07:25and you had to serialize it field-by-field back into DNS wire format before you could send it anywhere.
00:07:30Now though, it's already in DNS wire format, so most record types just get copied straight out of the buffer
00:07:35into the outgoing message.
00:07:37The only ones that still need parsing are the records that contain domain names,
00:07:40so CNAME, NS, MX, and SOA,
00:07:43and that's only because DNS name compression means you have to rewrite those names anyway.
00:07:47So this final change cuts the memory and deletes a load of work off the hot path.
00:07:51So there we go, that is 5 low-level changes to the cache,
00:07:54that when combined reduce the per-entry footprint from 953 bytes down to 420,
00:08:00so 56% smaller, and the memory actually allocated per-entry went from 1.1 kilobytes
00:08:05down to 461 bytes, so a 58% cut.
00:08:09On top of that, their insert throughput also went up by 43%,
00:08:12from 625,000 entries a second to 893,000,
00:08:17and lookups also got 19% faster, down from 828 nanoseconds to 670.
00:08:23They rolled these changes out across production this year,
00:08:25and their P99 resident memory went from 9.3 gigabytes down to 5.3,
00:08:29so a 43% cut on real traffic,
00:08:32which fleet-wide is roughly 100 terabytes of memory freed,
00:08:35or 130 of that Gen 13 server's worth of RAM.
00:08:38Now they plan to use that extra space to have a bigger cache,
00:08:41speeding things up even more.
00:08:43I really like this blog post because it highlights a decision that we will have to make.
00:08:46Should we have sat down before building any of this and worked out all of the optimization,
00:08:50or would that have been premature optimization?
00:08:52And I imagine back then in 2018 when this was built,
00:08:55the cost of RAM to Cloudflare was not as significant as it is today.
00:08:59The full post is a great write-up, so I'll leave it linked down below.
00:09:02Let me know what you think about this in the comments,
00:09:03while you're there subscribe,
00:09:04and as always, see you in the next one.
00:09:05See you in the next one.
Community Posts
No posts yet. Be the first to write about this video!
Write about this video