Memberof plugins compute 'memberof' using internal searches that can be costly

[389-ds-bot]

Cloned from Pagure issue: https://pagure.io/389-ds-base/issue/48856

• Created at 2016-05-30 21:42:47 by tbordaz (@tbordaz)
• Closed at 2019-12-16 15:23:18 as wontfix
• Assigned to nobody
• Associated bugzillas
  • https://bugzilla.redhat.com/show_bug.cgi?id=1362241

---

When adding an entry 'E' to a group, memberof plugin recalculate the 'memberof' attribute values.
To do this 'memberof_get_groups' builds a complete list of all the parents (direct and indirect) of the added entry 'E'. This task is done with internal searches of all the parents.

So if 'E' is member of N groups, it triggers N+1 internal searches.

The problem is that internal searches are costly and can create performance issue.

An other possibility would be to rely on the already calculated 'memberof' value.
For example 'E' is member of G1..G10 and is added to G11. Instead of searching 'E', G1..G10, G11, we may only search for all groups containing G11 (for example G1,G3, and G20) and merge the current value of memberof (G1..G10) with (G11,G1,G3,G20).

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2016-05-31 14:08:36

I think that this is a good (stop gap) solution for the addition problem. Relying on the existing memeberOf data is likely the correct solution here.

However, Del and Mod will still need full re-computations to maintain state of the graph.

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2016-05-31 15:08:04

Replying to [comment:1 Firstyear]:

I think that this is a good (stop gap) solution for the addition problem. Relying on the existing memeberOf data is likely the correct solution here.

However, Del and Mod will still need full re-computations to maintain state of the graph.

This solution can help with ADD and MOD_ADD of/on a group.
I agree it fails for DEL, MOD_DEL, MOD_REPLACE of/on a group.

[389-ds-bot]

Comment from nhosoi (@nhosoi) at 2016-06-03 00:43:47

Input from Thierry.

Will use a workaround in 1.3.5, so can wait for 1.3.6.

[389-ds-bot]

Comment from nhosoi (@nhosoi) at 2016-11-04 23:05:40

Per triage, set this ticket to 1.3.7.

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2016-11-08 09:09:27

attachment
0001-Ticket-48856-Reference-implementation-in-python-of-t.patch

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2016-11-21 22:27:40

attachment
memberof_algo2.py

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2016-11-21 22:33:16

Hi William

The python script looks really cool. It fixes http://www.port389.org/docs/389ds/design/memberof-scalability.html#problematic-case.
It is difficult to evaluate its performance efficiency but base on the counter search_count I think it could have perf hit when there are multiple paths to an impacted node.
I attached memberof_algo2.py where there is are searches for 6 nodes. In particular I think it does not address the optimization proposed in https://fedorahosted.org/389/ticket/48861.

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2017-01-09 07:22:48

It does actually work!

There was a fault in the algo2.py. I'm going to attach the updated algo patch with it fixed for multipath.

Please see this log of events also:

ds/dirsrvtests/tests/suites/memberof_plugin/memberof_design_reference_test.py ==> starting add_member for g
    adding b to g
    --> updating memberof for b
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for g
    adding c to g
    --> updating memberof for c
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for g
    adding d to g
    --> updating memberof for d
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for g
    adding e to g
    --> updating memberof for e
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for g
    adding f to g
    --> updating memberof for f
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for b
    adding a to b
    --> updating memberof for a
    current memberof set([])
    proposed memberof set([g, b])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for c
    adding a to c
    --> updating memberof for a
    current memberof set([g, b])
    proposed memberof set([g, b, c])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for d
    adding a to d
    --> updating memberof for a
    current memberof set([g, b, c])
    proposed memberof set([g, b, d, c])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for e
    adding a to e
    --> updating memberof for a
    current memberof set([g, b, d, c])
    proposed memberof set([g, e, b, d, c])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
==> starting add_member for f
    adding a to f
    --> updating memberof for a
    current memberof set([g, e, b, d, c])
    proposed memberof set([d, f, g, b, e, c])
    The current memberof set is not correct!
    update memberof complete, operation_count = 1, search_count = 2
<== add_member ended
START purge
Start fixup
==> starting fixup subtree
    working_group is g
    we belong to []
    working_group is f
    we belong to [g]
    working_group is e
    we belong to [g]
    working_group is d
    we belong to [g]
    working_group is c
    we belong to [g]
    working_group is b
    we belong to [g]
    working_group is a
    we belong to [b, c, d, e, f]
    found graph leaves [g]
    --> updating memberof for d
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    adding member a for update...
    --> updating memberof for a
    current memberof set([])
    proposed memberof set([d, f, g, b, e, c])
    The current memberof set is not correct!
    --> updating memberof for e
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    adding member a for update...
    --> updating memberof for a
    current memberof set([d, f, g, b, e, c])
    proposed memberof set([d, f, g, b, e, c])
    member of information is unchanged! Operation complete ...
    --> updating memberof for b
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    adding member a for update...
    --> updating memberof for a
    current memberof set([d, f, g, b, e, c])
    proposed memberof set([d, f, g, b, e, c])
    member of information is unchanged! Operation complete ...
    --> updating memberof for f
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    adding member a for update...
    --> updating memberof for a
    current memberof set([d, f, g, b, e, c])
    proposed memberof set([d, f, g, b, e, c])
    member of information is unchanged! Operation complete ...
    --> updating memberof for c
    current memberof set([])
    proposed memberof set([g])
    The current memberof set is not correct!
    adding member a for update...
    --> updating memberof for a
    current memberof set([d, f, g, b, e, c])
    proposed memberof set([d, f, g, b, e, c])
    member of information is unchanged! Operation complete ...
    update memberof complete, operation_count = 10, search_count = 16
    fixup complete, operation_count = 7, search_count = 8
<== fixup subtree ended
.

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2017-01-09 07:23:37

Add thierry's multipath test.
0001-Ticket-48856-Reference-implementation-in-python-of-t.2.patch

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2017-02-11 22:58:14

Metadata Update from @Firstyear:

• Issue set to the milestone: 1.3.7 backlog

[389-ds-bot]

Comment from mreynolds (@mreynolds389) at 2017-07-12 22:16:45

Status of this issue? 1.3.7, or?

[389-ds-bot]

Comment from mreynolds (@mreynolds389) at 2017-07-12 22:16:45

Metadata Update from @mreynolds389:

• Issue close_status updated to: None

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2017-07-13 11:55:54

With the improvement #2090 (in 1.3.6), performance hit of memberof reduced a lot.
So I think there is no urgency to fix 48856.

Now I think POC of 48856 gives track of futur improvement but is a major rewrite of the update part of the plugin.

I would vote for 'futur'. If there is enough bandwidth for 1.3.7, it can be '1.3.7' as well

[389-ds-bot]

Comment from mreynolds (@mreynolds389) at 2019-08-23 21:12:58

Metadata Update from @mreynolds389:

• Custom field reviewstatus adjusted to None
• Issue set to the milestone: FUTURE (was: 1.3.7 backlog)

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2019-12-16 15:23:07

Since 49031 and 50542 there is no more performance issue related to memberof update.

I am closing this ticket as wont fix.

It will be reopened if memberof perf is still a concern.
Others options are #1916#comment-123015 or moving memberof to make it a virtual attribute

[389-ds-bot]

Comment from tbordaz (@tbordaz) at 2019-12-16 15:23:19

Metadata Update from @tbordaz:

• Issue close_status updated to: wontfix
• Issue status updated to: Closed (was: Open)

[389-ds-bot]

Comment from firstyear (@Firstyear) at 2019-12-16 23:33:03

As a "for the record" making it a virtual attribute would likely cause it to perform worse than it currently does. Memberof is a trade off between "time in the write path" to reduce "time in the read path". If member of is read only once or twice, maybe virtual would be fine, but memberof is the absolute core of ipa and modern ldap group data, so it's read all the time with sssd. This means the trade into the write path is always going to be the most effective solution.