My intuition is that a Radix tree trie would make a lot more sense and is more maintainable than such a hack.
How we store 400M phone numbers with fast lookup
41–50 of 59 posts
Re: How we store 400M phone numbers with fast lookup
#42Their 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…
> 8 bytes * 400 million phone numbers I get 3.2GB, which fits in RAM.
So yes, I guess, but why hit the disk at all? I'd probably just sort the data and do a binary search.
Re: How we store 400M phone numbers with fast lookup
#43Their 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…
> 8 bytes * 400 million phone numbers I get 3.2GB, which fits in RAM. So yes, I guess, but why hit the disk at all? I'd probably just sort the data and do a binary search.
Good catch. I've recently resorted to using wolfram alpha for this sort of math, since it does an excellent job of keeping units straight:
Re: How we store 400M phone numbers with fast lookup
#44Did you look at Redis or strategies like bit stream and bloom filters as a possible solution ?
Re: How we store 400M phone numbers with fast lookup
#45I had interned in a similar company, they had this sorted out way back then, using bloom filters. This is the github link if anyone is interested: https://github.com/mobmewireless/fast-filter
Re: How we store 400M phone numbers with fast lookup
#46Their 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…
Absolute laziest approach, 10 billion numbers entries laid out sequentially. At 2 bytes for each entry, that's only 20GB. That's less than I can fit in some fairly cheap consumer box.
Would that work? Just an array in C. Or are there interesting performance problems I'd be likely to run into?
Re: How we store 400M phone numbers with fast lookup
#47Earlier 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...
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.
Re: How we store 400M phone numbers with fast lookup
#48Earlier 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.
Exactly: 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.Re: How we store 400M phone numbers with fast lookup
#49Their 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…
> 8 bytes * 400 million phone numbers I get 3.2GB, which fits in RAM. So yes, I guess, but why hit the disk at all? I'd probably just sort the data and do a binary search.
I must be sleep deprived. 1024^3 = gigabytes, not terabytes. Wow, then they've definitely over-engineered it, and disk isn't even necessary in the event of a 10-fold increase in the database size. Tries, search trees, or properly sized hash tables on phone number prefixes should be plenty fast and the whole thing can fit in RAM on a modern laptop...
Re: How we store 400M phone numbers with fast lookup
#50Earlier quoted context omitted.
> 8 bytes * 400 million phone numbers I get 3.2GB, which fits in RAM. So yes, I guess, but why hit the disk at all? I'd probably just sort the data and do a binary search.
Good catch. I've recently resorted to using wolfram alpha for this sort of math, since it does an excellent job of keeping units straight: http://www.wolframalpha.com/input/?i=64+bits+*+400+million
[deleted]