#48856 Memberof plugins compute 'memberof' using internal searches that can be costly
Closed: wontfix 4 years ago by tbordaz. Opened 7 years ago by tbordaz.

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).


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.

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.

Input from Thierry.

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

Per triage, set this ticket to 1.3.7.

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.

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
.

}}}

Metadata Update from @firstyear:
- Issue set to the milestone: 1.3.7 backlog

7 years ago

Status of this issue? 1.3.7, or?

Metadata Update from @mreynolds:
- Issue close_status updated to: None

6 years ago

With the improvement https://pagure.io/389-ds-base/issue/49031 (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

Metadata Update from @mreynolds:
- Custom field reviewstatus adjusted to None
- Issue set to the milestone: FUTURE (was: 1.3.7 backlog)

4 years ago

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 https://pagure.io/389-ds-base/issue/48856#comment-123015 or moving memberof to make it a virtual attribute

Metadata Update from @tbordaz:
- Issue close_status updated to: wontfix
- Issue status updated to: Closed (was: Open)

4 years ago

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.

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/1916

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.

Login to comment on this ticket.

Metadata