Recently, the company where I work announced the alpha release of Djangae, a compatibility layer that allows your Django application to work on App Engine, and to store your data in the App Engine Datastore. One of the things missing from the alpha was support for the Datastore's so called "Ancestor queries".
The App Engine Datastore is a remarkable feat of engineering. It's a non-relational database, which can scale to store mind-boggling amounts of data and deal with crazy high amounts of traffic. Of course, the sacrifice is that it's non-relational - so there are no joins, aggregate queries or the like. And if you want to count things then expect it to take some time!
Behind the scenes your data is seamlessly replicated and distributed across Google servers, which makes it extraordinarily reliable and performant.
Google achieves this by dividing your entities into "entity groups". The Datastore allows you to mark entities as being in a group by specifying their Ancestor when you create them. When you do this, the path to the root ancestor forms part of your entity's primary key and each member of the tree is part of the same entity group. Each entity group has its own index, and updates within the entity group are consistent.
If you edit an entity, and then perform a query for it using the entity's Ancestor then your results are strongly consistent. However, if you query without specifying the entity's Ancestor, your results will likely be stale. Your query might return entities that have been deleted, might fail to return new entities, or might return entities with stale data. This is because when you don't specify an ancestor, your query will look at the global index of all entities which is not strongly consistent, it's eventually consistent (updates will lag for a few seconds). Eventual consistency is a bitch to work with.
When you perform an ancestor query, the Datastore only looks at the entity group's local index, so you've already eliminated most of the entities in your datastore except for the ones below the specified ancestor. Which is why consistent results are possible.
There are a bunch of drawbacks with using Ancestor queries though, these are:
- All entities within the same group are limited to an overall total of 1 write per second
- To look up a descendant by key, you need to know the entire path to the root ancestor
- Keys just get confusing (does it have a parent? Can I look it up by kind and ID?)
- Moving descendants around means destroying and recreating them, and transferring any references to their old key
Anyway, there is an alternative to ancestor queries, which works better in nearly all situations; you can maintain a list of child IDs on the parent object. App Engine's list properties allow you to store up to 500 items (e.g. integers) in a single field. These items are indexed. By storing the IDs of related child entities on a logical parent, you gain the following things:
- Each entity has its own entity group, suddenly the write rate isn't so bad
- You can get all child entities consistently, at once by doing a Get rather than a query (you can then filter them in memory)
- You can query for the parent object by child ID (as list properties are indexed)
- Your entities can all be looked up with their ID
- Migrating child entities to a different parent just means updating the list on the parent
This is why Djangae doesn't have ancestor support yet, in nearly every situation that I've ever come across denormalizing child IDs has always been a better solution than building an ancestor tree. We'll get ancestor support into Djangae in time, but don't wait for it, just smartly structure your data.