Consistent inherited properties between entities on appengine HRD

Question

I'm implementing a file system. Folders each have an ACL, which will basically just be a list of user ids that are allowed to read/write to the folder. I want to implement this by copying ACLs from upper level folders down to lower level folders - I want inherited permissions, but I don't want to have to look them up at read-time. I store the relationship between folders as a reference to the superfolder in the subfolder.

The following order of operations, then, is hard to solve with the HRD:

1. Put folder B in the datastore as a subfolder of folder A, which already exists.
2. Change the permissions on A.

The problem is that, when I change the permissions on A in step 2, I need to look up all of the children of A so I can apply the permission changes to them as well. Unfortunately, this means a query, so B might not show up in that query. B could miss the permission changes!

The only solution I've thought of so far is to store "sub-folder" relationships bi-directionally: A has a reference to all of its subfolders, and B has a reference to its superfolder. Then I could use a cross-group transaction to update A and B simultaneously, and wouldn't need a query in step 2. This might be better anyway since direct gets can be cached easily, don't require an index scan, etc.

Anyone have any other ideas? I don't like the redundant storage needs of this solution, or the need for XG transactions.

Answer 1

The only transactional and strongly consistent unit in the datastore is an entity group. So if you want a reader of B to know about changes to A with transactional guarantees, A and B need to be in the same group. It sounds like you're trying to avoid the disadvantages of that approach (contention, write rate per group), so we need to find an acceptable tradeoff.

For instance, if it's unacceptable for the A and B entities to be in the same group, but it would be acceptable for instances of this kind of metadata to live in the same group (such as if it is rarely updated) and separately from the original entities (if XG update of the entity and this metadata is OK), you can just keep the data separate and analogous.

If you have a data structure that can quickly identify all of B's hierarchy ancestors, you can perform an asynchronous read of all ancestors when determining the aggregate metadata properties for B and its ancestors. You could manage this by storing full paths with the entities. This involves more datastore operations (on the order of path length), but not much more request time, and you get to keep this data normalized.