Hacker News Reader

Comment by mro_name | Hacker News Reader

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

(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/, 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://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html

> 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

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.

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/

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

Reply on news.ycombinator.com