A good day to trie-hard: saving compute 1% at a time

https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/

by eaufavor • 2 years ago

614 173 2 years ago

blog.cloudflare.com

amluto7• 2 years ago

If you had asked me to make a wild guess as to how Cloudflare stores internal headers and then removes them, I would have come up with some options:

- 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.

jgrahamc3• 2 years ago

Yeah, me too, but systems grew over time and grew and grew and we were using HTTP headers for all sorts of stuff. This optimization makes the situation better, but the solution (which is underway) is to use a different mechanism for IPC and get rid of the use of HTTP headers completely.

DamonHD3• 2 years ago

And when that happy day dawns, slightly sadly, this nice optimisation will evaporate!

throwaway77385• 2 years ago

For anyone not in the loop, the above poster (JGC) is Cloudflare's CTO himself :)

amluto7• 2 years ago

I’m certainly familiar with systems growing over time and outgrowing their original schema.

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.)

alex_suzuki• 2 years ago

You chiming in on this post makes me slightly bitter at having gone with CloudFront (I have everything on AWS so it seemed the obvious choice) instead of Cloudflare.

efitz• 2 years ago

Ive worked at several huge corporations in IT security, where we care about headers a lot, and they all use headers in a manner similar to CloudFlare.

Including using proxies at the edge to strip out internal headers bidirectionally- yes, inbound too.

sitkack3• 2 years ago

That doesn't make it better, it makes it worse.

hinkley11• 2 years ago

The first large scale piece of software I worked on was for telcos pre smart phone. We used internal headers to offload authentication and terminate SSL. We also had to pressure F5 to fix about half a dozen bugs in BIG-IP to do so. Bugs that should in no universe have existed in version 9 of a product.

I used to joke that F5 owed me and my coworker 3 months of salary for all the free QA we did for them.

620gelato2• 2 years ago

Or perhaps even, insert yet another header with just the list of internal headers being added to the request, assuming this happens at a single place, otherwise a recipe for disaster.

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.

amluto7• 2 years ago

This doesn’t work if the front end is older than an internal node and a header gets added, at least not without extra logic to patch everything up and handle conflicts.

The HTTP Connection header works like this, and one should generally assume that almost nothing implements it correctly.

adrianmonk• 2 years ago

yet another header with just the list of internal headers

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.

taeric4• 2 years ago

Other ideas:

  - 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.

In fact, if you preseed, you are basically combining these ideas but fixing how many internal headers are on each request. At that point, you can use a linked hash table that preserves creation order and just remove the first N from the final list that you send back to clients.

amluto7• 2 years ago

At that point, you can use a linked hash table that preserves creation order and just remove the first N from the final list that you send back to clients.

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.

giancarlostoro• 2 years ago

What if someone else uses this name?

Couldn't you bypass this by pre-fixing the ones that aren't yours? Or prefixing your internal ones with something unique enough?

e63f67dd-065b• 2 years ago

Former employee here; the interesting (horrifying?) fact is that you can set some of these internal headers (I remember a notable bug with cf-cache-status) in workers (the serverless offering) and cause all kinds of bad things to happen :)

Aeolun4• 2 years ago

It seems to me it should be trivial to strip anything internal that comes out of a worker right?

hn_throwaway_993• 2 years ago

I feel like I can point out lots of similar problems to the other solutions you suggest (heck, I thing some of those problems you list even apply to those other solutions).

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.

amluto7• 2 years ago

Lists, extensible protobufs, etc are indeed great in their extensibility. The issue I would see (if I worked at Cloudflare) isn’t to using a list — it’s that the list is the same list that’s used for externally visible HTTP headers.

Aeolun4• 2 years ago

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

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.

danbruc• 2 years ago

This might of course introduce quite a bit of overhead, but the clean solution would arguably be to not mix requests to begin with, the external requests you are processing are the payload of the requests you are sending around internally. This would also allow you to cook up an optimized encapsulation protocol that might be more efficient to process than parsing and modifying HTTP. This admittedly comes from someone with essentially zero knowledge of what exactly Cloudflare is doing to the requests they receive.

anonymoushn• 2 years ago

X years ago the manager of the cache team raised the lack of data plane and control plane separation as an issue and we came up with various plans to fix things, but I guess nothing has happened since

Scaevolus2• 2 years ago

Did you try a (tiny) bloom filter? Doing a quick convolution of the header key and a test against a bloom filter (SIMD? Using builtin CRC ops? 256-bit bloom filter size?) might avoid walking the trie altogether in most cases at the cost of a few cycles.

jgrahamc3• 2 years ago

I do not know if the team did that but Bloom filters aren't a panacea: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/

Scaevolus2• 2 years ago

Yeah, for this problem you'd want a bloom filter that can entirely fit in vector registers during the computation, which should work well for a few hundred items.

vlovich12311• 2 years ago

A bloom filter will have the same weaknesses of needing to do a hash. For static filters like this though where you have the set of strings to check against known up front, something like a binary fuse filter could work really well as it's significantly faster than bloom filters when you don't need online construction (you still need to do a hash of course but the evaluation against std::HashMap is flawed since it uses SipHash instead of modern constructions like xxh3 or gxhash).

jkaptur2• 2 years ago

I think that would require calculating the hash, which was ruled out as too slow.

pragma_x2• 2 years ago

Considering that each node's filter in their trie implementation is bloom-like already, the solution is awful close. I agree that testing wider swaths of the string at once might be a dramatic accelerator.

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.

IncreasePosts• 2 years ago

Off topic: how does 60M requests a second stack up with other big players like google, Facebook, TikTok?

xyst2• 2 years ago

This 2013 research article from facebook indicates memcached handled “billions of requests per second” [1].

[1] https://research.facebook.com/publications/scaling-memcache-...

joshuamorton• 2 years ago

I will note that http requests and internal requests are distinct.

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.

why_only_15• 2 years ago

People typically quote google search as ~300k QPS

miso2024• 2 years ago

Finally a blog post with a trie. Those trie leetcodes didn't go in vain ;)

marcosdumay• 2 years ago

You will find them in any fast spelling or grammar verifier.

koito17• 2 years ago

Routing libraries as well. In Clojure, the reitit library uses a prefix tree implementation when the route table is large enough for linear search to be non-optimal.[1] The Go ecosystem also has httprouter, which uses prefix trees under the hood.

[1] https://github.com/metosin/reitit/blob/master/doc/performanc...

[2] https://github.com/julienschmidt/httprouter#how-does-it-work

steve_adams_86• 2 years ago

I’ve used them in real code! They are pretty intuitive for some use cases. The last time I used a trie was for address lookup. I even used a generator, haha. Double whammy leetcode in real life situation I guess.

It’s definitely not a common tool I reach for though.

ayuhito• 2 years ago

I recently got a chance to find a practical use for a modified hybrid trie which was fun to implement! Lots of optimisations to go around.

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.

jitl• 2 years ago

i find myself reaching for a trie/radix-tree from time to time in medium-complexity build tools or code analysis scripts, where I need to store some information about zillions of filepaths, and factoring out the common prefixes saves a ton of memory while being pretty intuitive

cdelsolar• 2 years ago

Tries are huge for Scrabble move generators and playing programs, of which I've written a few. The fastest structures are compressed tries with rotated representations of words.

cwilby2• 2 years ago

Internally, we call the request’s destination server its “origin”

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?

toast0• 2 years ago

The origin is the origin of the content.

cwilby2• 2 years ago

Thus cross origin resource sharing. Thanks!

At least it's consistently inconsistent.

tills13• 2 years ago

On the internet, the origin is the server sending the response to the user. I suppose you can look at it from the perspective of the owner of the server -- from their frame of reference, their journey _starts_ when they receive, process, and respond to the request.

Granted, computer scientists are infamously known for being terrible at naming things.

hinkley11• 2 years ago

Had any fun with “Referer” headers lately?

fowl2• 2 years ago

Depends on your perspective :)

"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...

taeric4• 2 years ago

This hilariously reminds me of the complaining about X server semantics back in the day.

evmar• 2 years ago

This post uses a fancy data structure to construct a to_remove set, then iterates through it to remove these from the underlying header map.

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

aidenn0• 2 years ago

Given that the set if items to match is static, I wonder if they tried a perfect hash table; that would reduce it to a few arithmetic operations followed by a single string compare. It would be interesting to see how it compares to the trie.

sjf• 2 years ago

That is what I immediately thought as well. The problem though is that a perfect hash is still going to be O(key length) for the hash function, which they are trying to avoid.

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.

lesuorac2• 2 years ago

I wonder how much faster it gets when you shorten the maximum internal key length. If you re-map everything to like "cf-1", "cf-2", .. "cf-;" then you'd only need to hash like 4 characters.

sophacles• 2 years ago

So this trie uses a custom u256 type that is a wrapper around an array of 4 u64s. Is rust smart enough to vecorize it into AVX instructions for the bit twiddling?

What about for the other integer sizes that the trie supports?

FridgeSeal4• 2 years ago

A lot of Rusts' optimisations are from LLVM, so if that's smart enough to, then I assume it also benefits.

Validark3• 2 years ago

If the bit twiddling is independent in each u64, then probably. If it's treated as one giant bitstring, probably not.

mightyham3• 2 years ago

I'm not very well versed in data structure optimization, but I was surprised they dismissed hash tables so quickly, especially when the table they are searching through is static. I find it somewhat hard to believe that a specially optimized hash table would not be faster than their trie implementation.

supermatt• 2 years ago

They mentioned it is the overhead of the hashing that makes it slow compared to the trie.

hooli423• 2 years ago

Hash functions can be as simple as a single modulo.

mightyham3• 2 years ago

The point I'm making is that a specially optimized hashing function would probably blow away any trie traversal. When you know the data being hashed before hand it is possible to make custom hash functions that are as simple as a few bitwise operations on the first, middle and last character of the string (just an example).

vlovich12311• 2 years ago

If they just used the default, that's SipHash which is optimized for security and DOS resistance, not performance. XXh3 is ~10x faster than that and there's some newer ones that are even faster than Xxh3 like GxHash (like another ~1.5x-2x faster).

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.

5kg• 2 years ago

There is FxHashMap (https://github.com/rust-lang/rustc-hash) which is faster than std::collections::HashMap.

With ~100 static entries, o1hash (https://github.com/rurban/smhasher/blob/master/o1hash.h) should also work.

rapsey• 2 years ago

Note FxHashMap is just the std HashMap with a different hashing algorithm.

samatman4• 2 years ago

A hash function can't reject a string with a single test of the first byte. It just can't.

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.

MehdiHK• 2 years ago

Slightly off topic: I was a bit surprised nobody ported space-efficient marisa trie to Rust, or any other languages.

Anybody knows why?

https://github.com/s-yata/marisa-trie

hyperpape• 2 years ago

I'm interested to know why the regex crate didn't do better. I believe it should compile a search for multiple literal strings into an Aho-Corasick automaton, which is structured very much like a trie.

burntsushi3• 2 years ago

regex crate author here. From a quick look at trie-hard, my guess is that trie-hard can do lookups on short strings much more quickly than the regex crate can do matches on short strings. The regex crate has a fair bit of overhead for selecting the right matching engine and applying other optimizations appropriate to general purpose matching.

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.

vlovich12311• 2 years ago

can use up a lot more memory and take longer to build

Does it support const construction so that you build it during compilation from a static set of strings?

samatman4• 2 years ago

This is a gratifying read (along with the article) because I've been working on closely related things, and had come to the tentative conclusion that taking Aho-Corasick, anchoring it (so no failure transitions), and laying it out in contiguous memory, basically results in Liang's packed trie from TeX's hyphenation algorithm.

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.

hencoappel• 2 years ago

Given it's such a hot part of their code, I'm genuinely surprised they didn't go down the state machine route for as optimal a solution, or even further and made use of vector instructions. Maybe Rust can autovectorise the code though.

wolf550e• 2 years ago

I don't know Rust. Can someone explain how this data structure stores whether a node is itself a valid word or whether it only leads to more nodes? For example the node "do" in their (“and”, “ant”, “dad”, “do”, & “dot”) example. I guess it's a discriminated union provided by Rust algebraic data types or something like that, but why not show the full bit pattern in memory?

SkiFire13• 2 years ago

By looking at the source code [1] they have a discriminated union with 3 variants representing the possible combinations of representing a valid word and leading to more nodes (excluding the case where it is neither, which is impossible). So the node for the 'o' in "do" should be a `SearchOrLeaf` storing "do", its corresponding value (the `T`, in a set this would be empty) and the `SearchNode` containing the successors, which should only contain a 't' to "dot".

[1] https://github.com/cloudflare/trie-hard/blob/3d8163ca2d9208c...

steveklabnik2• 2 years ago

why not show the full bit pattern in memory?

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.)

pragma_x2• 2 years ago

It took me a moment to ponder the effectiveness of mapping utf8 characters into a bitmask. At first, it seemed unwise. Then I realized that 32 bits would get you `a-z` plus six special characters, and 64 bits would get you 'A-Z' (uppercase) plus six more. That's plenty of room for HTTP headers, and for a blazing fast matching algorithm since it just masks and compares a couple integers. Even figuring out which bit corresponds to which character is a simple lookup into a 256-word table.

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.

https://en.wikipedia.org/wiki/Bloom_filter

samatman4• 2 years ago

There are significant differences between trie-hard and a Bloom filter. Bloom filters are probabilistic, and use hashing. They're great for when rare false positives are acceptable in exchange for no false negatives, which isn't uncommon, but isn't what's needed here: this is exact, and hashing is the step to beat.

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. ^_^

https://tug.org/docs/liang/liang-thesis.pdf

gcbirzan• 2 years ago

The problem is that bloom filters are good when your dataset is large and calculating several hashes per item is not as expensive as looking it up in the original dataset. Here, they say that even one hash is expensive, so bloom filters would be much slower than the original hash map.

maciek122• 2 years ago

Am i missing something or is the big O notation in this article wrong? For example in "Sorted sets like BTreeSet use comparisons for searching, and that makes them logarithmic over key length O(log(L)), but they are also logarithmic in size too" how is the search done in logarithmic time? You could have a header that differs from an internal one only on the last character and then you have to read the whole thing. Also space-wise B-trees are linear, not O(nlogn). Additionally, at the end when talking about the trie, how do you achieve O(log(L)) for misses? Tries are not balanced, they do not halve the possible set on comparison (as I think the author states) and even if they did I don't see how that achieves the logarithmic time.

vlovich12311• 2 years ago

You could have a header that differs from an internal one only on the last character and then you have to read the whole thing

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.

maciek122• 2 years ago

Thanks for replying, I really appreciate you taking the time to check my concerns! I was afraid I was going crazy haha.

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.

o11c• 2 years ago

That late in the process, does it even need to support efficient lookup? Could it just be a Vec?

menaerus4• 2 years ago

They don't explicitly say that in the blog post but I assume that the engineering team behind this code does not run any workload performance experiments themselves but they only run the local (micro)benchmarks.

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.

vlovich12311• 2 years ago

If we compare the sampled performance of the different versions of clear_internal_headers, we can see that the results from the performance sampling closely match what our benchmarks predicted

Look at the end where they validate that the performance wins show up in production in a similar way that the microbenchmarks predict.

xyst2• 2 years ago

It’s a bit wild to me that one needs to add so many http headers internally that they need to get stripped off.

The “trie-hard” crate is a solution to the layers of cruft at CF

FridgeSeal4• 2 years ago

I don't think it would matter if there's only 1 header to be removed, it's still a problem to be solved.

mgaunard• 2 years ago

If it takes 3.5 us to remove a substring within a packet-sized string you're doing it wrong.

alexchamberlain• 2 years ago

Jumping on the bandwagon of other ideas... I wonder if it would be quicker to filter pit the internal headers when you write the request to the network (buffer)? ie something like `request_headers.filter(not_is_internal).for_each(...)`; that way you don't have to remove anything from the data structure at all, but does require you to break down a layer of abstraction for performance benefits.

vlovich12311• 2 years ago

No, you'd just be smearing the work at best. The expensive part is determining set containment not updating the data structure. It doesn't matter if you do it in a loop and update the data structure or do that check before writing.

sixo• 2 years ago

this post makes me think I could work at cloudflare, and also that I shouldn't

kristianp• 2 years ago

I would have stopped at the first step, saving almost 1% of cpu time (0.993%). Creating a new fast trie data type for the other 0.287% seems inefficient. Surely there are other parts of the code that take more than 1% of the cpu time elsewhere to be looked at first?

FridgeSeal4• 2 years ago

From the article:

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.

__turbobrew__2• 2 years ago

680 cores is peanuts. That is less than 10 modern specced compute servers. Its not nothing but you are probably talking about $20-30k/year in opex costs, which at the scale of cloudflare is probably a drop in the bucket.

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.

y04nn• 2 years ago

Why adding and then removing HTTP headers of a existing request for routing instead of adding a dedicated (custom) routing protocol above the HTTP stack? This would allow to just drop the added protocol on the outbound and be much more space efficient.

intelVISA• 2 years ago

The fabled tech talent shortage, probably.

gwittel• 2 years ago

Neat optimization! Would it have been feasible to spend a bit of cpu/memory and tag headers as internal upon the request construction? That way filtering on output is trivial.

unusualmonkey3• 2 years ago

My 2c:

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?

aetherspawn• 2 years ago

It might only be $XX,XXX but it is forever.

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.

unusualmonkey3• 2 years ago

It's not forever, in another comment they're reworking their entire internal comms protocol.

saagarjha• 2 years ago

If an engineer spends a couple of days on it then the savings seem worthwhile?

_zoltan_• 2 years ago

I don't understand your point about the ROI. Let's say it's 40k a year for 5 years that's 200k. That's a multi year salary Hungary/Poland (I have no idea of CF has offices there.)

lesuorac2• 2 years ago

Not just that but there's no time frame in the blog post. They mention that Pingora was released a few months ago (which was really 10) however I doubt they spent 10 months on the singular change.

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.

unusualmonkey3• 2 years ago

And if it introduces a bug that causes downtime that could cost millions.

Setting up a offshore office takes time and focus that could be spent on other initiatives etc.

cryptonym2• 2 years ago

That's such a tiny corner case but yet something you can easily publish. Fuelling marketing content to ends with hundred geeks discussing if what CF is doing makes sense or how much they care about perf.

That's million dollars.

pianoben• 2 years ago

This solution reminds me of an old blog post, where two members of the F# team at Microsoft battled back and forth on making the best solver for some word game. Cloudflare's solution here looks a lot like the second-to-last solution; the final post involved collapsing the tree nodes into a 2D array of u32s for maximum cache-hits. It was a really neat solution!

...and amazingly, it's still up from 2010: https://lorgonblog.wordpress.com/2010/02/21/dawg-gone/

bhawks2• 2 years ago

Alternatively at request ingress time you could take all original header names and save them, and at egress time you could use that list to drive which keys to emit?

Then you wouldn't need to maintain a list of what is internal and you wouldn't have to do any trie lookups.

Buckaroo9• 2 years ago

Shouldn't this line: > "using regular expressions clocks in as taking about twice as long as the hashmap-based solution." be written as the opposite? That the RE takes half as long/is twice as fast?

nitnelave• 2 years ago

I think the point is that naive regex are a very generic purpose tool, but it's still in the same ballpark. Having a custom optimized state machine for this specific use case could bring another 5x improvement on top, leading to 2.5x faster, potentially.

mwexler• 2 years ago

I know, they aren't the first to use it, but I still appreciate the pun.

Validark3• 2 years ago

It's silly to use Big-O to describe the number of comparisons when the goal is to analyze performance. Comparisons cost 1 cycle, and you can do many of them per cycle with instruction level parallelism and SIMD. The main bottleneck, the actual source of slowness, is memory. It costs thousands of cycles to go to memory, sometimes tens of thousands or hundreds of thousands (if you need a TLB walk or OS interrupt). If you want to use Big-O, use it to estimate the number of cache misses.

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.

gregsexton• 2 years ago

The presented data for demonstrating a win doesn't have enough power to actually show this - not enough samples were taken.

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

A p-value of 0.22 isn't below the magic 0.05 and the 95% confidence interval suggests that the trie might actually be slightly worse.

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.

alohashirt992• 2 years ago

This was an interesting blog - a real world example of tuning Rust code with actual measurements.

I have no experience with Rust so this is a naive question- why not use an array of strings to store these headers?

steveklabnik2• 2 years ago

They did do that at first; the “static Vec” reference is to this. A Vec<T> is a growable array type.

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.

A good day to trie-hard: saving compute 1% at a time

Related Stories