[bind10-dev] DomainTree::remove() and node fusion behavior

[Michal 'vorner' Vaner]

Hello

On Fri, Aug 30, 2013 at 08:25:28AM +0530, Mukund Sivaraman wrote:
> There is an unintended consequence to node fusion which replaces
> existing nodes. If client code (that uses DomainTree) has
> DomainTreeNode* pointers in its code, they could become invalid (as both
> the old parent and child nodes are deleted) and the user will have to
> re-lookup the required nodes with find() or other seek methods such as
> nextNode() and previousNode(). This is a drawback, but on the other
> hand, we cannot avoid performing node fusion on a long-living tree as
> the tree will simply grow otherwise. Please comment on this.

I don't think not performing the fusion would be such a big problem. Yes, in
theory, it can grow. However:
• There's a limit on how much it'll grow. We never do fisson in the middle of
  label. So, the tree will still be linearly bound by the size of the zone,
  though with worse constants.
• The problem would be with large zones, but large zones are usually flat (TLDs,
  for example). I'm not saying there are no complex zones, but they are usually
  small to medium in size (eg. university, but that'll not have millions or
  records and that's still not that large to be problematic on today's RAM sizes).
• The node fussion happens in somewhat rare circumstance. What must happen is
  that we have a conceptual DNS subtree (eg. bunch of nodes matching *.x.y) and
  there's exactly one left after the deletions. That is, it's a department with
  many computers originally, but only one left in the end. I'd be more common to
  just remove the whole department.

So, in that sense, I don't think it is a big problem.

On the other side. Does the documentation promise that we preserve pointers
through all the operations? Does it say at insert? I don't think so (but I did
not check). Do we rely on such thing anywhere? It seems quite common to have a
delete operation on container classes that invalidates all the iterators ‒ which
are abstracted pointers. So I think it would be OK to invalidate the pointers on
delete.

> One alternative is to add a bool argument to remove() that conditionally
> enables or disables node fusion. When node fusion is disabled, the old
> pointers do not become invalid after a delete operation. The tree is
> perfectly valid without node fusion, but is sub-optimal.

Please, don't. As I argue above, I think the problem is less significant than it
seems. IMO either solution is fine. So let's choose one and stick with it
instead of complicating the API. I don't think anyone will ever want to use such
insane data structure outside of the memory data source, so we only need to
worry about ourself and we would have one place where we call the remove anyway.

With regards

-- 
BOFH Excuse #452:
Somebody ran the operating system through a spelling checker.

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130830/ea04fe37/attachment.bin>