Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How we store 400M phone numbers with fast lookup

sparktg.com

Post reply on HN
Print view View original

31–40 of 59 posts

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

#31

Post by nulltype »

wtallis wrote: post #30
fleitz wrote: post #20

Earlier quoted context omitted.

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,…

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.

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?

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

#34

Post by idorosen »

Their solution seems over-engineered for the scale of data they're concerned with.

A 10 digit phone number can be encoded in 34 bits. Supposing they used 64 bit wide fields to store the key and target data, that leaves 30 bits (more than their 2 bytes) to play with for flags or whatever target data. To store the whole dataset in a trie or tree-like structure on disk in this model they would need 8 bytes * 400 million phone numbers The data just isn't that big by today's standards.

Since false negatives are not possible for a properly implemented Bloom filter, using a Bloom filter in front of this on-disk approach would make it even faster for the negative case, since the disk would only be hit for positive or false positive cases, the latter of which should be relatively rare.

EDIT: It might be even simpler/better/faster than a trie/tree to just store the data indexed by some hash function (even just prefix bucketing) and then sequentially scan the collision list for that prefix hash for matches to the target number, which would take advantage of the much better sequential read throughput for most commodity HDDs/SSDs so that only one random read is necessary.

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

#36

Post by latch »

fleitz wrote: post #13
vidarh wrote: post #10

Earlier quoted context omitted.

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

not to mention that it's so little memory that you can treat the live version as read-only and swap in new versions.

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

#39

Post by maerF0x0 »

20kleagues wrote: post #38
donarb wrote: post #15

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.

If it is opt-out, then won't they have just the list of people who don't want phone calls?

assuming a saturated numberspace, 400M numbers is just 5% of all possible #s . I doubt that the exceptions (911-xxx-xxxx) reduce the number enough to make a whitelist a better choice.
Post reply on HN