mempool

Documentation

Overview

(c) 2019 Dapper Labs - ALL RIGHTS RESERVED

Index

• type Approvals
• type Assignments
• type BlockFilter
• type Blocks
• type ChunkDataPacks
• type Collections
• type Deltas
• type ExecutionTree
• type Guarantees
• type IdentifierMap
• type Identifiers
• type IncorporatedResultSeals
• type IncorporatedResults
• type OnEjection
• type PendingReceipts
• type ReceiptDataPacks
• type ReceiptFilter
• type ResultDataPacks
• type Results
• type TransactionTimings
• type Transactions

Types

type Approvals

type Approvals interface {

	// Add will add the given result approval to the memory pool. It will return
	// false if it was already in the mempool.
	Add(approval *flow.ResultApproval) (bool, error)

	// RemApproval removes a specific approval.
	RemApproval(approval *flow.ResultApproval) (bool, error)

	// Rem will attempt to remove all the approvals associated with a chunk.
	RemChunk(resultID flow.Identifier, chunkIndex uint64) (bool, error)

	// ByChunk returns all the approvals associated with a chunk. It returns an
	// empty map if there is nothing.
	ByChunk(resultID flow.Identifier, chunkIndex uint64) map[flow.Identifier]*flow.ResultApproval

	// All will return a list of all approvals in the memory pool.
	All() []*flow.ResultApproval

	// Size will return the current size of the memory pool.
	Size() uint
}

Approvals represents a concurrency-safe memory pool for result approvals.

type Assignments

type Assignments interface {

	// Has checks whether the Assignment with the given hash is currently in
	// the memory pool.
	Has(assignmentID flow.Identifier) bool

	// Add will add the given assignment to the memory pool. It will return
	// false if it was already in the mempool.
	Add(assignmentFingerprint flow.Identifier, assignment *chunkmodels.Assignment) bool

	// Rem will remove the given Assignment from the memory pool; it will
	// return true if the Assignment was known and removed.
	Rem(assignmentID flow.Identifier) bool

	// ByID retrieve the chunk assigment with the given ID from the memory pool.
	// It will return false if it was not found in the mempool.
	ByID(assignmentID flow.Identifier) (*chunkmodels.Assignment, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all Assignments that are currently in the memory pool
	// as a slice.
	All() []*chunkmodels.Assignment
}

Assignments represents a concurrency-safe memory pool for chunk assignments

type BlockFilter

type BlockFilter func(header *flow.Header) bool

BlockFilter is used for controlling the ExecutionTree's Execution Tree search. The search only traverses to results for blocks which pass the filter. If an the block for an execution result does not pass the filter, the entire sub-tree of derived results is not traversed.

type Blocks

type Blocks interface {

	// Has checks whether the block with the given hash is currently in
	// the memory pool.
	Has(blockID flow.Identifier) bool

	// Add will add the given block to the memory pool. It will return
	// false if it was already in the mempool.
	Add(block *flow.Block) bool

	// Rem will remove the given block from the memory pool; it will
	// will return true if the block was known and removed.
	Rem(blockID flow.Identifier) bool

	// ByID retrieve the block with the given ID from the memory pool.
	// It will return false if it was not found in the mempool.
	ByID(blockID flow.Identifier) (*flow.Block, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all blocks that are currently in the memory pool
	// as a slice.
	All() []*flow.Block

	// Hash will return a hash of the contents of the memory pool.
	Hash() flow.Identifier
}

Blocks represents a concurrency-safe memory pool for blocks.

type ChunkDataPacks

type ChunkDataPacks interface {

	// Has checks whether the ChunkDataPack with the given chunkID is currently in
	// the memory pool.
	Has(chunkID flow.Identifier) bool

	// Add will add the given chunk datapack to the memory pool. It will return
	// false if it was already in the mempool.
	Add(cdp *flow.ChunkDataPack) bool

	// Rem will remove the given ChunkDataPack from the memory pool; it will
	// return true if the ChunkDataPack was known and removed.
	Rem(chunkID flow.Identifier) bool

	// ByID retrieve the chunk datapacke with the given chunk ID from the memory
	// pool. It will return false if it was not found in the mempool.
	ByChunkID(chunkID flow.Identifier) (*flow.ChunkDataPack, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all ChunkDataPacks that are currently in the memory pool
	// as a slice.
	All() []*flow.ChunkDataPack

	// Hash will return a hash of the contents of the memory pool.
	Hash() flow.Identifier
}

ChunkDataPacks represents a concurrency-safe memory pool for chunk data packs.

type Collections

type Collections interface {

	// Has checks whether the collection with the given hash is currently in
	// the memory pool.
	Has(collID flow.Identifier) bool

	// Add will add the given collection to the memory pool. It will return
	// false if it was already in the mempool.
	Add(coll *flow.Collection) bool

	// Rem will remove the given collection from the memory pool; it will
	// return true if the collection was known and removed.
	Rem(collID flow.Identifier) bool

	// ByID retrieve the collection with the given ID from the memory pool.
	// It will return false if it was not found in the mempool.
	ByID(collID flow.Identifier) (*flow.Collection, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all collections that are currently in the memory pool
	// as a slice.
	All() []*flow.Collection

	// Hash will return a hash of the contents of the memory pool.
	Hash() flow.Identifier
}

Collections represents a concurrency-safe memory pool for collections.

type Deltas

type Deltas interface {

	// Has checks whether the block delta with the given hash is currently in
	// the memory pool.
	Has(blockID flow.Identifier) bool

	// Add will add the given block delta to the memory pool. It will return
	// false if it was already in the mempool.
	Add(delta *messages.ExecutionStateDelta) bool

	// Rem will remove the given block delta from the memory pool; it will
	// will return true if the block delta was known and removed.
	Rem(blockID flow.Identifier) bool

	// ByID retrieve the block delta with the given ID from the memory
	// pool. It will return false if it was not found in the mempool.
	ByBlockID(blockID flow.Identifier) (*messages.ExecutionStateDelta, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// Limit will return the maximum size of the memory pool
	Limit() uint

	// All will retrieve all block deltas that are currently in the memory pool
	// as a slice.
	All() []*messages.ExecutionStateDelta

	// Hash will return a fingerprint has representing the contents of the
	// entire memory pool.
	Hash() flow.Identifier
}

Deltas represents a concurrency-safe memory pool for block deltas.

type ExecutionTree

type ExecutionTree interface {

	// AddResult adds an Execution Result to the Execution Tree (without any receipts), in
	// case the result is not already stored in the tree.
	// This is useful for crash recovery:
	// After recovering from a crash, the mempools are wiped and the sealed results will not
	// be stored in the Execution Tree anymore. Adding the result to the tree allows to create
	// a vertex in the tree without attaching any Execution Receipts to it.
	AddResult(result *flow.ExecutionResult, block *flow.Header) error

	// Add the given execution receipt to the memory pool. Requires height
	// of the block the receipt is for. We enforce data consistency on an API
	// level by using the block header as input.
	AddReceipt(receipt *flow.ExecutionReceipt, block *flow.Header) (bool, error)

	// ReachableReceipts returns a slice of ExecutionReceipt, whose result
	// is computationally reachable from resultID. Context:
	// * Conceptually, the Execution results form a tree, which we refer to as
	//   Execution Tree. A branch in the execution can be due to a fork in the main
	//   chain. Furthermore, the execution branches if ENs disagree about the result
	//   for the same block.
	// * As the ID of an execution result contains the BlockID, which the result
	//   for, all Execution Results with the same ID necessarily are for the same
	//   block. All Execution Receipts committing to the same result from an
	//   equivalence class and can be represented as one vertex in the Execution
	//   Tree.
	// * An execution result r1 points (field ExecutionResult.ParentResultID) to
	//   its parent result r0 , whose end state was used as the starting state
	//   to compute r1. Formally, we have an edge r0 -> r1 in the Execution Tree,
	//   if a result r1 is stored in the mempool, whose ParentResultID points to
	//   r0.
	// ReachableReceipts implements a tree search on the Execution Tree starting
	// from the provided resultID. Execution Receipts are traversed in a
	// parent-first manner, meaning that a the parent result is traversed
	// _before_ any of its derived results. The algorithm only traverses to
	// results, for which there exists a sequence of interim result in the
	// mempool without any gaps.
	//
	// Two filters are supplied:
	// * blockFilter: the tree search will only travers to results for
	//   blocks which pass the filter. Often higher-level logic is only
	//   interested in results for blocks in a specific fork. Such can be
	//   implemented by a suitable blockFilter.
	// * receiptFilter: for a reachable result (subject to the restrictions
	//   imposed by blockFilter, all known receipts are returned.
	//   While _all_ Receipts for the parent result are guaranteed to be
	//   listed before the receipts for the derived results, there is no
	//   specific ordering for the receipts committing to the same result
	//   (random order). If only a subset of receipts for a result is desired
	//   (e.g. for de-duplication with parent blocks), receiptFilter should
	//   be used.
	// Note the important difference between the two filters:
	// * The blockFilter suppresses traversal to derived results.
	// * The receiptFilter does _not_ suppresses traversal to derived results.
	//   Only individual receipts are dropped.
	ReachableReceipts(resultID flow.Identifier, blockFilter BlockFilter, receiptFilter ReceiptFilter) ([]*flow.ExecutionReceipt, error)

	// Size returns the number of receipts stored in the mempool
	Size() uint

	// PruneUpToHeight prunes all results for all blocks with height up to but
	// NOT INCLUDING `newLowestHeight`. Errors if newLowestHeight is smaller than
	// the previous value (as we cannot recover previously pruned results).
	PruneUpToHeight(newLowestHeight uint64) error

	// LowestHeight returns the lowest height, where results are still
	// stored in the mempool.
	LowestHeight() uint64
}

ExecutionTree represents a concurrency-safe memory pool for execution Receipts. Its is aware of the tree structure formed by execution results. All execution receipts for the _same result_ form an equivalence class and are represented by _one_ vertex in the execution tree. The mempool utilizes knowledge about the height of the block the result is for. Hence, the Mempool can only store and process Receipts whose block is known.

Implementations are concurrency safe.

type Guarantees

type Guarantees interface {

	// Has checks whether the collection guarantee with the given hash is
	// currently in the memory pool.
	Has(collID flow.Identifier) bool

	// Add will add the given collection guarantee to the memory pool. It will
	// return false if it was already in the mempool.
	Add(guarantee *flow.CollectionGuarantee) bool

	// Rem will remove the given collection guarantees from the memory pool; it
	// will return true if the collection guarantees was known and removed.
	Rem(collID flow.Identifier) bool

	// ByID retrieve the collection guarantee with the given ID from the memory
	// pool. It will return false if it was not found in the mempool.
	ByID(collID flow.Identifier) (*flow.CollectionGuarantee, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all collection guarantees that are currently in the memory pool
	// as a slice.
	All() []*flow.CollectionGuarantee

	// Hash will return a fingerprint has representing the contents of the
	// entire memory pool.
	Hash() flow.Identifier
}

Guarantees represents a concurrency-safe memory pool for collection guarantees.

type IdentifierMap

type IdentifierMap interface {
	// Append will append the id to the list of identifiers associated with key.
	Append(key, id flow.Identifier) error

	// Rem removes the given key with all associated identifiers.
	Rem(key flow.Identifier) bool

	// RemIdFromKey removes the id from the list of identifiers associated with key.
	// If the list becomes empty, it also removes the key from the map.
	RemIdFromKey(key, id flow.Identifier) error

	// Get returns list of all identifiers associated with key and true, if the key exists in the mempool.
	// Otherwise it returns nil and false.
	Get(key flow.Identifier) ([]flow.Identifier, bool)

	// Has returns true if the key exists in the map, i.e., there is at least an id
	// attached to it.
	Has(key flow.Identifier) bool

	// Keys returns a list of all keys in the mempool
	Keys() ([]flow.Identifier, bool)

	// Size returns number of IdMapEntities in mempool
	Size() uint
}

IdentifierMap represents a concurrency-safe memory pool for mapping an identifier to a list of identifiers

type Identifiers

type Identifiers interface {
	// Has checks whether the mempool has the identifier
	Has(id flow.Identifier) bool

	// Add will add the given identifier to the memory pool. It will return
	// false if it was already in the mempool.
	Add(id flow.Identifier) bool

	// Rem removes the given identifier
	Rem(id flow.Identifier) bool

	// Size returns total number of identifiers in mempool
	Size() uint

	// All will retrieve all identifiers that are currently in the memory pool
	// as an IdentityList
	All() flow.IdentifierList
}

Identifiers represents a concurrency-safe memory pool for identifiers

type IncorporatedResultSeals

type IncorporatedResultSeals interface {
	// Add adds an IncorporatedResultSeal to the mempool
	Add(irSeal *flow.IncorporatedResultSeal) (bool, error)

	// All returns all the IncorporatedResultSeals in the mempool
	All() []*flow.IncorporatedResultSeal

	// ByID returns an IncorporatedResultSeal by ID
	ByID(flow.Identifier) (*flow.IncorporatedResultSeal, bool)

	// RegisterEjectionCallbacks adds the provided OnEjection callbacks
	RegisterEjectionCallbacks(callbacks ...OnEjection)

	// Limit returns the size limit of the mempool
	Limit() uint

	// Rem removes an IncorporatedResultSeal from the mempool
	Rem(incorporatedResultID flow.Identifier) bool

	// Size returns the number of items in the mempool
	Size() uint

	// Clear removes all entities from the pool.
	Clear()
}

IncorporatedResultSeals represents a concurrency safe memory pool for incorporated result seals

type IncorporatedResults

type IncorporatedResults interface {
	// Add adds an IncorporatedResult to the mempool
	Add(result *flow.IncorporatedResult) (bool, error)

	// All returns all the IncorporatedResults in the mempool
	All() []*flow.IncorporatedResult

	// ByResultID returns all the IncorporatedResults that contain a specific
	// ExecutionResult, indexed by IncorporatedBlockID, along with the
	// ExecutionResult.
	ByResultID(resultID flow.Identifier) (*flow.ExecutionResult, map[flow.Identifier]*flow.IncorporatedResult, bool)

	// Rem removes an IncorporatedResult from the mempool
	Rem(incorporatedResult *flow.IncorporatedResult) bool

	// Size returns the number of items in the mempool
	Size() uint
}

IncorporatedResults represents a concurrency safe memory pool for incorporated results

type OnEjection

type OnEjection func(flow.Entity)

OnEjection is a callback which a mempool executes on ejecting one of its elements. The callbacks are executed from within the thread that serves the mempool. Implementations should be non-blocking.

type PendingReceipts

type PendingReceipts interface {
	// Add a pending receipt
	// return true if added
	// return false if is a duplication
	Add(receipt *flow.ExecutionReceipt) bool

	// Remove a pending receipt by ID
	Rem(receiptID flow.Identifier) bool

	// ByPreviousResultID returns all the pending receipts whose previous result id
	// matches the given result id
	ByPreviousResultID(previousReusltID flow.Identifier) []*flow.ExecutionReceipt

	Size() uint
}

PendingReceipts stores pending receipts indexed by the id. It also maintains a secondary index on the previous result id, which is unique, in order to allow to find a receipt by the previous result id.

type ReceiptDataPacks

type ReceiptDataPacks interface {

	// Add will add the given ReceiptDataPack to the memory pool. It will return
	// false if it was already in the mempool.
	Add(rdp *verification.ReceiptDataPack) bool

	// Get returns the ReceiptDataPack and true, if the ReceiptDataPack is in the
	// mempool. Otherwise, it returns nil and false.
	Get(rdpID flow.Identifier) (*verification.ReceiptDataPack, bool)

	// Has checks if the given ReceiptDataPack is part of the memory pool.
	Has(rdpID flow.Identifier) bool

	// Rem will remove a ReceiptDataPack by ID.
	Rem(rdpID flow.Identifier) bool

	// Size returns total number ReceiptDataPacks in mempool
	Size() uint

	// All will return a list of all ReceiptDataPacks in the memory pool.
	All() []*verification.ReceiptDataPack
}

ReceiptDataPacks represents a concurrency-safe memory pool for ReceiptDataPack data structure.

type ReceiptFilter

type ReceiptFilter func(receipt *flow.ExecutionReceipt) bool

ReceiptFilter is used to drop specific receipts from. It does NOT affect the ExecutionTree's Execution Tree search.

type ResultDataPacks

type ResultDataPacks interface {
	// Add will add the given ResultDataPack to the mempool. It will return
	// false if it was already in the mempool.
	Add(result *verification.ResultDataPack) bool

	// Has returns true if a ResultDataPack with the specified identifier exists.
	Has(resultID flow.Identifier) bool

	// Rem will remove the pending result from the memory pool
	Rem(resultID flow.Identifier) bool

	// Get returns the ResultDataPack and true, if the ResultDataPack is in the
	// mempool. Otherwise, it returns nil and false.
	Get(resultID flow.Identifier) (*verification.ResultDataPack, bool)

	// Size returns total number ResultDataPacks in mempool
	Size() uint
}

ResultDataPacks represents a concurrency-safe memory pool for ResultDataPack data structure.

type Results

type Results interface {

	// Has will check if the given result is in the memory pool.
	Has(resultID flow.Identifier) bool

	// Add will add the given execution result to the memory pool. It will return
	// false if it was already in the mempool.
	Add(result *flow.ExecutionResult) bool

	// Rem will attempt to remove the result from the memory pool.
	Rem(resultID flow.Identifier) bool

	// ByID retrieve the execution result with the given ID from the memory pool.
	// It will return false if it was not found in the mempool.
	ByID(resultID flow.Identifier) (*flow.ExecutionResult, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will return a list of all approvals in the memory pool.
	All() []*flow.ExecutionResult
}

Results represents a concurrency-safe memory pool for execution results.

type TransactionTimings

type TransactionTimings interface {

	// Add adds a transaction timing to the mempool.
	Add(tx *flow.TransactionTiming) bool

	// ByID returns the transaction timing with the given ID from the mempool.
	ByID(txID flow.Identifier) (*flow.TransactionTiming, bool)
	// Adjust will adjust the transaction timing using the given function if the given key can be found.
	// Returns a bool which indicates whether the value was updated as well as the updated value.
	Adjust(txID flow.Identifier, f func(*flow.TransactionTiming) *flow.TransactionTiming) (*flow.TransactionTiming,
		bool)

	// All returns all transaction timings from the mempool.
	All() []*flow.TransactionTiming

	// Rem removes the transaction timing with the given ID.
	Rem(txID flow.Identifier) bool
}

TransactionTimings represents a concurrency-safe memory pool for transaction timings.

type Transactions

type Transactions interface {

	// Has checks whether the transaction with the given hash is currently in
	// the memory pool.
	Has(txID flow.Identifier) bool

	// Add will add the given transaction body to the memory pool. It will
	// return false if it was already in the mempool.
	Add(tx *flow.TransactionBody) bool

	// Rem will remove the given transaction from the memory pool; it will
	// will return true if the transaction was known and removed.
	Rem(txID flow.Identifier) bool

	// ByID retrieve the transaction with the given ID from the memory
	// pool. It will return false if it was not found in the mempool.
	ByID(txID flow.Identifier) (*flow.TransactionBody, bool)

	// Size will return the current size of the memory pool.
	Size() uint

	// All will retrieve all transactions that are currently in the memory pool
	// as a slice.
	All() []*flow.TransactionBody

	// Clear removes all transactions from the mempool.
	Clear()

	// Hash will return a fingerprint has representing the contents of the
	// entire memory pool.
	Hash() flow.Identifier
}

Transactions represents a concurrency-safe memory pool for transactions.