Better algorithm for aggregating data from various LDAP systems
Your algorithms seem fine.  I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side.

At a high level, I would say that your design seems good enough as is.  If the primary objection is that it requires 20GB of RAM, well, buying RAM is a lot cheaper than spending a day of a software developer's time to implement a more memory-efficient solution.  So my primary advice would be to order some more RAM and call it good enough.

But if you still want to push on, I'll offer some other reactions...

Millions of users and groups is a fairly small data set.  20GB of RAM seems excessive for that.  Suppose there are 5M users, and each user is a member of 5 groups on average (say), and each group name is 10 characters long on average.  That corresponds to 50 bytes of data per user.  Add some overhead and round up and I'd estimate something like 80 bytes per user.  Yet your current data structure seems to be using 4KB per user.  That seems 50x too large; I would have expected something like 400MB would be sufficient.

Therefore, I'd suggest you do some memory profiling and look into why your in-memory store is taking up so much memory.  Perhaps you are using an unnecessarily inefficient data structure or hashmap implementation.  Keep in mind that you don't need to store the entire user object and group object (with all their attributes) in memory.  All you need to store in memory is the name of the user (a string) and the names of the groups they are in (a list of strings); the attributes can be stored in the database.  There are other techniques for reducing memory, such as sharding the data structure across multiple machines, but that hardly seems necessary or worth the effort.

Also, I wonder whether it's really necessary to run on multiple machines.  With only a few million users, I would have expected one machine to be more than adequate.  So if you care about the time to completion, you might want to look into that.  If you can do it on one machine, that will be simpler to implement, simpler to deploy, simpler to maintain, simpler to manage, and will reduce your stress about tying up 20GB of RAM on multiple machines.  I would have expected that the rate-limiting step is the number of LDAP queries you can make per second, so you could investigate what is keeping that down.  Perhaps you can have multiple threads making LDAP queries in parallel.  Perhaps you can reuse the same connection for multiple queries, to avoid connection setup and teardown costs.  Maybe you can run this on the same machine as the LDAP server to reduce network overhead.  Maybe you can think of some other speedups.

But overall, my guess is that this is a problem better solved by a beefier hardware rather than a software developer's time to optimize the code; and if you do want to improve the software, you're more likely to see gains from focusing on quality of implementation rather than algorithms.



Based on your comments, here is an alternative data structure that might save memory.  Assign each user and each group a unique integer ID (incremented by one for each new user/group).  Keep a mapping from name of user -> ID of user (with a hashtable) and a mapping from user ID -> user name (with an array); this is probably doable with 2-4GB, based on your numbers.  Do the same for groups; that's probably much less.  Then, keep a mapping from user ID -> array of group IDs that the user is in; that's probably doable with another 2-4GB.  All in all, I'd expect this could reduce your memory consumption to 4-8GB instead of 20GB.  You might be able to get further reduction by storing names in UTF-8 rather than UTF-16.