See also tinycdb, a public domain reimplementation http://www.corpit.ru/mjt/tinycdb.html
Cdb: a fast, reliable, simple package for creating, reading constant databases
21–30 of 43 posts
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#22Weird side-note, when using CDB's from Perl, do not use tie, its painfully unperformant (realized this the hard way)
CDB isn't really a DBM.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#23CDB is awesome for its use case - slow changing, read-heavy workflows that are tolerant of stale data. One limitation of the original implementation is the use of 32-bit keys for addressing, which limit the addressable size to 4gb. There are 64 bit modifications, but I have not used them. Does anyone have an opinion on any of the 64-bit implementations?
Supposedly https://github.com/gstrauss/mcdb is quite good.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#24CDB is one of my favorite data structures. When a student wants to learn about databases, I get them to implement cdb. It's easy to implement and really demonstrates some good system engineering tradeoffs.
Any links to theory behind cdb?
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#25I'm put in mind of all the things that take up the most space on a minimal Ubuntu installation: charmaps, mime types, tzdata, geoip, etc. Seems like all of these could do with being packed into a tight, read-only K/V store.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#26That's cool. But I feel like I'll totally forget about it and lose reference to this (in case I have future interest). Where's a github mirror? A google search reveals some entries from the language implementations. Go: https://github.com/jbarham/go-cdb Java: https://github.com/malyn/sg-cdb Haskell: https://github.com/adamsmasher/hs-cdb
Most open source development takes place outside of github. It is a very valley-centric thing. You'll find a ton of life changing stuff on SourceForge and random FTP sites.
I'd be really interested to see statistics on this. I don't work in Silicon Valley, and almost all of the stuff people around me are publishing is on GitHub.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#27CDB is awesome for its use case - slow changing, read-heavy workflows that are tolerant of stale data. One limitation of the original implementation is the use of 32-bit keys for addressing, which limit the addressable size to 4gb. There are 64 bit modifications, but I have not used them. Does anyone have an opinion on any of the 64-bit implementations?
An alternative to using 64-bit pointers would be to use something like the JVM's "compressed OOPs":
https://wikis.oracle.com/display/HotSpotInternals/Compressed...
Where the pointers are notionally 32+k bits long, but the bottom k bits are always zero, so they can be stored in 32 bits. This would mean that records always have to be aligned to a 2^k-byte boundary. If the data has some natural alignment anyway, this could be arranged so as to not involve wasted space, and even if it doesn't, for large keys and/or values, the amount of wasted space would be relatively small.
Alternatively, there was a way to reliably locate the start of a record when scanning through data, the records could be packed without padding, and the 2^k-aligned pointers could simply be approximate, pointing to somewhere in the 2^k bytes before the start of the record. Retrieval would involve following the pointer, then scanning forward to find the actual record. This would be a bit sketchy, but something a bit like this is done in ATM:
http://en.wikipedia.org/wiki/CRC-based_framing
CDB doesn't include CRCs. However, you could think up various schemes to identify records based on what you know about the record format, the key you're looking for, and its hash. It's probably not worth the effort!
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#28CDB is one of my favorite data structures. When a student wants to learn about databases, I get them to implement cdb. It's easy to implement and really demonstrates some good system engineering tradeoffs.
Any links to theory behind cdb?
I'd be particularly interested to know why there are 256 hashtables, rather than one, or some other number. I don't think i've seen this hybrid trie-hashtable before.
I wonder if there's any mileage in using a perfect hash function to build a database like this. It seems suited to the operating model of being slow to build but fast to access.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#29That's cool. But I feel like I'll totally forget about it and lose reference to this (in case I have future interest). Where's a github mirror? A google search reveals some entries from the language implementations. Go: https://github.com/jbarham/go-cdb Java: https://github.com/malyn/sg-cdb Haskell: https://github.com/adamsmasher/hs-cdb
Most open source development takes place outside of github. It is a very valley-centric thing. You'll find a ton of life changing stuff on SourceForge and random FTP sites.
Notice cordite said a Github mirror, not the Github mirror. You don't need to have your main development happen on Github to have a mirror there, just someone mirroring from the main server.
See, for example, the Linux kernel.
Re: Cdb: a fast, reliable, simple package for creating, reading constant databases
#30We know that a number of very high-traffic, high-volume startups in Silicon Valley have gone great distances with CDB... OpenDNS included. :-)
[deleted]