Friday, 16 February 2007

A better way to cascade in MySource 4.0

When the MySource Matrix permission system was first being planned, we tried a number of different database schemas to allow permissions to inherit to assets from multiple parents. The biggest problem was the time taken to check if a permission exists (eg. read access). With permission queries being some of the most common, they really needed to be as fast as possible.

The solution we came up with was a pretty basic one; cascade permissions to all child assets when setting them. So, for example, when you grant public read access on a Site asset, we run a HIPO job to set that same permission on every asset within the site. This allows us to check if any particular asset has public read access without having to determine its position in the tree. Instead of waiting for slow queries on the frontend, we made the backend processing slower.

There are two main problems with this approach. The first is that the data storage requirements are significantly greater than if we inherited permissions. The second problem is that cascading takes a very long time.

We just finished the planning of the Roles system for MySource 4.0. The roles system replaces the Permissions system in MySource Matrix, but requires the same general concept. We reevaluated the storage of permission assignments in MySource Matrix to see if we could remove the need for cascading role assignments.

Long story short; we couldn't. We still need to have a table with all the role assignments for every asset so we can quickly access role assignments for specific assets, and so that we can join the table to add permission checks to other queries. So we turned our attention to how we cascade assignments and looked for ways to make the process faster.

Here, we did succeed.

In MySource Matrix, we first get a list of all assets under the asset we are setting permissions on. Then we loop through each asset and assign the permission. A database query is executed for each of these assets to add the permission assignment. In reality, a lot more database queries are executed to load the asset and check its current assignments. HIPO thresholds are used to process more than one asset at a time, and the Squiz Server is used to process all assets in one go. Both thresholds and the Squiz Server make the process faster, but they don't reduce the number of queries executed.

In MySource 4.0, we have always wanted to get rid of the need for HIPO jobs and the Squiz Server. We are pretty sure we don't need the Squiz Server any more, but we will still need a HIPO job of some sort. The big difference are the thresholds. Whereas in MySource Matrix you could potentially process up to 50 assets at a time, MySource 4.0 thresholds will be more like 50,000. So even with HIPO jobs, you'll probably never see them.

We have written some new queries that will allow us to process different levels of the tree in one go, or multiple levels if they fit within the threshold. The reason we can increase the number of assets processed at once so much is because we no longer load assets and insert rows one by one. Instead, our new queries can look at the tree, select an entire level, and insert several thousand rows at once. These queries can also take granted and denied permissions into account, so you can't apply public read access where it is already denied (eg. a members only area).

We tested our theory yesterday with a sample of 44,000 assets from a MySource Matrix system. The goal was to select a entire section of a tree and insert new role assignments for all assets that did not currently have that role set. Here are the results:

# INSERT INTO asset_role_assignments (assetid, userid, roleid, granted)
# SELECT distinct l.minorid AS assetid, '90211' AS userid, '1234' AS roleid, 1 AS granted FROM
# sq_ast_lnk l INNER JOIN sq_ast_lnk_tree t ON t.linkid = l.linkid
# t.treeid like '00010002000D00030000%'
# sq_ast_perm p
# p.assetid = l.minorid
# AND p.userid = '90211'
# AND p.permission = 2
# );
INSERT 0 44041
Time: 2441.133 ms
This test was run on a dedicated database server using PostgreSQL 8.2. Over 44,000 entries were inserted in about 2.4 seconds. We calculated that processing 44,000 assets in MySource Matrix would take around 6 hours. The other thing to consider is that a Standard Page in MySource Matrix is actually 4 assets, whereas it is only 1 asset in MySource 4.0. So these figures actually tell us that MySource 4.0 can process 44,000 pages in 2.4 seconds whereas MySource Matrix can process 11,000 in 6 hours.

We have now started development of the Roles system, so it wont be too long until we can start trying this out with some real data. The results so far do look very promising though.