[LONG] WinBind and/or nss-ldap - fundamental problems with Networ k Naming Services for Unix

[Mayers, Philip J]

All,

Please forgive the cross-posting - the issues I'm going to raise are
potentially pertinent to a broad range of people, so I'm distributing the
mail widely...

We've recently been investigating the possibility of a single campus-wide
naming service to replace our ageing NIS infrastructure. The obvious choice
was LDAP, since Sun and RedHat both seem to be moving in that direction. The
same problems we've been having will also apply to winbind-based
installations though.

We have a large user database, >40k entries, and an even larger group
membership database: >200k user/group membership tuples. Once we got over
the initial problems of loading and updating this many entries into an ldap
server, we found that supplementary group memberships only work *up to a
point*.

To see what I mean, imagine an SSH or console login
(Python-esque-pseudo-code):

username = getusername()
pam_start('sshd')
pam_set_item(PAM_USER,username)
/* Set other pam stuff up */
if not pam_authenticate():
	return -1
username = pam_get_item(PAM_USER)
uid,userPassword,uidNumber,gidNumber,gecos,homeDirectory,loginShell =
getpwnam(username)
initgroups(uid,gidNumber)
setgid(gidNumber)
setuid(uidNumber)
chdir(homeDirectory)
exec(loginShell)

All of this works fine - a user can be in 20 groups, and they will gain all
their group memberships, because the (PADL-provided) nss_ldap module will do
this:

def _nss_ldap_initgroups(username,additional):
    gids = [additional,]
    c = ldap.open(ldapserver)
    if binddn and bindpw:
        c.simple_bind_s(binddn,bindpw)
    done = 0
    for dn,entry in c.search_s(basedn,scope,'uid=%s' % (username,))
        if done:
            raise Exception, "Multiple entries for user %s" % (username,)
        done = 1
        for groupdn,groupentry in c.search_s(basedn,scope,
 
'(&(objectclass=posixGroup)(|(memberUid=%s)(uniqueMember=%s)))' %
(username,dn),
                                             ['cn','gidNumber']):
            gids.append(groupentry['gid'][0])
    return setgroups(gids)

So - a user can be a member of "Domain Users", which may well have >40k
users in it, but the only data that comes back across the wire for the LDAP
query is the cn (groupname) and gidNumber (passed to setgroups). So, the
query is fast server-side (given the appropriate indexing) and lightweight,
since there's relatively little data.

*But* - now imagine someone logged in, doing "id anotherusername" (I know
this python code isn't correct - assume it's C-ish :o)

def get_user_suppgroups(username):
    groups = {}
    import grp
    grp.setgrent()
    for gid,groupPassword,gidNumber,members in grp.getgrent():
        for m in members:
            if m==username: groups[(gid,gidNumber)] = 1
    return groups.keys()

Now, imagine 100 groups with 1000 members - that's
100*1000*averageusernamelength+overhead bytes that has to come from the LDAP
server for this query to succeed. In actual fact, this *could* be done
using:

def get_user_suppgroups(username):
    import ldap
    groups = {}
    c = ldap.open(server)
    if binddn and bindpw:
        c.simple_bind_s(binddn,bindpw)
    for groupdn,grouppentry in c.search(basedn,scope,
 
'(&(objectclass=posixGroup)(|(memberUid=%s)(uniqueMember=%s)))' %
(username,dn),
                                        ['cn','gidNumber']):
        groups[(groupentry['gid'][0], groupentry['gidNumber'][0])] = 1
    return groups.keys()

This would be much more efficient, and would have the same result for the
calling application - the difference is in network traffic and load on the
directory server and querying client.

I'm sure you can see the problem - any application that authenticates based
on named group membership (rather than the kernel, which authenticates file
access based on numeric primary uid/gid and supplementary gids) will have to
do this kind of lookup, and for large groups or large numbers of groups,
it's going to be prohibitively expensive. Apache is one obvious example -
samba shares are another, as is any login (ssh native group checking or a
PAM module) group membership check - do you have machines that are
restricted to certain groups - we do, and we aren't going to be able to do
this kind of thing due to the load on both the client and the server.


The same arguments that apply for LDAP apply for WinBind, or an SQL-based
system, or any other network naming service. It seems obvious what the
culprit is - getgrent() is a hog. What we need is a standardised pair of
calls:

int get_user_groups(char* username, int size, char* names[]);
int get_group_users(char* groupname, int size, char* names[]);

...or something similar. These can have NSS hooks, which nss_ldap or
nss_winbind can hook and do efficient queries for backending.

Active Directory takes a sort-of similar approach, where IADsGroup has an
IsMember method and a Members method that returns the full list of members,
but an enumerate of all the groups in the directory will be a relatively
efficient operation - it's the retrival of members that takes time. That's
done by default under Unix (with the getgr* calls) but not under
ActiveDirectory or NT4 domains (e.g. the NetUserGetGroups and
NetGroupGetUsers calls).



So - what solutions are there?

1) Very aggressive client-side caching - for M users of N-byte average
username, it's M*(N+1(null)+sizeof(char*)) to store an array of pointers to
group members - which for a 40k user group is 430k (likely more over the
wire, given the verbosity of the BER encoding for LDAP and NDR for DCE/RPC
over SMB) - this is likely to be very expensive in terms of both memory
(which is cheap these days, so maybe not) and memory bandwidth (which is not
cheap). Don't forget embedded systems.

2) Addition of a get_user_groups/get_group_users functions (and possibly an
is_group_member) to the standard C libraries, and recoding of all of the
standard utilities to use those functions. Additionally, perhaps an
administrator control to always return empty gr_mem from getgrent. I favour
this option, but it's a longer-term prospect (1+ years, very likely).

Interestingly, a grep of the RedHat and OpenBSD base sources gives egrep -r
'getgr(nam|uid|ent)' * | wc -l

OpenBSD - 310
RedHat - 2164

That's not a completely unreasonable proposition... If anyone wants the
package/file listings, let me know.

3) Replacement of the getXbyY routines with a more robust alternative - I
know several people would like this on other grounds, something like:

o = get_naming_object('user','uid','<useruid>')
uidNumber = get_naming_object_property(o,'uidNumber')
gidNumber = get_naming_object_property(o,'gidNumber')
# etc...

Obviously, this would be a *much* longer term prospect, although the old
library routines could be maintained for compatibility. I'm not sure this
would ever happen, certainly not to the penetration required.

4) Ignore it. A colleague of mine points out that supplementary groups are
hardly used "in his experience" - I can see several possible uses for them
in large environments, but I'm by no means sure that's not just a personal
bias.


So - that's my thoughts. I'd be interested to know what other people's
experiences are with large-scale network-distributed information databases.
If anyone from Sun/Novell/RedHat could comment on what they plan on doing
about it, I'd be grateful. Also, anyone from the
glibc/sh-utils/fileutils/OpenBSD/RedHat/Debian/other teams.

Your comments are welcome. If there's sufficient interest, I'll start a
mailing at IC that we can discuss this issue on.

Regards, 
Phil 

+----------------------------------+ 
| Phil Mayers, Network Support     | 
| Centre for Computing Services    | 
| Imperial College                 | 
+----------------------------------+