Blog

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:

  • We have a materialized view (i.e. the model PhotoUserView) containing denormalized properties of users (i.e. gender) and denormalized properties of photos (i.e. popularity). This materialized view is used to emulate JOINs in the to-one direction. Instances of PhotoUserView have to be kept up to date.
  • If a user edits properties of a photo we have to start a background task in order to update all denormalized fields of the corresponding PhotoUserView entity
  • If a user changes his/her gender (or her hair color) we have to start background tasks in order to update the denormalized gender of all PhotoUserView entities which point to that specific user

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:

  • User edits a photo
  • Corresponding submit_view saves these changes
  • Web server crahses

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:

http://lh3.ggpht.com/_8v0Ka-uUQOY/TKsQr3CAOhI/AAAAAAAAANk/W1Y6qBG9Kes/Background%20tasks%20conflicts.jpg
  • At time t1 an update to a photo is being saved (via a submit from an user for example)
  • At t2 the background task 1 starts right after the save
  • Background task 1 fetches the data to be denormalized out of the database (photo and user). For some reason we have some delay after this
  • At t3 another update happens to the same photo
  • At t4 background task 2 starts and finishes before background task 1 does
  • Background task 1 finishes its updates to the materialized view using old data resulting in overwriting background task 2's updates

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.

http://lh6.ggpht.com/_8v0Ka-uUQOY/TKsgErRYmpI/AAAAAAAAAOo/i5LT4Zuq9Rw/Background%20tasks%20%20with%20big%20delays.jpg

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:

  • User's gender (hair color) changes
  • Photo's title changes
  • Background task 1 starts and only gets the user and the corresponding materialized view out of the database (in order to update denormalized_gender)
  • Background task 2 starts and only gets the photo and the same materialized view out of the database (in order to update denormalized_title)
  • Background task 1 saves updates to the materialized view i.e. changes denormalized_gender
  • Background task 2 saves updates to the materialized view i.e. changes denormalized_title overwriting changes by background task 1 i.e. the denormalized_gender

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.

http://lh3.ggpht.com/_8v0Ka-uUQOY/TJMq9RHWA4I/AAAAAAAAAJI/kN1bhp1oGEI/Background%20task%20conflict%20solved.png

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:

  • Always start background tasks before saving entities using a large enough delay. This has the nice side effect of cleaning up wrongly updated materialized views
  • Start background tasks after saving entities to ensure fast updates to the materialized view

Summary

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:

  • JOINs are achieved via denormalization using an additional model (the materialized view)
  • This solution comes with eventual consistency (in most cases no problem)
  • Doubles storage requirements (because of the materialized view) but storage is cheap
  • If the values of denormalized properties are allowed to change, we need background tasks

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:

  • For each model which requires JOINs you have to maintain materialized views by hand
  • You are forced to rethink your queries and to remember to formulate them using the denormalized fields on a different model (materialized view). Then you have to get the model actually queried for
  • Materialized views create dependencies between models (photos and users for example) which make them less reusable
  • Thus you are predestined to make bugs. The result is less productivity and much more pain while coding

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!