Ancestry trie of ledgers. More...

Collaboration diagram for ripple::LedgerTrie< Ledger >:

[legend]

Public Member Functions
	LedgerTrie ()

void	insert (Ledger const &ledger, std::uint32_t count=1)
	Insert and/or increment the support for the given ledger. More...

bool	remove (Ledger const &ledger, std::uint32_t count=1)
	Decrease support for a ledger, removing and compressing if possible. More...

std::uint32_t	tipSupport (Ledger const &ledger) const
	Return count of tip support for the specific ledger. More...

std::uint32_t	branchSupport (Ledger const &ledger) const
	Return the count of branch support for the specific ledger. More...

std::optional< SpanTip< Ledger > >	getPreferred (Seq const largestIssued) const
	Return the preferred ledger ID. More...

bool	empty () const
	Return whether the trie is tracking any ledgers. More...

void	dump (std::ostream &o) const
	Dump an ascii representation of the trie to the stream. More...

Json::Value	getJson () const
	Dump JSON representation of trie state. More...

bool	checkInvariants () const
	Check the compressed trie and support invariants. More...

Private Types
using	Seq = typename Ledger::Seq

using	ID = typename Ledger::ID

using	Node = ledger_trie_detail::Node< Ledger >

using	Span = ledger_trie_detail::Span< Ledger >

Private Member Functions
std::pair< Node *, Seq >	find (Ledger const &ledger) const
	Find the node in the trie that represents the longest common ancestry with the given ledger. More...

Node *	findByLedgerID (Ledger const &ledger, Node *parent=nullptr) const
	Find the node in the trie with an exact match to the given ledger ID. More...

void	dumpImpl (std::ostream &o, std::unique_ptr< Node > const &curr, int offset) const

Private Attributes
std::unique_ptr< Node >	root

std::map< Seq, std::uint32_t >	seqSupport

Detailed Description

template<class Ledger>
class ripple::LedgerTrie< Ledger >

Ancestry trie of ledgers.

A compressed trie tree that maintains validation support of recent ledgers based on their ancestry.

The compressed trie structure comes from recognizing that ledger history can be viewed as a string over the alphabet of ledger ids. That is, a given ledger with sequence number seq defines a length seq string, with i-th entry equal to the id of the ancestor ledger with sequence number i. "Sequence" strings with a common prefix share those ancestor ledgers in common. Tracking this ancestry information and relations across all validated ledgers is done conveniently in a compressed trie. A node in the trie is an ancestor of all its children. If a parent node has sequence number seq, each child node has a different ledger starting at seq+1. The compression comes from the invariant that any non-root node with 0 tip support has either no children or multiple children. In other words, a non-root 0-tip-support node can be combined with its single child.

Each node has a tipSupport, which is the number of current validations for that particular ledger. The node's branch support is the sum of the tip support and the branch support of that node's children:

@code
node->branchSupport = node->tipSupport;
for (child : node->children)
   node->branchSupport += child->branchSupport;
@endcode

The templated Ledger type represents a ledger which has a unique history. It should be lightweight and cheap to copy.

// Identifier types that should be equality-comparable and copyable
struct ID;
struct Seq;
 
struct Ledger
{
   struct MakeGenesis{};
 
   // The genesis ledger represents a ledger that prefixes all other
   // ledgers
   Ledger(MakeGenesis{});
 
   Ledger(Ledger const&);
   Ledger& operator=(Ledger const&);
 
   // Return the sequence number of this ledger
   Seq seq() const;
 
   // Return the ID of this ledger's ancestor with given sequence number
   // or ID{0} if unknown
   ID
   operator[](Seq s);
 
};
 
// Return the sequence number of the first possible mismatching ancestor
// between two ledgers
Seq
mismatch(ledgerA, ledgerB);

The unique history invariant of ledgers requires any ledgers that agree on the id of a given sequence number agree on ALL ancestors before that ledger:

@code
Ledger a,b;
// For all Seq s:
if(a[s] == b[s]);
    for(Seq p = 0; p < s; ++p)
        assert(a[p] == b[p]);
@endcode

◆ LedgerTrie()

template<class Ledger >

ripple::LedgerTrie< Ledger >::LedgerTrie ( )

Definition at line 439 of file LedgerTrie.h.

Member Function Documentation

◆ find()

template<class Ledger >

std::pair<Node*, Seq> ripple::LedgerTrie< Ledger >::find ( Ledger const & ledger ) const

private

Find the node in the trie that represents the longest common ancestry with the given ledger.

Returns: Pair of the found node and the sequence number of the first ledger difference.

Definition at line 368 of file LedgerTrie.h.

◆ findByLedgerID()

template<class Ledger >

Node* ripple::LedgerTrie< Ledger >::findByLedgerID	(	Ledger const &	ledger,
		Node *	parent = `nullptr`
	)		const

private

Find the node in the trie with an exact match to the given ledger ID.

Returns: the found node or nullptr if an exact match was not found.

Note: O(n) since this searches all nodes until a match is found

Definition at line 406 of file LedgerTrie.h.

◆ dumpImpl()

template<class Ledger >

void ripple::LedgerTrie< Ledger >::dumpImpl	(	std::ostream &	o,
		std::unique_ptr< Node > const &	curr,
		int	offset
	)		const

private

Definition at line 422 of file LedgerTrie.h.

◆ insert()

template<class Ledger >

void ripple::LedgerTrie< Ledger >::insert	(	Ledger const &	ledger,
		std::uint32_t	count = `1`
	)

Insert and/or increment the support for the given ledger.

Parameters

ledger	A ledger and its ancestry
count	The count of support for this ledger

Definition at line 449 of file LedgerTrie.h.

◆ remove()

template<class Ledger >

bool ripple::LedgerTrie< Ledger >::remove	(	Ledger const &	ledger,
		std::uint32_t	count = `1`
	)

Decrease support for a ledger, removing and compressing if possible.

Parameters

ledger	The ledger history to remove
count	The amount of tip support to remove

Returns: Whether a matching node was decremented and possibly removed.

Definition at line 535 of file LedgerTrie.h.

◆ tipSupport()

template<class Ledger >

std::uint32_t ripple::LedgerTrie< Ledger >::tipSupport ( Ledger const & ledger ) const

Return count of tip support for the specific ledger.

Parameters

ledger The ledger to lookup

Returns: The number of entries in the trie for this exact ledger

Definition at line 589 of file LedgerTrie.h.

◆ branchSupport()

template<class Ledger >

std::uint32_t ripple::LedgerTrie< Ledger >::branchSupport ( Ledger const & ledger ) const

Return the count of branch support for the specific ledger.

Parameters

ledger The ledger to lookup

Returns: The number of entries in the trie for this ledger or a descendant

Definition at line 603 of file LedgerTrie.h.

◆ getPreferred()

template<class Ledger >

std::optional<SpanTip<Ledger> > ripple::LedgerTrie< Ledger >::getPreferred ( Seq const largestIssued ) const

Return the preferred ledger ID.

The preferred ledger is used to determine the working ledger for consensus amongst competing alternatives.

Recall that each validator is normally validating a chain of ledgers, e.g. A->B->C->D. However, if due to network connectivity or other issues, validators generate different chains

    /->C
A->B
    \->D->E

we need a way for validators to converge on the chain with the most support. We call this the preferred ledger. Intuitively, the idea is to be conservative and only switch to a different branch when you see enough peer validations to know another branch won't have preferred support.

The preferred ledger is found by walking this tree of validated ledgers starting from the common ancestor ledger.

At each sequence number, we have

The prior sequence preferred ledger, e.g. B.
The (tip) support of ledgers with this sequence number,e.g. the number of validators whose last validation was for C or D.
The (branch) total support of all descendants of the current sequence number ledgers, e.g. the branch support of D is the tip support of D plus the tip support of E; the branch support of C is just the tip support of C.
The number of validators that have yet to validate a ledger with this sequence number (uncommitted support). Uncommitted includes all validators whose last sequence number is smaller than our last issued sequence number, since due to asynchrony, we may not have heard from those nodes yet.

The preferred ledger for this sequence number is then the ledger with relative majority of support, where uncommitted support can be given to ANY ledger at that sequence number (including one not yet known). If no such preferred ledger exists, then the prior sequence preferred ledger is the overall preferred ledger.

In this example, for D to be preferred, the number of validators supporting it or a descendant must exceed the number of validators supporting C plus the current uncommitted support. This is because if all uncommitted validators end up validating C, that new support must be less than that for D to be preferred.

If a preferred ledger does exist, then we continue with the next sequence using that ledger as the root.

Parameters

largestIssued The sequence number of the largest validation issued by this node.

Returns: Pair with the sequence number and ID of the preferred ledger or std::nullopt if no preferred ledger exists

Definition at line 677 of file LedgerTrie.h.

◆ empty()

template<class Ledger >

bool ripple::LedgerTrie< Ledger >::empty ( ) const

Return whether the trie is tracking any ledgers.

Definition at line 775 of file LedgerTrie.h.

◆ dump()

template<class Ledger >

void ripple::LedgerTrie< Ledger >::dump ( std::ostream & o ) const

Dump an ascii representation of the trie to the stream.

Definition at line 783 of file LedgerTrie.h.

◆ getJson()

template<class Ledger >

Json::Value ripple::LedgerTrie< Ledger >::getJson ( ) const

Dump JSON representation of trie state.

Definition at line 791 of file LedgerTrie.h.

◆ checkInvariants()

Private Member Functions

Private Attributes

Detailed Description

template<class Ledger> class ripple::LedgerTrie< Ledger >

Member Typedef Documentation

◆ Seq

◆ ID

◆ Node

◆ Span

Constructor & Destructor Documentation

◆ LedgerTrie()

Member Function Documentation

◆ find()

◆ findByLedgerID()

◆ dumpImpl()

◆ insert()

◆ remove()

◆ tipSupport()

◆ branchSupport()

◆ getPreferred()

◆ empty()

◆ dump()

◆ getJson()

◆ checkInvariants()

Member Data Documentation

◆ root

◆ seqSupport

template<class Ledger>
class ripple::LedgerTrie< Ledger >