SharedTree Batch vs Single Synchronous Transaction in EditableTree

[milanro]

EditableTree so far offers only automatic transaction per command. No batch API is available for the case, that we want to change different places in the tree at once. This has the consistency and the performance impact.

I recorded the video showing these impacts:
I have a table with rows and cells. At the beginning, all cells are set to 0. I want to increase the number in each cell to 5 by executing cell++ in each cell and repeating it 5 times. I execute this 3 times within 1 transaction and then once so that each cell++ is executed in it's own transaction. The execution at the action site takes relatively the same time. However the receiving client reacts differently at single / multi transaction. Single transaction brings the receiving client from consistent state (all cells 0) to consistent state (all cells 5) almost immediately. Multi transactions are slowly increasing numbers at cells, the inconsistent states are visible and the performance is poor.

SharedTreeBatchTx.webm

I implemented a very simple POC to enable batch transactions at Editable Tree. The idea is to have the member attribute transactionContext: { editor: DefaultEditBuilder }| undefined in the ProxyContext (which implements EditableTreeContext). If that attribute is not undefined, the runTransaction method does not open the new transaction but it rather uses the editor from the transactionContext. There is an entry method in the EditableTreeContext.editInSynchronousTransaction which opens the transaction, sets it to transactionContext and then calls the code passed via parameter.

The code change in editableTreeContext.ts at the ProxyContext class is like :

    private transactionContext: { editor: DefaultEditBuilder } | undefined = undefined;

    public editInSynchronousTransaction(edits: () => void): boolean {
        assert(
            this.transactionCheckout !== undefined,
            0x45a /* `transactionCheckout` is required to edit the EditableTree */,
        );
        const result = runSynchronousTransaction(
            this.transactionCheckout,
            (forest: IForestSubscription, editor: DefaultEditBuilder) => {
                try {
                    this.transactionContext = { editor };
                    edits();
                    return TransactionResult.Apply;
                } finally {
                    this.transactionContext = undefined;
                }
            },
        );
        return result === TransactionResult.Apply;
    }

    private runTransaction(transaction: (editor: DefaultEditBuilder) => void): boolean {
        assert(
            this.transactionCheckout !== undefined,
            0x45a /* `transactionCheckout` is required to edit the EditableTree */,
        );
        let result;
        if (this.transactionContext !== undefined) {
            transaction(this.transactionContext.editor);
            result = TransactionResult.Apply;
        } else {
            result = runSynchronousTransaction(
                this.transactionCheckout,
                (forest: IForestSubscription, editor: DefaultEditBuilder) => {
                    transaction(editor);
                    return TransactionResult.Apply;
                },
            );
        }
        return result === TransactionResult.Apply;
    }

Then there is an addition in the editableTreeContext.ts at the EditableTreeContext interface :

/**
     * This method runs the code specified by the edits parameter in the synchronous transaction.
     * The editing code is supposed to perform edits only by calling edit methods within this instance,
     * such as setValue, insertNodes etc.
     * @param edits - The code calling edit methods within this instance.
     * @returns True if transaction was applied, false if it was aborted.
     */
    editInSynchronousTransaction(edits: () => void): boolean;

[sharptrip]

@milanro Hi, unfortunately, it is not so easy. Even though it might work for some simple cases (like updating the value of the same primitive node), it won't work in general. The EditableTree does not hold any state (in a form of a view or something like that) of the data, completely relying on the forest data underneath. That said, if we just collect "commands" without actually executing them, this will not change the state of the tree, and if any next "command" should rely on that state (e.g., if we delete a field and create it again in the same transaction), it will get initial state to rely on without taking the first "command" into account. And that's only at a very shallow level, there is much more to consider.

So, as it was once said in a discussion, this feature needs to be well thought out and designed (plus, there are at least to possible approaches we could follow, so this has to be decided as well). Unfortunately, it can't be solved just by some refactoring of the way the EditableTree works with the transactions.

[milanro]

@sharptrip

That said, if we just collect "commands" without actually executing them, this will not change the state of the tree, and if any next "command" should rely on that state

Do you refer to the point that if I run the code

runInTransation ((forest,editor) => {
field1.delete(0); // delete node with value 10
console.log(field1[0].value) // you will get still 10 because command was not yet applied to forest
}

because the change happens at first when transaction is executed as the execution of commands is only the collecting of changes? That means that you could theoretically execute modification commands but not read commands because modification commands are executed at the transaction when all commands are already collected. You are pointing to the delete and insert of the node. It looks to me (but I might be wrong) that this should work.

field1.delete(0); // deleting 10, executed at the applying the transaction at the end
field1.insert(5); // executed after the delete command

Because insert command is really executed at first after the delete at the forest.

but if I do
field1.delete(0); // deleting 10
field1.insert(5);
console.log(field1[0].value) // I would still get 10

Am I right with my understanding?
Does this also mean that the method SharedTree.runInTransation is not robust and will be dropped?

In case I understand the problem correctly, I see the challenges. In that case, the robust database backend is to be designed where the command immediately changes the underlying data and beside this, it generates the change (REDO). We can get inspired by databases like oracle which generates UNDO for each change.

[sharptrip]

@milanro No, I mean something totally different. When you try to insert the field after it been deleted, the API checks if the field exists before inserting (this is required, as otherwise it could lead to unwanted side effects). Since we didn't actually change the tree, the deletion is unknown to the API at that point, so it gets back a hint that the field exists, and considers e.g. to replace it instead of creating a new one. This leads to the wrong changes, since the first commands deletes the field, whereas the second tries to replace it i.e. to delete again the deleted field. This is just an example of what could go wrong, there are much more.

[milanro]

@sharptrip I guess that it is similar case, the issue happens on read as we read outdated data and make the wrong decision (delete before insert). In this case the automatism makes things even worse (here we actually deal not with insert but with upsert ). In any case, I believe that I understand the challenge, explicit or implicit (framework) reads return wrong answers. And I understand that addressing this will need changes in the storage structures. I must say that I would be happy to participate on the design talks if possible.

[milanro]

@sharptrip I am planning to deep dive to transaction processing. @CraigMacomber suggested that the commands within the transaction are applied to the ObjectForest immediately, not just at the TransactionResult.Apply return. I looked at the simple insert at first and indeed it looks like the change, when command is executed inside the runInTransaction method, is at first appended to the changes sequence (for further flushing to fluid server) but just after that it is applied to the ObjectForest so that when command is finished, the ObjectForest is reflecting the change. The code looks to be highly plugable so this action is not perfectly obvious but I believe that it happens somewhere at progressiveEditBuilder.applyChange at the class ProgressiveEditBuilderBase.

    applyChange(change) {
        this.changes.push(change);
        this.changeFamily.rebaser.rebaseAnchors(this.anchorSet, change);
        this.changeReceiver(change);
    }

The method call this.changeReceiver(change); looks to apply the change to the forest.
This is the first sight, need to dig deeper because it looks to me strange that this change should be applied in the Builder (Builder pattern), maybe I am wrong and only some temporary state is built here.

If this is the expected and implemented behavior, I expect that solution prototyped in this ticket could theoretically work after all (unless other challenges are found). I will deep dive next week and test more complicated cases, the multi-command transaction is essential for us (I am still talking about synchronous transaction).

Here is the stack

moveIn (objectForest.js:70)
onInsert (objectForest.js:78)
firstPass (visitDelta.js:126)
visitFieldMarks (visitDelta.js:75)
visitModify (visitDelta.js:89)
firstPass (visitDelta.js:122)
visitFieldMarks (visitDelta.js:75)
visitModify (visitDelta.js:89)
firstPass (visitDelta.js:122)
visitFieldMarks (visitDelta.js:75)
visitModify (visitDelta.js:89)
firstPass (visitDelta.js:122)
visitFieldMarks (visitDelta.js:75)
visitDelta (visitDelta.js:67)
applyDelta (objectForest.js:112)
(anonymous) (defaultTransaction.js:21)
applyChange (progressiveEditBuilder.js:20)
submitChange (modularChangeFamily.js:259)
insert (defaultChangeFamily.js:66)
(anonymous) (editableTreeContext.js:131)
runTransaction (editableTreeContext.js:151)
insertNodes (editableTreeContext.js:129)
insertNodes (editableTree.js:459)
(anonymous) (editableTree.js:524)
setCellValue (App.tsx:446)

[sharptrip]

@sharptrip I am planning to deep dive to transaction processing. @CraigMacomber suggested that the commands within the transaction are applied to the ObjectForest immediately...

@milanro I have prepared a PoC, which is a compilation of code from runSynchronousTransaction, ModularChangeFamily, editManager and so on. The code there is totally suboptimal and might very much be even wrong at many places, but it works somehow.

sharptrip#21

So, basically, what this code does is that it keeps receiving and applying changes from the EditableTree and to the Forest while transaction is "opened", but defers a submitEdit call, which seems to be a trigger for a client to send the changes to space.

The how-to use it could be found in a new test case.

It would be really nice if you could adopt it in your app and see how it works now.

[milanro]

@sharptrip does this mean that the functionality prior your POC did not work as you describe in your POC?

I understood the current tx implementation (pre-POC) the same way, so far my experience is that the local changes are applied on the fly to the local tree / forest but not populated to fluid server until commit (TransactionResult.Apply) is executed. This looks to me partially correct, only commit should allow the changes to leave the client. What looks to me incorrect is that locally, it looks no rollback to previous state to happen on rollback (TransactionResult.Abort). It looks like it is expected to reload the DDS on abort at present.

Is this what did not work and what you introduced with your POC? I will definitely go through your changes and give you an opinion. Thanks for looking into this.

[sharptrip]

What looks to me incorrect is that locally, it looks no rollback to previous state to happen on rollback (TransactionResult.Abort). It looks like it is expected to reload the DDS on abort at present.

@milanro This code below (a rollback de facto) is executed unconditionally disregards if it should be commited (result === TransactionResult.Apply) or rolled back (result === TransactionResult.Abort), so I guess that's correct.

FluidFramework/packages/dds/tree/src/feature-libraries/defaultTransaction.ts

Lines 50 to 58 in 83bd57f

	{
	// Roll back changes
	for (const inverse of inverses) {
	// TODO: maybe unify logic to edit forest and its anchors here with that in ProgressiveEditBuilder.
	// TODO: update schema in addition to anchors and tree data (in both places).
	changeFamily.rebaser.rebaseAnchors(forest.anchors, inverse);
	forest.applyDelta(changeFamily.intoDelta(inverse, repairStore));
	}
	}

The main conceptional difference between my PR and runSynchronousTransaction is that in my code the following part is not executed after each and every change, but wrapped into commitTransaction allowing the users to decide, when to call it and close the transaction.

FluidFramework/packages/dds/tree/src/feature-libraries/defaultTransaction.ts

Lines 60 to 63 in 83bd57f

	if (result === TransactionResult.Apply) {
	const edit = changeFamily.rebaser.compose(changes.map((c) => makeAnonChange(c)));
	submitEdit(edit);
	}

Btw, in my PR there is no such thing like rollbackTransaction. I'll add a placeholder for it.

[milanro]

@milanro This code below (a rollback de facto) is executed unconditionally disregards if it should be commited (result === TransactionResult.Apply) or rolled back (result === TransactionResult.Abort), so I guess that's correct.

I debugged this code long ago and it looked not to work properly. It was executed but inverse looked to be generated incorrectly. I tested it for a simple value change and the inverse changeset did not contain the previous value which resulted in the no change at all. This is possibly already fixed.

These are notes, which I made in my internal documentation :

Transactions look to revert changes at transaction.ts# runSynchronousTransaction

• The revert however does not look to work, after revert the value still persists
• Abort does not post the values to fluid but local changes persist
• Inverse does not look to work for setValue

As I said, a lot changed since then so I will go through the present code and find out how it works right now.

On the other hand, even if this would work as expected, I still believe that it is not correct. On commit, the values should not be rolled back after the successful transaction end, it would be strange that the values would be reverted and then fixed back by obtaining the changes from fluid server.

I see the comment :

    // TODO: in the non-abort case, optimize this to not rollback the edit,
    // then reapply it (when the local edit is added) when possible.

I would say that it is not even optimize but bugfix.

[sharptrip]

@milanro I have updated the PR to use EditManager (i.e. delegate change handling to the SharedTree and co.)

In addition, here is a new inspector version including transactions. By playing with it, I found some interesting issues revealed. sharptrip#22

[microsoft-github-policy-service]

This issue has been automatically marked as stale because it has had no activity for 180 days. It will be closed if no further activity occurs within 8 days of this comment. Thank you for your contributions to Fluid Framework!