Optimize atree to reduce Flow's mtrie size and reduce number of reads

[fxamacker]

Issue To Be Solved

We should make Execution Nodes use less memory without sacrificing performance. Also, given the same user data growth rate, we should reduce the rate of Execution Node system requirements growth.

Suggested Solution and Implementation

• https://github.com/onflow/atree/pull/342
• Also see https://github.com/dapperlabs/flow-go/issues/6320 and other PRs

Solution requires changes to onflow/atree, onflow/cadence, onflow/flow-go, and data migration.

See also:

• https://github.com/dapperlabs/flow-go/issues/6320
• https://github.com/onflow/flow-go/issues/1744
• https://github.com/onflow/cadence/issues/1854

Atree Inlining & Deduplication

Before/After Comparison Using Aug 14, 2024 Devnet State

Mtrie Nodes and Atree Payloads

Atree Payload Sizes (bytes)

#### Total Counts | | Before | After | Change | | :---: | ---: | ---: | ---: | | mtrie nodes | 1,182,195,945 | 343,949,052 | -838,246,893 | | atree payloads | 455,399,623 | 102,283,931 | -353,115,692 | #### Total Sizes | | Before | After | Change | | :---: | ---: | ---: | ---: | | mtrie nodes | 113.49 GB | 33.02 GB | -80.47 GB | | atree payloads | 87.74 GB | 69.28 GB | -18.46 GB | | combined | 201.23 GB | 102.30 GB | -98.93 GB |

| | Before | After | | :---: | ---: | ---: | | count | 455,399,623 | 102,283,931 | | mean | 192.7 | 677.4 | | std | 996.4 | 2,065.7 | | min | 13 | 22 | | 25% | 88 | 199 | | 50% | 139 | 665 | | 75% | 206 | 1,043 | | 99% | 876 | 1,267 | | 99.5% | 1,078 | 1,453 | | max | 5,853,892 | 5,853,892 |

Atree inlining and data deduplication on testnet indicates:

• Reduced memory usage by about 1/2 (on testnet) but results may be more modest on mainnet :point_left:
• Block execution speed was also 7% faster according to test results shared by @j1010001
• Significantly reduced number of payloads
• Significantly reduced number of nodes (non-payloads)
• Significantly reduced total combined size of all payloads
• Reduced data growth rate (given same data)
• Also expected to benefit other db and software (even if not on EN) if they store/index/cache payloads

NOTE: Impact on testnet and mainnet will differ, depending on actual usage, data, etc.

Impact on memory and storage size

These charts should probably be updated when time allows.

Impact on payload count and node count

These charts should probably be updated when time allows.

[j1010001]

Complete TPS throughput test before closing:

Test 1 - non-inlined state

• [ ] Spin up an EN
• [ ] remove exec results for ~100K blocks
• [ ] re-execute blocks on a non-inline state - capture TPS + block exec time

Test 2 - atree-inlined state

• [ ] migrate the state with Atree inlining
• [ ] remove exec results for ~100K blocks
• [ ] re-execute blocks on a atree-inlined state - capture TPS + block exec time

Doc that contains necessary steps: https://www.notion.so/flowfoundation/Execution-Fork-Handbook-a8b70533978c44c5963bc68af99a536d

[fxamacker]

@j1010001 thanks again for providing testnet memory reduction screenshot we can share on GitHub!

• atree smoke tests completed 517 hours with no problems (I manuallly stopped it last week)
• I also manually compared diff-states results (1.8GB JSONL report) after reexecuting 1,000 blocks
  • https://discord.com/channels/613813861610684416/1108968095982293002/1266058761412280341
• these are in addition to check-storage command showing no problems on testnet data after spork

Closing this as completed. Please re-open if needed! :pray: