consider libjudy for a cache backend
In reading more about the lmdb cache backend I remembered something I read about a while back, libjudy. Here's is an introduction:
http://judy.sourceforge.net/doc/10minutes.htm
I have no idea if it's appropriate for your use case, but thought it was worth letting you know. Available in Debian/Fedora/CentOS/etc. Thanks
Edit: This wikipedia article has some more info/critique