[WIP][PATCH] GUID index for LDB

[Andrew Bartlett]

On Wed, 2017-08-16 at 17:05 +1200, Andrew Bartlett via samba-technical
wrote:
> On Tue, 2017-08-15 at 10:55 +0200, Volker Lendecke wrote:
> > On Tue, Aug 15, 2017 at 08:21:25PM +1200, Andrew Bartlett via
> > samba-technical wrote:
> > > This is a heads-up about a work I have in progress.
> > 
> > When doing format changes I'd recommend taking a look at Chapter 7
> > of
> > http://shop.oreilly.com/product/0636920023913.do which has a hint
> > how
> > stuff might be stored in AD. Also, when talking to Metze I learn
> > that
> > there are some optimizations possible in the way we store
> > attributes.
> > 
> > The problem with format changes is that any time we do that we have
> > to
> > be backwards compatible and have upgrade code. Just take a look at
> > pdb_tdb.c. We should be careful to not accumulate too much of those
> > versions, so some good consideration is due here I guess.
> 
> I do agree.  It would be the hight of irony if ldb, designed in
> response to the inflexibility of tdb_pack based formats, was caught
> needing multiple version upgrade handlers.
> 
> Thankfully in this case I confine myself to the index code and index
> records.  The actual packed objects are not changed.  An upgrade will
> trigger a re-index without changing the objects, and a downgrade will
> (when I'm finished) simply detect a corrupt index and fall back to a
> full scan and then re-index.
> 
> I'll write more of a compare and contrast with AD and OpenLDAP when I
> get a working prototype, but I do hope this will be a practical and
> useful incremental change. 

I've looked into this, and OpenLDAP uses a very similar design to what
I've built, which is a sorted list of IDs as the core structure.  The
OpenLDAP abstraction is an MDB_IDL, whereas LDB uses struct dn_list
(re-purposed to contain either a DN or GUID in the ldb_val). 

Where we differ is that we use the GUID as the ID, rather than a
database key that could be followed directly.  We also still record the
full DN in the index and in the records, whereas to allow a fast
subtree rename, OpenLDAP has a DN to ID database and parent chain.  

Like OpenLDAP, Microsoft also uses a database id and no full DN.

Metze mentioned this very helpful link off-list:
https://blogs.technet.microsoft.com/askpfeplat/2012/07/22/mcm-core-active-directory-internals/

As mentioned, our LDB pack format and use of DNs is not ideal, nor like
these examples.  It is also outside my current scope of work, but is
something I would like to tackle later.

Finally, my GUID-index branch has been updated.  More work on tests,
both new and existing will keep me busy for another week, but I'm
pretty pleased with how it is working out.

Thanks!

Andrew Bartlett
-- 
Andrew Bartlett
https://samba.org/~abartlet/
Authentication Developer, Samba Team         https://samba.org
Samba Development and Support, Catalyst IT   
https://catalyst.net.nz/services/samba