Saving 100 terabytes of memory by optimizing 1.1.1.1's DNS cache

Were there no design discussions/reviews when the system was setup to catch trivial things like this?

Another interesting thing that happens is you don't necessarily know what form your actual optimizations will need to take. Later when your systems grow you discover the suboptimal parts you hadn't optimized for.

Very early on at Cloudflare I worked on part of the DNS infrastructure that took DNS records from the UI and got them in a state for actual authoritative serving. The system had been constructed anticipating Cloudflare having millions of customers with unique domains, but it had not been constructed for a single customer with a single domain with millions of records. This caused a periodic slow down in DNS record updating while the system churned on that one customer.

In a different job I worked on a piece of optimization software that needed to keep track of "node" A is reachable from node "B". This had been implemented as a matrix (literally a malloced NxN matrix of ints storing 0 or 1) which worked really well for small systems. But you'd be out of memory really fast on a large project. I replaced the matrix with a hash table and all was good because the matrix was actually really sparse.

With a rather short prompt, claude/codex will take your code, write a harness, profile it, build experiments, profile those, and give some pretty solid advice which one to pick. Then integrate the changes. It's the kind of goal-directed, bite-sized job that LLMs excel at. Extremely low-commitment.

Except for the whole "making changes in production at scale" problem, of course.

Because anyone willing to come in just to design your cache format is going to expect payment that is many multiples more than the engineers you already cannot afford? Long-term employees cost less, which brings them closer to being affordable, but you have to be able to keep them busy for long periods of time to realize that reduction in cost. A engineer who doesn't understand your codebase isn't going to be useful for very long.

The “evil” of premature optimization is that it’s a misapplication of priority. If I have an acute medical problem that needs attention, it’s not the right time to talk about chloresterol and statins, get my broken leg set.

There’s always a tension between engineering management who needs to deliver a solution to the business and engineers who want to deliver a beautiful object.

At the point someone queries the 100TB of RAM, then maybe it is worth revisiting but even that has risks. You have to design the migration path, have fallback mechanisms etc.

So how would you decide which path to take in situations like this?

if you spend cycles on nitty gritty opinions like this time to market goes out further and further out. some napkin math, 130 gen13 servers cost "only" ~$2.6M. relative to the importance of the 1.1.1.1 and the market at the time. that is nothing to cloudflare.

this is not to say good system design does not matter. it very much does, but making that call at that time would've butchered the prodcut very much similar to google+, youtube etc.

It's also not nothing, otherwise it would never be optimized away now, but left as is. After all, wasting time on optimization delays "time to market" for other useful features.

I also don't get the reference to YouTube, it's a very successful product, how was it butchered by good system design???

You're tasked with making a DNS caching recursive resolver that can operate at a large scale and will be run on thousands of servers each of which has a lot of GBs of ram.

You are given some period of time to build this and make it production ready. How do you spend your time:

* Focusing on making sure that the resolver works correctly?

* Focusing on make sure that it actually provides improved DNS performance for internet users?

* Handles an very large number of record requests/s?

* Saves a few GB of ram per server?

There are tradeoffs to consider. RAM is cheap, even at today's prices RAM is not the most expensive thing that can go wrong in such a scenario. Having the responses be slow or incorrect is a far more expensive problem. A good engineer would pick a simple data structure that has the right shape but might not be optimal in footprint to focus on correctness and response time. The few extra GBs of RAM per server can be dealt with later.

When building things at scale you want to make sure it works correctly, fails correctly, and does the thing quickly before worrying about reducing resource consumption. I've never seen a project fail on Vec<T> vs Box<[T]> memory differeneces, or even on a few GBs of RAM usage per instance. I have seen them fail on "one wierd corner case of correctness" though, and on poorly thought through failure modes.

Doesn't this also inform you that your cache will be very large, so you shouldn't use growable structures with slack space when cache entries won't grow; slop space reduces the size of your cache. And also that the query volume will be high so the cached data should require as little work as possible before returning data; spending time marshalling response data on every cache hit increases response time and decreases capacity.

* unbounded growth of the cache and properly invalidating after TTL expires (a few GBs of slop is nothing on a server with 64 or more GBs of ram, unbounded growth is a problem).

* making sure the DNS implementation works correctly on both the serving side and recursive resolution side.

* What strategy is best for deduping recursive requests across machines (if something a few miliseconds away has a live result, why do a full lookup taking hundreds or thousands of milliseconds?). This potentially improves RAM usage across the datacenter too from not having a given record on dozens (or more) machines' local cache. I don't know exactly how they do it, but naively I'd look at some sort of DHT shaped solution to look for records in peers within the datacenter. Or maybe some sort of tiered caching with the upper tier being sharded on domain name or the like.

* The biggest performance gains cloudflare can provide in Web and DNS cache come from a cache hit. This is on the order of 10s or 100s of ms due to having a big cache and short distance to the requesting machine. A suboptimal lookup algorithm that is a few microseconds slower in local compute and ram access is just not as important as the other concerns for dedup and cache sharing. That's not to say it's unimportant, just that it's not the top priority when you're trying to deliver this much larger performance gains from other aspects of the system. Thats why they are getting to it several years after release.

Cloudflare writes a lot about distributed systems solutions to various problems. They likely don't think as hard about single machine performance as much as whole datacenter performance when approaching problems.

Keep in mind that the per-server cost of the whole program pre-optimization seems to be about 10GB (from the graph in the post). IME that's not bad for a big busy caching service.

Using twice as much ram per cache entry makes the cache half as large, assuming your cache is bounded by ram, unless the queried, unexpired result set is less than the ram budget (which I would tend to doubt... lots of randomized queries out there; maybe I'm wrong if the cache size dropped).

When you're storing billions of records, it makes sense to spend a few minutes to consider how they're used and make a good choice about how to store them.

When you're getting a cache hit tons of times per second, it makes sense to consider every step and which ones don't need to happen every time. You have to consider every step while you're pursing correctness anyway, so might as well have the performance lens active too.

I'm not asking for heroic optimization: I didn't ask for vectorized stuff or kernel/nic offloading or kernel bypass networking... Just you have to use some data structures, you might as well not use ones that are expensive for features you don't need; and you have to store something in your cache, you may as well store something that requires less munging on the way out.

If this were a small local cache, that didn't want to use something already existing like unbound for some reason then yeah, data structures don't make a huge difference, extra marshalling doesn't make a huge difference, just don't reimplement all the CVEs that BIND had in the 90s. But if you're going to allocate 100 TB of ram, make it count. Even if you do use twice the ram but you get value from it, maybe that's fine... I've run wacky systems with bloated storage when there was a benefit. Vec doesn't give any value over a Box<[]> in this case; convenience or lazyness would be fine except that the sheer number of objects makes it worth the few minutes it takes to do something better.

This is true. I'm arguing that its unlikely this was ever bound by available RAM. Cloudflare is a DDoS protection company that absorbs attacks. They have a lot of available capacity at any moment. When you're building a service in a sitaution where you have more capacity than you'll likely need.

The savings were 100 TB across >300 data centers. The savings were on the order of 50%. So prior to this reduction the service was using something less than 2/3 of TB per datacenter. The service ram usage was about 10GB per instance according to the graph in post. IDK how cloudflare divides thier stuff between machines, but assuming they don't run less than 64 GB per server that's less than 12 servers per datacenter of ram for a flagship product, and they likely run it spread across 65 of the machines in the datacenter that are also doing other stuff. The per-instance RAM likely isn't the the concerning limit.

Overall RAM usage is proabably a bigger concern. Thats why I would think about dedup between instances and distributed caching strategy first. I could focus on redudcing the ram needed per service instance and get a 50% reduction per machine. Or I could focus on deduping 1/n (where n > 2) reduction in total memory usage across all instances. Personally if I was worried about reducing RAM I'd put more energy into growing N.

However all this is a red herring. The assumption people are making is that the cache was always read-only, and it's obvious that Box<[T]> was the best decision because in a RO cache smaller entries hold more things.

The 1.1.1.1 service advertises improved DNS performace. That's its value add. The biggest performance gain you can have from a cache is not having a cache miss, and in DNS a cache miss means a very expensive recursive lookup. So there's concerns about how to minimize those lookups. If one instance has does a lookup, it makes sense to share that result to the other instances that may need to do a lookup [1]. I don't know off the top of my head if it makes sense to get those updates and modify the existing record or just replace it in the local cache. That comes down to locking strategies and reading patterns in the specific code and service traffic patterns. Until i have hard evidence one way or another I'd like my cache to be able to do both and keep the data structs modifiable until that's nailed down. If per-isntance ram ever becomes the issue, there's easy wins there to buy me time to find better large scale solutions to the problem.

No one is disagreeing that the larger datastructures are larger. No one is disagreeing that they take more RAM, and or even if RAM was the the problem reducing it would be good.

The thing people are pointing out is that this isn't a homework problem about an optimal cache structure in a vacuum. We're pointing our that engineering real large scale solutions has a lot more to consider than a homework problem, and that the thing you're harping about likely didn't have any real budgetary or noticable performance impact on bulding that system. The reduction in ram is just a smallish improvement in operating costs after all the more expensive stuff was figured out.

Put another way 100TB of RAM is ~$350K. Thats one engineer year for a mid-level engineer.[2] Would you rather spend that money to save an equivalent amount of money somewhere, or... would you spend that money putting the engineer on something that saved $700K elsewhere (alternately that generated $700K)?

[1] I talked a lot about dedup and the simple gotcha is "hahah then its not deduped so you need smaller objects". But on a service that is running on a few dozen instances having a few redundant copies to deal with loss of a machine and/or load can still result in 1/(n>2) savings in total ram.

[2] I'm not saying someone worked on this for a year btw, a couple people likely spent a couple months on the code, validation and testing of it. A manager spent time overseeing it. Operations people spent time understaning any effects it had on running systems. Costs add up and it wouldn't suprise me if this didn't end up being roughly break-even for the year.

Rule 1. You can't tell where a program is going to spend its time. Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you've proven that's where the bottleneck is.

Rule 2. Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.

Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)

Rule 4. Fancy algorithms are buggier than simple ones, and they're much harder to implement. Use simple algorithms as well as simple data structures.

Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

https://web.archive.org/web/20260314210910/https://users.ece...

So you agree that they should've designed the system to use the appropriate data structure from the beginning?

Genuine question, is software performance really linear like that, that one can and should only fight the tightest bottleneck, one workload at a time? Never really sounded right.

It also sounds like the typical sleight of hand where the difficult bit is simply laundered a layer up, in this case the choice of what workload one investigates.

Sometimes it's a lot of small things everywhere and you can pick up significant performance after a lot of small value fixes. In this case, caching wire data instead of structured data is almost one of these, because the contribution to response time for serving a cache hit is small... otoh it happens so often than a small improvement matters; but this is a pretty focused use case, you usually hit the many smalln improvement issue in a less focused application where there are many code paths.

Sometimes the whole code structure / data structures are so wrong, but it works and perf is bad and profiling will never tell you. This article is not that case; these data structures only needed refinement.

Looks like they're missing the obvious optimisation of putting the record data right after the CacheEntry members instead of allocating memory separately though. But that might just be me as a C-programmer talking and not be all that easy in Rust.

[1] https://doc.rust-lang.org/reference/dynamically-sized-types....

[2] https://doc.rust-lang.org/nomicon/exotic-sizes.html

Cloudflare started to pick Zig recently, for projects, that have memory constraints.

You definitely can and this is done a lot. What you might mean is that you can't use standard library's collections with them (this is getting stabilized soon!) and have to use third-party, but that is a different thing than "can't use arenas".

> Rust is not a good choice for this kind of tricks.

Rust can do those tricks, but it's true that it is hard than in C or Zig. That said there are often crates to help.

I assumed they couldn't do that because they're using it with some kind of generic HashMap<K, V>. In that situation, can "V" be dynamically sized?

A dynamically sized "V" would mean you can't have an array of them, which might preclude some hash map implementations.

, which HashMap does not do, i.e. the keys and values have to have a statically known size.

The CloudFlare manually implemented a clumsy version of this.

Wouldn’t it be nice for the compiler to manage this for you in the same way that your database engine does when it saves a “row”?

Are you able to explain this? Do you mean an N sized array where each entry is either a value or a pointer to a value where the 'pointed-to' values are after the end of the array?

I'm trying to underatnd how you'd do this without having to parse M-1 elements to get the Mth entry if you did a [{size0, value0}, ....., {sizeN, valueN}] arrangement

In a row oriented database, you get a contiguous spot for the whole row even when there are multiple variable width fields.

So logically you'd have the equivalent of:

    struct FooRecord {
        int fixed_sized_field;
        char some_other_field;
        string first;
        string last;
        string title;
    }

    struct FooRecord {
        long __length__;
        int fixed_sized_field;
        char some_other_field;
        char* first;
        char* last;
        char* title;
    }

There are variants of the above, of course. Instead of pointers the compiler could use lengths, offsets, or a pointer to the end of the variable length field -- this works because the beginning of the first field is at a fixed offset, and then pairs of pointers delimit the rest.

You can rely on the heap allocator to track the "__length__" instead, or you can encode it into the record explicitly to make "dynamic sized copies" simple.

Windows APIs generally work this way! You create a buffer, put a length in the first field, and then the API call writes a fixed-sized prefix followed by the dynamic-sized fields into the buffer. The 'length' is replaced too, so you know how many bytes to copy out without having to understand the structure.

Database engines go one step further and pack multiple "records" into a single "row". They typically store the fields "packed" at the start of the row with 16-bit length or offset markers at the end for the various dynamic sizes.

Something like:

    fixed_sized_field // Row #0
    some_other_field
    first
    last
    title
    fixed_sized_field // Row #1
    some_other_field
    first
    last
    title
    ... empty space ...
    next_offset      // always populated
    row#1_title_offset
    row#1_last_offset
    row#1_first_offset
    row#1_offset
    row#0_title_offset
    row#0_last_offset
    row#0_first_offset
    row#0_offset  // typically the constant zero

When I was using one malloc() per entry, a large blacklist took up 237 megabytes of memory. The same blacklist, once optimized to be loaded with a single malloc() call, only took up 9.5 megabytes of memory.

https://samboy.github.io/blog/entries/MaraDNS.html#BlogEntry...

Interestingly this is exactly how netlink works-ish: https://manpages.ubuntu.com/manpages/focal/man3/netlink.3.ht...

You start, get the type & length, and then that is how many bytes you read.

Some issues with that when you deserialize, from a raw stream in to `[u8; 4096]` buffer, the alignment is only guaranteed to be on 1 byte, not 4 bytes.

In practice it is 4 bytes, but if you run those tests with Miri, you'll get yelled at. So the fix there is to declare the buffer with a type that mandates the alignment of the largest type that you're going to be deserializing.

So then you start your buffer as follows: `[u32; 1024]`, and with `slice::from_raw_parts` you get to turn that into `[u8; 4096]` with the expected alignment.

As an exercise I wrote a streaming parser for netlink, the current existing package serializes everything, all at once.

Hey dang can I get my rate limit turned off pretty please?

[0] https://en.wikipedia.org/wiki/Type–length–value

What's the speed of service/response time relative to the data source?

At that point it might be enough to replace your multiple caches with fewer in-RAM databases?

It's an interesting problem.

Not really, TTLs are often short, but IPs might not change for years.

You can probably generate your own TTL, at scale, and avoid many DNS requests.

https://www.rfc-editor.org/info/rfc8767/

As a corollary, there is obviously no floor on refetching unexpired RRs, of course, except for efficiency concerns.

At least in my country (UK) I know of no law relating to DNS caching.

Why throwaway perfectly good data every few minutes that is only modified every couple of years, just so someone can move their domain quickly when they eventually wish to? It is my contention that a [caching] DNS service can do far better. Trusting user (domain owner) input blindly is not for me.

I should be a bit clearer here; the TTL is an upper bound on how long it can be cached. Caches are free to consult more frequently but not less frequently. That said, out of respect for upstream cache operators and authoritative servers, most DNS caches honor TTLs as best they can.

Advocating to do things against agreed-upon standards without a compelling reason and without giving due consideration to the adverse consequences is one of the hallmarks of a bad engineer. Even Microsoft played nice with Internet standards for the most part (although with some notable exceptions at the application layer that got them well-deserved criticism).

Or alternatively, if you don't tamper why would I want to use a service that serves stale data?