[PATCH v2] Faster handling of linked attributes

[Douglas Bagnall]

hi,
I think this version is correct, but I am getting flapping tests all
over the place, which I tentatively put down to exposing new territory
in the time-dependent tests.

I'm hoping but not hopeful that some pattern will emerge.

Douglas

On 12/01/17 15:44, Douglas Bagnall wrote:
> In AD, linked attributes are complementary pairs of attributes that
> describe a relationship between two objects. One of these attributes
> is called the "forward link"; adding this implies and automatically
> creates the corresponding "back link".
> 
> The canonical example is group membership: when you add a user to a
> group, you add a "member" attribute to the group that points to the
> user, which magically creates a "memberOf" attribute on the user
> pointing to the group. Groups can have many members.
> 
> If we didn't manage linked attributes in a vaguely sensible way, we
> would end up having to traverse all the existing members of a group
> for simple operations like adding or deleting users. For domain
> replication we would be performing this traversal for each user being
> replicated, meaning a group would have a potential (and often real)
> cost proportional to the square of the number of members.
> 
> This hypothetical situation describes what we currently do. To
> compound our misfortune, we have to explode the extended DN of every
> linked object in order to find a GUID to compare against, which turns
> out to be far more expensive than the comparing the GUIDs or shifting
> the values about.
> 
> The solution in these patches is to store the links in a sorted order
> in the database. When a new value is added we bisect the array to find
> the link or insertion point. This means we only have to explode the
> DNs of bisection pivots.
> 
> The existing code already uses a binary search, but it can only do so
> after the expensive work of exploding, parsing, and sorting all of the
> DNs. The binsearch macro it uses is only gives an absence/presence
> answer, which means we end up searching multiple times to find the
> exact status of each member. Using a binary search that returns a
> pointer to the object found allows us to simplify the code in many
> places (by some measures of simplify).
> 
> How do we change the database storage order? For existing databases,
> we don't. Only new databases (including e.g. those used in autobuild
> runs) maintain the links in sorted order. When we're setting up the
> indexes on a new database, we add a record called
> "@SAMBA_FEATURES_SUPPORTED" which lists features the database might be
> compatible or incompatible with. If we find the value "sortedLinks" in
> the compatible features attribute, we tell the replmd module to assume
> links are sorted.
> 
> It should not be terribly tricky to make a dbcheck rule or something
> that upgraded existing databases, but we don't provide that here.
> 
> Without the "sortedLinks" flag the new code will parse and sort the
> links as before, and will store them in sorted order. It seems to be
> slightly faster than before. With the flag the speed-up depends on how
> many links the object has. The ad dc performance tests
> (source4/dsdb/tests/python/ad_dc_performance.py) get up to perhaps a
> thousand links and see a 60% reduction in clock time for several
> tests. Overall for these tests the percentage of CPU time spent in the
> replmd_modify_la_* functions drops from 29.4% to 4.2%, with most of
> the remaining time spent on back link processing. The bit these
> patches deal with really is several orders of magnitude faster on
> large databases.
> 
> For what its worth, we are now finding that nearly half the CPU time
> is spent in memcpy inside tdb. But even with TDB_NO_FSYNC, the elapsed
> time for these tests is divorcing itself from the CPU time.
> 
> please review carefully!

-------------- next part --------------
A non-text attachment was scrubbed...
Name: replmd-links.patch
Type: text/x-diff
Size: 110071 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20170113/9f891350/replmd-links-0001.diff>