mempool

package
v0.18.0 Latest Latest
Warning

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

Go to latest
Published: Jun 9, 2021 License: AGPL-3.0 Imports: 5 Imported by: 16

Documentation

Overview

(c) 2019 Dapper Labs - ALL RIGHTS RESERVED

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

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 added in v0.14.0

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 ChunkRequestHistoryUpdaterFunc added in v0.17.0

type ChunkRequestHistoryUpdaterFunc func(uint64, time.Duration) (uint64, time.Duration, bool)

ChunkRequestHistoryUpdaterFunc is a function type that used by ChunkRequests mempool to perform atomic and isolated updates on the underlying chunk requests history.

func ExponentialUpdater added in v0.17.0

func ExponentialUpdater(multiplier float64, maxInterval time.Duration, minInterval time.Duration) ChunkRequestHistoryUpdaterFunc

ExponentialUpdater is a chunk request history updater factory that updates the retryAfter value of a request to multiplier * retryAfter. For example, if multiplier = 2, then invoking it n times results in a retryAfter value of 2^n * retryAfter, which follows an exponential series.

It also keeps updated retryAfter value between the minInterval and maxInterval inclusive. It means that if updated retryAfter value is below minInterval, it is bumped up to the minInterval. Also, if updated retryAfter value is above maxInterval, it is skimmed off back to the maxInterval.

Note: if initial retryAfter is below minInterval, the first call to this function returns minInterval, and hence after the nth invocations, the retryAfter value is set to 2^(n-1) * minInterval.

func IncrementalAttemptUpdater added in v0.17.0

func IncrementalAttemptUpdater() ChunkRequestHistoryUpdaterFunc

IncrementalAttemptUpdater is a chunk request history updater factory that increments the attempt field of request status and makes it instantly available against any retryAfter qualifier.

type ChunkRequests added in v0.17.0

type ChunkRequests interface {
	// ByID returns a chunk request by its chunk ID.
	//
	// There is a one-to-one correspondence between the chunk requests in memory, and
	// their chunk ID.
	ByID(chunkID flow.Identifier) (*verification.ChunkDataPackRequest, bool)

	// RequestHistory returns the number of times the chunk has been requested,
	// last time the chunk has been requested, and the retryAfter duration of the
	// underlying request status of this chunk.
	//
	// The last boolean parameter returns whether a chunk request for this chunk ID
	// exists in memory-pool.
	RequestHistory(chunkID flow.Identifier) (uint64, time.Time, time.Duration, bool)

	// Add provides insertion functionality into the memory pool.
	// The insertion is only successful if there is no duplicate chunk request with the same
	// chunk ID in the memory. Otherwise, it aborts the insertion and returns false.
	Add(request *verification.ChunkDataPackRequest) bool

	// Rem provides deletion functionality from the memory pool.
	// If there is a chunk request with this ID, Rem removes it and returns true.
	// Otherwise it returns false.
	Rem(chunkID flow.Identifier) bool

	// IncrementAttempt increments the Attempt field of the corresponding status of the
	// chunk request in memory pool that has the specified chunk ID.
	// If such chunk ID does not exist in the memory pool, it returns false.
	//
	// The increments are done atomically, thread-safe, and in isolation.
	IncrementAttempt(chunkID flow.Identifier) bool

	// UpdateRequestHistory updates the request history of the specified chunk ID. If the update was successful, i.e.,
	// the updater returns true, the result of update is committed to the mempool, and the time stamp of the chunk request
	// is updated to the current time. Otherwise, it aborts and returns false.
	//
	// It returns the updated request history values.
	//
	// The updates under this method are atomic, thread-safe, and done in isolation.
	UpdateRequestHistory(chunkID flow.Identifier, updater ChunkRequestHistoryUpdaterFunc) (uint64, time.Time, time.Duration, bool)

	// All returns all chunk requests stored in this memory pool.
	All() []*verification.ChunkDataPackRequest

	// Size returns total number of chunk requests in the memory pool.
	Size() uint
}

ChunkRequests is an in-memory storage for maintaining chunk data pack requests.

type ChunkStatuses added in v0.17.0

type ChunkStatuses interface {
	// ByID returns a chunk status by its chunk ID.
	// There is a one-to-one correspondence between the chunk statuses in memory, and
	// their chunk ID.
	ByID(chunkID flow.Identifier) (*verification.ChunkStatus, bool)

	// Add provides insertion functionality into the memory pool.
	// The insertion is only successful if there is no duplicate status with the same
	// chunk ID in the memory. Otherwise, it aborts the insertion and returns false.
	Add(status *verification.ChunkStatus) bool

	// Rem provides deletion functionality from the memory pool.
	// If there is a chunk status with this ID, Rem removes it and returns true.
	// Otherwise it returns false.
	Rem(chunkID flow.Identifier) bool

	// All returns all chunk statuses stored in this memory pool.
	All() []*verification.ChunkStatus

	// Size returns total number of chunk statuses in the memory pool.
	Size() uint
}

ChunkStatuses is an in-memory storage for maintaining the chunk status data objects.

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 added in v0.10.0

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 added in v0.14.0

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

	// AddReceipt adds 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 added in v0.11.0

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 OnEjection added in v0.13.0

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 added in v0.14.1

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
}

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 added in v0.14.0

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.

Directories

Path Synopsis
(c) 2019 Dapper Labs - ALL RIGHTS RESERVED
(c) 2019 Dapper Labs - ALL RIGHTS RESERVED

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL