A good day to trie-hard: saving compute 1% at a time
blog.cloudflare.com
blog.cloudflare.com
- An entire separate dictionary or other data structure.
- One single header containing all internal metadata.
- All headers have a prefix, and the internal ones start with I and the external ones start with E.
- All internal headers start with “CFInt”.
I would not have come up with a scheme in which headers in a particular list are internal. (What if someone else uses this name? What if something forgets to sanitize? What if different simultaneously running programs disagree in the list? What if the Connection header names a Cloudflare-internal header? What if the set-difference algorithm is annoyingly slow?)
The web is already full of obnoxiously ambiguous in-band signaling and header naming, and I find it bizarre that a company with Cloudflare’s scale uses such a tedious and error-prone mechanism internally.
I recall returning to a bank and discovering that router and load balancer admin passwords hadn't changed in seven years..
Is this the same phenomenon that resulted in Cloudflare Tunnels apparently being domain names? Or why domains that are proxied by Cloudflare show up as “CNAME” in the DNS panel? (The latter one seems extra strange — wasn’t the reverse proxy service the very first service that Cloudflare offered? There must be some history here.)
Often it’s better to clean as you go. If you have the time and the inclination, shore up one of the least good enough things.
It’s not unheard of to open up new feature sets via refactoring. Something that previously would have taken an “impossible” amount of time now becomes profitable, not just possible.
But if you limit yourself to one part of the interaction, they don’t get as mad. A dozen changes in the signup system piss them off less than five changes across the app.
Including using proxies at the edge to strip out internal headers bidirectionally- yes, inbound too.
You’re on enclaves all the time. This is just a different one. Separate networks per class of traffic used to be de rigeur before Cloud. Now it’s all munged together.
It isn't about being in the enclave, it is having to keep track of what headers you set vs external. It is fragile and error prone and it will absolutely break someone else when there is a name collision.
All security exploits are a subset of bugs.
There’s probably a dozen things you can terminate at a boundary that would cost so much to run through the entire system that it would bankrupt a company.
And then there’s tracing, which also uses headers.
The whole point is that a genuine user header should never conflict with a Cloudflare internal header, and a browser should never see an internal header.
If all internal headers were prefixed with X-CF-, you could strip them all via SIMD that had no knowledge of any specific header. Hell, you could probably do it on the NIC.
(Also sibling is right, I spaced on X-CF- being a header sent to CF customers’ servers. I don’t used cloudflare but cloudfront does the exact same thing)
But even for workstations wired to a trusted LAN it still makes sense because you never know which of the various tunnels might assign and expose some IPv6 address to the internet.
For servers you might be able to make an exception if you have a vigilant IT and the people with admin access aren't actively trying to circumvent security, but even then that better not be your only layer of security.
I used to joke that F5 owed me and my coworker 3 months of salary for all the free QA we did for them.
I was a little bummed it was “just” a Linux box but that’s pretty common today. I hadn’t discovered dd-wrt yet and wouldn’t for a few years.
I have a slightly different example of this, where a rpc framework used in my company disallows the service owner from modifying certain headers (say request identifier), and will instead create a duplicate header with a suffix. In that scenario at least, I can see this as a fairly reasonable tradeoff, as the goal is to control certain headers from being modified, not because they are platform internal but because there are certain assumptions associated with those headers that are followed company-wide.
I'll go check what mechanism is used for this matching.
The HTTP Connection header works like this, and one should generally assume that almost nothing implements it correctly.
Or the same but with a list of headers which AREN'T internal.
You'll probably have a custom header-adding function that people should always use instead of the regular one. And this way, if someone forgets to use it, their header will get stripped.
You can think of a header escaping the internal network as something that needs to be authorized. This is a deny by default approach.
- Ensure all headers added internally that are not for export at the front of the header list
- Preseed the hashtable of all requests with internal headers you plan to remove.
While Python provides data structures like this out of the box, designing a big system to require a special, nonstandard data structure to identify private metadata seems like a mistake to me.
Is this somewhat special? I mean, sure. But it wasn't long ago that a hash table was already in the special territory of data structures.
Edit: I should add that I'm not certain this idea would be better. Just more ideas on what you could do.
The creation-order-preserving hash map is basically two data structures in one, it’s more complex and slower than a normal hash map, and IMO it’s rather bizarre and I have never really understood why anyone wants one.
My last job did rely on ordered-ness of `QMap`, because the elements are listed in a Qt GUI and it could confuse users if those widgets randomly rearranged themselves. That's the only use-case I've personally encountered for an ordered hash map.
My main "idea" here is to stop from having to check all of the headers on a "per header" basis. Yes, you can make each check faster, as the TRIE does. You can also remove the entire reason to check individual headers by starting a traversal after where the internal headers are.
You could also go with something like making sure the first header is "InternalHeaderCount: N" where you then keep the internal headers segregated form the others by a simple count. (This assumes you have solid control over what is adding the headers internally, of course.)
(I also forgot to give kudos on the blog title. Any Die Hard reference is a good reference. :D )
Couldn't you bypass this by pre-fixing the ones that aren't yours? Or prefixing your internal ones with something unique enough?
The list approach has some downsides, but it also has a bunch of upsides. I feel like when people like to point out potential flaws of these approaches, they're ignoring the history and difficulties that comes with Cloudflare's scope. An enumerated list is the simplest and most flexible of the approaches, and it also doesn't require any a priori agreement on the structure of a header key - this is probably important when you think about the sheer number of teams at Cloudflare, potential technology acquisitions, etc.
"Hey any teams out there, before you can add internal headers, you need to register them with some service." Then the list is loaded from static storage at startup time and/or refreshed on some periodic basis.
That’s more of an indictment of how little effort is spent aligning things. It’s not that hard to tell every team that any headers have to start with ‘CFint’ and then enforce that.
How many years do you have to spend in software before you stop uttering those four cursed words?
* Headers that are intended to be public, but then are changed to private
* Headers that were created in the very early days of the company, which are so deeply integrated into everything that renaming them is basically impossible (or at least very hard and risky)
* Headers that are set by some appliance/third party solution not controlled by CF, but which are technically internal and must be stripped.
* Newly acquired company has its own set of internal headers. Management is not amused when a huge, disrupting refactor is suggested by engineers.
And this is just a tip of the iceberg of possible problems when your scale is big enough.
Maintaining the header to strip list is just another piece of technical debt to keep paying down.
Having a policy to strip everything under a prefix seems much less error prone.
To be a little bit blunt, this just means you have never built software in a very large company that may have a lot of existing/completely independent software, or have made technology acquisitions after the fact. That is, if you are starting from "time 0" of course it's very easy to say "internal headers need to start with CFInt", but that's rarely the case.
If they do, it suddenly becomes very easy to get everything aligned, because there is likely a vast collection of bodies just collecting a paycheck that can be more productively assigned to manually renaming everything.
One thing the author leaves out is this technique is technically a Bloom Filter. I find these kinds of things fascinating since they came about in an era where computing was far more resource bound than today (1970 in this case). But here we are, still finding real-world corners to use the same old optimizations.
Rather, this is a refinement/variation on Liang's algorithm, used in TeX for storing a hyphenation dictionary. The thesis mentions Bloom's algorithm, which it calls "superimposed coding", and very much hearkens back to a time when memory was often the most precious commodity. I think you'll like it. ^_^
A very simple analysis in R:
> prop.test(c(9, 4), c(1103,1171))
2-sample test for equality of proportions with continuity correction
data: c(9, 4) out of c(1103, 1171)
X-squared = 1.4915, df = 1, p-value = 0.222
alternative hypothesis: two.sided
95 percent confidence interval:
-0.002409831 0.011897193
sample estimates:
prop 1 prop 2
0.008159565 0.003415884
I imagine the trie is better, given the prior analysis, and there is weak evidence for this. But take (a lot) more samples and know with confidence how much better.
I'd probably go with a custom perfect hash function. And Phil Bagwell's popcount trick. That would be faster than everyone else's solution that involves multiple lookups in memory.
The CPU is fast, memory is slow.
Maybe for the default hash function. As another commenter pointed out, your data may make the following hash very effective: s[0] + s[len(s)//2] + s[-1] which would be very fast. The point being is spending a day seeing if such a hash exists is worth it.
And in the case of a match, a fast hash + memcmp will be way faster than a trie traversal. In fact, according to the trie-hard github readme, std::HashMap is already much faster than their trie implementation when searching for a match.
Last time I checked, CRC32 worked surprisingly well as a hash.
The 'weird' instructions can often be 3-4 orders of magnitude slower than arithmetic instructions, though I doubt that matters here.
If you Google the words "CRC32 is slow", you can see hundreds of people complaining about this.
You would precompute the hash for the constant string list & then compute the hash only for for the set of strings that begin with C/c since "cf-" is a common prefix for those internal headers if I recall correctly, using RawTable to find entries by hash & then comparing against the precomputed value to see if a collision matched before checking a string for equality.
With ~100 static entries, o1hash (https://github.com/rurban/smhasher/blob/master/o1hash.h) should also work.
For this application, that's a leg up which a hash won't be able to touch. The rest of the art here is shaving down the constant factor of a trie far enough that the initial boost pays off in real-world performance.
It appears the "remove_header" call is this one: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.h... which calls .remove() on two other data structures, both of which bottom out in this mountain of code: https://docs.rs/http/latest/src/http/header/map.rs.html#1550
[1] https://github.com/metosin/reitit/blob/master/doc/performanc...
[2] https://github.com/julienschmidt/httprouter#how-does-it-work
It’s definitely not a common tool I reach for though.
It’s a nifty user-agent parser for Go: https://github.com/medama-io/go-useragent
Typically this sort of problem relies on lots of regex parsing, so it was nice to take a more novel approach.
In theory, if they used a regex it would be using a state machine to do the matching, which should have similar performance to the trie- only O(k) in the worst case. But from what I understand regex libraries don't actually build the state machine, they use backtracking so the performance is no longer O(k).
I'm surprised they couldn't find a performant regex library that already existed that uses state machines. It should have similar performance to the trie. But in reality, the performance is affected more deeply by things like memory access patterns and the performance of specific arithmetic operations, so it's impossible really to speculate.
A more naive approach might also be warranted. Some frequency analysis of hit/miss for trie nodes might allow them to find specific character positions with a higher miss rate than the first one. Testing such special positions first would speed things up. That assumes, of course, that the header data is fairly regular in nature.
1) Is this worthwhile? Looks like ~500 CPU cores were saved (are these real cores, or does this include hyperthread cores?). I don't know cloudflare's costs, but this seems like single digit servers and probably savings only in the $XX,XXX range. Not nothing, but do you expect a positive ROI on engineering?
2) If you do want to go to this detail, did you consider in putting the filter at the deserialization step, preventing the headers from being created in the first place?
Power savings forever.
Lower carbon emissions.
etc
Nice to see a company that cares about making things 1% faster rather than trying to analyse headers with AI to sell me sandals or something stupid like that.
So lets very conservatively assume 2 months. 12 months in a year so 6 40k savings a year. Thats 240k which is still below a fang salary but yeah it's per year forever and also as cloudflare gets bigger the 40k would turn into 50k without anybody acknowledging it.
Setting up a offshore office takes time and focus that could be spent on other initiatives etc.
That's million dollars.
But the aho-corasick crate, and especially the specific automatons, would be interesting to try. There's much less overhead there. But, there are some differences:
* The contiguous NFA in aho-corasick has a lot more going on inside its "next transition" routine: https://github.com/BurntSushi/aho-corasick/blob/cd400ad792d6... --- This is primarily because an Aho-Corasick automaton isn't just a trie. It also has failure transitions to support unanchored search. You can search without respecting failure transitions (and thus treat it as a trie), but the code is still there to deal with failure transitions. So that may have deleterious effects.
* The contiguous NFA also specializes its transition function depending on the size of the node. It would be interesting to see whether these techniques would be useful for trie-hard to play with. But there is definitely a benefit to keeping one simple and fast code path for all node types. (Less branching.)
* The aho-corasick crate does also expose a DFA directly: https://docs.rs/aho-corasick/latest/aho_corasick/dfa/struct.... --- In theory this should do less work per transition than trie-hard, and so it would be very interesting to measure its perf when compared to trie-hard. The main downside is that it's a DFA and can use up a lot more memory and take longer to build. It seems like Cloudflare cares less about that in favor of optimizing read perf though, so it's not clear why they didn't go this route.
* The aho-corasick crate doesn't let you store arbitrary values. You only get back a PatternID when a match occurs. So to get equivalent functionality as trie-hard, you'd need a separate map of PatternID->YourValue. Since that isn't stored with the data in the trie, this alone might penalize you quite a bit with poorer CPU cache performance.
* trie-hard seems to provide some customization options for its representation. i.e., Let's you use a `u8` to store its transitions versus a `u128` or `u256`. This might also help with cache usage for a small enough trie.
Does it support const construction so that you build it during compilation from a static set of strings?
(The `memchr` crate doesn't even support const construction of a single substring searcher. I haven't spent much time thinking about it because `const` is still pretty limited in what it supports, although progress is being made. For example, you can't use trait methods in `const`. So while you can undoubtedly use `const` Rust to build a single substring searcher, whether `const` Rust can be used to build the one in `memchr` specifically isn't clear to me. And if it could be done, it will undoubtedly come with development/code-clarity costs and it's not clear to me that those are worth paying. Because as I said, amortizing construction for a static set of strings is usually very simple to do.)
And in any case, "takes a long time to build and uses a lot of memory" isn't avoided by doing it at compile time. Instead, you get bloated binaries and longer compile times. Which costs matter more? Dunno, especially when you amortize construction at runtime.
> Instead, you get bloated binaries and longer compile times
Longer compile times probably are solved by having the strings live in a standalone compilation unit which the compiler will end up caching and you can only dirty it by adding a new string. Needing to shuffle that extra data around might still cost extra compile time, but in a real world program I suspect that's likely to not matter (both in terms of binary size & that other things in the program will be more expensive to compile).
That being said I agree that doing a LazyLock is probably sufficient and given the amount of entries being compared against acquiring the lazy lock probably also gets amortized (it's cheap but not free).
trie-hard seems to be effectively that, but with some clever masking to get mileage out of having a limited byte vocabulary to deal with.
The DFA might pull ahead, but I wouldn't just bet on that. Branch predictors don't like lookup tables much, and the memory locality hit is small but real: more of a packed trie fits in a cache line than would a DFA.
You seem to have landed on similar conclusions here: beating a packed trie for this specific use case is going to be tough.
I also like that they hit on the same popcount-and-shift technique I've used in a data structure for UTF-8 character sets: https://github.com/mnemnion/runeset. I admittedly haven't benchmarked this much, correctness first and all, but seeing that Cloudflare has seen good numbers for something closely related reinforces the few tests I have run.
As a text-matching connoisseur, you may find the runeset interesting. It turns out to be hard to search for papers on "UTF-8 character set", so if you're aware of any prior art here I'd love a heads-up. It's fundamentally a generalization of using u64 bitmasks for sets of ASCII, which is as old as the hills at this point.
To be clear, I'd bet trie-hard is still more space efficient. And using byte classes does require an extra look-up per transition.
But, worth measuring.
As your your RuneSet thing, I'd look at lightgrep and icgrep. I'm not 100% they have relevant work for you, but they might. In practice, I just combine sets of codepoints down into UTF-8 automata since that's needed anyway for lazy DFA matching.
I concur.
> lightgrep and icgrep
These are great tips for a "related work" section, but nothing like prior art as it turns out. So yes, relevant and appreciated.
> UTF-8 automata .. lazy DFA matching
I wouldn't expect RuneSet to be useful for any automata-based regex pattern matching approach, there's not a good way to incorporate the context switch, among other considerations, and while it's fast, I will be surprised (very pleased, but surprised) if it's faster. It's designed as a component of an LPeg style parsing machine, where it can be added inline and treated as an unusually large instruction. I haven't done more than time its test suite, which has shown that it's fast enough for the intended use, and that optimization time is best put into other parts of the design for now.
Origin: The point at which something comes into existence or from which it derives or is derived.
How can the request's destination server be the origin, if it is the destination server?
At least it's consistently inconsistent.
Granted, computer scientists are infamously known for being terrible at naming things.
"Origin" is a term from web browsers, from their point of view it refers to where a web page came from.
see https://developer.mozilla.org/en-US/docs/Web/Security/Same-o...
What about for the other integer sizes that the trie supports?
When people talk about BigO they usually talk about average Big-o and worst/best case Big-o is explicitly called out if mentioned, so you can't just think in terms of the worst possible case. Regardless I think they made several mistakes here as you note correctly.
BTreeSet is log(N) in number of nodes compared. But for strings that comparison is O(L) since you at least have to compare it to the string you find. So I believe it's at best O(L log(N)) where L is the average string length and N is the number of nodes which is worse than the hash table which is just O(L). It's tricky though if most strings don't match your string. In that case I believe you end up degrading to an O(L) + O(log(N)).
Similarly, you are correct that they can't be logarithmic in size and must be linear since you have to store the data. Tries can be sublinear depending on the input since it's a form of compression as well.
Similarly you are right about trie complexity not being O(log(L)) for trie misses. I think what they're observing is a massive speedup because mismatches error out on the first character usually. But it wouldn't be logarithmic as there's unlikely to be a logarithmic relation between headers that mismatch and the universe of matching words.
The part about big O being usually about the average case was helpful, I'm still at uni where we mostly talk about worst case performance.
If you're in a relevant course, might be a good opportunity to flag this to a professor or TA as a way to review. These kind of analyses can be tricky sometimes, especially if you need to prove it vs just do an answer by feel which is how engineers end up doing it (vs CS students that take the proofs much more seriously).
A way to sometimes double-check is to just simulate performance as input grows and see if it matches the expected log(N).
Anybody knows why?
[1] https://research.facebook.com/publications/scaling-memcache-...
The Zanzibar white paper from Google in 2019, for example lists top-line rpcs to Zanzibar at around 10m qps, but internal (in memory) cache hits at 200m qps and non cache internal fan-out at >20m qps. Zanzibar of course isn't http, but is a good public example of internal rpc fan-out.
Id expect cloutdflare similarly has some extremely high qps internal services.
[1]: https://github.com/cloudflare/trie-hard/blob/3d8163ca2d9208c...
Rust doesn't guarantee a particular memory layout except for types explicitly requesting that you get a specific representation, so showing this would at least require a caveat that it's not guaranteed to be accurate.
Furthermore, this specific data structure's internals are generic, so to show the memory layout, it would have to be for a specific instantiation.
(They do also provide a structure that includes instantiations between u8 and u256, mentioning in a doc comment that the 256 size dominates overall size, and so if you want to slim it down, use the internals directly.)
Then you wouldn't need to maintain a list of what is internal and you wouldn't have to do any trie lookups.
> At the time of writing, the rate of requests leaving pingora-origin (globally) is 35 million requests per second. Any code that has to be run per-request is in the hottest of hot paths...function consumes more than 1.7% of pingora-origin’s total cpu time. To put that in perspective, the total cpu time consumed by pingora-origin is 40,000 compute-seconds per second. You can think of this as 40,000 saturated CPU cores fully dedicated to running pingora-origin. Of those 40,000, 1.7% (680) are only dedicated to evaluating clear_internal_headers. The function’s heavy usage and simplicity make it seem like a great place to start optimizing.
Given how many requests are going out, and just how hot the function is, every single gain matters. If my read of the article is correct, this is the hottest part of the hot path, so every gain here is super important.
Obviously it is an improvement but a lot of time there is lower hanging fruit, like the fact that the cloudflare control plane is/was not globally distributed and could not tolerate data center outages.
That said: probably different teams with different priorities.
I also disagree that “it’s _only_ $20-30k” as some kind of reason to not do this kind of work. Think of it another way: that’s now another 680 cores that can do _net more work_, that’s another 20-30k we don’t have to spend when traffic increases. “I landed a small PR that wiped $30k net off our costs” is a statement that would make a lot of people in a business pretty happy.
It is about the opportunity cost, nobody is going to disagree that small optimizations are a net positive but what else could you have done with your time? Maybe cloudflare is at the point of maturity where there are no easy wins and only 1% gains left but I kind of doubt it given their reliability track record. How many dollars do they lose for every hour they are down? Probably more than $20k.
Because of this I think there's no way for them to answer your question or to say "hey, this could very well be a vector since we could not find any statistically significant impact between a vector, hash-map and trie in this code path for given workload".
This is a common fallacy I've seen in too many places. In other words, investing non-trivial engineering effort into optimizing a code-path that resembles .000001% of your workload is a waste of resources.
And due to the Amdahl's law
> Optimizing operations that are already measured in microseconds may seem a little silly, but these small improvements add up.
this is not how things usually work out in the end. Making small improvements in insignificant code-paths will still remain insignificant in the overall runtime performance.
Look at the end where they validate that the performance wins show up in production in a similar way that the microbenchmarks predict.
Do you perhaps know what the actual scale is? Is it a 100 proxies around the world or is 1k, 10k, 100k ...? I imagine that number is not very high since the blog post says that pingora-origin can serve 35M+ requests per second. My wild guess would be not more than 100 deployments. If so, then the "at scale" argument loosens up quite a bit IMO.
> it frees up the cycles for other software
I see this more like a theoretical stance since with such argument we could micro-optimize the code all day every day. It's a reverse HTTP proxy intended to be high-performance and low-latency so I don't imagine that the server that is running it has more important software to run.
Literally every single Cloudflare edge server that processes requests runs this proxy. Based on other things you said, it seems like your mental model of how Cloudflare's network runs is inaccurate. Mapping pingora origin requests/s to number of servers is difficult because of how tiered caching works & not all traffic is tiered cached and from what I remember pingora origin refers to all origin requests and a good amount of them aren't tiered (e.g. Workers outbound requests to the origin go through pingora origin & don't typically tier) which means those requests are being made directly from the edge (also tiering isn't like there's 100 servers - it spreads the load out evenly to avoid overwhelming any single server).
[1] suggests ballpark of 164 data centers and each data center is multiple machines each with multiple cores; [2] says the next gen servers have 128 cores while [3] suggests that the current gen has 96 and the previous has 48. We can assume that on average each server in a data center has 64 cores. Let's assume there are 20 machines in a data center on average (I don't remember the exact number so it's a wild guess). That comes out to an estimate of ~30k machines with ~2M total cores and this reverse proxy being responsible for ~20% of CPU time on average for every single machine (40k CPU cores from the article divided by 2M total cores across the network).
> It's a reverse HTTP proxy intended to be high-performance and low-latency so I don't imagine that the server that is running it has more important software to run.
In fact, the server that's running the proxy is also the server that's handling the inbound request as well as the Workers runtime, Cloudflare tunnels, firewall product, image optimizations, DDOS protections, etc etc etc & any other internal software they have to run to maintain their network (observability, keeping track of routing graphs, etc). So yes, CPU cycles are largely fungible and will be freed up for use on other tasks / to absorb growth as they acquire more traffic (& even if your server is underutilized this can help because it means the CPUs are switching contexts less often given how many threads are on these machines resulting in potentially better latencies at the extremes for neighboring services). There's more nuance here but this is a good first order approximation.
And yes, it's a micro optimization but clearly helpful at scale when you add up many teams doing micro optimizations. For example, here's a sqlite blog post [4] explaining how micro optimizations that don't even show up in real world systems (unlike this one which does) over an extended period of time yielded an overall 50% improvement.
Now how much is it worth to optimize global CPU usage by 0.34%? I don't know but Cloudflare does have a good way of converting CPU cycles saved to how much it saved in terms of number of servers they had to buy. Back of the envelope this added ~1k machines worth of compute time capacity to the network (0.34% * 2 million cores / 64 cores per machine). I think it's interesting the 0.34% is the actual CPU usage from their blog post and also comes up if you multiply the 20% of CPU time I estimated for the server by the 1.7% they said that hot function takes up but I think that's mostly an accident - they predicted 0.43% which suggests that the network is larger than 2M (~31k servers) and maybe they have 2.5M cores (~39k servers) and between offline servers and workloads varying due to time of day in practice they're probably closer to using ~2M cores total of their overall capacity. That optimization could still be worth doing since SRE's are responsible for maintaining fleet health while the Pingora team is responsible for their corner.
[1] https://community.cloudflare.com/t/how-many-datacenters-does...
[2] https://blog.cloudflare.com/cloudflare-gen-12-server-bigger-...
[3] https://blog.cloudflare.com/the-epyc-journey-continues-to-mi...
[4] https://sqlite-users.sqlite.narkive.com/CVRvSKBs/50-faster-t...
I think you wanted to say 2% of CPU time on average and not 20%, no?
> In fact, the server that's running the proxy is also the server that's handling the inbound request as well as the Workers runtime, Cloudflare tunnels, firewall product, image optimizations, DDOS protections, etc etc etc & any other internal software they have to run to maintain their network (observability, keeping track of routing graphs, etc).
Sure, they have plethora of software that they need to run but that wasn't my point. My point was rather that I cannot imagine that a single VM that runs the low-latency service such as the proxy is also running any type of heavier weight services. Thus an argument of freeing up the CPU cycles for some other software when in reality there probably isn't any didn't make much sense to me.
This would be a legitimate argument if there was a challenge to begin with. Such as "we noticed that our 64-core 128G VM that runs the proxy is becoming saturated and thus the tail-latency of our XYZ service running on the same VM is starting to degrade". Without the problem statement "freeing up cycles for other software" is otherwise purely theoretical goal that is difficult if not impossible to quantify.
> And yes, it's a micro optimization but clearly helpful at scale when you add up many teams doing micro optimizations.
Perhaps in companies such as Google where they have a dedicated team developing fundamental low-level data-structures and/or runtime which is then used by 1000's of their other internal services. I believe that's actually one of the reasons why GoogleBenchmark was designed. In majority of other companies micro-optimizations are only a very good brain gymnastics exercise, I think.
> For example, here's a sqlite blog post [4] explaining how micro optimizations that don't even show up in real world systems (unlike this one which does) over an extended period of time yielded an overall 50% improvement.
The hypothesis of
"100s of micro-optimizations add up to an overall 50% improvement"
"there were a few changes but we don't know what are the exact changes that contributed to the majority of 50% improvement"
That said, reducing the CPU cycles for certain workload by ~30% is a noble and quantifiable artifact especially if you're a database company hosting thousands of your database instances since this obviously directly translates to more $$$ due to the better hardware utilization.
However, trie-hard micro-optimization is done in the software that constitutes 2% of their total CPU time (if your ballpark estimates are somewhat close). Since the micro-optimization cut down the CPU utilization from 1.71% to 0.34% of 2% of 100% of CPU time this, in other words, means that total fleet-wide net of CPU utilization went from 0.000342% (before the change) to 0.000068% (after the change).
I encourage you to imagine harder then. Nearly all of the software is running bare metal and as I said it’s all replicated on each machine. So the same server is running the reverse proxy and the CDN and the Workers runtime and Cloudflare tunnels because the any cast routing they use intentionally means that every single inbound request always hits the nearest server which generally processes the entire request right on the machine and uses Unimog to distribute the requests within a data center [1] and Plurimog [2] to distribute load between data centers. I’ll repeat again - every server runs the proxy along with every other internal and external product and there’s no VMs or containers*.
I’m not going to engage with the rest of your hypothesis that it’s not worth the effort until services are falling over or it’s the root cause for some tail latency since the team has indicated it clearly is worth their time and value to Cloudflare.
[1] https://blog.cloudflare.com/unimog-cloudflares-edge-load-bal...
[2] https://blog.cloudflare.com/meet-traffic-manager/
* technically there are VMs but it’s not worth thinking about for this specific discussion since the VM is closer to being just like any other application. It’s not virtualizing the cloudflare software stack but just providing a layer of isolation.
I have no experience with Rust so this is a naive question- why not use an array of strings to store these headers?
Arrays have O(n) lookup in the worst case, and HashMaps have O(1), as the post mentions. Basically, you have to walk through the entire array of the header you’re looking for is at the end, whereas it’s always cheap with a HashMap. But the trie is even better!
Basically, none of this is Rust specific, it’s just algorithms stuff.
The “trie-hard” crate is a solution to the layers of cruft at CF
...and amazingly, it's still up from 2010: https://lorgonblog.wordpress.com/2010/02/21/dawg-gone/