On Tue, 2017-08-15 at 22:03 +0300, Ilias Stamatis wrote:
> 2017-08-15 9:56 GMT+03:00 William Brown <wibrown@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

_______________________________________________
389-devel mailing list -- 389-devel@lists.fedoraproject.org
To unsubscribe send an email to 389-devel-leave@lists.fedoraproject.org