4 ms·

I would atleast use a hashmap rather than a linear scan for lookup. My guess is you would be utmost 10x faster in that case

TaikiSan 8y ago
Absolutely! This would have been a problem when a IP range was blocked however. You would have to test 32 subnets for any given IPv4 (or 128 for IPv6!). We knew it was not ideal, but it had the least downsides at the time.
- daveFNbuck 8y ago
  This is the question I had the entire time I was reading your post too. Doing set membership testing in constant time is already a solved problem, so why go through the trouble of radix trees when you could use any number of pre-built solutions? I think it would have been a much more interesting and useful read if you had included the reasons that a radix tree is a better solution for your use case than hashing and how you implement range blocking. I also wasn't able to understand the advantage of path compression or why being fixed-length is important.
  - dgritsko 8y ago
    Wouldn't the benefit of path compression mean reducing the memory footprint of the data structure? And regarding fixed-length: "This lets us optimize the lookup code." More detail here would be cool but it wasn't really the point of the article.
    - daveFNbuck 8y ago
      My guess is that the path compression speeds up lookups by increasing data locality and reducing the number of fetches needed. Memory footprint probably isn't a big concern for storing 10,000 entries.
  - ganonm 8y ago
    If I understand the post correctly, the advantage for e.g. inserting a subnet is that most of the overall IP address value is shared between each IP in the subnet. In a Radix tree, this shared data will only be represented once in the three (since the entire path from root to leaf makes up the entry value). For a hash based solution, yes you get constant time insertion and constant time access, but you need a unique entry of the entire IP for each individual entry. This increases overall memory requirements. If query time became a bottleneck, would you consider putting a Bloom Filter in front of the Radix tree? This would have low memory usage and a low false positive rate. Any positive hits would then do an exact check on the radix tree. So, for say 99% of non-blacklisted IPs, you would get constant time blacklist checks.
    - daveFNbuck 8y ago
      The problem they were solving had to do with blocking 10,000 IP addresses. This would require maybe 100kb in a hash table, so memory requirements probably aren't the issue.
  - TaikiSan 8y ago
    We didn't spend too much time on the specific of our choice, because we chose to make something more widely usable (this is how radix trees work) than the specific product evolution we did. That being said, we probably were a bit light on details. Going with an hash map was an option, but we feared the ballooning memory footprint when a large number of IPs is blocked, performance outliers (if you're unlucky enough for a lot of blocked IPs/ranges to end up in the same bucket) and we wanted the solution to work as well with IPv6 (where checking each bit takes a bit longer). As for using existing optimal constant time membership tests, we couldn't go with too complex algorithms because we would have to reimplement them and maintain them in each of our agent's language. Radix trees were attractive in this regard because this is a widely available data structure and when it's not, it's fairly easy to implement from scratch. As for range blocking, it's actually very simple: we block the network IP and tag the node as "range". This way, when in the process of looking up an IP we hit a range node, we know we don't have to look any farther. This has the downside of preventing us from processing differently specific parts of the range but it's not a problem in our architecture. Path compression lets you save on nodes, which is good for memory and make looking up an IP faster (because you have to go through fewer nodes before hitting a leaf or a divergence). Fixed length makes using bit mask to compare a value to the node simpler and take care of alignment issues, but we could do without it if we had to.
    - daveFNbuck 8y ago
      Thanks for the explanations, that makes a lot of sense. Is the memory footprint a concern for individual customers, or is this more about reducing the overall footprint across your combined customers?
      - TaikiSan 8y ago
        I'm not sure what you're referring to. The radix tree is stored within the agent context which is running within our user's application. Because of this architecture, making the radix tree larger make the memory footprint of our user's application larger. Keeping it small was thus advantageous for all our customers, although only one ever had a problem due to them.
  - loeg 8y ago
    Path compression just means less pointer dereferences — fewer cache misses and branch mispredictions.
lsllc 8y ago
If the list doesn't change that often, then sort the list and do a binary search for a worst case of O(log n) time.
- viraptor 8y ago
  And save on some cache misses as well.
- loeg 8y ago
  Binary search is cache and branch-predictor inefficient, although certainly not as bad as linear scan (over large datasets).
- darkarmani 8y ago
  If it is only for lookups and is static, why not do a dictionary with perfect hashing? You recalculate the hash each time you need to change the input. (same as the postgres keyword lookup posted last week to HN using perfect hashing)

TaikiSan 8y ago

Absolutely! This would have been a problem when a IP range was blocked however. You would have to test 32 subnets for any given IPv4 (or 128 for IPv6!). We knew it was not ideal, but it had the least downsides at the time.

daveFNbuck 8y ago
This is the question I had the entire time I was reading your post too. Doing set membership testing in constant time is already a solved problem, so why go through the trouble of radix trees when you could use any number of pre-built solutions? I think it would have been a much more interesting and useful read if you had included the reasons that a radix tree is a better solution for your use case than hashing and how you implement range blocking. I also wasn't able to understand the advantage of path compression or why being fixed-length is important.
- dgritsko 8y ago
  Wouldn't the benefit of path compression mean reducing the memory footprint of the data structure? And regarding fixed-length: "This lets us optimize the lookup code." More detail here would be cool but it wasn't really the point of the article.
  - daveFNbuck 8y ago
    My guess is that the path compression speeds up lookups by increasing data locality and reducing the number of fetches needed. Memory footprint probably isn't a big concern for storing 10,000 entries.
- ganonm 8y ago
  If I understand the post correctly, the advantage for e.g. inserting a subnet is that most of the overall IP address value is shared between each IP in the subnet. In a Radix tree, this shared data will only be represented once in the three (since the entire path from root to leaf makes up the entry value). For a hash based solution, yes you get constant time insertion and constant time access, but you need a unique entry of the entire IP for each individual entry. This increases overall memory requirements. If query time became a bottleneck, would you consider putting a Bloom Filter in front of the Radix tree? This would have low memory usage and a low false positive rate. Any positive hits would then do an exact check on the radix tree. So, for say 99% of non-blacklisted IPs, you would get constant time blacklist checks.
  - daveFNbuck 8y ago
    The problem they were solving had to do with blocking 10,000 IP addresses. This would require maybe 100kb in a hash table, so memory requirements probably aren't the issue.
- TaikiSan 8y ago
  We didn't spend too much time on the specific of our choice, because we chose to make something more widely usable (this is how radix trees work) than the specific product evolution we did. That being said, we probably were a bit light on details. Going with an hash map was an option, but we feared the ballooning memory footprint when a large number of IPs is blocked, performance outliers (if you're unlucky enough for a lot of blocked IPs/ranges to end up in the same bucket) and we wanted the solution to work as well with IPv6 (where checking each bit takes a bit longer). As for using existing optimal constant time membership tests, we couldn't go with too complex algorithms because we would have to reimplement them and maintain them in each of our agent's language. Radix trees were attractive in this regard because this is a widely available data structure and when it's not, it's fairly easy to implement from scratch. As for range blocking, it's actually very simple: we block the network IP and tag the node as "range". This way, when in the process of looking up an IP we hit a range node, we know we don't have to look any farther. This has the downside of preventing us from processing differently specific parts of the range but it's not a problem in our architecture. Path compression lets you save on nodes, which is good for memory and make looking up an IP faster (because you have to go through fewer nodes before hitting a leaf or a divergence). Fixed length makes using bit mask to compare a value to the node simpler and take care of alignment issues, but we could do without it if we had to.
  - daveFNbuck 8y ago
    Thanks for the explanations, that makes a lot of sense. Is the memory footprint a concern for individual customers, or is this more about reducing the overall footprint across your combined customers?
    - TaikiSan 8y ago
      I'm not sure what you're referring to. The radix tree is stored within the agent context which is running within our user's application. Because of this architecture, making the radix tree larger make the memory footprint of our user's application larger. Keeping it small was thus advantageous for all our customers, although only one ever had a problem due to them.
- loeg 8y ago
  Path compression just means less pointer dereferences — fewer cache misses and branch mispredictions.

lsllc 8y ago

If the list doesn't change that often, then sort the list and do a binary search for a worst case of O(log n) time.

viraptor 8y ago
And save on some cache misses as well.
loeg 8y ago
Binary search is cache and branch-predictor inefficient, although certainly not as bad as linear scan (over large datasets).
darkarmani 8y ago
If it is only for lookups and is static, why not do a dictionary with perfect hashing? You recalculate the hash each time you need to change the input. (same as the postgres keyword lookup posted last week to HN using perfect hashing)