How to handle large number of users in SELinux?

This feels like a oversight regarding libselinux to me.

A 'fix' here would be to rename the old /etc/selinux/targeted/contexts/files/file_contexts.homedirs to something else. Create a new one (typically containing a few generic regular expressions which you can find at the top of the original file) and then setting that file immutable so that the policy rewriter doesn't regenerate the file (this happens when a new selinux-policy-targeted rpm is deployed).

This will prevent the CPU chew you are getting.

Your problem happens because restorecond opens this file as a reference to scan for files in users directories which must always be protected from invalid file label changes. But since your file contains thousands upon thousands of entries the scan uses up large quantities of CPU.

I suspect this was never considered when the library was created and probably needs a rethink from the SELinux end. But for now - that 'fix' should work.

It really depends on what restorecon is actually doing, but normally you don't want to run it at all, since it means that files get labeled with wrong labels and restorecon wants to make it right. The solution would be to have these files already created with the right label.

If it's actually the daemon restorecond that runs in background to do the relabeling then you can tune it so it doesn't do files where it shouldn't. See the man page of restorecond.

Do these servers deal with many files? Or do many files get created? Does it mount NFS shares?

What distro do you use? Redhat and Fedora are very responsive to selinux related problems. If the sheer size of the user database or users in groups is the real problem, they will almost certainly want to know about it. File a bug with bugzilla.