> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is intereste

> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is interested (and this may not be what OP had in mind): In trading memory gains with computation, this is how I squeezed ~4M entries in less than 30 MiB: 1. Compress (reversed) individual entries using a dictionary or entropy encoder. I experimented with Shoco [0], Femto [1], and a modified LZ78 [2]. 2. Create a bloom filter for membership checks, [3] or any probabilistic structure for that matter, like the xor-filters [4]. This prevents expensive but unnecessary lookups. 3. Insert the compressed (reversed: google.com -> com.google) entries into a radix-tree [5]. You could use a directed-acyclic graph (DAG), if you don't need to store key-value pairs. 4. Compact [6][7] the radix-tree [8] (compacting a DAG might be super complicated). 5. On every search: 5a. Compress (reversed) incoming query (i.e. domain-name). 5b. Check the bloom filter. 5c. Traverse the radix-tree, if necessary. 5d. Cache an eligible entry in a LFU [9] or possibly, using any other suitable algorithm inspired from Linux's page replacement implementations [10]. 6. Strive for zero-allocation and zero-gc. --- [0] https://news.ycombinator.com/item?id=10060018 https://news.ycombinator.com/item?id=10060018 [1] https://github.com/gtoubassi/femtozip/wiki/How-femtozip-works https://github.com/gtoubassi/femtozip/wiki/How-femtozip-work... [2] https://en.wikipedia.org/wiki/LZ78 https://en.wikipedia.org/wiki/LZ78 [3] https://news.ycombinator.com/item?id=12231623 https://news.ycombinator.com/item?id=12231623 [4] https://news.ycombinator.com/item?id=21840821 https://news.ycombinator.com/item?id=21840821 [5] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin... [6] https://news.ycombinator.com/item?id=22544718 https://news.ycombinator.com/item?id=22544718 [7] https://www.youtube-nocookie.com/embed/3Y2weLDiUWw https://www.youtube-nocookie.com/embed/3Y2weLDiUWw [8] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619 [9] https://github.com/ronomon/hash-table/blob/master/README.md https://github.com/ronomon/hash-table/blob/master/README.md [10] https://en.wikipedia.org/wiki/Page_replacement_algorithm https://en.wikipedia.org/wiki/Page_replacement_algorithm