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

By George Mitenkov, Satya Vusirikala, Igor Kabiljo, Alexander Spiegelman, and Rati Gelashvili

Aptos Labs

Published in

Aptos

10 min readDec 20, 2023

By George Mitenkov, Satya Vusirikala, Igor Kabiljo, Alexander Spiegelman, and Rati Gelashvili

TL;DR: At Aptos Labs, we 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.

For example, consider a simple sequence of transactions, all updating some counter stored in the blockchain state but not conflicting otherwise.

Here, the first transaction subtracts 10 and so the recorded update is -10. The second transaction adds 20 and subtracts 17. Instead of reading the counter value and writing the new value, one can record two updates: +20 and -17 which gives the total update of +3 made by this transaction. Similarly, the third and the fourth transactions have updates of -10 and -20 respectively.

If these transactions have no other read-write conflicts, they can be executed in parallel, and the updates to the counter can be applied in the end in any order. For example, if the counter value was initially 100, then after executing these four transactions it becomes 63. More generally, the read-write conflicts due to updating a global counter can be avoided and the workloads can be executed fully in parallel.

Sequential execution can then be used only when conflicts are unavoidable. For example, if the counter is read, e.g., by the third transaction, the read enforces all preceding updates (from the first and the second transactions) to be computed beforehand, limiting the parallelism.

Dealing with integer overflows and underflows

Updates to the global counter can overflow or underflow. For instance, in the example below, the counter overflows in the second transaction. Importantly, the updates to the counter can still be executed in parallel as long as the overflow is correctly predicted. If not, the transaction can be re-executed by Block-STM just like any other conflicting transaction. The hope here is that the speculative prediction is correct, and overflows or underflows are not common.

Snapshots — conflict-free writes to the blockchain state

Even if the updates to global counters are parallelized, it still does not solve the NFT minting problem. The index (when an NFT was minted) and the token’s name (that can also include the index) read the counter value before the token is persisted to the blockchain state.

Nevertheless, these operations can also be delayed by deferring the write to the blockchain state. Instead of storing the token’s index to the state immediately, a “snapshot” of the current index value can be taken and stored later, e.g., when a transaction is committed. Essentially, a snapshot saves the current partial updates to the global counter variable.

This approach can be easily generalized to handle NFT naming, if that depends on the token’s index. In this case, for each transaction the conversion to string of the snapshotted index variable is delayed. The string name is computed and persisted in the global state later.

Aggregators on Aptos

At Aptos Labs, we developed a general library, which can be used to handle the aforementioned use cases and that can be found under aptos-framework.

The library defines Aggregators — concurrent counter implementation that developers can use to avoid sequential bottlenecks when executing transactions in parallel, e.g., for implementing size tracking in their token collections.

Aggregators are wrappers around integers, which can be created with an initial value of zero. When an Aggregator is created, the user can specify a custom limit. The limit is the maximum value an Aggregator can store. Because we consider unsigned integer Aggregators, the smallest value an Aggregator can have is 0.

// Type parameter allows one to support different integer bit widths,
// e.g., u64 or u128.
struct Aggregator<IntTy> has store {
  value: IntTy,
  max_value: IntTy,
}

let counter = aggregator::create(/*max_value=*/100);

Like regular integers, Aggregators can be updated (but in parallel!) using addition and subtraction methods called try_add and try_sub. These methods return a boolean. The returned value signifies whether the value of an Aggregator has been modified (i.e., if there is no overflow the result is true, and false otherwise).

let success = aggregator::try_add(&mut counter, 20);

let success = aggregator::try_sub(&mut counter, 40);
if (success) {
  // Counter has been modified.
} else {
  // Error handling goes here.
};

Importantly, concurrent updates to Aggregators do not cause transactions to conflict with each other as the multi-version data structure used by Block-STM eliminates write-write conflicts already. Also, the behavior of Aggregators match sequential execution, i.e., whether executed sequentially or in parallel, the outcome is the same.

Aggregators can also be read. The read returns the value stored in an Aggregator, but limits the parallelism across multiple transactions and is better avoided if possible.

// This limits the parallelism of the system.
let value = aggregator::read(&counter);

To allow reading Aggregator values (e.g., for indexing or naming NFT collections) without paying the penalty of sequential execution, one can also take a snapshot of an Aggregator. Aggregator snapshots capture the value of an Aggregator at a particular moment in time, but do not disclose the actual value.

struct AggregatorSnapshot<Ty> has store {
  value: Ty,
}

// Snapshot captures the value of the counter.
// This does not affect the parallelism of the system. 
let snapshot = aggregator::snapshot(&counter);

If the actual value of a snapshot is needed, then it can be read just like an Aggregator.

// Limits the parallelism of the system, but returns the actual
// value stored inside of a snapshot.
let value = aggregator::read_snapshot(&snapshot);

In the current implementation, snapshots can also be formatted as a string.

let name = aggregator::concat("star #", &snapshot, "");

We evaluated Aggregators on representative workloads during our latest (mainnet-like) previewnet, focusing on minting of NFTs. The NFT collections we used had a limited supply and were sequentially named. We were able to mint a 1M collection in 90 seconds, or a 5M collection in 8 minutes, with sustained high throughput. That significantly improves the performance compared to the execution without Aggregators (~10x).

Additionally, we used synthetic benchmarks to test the performance of Aggregators. We observed that updating an unbounded global counter in Move becomes almost 9x faster with Aggregators, because of better parallelism.

Production

Aggregators are used in the Aptos codebase since the launch to track the total native token supply, which means that burning transaction fees does not affect the parallelism of the system. Even though the total supply is updated by every single transaction, workloads can be executed in parallel.

AIP-47 proposes new and more powerful APIs for Aggregators and snapshots, as well as makes them publicly available. With AIP-43, Aggregators can also be deployed to the framework. With this feature, digital asset collections on Aptos can be minted and burnt in parallel even if their size is tracked. Also, collections can be indexed and have formatted names. If these AIPs are accepted, operations on digital assets will become parallel and can be enabled in the mainnet in Q1 2024.

But how are Aggregators implemented? How do they decrease the number of conflicts between transactions in Block-STM and scale with more threads? You can find all the answers in the upcoming posts. Stay tuned!