Thomas Wanschik on October 06, 2010

JOINs via denormalization for NoSQL coders, Part 3: Ensuring consistency

In part 1 and part 2 we introduced the concept of denormalization, materialized views and background tasks in order to emulate JOINs in the to-one direction on NoSQL databases. Now we'll talk about all remaining little but important snippets of the puzzle left over and discuss how to ensure that this method works in real world situation like server crashes.

When to start background tasks?

Let's first remember our current situation:

Given this we have to answer when to start background tasks while keeping in mind that the connection / database / web server can fail for many reasons. A straightforward way is to start background tasks right after having saved changes to photos or users (via Django's post_save signal for example). However this solution comes with some problems. Let's take the following evil failing scenario when trying to edit an already existing photo:

In this scenario we succeeded in saving the user's changes to one of his/her photos but we didn't start a background task yet in order to update the corresponding materialized view. A query (like the first one from section "Materialized views" in our last post) using this materialized view would fail to find the changed photo because it doesn't contain up-do-date denormalized properties of its corresponding photo.

Another problem with starting background tasks after a save() is that background tasks and a save() can come into update-conflicts. To see this, let's take a closer look at the following example:

As a result we have an incorrectly updated materialized view because the first background task fetched the data before the second background task saved its updates. This problem exists in general if the delay between a save() and the corresponding background tasks is smaller than the biggest time interval a background task is allowed to be executed in. In such cases overlaps between background tasks can happen.

One way out of both problems is to start background tasks right before a save() using a delay larger than the longest time interval for an update to the materialized view (longest time for getting the data + longest time for saving the data). On App Engine a request can't take longer than 30 seconds for example. This will ensure that background tasks get executed after the saving process is finished and avoid the update-conflicts discussed above because overlaps between background tasks and another save() and its corresponding background task like in the example above can't happen (see figure below). Additionally crashes right after a save() won't stop updates of materialzed views because we've already started the background tasks before. Background tasks will get the photo out of the database via the photo's primary key and update its corresponding materialized view.

Using big delays avoids update-conflicts and ensures correct updates

Multiple updates to photos almost at the same time don't represent any problem for updates of materialized views because they'll start in delayed background tasks i.e. they will get the latest version of the photo out of the database in order to update the corresponding materialized view.

Apart from that, if the database crashes right before saving the user's changes but after starting the background task, the background task will still be executed resulting in updating the materialized view with the same data already saved in the materialized view. This case doesn't represent any problem.

What about inserts?

Now we still have to consider the situation in which a user creates a new photo. Because we start background tasks before a save() we don't have the primary key of the photo i.e. we can't pass the primary key of the photo to the background task. One way to solve this is to mark newly created photos with a unique UUID. The corresponding background task will use this UUID to get the newly inserted photo and create the corresponding materialized view.

How to update materialized views

Until now we discussed when to start background tasks but not how to update materialized views. It's important that each update to a materialized view will rebuild the affected entities of the materialized view from scratch (but not unaffected entities of the materialized view) because otherwise it can result in incorrect updates. Let's assume that changing a user's gender only updates the denormalized gender for the corresponding materialized view and that changes to a photo's title only update the denormalized title for the corresponding materialized view. Given this we can get into the following situation:

As a result we have an incorrectly updated materialized view because the background task 2 fetched the data before background task 1 saved its updates. To avoid this we always have to completely rebuild the affected entities of the materialized view. Even if only the photo's title changes we have to update the denormalized_gender too! I.e., we have to get the corresponding photo and the user! This ensures correct updates even if overwrites happen because each update rebuilds the affected entities completely i.e. the materialized view is kept up-to-date with the latest data.

Best of both worlds

Using large delays for background tasks may be unsatisfying because user may notice them. For example, a user inserts a photo but can't find it right afterwards. So you may ask "why not start another background task right after we save a photo too?" And yes that's what we suggest. Starting background tasks right after having saved an entity will ensure fast updates so we can use up-to-date materialized views in queries almost immediately. Starting delayed background tasks before we save an entity will ensure the execution of background tasks as well as correct updates to the materialized view.

However we have to keep in mind that background tasks which start immediately after a save can get into conflicts as discussed above. So you might think: "Forget about starting background tasks after a save()", but remember we still have the background task started right before the save. This background task will clean up incorrectly updated materialized views.

The cleanup background tasks will fetch the latest photo and user info so that the materialized view will contain correctly denormalized properties afterwards even if the first background tasks got into update-conflicts.

Even if we get into the same conflict between a third update to a photo and a cleanup background task, this update starts its own delayed background task so that we've ensured a cleanup to come. So in the worst case scenario we have incorrectly updated materialized views which will get cleaned up soon. In a best case scenario we always have immediately updated materialized views. The important aspect here is that we'll always have correct materialized views.

Summarized, the following should be done:


In the last three posts (including this one) we described one possible method to handle JOINs for the to-one side on non-relational databases. Let's summarize the most important points:

This method can be implemented on App Engine and MongoDB (in combination with celery for example) as well as on other NoSQL databases.

It becomes clear that using JOINs in the to-one direction on non-relational databases is a mess to deal with. From the view point of a developer, it's far from optimal for the following reasons:

So is there a better solution than setting up the whole process by hand each time we need JOINs? We believe that there is a much more elegant way to do so. Our answer is django-dbindexer, which will use the method described in this blog post series so you can use JOINs without having to rethink your queries or to add denormalized fields to your models manually! Just tell django-dbindexer which JOINS you want to use and the indexer will take care of everything else. Stay tuned!