Previously, once a work tree was constructed with an initial commit, the only way to evolve its state was by applying operations. This was problematic because after a long period of collaboration, an unbounded number of operations could accumulate, which made it expensive to fetch and apply operations when joining the work tree. This PR addresses the situation by dividing the operation history into epochs, each of which builds forward from a commit in the underlying Git repository.
Conceptually, epochs are similar to commits, but are open to real time evolution as additional operations are applied. The diagram below demonstrates how they fit into the existing Git mental model:
In the diagram, three separate epochs all start at commit A, each associated with a different branch. In branches foo and bar, epochs 0 and 3 are inactive. This means that new commits have been created on those branches. Going forward, we can associate commits with the epochs that preceded them to enable history replay. Epoch 5, depicted in green, is being actively edited, as are epochs 2 and 4, which are based off of different commits.
In this first PR related to epochs, we've laid down the basic infrastructure needed for a work tree to switch between epochs. Though this PR introduces epochs, the Epoch struct it introduces is mostly just renamed from the previous WorkTree implementation. The WorkTree is now a wrapper that forwards requests to the current epoch and handles switching between epochs.
Previously, Memo was only exposed a synchronous API and relied on the client to perform all I/O. This synchronous API continues to exist internally within the Epoch implementation, but the public API is now asynchronous in multiple places. The WorkTree now accepts a GitProvider trait object from which it can request the base entries for a given commit oid or the text of a file given a commit oid and a path. Because most providers will need to perform I/O to service these requests, these methods are expected to return streams and futures from the futures crate. Similarly, several methods on WorkTree now also return futures or streams when they may require interaction with the Git provider. In Memo JS, we can accept and return asynchronous iterators and promises and translate them to the relevant objects from the futures crate via adaptors. This allows the JS event loop to drive execution of our streams and futures, avoiding the need for an explicit executor in Memo JS. For the daemon, we can drive these futures with the Tokio event loop.
The most interesting async code introduced in this PR is the SwitchEpochs future, which is returned whenever we want to reset the work tree to a different HEAD. We can perform a reset following a commit or simply to express a hard or soft reset in the repository. When async/await support stabilizes it will be easier to implement this kind of async routine in higher-level code, but for now we implement the Future trait directly with a custom poll method. When polling the future, we first need to stream in base entries for the new epoch. Once this is done, for each open buffer in the current epoch, we need to open a corresponding buffer in the epoch to which we are switching. We rely on path correspondence to match up files between the two epochs, which is imperfect but no worse than the typical text editor does in the face of Git operations.
It's also worth noting that this PR changes the JS interface to the library quite a bit. We now expose a higher level API. As mentioned above, you instantiate the WorkTree with a GitProvider. You also receive Buffer objects when you call openTextFile, which have a getText and edit method as well as an onChange method to allow you to subscribe to changes. Finally, all returned operations are now wrapped in an OperationEnvelope that associates each base64-encoded operation with the replicaId and replicaTimestamp of its associated epoch. These need to be used as a key to group and sort stored operations in the database.
Going forward, there are still a few improvements we'd like to land.
When resetting, we may be left with buffers corresponding to paths that don't exist in the new epoch. In the current implementation, each replica will create its own duplicate of these orphaned buffers. We need to enhance the epoch change operation to include a mapping for these orphaned buffers generated by the replica that initiates the resets so we can avoid duplication.
We currently discard all changes that are concurrent to the reset operation. The number of discarded changes should be small, since it is bounded by the latency of the network connections between participants. For user-initiated Git operations such as commits and resets, this kind of data loss is acceptable in the short term. However, we also plan to use epochs to support background "checkpoint" operations to put an upper bound on the number of operations participants need to download when joining the collaboration. When these checkpoints are occurring in the background, data loss will be unacceptable. We have a plan for avoiding it where we capture a version vector when performing the reset that allows us to determine which operations were concurrent upon receiving the reset.
Previously, once a work tree was constructed with an initial commit, the only way to evolve its state was by applying operations. This was problematic because after a long period of collaboration, an unbounded number of operations could accumulate, which made it expensive to fetch and apply operations when joining the work tree. This PR addresses the situation by dividing the operation history into epochs, each of which builds forward from a commit in the underlying Git repository.
Conceptually, epochs are similar to commits, but are open to real time evolution as additional operations are applied. The diagram below demonstrates how they fit into the existing Git mental model:
In the diagram, three separate epochs all start at commit A, each associated with a different branch. In branches
fooandbar, epochs 0 and 3 are inactive. This means that new commits have been created on those branches. Going forward, we can associate commits with the epochs that preceded them to enable history replay. Epoch 5, depicted in green, is being actively edited, as are epochs 2 and 4, which are based off of different commits.In this first PR related to epochs, we've laid down the basic infrastructure needed for a work tree to switch between epochs. Though this PR introduces epochs, the
Epochstruct it introduces is mostly just renamed from the previousWorkTreeimplementation. TheWorkTreeis now a wrapper that forwards requests to the current epoch and handles switching between epochs.Previously, Memo was only exposed a synchronous API and relied on the client to perform all I/O. This synchronous API continues to exist internally within the
Epochimplementation, but the public API is now asynchronous in multiple places. TheWorkTreenow accepts aGitProvidertrait object from which it can request the base entries for a given commit oid or the text of a file given a commit oid and a path. Because most providers will need to perform I/O to service these requests, these methods are expected to return streams and futures from thefuturescrate. Similarly, several methods onWorkTreenow also return futures or streams when they may require interaction with the Git provider. In Memo JS, we can accept and return asynchronous iterators and promises and translate them to the relevant objects from thefuturescrate via adaptors. This allows the JS event loop to drive execution of our streams and futures, avoiding the need for an explicit executor in Memo JS. For the daemon, we can drive these futures with the Tokio event loop.The most interesting async code introduced in this PR is the
SwitchEpochsfuture, which is returned whenever we want toresetthe work tree to a different HEAD. We can perform a reset following a commit or simply to express a hard or soft reset in the repository. When async/await support stabilizes it will be easier to implement this kind of async routine in higher-level code, but for now we implement theFuturetrait directly with a custompollmethod. When polling the future, we first need to stream in base entries for the new epoch. Once this is done, for each open buffer in the current epoch, we need to open a corresponding buffer in the epoch to which we are switching. We rely on path correspondence to match up files between the two epochs, which is imperfect but no worse than the typical text editor does in the face of Git operations.It's also worth noting that this PR changes the JS interface to the library quite a bit. We now expose a higher level API. As mentioned above, you instantiate the
WorkTreewith aGitProvider. You also receiveBufferobjects when you callopenTextFile, which have agetTextandeditmethod as well as anonChangemethod to allow you to subscribe to changes. Finally, all returned operations are now wrapped in anOperationEnvelopethat associates each base64-encoded operation with thereplicaIdandreplicaTimestampof its associated epoch. These need to be used as a key to group and sort stored operations in the database.Going forward, there are still a few improvements we'd like to land.
When resetting, we may be left with buffers corresponding to paths that don't exist in the new epoch. In the current implementation, each replica will create its own duplicate of these orphaned buffers. We need to enhance the epoch change operation to include a mapping for these orphaned buffers generated by the replica that initiates the resets so we can avoid duplication.
We currently discard all changes that are concurrent to the reset operation. The number of discarded changes should be small, since it is bounded by the latency of the network connections between participants. For user-initiated Git operations such as commits and resets, this kind of data loss is acceptable in the short term. However, we also plan to use epochs to support background "checkpoint" operations to put an upper bound on the number of operations participants need to download when joining the collaboration. When these checkpoints are occurring in the background, data loss will be unacceptable. We have a plan for avoiding it where we capture a version vector when performing the reset that allows us to determine which operations were concurrent upon receiving the reset.
Before merging:
/cc @as-cii @probablycorey @joshaber @jeffrafter @asheren @miskander