Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
Because the interesting part of the effort is doing it fast in anticipation of translating the optimization tricks to cases where you can't just go buy more RAM anymore. A lot of problems can be "solved" with current hardware because accesses or comparisons or whatnot become ridiculously cheap but that's not what computer science is about.
This is one of the biggest problems I run into in 'software engineering', people building way to complex systems because they are 'interesting' rather than buying $50 of RAM and being done with it, and then poo-poo'ing systems that cost $50 and work.
Querying a DNC list is not a problem in which you will ever not be able to buy more RAM, it's trivially parallel, if for some reason DNC lists ever outpace Moore's law, just buy another system.
To be fair to the authors at least they didn't do something ridiculous like build a 100 note cassandra cluster.
This is one of the biggest problems I run into in 'software engineering', people building way to complex systems because they are 'interesting' rather than buying $50 of RAM and being done with it, and then poo-poo'ing systems that cost $50 and work.
Funny; one of the most common complaints about the software industry (common on HN) is that people use inefficient languages or algorithms and then waste too much hardware.
And realistically, there's nothing you can do with phone numbers that even needs the full speed of RAM. A fast SSD can do enough random reads to load the entire database in under 20 minutes, and nobody actually needs to know the status of all 400M numbers in the same 20 minutes because they can't all be dialed that quickly.
A single fatcache can do close to 100K set/sec for 100 bytes item sizes.
A single fatcache can do close to 4.5K get/sec for 100 byte item sizes.
All the 8 fatcache instances in aggregate do 32K get/sec to a single 600 GB SSD.
Yeah, looking at the graph in the article is really weird. Wait, you can query 10k phone numbers per second with a single crappy linode machine, why does it need to be faster than that?
Comments
Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
Why is 7 bytes (2b prefs + 5b number) x 400M = ~2.4GB of RAM not good enough?
Exactly. My response to the headline was "Um... using ten lines of C and $44 worth of RAM?"
Because the interesting part of the effort is doing it fast in anticipation of translating the optimization tricks to cases where you can't just go buy more RAM anymore. A lot of problems can be "solved" with current hardware because accesses or comparisons or whatnot become ridiculously cheap but that's not what computer science is about.
This is one of the biggest problems I run into in 'software engineering', people building way to complex systems because they are 'interesting' rather than buying $50 of RAM and being done with it, and then poo-poo'ing systems that cost $50 and work.
Querying a DNC list is not a problem in which you will ever not be able to buy more RAM, it's trivially parallel, if for some reason DNC lists ever outpace Moore's law, just buy another system.
To be fair to the authors at least they didn't do something ridiculous like build a 100 note cassandra cluster.
This is one of the biggest problems I run into in 'software engineering', people building way to complex systems because they are 'interesting' rather than buying $50 of RAM and being done with it, and then poo-poo'ing systems that cost $50 and work.
Funny; one of the most common complaints about the software industry (common on HN) is that people use inefficient languages or algorithms and then waste too much hardware.
Yup, there's certainly a balance to be achieved.
And realistically, there's nothing you can do with phone numbers that even needs the full speed of RAM. A fast SSD can do enough random reads to load the entire database in under 20 minutes, and nobody actually needs to know the status of all 400M numbers in the same 20 minutes because they can't all be dialed that quickly.
Exactly: https://github.com/twitter/fatcache
Yeah, looking at the graph in the article is really weird. Wait, you can query 10k phone numbers per second with a single crappy linode machine, why does it need to be faster than that?
Or one line of C and $500 of RAM (assuming we're going to spring for registered/ECC memory).
Now do fast lookups. It needs an index, which is what their post is about.
It doesn't need an index, it just needs to be sorted...
Then you can do fast lookups...
You still won't get fast lookups without an index.
And if you've first sorted it, you can save space with an index in the form of a trie or limited skip list by eliminating common prefixes.
not to mention that it's so little memory that you can treat the live version as read-only and swap in new versions.