4 ms·
Not sure what they use to hold the cache key and entry. If a hashmap is used, then a radix tree (adaptive radix tree) would be better in saving memory space. Mo
by ww520 29d ago
Not sure what they use to hold the cache key and entry. If a hashmap is used, then a radix tree (adaptive radix tree) would be better in saving memory space. Most of content of the qname field of the CacheKey is hostname, like www.site.com. The reverse version com.site.www fits nicely in navigation path of a radix tree. The common prefixes like "com." are shared and compressed in the parent nodes of the tree.
Even a BTree with compressed prefix keys can save space in the qname.
- Tuna-Fish 29d agoAt this scale, moving from one pointer chase to multiple is almost certainly a huge loss, even if radix tree would save a lot of memory.
- ww520 29d agoUnless the keys are completely random, compressed keys shorten the tree height and cause fewer pointer jumps. Hostnames are highly compressible. Plus the root and the upper levels of the tree are always hot, most likely in L1/L2/L3 all the times. OTOH collisions in hash table cause pointer chase as well.
- vismit2000 27d agoExactly: https://github.com/pytries/marisa-trie https://github.com/pytries/marisa-trie