Re:How we store 400M phone numbers with fast lookup
by vidarh on Sunday July 19, 2015 @01:36PM
(#9911997)
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
by waterside81 on Sunday July 19, 2015 @04:05PM
(#9912628)
For the gophers in the crowd, a CDB implementation in pure Go. Memory mapped, thread safe.
[1] https://en.wikipedia.org/wiki/Cdb_(software)