Contention-friendly database architecture for large documents and inner arrays

user_4102561 0
Viewed 172

Context

I have a database with a collection of documents using this schema (shortened schema because some data is irrelevant to my problem):

{
    title: string;
    order: number;
    ...
    ...
    ...
    modificationsHistory: HistoryEntry[];
    items: ListRow[];
    finalItems: ListRow[];
    ...
    ...
    ...
}

These documents can easily reach 100 or 200 kB, depending on the amount of items and finalItems that they hold. It's also very important that they are updated as fast as possible, with the smallest bandwidth usage possible.

This is inside a web application context, using Angular 9 and @angular/fire 6.0.0.

Problems

When the end user edits one item inside the object's item array, like editing just a property, reflecting that inside the database requires me to send the entire object, because firestore's update method doesn't support array indexes inside the field path, the only operations that can be done on arrays are adding or deleting an element as described inside documentation.

However, updating an element of the items array by sending the entire document creates poor performances for anyone without a good connection, which is the case for a lot of my users.

Second issue is that having everything in realtime inside one document makes collaboration hard in my case, because some of these elements can be edited by multiple users at the same time, which creates two issues:

  • Some write operations may fail due to too much contention on the document if two updates are made in the same second.
  • The updates are not atomic as we're sending the entire document at once, as it doesn't use transactions to avoid using bandwidth even more.

Solutions I already tried

Subcollections

Description

This was a very simple solution: create a subcollection for items, finalItems and modificationsHistory arrays, making them easy to edit as they now have their own ID so it's easy to reach them to update them.

Why it didn't work

Having a list with 10 finalItems, 30 items and 50 entries inside modificationsHistory means that I need to have a total of 4 listeners opened for one element to be listened entirely. Considering the fact that a user can have many of these elements opened at once, having several dozens of documents being listened creates an equally bad performance situation, probably even worse in a full user case.

It also means that if I want to update a big element with 100 items and I want to update half of them, it'll cost me one write operation per item, not to mention the amount of read operations needed to check permissions, etc, probably 3 per write so 150 read + 50 write just to update 50 items in an array.

Cloud Function to update the document

const {
  applyPatch
} = require('fast-json-patch');

function applyOffsets(data, entries) {
  entries.forEach(customEntry => {
    const explodedPath = customEntry.path.split('/');
    explodedPath.shift();
    let pointer = data;
    for (let fragment of explodedPath.slice(0, -1)) {
      pointer = pointer[fragment];
    }
    pointer[explodedPath[explodedPath.length - 1]] += customEntry.offset;
  });
  return data;
}

exports.updateList = functions.runWith(runtimeOpts).https.onCall((data, context) => {
  const listRef = firestore.collection('lists').doc(data.uid);
  return firestore.runTransaction(transaction => {
    return transaction.get(listRef).then(listDoc => {
      const list = listDoc.data();
      try {
        const [standard, custom] = JSON.parse(data.diff).reduce((acc, entry) => {
          if (entry.custom) {
            acc[1].push(entry);
          } else {
            acc[0].push(entry);
          }
          return acc;
        }, [
          [],
          []
        ]);
        applyPatch(list, standard);
        applyOffsets(list, custom);
        transaction.set(listRef, list);
      } catch (e) {
        console.log(data.diff);
      }
    });
  });
});

Description

Using a diff library, I was making a diff between previous document and the new updated one, and sending this diff to a GCF that was operating the update using the transaction API.

Benefits of this approach being that since transaction happens inside GCF, it's super fast and doesn't consume too much bandwidth, plus the update only requires a diff to be sent, not the entire document anymore.

Why it didn't work

In reality, the cloud function was really slow and some updates were taking over 2 seconds to be made, they could also fail due to contention, without firestore connector knowing it, so no possibility to ensure data integrity in this case.

I will be edited accordingly to add more solutions if I find other stuff to try

Question

I feel like I'm missing something, like if firestore had something I just didn't know at all that could solve my use case, but I can't figure out what it is, maybe my previously tested solutions were badly implemented or I missed something important. What did I miss? Is it even possible to achieve what I want to do? I am open to data remodeling, query changes, anything, as it's mostly for learning purpose.

angularfire2 google-cloud-firestore
2 Answers

Your diff-approach appeared mostly sensible, details aside.

You should store items inline, but defer modificationsHistory into a sub collection. For the entire root document, record which elements of modificationsHistory have been merged yet (by timestamp should suffice), and all elements not merged yet, you have to re-apply individually on each client, querying with aforementioned timestamp.

Each entry in modificationsHistory should not describe a single diff, but whenever possible a set of diffs.

Apply changes from modificationsHistory collections onto items in batch, deferred via GCF. You may defer this arbitrarily far, and you may want to exclude modifications performed only in the last few seconds, to account for not established consistency in Firestore. There is no risk of contention, that way.

Cleanup from the modificationsHistory collection has to be deferred even further, until you can be sure that no client has still access to an older revision of the root document. Especially if you consider that the client is not strictly required to update the root document when the listener is triggered.

You may need to reconstruct the patch stack on the client side if modificationsHistory changes in unexpected ways due to eventual consistency constraints. E.g. if you have a total order in the set of patches, you need to re-apply the patch stack from base image if the collection unexpectedly suddenly contains "older" patches unknown to the client before.

All in all, you should be able avoid frequent updates all together, and limit this solely to inserts into to modificationsHistory sub-collection. With bandwidth requirements not exceeding the cost of fetching the entire document once, plus streaming the collection of not-yet-applied patches. No contention expected.

You can tweak for how long clients may ignore hard updates to the root document, and how many changes they may batch client-side before submitting a new diff. Latter is also a tradeof with regard to how many documents another client has to fetch initially, with regard to max-documents-per-query limits.

If you require other information which are likely to suffer from contention, like list of users currently having a specific document open, that should go into sub-collections as well.

Should the latency for seeing changes by other users eventually turn out to be unacceptable, you may opt for an additional, real-time capable data channel for distribution of patches on a specific document. ActiveMQ or some other message broker operated on dedicated resources, running independently from FireStore.

user_28793250

You should be able to reduce the bandwidth required to update your documents by using Maps instead of Arrays to store your data. This would allow you to send only the item that is being updated using its key.

I don't know how involved this would be for you to change, but it sounds like less work than the other options.

You said that it's not impossible for your documents to reach 200kb individually. It would be good to keep in mind that Firestore limits document size to 1mb. If you plan on supporting documents beyond that, you will need to find a way to fragment the data.

Regarding your contention issues... You might consider a system that "locks" the document and prevents it from receiving updates while another user is attempting to save. You could use a simple message system built with websockets or Firebase FCM to do this. A client would subscribe to the document's channel, and publish when they are attempting an update. Other clients would then receive a notice that the document is being updated and have to wait before they can save their own changes.

Also, I don't know what the contents of modificationsHistory look like, but that sounds to me like the type of data that you might keep in a subcollection instead.

Of the solutions you tried, the subcollection seems like the most scalable to me. You could look into the possibility of not using onSnapshot listeners and instead create your own event system to notify clients of changes. I suppose it could work similar to the "locking" system I mentioned above. A client sends an event when it updates an item belonging to a document. Other clients subscribed to that document's channel will know to check the database for the newest version.

user_34210280
Related