txcache

package
v0.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 15, 2025 License: GPL-3.0 Imports: 21 Imported by: 0

README

Mempool

Glossary

  1. selection session: an ephemeral session during which the mempool selects transactions for a proposer. A session starts when a proposer asks the mempool for transactions and ends when the mempool returns the transactions. The most important part of a session is the selection loop.
  2. transaction PPU: the price per unit of computation, for a transaction. It's computed as initiallyPaidFee / gasLimit.
  3. initially paid transaction fee: the fee for processing a transaction, as known before its actual processing. That is, without knowing the refund component.

Configuration

  1. SelectTransactions::gasRequested: 10_000_000_000, the maximum total gas limit of the transactions to be returned to a proposer (one selection session). This value is provided by the Protocol.
  2. SelectTransactions::maxNum: 30_000, the maximum number of transactions to be returned to a proposer (one selection session). This value is provided by the Protocol.

Transactions selection

Paragraph 1

When a proposer asks the mempool for transactions, it provides the following parameters:

  • gasRequested: the maximum total gas limit of the transactions to be returned
  • maxNum: the maximum number of transactions to be returned

Paragraph 2

The PPU (price per gas unit) of a transaction, is computed (once it enters the mempool) as follows:

ppu = initiallyPaidFee / gasLimit

In the formula above,

initiallyPaidFee =
    dataCost * gasPrice +
    executionCost * gasPrice * network.gasPriceModifier

dataCost = network.minGasLimit + len(data) * network.gasPdrTataByte

executionCost = gasLimit - dataCost

Network parameters (as of November of 2024):

gasPriceModifier = 0.01
minGasLimit = 50_000
gasPdrTataByte = 1_500
Examples

(a) A simple native transfer with gasLimit = 50_000 and gasPrice = 1_000_000_000:

initiallyPaidFee = 50_000_000_000 atoms
ppu = 1_000_000_000 atoms

(b) A simple native transfer with gasLimit = 50_000 and gasPrice = 1_500_000_000:

initiallyPaidFee = gasLimit * gasPrice = 75_000_000_000 atoms
ppu = 75_000_000_000 / 50_000 = 1_500_000_000 atoms

(c) A simple native transfer with a data payload of 7 bytes, with gasLimit = 50_000 + 7 * 1500 and gasPrice = 1_000_000_000:

initiallyPaidFee = 60_500_000_000_000 atoms
ppu = 60_500_000_000_000 / 60_500 = 1_000_000_000 atoms

That is, for simple native transfers (whether they hold a data payload or not), the PPU is equal to the gas price.

(d) A contract call with gasLimit = 75_000_000 and gasPrice = 1_000_000_000, with a data payload of 42 bytes:

initiallyPaidFee = 861_870_000_000_000 atoms
ppu = 11_491_600 atoms

(e) Similar to (d), but with gasPrice = 2_000_000_000:

initiallyPaidFee = 1_723_740_000_000_000 atoms
ppu = 22_983_200 atoms

That is, for contract calls, the PPU is not equal to the gas price, but much lower, due to the contract call cost subsidy. A higher gas price will result in a higher PPU.

Paragraph 3

Transaction A is considered more valuable (for the Network) than transaction B if it has a higher PPU.

If two transactions have the same PPU, they are ordered by gas limit (higher is better, promoting less "execution fragmentation"). In the end, they are ordered using an arbitrary, but deterministic rule: the transaction with the "lower" transaction hash "wins" the comparison.

Pseudo-code:

func isTransactionMoreValuableForNetwork(A, B):
    if A.ppu > B.ppu:
        return true
    if A.ppu < B.ppu:
        return false

    if A.gasLimit > B.gasLimit:
        return true
    if A.gasLimit < B.gasLimit:
        return false

    return A.hash < B.hash

Paragraph 4

The mempool selects transactions as follows (pseudo-code):

func selectTransactions(gasRequested, maxNum):
    // Setup phase
    senders := list of all current senders in the mempool, in an arbitrary order
    bunchesOfTransactions := sourced from senders, nicely sorted by nonce

    // Holds selected transactions
    selectedTransactions := empty

    // Holds not-yet-selected transactions, ordered by PPU
    competitionHeap := empty
    
    for each bunch in bunchesOfTransactions:
        competitionHeap.push(next available transaction from bunch)
    
    // Selection loop
    while competitionHeap is not empty:
        mostValuableTransaction := competitionHeap.pop()

        // Check if adding the next transaction exceeds limits
        if selectedTransactions.totalGasLimit + mostValuableTransaction.gasLimit > gasRequested:
            break
        if selectedTransactions.length + 1 > maxNum:
            break
        
        selectedTransactions.append(mostValuableTransaction)
        
        nextTransaction := next available transaction from the bunch of mostValuableTransaction
        if nextTransaction exists:
            competitionHeap.push(nextTransaction)

    return selectedTransactions

Thus, the mempool selects transactions using an efficient and value-driven algorithm that ensures the most valuable transactions (in terms of PPU) are prioritized while maintaining correct nonce sequencing per sender. The selection process is as follows:

Setup phase:

  • Snapshot of senders:

    • Before starting the selection loop, obtain a snapshot of all current senders in the mempool in an arbitrary order.

  • Organize transactions into bunches:

    • For each sender, collect all their pending transactions and organize them into a "bunch."
    • Each bunch is:
      • Sorted by nonce: Transactions are ordered in ascending order based on their nonce values.

  • Prepare the heap:

    • Extract the first transaction (lowest nonce) from each sender's bunch.
    • Place these transactions onto a max heap, which is ordered based on the transaction's PPU.

Selection loop:

  • Iterative selection:

    • Continue the loop until either the total gas of selected transactions meets or exceeds gasRequested, or the number of selected transactions reaches maxNum.
    • In each iteration:
      • Select the most valuable transaction:
        • Pop the transaction with the highest PPU from the heap.
        • Append this transaction to the list of selectedTransactions.
      • Update the sender's bunch:
        • If the sender of the selected transaction has more transactions in their bunch:
          • Take the next transaction (next higher nonce) from the bunch.
          • Push this transaction onto the heap to compete in subsequent iterations.
    • This process ensures that at each step, the most valuable transaction across all senders is selected while maintaining proper nonce order for each sender.

  • Early termination:

    • The selection loop can terminate early if either of the following conditions is satisfied before all transactions are processed:
      • The accumulated gas of selected transactions meets or exceeds gasRequested.
      • The number of selected transactions reaches maxNum.

Additional notes:

  • Within the selection loop, the current nonce of the sender is queried from the blockchain, lazily (when needed).
  • If an initial nonce gap is detected, the sender is (completely) skipped in the current selection session.
  • If a middle nonce gap is detected, the sender is skipped (from now on) in the current selection session.
  • Transactions with nonces lower than the current nonce of the sender are skipped.
  • Transactions having the same nonce as a previously selected one (in the scope of a sender) are skipped. Also see paragraph 5.
  • Incorrectly guarded transactions are skipped.
  • Once the accumulated fees of selected transactions of a given sender exceed the sender's balance, the sender is skipped (from now one).

Paragraph 5

On the node's side, the selected transactions are shuffled using a deterministic algorithm. This shuffling ensures that the transaction order remains unpredictable to the proposer, effectively preventing front-running attacks. Therefore, being selected first by the mempool does not guarantee that a transaction will be included first in the block. Additionally, selection by the mempool does not ensure inclusion in the very next block, as the proposer has the final authority on which transactions to include, based on the remaining space available in the block.

Order of transactions of the same sender

Transactions from the same sender are organized based on specific rules to ensure proper sequencing for the selection flow:

  1. Nonce ascending: transactions are primarily sorted by their nonce values in ascending order. This sequence ensures that the transactions are processed in the order intended by the sender, as the nonce represents the transaction number in the sender's sequence.

  2. Gas price descending (same nonce): if multiple transactions share the same nonce, they are sorted by their gas prices in descending order - transactions offering higher gas prices are prioritized. This mechanism allows one to easily override a pending transaction with a higher gas price.

  3. Hash ascending (same nonce and gas price): for transactions that have identical nonce and gas price, the tie is broken by sorting them based on their transaction hash in ascending order. This provides a consistent and deterministic ordering when other factors are equal. While this ordering isn't a critical aspect of the mempool's operation, it ensures logical consistency.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ConfigDestinationMe 

type ConfigDestinationMe struct {
	Name                        string
	NumChunks                   uint32
	MaxNumItems                 uint32
	MaxNumBytes                 uint32
	NumItemsToPreemptivelyEvict uint32
}

ConfigDestinationMe holds cache configuration

func (*ConfigDestinationMe) String 

func (config *ConfigDestinationMe) String() string

String returns a readable representation of the object

type ConfigSourceMe 

type ConfigSourceMe struct {
	Name                        string
	NumChunks                   uint32
	EvictionEnabled             bool
	NumBytesThreshold           uint32
	NumBytesPerSenderThreshold  uint32
	CountThreshold              uint32
	CountPerSenderThreshold     uint32
	NumItemsToPreemptivelyEvict uint32
}

ConfigSourceMe holds cache configuration

func (*ConfigSourceMe) String 

func (config *ConfigSourceMe) String() string

String returns a readable representation of the object

type CrossTxCache 

type CrossTxCache struct {
	*immunitycache.ImmunityCache
	// contains filtered or unexported fields
}

CrossTxCache holds cross-shard transactions (where destination == me)

func NewCrossTxCache 

func NewCrossTxCache(config ConfigDestinationMe) (*CrossTxCache, error)

NewCrossTxCache creates a new transactions cache

func (*CrossTxCache) AddTx 

func (cache *CrossTxCache) AddTx(tx *WrappedTransaction) (has, added bool)

AddTx adds a transaction in the cache

func (*CrossTxCache) ForEachTransaction 

func (cache *CrossTxCache) ForEachTransaction(function ForEachTransaction)

ForEachTransaction iterates over the transactions in the cache

func (*CrossTxCache) Get 

func (cache *CrossTxCache) Get(key []byte) (value interface{}, ok bool)

Get returns the unwrapped payload of a TransactionWrapper Implemented for compatibility reasons (see txPoolsCleaner.go).

func (*CrossTxCache) GetByTxHash 

func (cache *CrossTxCache) GetByTxHash(txHash []byte) (*WrappedTransaction, bool)

GetByTxHash gets the transaction by hash

func (*CrossTxCache) GetTransactionsPoolForSender 

func (cache *CrossTxCache) GetTransactionsPoolForSender(_ string) []*WrappedTransaction

GetTransactionsPoolForSender returns an empty slice, only to respect the interface CrossTxCache does not support transaction selection (not applicable, since transactions are already half-executed), thus does not handle nonces, nonce gaps etc.

func (*CrossTxCache) ImmunizeTxsAgainstEviction 

func (cache *CrossTxCache) ImmunizeTxsAgainstEviction(keys [][]byte)

ImmunizeTxsAgainstEviction marks items as non-evictable

func (*CrossTxCache) IsInterfaceNil 

func (cache *CrossTxCache) IsInterfaceNil() bool

IsInterfaceNil returns true if there is no value under the interface

func (*CrossTxCache) Peek 

func (cache *CrossTxCache) Peek(key []byte) (value interface{}, ok bool)

Peek returns the unwrapped payload of a TransactionWrapper Implemented for compatibility reasons (see transactions.go, common.go).

func (*CrossTxCache) RemoveTxByHash 

func (cache *CrossTxCache) RemoveTxByHash(txHash []byte) bool

RemoveTxByHash removes tx by hash

type DisabledCache 

type DisabledCache struct {
}

DisabledCache represents a disabled cache

func NewDisabledCache 

func NewDisabledCache() *DisabledCache

NewDisabledCache creates a new disabled cache

func (*DisabledCache) AddTx 

func (cache *DisabledCache) AddTx(_ *WrappedTransaction) (ok bool, added bool)

AddTx does nothing

func (*DisabledCache) Clear 

func (cache *DisabledCache) Clear()

Clear does nothing

func (*DisabledCache) Close 

func (cache *DisabledCache) Close() error

Close does nothing

func (*DisabledCache) Diagnose 

func (cache *DisabledCache) Diagnose(_ bool)

Diagnose does nothing

func (*DisabledCache) ForEachTransaction 

func (cache *DisabledCache) ForEachTransaction(_ ForEachTransaction)

ForEachTransaction does nothing

func (*DisabledCache) Get 

func (cache *DisabledCache) Get(_ []byte) (value interface{}, ok bool)

Get returns no transaction

func (*DisabledCache) GetByTxHash 

func (cache *DisabledCache) GetByTxHash(_ []byte) (*WrappedTransaction, bool)

GetByTxHash returns no transaction

func (*DisabledCache) GetTransactionsPoolForSender 

func (cache *DisabledCache) GetTransactionsPoolForSender(_ string) []*WrappedTransaction

GetTransactionsPoolForSender returns an empty slice

func (*DisabledCache) Has 

func (cache *DisabledCache) Has(_ []byte) bool

Has returns false

func (*DisabledCache) HasOrAdd 

func (cache *DisabledCache) HasOrAdd(_ []byte, _ interface{}, _ int) (has, added bool)

HasOrAdd returns false, does nothing

func (*DisabledCache) ImmunizeTxsAgainstEviction 

func (cache *DisabledCache) ImmunizeTxsAgainstEviction(_ [][]byte)

ImmunizeTxsAgainstEviction does nothing

func (*DisabledCache) IsInterfaceNil 

func (cache *DisabledCache) IsInterfaceNil() bool

IsInterfaceNil returns true if there is no value under the interface

func (*DisabledCache) Keys 

func (cache *DisabledCache) Keys() [][]byte

Keys returns an empty slice

func (*DisabledCache) Len 

func (cache *DisabledCache) Len() int

Len returns zero

func (*DisabledCache) MaxSize 

func (cache *DisabledCache) MaxSize() int

MaxSize returns zero

func (*DisabledCache) NumBytes 

func (cache *DisabledCache) NumBytes() int

NumBytes returns zero

func (*DisabledCache) Peek 

func (cache *DisabledCache) Peek(_ []byte) (value interface{}, ok bool)

Peek returns no transaction

func (*DisabledCache) Put 

func (cache *DisabledCache) Put(_ []byte, _ interface{}, _ int) (evicted bool)

Put does nothing

func (*DisabledCache) RegisterHandler 

func (cache *DisabledCache) RegisterHandler(func(key []byte, value interface{}), string)

RegisterHandler does nothing

func (*DisabledCache) Remove 

func (cache *DisabledCache) Remove(_ []byte)

Remove does nothing

func (*DisabledCache) RemoveTxByHash 

func (cache *DisabledCache) RemoveTxByHash(_ []byte) bool

RemoveTxByHash does nothing

func (*DisabledCache) SelectTransactions 

func (cache *DisabledCache) SelectTransactions(uint64, int) ([]*WrappedTransaction, uint64)

SelectTransactions returns an empty slice

func (*DisabledCache) SizeInBytesContained 

func (cache *DisabledCache) SizeInBytesContained() uint64

SizeInBytesContained returns 0

func (*DisabledCache) UnRegisterHandler 

func (cache *DisabledCache) UnRegisterHandler(string)

UnRegisterHandler does nothing

type ForEachTransaction 

type ForEachTransaction func(txHash []byte, value *WrappedTransaction)

ForEachTransaction is an iterator callback

type MempoolHost 

type MempoolHost interface {
	ComputeTxFee(tx data.TransactionWithFeeHandler) *big.Int
	GetTransferredValue(tx data.TransactionHandler) *big.Int
	IsInterfaceNil() bool
}

MempoolHost provides blockchain information for mempool operations

type SelectionSession 

type SelectionSession interface {
	GetAccountState(accountKey []byte) (*types.AccountState, error)
	IsIncorrectlyGuarded(tx data.TransactionHandler) bool
	IsInterfaceNil() bool
}

SelectionSession provides blockchain information for transaction selection

type TxCache 

type TxCache struct {
	// contains filtered or unexported fields
}

TxCache represents a cache-like structure (it has a fixed capacity and implements an eviction mechanism) for holding transactions

func NewTxCache 

func NewTxCache(config ConfigSourceMe, host MempoolHost) (*TxCache, error)

NewTxCache creates a new transaction cache

func (*TxCache) AddTx 

func (cache *TxCache) AddTx(tx *WrappedTransaction) (ok bool, added bool)

AddTx adds a transaction in the cache Eviction happens if maximum capacity is reached

func (*TxCache) Clear 

func (cache *TxCache) Clear()

Clear clears the cache

func (*TxCache) Close 

func (cache *TxCache) Close() error

Close does nothing for this cacher implementation

func (*TxCache) CountSenders 

func (cache *TxCache) CountSenders() uint64

CountSenders gets the number of senders in the cache

func (*TxCache) CountTx 

func (cache *TxCache) CountTx() uint64

CountTx gets the number of transactions in the cache

func (*TxCache) Diagnose 

func (cache *TxCache) Diagnose(_ bool)

Diagnose checks the state of the cache for inconsistencies and displays a summary, senders and transactions.

func (*TxCache) ForEachTransaction 

func (cache *TxCache) ForEachTransaction(function ForEachTransaction)

ForEachTransaction iterates over the transactions in the cache

func (*TxCache) Get 

func (cache *TxCache) Get(key []byte) (value interface{}, ok bool)

Get gets a transaction (unwrapped) by hash Implemented for compatibility reasons (see txPoolsCleaner.go).

func (*TxCache) GetByTxHash 

func (cache *TxCache) GetByTxHash(txHash []byte) (*WrappedTransaction, bool)

GetByTxHash gets the transaction by hash

func (*TxCache) GetTransactionsPoolForSender 

func (cache *TxCache) GetTransactionsPoolForSender(sender string) []*WrappedTransaction

GetTransactionsPoolForSender returns the list of transaction hashes for the sender

func (*TxCache) Has 

func (cache *TxCache) Has(key []byte) bool

Has checks if a transaction exists

func (*TxCache) HasOrAdd 

func (cache *TxCache) HasOrAdd(_ []byte, _ interface{}, _ int) (has, added bool)

HasOrAdd is not implemented

func (*TxCache) ImmunizeTxsAgainstEviction 

func (cache *TxCache) ImmunizeTxsAgainstEviction(_ [][]byte)

ImmunizeTxsAgainstEviction does nothing for this type of cache

func (*TxCache) IsInterfaceNil 

func (cache *TxCache) IsInterfaceNil() bool

IsInterfaceNil returns true if there is no value under the interface

func (*TxCache) Keys 

func (cache *TxCache) Keys() [][]byte

Keys returns the tx hashes in the cache

func (*TxCache) Len 

func (cache *TxCache) Len() int

Len is an alias for CountTx

func (*TxCache) MaxSize 

func (cache *TxCache) MaxSize() int

MaxSize returns the maximum number of transactions that can be stored in the cache. See: https://github.com/TerraDharitri/drt-go-chain/blob/v1.8.4/dataRetriever/txpool/shardedTxPool.go#L55

func (*TxCache) NumBytes 

func (cache *TxCache) NumBytes() int

NumBytes gets the approximate number of bytes stored in the cache

func (*TxCache) Peek 

func (cache *TxCache) Peek(key []byte) (value interface{}, ok bool)

Peek gets a transaction (unwrapped) by hash Implemented for compatibility reasons (see transactions.go, common.go).

func (*TxCache) Put 

func (cache *TxCache) Put(_ []byte, _ interface{}, _ int) (evicted bool)

Put is not implemented

func (*TxCache) RegisterHandler 

func (cache *TxCache) RegisterHandler(func(key []byte, value interface{}), string)

RegisterHandler is not implemented

func (*TxCache) Remove 

func (cache *TxCache) Remove(key []byte)

Remove removes tx by hash

func (*TxCache) RemoveTxByHash 

func (cache *TxCache) RemoveTxByHash(txHash []byte) bool

RemoveTxByHash removes transactions with nonces lower or equal to the given transaction's nonce

func (*TxCache) SelectTransactions 

func (cache *TxCache) SelectTransactions(session SelectionSession, gasRequested uint64, maxNum int, selectionLoopMaximumDuration time.Duration) ([]*WrappedTransaction, uint64)

SelectTransactions selects the best transactions to be included in the next miniblock. It returns up to "maxNum" transactions, with total gas <= "gasRequested".

func (*TxCache) SizeInBytesContained 

func (cache *TxCache) SizeInBytesContained() uint64

SizeInBytesContained returns 0

func (*TxCache) UnRegisterHandler 

func (cache *TxCache) UnRegisterHandler(string)

UnRegisterHandler is not implemented

type WrappedTransaction 

type WrappedTransaction struct {
	Tx              data.TransactionHandler
	TxHash          []byte
	SenderShardID   uint32
	ReceiverShardID uint32
	Size            int64

	// These fields are only set within "precomputeFields".
	// We don't need to protect them with a mutex, since "precomputeFields" is called only once for each transaction.
	// Additional note: "WrappedTransaction" objects are created by the Node, in dataRetriever/txpool/shardedTxPool.go.
	Fee              *big.Int
	PricePerUnit     uint64
	TransferredValue *big.Int
}

WrappedTransaction contains a transaction, its hash and extra information

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.