[backup] #9012,[diem_vm] #8923(129)

[Nirish133]

[backup] replay-verify CLI tool #9012

Motivation

For use by VM compatilibity tests. Restores proper state snapshot, on top of which replays desired range of transactions, to comfirm compatibilities with the latest software.

Test Plan

CI/CD test covers the test cases.

[diem_vm] Implemented a standalone parallel transaction executor #8923

Motivation

This PR aims to implement a standalone version of parallel executor that we will use in the diem network. The newly introduced parallel_executor crate will serve as the abstract scheduler and executor for parallel and have zero dependencies to diem/move components. The structure of the package will look like following:

• src/task.rs This is the file that defines the type of transaction that could be parallelly processed by this executor and the single threaded executor for running such transaction.

• src/error.rs Defines the error and result type of parallel execution.

• src/scheduler.rs The naive scheduler that tracks transaction dependencies and task dispatcher for all threads.

• src/executor.rs The actual orchestration of the computation: spawn threads to parallel process transactions that are passed in.

• src/proptest_types Defines the proptest based testing and bencher strategy

  • types.rs Defines a naive transaction type that implements all traits required by parallel executor and its sequential
    computation baseline.
  • tests.rs Defines a number of proptest to test the correctness of the scheduling algorithm
  • bench.rs Generates random transactions to be executed and test the throughput of the system under trivial payloads.
    Executing each transaction could yield one of the following results:

1. Success: The transaction finished its execution with output.
2. SkipRest: The transaction finished its execution with output, but the executor will drop the execution result of any transaction that comes after it.
3. Abort: The transaction execution failed with non recoverable error. The executor will need to propagate such error to its caller
4. Retry: The transaction reads from a key that is not yet computed. The executor will need to re-execute this transaction when that key is assigned.

Note that for either SkipRest or Abort state, the executor guarantees to return the first transaction in the list that causes such status, regardless of the scheduling order.

Test Plan

A proptest strategy is implemented for the executor. The baic setup is following:

We randomly generate 100 distinct keys as a key universe. Then we randomly generate 3000 transactions where each of the transaction will randomly pick 10 keys they are estimated to write to, and will actually write to a half of those keys. Each transaction will also read a few keys and test if the value they see is the same as the sequential execution.

Based on the basic setup, we then randomly tell some of those transactions to return SkipRest or Abort signal to force the early termination of the algorithm. We then check if the termination is indeed at the right index (only the first of those transactions should matter for the scheduler).

We also tested the scenario when read set estimation is imprecise: the read inferencer will randomly drop a key that a transaction will read from, and make sure the system won't halt in such scenario.

Other than the proptest, we also implemented a bencher to test the system's raw throughput on those naive transaction, here's the result:

random_benches time: [73.161 ms 74.892 ms 76.656 ms]
The number reflects the time spent on processing 10k transactions generated in the previous setup described.

[dhaneshacn]

/canary

[bors-diem]

💔 Test Failed - ci-test

[ankitkacn]

/canary

[bors-diem]

💔 Test Failed - ci-test

[Nirish133]

/canary

[bors-diem]

💔 Test Failed - ci-test

[Nirish133]

Closing this PR due to merge issues