[WIP][PATCH] GUID index for LDB

classic Classic list List threaded Threaded
32 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[WIP][PATCH] GUID index for LDB

Samba - samba-technical mailing list
This is a heads-up about a work I have in progress.

I know that this is a topic around which many folks will have great
ideas, but if we can keep those to small fixes and practical
improvements, that would be really awesome.  We can always make further
changes once we finish and measure this initial set of work.

I know I'm not going to win any awards for this improvement, but my aim
is to make adding users to Samba a little bit faster (because the index
records, for objectclass=user in particular, will be smaller), and to
optimise searching by removing the need to casefold all DNs between the
index and TDB key.

If successful this will make large domains more practical. 

The design is quite simple.  Where we keep records in TDB under a key
of DN=DC=SAMBA,DC=EXAMPLE,DC=COM, instead use the GUID.  Then put that
GUID in the index records.

The patches as is use the raw GUID except for special records, but of
course that means some @ record could match an unlucky GUID, so I'll
rework it tomorrow to use a GUID= prefix.  

One question, should I use:

GUID=9515e108-3b76-41fb-be2a-956cc90f644a
or
GUID=<binary GUID as raw 16 bytes>

as the key?

To do a base search, the DN -> GUID index in @IDXDN is consulted.  To
offset the cost of that, I optimise the base search not to fetch the
record twice.

TODO/ideas:
 - make it work (the DN -> GUID index write needs work)
 - use a GUID for linked attribute equality (eg memberOf) /
   rework the extended_dn_in module to prefer GUIDs for the query
 - sort index records
 - use sorted index records for faster intersection calculations.
 - always use the IDXONE index for SCOPE_ONE searches and trust that
result.

The saving from this change is primarily expected to be in the record
page in and parse time by reducing it from variable length strings to
fixed size GUIDs.  'perf' suggests that reading and parsing the index
records is around 10% of the CPU time to add a user, and grows with the
number of users.

Not included are the full set of tasks to allow O(1) subtree rename, as
that would require re-working the DN->GUID index rather than re-using
the existing code.  

I'm told a B-tree may be a much better structure, in particular a
structure were we don't need to page in and read a large index like
objectclass=user.  I see this kind of a rework as a second stage.

The patches are at:

https://git.samba.org/?p=abartlet/samba.git/.git;a=shortlog;h=refs/heads/GUID-index

The current WIP patches are attached for your interest.

Thanks,

Andrew Bartlett

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

GUID-index.patch.txt (152K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [WIP][PATCH] GUID index for LDB

Samba - samba-technical mailing list
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.

Volker

--
SerNet GmbH, Bahnhofsallee 1b, 37081 Göttingen
phone: +49-551-370000-0, fax: +49-551-370000-9
AG Göttingen, HRB 2816, GF: Dr. Johannes Loxen
http://www.sernet.de, mailto:[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [WIP][PATCH] GUID index for LDB

Samba - samba-technical mailing list
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.

(Previous research by Garming has showed that for performance we do
need to change the packed objects, at least by sorting them, but
thankfully that is not required to take on these changes.)

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





Reply | Threaded
Open this post in threaded view
|

[PATCH] GUID index for LDB

Samba - samba-technical mailing list
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'm pleased to day that as I finished work today, I got it working!

As a guide, with the old code we could, on my workstation with
TDB_NO_FSYNC set, add this many users to the AD DC in just 2 mins:

master:  17500
GUID-index: 25000

Douglas has kindly queued up a test run on our perf box to see the
broader impact, and I'll do some larger runs over the weekend.

While not earth-shattering, I think this is pretty good for an
incremental change.  

I've not yet stepped back to read up on the OL and AD designs, Sorry.

Now that it works, it would be great if another developer could review
the changes and provide feedback while I work on tests and address the
TODO items from the list I mentioned earlier.

Finally:

Volker,

I've been watching the 80 column marker pretty closely while working on
this, so I hope it meets your expectations in this area.

Thanks!

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

GUID-index.patch.txt (203K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Thu, 2017-08-17 at 20:22 +1200, Andrew Bartlett via samba-technical
wrote:
>
> I'm pleased to day that as I finished work today, I got it working!

I've pushed an updated patch set that fixes an issue in rename.

This still fails a full make test, but I'll continue to chase down the
regressions over the next week or so.

That also showed that I'll need to backport a fix our unique index code
in ldb_tdb to make downgrade trivial.  (The fallback of ldbdump /
ldbadd / dbcheck --reindex remains in any case).  I hope to land that
in 4.7 with the py3 ABI changes in the next week.

> As a guide, with the old code we could, on my workstation with
> TDB_NO_FSYNC set, add this many users to the AD DC in just 2 mins:
>
> master:  17500
> GUID-index: 25000
>
> Douglas has kindly queued up a test run on our perf box to see the
> broader impact, and I'll do some larger runs over the weekend.

This showed some things faster, and some things (like indexed search)
much slower, so I'll investigate why that might be, and what we can do
about it.  My hope is that once we sort the GUIDs we can improve the
speed of the index list intersections and recover the lost time, but
first I'll get it under perf and see what changed.

Thanks!

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


Reply | Threaded
Open this post in threaded view
|

Re: [WIP][PATCH] GUID index for LDB

Samba - samba-technical mailing list
In reply to this post by Samba - samba-technical mailing list
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





Reply | Threaded
Open this post in threaded view
|

Re: [WIP][PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Tue, 2017-08-22 at 16:41 +1200, Andrew Bartlett via samba-technical
wrote:
>
> 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.

I have continued to work on this.  The full branch is at:

http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-5

I would like to start getting some of this into master.

I am also doing performance work, which shows some pretty impressive
improvements once enabled, but also shows some regressions, so I'm
continuing to chase those down.

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





Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Tue, 2017-08-29 at 17:20 +1200, Andrew Bartlett via samba-technical
wrote:

> On Tue, 2017-08-22 at 16:41 +1200, Andrew Bartlett via samba-
> technical
> wrote:
> >
> > 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.
>
> I have continued to work on this.  

I'm continuing to test this branch.  There are some issues with other
parts of Samba that worked due to DB ordering assumptions.  However
overall, I think it is good.

The only other news is that while upgrades will be seamless, downgrades
will require running a script (which I'll write) or modification of the
@INDEXLIST on all the backend DBs.  We don't support a seamless
downgrade.  

I'll do some performance work on it over the weekend.  The previous
tests show a small performance cost (5% or so) on searches, and a bit
performance benefit (%40) on adding users.

I'll e-mail Tridge/Douglas/Catalyst for permission on a re-licence to
LGPLv3 the binary search macros next week.

I know it is a massive patch set, but some feedback would be helpful.

http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-6

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





Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Fri, 2017-09-01 at 18:04 +1200, Andrew Bartlett via samba-technical
wrote:

> On Tue, 2017-08-29 at 17:20 +1200, Andrew Bartlett via samba-technical
> wrote:
> > On Tue, 2017-08-22 at 16:41 +1200, Andrew Bartlett via samba-
> > technical
> > wrote:
> > >
> > > 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.
> >
> > I have continued to work on this.  
>
> I'm continuing to test this branch.  There are some issues with other
> parts of Samba that worked due to DB ordering assumptions.  However
> overall, I think it is good.
>
> The only other news is that while upgrades will be seamless, downgrades
> will require running a script (which I'll write) or modification of the
> @INDEXLIST on all the backend DBs.  We don't support a seamless
> downgrade.  
>
> I'll do some performance work on it over the weekend.  The previous
> tests show a small performance cost (5% or so) on searches, and a big
> performance benefit (%40) on adding users.

I've also run (on my workstation) the test to add users and add them
into a group in a 2-hour time limit, with fsync() disabled.

I was able to add almost 100k (99847) users in 2 hours, including
adding them to 4 groups, which is now the major factor.  (The previous
record was 85,000).

Currently the biggest bottleneck to LDB performance is not DB
technology, but simply the way we pack and unpack an LDB record!

BTW, the resulting database is only 860MB, significantly because the
new GUID index code produces a smaller index.

> I'll e-mail Tridge/Douglas/Catalyst for permission on a re-licence to
> LGPLv3 the binary search macros next week.
>
> I know it is a massive patch set, but some feedback would be helpful.
>
> http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-6
>
Thanks,

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


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Sat, 2017-09-02 at 08:13 +1200, Andrew Bartlett via samba-technical
wrote:
>
> > I'll e-mail Tridge/Douglas/Catalyst for permission on a re-licence to
> > LGPLv3 the binary search macros next week.
> >
> > I know it is a massive patch set, but some feedback would be helpful.
> >
> > http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-6
> >

This has been a success, and I have now got some performance numbers.

See the attached graph, with test times normalized to 1.  It shows that
 some tasks are better (much better) and that the rest is pretty much
un-affected.  (We have found that the noise on these measurements is
about 5%).

This series also passes a full make test.  It also showed some flapping
tests, so I plan to chase those down and I look forward to a positive
review!

Andrew Bartlett

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

GUID-idx-results.png (642K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
Hi Andrew,

>>> I'll e-mail Tridge/Douglas/Catalyst for permission on a re-licence to
>>> LGPLv3 the binary search macros next week.
>>>
>>> I know it is a massive patch set, but some feedback would be helpful.
>>>
>>> http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-6
>>>
>
> This has been a success, and I have now got some performance numbers.
>
> See the attached graph, with test times normalized to 1.  It shows that
>  some tasks are better (much better) and that the rest is pretty much
> un-affected.  (We have found that the noise on these measurements is
> about 5%).
So there's no performance loss of 5% for searches?
As we're now doing one more hop from the index (now via the objectGUID)
to the dn.

Is it expected that only some workloads are faster?

Do these numbers already include the BINARY_SEARCH patches?

> This series also passes a full make test.  It also showed some flapping
> tests, so I plan to chase those down and I look forward to a positive
> review!

I guess you'll resort the commits so that the version bump happens
at the end just before the final patch that activates it in Samba?

Can you also run an autobuild without the activation in Samba,
so that we're sure we don't insert regressions for possible backports?

I'm planing to have a closer look during the next two weeks.
As this is a huge patchset that immediately results in a new
ldb release, we should take our time for this (as it won't make it
to 4.7.0) without rushing this into master.

Thanks!
metze


signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Wed, 2017-09-06 at 12:44 +0200, Stefan Metzmacher wrote:

> Hi Andrew,
>
> > > > I'll e-mail Tridge/Douglas/Catalyst for permission on a re-licence to
> > > > LGPLv3 the binary search macros next week.
> > > >
> > > > I know it is a massive patch set, but some feedback would be helpful.
> > > >
> > > > http://git.catalyst.net.nz/gitweb?p=samba.git;a=shortlog;h=refs/heads/GUID-index-6
> > > >
> >
> > This has been a success, and I have now got some performance numbers.
> >
> > See the attached graph, with test times normalized to 1.  It shows that
> >  some tasks are better (much better) and that the rest is pretty much
> > un-affected.  (We have found that the noise on these measurements is
> > about 5%).
>
> So there's no performance loss of 5% for searches?

There might be, but I don't think so.  Our experience is that even
after several runs the numbers below 5% are not statistically
significant, as the absolute values have too much noise.  Watch how the
'do nothing' line moves around for an idea.  I'll mail you the full
results file and the absolute values graph tomorrow.

> As we're now doing one more hop from the index (now via the objectGUID)
> to the dn.

We only change the cost for a base DN search really, plus the cost of
checking the base for a subtree search.  

Anything in an index avoids going from a DN -> key with a casefold, as
both the contents of the index and the key in the DB now match exactly
(plus a prefix).

So an indexed search that was:
 - index -> casefold -> key
is:
 - index -> key

and a base search that was:
 - DN -> casefold -> key
is:
 - DN -> index -> key

We use a number of tricks to ensure we don't waste the expense of the
casefold.

> Is it expected that only some workloads are faster?

Yes.  It is delete from an index that hurts the most in the current
code (linear scan), the rest of the benefit comes from having a smaller
index overall, reducing the memcpy time in the read and transaction
commit.

> Do these numbers already include the BINARY_SEARCH patches?

Yes.

> > This series also passes a full make test.  It also showed some flapping
> > tests, so I plan to chase those down and I look forward to a positive
> > review!
>
> I guess you'll resort the commits so that the version bump happens
> at the end just before the final patch that activates it in Samba?

Yes, that is the plan.

> Can you also run an autobuild without the activation in Samba,
> so that we're sure we don't insert regressions for possible backports?

Yes, I'll check it with and without activation.

I have another proposal for the changes that need to make it in for 4.7
in a distinct thread.

> I'm planing to have a closer look during the next two weeks.
> As this is a huge patchset that immediately results in a new
> ldb release, we should take our time for this (as it won't make it
> to 4.7.0) without rushing this into master.

To give you some confidence, Garming has had a look at it, and I plan
to deal with the small details he has found in the next couple of days.

Thanks,

Andrew Bartlett

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


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
Hi Andrew,

>> So there's no performance loss of 5% for searches?
>
> There might be, but I don't think so.  Our experience is that even
> after several runs the numbers below 5% are not statistically
> significant, as the absolute values have too much noise.  Watch how the
> 'do nothing' line moves around for an idea.  I'll mail you the full
> results file and the absolute values graph tomorrow.
>
>> As we're now doing one more hop from the index (now via the objectGUID)
>> to the dn.
>
> We only change the cost for a base DN search really, plus the cost of
> checking the base for a subtree search.  
>
> Anything in an index avoids going from a DN -> key with a casefold, as
> both the contents of the index and the key in the DB now match exactly
> (plus a prefix).
>
> So an indexed search that was:
>  - index -> casefold -> key
> is:
>  - index -> key
Isn't it index -> GUID-key -> DN->key ?

> and a base search that was:
>  - DN -> casefold -> key
> is:
>  - DN -> index -> key

I don't understand that case...

Do you actually change the primary key for the records to be GUID based?
I thought you would only change the index and keep the real objects
as they're now...

> We use a number of tricks to ensure we don't waste the expense of the
> casefold.
>
>> Is it expected that only some workloads are faster?
>
> Yes.  It is delete from an index that hurts the most in the current
> code (linear scan), the rest of the benefit comes from having a smaller
> index overall, reducing the memcpy time in the read and transaction
> commit.
>
>> Do these numbers already include the BINARY_SEARCH patches?
>
> Yes.
>
>>> This series also passes a full make test.  It also showed some flapping
>>> tests, so I plan to chase those down and I look forward to a positive
>>> review!
>>
>> I guess you'll resort the commits so that the version bump happens
>> at the end just before the final patch that activates it in Samba?
>
> Yes, that is the plan.
>
>> Can you also run an autobuild without the activation in Samba,
>> so that we're sure we don't insert regressions for possible backports?
>
> Yes, I'll check it with and without activation.
>
> I have another proposal for the changes that need to make it in for 4.7
> in a distinct thread.
I noticed that...

metze



signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Thu, 2017-09-07 at 01:25 +0200, Stefan Metzmacher wrote:

> Hi Andrew,
>
> > > So there's no performance loss of 5% for searches?
> >
> > There might be, but I don't think so.  Our experience is that even
> > after several runs the numbers below 5% are not statistically
> > significant, as the absolute values have too much noise.  Watch how
> > the
> > 'do nothing' line moves around for an idea.  I'll mail you the full
> > results file and the absolute values graph tomorrow. 
> >
> > > As we're now doing one more hop from the index (now via the
> > > objectGUID)
> > > to the dn.
> >
> > We only change the cost for a base DN search really, plus the cost
> > of
> > checking the base for a subtree search.  
> >
> > Anything in an index avoids going from a DN -> key with a casefold,
> > as
> > both the contents of the index and the key in the DB now match
> > exactly
> > (plus a prefix). 
> >
> > So an indexed search that was:
> >  - index -> casefold -> key
> > is:
> >  - index -> key
>
> Isn't it index -> GUID-key -> DN->key ?
No (unless you count the memcpy() for the GUID=prefix as the GUID-key
step).

> > and a base search that was:
> >  - DN -> casefold -> key
> > is:
> >  - DN -> index -> key
>
> I don't understand that case...
>
> Do you actually change the primary key for the records to be GUID
> based?
> I thought you would only change the index and keep the real objects
> as they're now...
Correct, I move all the objects to allow (as should have been
originally designed) the values in the index to be trivially converted
into TDB keys.

> > We use a number of tricks to ensure we don't waste the expense of
> > the
> > casefold. 
> >
> > > Is it expected that only some workloads are faster?
> >
> > Yes.  It is delete from an index that hurts the most in the current
> > code (linear scan), the rest of the benefit comes from having a
> > smaller
> > index overall, reducing the memcpy time in the read and transaction
> > commit. 
> >
> > > Do these numbers already include the BINARY_SEARCH patches?
> >
> > Yes.
> >
> > > > This series also passes a full make test.  It also showed some
> > > > flapping
> > > > tests, so I plan to chase those down and I look forward to a
> > > > positive
> > > > review!
> > >
> > > I guess you'll resort the commits so that the version bump
> > > happens
> > > at the end just before the final patch that activates it in
> > > Samba?
> >
> > Yes, that is the plan.
> >
> > > Can you also run an autobuild without the activation in Samba,
> > > so that we're sure we don't insert regressions for possible
> > > backports?
> >
> > Yes, I'll check it with and without activation. 
> >
> > I have another proposal for the changes that need to make it in for
> > 4.7
> > in a distinct thread.
>
> I noticed that...
I've fixed a couple of issues and am tidying that up today.  I've
verified it allows a downgrade of a backend TDB by editing @INDEXLIST,
which could then be followed by a dbcheck --reindex.  

This is helpful if folks downgrade from 4.8 to 4.7 and forget the run
the (to be written) downgrade script first.

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




signature.asc (879 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
Am 07.09.2017 um 01:46 schrieb Andrew Bartlett:

> On Thu, 2017-09-07 at 01:25 +0200, Stefan Metzmacher wrote:
>> Hi Andrew,
>>
>>>> So there's no performance loss of 5% for searches?
>>>
>>> There might be, but I don't think so.  Our experience is that even
>>> after several runs the numbers below 5% are not statistically
>>> significant, as the absolute values have too much noise.  Watch how
>>> the
>>> 'do nothing' line moves around for an idea.  I'll mail you the full
>>> results file and the absolute values graph tomorrow.
>>>
>>>> As we're now doing one more hop from the index (now via the
>>>> objectGUID)
>>>> to the dn.
>>>
>>> We only change the cost for a base DN search really, plus the cost
>>> of
>>> checking the base for a subtree search.  
>>>
>>> Anything in an index avoids going from a DN -> key with a casefold,
>>> as
>>> both the contents of the index and the key in the DB now match
>>> exactly
>>> (plus a prefix).
>>>
>>> So an indexed search that was:
>>>  - index -> casefold -> key
>>> is:
>>>  - index -> key
>>
>> Isn't it index -> GUID-key -> DN->key ?
>
> No (unless you count the memcpy() for the GUID=prefix as the GUID-key
> step).
>
>>> and a base search that was:
>>>  - DN -> casefold -> key
>>> is:
>>>  - DN -> index -> key
>>
>> I don't understand that case...
>>
>> Do you actually change the primary key for the records to be GUID
>> based?
>> I thought you would only change the index and keep the real objects
>> as they're now...
>
> Correct, I move all the objects to allow (as should have been
> originally designed) the values in the index to be trivially converted
> into TDB keys.
And how does the upgrade/downgrade works then?

>>
>> I noticed that...
>
> I've fixed a couple of issues and am tidying that up today.  I've
> verified it allows a downgrade of a backend TDB by editing @INDEXLIST,
> which could then be followed by a dbcheck --reindex.  
>
> This is helpful if folks downgrade from 4.8 to 4.7 and forget the run
> the (to be written) downgrade script first.

Can you explain the upgrade/downgrade and the overall design changes
in explicit/verbose text form?

Thanks!
metze



signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Thu, 2017-09-07 at 01:53 +0200, Stefan Metzmacher wrote:
> Am 07.09.2017 um 01:46 schrieb Andrew Bartlett:
> >
> > Correct, I move all the objects to allow (as should have been
> > originally designed) the values in the index to be trivially
> > converted
> > into TDB keys. 
>
> And how does the upgrade/downgrade works then?

Via the re-index.  The upgrade operates because until 

dn: @INDEXLIST
@IDXGUID: objectGUID

is set, the old DB format is still used.

At startup, Samba modifies @INDEXLIST to match the expected values, so
will then re-index.

The downgrade works because you can still edit the @INDEXLIST (as these
are not GUID base) in an older ldb version and remove @IDXGUID,
provided you get the patches in the other thread.  

The re-index renames all the records.

Downgrade to earlier versions without first doing that remains possible
via ldbdump as it considers every record to be a possible ldb entry,
regardless of the key.

Finally, for Samba I'll add a script to do the @INDEXLIST edit for
Samba's multi-database tree.

> > >
> > > I noticed that...
> >
> > I've fixed a couple of issues and am tidying that up today.  I've
> > verified it allows a downgrade of a backend TDB by editing
> > @INDEXLIST,
> > which could then be followed by a dbcheck --reindex.  
> >
> > This is helpful if folks downgrade from 4.8 to 4.7 and forget the
> > run
> > the (to be written) downgrade script first. 
>
> Can you explain the upgrade/downgrade and the overall design changes
> in explicit/verbose text form?
I'll put that in the release commit message and in the top of the
ldb_index.c file.

Thanks for your interest!

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




signature.asc (879 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Thu, 2017-09-07 at 12:03 +1200, Andrew Bartlett via samba-technical
wrote:
>
> I'll put that in the release commit message and in the top of the
> ldb_index.c file.

The attached, updated patch set includes this slab (see the patch for
the full text):

The new 'GUID index' format is:
-------------------------------

dn: @INDEX:NAME:DNSUPDATEPROXY
@IDXVERSION: 3
@IDX: <binary GUID>[<binary GUID>[...]]

The binary guid is 16 bytes, as bytes and not expanded as hexidecimal
or pretty-printed.  The GUID is chosen from the message to be stored
by the @IDXGUID attribute on @INDEXLIST.

If there are multiple values the @IDX value simply becomes longer,
in multiples of 16.

The corrosponding entry is stored in a TDB record with key:

GUID=<binary GUID>

This allows a very quick translation between the fixed-length index 
values and the TDB key, while seperating entries from other data
in the TDB, should they be unlucky enough to start with the bytes of
the 'DN=' prefix.  

Additionally, this allows a scope BASE search to directly find the
record via a simple match on a GUID= extended DN, controlled via
@IDX_DN_GUID on @INDEXLIST

Exception for special @ DNs:

@BASEINFO, @INDEXLIST and all other special DNs are stored as per the
original format, as they are never referenced in an index and are used
to bootstrap the database.


Control points for choice of index mode
---------------------------------------

The choice of index and TDB key mode is made based (for example, from
Samba) on entries in the @INDEXLIST DN:

dn: @INDEXLIST
@IDXGUID: objectGUID
@IDX_DN_GUID: GUID

By default, the original DN format is used.


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




GUID-index-6.patch.txt (319K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
Am 08.09.2017 um 05:56 schrieb Andrew Bartlett:

> On Thu, 2017-09-07 at 12:03 +1200, Andrew Bartlett via samba-technical
> wrote:
>>
>> I'll put that in the release commit message and in the top of the
>> ldb_index.c file.
>
> The attached, updated patch set includes this slab (see the patch for
> the full text):
>
> The new 'GUID index' format is:
> -------------------------------
>
> dn: @INDEX:NAME:DNSUPDATEPROXY
> @IDXVERSION: 3
> @IDX: <binary GUID>[<binary GUID>[...]]
>
> The binary guid is 16 bytes, as bytes and not expanded as hexidecimal
> or pretty-printed.  The GUID is chosen from the message to be stored
> by the @IDXGUID attribute on @INDEXLIST.
>
> If there are multiple values the @IDX value simply becomes longer,
> in multiples of 16.
>
> The corrosponding entry is stored in a TDB record with key:
>
> GUID=<binary GUID>
>
> This allows a very quick translation between the fixed-length index
> values and the TDB key, while seperating entries from other data
> in the TDB, should they be unlucky enough to start with the bytes of
> the 'DN=' prefix.  
>
> Additionally, this allows a scope BASE search to directly find the
> record via a simple match on a GUID= extended DN, controlled via
> @IDX_DN_GUID on @INDEXLIST
>
> Exception for special @ DNs:
>
> @BASEINFO, @INDEXLIST and all other special DNs are stored as per the
> original format, as they are never referenced in an index and are used
> to bootstrap the database.
>
>
> Control points for choice of index mode
> ---------------------------------------
>
> The choice of index and TDB key mode is made based (for example, from
> Samba) on entries in the @INDEXLIST DN:
>
> dn: @INDEXLIST
> @IDXGUID: objectGUID
> @IDX_DN_GUID: GUID
>
> By default, the original DN format is used.
So we're upgrading the database on first use with the new code?

My fear with this is that a simple package upgrade will make
a dc with a large database unusable for quite some time.

Can you please check the cost of an upgrade for databases with
1.) 5000 users, 5000 computers and 5000 groups
2.) 20000 users, 20000 computers and 20000 groups
3.) with the numbers of the largest known customer size

I guess rewriting the whole database consumes quite some cpu
and also memory. A server may run out of memory while doing this
as we need more than twice the size of all sam.ldb* databases together.

I think I'd prefer making the switch for existing databases an
explicit task for the admin.

Thanks!
metze


signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
On Fri, 2017-09-08 at 10:36 +0200, Stefan Metzmacher wrote:

> Am 08.09.2017 um 05:56 schrieb Andrew Bartlett:
> >
> >
> > Control points for choice of index mode
> > ---------------------------------------
> >
> > The choice of index and TDB key mode is made based (for example, from
> > Samba) on entries in the @INDEXLIST DN:
> >
> > dn: @INDEXLIST
> > @IDXGUID: objectGUID
> > @IDX_DN_GUID: GUID
> >
> > By default, the original DN format is used.
>
> So we're upgrading the database on first use with the new code?

Yes, when Samba 'fixes' the @INDEXLIST on schema load this will be
triggered.

> My fear with this is that a simple package upgrade will make
> a dc with a large database unusable for quite some time.
>
> Can you please check the cost of an upgrade for databases with
> 1.) 5000 users, 5000 computers and 5000 groups
> 2.) 20000 users, 20000 computers and 20000 groups
> 3.) with the numbers of the largest known customer size
>
> I guess rewriting the whole database consumes quite some cpu
> and also memory. A server may run out of memory while doing this
> as we need more than twice the size of all sam.ldb* databases together.

I understand your fears, but to be clear, a database of 100,000 users
was only 860MB with the new code.  

In terms of existing deployment scale, the indeed network that Kevin
presented at SambaXP is the largest production deployment I know of and
before Samba 4.7 significantly larger deployments are un-feasible due
to the O(n^2) handling on links at join time.  (They take him ~ 30-45
minutes).

* 45 domain controllers on 5 continents
* 6,252 User/Group objects , 
* 37,625 group memberships

> I think I'd prefer making the switch for existing databases an
> explicit task for the admin.

I understand the concern, and I changed the index re-write code not to
force the set of DSDB_FEATURES_SUPPORTED flag for 4.7 for this reason,
meaning only new databases support 'features'.  A similar arrangement
could be made if needed.

The reverse concern I have is that if we do that, we have to maintain
and test Samba in both modes in perpetuity, particularly as we start to
structure our code to try to be GUID rather than string DN based.

Either way, it is Samba (not LDB) that controls when this is enabled,
and this and the auto-upgrade is only proposed to be enabled on a major
version upgrade, for Samba 4.8.  I will naturally make any change we
make here very clear in the WHATSNEW.

Most installations (from the discussions on the list) upgrade by
joining a new DC to the domain.  The few that don't just upgrade one DC
in a pair, then the other.  We hear about these because folks regularly
ask if the versions need to be upgraded in sync.

Garming keeps a 40,000 user test DB around, so I'll get those numbers
from that and hope the above helps address your concerns.  

Thankfully, the new code (actually everything since 1.2.2) is much
faster to re-index than the old, as I removed an O(n^2) loop.

Thanks for your continued thoughts on this!

Andrew Bartlett

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


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] GUID index for LDB

Samba - samba-technical mailing list
Am 08.09.2017 um 11:07 schrieb Andrew Bartlett:

> On Fri, 2017-09-08 at 10:36 +0200, Stefan Metzmacher wrote:
>> Am 08.09.2017 um 05:56 schrieb Andrew Bartlett:
>>>
>>>
>>> Control points for choice of index mode
>>> ---------------------------------------
>>>
>>> The choice of index and TDB key mode is made based (for example, from
>>> Samba) on entries in the @INDEXLIST DN:
>>>
>>> dn: @INDEXLIST
>>> @IDXGUID: objectGUID
>>> @IDX_DN_GUID: GUID
>>>
>>> By default, the original DN format is used.
>>
>> So we're upgrading the database on first use with the new code?
>
> Yes, when Samba 'fixes' the @INDEXLIST on schema load this will be
> triggered.
>
>> My fear with this is that a simple package upgrade will make
>> a dc with a large database unusable for quite some time.
>>
>> Can you please check the cost of an upgrade for databases with
>> 1.) 5000 users, 5000 computers and 5000 groups
>> 2.) 20000 users, 20000 computers and 20000 groups
>> 3.) with the numbers of the largest known customer size
>>
>> I guess rewriting the whole database consumes quite some cpu
>> and also memory. A server may run out of memory while doing this
>> as we need more than twice the size of all sam.ldb* databases together.
>
> I understand your fears, but to be clear, a database of 100,000 users
> was only 860MB with the new code.  
My concern is about large database, which gets expanded by the
transaction, which means it will be more fragmented and all
of the new records are appended at the end and the old space
moves to the freelist.

How does the reindexing code operates in detail?
Were can I find the related code?

Do we delete all index related keys first?

Do we delete an old DN= based record before storing it under
the GUID= key?

And then rebuild the indexes?

> In terms of existing deployment scale, the indeed network that Kevin
> presented at SambaXP is the largest production deployment I know of and
> before Samba 4.7 significantly larger deployments are un-feasible due
> to the O(n^2) handling on links at join time.  (They take him ~ 30-45
> minutes).
>
> * 45 domain controllers on 5 continents
> * 6,252 User/Group objects ,
> * 37,625 group memberships

Is this in total or 45 mins per dc?

>> I think I'd prefer making the switch for existing databases an
>> explicit task for the admin.
>
> I understand the concern, and I changed the index re-write code not to
> force the set of DSDB_FEATURES_SUPPORTED flag for 4.7 for this reason,
> meaning only new databases support 'features'.  A similar arrangement
> could be made if needed.
>
> The reverse concern I have is that if we do that, we have to maintain
> and test Samba in both modes in perpetuity, particularly as we start to
> structure our code to try to be GUID rather than string DN based.
>
> Either way, it is Samba (not LDB) that controls when this is enabled,
> and this and the auto-upgrade is only proposed to be enabled on a major
> version upgrade, for Samba 4.8.  I will naturally make any change we
> make here very clear in the WHATSNEW.
Ok, I think it would include some numbers.

We may also need to document a procedure that avoids doing
the upgrade by starting samba. I guess a good strategy might
be disabling samba and use "samba-tool dbcheck --cross-ncs"
to trigger an offline upgrade. That would hopefully avoid
problems for clients which may talk to an unusable dc.

> Most installations (from the discussions on the list) upgrade by
> joining a new DC to the domain.  The few that don't just upgrade one DC
> in a pair, then the other.  We hear about these because folks regularly
> ask if the versions need to be upgraded in sync.
>
> Garming keeps a 40,000 user test DB around, so I'll get those numbers
> from that and hope the above helps address your concerns.  

Please backup the files before the upgrade, so we can redo it if needed.

What are the sizes before the upgrade?
Please collect "tdbtool $file info" for all files,
before and after the upgrade.

Please also watch top for the memory consumption.

> Thankfully, the new code (actually everything since 1.2.2) is much
> faster to re-index than the old, as I removed an O(n^2) loop.





signature.asc (853 bytes) Download Attachment
12