Hacker News Reader

Comment by gh02t | Hacker News Reader

So I've always been curious, does anybody have a writeup of how DNS servers like unbound etc are able to handle evaluating these massive blocklists? Like the algorithms and data structures they use to evaluate queries against these lists efficiently. My pfsense+pfblocker unbound instance has something like 400K hosts blocked and I've always been amazed that it doesn't even break a sweat scanning that many hosts with every query.

View on HN

> My pfsense+pfblocker unbound instance has something like 400K hosts blocked

But it is not 400k hosts to search:

    com
        facebook
                 www
                 ad
        google
               ad
               ads
               notadswepromise
        googletagmanager
                         tags
                         ads

to block ad.facebook.com you only need to scan 10-100k of .com domains in your block list and only a couple of records in facebook.com. Don't forget, DNS is a hierarchical system. And we, humans, actually record, use and remember all the DNS records in the wrong, reverse direction ;-)

> 400K hosts

I bet 30% of those hosts are don't resolve anymore and another 30% resolve to domain parking/404 hosts.

Eg: see my comment about "TOP 10M SITES"

https://news.ycombinator.com/item?id=33150554

I bet 30% of those hosts are don't resolve anymore

I've seen some evidence of this. I periodically dig all the blocked domains and noticed that some of them come and go so I assume people cycle them in and out to evade blocking. A handful of the domains just change the A record so I just block the apex domain which makes it a little harder to keep the block lists optimized but does reduce the size a little.

I should add that blocking the apex of some domains includes risk of dropping legit traffic but if I see more than {n} badware domains on the apex, I write it off as compromised or at very least poorly implemented and poorly secured.

I suspect parent meant the way the list is processed and how the structure resides in memory.

We'd optimally want, e.g., aaa.ai to resolve as fast as zzz.zx. If we just loaded the file for every query and ran down the list linearly we'd probably see a large disparity with the former being much quicker than the latter.

So, the question would be: how is it done in an efficient way? Is it loaded into a btree, is each domain broken into various parts, are certain domains prioritized, threading, compression?

Plus, there's the queries for dns updates, and how the results get integrated.

Some combination of tries, B-trees and Bloom filters would get you most of the way there.

Here's Tony Finch's discussion of the data structures he's working on for ISC's BIND:

https://dotat.at/prog/qp/README.html

https://news.ycombinator.com/item?id=20148457

Not sure how out of date that is

Reply on news.ycombinator.com