Modularity and Testing: Case Study of the Miner Loop Optimizations

[gregorycoppola]

Introduction

The recent work on optimizing the miner loop’s iteration of the mempool (#3326, #3337) has been interesting on many fronts.

One question which has come up is:

• how should “iteration” through the mempool be structured

The options that have been considered we will call:

• monolithic
  • structure
    • all logic for a problem is in a single black-box method
  • testing
    • only one opportunity to pass in inputs and get outputs
• modular
  • structure
    • breaks a monolithic function into a directed acyclic graph of parts
    • optional: restrict interfaces used to a very small set, even just Iterator
  • testing
    • have the opportunity to pass in inputs and get outputs for each little part

DAG Representation of Mempool Iterator

The “modular” approach discussed here represents the iteration implicit in iterate_candidates as it is in #3337 into a directed acyclic graph-structured pipeline, where each stage uses type Iterator. Blue boxes represent iterators of MempoolTxMinimalInfo objects, and the green box represents an iterator of StacksTransaction. The orange circle represents an end result.

Functions

The function modules depicted are:

• creation iterators
  • create a Rust Iterator from the database
• transformation iterators (map)
  • mix two (or N) iterators randomly
  • filter by nonces
    • either
      • caching version
      • non-caching version
  • transform from MinimalTxInfo into StackTransaction by deserializing
• reduce nodes
  • turn iterators into result objects

Testing

“Modular” Testing

The main benefit of using an Itetator pattern for testing is that one can write very specific tests for each module.

In this case, we can individually test:

• read from SQL
  • test that fee rate table from tiny db is really sorted by fee
  • test that null rate table from tiny db is really sorted by acceptance time
• randomly mix iterators
  • can pass in a random generator with a canned seed, so it has predictable behavior
• filter by nonces
  • test the basic version specifically
  • test the caching version specifically
• deserialize

“Black Box” Testing

By putting the entire logic of this pipeline into a single method, we are creating a “black box”, in which the individually separable operations in the DAG formulation can no longer be tested individually, but must be tested all together.

For example, if we want to test the caching of nonce checks, this has to be done in the presence of the random mixing. There is currently no parameter for the random number generator in iterate_candidates, and adding one just for testing clutters the interface.

Dimensions of “Modularity”

There are two dimensions on which we can measure modularity:

• separable parts
  • key parts of the computation flow can be separated and tested individually
• minimal interfaces
  • all ops in the system instantiate interfaces
    • mainly just Iterator
  • the operation nodes are either of type
    • map
      • transform one (or N) iterators into one iterator
    • reduce
      • transform an iterator (or N) into a non-iterator result

The Borrow Checker

The translation of #3337 into a formulation that uses only Iterator got further than I initially thought: #3344. I was able to capture the lifetime of rusqlite::Connection by using the type:

• Iterator<Item=M> + 'connection

However, there was ultimately a case in which the translation of #3337 into an abstract iterator framework required, and using the stacks-node codebase as it is, would require over-ruling the borrow checker:

let &mut clarity_tx:<C: ClarityConnection> = // from input

// first borrow of `clarity_tx`
let mut tx_iterator = get_filtered_transactions_iterator(
            connection,
            clarity_tx,
            null_estimate_fraction);

for tx in tx_iterator {
        // second borrow of `clarity_tx`
        // fails to pass borrow checker
        match todo(clarity_tx, &tx, self.cost_estimator.as_mut()) { ... }
}

This is an interesting example because it shows a concrete historical case from stacks-node in which something we do approve of as working (#3337) will be over-ruled in a different formulation (#3344) by the borrow-checkers rule against multiple borrows.

In other words, there are cases on a single-core machine where some object can be borrowed as mutable multiple times, and this is in fact the desired behavior.