Efficient caching for groups of users and subgroups, whether a user belongs to a group

Question

Consider a system with a finite number of users and a finite number of groups.

To each group it corresponds a set of users. (We say that users "directly belong" to a group.)

Groups of users form a directed graph without cycles. If A→B for groups A and B, then I say that B is a direct subgroup of A.

The following operations are defined:

• add a user to a group
• remove a user from a group
• add a direct subgroup to a group
• remove a direct subgroup from a group

Note that attempt to make a cycle in the directed graph should throw an exception.

Also new users and groups may be created and existing users and groups may be deleted.

I need to efficiently cache this information, so that checking whether a user (directly or indirectly) belongs to a group (or any of its direct or indirect subgroups) should be a fast operation. Caching is done by a caching engine like memcached.

Please refer me to an efficient caching algorithm. I think I am not the first person to solve this problem and there is a known algorithm.

Note that we write in Python programming language.

Answer 1

First, my first idea to use memcached was wrong, because if a user does not login for awhile all references to him or her are removed from the cache. In this situation to check whether the user belongs to a toplevel group all groups need to be checked. It may be not efficient.

Instead I propose to add a caching relational DB table. This table will contain for a given group the set of all its direct and indirect users.

So checking if a user belongs to a group becomes completely straightforward.

Adding new users to a group and adding new subgroups are also easy.

A harder think is removal a user from a group. To do this, we can:

1. get the set of all groups directly containing this user;

2. calculate the set of all groups which directly or indirectly contain the first set;

3. subtract this last set from the set of all groups which directly or indirectly contain this user;

4. remove the user from each element of the last set.

Well, I have not yet decided how to behave when removing a group (rather than a user). Comments are welcome.

Answer 2

The previous solution suffers from DoS attacks (when a big user group changes its parent group many times, this may result in delays and even query overflow. So here I propose an alternative solution.

The same as in the previous solution, we add a caching relational DB table. This table will contain for a given group the set of all its direct and indirect users.

Using a global mutex (in fact, an advisory file lock) I run the worker process (the one which updates the DB) in no more than one process/thread simultaneously.

We mark (with a boolean flag) some tables as "needs update".

At start of the process we retrieve the set of tables needing update and construct an acyclic directed graph of dependencies between such tables.

The we start actual update process starting with the leaf nodes of this graph.

This process reads into memory the set of users for a given table and then one-by-one removes and adds correct rows.

The above mentioned process may be interrupted by a mutex (probably a value in the database). In this case the group is marked as needing update again and process starts from the beginning again.

The process is interrupted if a new task comes into the queue.

The above are my preliminary thoughts on the algorithm. They should be improved making the algorithm more detailed (to be worth of the name "algorithm") and more understandable.

Answer 3

Third (more efficient) algorithm.

We have the same caching table as in two other answers.

We keep (either in memory or in the DB) the set (let's denote it M) of all groups for which we should either add or remove users together with the lists of users to add and to remove.

Then we just do it (add and remove users to the caching table) in the worker thread, one-by-one user or in small transactions.

Between steps of the previous algorithm, the sets of users to add or remove can be modified.

To know when to remove a user also from a parent group when we remove the user from a child group, we can use reference counting in the many-to-many relation table between groups and users.

In the set M we also should keep reference counting of how many times a user was added or removed. When it is removed, we just decrement it reference counter in the many-to-many link table table and remove only if it reaches zero. When we add it, we increment the reference counter in the many-to-many link table.

The above are my preliminary thoughts on the algorithm. They should be improved making the algorithm more detailed (to be worth of the name "algorithm") and more understandable.