1
$\begingroup$

I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like name/systemName where name is name of user or group.

Group objects store which users are members of the group.

GroupA = {UserA, UserB, UserC ....}
GroupD = {UserF, UserB, UserK ....}

This information is not stored in the users object. User objects have user related attributes.

UserA = {name="ABC", dob="x/x/x", }
UserB = {name="PQR", dob="x/x/x", }

I want to make a system, which will query all systems to get user and group objects and show them on GUI this way

UserA = {name="ABC", dob="x/x/x", memberOf=[GroupA]}
UserB = {name="ABC", dob="x/x/x", memberOf=[GroupA, GroupB]}

There are millions of users and millions of groups in these systems overall. The software I have created runs on various machine simultaneously. The software is written in Java.

I am using this approach to achieve this:

  • Start my program on one machine - Machine#1
  • Get all group objects from all the systems one by one and store them in memory store with key as user and value as list of group names
  • Once all the groups are queried and stored in memory store, then fire my program on other machines too
  • Other machines will copy the memory store created on Machine#1 to their machine (using third party lib - ehcache)
  • Program on each machine will query some set of Systems (Machine#1 will query system 1,2,3; Machine#2 will query 4,5,6 .. and so on)
  • Get all user objects and as I receive each user object, query memory store to see if user has any groups attached. If yes, pick them and store in DB?
  • Once all the programs on all machines are finished, we have result in DB which can then be shown anywhere

This approach has following disadvantages:

  • Consumes lot of memory (memory stores uses 20 GB RAM on one machine)
  • Memory store which needs to be replicated on other machines is not so stable process
  • Memory store is only built on single machine. This takes about 3 hrs to complete. During this time, other machines are idle, which is waste of resources.

End goals of application should be:

  • Best performance possible
  • Minimal wastage of computing time
  • Data (user objects showing groups) should be available in said format. The format cannot be changed as there is dependency with other downstream systems.

Is there a better approach to achieve the same ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For the memory part: The language used is Java. In Java the size of char is 2 bytes. Each user identifier on an average is 50 chars long, which means consumes 100 bytes. Each user on an average is member of 20 groups (2 groups per system). Each group identifier is on an average 50 chars long. So groups for each user take 20 x 50 x 2 = 2000 bytes. Considering overhead and all, it takes about 3000 bytes or 3KB to store a single user with groups. There are 20 million such users. This means all users take 7 x 3 x 1 million Kbytes = 21 million Kbytes = 21,000 MBytes = 21 GBytes approx. $\endgroup$ – SimpleGuy May 15 '18 at 7:30
  • $\begingroup$ @SimpleGuy, OK, makes sense. See revised answer -- I added a paragraph at the end to address your specific numbers. $\endgroup$ – D.W. May 15 '18 at 15:10
  • $\begingroup$ @DW I liked of approach of reducing the memory by storing a mapping. Replacing UTF-16 with 8 would not be possible LDAP systems I am connecting to are supporting UTF-16 names, so have to go with UTF-16. But the mapping suggestion can be incorporated. I am more looking into changing the algorithm to something I don't know at this point... $\endgroup$ – SimpleGuy May 16 '18 at 7:15
  • $\begingroup$ @SimpleGuy, UTF-16 is just an encoding. You don't have to store the data on your machine using the same encoding it's stored in the database. You can convert UTF-16 to UTF-8. Nothing will be lost in the conversion. I don't see anything wrong with the algorithm and I don't see any opportunity to improve the algorithm itself, personally. $\endgroup$ – D.W. May 16 '18 at 15:06
  • $\begingroup$ @DW I never knew that about UTF-16 to UTF-8 thing.. Thanks for that. And I read more about here in excellent answer by DPenner1 stackoverflow.com/questions/2241348/… $\endgroup$ – SimpleGuy May 17 '18 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.