How we store 400M phone numbers with fast lookup
1–10 of 59 posts
Re: How we store 400M phone numbers with fast lookup
#2Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
Re: How we store 400M phone numbers with fast lookup
#3Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
> 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?
Re: How we store 400M phone numbers with fast lookup
#4We 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.
Re: How we store 400M phone numbers with fast lookup
#5We 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)
I'm sure that works great for 15m. (EDIT: To be clear, I love CDB, and I'm not being sarcastic - for 15m it's probably perfectly fine; it's just space inefficient for large datasets where the combined key+value lengths are very low)
But even if we ignore the hash table pointer tables which can be made arbitrarily small at the cost of probing a higher number of entries on average before finding the right key (but in reality you'd want them to be fairly large), the minimum space used per entry is [1]:
8 bytes for the length of the key and length of the value + 5 bytes for the key + 2 bytes for the value, so 15 bytes per number, or 6GB (EDIT: fixed numbers to account for BCD encoding of number). Which means you'd need to switch to one of the (non-standard) 64-bit CDB-inspired formats, as CDB itself can only handle 4GB data files.
[1] CDB format: http://cr.yp.to/cdb/cdb.txt
Re: How we store 400M phone numbers with fast lookup
#6This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient.
The described approach doesn't seem bad, though it's a bit amusing to see this described as if it's not a very well trodden area of computer science.
[1] https://en.wikipedia.org/wiki/Trie
Re: How we store 400M phone numbers with fast lookup
#7Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
> 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?"
Re: How we store 400M phone numbers with fast lookup
#8This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient. The described approach doesn't seem bad , though it's a bit amusing to see this described as if it's not a very well trodden area of computer science. [1] http…
Depending on exactly how they're implemented, tries can give you unacceptable numbers of random disk seeks / uncached memory lookups per read.
Re: How we store 400M phone numbers with fast lookup
#9This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient. The described approach doesn't seem bad , though it's a bit amusing to see this described as if it's not a very well trodden area of computer science. [1] http…
Depending on exactly how they're implemented, tries can give you unacceptable numbers of random disk seeks / uncached memory lookups per read.
They can, but they certainly don't have to, especially not for a dataset like this which is small enough to re-generate offline with data suitably clustered. And certainly no reason why it'd be worse than the describe approach, which isn't really all that conceptually different. What the article described isn't necessarily bad, just unnecessarily ad-hoc when there's plenty of suitable algorithms with well understood tradeoffs and implementations.
Re: How we store 400M phone numbers with fast lookup
#10Earlier submission tanked on HN and the link didn't work, resubmitting with lookup timings added. Hopefully, readers will find it interesting this time.
> 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.