Additional fees were introduced to transactions as a method to allow users to bid for priority for their transactions in the leader's queue.
The fee priority of a transaction
T can then be defined as
F(T) is the "fee-per
compute-unit", calculated by:
(additional_fee + base_fee) / requested_compute_units
To ensure users get fair priority based on their fee, the proposed scheduler for the leader must
guarantee that given
T2 in the pending queue, and
F(T1) > F(T2):
T1should be considered for processing before
T1cannot be processed before
T2because there's already a transaction currently being processed that contends on an account
T2should not be scheduled if it would grab any account locks needed by
T1. This prevents lower fee transactions like
T2from starving higher paying transactions like
- BankingStage threads
Transactions from sigverify are connected via a channel to the scheduler. The scheduler maintains
N bi-directional channels with the
N BankingStage threads, implemented as a pair of two
The scheduler's job is to run an algorithm in which it determines how to schedule transactions
received from sigverify to the
N BankingStage threads. A transaction is scheduled to be executed
on a particular BankingStage thread by sending that transaction to the thread via its associated
Once a BankingStage thread finishes processing a transaction
T , it sends the
to the scheduler via the same channel to signal of completion.
The scheduler is the most complex piece of the above pipeline, its implementation is made up of a few pieces. Note for now, all these pieces are maintained by the single scheduler thread to avoid locking complexity.
Components of the
default_transaction_queue- A max-heap
BinaryHeap<Transaction>that tracks all pending transactions. The priority in the heap is the additional fee of the transaction. Transactions are added to this queue from sigverify before the leader slot begins.
VecDeque<BinaryHeap<Transaction>>that tracks all pending queues of work. Some pending queues have higher priority than others (as will be explained later in the
Handling Completion Signals from BankingStage Threadssection below). The list is ordered in priority from highest to lowest priority. On initialization,
all_transaction_queues = default_transaction_queue.
HashMap<LockedPubkey, usize>that tracks the set of accounts needed to execute the current set of transactions scheduled/sent to banking threads. Accounts are added to this set before being sent to BankingStage threads. The
usizerepresents a refcount, because multiple read accounts could be grabbed.
LockedPubkeyis defined as:
HashMap<Signature, Rc<BlockedTransactionsQueue>>keyed by transaction signature, and maps to a
HashMap<Pubkey, Rc<BlockedTransactionsQueue>>keyed by account keys.
N BankingStage threads:
The scheduler will run for each banking thread a function
Pop off the highest priority transaction
self.all_transaction_queues. If `
self.all_transaction_queuesis empty, pop off the first deque item and continue.
transaction_accountsbe the set of
LockedPubkeykeys needed by
next_highest_transaction. We run the following:
- In the case of a
- In the case of a
- Run until all
NBankingStage threads have been sent
processing_batchtransactions (i.e. hit step 3 above).
- Banking threads maintain a queue of transactions sent to them by the scheduler, sorted by priority.
- Because the scheduler has guaranteed that there are no locking conflicts, the banking thread can process
Mof these transactions at a time and pack them into entries
Outside of the main loop above, we rely on BankingThreads threads signaling us they've finished their task to schedule the next transactions.
Once a BankingStage thread finishes processing a batch of transactions
completed_transactions_batch, it sends the
completed_transactions_batchback to the scheduler via the same channel to signal of completion.
Upon receiving this signal, the BankingStage thread processes the locked accounts
- Check if the finished transaction was the blocking transaction for any queue: