Emmanuel Lecharny wrote:
That sounds interesting. Now, you may consider another idea to be totally insane, but instead of writing your own DB engine implementation, what about relying on the FS ? We discussed about this idea recently in the Apache Directory community (we have pretty much the same concern : 3 level of cache is just over killing). So if you take Window$ out of the picture (and even if you keep it in the full picture), many existing linux/unix FS are already implemented using a BTree (EXT3/4, BTRFS, even NTFS !). What about using this underlying FS to store entries directly, instead of building a special file which will be a intermediate layer ? The main issue will be to manage indexes, but that should not be a real problem. So every entry will be stored as a single file (could be in LDIF format :)
So far, this is just a discussion we are having, but that might worth a try at some point...
Does it sound insane ?
In fact we already have a back-ldif which does exactly this, but it's not intended for real use. It was only written to serve as a vehicle for back-config. (I.e., we wanted a simple, zero-config persistent store that could still behave like an LDAP database in very specifically defined use cases.) I'm pretty sure we've documented that it's not recommended for general purpose use, although some folks seem to want to misuse it that way regardless.
One of the main downsides - any such backend requires a couple system calls to access any given entry, and that generally means at least a few context switches. No matter how wonderfully efficient the FS itself is, anything that forces you to switch context between user mode and kernel mode for every entry is always a loss.
And no matter how wonderful these FSs are, to my knowledge none of them are using B-link trees, which means they all still have higher lock contention than necessary for reads, inserts, and deletes. In fact the only open B-link implementation I'm aware of is written in Java (bonus for you guys!), and some of the thornier issues of B-link management have only been solved in the past couple years. When I first started looking into them a few years ago the issue of Delete rebalancing hadn't actually been solved yet. This is all pretty new stuff. (In the original paper, the authors described how to do searches and inserts without any lock-coupling, which is a huge concurrency win. They had no solution for deletes though, and just allowed deleted nodes to accumulate in the tree.)
For a C implementation I'd try to re-use as much as possible of the existing BerkeleyDB code since it's quite mature and provides a lot of features we already like/want/need...
Anton Bobrov wrote:
i did try a dummy prototype awhile back and it doesnt perform very well. you end up incurring too much overhead and it doesnt pay off even when underlaying FS data is 100% cached. plus you can never truly control what happens with FS cache, you can size and influence it in some ways but you cannot guarantee your operation will hit cached data which does make it difficult to deliver predictable response times, in other words you gonna have to accept I/O hits and widen your response window to the worst case scenario for at least some %tage of operations. this can be optimized and made more predictable on a black box where you control the entire machine but moot otherwise. the FS was ZFS and just for the record the perf didnt suck per se but didnt quite match traditional db backends perf [especially with entry caches] either. i dont have slamd comparison data anymore to show you unfortunately.
Also true, which is one of the reasons I wasn't too thrilled with Jong's original line of research here; it would degrade slapd's performance for the benefit of anything else on the box when other processes' resource demands increased. But in the face of a heavily overcommitted machine, all bets are off and you might as well go down gracefully instead of getting killed by OOM or somesuch.