Optimization opportunity: use "to" in getOps query

[curran]

Currently, all ops for a document are loaded into memory when getOps is invoked, then filtered to exclude those ops before to.

sharedb-mongo/index.js

Line 362 in 5a7c674

self._getOps(collectionName, id, from, options, function(err, ops) {

There is an opportunity to optimize the amount of memory used, by querying for only the ops before the specified to value.

Related to share/sharedb#220

[gkubisa]

To be precise, the from param is still used to limit the number of ops loaded from the database. In most cases, eg when resolving conflicts, ShareDB needs to load all ops from a specific version up to the latest version, so the lack of efficient support for the to param is not a problem at all.

However, when loading a snapshot at a specific version, not supporting the to param at the database level is very inefficient.

Proposed Solution

First of all, we need to add an upper version limit to the MongoDB query here https://github.com/share/sharedb-mongo/blob/master/index.js#L543-L547. Unfortunately, this is not enough because it is possible to have more than one operation at the same version. Extraneous ops can be created, if a ShareDB server writes an op but fails to write a corresponding snapshot - MongoDB does not support transactions yet.

In the current implementation, the extraneous ops are filtered out by following the op links, starting from the snapshot. However, I think that instead of always starting from the snapshot, we could start from any older op, as long as the op version is not duplicated and the op version is lower than the snapshot version.

Considering that ops with a duplicate version are extremely rare, we wouldn't incur any overhead in most cases. However, if we find multiple ops at version to, we'd need to load an op with a higher version, until we reach an op with a non-duplicated version or the snapshot. We would then filter out unwanted ops as normal.

As an optimization for future queries and to remove redundant data, we should also remove extraneous ops whenever we come across one.

As a bonus, we could also allow retrieving ops by timestamps, instead of versions.

Would anyone be interested in implementing the above or has a better idea?

[alecgibson]

This was fixed in #68