How we store 400M phone numbers with fast lookup • Hacker News Board

Re: How we store 400M phone numbers with fast lookup

#11

Post by wtallis » Sun, Jul 19, 2015, 6:11 PM UTC

tacos wrote: post #7

nly wrote: post #3

Earlier quoted context omitted.

> 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?

Exactly. My response to the headline was "Um... using ten lines of C and $44 worth of RAM?"

Or one line of C and $500 of RAM (assuming we're going to spring for registered/ECC memory).

Re: How we store 400M phone numbers with fast lookup

#12

Post by waterside81 » Sun, Jul 19, 2015, 8:05 PM UTC

fasteo wrote: post #4

We are using a constant database for a similar use-case (MNP database), albeit much smaller, around 15 million phone numbers. It requires almost no RAM and you update the database as a whole with no downtime. [1] https://en.wikipedia.org/wiki/Cdb_(software)

For the gophers in the crowd, a CDB implementation in pure Go. Memory mapped, thread safe.

https://github.com/repustate/go-cdb

Re: How we store 400M phone numbers with fast lookup

#13

Post by fleitz » Sun, Jul 19, 2015, 8:06 PM UTC

vidarh wrote: post #10

nly wrote: post #3

Earlier quoted context omitted.

> 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?

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...

Re: How we store 400M phone numbers with fast lookup

#14

Post by [deleted] » Sun, Jul 19, 2015, 8:19 PM UTC

[deleted]

Re: How we store 400M phone numbers with fast lookup

#15

Post by donarb » Sun, Jul 19, 2015, 9:17 PM UTC

Their basic premise is all wrong. The list of people that actually want spam phone calls would be very short and is a faster search target.

Re: How we store 400M phone numbers with fast lookup

#16

Post by yason » Sun, Jul 19, 2015, 9:23 PM UTC

tacos wrote: post #7

nly wrote: post #3

Earlier quoted context omitted.

> 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?

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.

Re: How we store 400M phone numbers with fast lookup

#17

Post by fencepost » Sun, Jul 19, 2015, 9:27 PM UTC

The thing that strikes me is that while the data being searched for has been optimized down to 2 bytes of bitfields, the same hasn't been done with the phone numbers - area codes in India appear to be variable-length (2, 3, ? digits) with that length being part of the 10 digits, and presumably mobile numbers are handled similarly either with their own area codes or overlapping. Breaking the data by area code would allow the elimination of significant chunks of the total possible address space, and further separating (as they do) into dense and sparse would further reduce the requirements (since tries, skip-lists, etc. have their own overhead).

It comes down to this: while the Indian phone system could in theory allow 10 billion phone numbers, there are not in fact 10 billion legally-allocatable phone numbers and the rules in place likely effectively reduce the legally-allocatable number to somewhere between 1-3 billion numbers. Dividing based on those rules may both reduce the problem to something requiring less engineering time and simiplify possible marketing-related factors (e.g. selling access/systems targeted only to specific area codes).

Re: How we store 400M phone numbers with fast lookup

#18

Post by d_e_solomon » Sun, Jul 19, 2015, 10:02 PM UTC

Thanks for posting this article. Would this be a good use case for a bloom filter?

Re: How we store 400M phone numbers with fast lookup

#19

Post by alexeyshurygin » Sun, Jul 19, 2015, 10:06 PM UTC

Does it worth mentioning? Straightforward approach of storing numbers in a hash map in memory solves the problem. This may require say 40 Gb of ram w/o ANY optimizations.

Re: How we store 400M phone numbers with fast lookup

#20

Post by fleitz » Sun, Jul 19, 2015, 10:11 PM UTC

yason wrote: post #16

tacos wrote: post #7

Earlier quoted context omitted.

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.