There appears to be a long-standing problem with back-bdb and entries with more than BDB_IDL_DB_MAX immediate children. If the entryIDs of the children are non-contiguous, then attempts to delete the subtree of the entry will fail, because the IDL range for the OneLevel index in the dn2id DB will never zero out.
back-hdb doesn't have this problem.
Not sure what an appropriate fix is. Ideally, when deleting an entry whose ID corresponds to either the lower or upper bound of the range, we should update the range with the ID of the next remaining sibling. But there's no easy way to search for that ID, so we just increment/decrement the range by 1. The OneLevel index is the only structure that can quickly tell us what the siblings are, and it's obviously useless when this situation arises.
The only way to search would be to [inc/dec]rement the ID and retrieve the corresponding entry's DN to see if it is a sibling of the deleted entry, and loop until a sibling is found or we run into the opposite range boundary. On a large DB this will be extremely slow.
Seems like the best fix is to deprecate back-bdb and only use back-hdb from now on.
Michael Ströder wrote:
Howard Chu wrote:
Seems like the best fix is to deprecate back-bdb and only use back-hdb from now on.
But I vaguely remember that back-hdb has higher memory consumption.
Eh? back-hdb has a smaller memory footprint, as well as a smaller on-disk footprint.
Maybe you're thinking of the original design in 2.1 http://www.openldap.org/lists/openldap-devel/200303/msg00055.html
which changed quite a bit since then.
Thinking about it some more, we can still salvage back-bdb, but it will require a change in the dn2id index format. The only thing that bothers me about this is that once you start down the path of making "sensible" changes to back-bdb's dn2id format, you eventually arrive at back-hdb anyway, so again, is it really worth the effort...
Anyway, the solution I'm thinking of is to reverse the RDN order in the dn2id index keys. (I.e., use X.500 order.) This way we can use BDB range lookups to find children/siblings of entries. That will give us a quick method of validating the OneLevel index. (The next logical step is of course to eliminate the OneLevel index because it's superfluous once you organize the RDNs this way. But we can stop short of that, no point in repeating the development of back-hdb yet again.)
--On Tuesday, July 22, 2008 1:22 PM -0700 Howard Chu hyc@symas.com wrote:
Thinking about it some more, we can still salvage back-bdb, but it will require a change in the dn2id index format. The only thing that bothers me about this is that once you start down the path of making "sensible" changes to back-bdb's dn2id format, you eventually arrive at back-hdb anyway, so again, is it really worth the effort...
Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at the same time, and rework back-hdb to work with BDB 4.7's new locking stuff. Honestly it seems like a bit of work to go to, to save a backend that's already been obsoleted.
--Quanah
--
Quanah Gibson-Mount Principal Software Engineer Zimbra, Inc -------------------- Zimbra :: the leader in open source messaging and collaboration
Quanah Gibson-Mount wrote:
--On Tuesday, July 22, 2008 1:22 PM -0700 Howard Chuhyc@symas.com wrote:
Thinking about it some more, we can still salvage back-bdb, but it will require a change in the dn2id index format. The only thing that bothers me about this is that once you start down the path of making "sensible" changes to back-bdb's dn2id format, you eventually arrive at back-hdb anyway, so again, is it really worth the effort...
Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at the same time, and rework back-hdb to work with BDB 4.7's new locking stuff. Honestly it seems like a bit of work to go to, to save a backend that's already been obsoleted.
Sounds about right to me. Of course, we knew that back-bdb's dn2id index was a problem 'way back in the beginning...
http://www.openldap.org/lists/openldap-devel/200112/msg00118.html
and we knew that back-hdb didn't have these problems. And we've talked about dropping back-bdb in favor of back-hdb several times through the years. It seems now is the time.
<quote who="Howard Chu">
Quanah Gibson-Mount wrote:
--On Tuesday, July 22, 2008 1:22 PM -0700 Howard Chuhyc@symas.com wrote:
Thinking about it some more, we can still salvage back-bdb, but it will require a change in the dn2id index format. The only thing that bothers me about this is that once you start down the path of making "sensible" changes to back-bdb's dn2id format, you eventually arrive at back-hdb anyway, so again, is it really worth the effort...
Maybe we just deprecate it, tell everyone to move off of BDB 4.2.52 at the same time, and rework back-hdb to work with BDB 4.7's new locking stuff. Honestly it seems like a bit of work to go to, to save a backend that's already been obsoleted.
Sounds about right to me. Of course, we knew that back-bdb's dn2id index was a problem 'way back in the beginning...
http://www.openldap.org/lists/openldap-devel/200112/msg00118.html
and we knew that back-hdb didn't have these problems. And we've talked about dropping back-bdb in favor of back-hdb several times through the years. It seems now is the time.
What's the overall impact to everything else code wise? "make test" will take half the time now though.
Gavin Henry wrote:
<quote who="Howard Chu"> > and we knew that back-hdb didn't have these problems. And we've talked > about > dropping back-bdb in favor of back-hdb several times through the years. It > seems now is the time.
What's the overall impact to everything else code wise? "make test" will take half the time now though.
Considering that back-hdb and back-bdb share 90% of their code, I don't see any immediate impact from this decision. Even going thru and deleting/moving the files in CVS is more trouble than it's worth. I guess we can disable it by default in the configure script, and drop it from the default tests.
Howard Chu writes:
Considering that back-hdb and back-bdb share 90% of their code, I don't see any immediate impact from this decision. Even going thru and deleting/moving the files in CVS is more trouble than it's worth.
If so, the version (RE25?) which removes back-bdb can rename the "hdb" backend to "bdb", maybe leaving "hdb" as an alias to be removed later. They are similar enough that this should not cause confusion. slapcat - slapadd will be required to upgrade, but that's required anyway between release branches.
What advantages do bdb still have over hdb today? Only that it's more used and thus somewhat better tested?
Howard Chu wrote:
And we've talked about dropping back-bdb in favor of back-hdb several times through the years. It seems now is the time.
If back-hdb has no disadvantages (like higher memory footprint) I'm for deprecating back-bdb. back-hdb offers more features anyway.
Ciao, Michael.
Howard Chu wrote:
Michael Ströder wrote:
Howard Chu wrote:
Seems like the best fix is to deprecate back-bdb and only use back-hdb from now on.
But I vaguely remember that back-hdb has higher memory consumption.
Eh? back-hdb has a smaller memory footprint, as well as a smaller on-disk footprint.
Glad to stand corrected regarding this. ;-)
Ciao, Michael.
Howard Chu writes:
There appears to be a long-standing problem with back-bdb and entries with more than BDB_IDL_DB_MAX immediate children. If the entryIDs of the children are non-contiguous, then attempts to delete the subtree of the entry will fail, because the IDL range for the OneLevel index in the dn2id DB will never zero out.
I'm not aware of a recursive delete LDAP control - do you mean "attempts to delete the entry after having deleted the subtree"? If so:
Is the problem only to (make it feasible to) detect this situation, or also to act on it? To detect it, I assume Delete before returning notAllowedOnNonLeaf could search with scope onelevel/children, and see if it finds any entires.
Hallvard B Furuseth wrote:
Howard Chu writes:
There appears to be a long-standing problem with back-bdb and entries with more than BDB_IDL_DB_MAX immediate children. If the entryIDs of the children are non-contiguous, then attempts to delete the subtree of the entry will fail, because the IDL range for the OneLevel index in the dn2id DB will never zero out.
I'm not aware of a recursive delete LDAP control - do you mean "attempts to delete the entry after having deleted the subtree"? If so:
Pretty much. E.g. using ldapdelete -r, but it would apply to any situation where an entry had many children, and eventually they were all deleted, and then eventually someone attempts to delete the entry itself.
Is the problem only to (make it feasible to) detect this situation, or also to act on it? To detect it, I assume Delete before returning notAllowedOnNonLeaf could search with scope onelevel/children, and see if it finds any entires.
Yes... back-bdb would also need to check this for modrdn as well. Seems like quite a lot of extra expense to perform this check each time.
Howard Chu writes:
Hallvard B Furuseth wrote:
Is the problem only to (make it feasible to) detect this situation, or also to act on it? To detect it, I assume Delete before returning notAllowedOnNonLeaf could search with scope onelevel/children, and see if it finds any entires.
Yes... back-bdb would also need to check this for modrdn as well. Seems like quite a lot of extra expense to perform this check each time.
Only at failure. Maybe it's more work than I imagine - it's an index after all. But IIRC we already have similar slowdowns in situations I'd assume are more common. When deleting multiple attribute values in an entry have the same hash, or something.
Hallvard B Furuseth wrote:
Howard Chu writes:
Hallvard B Furuseth wrote:
Is the problem only to (make it feasible to) detect this situation, or also to act on it? To detect it, I assume Delete before returning notAllowedOnNonLeaf could search with scope onelevel/children, and see if it finds any entires.
Yes... back-bdb would also need to check this for modrdn as well. Seems like quite a lot of extra expense to perform this check each time.
Only at failure.
We need to do this check whenever deleting an entry whose parent's onelevel index is an IDL range.
Maybe it's more work than I imagine - it's an index after all.
Yes, it's an index. But there's no efficient way to determine this info without the index. (Which again is why back-hdb doesn't do things this way...) The checks we're considering here could also seriously impair concurrency, since the Delete transaction could end up taking read locks on many entries before finding the next sibling.
But IIRC we already have similar slowdowns in situations I'd assume are more common. When deleting multiple attribute values in an entry have the same hash, or something.
No, not a comparable situation. In that case, we compute all of the hashes in memory but we cancel out the duplicates and only push the true changes into the DB. Computing the hashes is cheap, DB operations are not.
Seems like it's time to revisit this thread... http://www.openldap.org/lists/openldap-devel/200503/msg00012.html
The notion of bit-vectors for IDLs is looking good again. The whole reason this problem exists is because range IDLs lose so much information.
Hallvard B Furuseth wrote:
Does this bug produce incorrect hasSubordinates: TRUE values too?
Yes.
-
Gavin Henry -
Hallvard B Furuseth -
Howard Chu -
Michael Ströder -
Quanah Gibson-Mount