A formatter for a bespoke serialization for acyclic DepGraph objects. More...

#include <cluster_linearize.h>

Public Member Functions
template<typename Stream , typename SetType >
void	Unser (Stream &s, DepGraph< SetType > &depgraph)

Static Public Member Functions
static uint64_t	SignedToUnsigned (int64_t x) noexcept
	Convert x>=0 to 2x (even), x<0 to -2x-1 (odd). More...

static int64_t	UnsignedToSigned (uint64_t x) noexcept
	Convert even x to x/2 (>=0), odd x to -(x/2)-1 (<0). More...

template<typename Stream , typename SetType >
static void	Ser (Stream &s, const DepGraph< SetType > &depgraph)

Detailed Description

A formatter for a bespoke serialization for acyclic DepGraph objects.

The serialization format outputs information about transactions in a topological order (parents before children), together with position information so transactions can be moved back to their correct position on deserialization.

For each transaction t in the DepGraph (in some topological order);
- The size: VARINT(t.size), which cannot be 0.
- The fee: VARINT(SignedToUnsigned(t.fee)), see below for SignedToUnsigned.
- For each direct dependency:
  - VARINT(skip)
- The position of t in the cluster: VARINT(skip)
The end of the graph: VARINT(0)

The list of skip values encodes the dependencies of t, as well as its position in the cluster. Each skip value is the number of possibilities that were available, but were not taken. These possibilities are, in order:

For each previous transaction in the graph, in reverse serialization order, whether it is a direct parent of t (but excluding transactions which are already implied to be dependencies by parent relations that were serialized before it).
The various insertion positions in the cluster, from the very end of the cluster, to the front.
The appending of 1, 2, 3, ... holes at the end of the cluster, followed by appending the new transaction.

Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,_,G,E,_,D (where _ represent holes; unused positions within the DepGraph) but serialized in order A,B,C,D,E,F,G, because that happens to be a topological ordering. By the time G gets serialized, what has been serialized already represents the cluster F,A,C,B,_,E,_,D (in that order). G has B and E as direct parents, and E depends on C.

In this case, the possibilities are, in order:

[ ] the dependency G->F
[X] the dependency G->E
[ ] the dependency G->D
[X] the dependency G->B
[ ] the dependency G->A
[ ] put G at the end of the cluster
[ ] put G before D
[ ] put G before the hole before D
[X] put G before E
[ ] put G before the hole before E
[ ] put G before B
[ ] put G before C
[ ] put G before A
[ ] put G before F
[ ] add 1 hole at the end of the cluster, followed by G
[ ] add 2 holes at the end of the cluster, followed by G
[ ] add ...

The skip values in this case are 1 (G->F), 1 (G->D), 4 (G->A, G at end, G before D, G before hole). No skip after 4 is needed (or permitted), because there can only be one position for G. Also note that G->C is not included in the list of possibilities, as it is implied by the included G->E and E->C that came before it. On deserialization, if the last skip value was 8 or larger (putting G before the beginning of the cluster), it is interpreted as wrapping around back to the end.

Rationale:

Why VARINTs? They are flexible enough to represent large numbers where needed, but more compact for smaller numbers. The serialization format is designed so that simple structures involve smaller numbers, so smaller size maps to simpler graphs.
Why use SignedToUnsigned? It results in small unsigned values for signed values with small absolute value. This way we can encode negative fees in graphs, but still let small negative numbers have small encodings.
Why are the parents emitted in reverse order compared to the transactions themselves? This naturally lets us skip parents-of-parents, as they will be reflected as implied dependencies.
Why encode skip values and not a bitmask to convey the list positions? It turns out that the most complex graphs (in terms of linearization complexity) are ones with ~1 dependency per transaction. The current encoding uses ~1 byte per transaction for dependencies in this case, while a bitmask would require ~N/2 bits per transaction.

Definition at line 97 of file cluster_linearize.h.

Member Function Documentation

◆ Ser()

template<typename Stream , typename SetType >

static void cluster_linearize::DepGraphFormatter::Ser	(	Stream &	s,
		const DepGraph< SetType > &	depgraph
	)

inlinestatic

Construct a topological order to serialize the transactions in.

Which positions (incl. holes) the deserializer already knows when it has deserialized what has been serialized here so far.

Which depgraph index we are currently writing.

< How many potential parent/child relations we have skipped over.

Which depgraph index we are currently considering as parent of idx.

Definition at line 120 of file cluster_linearize.h.

Here is the call graph for this function:

◆ SignedToUnsigned()

static uint64_t cluster_linearize::DepGraphFormatter::SignedToUnsigned ( int64_t x )

inlinestaticnoexcept

Convert x>=0 to 2x (even), x<0 to -2x-1 (odd).

Definition at line 100 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Unser()

template<typename Stream , typename SetType >

void cluster_linearize::DepGraphFormatter::Unser	(	Stream &	s,
		DepGraph< SetType > &	depgraph
	)

inline

The dependency graph which we deserialize into first, with transactions in topological serialization order, not original cluster order.

Mapping from serialization order to cluster order, used later to reconstruct the cluster order.

How big the entries vector in the reconstructed depgraph will be (including holes).

< The new transaction's fee and size.

< The new transaction's ancestors (excluding itself).

< How many potential parents/insertions we have to skip.

Which topo_depgraph index we are currently considering as parent of topo_idx.

Definition at line 185 of file cluster_linearize.h.

Here is the call graph for this function:

◆ UnsignedToSigned()

static int64_t cluster_linearize::DepGraphFormatter::UnsignedToSigned ( uint64_t x )

inlinestaticnoexcept

Convert even x to x/2 (>=0), odd x to -(x/2)-1 (<0).

Definition at line 110 of file cluster_linearize.h.