Make Trie Size MerkleDB compatible

[richardpringle]

This is a two-step process

• Add path's to branch nodes:
  Branch nodes will contain the compression and thus Extension nodes will only exist as dead-code
  Landed in Add path to Branch-Nodes (don't use Extension-Nodes) #344
• Remove Extension nodes:
  This part should be trivial
• Ensure hash-compatibility for PlainCodec

Note:
We need to test the effects of adding a path to the branch-nodes on performance

[richardpringle]

Initial results for insertion and reading without extension nodes

Note: This isn't supposed to be a perfect benchmark, this is just supposed to be a leading indicator of whether or not it's worth continuing to pursue MerkleDB compatibility by structure or request that MerkleDB add extension nodes.

Branch Nodes with Paths (no Extension Nodes)

1000 individual inserts without verification (no reads)

root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.827124086s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.07s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.692263419s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.70950371s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.98175621s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.899652169s

average time: 4.822s

2 individual inserts in batches of 100,000 without verification (no reads)

root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 3.953046377s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.02696871s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.030867711s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.098324585s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.105997336s

average time: 4.043s

1000 individual inserts with 100% verification

root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99      
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.611325252s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.239647252s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.569293211s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.740159752s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.07s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.418866752s

average time: 5.516s

2 individual inserts in batches of 100,000 with 100% verification

root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.606125544s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.411853253s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.424732711s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.392676878s
root ➜ /com.docker.devenvironments.code (remove-extension-node) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.417209253s

average time: 5.451s

Branch Nodes without Paths (Extension Nodes)

1000 individual inserts without verification (no reads)

root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 5.100619377s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.887870627s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 5.145393086s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.946307543s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 0 -s 99`
Generated and inserted 1000 batches of size 1 in 4.783746169s

average time: 4.973s

2 individual inserts in batches of 100,000 without verification (no reads)

root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99  
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.350950751s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.205662418s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.209157002s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.153208669s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 0 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 0 -s 99`
Generated and inserted 2 batches of size 100000 in 4.272027626s

average time: 4.238s

1000 individual inserts with 100% verification

root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99       
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.075127169s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.09s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.287121003s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.348910002s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.539677961s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 1000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 1000 -r 100 -s 99`
Generated and inserted 1000 batches of size 1 in 5.063398585s

average time: 5.263s

2 individual inserts in batches of 100,000 with 100% verification

root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.436908586s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.480105044s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.471086586s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.498475336s
root ➜ /com.docker.devenvironments.code (main) $ cargo run --release  --example insert -- -i 2 -b 100000 -r 100 -s 99
    Finished release [optimized + debuginfo] target(s) in 0.08s
     Running `/root/target/release/examples/insert -i 2 -b 100000 -r 100 -s 99`
Generated and inserted 2 batches of size 100000 in 5.478142918s

average time: 5.473s

Summary

Results

Copied from above

Branch with path on top
Extension node on the bottom

1000 individual inserts without verification (no reads)

average time: 4.822s
average time: 4.973s

2 individual inserts in batches of 100,000 without verification (no reads)

average time: 4.043s
average time: 4.238s

1000 individual inserts with 100% verification

average time: 5.516s
average time: 5.263s

2 individual inserts in batches of 100,000 with 100% verification

average time: 5.451s
average time: 5.473s

With this particular seed, only individual inserts with 100% verification were slower for the case of branch-nodes with paths. In my opinion, in stands to reason that it continues to be worth pursuing the removal of extension nodes in their entirety. Removing the extension nodes simplifies the code, allows for full MerkleDB hash compatibility, and does not appear to introduce any performance regressions at this time.

[rkuris]

Solved with new design