Alex Karasulu wrote:
On Jan 30, 2008 8:00 AM, Emmanuel Lecharny <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
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.
Way back in the OpenLDAP 2.1 days we used hashes for our indexing in back-bdb.
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 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
carefully.
A good hash function is one that evenly distributes the input keys across the
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 the
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.
You will find that anything that turns memory read operations into memory
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:
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.
Wish I could shake some more time loose right away, this is the really fun
part. ;)
--
-- Howard Chu
Chief Architect, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
