Implement rollbacks for finalize state

[raychu86]

Motivation

This PR implements rollbacks for finalize state using a new RollbackOperation and RollbackStore. Each FinalizeOperation has a corresponding RollbackOperation

The procedure is as follows:

1. FinalizeStore operations (initialize_mapping, insert_key_value, update_key_value, etc.) will now return both the FinalizeOperation and the RollbackOperation corresponding to the finalize operation.

2. finalize_deployment and finalize_execution will now also return the list of RollbackOperations that correspond to their applied FinalizeOperations.

3. In addition to performing the finalize operations, VM::atomic_finalize will now store the rollback operations into the RollbackStore.

4. If VM::add_next_block fails for whatever reason, we can rollback the block and the committed finalize operations accordingly.

Note: As we commit blocks to history, we can clear the RollbackStore of the RollbackOperations that have been deemed "old enough". This will help to save disk space as we continue to add blocks.

Test Plan

Tests have been added to check that the state can be rolled back properly in FinalizeStore.

TODO

• [ ] Write integration tests for rolling back blocks/finalize state in VM::add_next_block.

[zhiqiangxu]

Is it possible to do it this way:

snapshot := pendingState.Snapshot()
...
pendingState.RevertToSnapshot(snapshot)

This is how ethereum does rollback.

[howardwu]

@zhiqiangxu @ljedrz is there a convenient way to snapshot() with RocksDB? (that is fast enough to call in consensus)

I think this rollback approach effectively implements the same snapshot mechanism.

[zhiqiangxu]

@howardwu IMO there's no need to rely on RocksDB, snarkVM could maintain a journal internally for each change, the snapshot is basically an index of the change, and what RevertToSnapshot(snapshot) does is to revert the change from latest index to snapshot.

[ljedrz]

If I understand correctly, we need to be able to roll back several operations, and I'm assuming that the rollbacks should still be doable even if the node is shut down in the meantime (at least for the RocksDB impl). Judging by the current implementation, we are also interested in being able to do it in a "typed" fashion, i.e. not just save entire current states of storage and roll back by an N number of snapshots, but roll back some specific operations.

As for the snapshotting mechanism native to RocksDB, there are 2 related entities:

• a Snapshot (more docs)
• a Checkpoint (more docs)

And both are designed with a different purpose in mind; the Snapshot is fast and provides the means to view database entries that had existed at the point of its creation, but it can't be rolled back to or stored, while the Checkpoint is slower (~2.5ms compared to ~2µs in a 338MB database I tested them on), and creates a new directory in the filesystem that can later be opened and used as a standalone database.

Rollbacks are only possible with the latter, but they may become costly, both performance- and disk-wise (even though hardlinks are used as much as possible); using the Checkpoint would most likely also force us to reopen all of the storage-related objects, which would be quite tricky.

The simplest general approach to rollbacks I can see here is to store a specific number of IndexMap indices in case of the MemoryMap and to save the same number of WriteBatch objects (of which ideally there would only be one per block) in case of the DataMap (though I'm assuming we're normally only ever adding or updating records - it wouldn't allow us to roll back deletions). A rollback would then cause map truncations in the former, and the reversal of the WriteBatches in the latter.

This approach, however, is type-agnostic, and doesn't care about what is being rolled back, only to which point in time.