The design of RavenDB 4.0The cost of Load Document in indexing

time to read 7 min | 1351 words

LoadDocument in RavenDB is a really nice feature. It allows you to reach out to another document during indexing, and load its value. A simple example of that would be:

from p in docs.Pets
select new { Name = p.Name, OwnerName = LoadDocument(p.OwnerId).Name }

When we got the idea for LoadDocument, we were very excited, because it allowed us to solve some very tough problems.

Unfortunately, this also has some really nasty implementation issues. In particular, one of the promises we give for LoadDocument is that we’ll re-index the referencing document if the referenced document changed. In other words, if my wife changed her name, even though my document wasn’t changed, it will be re-indexed, my wife’s document will be loaded and the new name will end up in the index.

Now, consider what happens when there are two concurrent transactions. The first transaction happens during indexing, we try to load the owner document, which doesn’t exists, so we leave a record in place so force re-indexing when it is inserted, but at the same time, a new transaction is opened and the owner document is inserted. During the insert, it checks if there are any referencing documents, but since both transactions aren’t committed yet, they can’t see each other changes. And we end up with a bug. Resolving that took a bit of coordination between the two processes, which was hard to get right.

Another issue that we have is the fact that each LoadDocument call need to create a record of its existence, so we’ll know what documents require re-indexing. However, for large indexes that use LoadDocument, the number of entries there can be staggering, and impact the amount of time we have to delete an index, for example. It also force up to do a bit of work during document updates that is proportional to the number of documents referencing a particular document. In some cases, all documents in the database reference a single document, and an update to that document can take a very long time. In fact, we limit the amount of time that this can take to 30 seconds, and abort the update if it takes this long. This is one of the only cases where insert speed is impacted in RavenDB (we have a workaround to update the document without triggering re-indexing, of course).

So, overall, we have a really nice feature, but it has some serious drawbacks when you peel back the implementation details. In RavenDB 4.0, we have decided to try as much as possible to avoid having things like that, so we sat down and tried to think how we can get something like that working.

We have the following considerations:

  • All data must be scoped to the index level. Nothing that require multiple indexes to cooperate.
  • We cannot have any  global data, or have interactions between documents an indexing that require complex coordination.
  • We cannot use TouchDocument as a control mechanism any longer.
  • It should be as simple as we can get away with it.

The solution we came up with goes like this (a full walkthrough can be found after the explanation):

  • An index that uses LoadDocument cannot just look at the items in the collections it covers, it need to go over all documents.
    • We can probably get away with only scanning the documents from collections that we loaded documents from, but what if the document doesn’t exists yet? In that case, we need to scan all documents anyway.
    • We’ll have an overload of LoadDocument that specify the collection type (which we can auto fill from the client side based on the provided type) to optimize this.
  • A call to LoadDocument is going to record the relationship between the two documents, in the index’s own storage (Unlike before, we have no global tracking). Conceptually, you can think about that storage as the “references table”, with the source document key and the destination document key. In practice, we’ll use an optimal data structure for this, but it is easier if you imagine a table with those two columns.
  • Instead of using TouchDocument to modify documents etag (which requires us to mix indexing and documents operations), the index will keep track of two sets of etags. The first is the index’s own collection of documents it is indexing, and it is known as the “last indexed etag”. The second is the last etag of the documents that are being referenced via LoadDocument by this index, and is known as the “last referenced etag”.
  • When a document from a collection that is being referenced is updated, we’ll wake the index and check all the documents in that collections after the last referenced etag we have. For each of those, we’ll see if they have any references in the “references table”. If they don’t, there is nothing to do. If there is, we’ll reindex those documents immediately (see below for some optimization opportunities there).
  • The index will then update the last referenced etag it scanned.
  • Such an index will be considered non stale if both the last indexed etag and the last referenced etag are equal to the last document etag in the database.

Basically, we move the entire responsibility of updating the index from the database as a whole to just the index.

It also makes the index in question alone pay for those costs. And given that we have a separate “re-indexing” round, we can track the additional costs of such measure directly.

It is a lot to take in, so let me try to explain in detail. We start with the new index definition.

from p in docs.Pets
select new { Name = p.Name, OwnerName = LoadDocument(p.OwnerId, “People”).Name }

The first change is that the LoadDocument call is going to specify the collection of the loaded document (or no collection, if the document can come from any collection).

The index is going to keep track of the following details:

  • LastIndexedEtag – for the collection that this covers, in this case, the “Pets” collection.
  • LastReferencedEtag – for the collection(s) specified in the LoadDocument, in this case, the People collection.

We now have the following state in the database:

  • LastIndexedEtag is 10 for the Pets collection.
  • LastReferencedEtag is 0 for the People collection.
  • People/1’s etag is set to 12.
  • Pets/1’s etag is set to 7.
  • Pets/2’s etag is set to 11.

Now, when indexing, we are going to do the following steps:

  • For each of the collections we have setup tracking for, get all documents following the LastReferencedEtag
      • In this case, scan the People collection for all etags following 0.
    • For each of the resulting documents, check whatever there is are documents referencing that document.
      • In this case, people/1 is returned, and it is being referenced by pets/1 and pets/2.
      • Because the etag of pets/1 (7) is lower than the LastIndexedEtag (10), we need to index that right away.
      • The etag of pets/2 (11) is higher than the LastIndexedEtag (10), so we don’t index it.
    • After we are done scanning through the People collection, we update our LastReferencedEtag to the last item in the people collection (which would be 12).
  • We then continue to index the Pets collection normally.
    • We get pets/2, whose etag is 12 and index that, loading People/1 again. (This is why we could skip it previously).
    • Finally, we update our LastIndexedEtag to 12 (the last Pets document we indexed).

On the next batch of indexing, we’ll again scan the People collection for documents that have changed, and then the pets that changed, and so on.

Now, a document that is being referenced by many other documents will not require any additional work on our side. We’ll just re-index the documents referencing it, which is much better than the current state.

Note that this design ignores a few details, but this should paint the general outline.

More posts in "The design of RavenDB 4.0" series:

  1. (26 May 2016) The client side
  2. (24 May 2016) Replication from server side
  3. (20 May 2016) Getting RavenDB running on Linux
  4. (18 May 2016) The cost of Load Document in indexing
  5. (16 May 2016) You can’t see the map/reduce from all the trees
  6. (12 May 2016) Separation of indexes and documents
  7. (10 May 2016) Voron has a one track mind
  8. (05 May 2016) Physically segregating collections
  9. (03 May 2016) Making Lucene reliable
  10. (28 Apr 2016) The implications of the blittable format
  11. (26 Apr 2016) Voron takes flight
  12. (22 Apr 2016) Over the wire protocol
  13. (20 Apr 2016) We already got stuff out there
  14. (18 Apr 2016) The general idea