07 Jul 2024
Parallel EVM: BNB chain
This is a personal note for BNB chain-blog.
1. Blockchain fundamentals
1.1. Why is parallel EVM not easy
- Lack of visibility of potential transaction conflict.
- Blockchains experience transaction bursts, e.g., >70M transactions per day.
1.2. A Parallel EVM ideas
- Run multiple EVM instances concurrently on different threads.
- Execute transactions independently on each thread and later merge a finial state update.
- Parallel EVM scheme
1.3. Block STM algorithm
- Optimistic parallelism: assigns transactions to various threads.
- Software transaction memory (STM): detect conflicts when transactions try to modify the same shared state simultaneously.
- Conflict resolution: when conflicts are detected, the offending transactions are discarded without affecting the blockchain state and are re-executed.
2. BNB Parallel EVM 1.0: Infrastructure
- Proposal: BEP-130 (2022)
- Dispatcher: distributes transactions across threads to optimize throughput.
- Parallel execution engine: execute transactions independently on each thread.
- Local stateDB: each thread maintains a local stateDB to record state access.
- Conflict detection: detect conflicts and re-execute conflicting transactions.
- State commit: the finalized results are committed to the global state DB.
3. BNB Parallel EVM 2.0: Performance enhancement
- Dispatcher: combine both static and dynamic dispatch strategies.
- Execution engine: streaming pipeline to enable smooth transaction processing.
- Conflict detection: ensure data integrity while minimizing unnecessary re-execution.
- Memory: shared memory pools and light copying techniques to reduce memory footprint.
- The overall performance ranges from 20% to 50%.
4. BNB Parallel EVM 3.0: Production
4.1. Hint-based dispatcher
- leverages external hint providers to analyze transactions and generate predictions about potential state access conflicts.
- Simple hints include read/write state sets; advanced hints incorporate weak/strong ordering for optimal parallelism.
- Conflicting transactions are assigned to the same slot.
- Transactions with no conflicts are distributed across different slots.
- Conflict detector remains as a backup for handling unforeseen conflicts.
4.2. Seamless BNB chain ecosystem integration
- Modularization and reconstructing.
- Thorough testing and validation.
5. Comparison with other solutions
| Solutions | TX dependency check | Conflict resolution | StateDB optimization |
|---|---|---|---|
| BlockSTM | tracks at execution | re-execution | N/A |
| Polygon | minimal metadata solution | reduced re-execution | N/A |
| Monad | static analysis | reduced re-execution | Monad DB |
| Sei | tracks at execution | re-execution | SeiDB |
| Neon EVM and Solana Sealevel | contract provided | reduced re-execution | depends on Solana |
| BNBChain | hint info | reduced or eliminated re-execution | Thread local DB |
6. Other optimizations
- Opcode-level optimization: fine-tuning individual EVM instructions for maximum efficiency.
- Compilation optimization: JIT/AOT compilation paradigms; instruction-level parallelism (SIMD).
- Database sharding: distribute data across multiple databases.
- Concurrent node execution.