7 ms·

Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.

nly 11y ago
> Unfortunately, 10 digits won't fit in 32 bits and 5 * 400 MB for storing number is not a very happy situation and it is NOT readily searchable. Why is 7 bytes (2b prefs + 5b number) x 400M = ~2.4GB of RAM not good enough?
- tacos 11y ago
  Exactly. My response to the headline was "Um... using ten lines of C and $44 worth of RAM?"
  - wtallis 11y ago
    Or one line of C and $500 of RAM (assuming we're going to spring for registered/ECC memory).
  - yason 11y ago
    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.
    - fleitz 11y ago
      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.
      - wtallis 11y ago
        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.
        nulltype 11y ago
        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?
        fleitz 11y ago
        Exactly: https://github.com/twitter/fatcache https://github.com/twitter/fatcache 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.
      - icebraining 11y ago
        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.
        fleitz 11y ago
        Yup, there's certainly a balance to be achieved.
- vidarh 11y ago
  Now do fast lookups. It needs an index, which is what their post is about.
  - fleitz 11y ago
    It doesn't need an index, it just needs to be sorted... Then you can do fast lookups...
    - latch 11y ago
      not to mention that it's so little memory that you can treat the live version as read-only and swap in new versions.
    - vidarh 11y ago
      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.

nly 11y ago

> Unfortunately, 10 digits won't fit in 32 bits and 5 * 400 MB for storing number is not a very happy situation and it is NOT readily searchable. Why is 7 bytes (2b prefs + 5b number) x 400M = ~2.4GB of RAM not good enough?

tacos 11y ago
Exactly. My response to the headline was "Um... using ten lines of C and $44 worth of RAM?"
- wtallis 11y ago
  Or one line of C and $500 of RAM (assuming we're going to spring for registered/ECC memory).
- yason 11y ago
  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.
  - fleitz 11y ago
    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.
    - wtallis 11y ago
      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.
      - nulltype 11y ago
        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?
      - fleitz 11y ago
        Exactly: https://github.com/twitter/fatcache https://github.com/twitter/fatcache 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.
    - icebraining 11y ago
      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.
      - fleitz 11y ago
        Yup, there's certainly a balance to be achieved.
vidarh 11y ago
Now do fast lookups. It needs an index, which is what their post is about.
- fleitz 11y ago
  It doesn't need an index, it just needs to be sorted... Then you can do fast lookups...
  - latch 11y ago
    not to mention that it's so little memory that you can treat the live version as read-only and swap in new versions.
  - vidarh 11y ago
    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.