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

• Atree Register Inlining and Data Deduplication #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
• [Execution State] Memory usage and performance optimisation flow-go#1744
• Improving efficiency when storing composite values (specially nested ones) cadence#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 👈
• 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! 🙏