sync v2

[dshulyak]

Description

syncv2 protocol uses recursive set reconciliation to make sure the nodes are always in sync.
It will replace existing sync, providing the following benefits:

• avoid expensive database queries that happen very often with current ATX syncer, namely, ax/1 epoch queries
• make it possible to split large sync requests between multiple peers ("torrent style")
• make it very cheap to verify if 2 nodes are in sync
• help resolve small differences between nodes with very little network traffic and resource usage
• make it more practical to sync from scratch (this may require some additional database optimizations)
• eventually, replace gossip for ATXs and malfeasance proofs

The plan is to use syncv2 for ATXs only initially, later adding support for malfeasance proofs, then extending the use of the protocol to active set synchronization, etc.

The recursive set reconciliation protocol is based on Range-Based Set Reconciliation paper by Aljoscha Meyer.
The multi-peer reconciliation approach is loosely based on SREP: Out-Of-Band Sync of Transaction Pools for Large-Scale Blockchains paper by Novak Boškov, Sevval Simsek, Ari Trachtenberg, and David Starobinski.

Full description of the syncv2 protocol

TODO

• Set reconciliation machinery
  • [Merged by Bors] - syncv2: pairwise set reconciliation go-spacemesh#6350
  • [Merged by Bors] - sync2: implement multi-peer synchronization go-spacemesh#6358
  • [Merged by Bors] - sync2: improve rangesync Receive semantics go-spacemesh#6404
  • [Merged by Bors] - sync2: add sqlstore go-spacemesh#6405
  • [Merged by Bors] - sync2: implement database-backed sync based on FPTree go-spacemesh#6406
• Fixes/improvements
  • [Merged by Bors] - sql: add Database.WithConnection go-spacemesh#6445
  • sync2: dbset: use single connection for each sync session go-spacemesh#6446
  • sync2: multipeer: fix edge cases go-spacemesh#6447
  • [Merged by Bors] - sync2: fptree: fix deadlock go-spacemesh#6475
  • [Merged by Bors] - fetch: smarter peer selection go-spacemesh#6477
  • [Merged by Bors] - sync2: fptree: fix race in SyncedTable go-spacemesh#6491
• sync2: ATX integration go-spacemesh#6448
• Testing before release
  • Verify on testnet-15
  • Verify mainnet sync against several mainnet nodes
  • Enable server-only mode on the whole mainnet (passive sync)
  • Test against multiple syncv2 servers on mainnet
• Enable active syncv2 for mainnet
• Malfeasance sync
• ActiveSet sync
  • Use per-ATX-ID syncv2 to distribute active sets instead of sending them as the whole blob
  • See if we can stop hinting active set IDs
• Further improvements
  • Increase fingerprint size to 16 bytes instead of 12 to increase collision resistance
  • Drop old sync and unused fetcher requests/handlers
  • Refactor the fetcher
  • Compact bitstream-based protocol (may provide 2x-3x traffic reduction)
  • Improved recent sync based on sending (normal, non-counting) Bloom filters, with local counting Bloom filters keeping track of recent items
  • Try to replace ATX / malfeasance gossip

---

Original issue contents

this is a placeholder (not a spec) for all known sync improvements:

• drop custom communication protocol for fetcher and use stream per request

this was implemented way before project switched to libp2p and had other requirements in mind. right now this code has no benefits.

• efficient sync from scratch

the goal is to have implementation that makes good use of hardware resources:

• limited by network throughput it can get from peers. good metric is how fast state is synced based on total throughput it can get from peers. for example if it can get 10MB/s from peers and total unique data is 1GB, then whole sync should take ~100s

• downloading data should not be blocked by validation and writing to disk. this is straighforward to solve with pipelining, but will require some changes in a way sync interacts with validators

• dos resistance

current implementation lacks protection against abuse. some queries are expensive and we should rate limit them in a way that allows honest nodes to get data that they need, and prevents abusers from causing harm.

additionally every sync endpoint should be fuzzed. it needs to be taken into account when writing code for it.

• hash resolution that also download late data (atxs/ballot/malfeasance proofs)

existing implementation may miss out of order data. this is required long term for consensus correctness.
the implementation idea was to index data by received timestamp, and send such data to peers according to the timestamp.

---

from that list above it will be good implement 3 first items within 3 months. 4th item in 6 month or so

[pigmej]

We should also make it so that requests are evenly split, because right now they're not.

I understand the need for recent layers (yellow), but all others are DDoSing nodes.

[lrettig]

We should also make it so that requests are evenly split, because right now they're not.

I understand the need for recent layers (yellow), but all others are DDoSing nodes.

I don't understand any of what I'm looking at here. What does this mean? What are the colors? What are the axes?

[fasmat]

@lrettig: Requests for layer data comes in bursts, roughly every 5 minutes. For recent layers (yellow - recent 10 layers) this is OK, but for older layers (other colours, e.g. blue - last 2000 layers) this should be more evenly spread out to avoid spikes of requests / traffic that could be spread across a larger timeframe.

[pigmej]

very good summary from @fasmat that's exactly what it is. X time, Y number, colors, and legend "layers behind CurrentLayer at the time of asking.

[ivan4th]

Current code related to synvc2 effort is here: spacemeshos/go-spacemesh#5769
The generic peer-to-peer set reconciliation algorithm based on the "monoid tree" structure is already implemented.
The work is being done to perform "SREP"-style" multi-peer sync that eventually can replace gossip.

There's also another proposal of a potentially simpler sync approach, but it makes an assumption that transferring e.g. a month worth of ATX IDs is and always will be cheap, and while this assumption may (or may not) hold for a while for a while after the ATX merge, it is not guaranteed to hold in the long run

[ivan4th]

In order to improve the efficiency of the set reconciliation algorithm, we need LayerID field in ATXv2. It is NOT critical to be able to validate that field, b/c some bad actors using some invalid LayerID values in ATXs cannot cause noticeable performance degradation, given the honest majority.
Discussion: spacemeshos/go-spacemesh#5785 (comment)

[ivan4th]

After research discussion:
While it might not be really easy or efficient to add LayerID to the ATXs, the efficiency of sync can be improved in the following manner: a time filter is applied to the set based reconciler, so that only items which were received by the means of gossip some time ago (e.g. a minute) are reconciled.
Additional note: this might even work with the current gossip, so that the set reconciler quickly and efficiently fixes any data missed by the gossip mechanism.

[ivan4th]

Current progress: the multipeer reconciliation code has been added with support for both split-sync ("serve") and full-sync mode.
It appears that for efficient review of the syncv2 code the big PR #5769 needs to be split into smaller parts.
After a bit of stabilization and refactoring, the following PRs will be produced:

• SyncTree
• pairwise reconciler
• multi-peer reconciler
• integration with the existing syncer for ATXs and malfeasant identities

syncv2 will be feature-gated, initially. At some point later, we'll first enable syncv2 server across the network that will not initiate any sync by itself, and then, after some time, full syncv2 implementation will replace the current sync.

[ivan4th]

Pairwise sync part: spacemeshos/go-spacemesh#6350

[ivan4th]

syncv2 related PRs: https://github.com/spacemeshos/go-spacemesh/pulls?q=is%3Apr+label%3Aarea%2Fsyncv2

[ivan4th]

Updated issue description for easier tracking of this issue.