🔷 [Project Tracking] Resharding v3

[wacban]

Goals

• The ability to increase the blockchain capacity by increasing the number of shards
• The ability to balance the load across shards
• The ability to do the above fast
• The ability to do the above automatically (dynamic resharding)

References

Resharding Docs
Resharding V2 tracking issue

Tasks

• MVP Implementation

  • [ReshardingV3] State Witness #12019 @Longarithm
  • MemTrie @shreyan-gupta
  • [Tracking Issue] Flat storage for resharding V3 #12174 FlatState @Trisfald
  • [ReshardingV3] State #12050 @staffik
  • State Sync @marcelo-gonzalez
  • Shard Layout and non-contiguous shard ids @wacban
  • boundary accounts
  • Multiple resharding support
  • Misc
    • [ReshardingV3] - forknet testing and follow ups #12552
    • Transaction Pool resharding
    • Congestion Control integration
    • Yield Resume integration
    • Cold Storage integration (inc not losing data again)
    • ReadRPC integration
      • Dynamic Resharding
        • How to listen to that even from blockchain?
        • How to know the shard layout asap?
      • Will there be merges?
    • Make sure that all nodes have memtrie enabled
    • Node Restart handling
    • Fork handling & double signing
    • Validator Assignment
    • Chunk Headers have old data (inc shard id) when chunk is missing

• Design

  • Resharding Ideas Comparison
    • Decision: Instant Resharding
  • Shard splitting
    • Instant Resharding
    • Continuous Balancing
    • Resharding v2.1
  • Automatic Scheduling
  • Mid-Epoch / Next-Epoch Resharding

Design - Instant Resharding

• High level design
  • doc
• [ReshardingV3] Instant Resharding | Storage - State #11907 @staffik
  • How to split state in the db (inc migration if needed)
  • How to clean state after state sync
  • How to clean state after resharding (parent state)
  • overview doc
  • node hash @wacban
    • design doc
    • migration feasibility
  • Shard Columns @staffik
    • doc
  • Mapping @shreyan-gupta
  • Getting rid of State @tayfunelmas
• [ReshardingV3] Storage - FlatState #11909 @Longarithm
• Storage - MemTrie @shreyan-gupta
  • How to split state in memory
  • How to clean state after state sync
  • How to clean state after resharding (parent state)
  • Estimate the overhead and hardware requirements
  • Estimate how much time does it take to clone memtrie arena
• State Sync integration @marcelo-gonzalez
  • State for epoch T + 2 is dumped in T
  • StateSyncDumpProgress::Skipped
  • receipts proofs (filter_incoming_receipts_for_shard)
• Shard Merging
• [ReshardingV3] Receipts Reassignment #11966

Design - Continuous Balancing @Longarithm & @Trisfald

• High level design
  • doc
• Design document WIP
  • doc
  • How to handle large accounts?
    • account transfer
    • balancing manager should prevent large / busy accounts from hopping back and forth
  • Estimate and address the balancing overhead.
  • Account availability during transfer.
  • How to handle all sorts of receipts?
  • Estimate impact on the archival node storage.
  • Consider implementing a limit on account size.
  • Polish and verify design assumptions

Design - Resharding v2.1 @wacban

The old resharding is not particularly interesting because it takes at least an epoch to take effect. It's here mostly for completeness but it may be also worth considering it as a milestone towards the v3. Viability depends on the overlap with the end goal design and the amount of throw away work.

• High level design, Short Epochs
  • Resharding 2.1
• Suitability as milestone towards Instant Resharding

Design - Automatic Scheduling aka Dynamic Resharding

• High level design
  • Resharding Manager
• ReadRPC integration

Design - Mid-Epoch / Next-Epoch Resharding

The typical resharding operations, splitting and merging shards, require changes to the validator assignment. In order to execute resharding fast we will need to enhance the assignment to be able to be adjusted without the usual two epoch delay.

• High level design
  • doc
  • Some ideas were presented in the Instant Resharding doc
  • Mid-Epoch may not work well with State Sync :(

[wacban]

The design phase is now completed. We will be implementing the Instant Resharding approach. I will rearrange the issue to reflect the current work and I'll move the design task list down the description.

[walnut-the-cat]

Sept 2-13

• flat storage and state witness designs review and discussion

• resharding proof generation discussion

• memtrie implementation discussion

• proposal for changes to the state sync epoch during catchup and its implementation

• state handling: [ReshardingV3] State #12050

• mapping strategy for state implmenetation: [reshardingV3] State ShardUIdMapping - initial implementation #12084

• Implementation of Frozen MemTries and HybridMemTries that can deal with shared memory between MemTries ([memtrie] Introduce HybridArena and FrozenArena #12075)

• Some simplifications across the MemTries interface ([memtrie] Simplify MemTries interface #12073, [memtrie] Separate mutable interface for Arena and ArenaMemory #12069)

• Marcelo:

  • State sync doc, impl, 2 weeks
  • Definition of sync hash
  • Wait for 2 chunks to be produced
  • Flat storage may not be created in new layout + 2 chunks
  • Handle banning peers for not providing state parts

• Alex:

  • [ReshardingV3] State Witness #12019
  • WIP feat: stub for instant resharding state root creation #12083
  • State witness logic + split logic
  • Nodes generated from split logic may need to be committed back to state database

• Shreyan:

  • [memtrie] Introduce HybridArena and FrozenArena by shreyan-gupta · Pull Request #12075 · near/nearcore (github.com)
  • Implemented HybridArena for MemTries

• Adam:

  • [reshardingV3] State ShardUIdMapping - initial implementation #12084
  • Need to figure out whether we need to store the mapping in DB or in memory