Client: "best chain containing" operation

[rphmeier]

This is an operation that is necessary for the new consensus algorithm.
We want to be able to get the best chain containing a given block hash, which in the general case will be the best chain we have.

Probably will require adding a "children" entry for each block in the DB.

[snd]

under way at https://github.com/paritytech/substrate/tree/snd-issue-603

[snd]

after considering a naive solution i came up with a more efficient one.
both are laid out below. implementation for efficient solution is under way.
@rphmeier let me know whether you see any problems with it

naive solution

make children available in blockchain::Backend via

/// Returns block hashes for all blocks whose parent block is `id`
fn child_hashes(&self, id: BlockId<Block>) -> Result<Vec<Block::Hash>>;

store list of children for each block in storage/metadata.
each time a block is inserted append its hash to its parents list of children.

implement best_chains_containing_block_hash by going
down the whole "block tree" by repeatedly fetching children
until a set of blocks remain that have no children and all have the same
max length.

cons

• need to store children for each block
• search visits many blocks in an inefficient order (all blocks below the starting block)

efficient solution

keep track of the leaf block hashes (hashes of blocks without children) of the block tree in storage/metadata.
ordered by block their number (which puts the best chain(s) first).

the list of leaf block hashes is easy to maintain.
if a block is inserted it is added and its parent is removed.

when searching for the best chain containing target_hash
iterate over leaf block hashes (in order from best/longest to shortest)
and do the following for each:
go backwards from the leaf block hash
parent by parent (through header.parent_hash())
until the current block number is block_number(target_hash).
if that blocks hash is the target_hash return it.
otherwise stop going backwards for this chain and repeat for the next best leaf block hash.

pros

• less storage
  • the naive solution stores at least 1 child hash for every (except the last)
    block in the canonical chain
  • the efficient solution stores only one leaf block hash (last block)
    for the canonical chain
• fast common case
  • for the common case where best_chain_containing(target_hash) = canonical chain
    the efficient solution only visits the suffix of the canonical chain that starts at target_hash
• faster general case
  • visits suffixes of shortest chains last in the search
    whereas naive solution visits them first

[snd]

discussed this with @rphmeier:

it's possible that with certain methods of block production we will have a relatively large amount of small forks. over time, we could end up with lots of useless metadata about irrelevant leaves
the leaf nodes should be paired with their ancestor block in canonical chain (this needs to be updated on reorgs) and pruned on finality
other than that it's good!

i was looking for an alternative to "pairing the leaf nodes with their ancestor blocks and pruning on finality" that would also prevent the number of entries on the leaf list from getting out of hand.
since the pairing requires twice the storage and requires updating on reorgs.

how about this:
once there's a new final block F we iterate through the leaf list until we find a block P whose block number is equal or smaller than the number of F.
since the leaf list is ordered descending by block number we can then prune the suffix of the leaf node list starting at P.
this uses the fact that leaf blocks with a number smaller than the last final block will never be canonical.

the definition of the leaf list would change from
"list of blocks without children" to
"list of blocks without children that could end up being canonical in the future".

that should keep the leaf node list reasonably small and prevent it from growing infinitely and it doesn't require updates on reorg.

[snd]

@rphmeier also suggested

before iteration it should simply check if the block is in the canonical chain

to make the common case faster

[snd]

edit: no longer using this approach

storing leaf list in KeyValueDb

the above solution relies on storing an ordered list of block hashes
(block index entries in the implementation for performance reasons).

the list should support the following operations efficiently:

• iteration
• insert at specific location
• prune suffix (delete all after block x)

since all implementations but the in-memory implementation are
backed by a KeyValueDb we need to store the ordered list in there.

i'd suggest we store the list [A, B, C] as the following mapping
in its own column (to prevent key clashes):

b"start" -> A
A -> B
B -> C

b"start" is a special key to find the start of the list.

the implementation would be reusable for other lists that might need storing.

this is my first time working on the substrate backend/database part.
better solutions are greatly appreciated!

i'll go into more details in further comments

[snd]

edit: no longer using this approach

iterating the list

let COLUMN = Some(8);

let mut items: Vec<Vec<u8>> = Vec::new();

let next_key: Vec<u8> = b"start".into();

loop {
  match db.get(COLUMN, &next_key).unwrap() {
	Some(db_value) => {
	  let value = db_value.into_vec();
	  next_key.clear();
	  next_key.extend_from_slice(&value);
	  items.push(value);
	},
        // if no further mapping is found that means "end of list"
	None => { break; },
  }
}

// `items` now contains list contents

the real impl would be an iterator

[snd]

we could also store the entire list concatenated under a single key in the metadata column.
only if the KeyValueDb has no (or a sufficiently large) limit on value size.

this would make lookups faster (single get to retrieve entire list) but updates more expensive (entire list needs to be read and written to insert a single entry).

[rphmeier]

The leaf list approach sounds good to me! We might want to keep entries in the same column family with other chain data, but with keys prefixed.

[arkpar]

Do we need "best chain containing" only for unfinalised blocks?
Is there an upper limit on how long the returned chain might be?
If that's only required for unfinalized blocks it could be an in-memory structure that gets recreated on startup with no additional data stored in the DB.

[snd]

my understanding from previous conversations with @rphmeier is that we'll only need it for unfinalised blocks. since under certain scenarios there might be a lot of leaves (leaves of the block tree which best_containing uses) we'll prune finalized leaves.

currently (see PR) these leaves are stored with an in-memory structure that is used for reads and that is initialized on startup from leaves stored in the DB (iterating over a prefix). on block import both the leaves in DB and the in-memory structure get written to. it is easy to remove the DB leaves storage and have the in-memory structure be entirely recreated on startup. i think this is a good idea. it reduces complexity, stored data and any chance for stored leaves to get out of sync with the rest of the DB.

Is there an upper limit on how long the returned chain might be?

good question

[rphmeier]

We'll call it either for a recently finalized block or some unfinalized block which will usually be in near proximity to the finalized chain head (although no guarantees!)

There's no upper limit on the length of the chain, although we could add an artificial one of e.g. 256 (reducing the amount of blocks we could finalize at once). It would take some thinking whether that would not break the workings of the finality gadget. Since the chains are usually going to be short since forks are not that common, it's probably not important that we have a limit yet.