bp materialize-project-hierarchy
To manage hierarchical multitenancy data effectively the existing adjacency list paradigm is not enough: recursion is required to traverse the tree. Materialized path concept allows you to find all ascendants, descendants, children of the node in a single request operation.
Given the project hierarchy as follows:
+------------------------+
| A |
| |
| / \ |
| |
| / \ |
| |
| B C |
| |
| / \ / \ |
| |
| / \ / \ |
| |
| D E F G |
+------------------------+
It is possible to avoid recursion having entire project pedigree stored in the model instead of simple parent link.
For example:
DELIMITER = '->'
project.pedigree = A.id + DELIMITER + B.id + .. + DELIMITER + D.id
So every project has it’s pedigree stored that allows discovery of all projects needing to be checked, and all descendant projects will have pedigree starting with pedigree of ancestor.
This change is proposed to Resource SQL driver as entire HMT is implemented this way:
In order materialized path to work backend must be capable of either prefixed wildcard search or storing and indexing array fields. So pedigree column may either be a text field containing delimiter-separated project id’s or array of them.
Pre-order Tree Traversal offers an interesting model allowing compact fields to be used, alas many tree operations involve either complete tree reordering or, at least, comparison operators performed not using indexes in SQL backends. The idea is to store left and right integer markers in each node following the rule: any descendant node has left and right between left and right of the current node. (current.left < descendant.left < descendant.right < current.right)
Adjacency list gives the most flexible way to describe any graph, though in SQL backend it will result in 2-column indexed table of size up to N*(N-1)/2 that will lead to a poor performance of modification operations.
Adjacency matrix is a perfect tool to perform a special graph theory calculations and requires special software to be effective.
Caching of project structure may be an easier answer for small deployments and when scalability becomes an issue the caching system itself can become a complex solution with it’s own issues.
none
none
none
Operations on tree structure can be done in a single query without recursion. For example: * to delete a subtree one needs to delete projects with pedigree starting with pedigree of the project in question; * to get parent id’s there is no need to use a backend at all - entire pedigree is already stored in a model; * to move a sub-tree to another node all moved nodes’ pedigree has to be updated so that the old parent id replaced with the new parent id.
Algorithms comparison:
Get parent chain for D using ``parent_id``:
1. Request parent for D -> B
2. Request parent for B -> A
Total: 2 requests (the deeper the tree the more requests are needed)
Get parent chain for D using ``pedigree``:
1. Disassemble ``pedigree`` -> A.id/B.id/D.id
2. Request the content for A, B
Total: 1 request (independent of tree depth)
Get children of a node using ``parent_id``:
1. Request all nodes with ``parent_id`` == node.id
Total: 1 request, 1 filter by index
Get children of a node using ``pedigree``:
1. Request all nodes with ``pedigree`` starting with node.pedigree,
size of node.pedigree + size of node.id + size of delimiter
Total: 1 request, 1 filter by index, 1 sequence scan filter
Get sub-tree of a node using ``parent_id``:
1. For each node request all nodes with ``parent_id`` == node.id
Total: 7 requests (1 for every node in sub-tree)
BFS yields 2 requests here: 1 request per level of the tree.
Get sub-tree of a node using ``pedigree``:
1. Request all nodes with ``pedigree`` starting with node.pedigree
Total: 1 request (independent of tree depth)
Delete the sub-tree of the node using ``parent_id``::
1. Traverse the tree to find leaf nodes
2. Go up deleting them
Total: 1 request per node on traversal + 1 per node on deletion
May be optimised using BFS to iterate through levels and deleting groups
of siblings.
Delete the sub-tree of the node using ``pedigree``::
1. Delete everything with ``pedigree`` starting with node ``pedigree``
Total: 1 request (independent of tree depth)
Move the sub-tree using ``parent_id``::
1. update sub-tree top node's ``parent_id`` field with the new parent id
Total: 1 request updating 1 node (independent of tree depth)
Move the sub-tree using ``pedigree``::
1. update ``pedigree`` of all nodes with ``pedigree`` starting with the old
parent ``pedigree`` replacing it with the new parent ``pedigree``
Total: 1 request updating all moved nodes
Depth of the tree limitation may be increased if not removed at all: the single restriction is a pedigree column capacity.
Another gain is a possibility to have token validation in HMT case simplified. To filter revocation events by token’s project:
- Request pedigree for token’s project
- Request if revocation event with project id in the pedigree exists
Example:
User's U role R on project A was revoked. Client authenticated as user U has
a token scoped to project D. Request to check if token is revoked: revocation
event with user U, specified role, project in [A, B, D] exists.
Structure storage may feel a bit more complicated to developers to work with.
Who is leading the writing of the code? Or is this a blueprint where you’re throwing it out there to see who picks it up?
If more than one person is working on the implementation, please designate the primary author and contact.
DB migration: * Add pedigree column to the resource model * Populate every project’s pedigree column with actual pedigree calculated using parent_id. * Create btree index on pedigree. * Drop parent_id with it’s index.
none