0

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.

1
  • @Paparazzi Read my question carefully. It can be not a tree, it is a directed graph without cycles
    – porton
    Sep 15, 2016 at 20:48

3 Answers 3

0

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.

5
  • The obvious way to modify my algorithm to be able to remove groups efficiently, we may add a table which will list for every group all its direct and indirect subgroups and then do removal of a group similarly to user removal. It is a complete solution now, but probably may be simplified or made more efficient. I also think about using reference counting in some way
    – porton
    Sep 16, 2016 at 22:42
  • Hm, adding a group with thousands of users may be slow. Possible solution is to add the users one-by-one or in small chunks (e.g. by 10 users) rather than in one big transaction.
    – porton
    Sep 16, 2016 at 22:55
  • Well, adding by parts needs to mark some groups as incomplete, so they would be "finished" if for example our server reboots in the middle
    – porton
    Sep 16, 2016 at 22:57
  • If we split in into small transactions, for complete reliability we need to check inside each transaction that the subgroup from which we copy entries remains a subgroup. Which bad things (if any) may happen otherwise?
    – porton
    Sep 16, 2016 at 23:33
  • What to do if a new user is added to a subgroup between these small transactions? This user may be forgotten to be insert into the parent group! One way to do this is to forbid adding new users to a group when its parent group is in re-building. Yes, I know what to do: the operations of modifying groups should run in-order in which these operations were called in a separate thread (not in several competing threads). This way we can even get rid of transactions (and thus the need to split into small transactions for efficiency)
    – porton
    Sep 16, 2016 at 23:44
0

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.

1
  • To make it faster, instead of "needs update" flag, we can use two flags: "needs add users" and "needs remove users"
    – porton
    Sep 20, 2016 at 12:58
0

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.

5
  • In M we may make counters for some groups "lazy" (what means that we could add counters from child groups only when needed. Not sure if it is a big improvement of performance.
    – porton
    Sep 20, 2016 at 13:39
  • Forming M may also be lazy. First add to it only these groups which were modified directly (not through their subgroups)
    – porton
    Sep 20, 2016 at 13:47
  • We should modify M in the same transaction as which modifies the main table, for data integrity. This transaction is not heavy weight, because modification of M is lazy
    – porton
    Sep 20, 2016 at 23:33
  • Well, no need to make a transaction if we modify data in single thread only
    – porton
    Sep 20, 2016 at 23:39
  • In the case if we do all groups modification in single worker thread, we also do not need to make checking for no cycles in our graph inside a transaction. So we do not need transactions for this at all
    – porton
    Sep 20, 2016 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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