7:25 p.m.
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.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/