1. Jun 11, 2024
    • Sebastian Kunert's avatar
      finalization: Skip tree route calculation if no forks present (#4721) · 96ab6869
      Sebastian Kunert authored
      ## Issue
      
      Currently, syncing parachains from scratch can lead to a very long
      finalization time once they reach the tip of the chain. The problem is
      that we try to finalize everything from 0 to the tip, which can be
      thousands or even millions of blocks.
      
      We finalize sequentially and try to compute displaced branches during
      finalization. So for every block on the way, we compute an expensive
      tree route.
      
      ## Proposed Improvements
      
      In this PR, I propose improvements that solve this situation:
      
      - **Skip tree route calculation if `leaves().len() == 1`:** This should
      be enough for 90% of cases where there is only one leaf after sync.
      - **Optimize finalization for long distances:** It can happen that the
      parachain has imported some leaf and then receives a relay chain
      notification with the finalized block. In that case, the previous
      optimization will not trigger. A second mechanism should ensure that we
      do not need to compute the full tree route. If the finalization distance
      is long, we check the lowest common ancestor of all the leaves. If it is
      above the to-be-finalized block, we know that there are no displaced
      leaves. This is fast because forks are short and close to the tip, so we
      can leverage the header cache.
      
      ## Alternative Approach
      
      - The problem was introduced in #3962. Reverting that PR is another
      possible strategy.
      - We could store for every fork where it begins, however sounds a bit
      more involved to me.
      
      
      fixes #4614
      96ab6869
  2. Jun 10, 2024
  3. Jun 08, 2024
  4. Jun 07, 2024
  5. Jun 06, 2024
  6. Jun 05, 2024
  7. Jun 04, 2024
  8. Jun 03, 2024