Article seems down. Here is a google cached version:
http://webcache.googleusercontent.com/search?q=cache:http://...
How we store 400M phone numbers with fast lookup
51–59 of 59 posts
Re: How we store 400M phone numbers with fast lookup
#52Earlier quoted context omitted.
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,…
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.
Re: How we store 400M phone numbers with fast lookup
#53Earlier 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,…
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 hardwa…
Yup, there's certainly a balance to be achieved.
Re: How we store 400M phone numbers with fast lookup
#54Yeah, or you could just, like, use indexes?
Remind me not to hire these guys.
Re: How we store 400M phone numbers with fast lookup
#55Earlier 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.
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...
Our solution maintains the data in a simpler scheme because keeping the data in a maintainable format is important aspect when the data is ever changing - every couple of days millions of people update their preferences and we need to be able to apply these changes. When choosing a single data structure for all the numbers, we need to optimize for space or for faster inserts/updates. Our solution is a trade-off between these options.
Re: How we store 400M phone numbers with fast lookup
#56Earlier quoted context omitted.
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...
Our solution maintains the data in a simpler scheme because keeping the data in a maintainable format is important aspect when the data is ever changing - every couple of days millions of people update their preferences and we need to be able to apply these changes. When choosing a single data structure for all the numbers, we need to optimize for space or for faster inserts/updates. Our solution is a trade-off betwe…
[deleted]
Re: How we store 400M phone numbers with fast lookup
#57Earlier quoted context omitted.
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...
Our solution maintains the data in a simpler scheme because keeping the data in a maintainable format is important aspect when the data is ever changing - every couple of days millions of people update their preferences and we need to be able to apply these changes. When choosing a single data structure for all the numbers, we need to optimize for space or for faster inserts/updates. Our solution is a trade-off betwe…
A hash table is more than compact enough. It should work fine even at high load factors (80%/90%) given a decent hash scheme (eg. Robin Hood hashing) which means you need only 4GB memory. It's random access and on average should have one cache miss per lookup. Updating is rather trivial.
Re: How we store 400M phone numbers with fast lookup
#58Earlier quoted context omitted.
Our solution maintains the data in a simpler scheme because keeping the data in a maintainable format is important aspect when the data is ever changing - every couple of days millions of people update their preferences and we need to be able to apply these changes. When choosing a single data structure for all the numbers, we need to optimize for space or for faster inserts/updates. Our solution is a trade-off betwe…
A hash table is more than compact enough. It should work fine even at high load factors (80%/90%) given a decent hash scheme (eg. Robin Hood hashing) which means you need only 4GB memory. It's random access and on average should have one cache miss per lookup. Updating is rather trivial.
Sounds promising. Little bit concerned on the computational cost of hashing function. Gotta explore this option!
Re: How we store 400M phone numbers with fast lookup
#59Earlier quoted context omitted.
A hash table is more than compact enough. It should work fine even at high load factors (80%/90%) given a decent hash scheme (eg. Robin Hood hashing) which means you need only 4GB memory. It's random access and on average should have one cache miss per lookup. Updating is rather trivial.
Sounds promising. Little bit concerned on the computational cost of hashing function. Gotta explore this option!
I wouldn't be worried about hashing, either, given you effectively want to hash a 34 bit integer to a ⌈log 4e8⌉ = 29 bit integer.
An easy way is to take a 32 to 32 bit hash (eg. http://stackoverflow.com/a/12996028/1763356), calculate
hash(top 32 bits) ^ hash(bottom 32 bits)