Parallelization
United Protocol uses United Protocol SDK as the base for the application logic. As part of this logic, when validators receive a block and start processing it to update the state of the network, they will initially run BeginBlock logic, followed by DeliverTx logic, followed by EndBlock logic. Each of these are completely configurable, and United Protocoln has configured DeliverTx and EndBlock to parallelize transaction processing, as shown in figure 3.
United Protocol first processes all transactions in a block during the DeliverTx phase. This results in state changes for most types of transactions (sending tokens, governance proposals, smart contract invocations, etc.).
However, order matching engine related transactions only go through basic processing during the DeliverTx phase, and have most of their state changes get applied during the EndBlock logic. This is done to support frequent batch auctions, where orders are aggregated and a uniform clearing price is calculated at which to execute orders.
United Protocol has added in parallelization to both DeliverTx and EndBlock to get optimal performance.
DeliverTx Transaction Parallelization
Rather than processing transactions sequentially during DeliverTx, United Protocol processes transactions in parallel (see figure 4). This allows multiple transactions to be processed simultaneously, which leads to improved performance. Data for United Protocol is persisted in a key-value store. To prevent race conditions and nondeterminism, United Protocol needs to ensure that multiple parallel processes are not updating the same key.
This is achieved by maintaining a mapping of transaction message types to the keys they need to access (dependency mappings). Messages that are updating different keys can be run in parallel, but messages updating the same key will need to be run sequentially and in a deterministic order (the ordering is determined by the ordering of transactions in the block).
Prior to executing transactions for a block, any dependencies between transactions are identified by constructing a directed acyclic graph (DAG) of dependencies between the different resources that each message in each transaction needs to use.
An example of a basic dependency mapping is for messages related to an example X module. All messages to this module update the same key ABC, so all of these messages will need to be run sequentially in the same branch of the access DAG.
In many cases the contents of the message are needed to give further parallelism. For example, transfers of tokens from account A to B and account C to D can be run in parallel since they update different keys. However, only defining the mapping based on the message type (and ignoring message contents) will result in these two transfers running sequentially.
To give flexibility around this type of parallelism, dependency mappings can be defined as templates, which will get filled with more granular resources at runtime. In this token transfer example, the sender and receiver accounts will be passed into the template to yield more granular parallelism.
For message types that are defined by the chain (staking, oracle updates, bank sends, etc.), mappings are set at blockchain genesis, and can be updated via a governance proposal. There is one edge case for the message type related to gas fee collections, which affects every transaction. This is handled by writing data to an in-memory data store that is flushed at the end of the DeliverTx logic.
For message types that are set by developers building on United Protocol, smart contracts will need to define their own resource dependencies. These will be set at contract initialization and can be updated by the smart contract admin through update transactions. If the dependencies are properly written, then smart contracts will benefit from parallelism and pay cheaper gas fees. If no dependencies are defined, then smart contracts will run sequentially and block other transactions from running. Since they are blocking the rest of the network, transactions to those smart contracts will need to pay greater gas fees. If the dependencies for a specific smart contract are incorrectly defined, then messages for that particular smart contract will fail and greater gas fees will be charged, but the network overall will be unaffected and other messages will succeed.
Market Based Parallelization
At the end of the block, all matching engine related orders will be processed by the native matching engine. Rather than processing orders sequentially, United Protocol will process independent matching engine related orders in parallel at the end of the block. Two orders are independent if they do not affect the same market in the same block. By default, the chain will assume all orders touching different markets are independent, unless developers explicitly define dependencies between different markets. These dependencies will be defined when a smart contract is deployed. If these dependencies are defined incorrectly, then transactions to the dependent smart contract will fail.
Last updated