Do you know of a C dictionary that supports COW transactions?

Question

I'm looking for a key -> value dictionary library written in C that supports a theoretically unlimited number of cheap transactions.

I'd like to have one dictionary in memory, with hundreds of threads starting transactions, possibly modifying the dictionary, ending (completing) the transaction or potentially aborting the transaction. Only 50% of the time will these threads actually modify the dictionary.

Most dictionary transaction implementations that I've seen copy always, instead of copying on write, whenever a transaction is started. Given the expected size (> 1GB) of the dictionary, I'm hoping to find something that COWs only when something is actually changed during a transaction. I'm also hoping for something that is packaged by most major GNU/Linux distributions.

Any suggestions or links are very much appreciated.

Answer 1

SQLite3 is transactional and can exist entirely in memory. Its not as cheap as some might like when it comes to transactions, but not all that expensive either. A quick mlock() / mlockall() keeps the DB from being paged out, YMMV with posix_madvise(). Its not an out of the box solution, but not too difficult to adapt.

BDB is another option, which Oracle currently markets.

SQLite3 fit my needs (almost) perfectly. Given that I earned the Tumbleweed badge by asking this question, the least I could do is answer it.

Answer 2

Isn't SQLite overkill for basic dictionary needs? Typically if you're not going to be executing queries, the overhead of a database is unnecessary.

BDB is definitely great, I've been meaning to incorporate it into a number of my projects for a while, and definitely sounds like you could benefit from its performance boosts.

The easiest solution would probably be to create a wrapper class (i.e. COWString) which will implement the copy-on-write behavior, then create a stl::map or hash_map of the wrapper object. That way, you're abstracting the COW logic from the container logic, which will also free you from having to write your own container class and the huge complexities therein.