Aggregators: How sequential workloads are executed in parallel on the Aptos Blockchain

Aptos Labs, has designed a new Move feature called Aggregators, which allows parallel execution of smart contracts on the Aptos Blockchain even in the presence of read-write conflicts. The Aptos Network has successfully used Aggregators to track the total native token supply since its mainnet launch. Even though supply is modified by every transaction, due to Aggregators, it does not affect parallelism. With the recent AIP-43, Aggregators can also be used by collections of digital assets with limited supply (e.g., NFTs), dramatically increasing the speed of minting. As demonstrated in the latest previewnet, 1M NFTs on Aptos can be minted in under 90 seconds by leveraging Aggregators.

Parallel execution background

Block-STM — the parallel execution engine powering Aptos — is based on optimistic concurrency and multi-version data structures to execute transactions speculatively in parallel. If the speculative execution of some transaction is incorrect, Block-STM detects it, aborts the transaction, and re-executes it later.
The performance of any parallel engine such as Block-STM heavily depends on the workload. In particular, the amount of read-write conflicts. For example, consider two ordered transactions: a transfer from Alice to Bob followed by a transfer from Carol to David. These two transactions are commutative because both read- and write-sets for these transactions are disjoint. Thus, both can be executed in parallel.
Now consider another pair of ordered transactions: a transfer from Alice to Bob followed by a transfer from Bob to Carol. Block-STM can speculatively execute the second transfer first, and then detect a conflict with an earlier transaction (transfer from Alice to Bob). This is because the second transaction has read Bob’s balance while the first transaction has not updated it yet. As a result, the transaction that transfers some tokens from Bob to Carol is aborted and later re-executed when the transfer from Alice to Bob is completed.

Sequential workloads

Contended workloads with many read-write conflicts cannot be efficiently executed in parallel. Sequential workloads are an extreme case in which all transactions conflict with each other. In this case, sequential execution of the transactions is inherently the best approach. Unfortunately, there are multiple blockchain use cases when the workload can be sequential, which we explore below.
Supply and balance counters
Many blockchains burn a fraction of transaction fees. As a result, every transaction implicitly updates the total supply of the native token, making all transactions conflict.

This way even simple peer-to-peer non-conflicting transfers become a sequential workload due to read-write conflict on the supply counter. This is a common issue, which forces some blockchains to stop tracking the total supply of native currency in smart contracts. Instead, to allow for parallelism, the supply is tracked by the protocol implementation, e.g., using an atomic counter.
For collections of digital assets such as Non-Fungible Tokens (NFTs), the collection size is usually tracked as well. For example, these collections can be used as tickets for music festivals. Because there is a limited number of tickets, there is a limited number of NFTs to ever exist.
Similar to tracking the total supply of the native token, the size of the NFT collection needs to be updated by every transaction that mints or burns a token. Additionally, it is crucial that the number of minted NFTs do not exceed the size of the collection fixed by its creator.

Under these constraints, NFTs can only be minted sequentially, significantly reducing the throughput of the network. To the best of our knowledge, many blockchains struggle to mint large volumes of NFTs fast, taking hours instead.
Finally, another source of read-write conflicts is account balance because every transaction has to pay a fee for execution. The fee is subtracted from the account balance, and so all transactions with the same fee payer conflict with each other. This prevents single-sender parallelism, where one account sends a burst of transactions, which can be important for applications such as gaming.

Indexing and naming of Non-Fungible Tokens
NFTs are usually sequentially indexed based on when they were minted. They also have a name that can include the index, e.g., “Star #17”. This way, even if the NFT collection does not track its size, avoiding read-write conflicts on the size counter, tokens cannot be minted in parallel because indexing introduces another sequential bottleneck.

The Aptos magic
To address the issue above, engineers at Aptos Labs proposed a Move feature called Aggregators in AIP-47 that allows the Aptos Network to execute in parallel workloads that would otherwise be sequential.

Observation

Certain workloads that look sequential do not have many read-write conflicts. Also, these conflicts do not have a significant impact on the results of transaction execution. The conflicts can be avoided by delaying the reads from the blockchain state and deferring the writes back to the state.
The conflicting parts of transactions can be captured and their execution result can be speculatively predicted instead. As a result, the main part of a transaction can be executed fully in parallel. Here are a few examples.
Parallel aggregation by postponing reads
Instead of updating a counter (e.g., the native token supply or the size of NFT collection), one can leverage the multi-version data structures used by Block-STM to record this update without applying it yet.