Sozu routing benchmarks
This project explores optimizations for the SNI certificate lookup and HTTP router algorithm in the sozu HTTP reverse proxy.
In sozu, configuration changes happen often at runtime, and it is designed as a load balancer for tens of thousands of different applications and routes.
We need a compact way to store those routes, that can be updated quickly, and for which lookup is fast. As a point of comparison, a fast HTTP parser takes 150-300ns to parse all the headers.
The current implementation in sozu is based on a trie that works on reversed domain names, ie for the "example.com" domain, the key will be "moc.elpmaxe". It matches on prefixes, handles the special case of wildcard domain names for SNI. Once the trie has found a matching node for the domain, the node holds a list of URL prefixes that match to applications.
This has served sozu well in the context of Clever Cloud, where we have a lot of different domains, but the more common use case is to have a few domains, but a lot of URL/app matches.
We also need more flexible matching patterns, like regular expressions on domain names and URL.
Routing experiments
this repository holds various experiments around routing and trie optimizations, mostly working on domain names.
Some base examples are available:
- the "sozu" version uses the trie available in sozu 0.11
- the "hashmap" version uses a hashmap to lookup the route (so no prefix or wildcard usage)
- the "linear" version tests routes one after the other until one matches
(key, child)
Exp 1: trie with vector of This is a naive implementation of a trie, with wildcard domain support. It is easy to write, and easy to update in place.
Exp 2: trie with vector of key and vector of children
Builds on exp1 but separates the keys
This is the current version on sozu 0.11
Exp 3: keep a local prefix, and only the first byte of each child key
this implementation leverages common prefixes to only match them once. And the children will necessarily have differences on the first byte of the rest of their key.
Exp 4: state machines
Experiment 4 uses the fst crate. This comes with a tradeoff: since the list of keys has to be sorted, any edition requires rebuilding the entire machine. We could live with this tradeoff, by making the master process write a new state machine while the workers use the previous one.
Exp 5: trie with bitvec
this one uses the bitvec crate to test a language restriction: domain name uses alphanumerical characters (we can limit to lowercase) and '-', '.', '*', and '_' (the underscore is not in the spec, but we've seen usage in the wild.
We can convert those caracters to a 6 bit encoding, and have a more compact tree, with potentially faster lookup.
Exp 6: state machine with bitvec
Experiment 6 reuses the fst from exp 4 with the bitvec language from exp 5.
Exp 7: regex set
this version makes a regex out of each route, and uses a RegexSet
from the
regex crate to assemble them.
Exp 8: specialised trie
This is a more complex version of the exp 3 trie. It uses a cursor structure made from the domain name and the URLL, and can match prefixes, regexes and SNI wildcard on it. As a result, the trie nodes are a bit larger
Exp 9: tree of hashmaps
This version cuts domain names in labels, and each node contains a hashmap of the next labels to the corresponding children. It uses the hashbrown crate for its fast hashmap implementation (swisstable)
Exp 10: tree of hashmaps with SipHash
There's a case where exp 9 could be vulnerable to hash flooding, since at Clever Cloud, our users control which domain names are used. So this one takes the code of exp 9 with the siphash hash algorithm (currently used as default hasher in Rust)
Benchmark results
tested on a MacBook Pro (Retina, 15-inch, Late 2013), CPU 2,3 GHz Intel Core i7
We have 3 main benchmarks to compare results:
- time to fill the structure with 100 entries, by incremental edition
- time to lookup a known key in a structure of 1000 entries
- time to lookup an unknown key in a structue of 1000 entries
fill structure | lookup known key | lookup unknown key | |
---|---|---|---|
linear | 1.35 ms | 31 us | 34.31 us |
hashmap | 1.42 ms | 7 ns | 1 ns |
current sozu impl | 1.60 ms | 182 ns | 229 ns |
1: trie | 1.82 ms | 138 ns | 80 ns |
2: trie+separated keys | 1.95 ms | 144 ns | 80 ns |
3: optimized trie | 1.72 ms | 74 ns | 52 ns |
4: fst | 7.58 ms | 354 ns | 117 ns |
5: trie+bitvec | 12.89 ms | 5.79 us | 2.08 us |
6: fst+bitvec | 14.69 ms | 5.82 us | 2.12 us |
7: regexset | 33.10 ms | 1.15 ms | 1.19 ms |
8 trie cursor | 1.89 ms | 119 ns | 57 ns |
9: hashmap tree | 1.73 ms | 65 ns | 28 ns |
10 hashmap tree + siphash | 1.89 ms | 109 ns | 57 ns |
We also have a version with larger values, but eliminating the slowest versions (experiments 4, 5, 6 and 7), as they would make a the benchmark take too long.
- time to fill the structure with 1000 entries, by incremental edition
- time to lookup a known key in a structure of 10000 entries
- time to lookup an unknown key in a structue of 10000 entries
fill structure | lookup known key | lookup unknown key | |
---|---|---|---|
linear | 12.68 ms | 560.68 us | 586 us |
hashmap | 13.88 ms | 7 ns | 1 ns |
current sozu impl | 15.71 ms | 230 ns | 223 ns |
1: trie | 18.14 ms | 158 ns | 81 ns |
2: trie+separated keys | 19.17 ms | 159 ns | 87 ns |
3: optimized trie | 16.45 ms | 83 ns | 51 ns |
8 trie cursor | 19.62 ms | 127 ns | 58 ns |
9: hashmap tree | 16.50 ms | 64 ns | 28 ns |
10 hashmap tree + siphash | 18.34 ms | 113 ns | 58 ns |
We can see that the trie implementations stay stable when we increase the number of entries. They do not perform exactly the same tasks (experiment 8 especially is testing regexps along with the prefixes). While version 9 and 10 looks like a quick and dirty fix, it's actually easy to write and maintain, its performance is very stable, and we can make Siphash usage configurable. So we will recommend adapting the tree of hashmaps as new solution.