On (19/01/16 22:52), Sumit Bose wrote:
>On Tue, Jan 19, 2016 at 09:08:53PM +0100, Lukas Slebodnik wrote:
>> On (19/01/16 17:52), Sumit Bose wrote:
>> >On Tue, Jan 19, 2016 at 11:08:50AM -0500, Simo Sorce wrote:
>> >> On Tue, 2016-01-19 at 16:27 +0100, Lukas Slebodnik wrote:
>> >> > I'm not sure about the defualt value.
>> >> >
>> >> > Simo wrote few comments on IRC few days ago that this feature is
not
>> >> > deterministic among more machines.
>> >> > e.g.
>> >> > there are few users
>> >> > jakub -- S-1-5-21-100-200-300-12809
>> >> > simo -- S-1-5-21-100-200-300-212809
>> >> > sumit -- S-1-5-21-300-200-100-12809
>> >> >
>> >> > Let say that S-1-5-21-100-200-300 will be mapped to the slice 10
>> >> > and S-1-5-21-300-200-100 to the slice 11
>> >> >
>> >> > machine A:
>> >> > * getent passwd jakub -> slice 10 is created
>> >> > * getent passwd simo -> slice 11 is created based on this
feature
>> >> >
>> >> > machine B:
>> >> > * getent passwd jakub -> slice 10 is created
>> >> > * getent passwd sumit -> slice 11 is created
>> >> >
>> >> >
>> >> > And user 'simo' will have the same UID on 'machine
A' as user
>> >> > 'sumit' on 'machine B'. It can be a problem on
nfs.
>> >> >
>> >> >
>> >> > So I'm not sure we should enable this feature by default.
>> >> > But on the other hand this feature might fix many users
complications.
>> >>
>> >> Sumit explained to me the slice selected was going to be determined by
>> >> the murmur hash, is it not ?
>> >> Are slices selected linearly as a first come - first serve basis ?
>> >> That is not workable, the code must try *hard* to come up with the
same
>> >> slices regardless of the order in which users "appear".
>> >
>> >no, the slices are selected based on the SID of the object. The domain
>> >part is used as a prefix. The RID is divided by the range size which
>> >gives you the number of the slice of this domain. E.g. if the range size
>> >is 1000 and the rid is 3456 the number is 3 and this slice will map the
>> >RIDs from 3000 to 3999. The first RID of the slice is appended to the
>> >domain SID and the result is fed into murmurhash to get a matching slice
>> >of POSIX IDs which is equivalent to what we already do. This scheme is
>> >reproducible and can cover holes in the RID range as well. In the
>> >examples above, if there are no RID between 2000 and 2999 we will not
>> >allocate a range for this RIDs. But if later an object with a RID with
>> >e.g 2345 is added then the range can be added as well without changing
>> >any of the existing ones.
>> >
>> I would like to apologize that I'm asking to late in process but
>> I'm not sure I understand in correctly.
>> The design page says:
>>
https://fedorahosted.org/sssd/wiki/IdmapAutoAssignNewSlices
>> -> Overview of the solution
>> -> After primary slices for all domains are generated. Secondary slices
>> should be generated:
>> * Secondary slices should be computed at the start up of back end but
>> after primary slices for all domains are computed (to avoid potential
>> collision of primary slices with previously created secondary slices).
>> * Secondary slices should be created in round-robin manner meaning that
>> we first try to allocate #1 secondary slices for all domains,
>> then #2 secondary slices for all domains ... and finally
>> #$ldap_idmap_extra_slice_max secondary slices for all domains.
>>
>> It looks like there is an expectation that we will have all domain parts of
>> SIDs available on start up of sssd. But I'm not sure it's correct
expectation.
>> If this expectation is met then the algorithm should be deterministic.
>
>no, this is not expected. With the murmurhash based calculation I
>described the order in which the slices are calculated does not matter
>because the parameters of each slice are determined by the first SID in
>the slice, the range size and the overall upper and lower bound of the
>POSIX IDs we allow for SID mapping.
>
I'm sorry I worded it a little bit poorly.
I didn't want to say that input for murmurhash is not deterministic.
It is.
>The scheme from the design page is just useful in the case where there
>are collision in the secondary slices because it might indicate to the
>user that a collision occurs when adding e.g. the #5 additional
>secondary slices. Then it can be checked if that many SIDs are used at
>all and if it is the case then other idmap parameters might be tuned to
>avoid the collision.
>
My intention was to say that we increased probability
of collision. Because according to design page *secondary slices should be
generated on start up* of sssd. So there is 10 times higher probability
of collision. The default value of ldap_idmap_extra_slice_(max,init) is 10.
Let's imagine that user already increased ''ldap_idmap_range_size''
because he
needed it. After upgrade we will generate 10 additional slices by default.
and if the user already had 10 primary slices we will generate additional
slices on start up. Even though it will not be necessary. User already
increased ''ldap_idmap_range_size''.
>Please note that in the case of a collision we currently already have a
>race condition because the order in which the idmapping for the
>different domains are created might change.
>
Sure.
Fortunately murmurhash is good enough.
Pavel wrote that the semantic of ldap_idmap_extra_slice_(max,init) was changed
and it's just an initial value (minimal value). If we change the default to
very low value (1,3) then we should not generate many extra slices on start up.
and thus prevent issues with generating "collision".
You are right, the more ranges we use the higher the chance for a
collision. But I asked Pavel for a change in my last review comment
which should mitigate this considerably (and since I asked this on
Monday it is not yet mentioned on the design page, but either me or
Pavel will update it during the next days). Basically what is calculated
at the time a new domain is added (on startup) is a helper table which
contains the minimal and maximal POSIX ID and the first RID for the
first additional slices up to ldap_idmap_extra_slice_init. The main
purpose of this table is to speed up the POSIX ID to SID lookups with an
empty cache. But it might warn you about potential collisions as well.
A new range is only allocated if needed. This has the additional
advantage that larger holes in the RID spaces are skipped. E.g. if there
is an AD environment which has the default RIDs like -500 and -512 used
but then someone increase the RID for new objects to 1 million there
will be the initial slice which covers RIDs 0-199999 and an additional
one which covers RIDs 1000000-1199999. There will be no slices for RIDs
200000-999999 because they are not used which lowers the chances for
collisions. If later a new object with RID 500000 is tweaked into AD
SSSD will allocate a slice for RIDs 400000-599999 to cover this object.
And since domain-SID-first-RID-of-the-slices is used as input for
murmurhash all clients will use the same POSIX ID slices to map the
RIDs.
bye,
Sumit
>
> LS
> _______________________________________________
> sssd-devel mailing list
> sssd-devel(a)lists.fedorahosted.org
>