Howard, thanks much for this information; it really helps and is extremely valuable to us. We're very lucky and grateful to have you here.
More inline ...
On Feb 2, 2008 3:23 AM, Howard Chu <email@example.com> wrote:
Alex Karasulu wrote:
> On Jan 30, 2008 8:00 AM, Emmanuel Lecharny <firstname.lastname@example.org
> <mailto:email@example.com>> wrote:Way back in the OpenLDAP 2.1 days we used hashes for our indexing in back-bdb.
> Those long must be fetched
> quickly, as we will always get an entry by its ID. Using a BTree for
> that is time consuming, as fetching an entry will be done in O(log(N)).
> You're absolutely right a hash would be much better. We don't need to
> sort the ID's.
But we found that B-Trees still performed better, even though index lookups
have nearly zero locality of reference. The problem is with large DBs, the
hash tables grow too large to fit entirely in cache. Once the table grows past
a certain size, you can no longer directly reference the records; there's a
lot of expensive paging in/out that needs to be done. With a B-Tree, the
number of internal pages in the tree is still very small relative to the total
number of data pages, so you get a lot of cache reuse referencing those pages.
So we switched everything to use B-Trees in OpenLDAP 2.2...
Hashing is faster *in theory*, but in practice it loses out.
> We should use a Hash to speedup entries retrieval (of course, at theA good hash function is one that evenly distributes the input keys across the
> risk that the worst case scenario can transform a search operation to
> cost N read, but this is unlikely...). The only point to consider is
> that this ID is incremental, so the hash function must be chosen
entire hash table. This makes hashing extremely cache-unfriendly when doing
sequential traversals of a database, or sequentially bulk-loading.
> As the data are moved frequently, even on read,> this will increase the cost of searching so much that it will kill theYou will find that anything that turns memory read operations into memory
> main advantage of LDAP vs RDBMS. So, yes, we can use Splay trees in
> memory, but we can't store splay trees on disk.
> Yeah I agree. We can use splay trees for caches or for these low
> duplicate count records.
write operations will scale very poorly in a multiprocessor system.
> Yeah they're great ideas. We just need to have a solid SLAMD lab and> start testing these ideas out. I got the machines:Wish I could shake some more time loose right away, this is the really fun
> 9 load injectos
> 1 SLAMD Server
> 1 beefy server for running ApacheDS
> We just need someone to step up and help us manage this environment.
> Any volunteers would be appreciated.