5 ms·

create cdbs https://news.ycombinator.com/item?id=32648589 https://news.ycombinator.com/item?id=32648589

genericlemon24 4y ago
(replying with more details, because I think it's pretty cool, and I'll definitely try this out) The linked item is to https://blog.mro.name/2022/08/pwned-diy/ https://blog.mro.name/2022/08/pwned-diy/, where the author converts the passwords list to a CDB (Constant DataBase) file, a simple, fast lookup database format created by D. J. Bernstein. https://cr.yp.to/cdb.html https://cr.yp.to/cdb.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html
wolfgang42 4y ago
Having recently been digging into the CDB format[1], this was exactly my first thought as well. `tinycdb` is extremely fast at creating an index, and most successful lookups take only two disk seeks (failed lookups need only one), very close to the optimal possible lookup performance on this problem. [1]: https://search.feep.dev/blog/post/2022-12-03-cdb-file-format https://search.feep.dev/blog/post/2022-12-03-cdb-file-format
ciupicri 4y ago
> Positions, lengths, and hash values are 32-bit quantities, stored in little-endian form in 4 bytes. Thus a cdb must fit into 4 gigabytes. Source: https://cr.yp.to/cdb/cdb.txt https://cr.yp.to/cdb/cdb.txt
- mro_name 4y ago
  You're a bit hasty, young padawan. Do you insinuate this has never been tried while you don't even take a glimpse at it and see how it's done? What use is it linking the cdb docs? The article has it all in context if you bother reading. The dataset is turned to 16 cdbs to be precise in case you wonder how 37GB fit into the 4GB cdb size limit.
- mhuffman 4y ago
  There is a more modern rewrite that does away with the 4 gigabyte limit of the original[1]. I am not sure if the performance characteristics are the same. [1]https://github.com/gstrauss/mcdb/ https://github.com/gstrauss/mcdb/

(replying with more details, because I think it's pretty cool, and I'll definitely try this out) The linked item is to https://blog.mro.name/2022/08/pwned-diy/ https://blog.mro.name/2022/08/pwned-diy/, where the author converts the passwords list to a CDB (Constant DataBase) file, a simple, fast lookup database format created by D. J. Bernstein. https://cr.yp.to/cdb.html https://cr.yp.to/cdb.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html

wolfgang42 4y ago

Having recently been digging into the CDB format[1], this was exactly my first thought as well. `tinycdb` is extremely fast at creating an index, and most successful lookups take only two disk seeks (failed lookups need only one), very close to the optimal possible lookup performance on this problem. [1]: https://search.feep.dev/blog/post/2022-12-03-cdb-file-format https://search.feep.dev/blog/post/2022-12-03-cdb-file-format

ciupicri 4y ago

> Positions, lengths, and hash values are 32-bit quantities, stored in little-endian form in 4 bytes. Thus a cdb must fit into 4 gigabytes. Source: https://cr.yp.to/cdb/cdb.txt https://cr.yp.to/cdb/cdb.txt

mro_name 4y ago
You're a bit hasty, young padawan. Do you insinuate this has never been tried while you don't even take a glimpse at it and see how it's done? What use is it linking the cdb docs? The article has it all in context if you bother reading. The dataset is turned to 16 cdbs to be precise in case you wonder how 37GB fit into the 4GB cdb size limit.
mhuffman 4y ago
There is a more modern rewrite that does away with the 4 gigabyte limit of the original[1]. I am not sure if the performance characteristics are the same. [1]https://github.com/gstrauss/mcdb/ https://github.com/gstrauss/mcdb/