Challenge requirements: ASSIGNMENT.md.

Std's channels have been replaced with tokio channels. The benchmark data with std channels has been kept for reference.

cargo r       # runs the app (--release to run the release version of the binary)
cargo t       # tests the app (--release to test the release version of the binary)

cargo bench          # runs the criterion benchmark at `./benches`
./load/vegeta.sh     # runs the load test with vegeta. It requires both vegeta (https://github.com/tsenart/vegeta/releases) and jq (https://jqlang.org/) to be installed. Configurable parameters can be found in the script
k6 run load/k6.js    # runs the load test with k6. It requires k6 to be installed: https://github.com/grafana/k6/releases. Configurable parameters can be found in the script

This repo has three branches: main, skiplist, and arc_mutex. Each branch proposes a different implementation over the ordered data structure and the concurrency pattern. All use the axum crate to implement REST-compatible APIs, as well as leveraging tokio as the async runtime.

As there's not much core code, I decided to leave it at lib.rs to guarantee compatibility with criterion.

The ordered data structure has been implemented with BTreeSet or BinaryHeap, depending on the branch. Since the standard library's (std) BinaryHeap allows for duplicated items, the implementations using the BinaryHeap make use of a side HashSet to prevent insertions of duplicated transactions.

• main uses tokio::sync::mpsc::channel with the BinaryHeap + HashSet. channel allows for bounded concurrency (number of channels set to 10'000). Multiple producers ingest incoming requests, but only one consumer modifies the data structure
• arc_mutex allows any incoming request to modify the data structure but it uses std's Arc and Mutex to synchronize the access. The default implementation uses the BinaryHeap, but in the same branch there's a version using the BTreeSet (which can be replaced in main.rs by changing AppState to AppStateBTreeSet). Both versions live in the same branch to allow running and comparing the criterion benchmarks
• skiplist uses SkipSet of the external crate crossbeam-skiplist, a thread-safe version of std's BTreeSet. Every thread is allowed to modify the data structure thanks to the nature of the crate: no synchronization mechanism is required

• Async version using tokio -> axum
• Performance profiling output (e.g., with criterion.rs, flamegraph, or perf) -> criterion and flamegraph
• Visual output of transaction queue state over time (even just CLI stats) -> pool size printed every 3 seconds

Here goes a brief explanation of how I would implement the other two bonus points.

I think consistency is important here: if the block builder retrieves some transactions (txs) and shortly after high-priority ones come in the mempool, when it's time to delete txs, the block builder only wants to delete those that have actually been included in a block.

• fetch(n: usize) -> Vec<Transaction> and drain(txs: Vec<Transaction>) -> easiest solution for the mempool, least user-friendly for the block builder as it has to resubmit the entire array of txs
• fetch(n: usize) -> Vec<Transaction> and drain(ids: Vec<String>) -> a bit more user-friendly for the block builder but the worst solution in terms of time-complexity as the code has to scan the whole data structure
• fetch(n: usize) -> Vec<Transaction> and drain(n: usize)

  • when the block builder calls fetch, the mempool would mark those txs as "to be deleted" via another HashSet. When the block builder then calls drain, the code would get the first transaction from the queue, check if its id exists in the HashSet and if so, remove it from both data structures. The whole process repeated n times.

    I understand such HashSet adds overhead in memory, but I think it is acceptable as if an id is a 64-bytes hash, then 1M of "to-be-deleted" hashes only add 64MB of memory usage.

    If new higher priority txs come in, some low-priority ones might become stale in the HashSet. In such scenario, the HashSet might be replaced for a BTreeSet, with txs ordered by time-to-live and a background task evicting such entries periodically. This is something that Redis does in a more sophisticated way with its "active expiration policy" (if you're curious, check my implementation here).

• features flags choosing the desired function
• macro running before the server and generating the implementation code depending on a configuration parameter

• Sustained-load benchmark with requests sent over the network
• Mixed benchmark of concurrent submit and drain
• log is more appropriate in a production environment
• More pool stats? e.g. real-time insertions and deletions, but in that case I'd definitely add the log crate and hide those logs behind a trace or debug level
• Explore other data structures and concurrency options: avl tree, crossbeam::bounded, crossbeam-queue, mpmc with SkipSet or Arc Mutex BTreeSet, actix-web, sharded skiplist/binary heap
• Definitely a configurable (and maybe dynamic) number of channels as well as a configurable stats interval printing