2017-08-15 9:56 GMT+03:00 William Brown <wibrown(a)redhat.com>:
> On Fri, 2017-08-11 at 17:49 +0300, Ilias Stamatis wrote:
> > Hi everybody,
> >
> > Following Ludwig's and Mark's suggestions on how to perform a database
> dump
> > in LDIF format from dbscan, I have come up with a strategy. I'm talking
> > about ticket #47567:
https://pagure.io/389-ds-base/issue/47567
> >
> > I'd like to discuss this strategy and get some feedback.
> >
> > The general idea is:
> >
> > - We are cursing though id2entry.db printing entries in order.
> > - Parents should be printed before children.
> > - Hence if for some entry parenitd > entryid, we have to print its parent
> > first (out of order) and track that we did so.
> > - In order to do the above, we don't need to move the db cursor. We can
> > just go fetch something from a random place in the db and the cursor will
> > remain in its place, so we can continue from where we left off after
> we're
> > done with printing a parent.
> > - We also need to construct and print the DN of each entry using its RDN
> > and the DN of its father.
> > - Let's use something like a hash map to pair entryids with dns (only for
> > entries that has children), e.g. map[1] = "dc=example,dc=com", map[4]
=
> > "ou=People,dc=example,dc=com", etc.
> >
> > I'll present the algorithm that I came up with in python-like
> pseudo-code.
> >
> > First, the following function constructs the entry's DN and updates the
> > hash map if needed. We can know whether an entry is a parent or not, by
> the
> > presence of the numSubordinates attribute.
> >
> > # assumes that parentid already exists in the map
> > function display_entry(e, map):
> > if not e.parentid:
> > e.dn = e.rdn
> > else:
> > e.dn = e.rdn + map[e.parentid]
> > if isparent(e):
> > map[e.entryid] = e.dn
> > print_to_ldif_format(e)
> >
> > Then, the main loop:
> >
> > map = new(hashmap)
> > printed_in_advance = []
> >
> > for e in entries:
> > if e.entryid in printed_in_advance:
> > continue # skip this, we have already displayed it
> >
> > if e.parentid < e.entryid:
> > display_entry(e, map)
> >
> > else:
> > # we need to display parents before children
> >
> > list_of_parents = []
> >
> > p = e
> > while p.parentid > p.entryid:
> > p = get_from_db(key = p.parentid)
> > list_of_parents.append(p) # see note below (*)
> >
> > for p in reversed(list_of_parents):
> > display_entry(p, map)
> > printed_in_advance.append(p.entryid)
> >
> >
> > * here we store the whole entry in the list (aka its data) and not just
> > its id, in order to avoid fetching it from the database again
> >
> > As a map, we can use a B+ tree implementation from libsds.
> >
> > I would like to know how the above idea sounds to you before going ahead
> > and implementing it.
> >
>
> Looks like a pretty good plan to me.
>
> What happens if you have this situation?
>
> rdn: a
> entryid: 1
> parentid: 2
>
> rdn: b
> entryid: 2
> parentid: 3
>
> rdn: c
> entryid: 3
> parentid: 4
>
> etc.
>
> Imagine we have to continue to work up ids to get to the parent. Can
> your algo handle this case?
>
Unless I'm mistaken, yes. Provided of course that there is a root entry
which has no parentid.
This is the part that handles this:
p = e
while p.parentid > p.entryid:
p = get_from_db(key = p.parentid)
list_of_parents.append(p)
We may jump at a few random points in the db for this and we will have to
keep just a few entries in memory. But I think this number of entries is
always going to be very small e.g. 1-2 or maybe even 7-8 in more "extreme"
cases, but never more than let's say 15. I might as well be completely
wrong about this, so, please correct me if that's the case.
> It seems like the way you could approach this is to sort the id order
> you need to display them in *before* you start parsing entries. We can
> file allids in memory anyway, because it's just a set of 32bit ints, so
> even at 50,000,000 entries, this only takes 190MB of ram to fit allids.
> So I would approach this as an exercise for a comparison function to the
> set.
>
> universal_entry_set = [....] # entryrdn / id2entry
> # The list of entries to print
> print_order = []
>
> for e in universal_entry_set:
> printer_order_insert_sorted(e)
>
> So we can imagine that this would invoke a sorting function. Something
> that would work is:
>
> compare(e1, e2):
> # if e1 parent is 0, return -1
> # if e2 parent is 0, return 1
> # If e1 is parent to e2, return -1
> # If e2 is parent to e1, return 1
> # return compare of eid.
>
> Then this would create a list in order of parent relationships, and you
> can just do:
>
> for e in print_order:
>
> Which despite jumping about in the cursor, will print in order.
>
> So you'll need to look at entryrdn once, and then id2entry once for
> this.
>
> If you want to do this without entryrdn, you'll need to pass id2entry
> twice. But You'll only need 1 entry in memory at a time to achieve it I
> think. It also doesn't matter about order of ids at all here.
>
Hmm, I just didn't understand what's wrong with what I proposed previously.
As you said with the technique you just described we either have to pass
both entryrdn and id2entry once, or pass id2entry twice in any case. With
what I described previously we have to pass id2entry only once (and
probably for a few entries we will have to skip them if we come across them
a second time).
Could you explain why do you think the first one would be better / more
efficient?
I think your algo doesn't handle the case where you have *multiple* outo
of order parents. Even though you have to do two passes, the way I
proposed will guaranteed correct display regardless of id number because
they are solely sorted on parent relationships.
I think your one will get to
> while p.parentid > p.entryid:
> > p = get_from_db(key = p.parentid)
> > list_of_parents.append(p) # see note below (*)
> >
> > for p in reversed(list_of_parents):
> > display_entry(p, map)
> > printed_in_advance.append(p.entryid)
^ Here, what if the parent's parent is not yet printed? display_entry
would need to be recursive to handle this (and it appears to be
iterative).
Does that help?
--
Sincerely,
William Brown
Software Engineer
Red Hat, Australia/Brisbane