feat: Design and implement a new sync model that doesn't rely on full block history

[sanjayprabhu]

Snapchain currently syncs in two ways:

• Snapshot sync which syncs block state and account state at the same time by downloading a copy of the db
• block sync which syncs and replays blocks to regenerate current account state from historical transactions

Because snapchain design intends to throw away vast majority of historical blocks, we need an additional sync mechansim that's decentralized and works with nodes that don't have full block history.

Ideally, it would work like this:

1. When you start a brand new node, it fetches the latest block.
2. For all accounts in that block, atomically fetch the account state as of that block via a new API
3. Persist account state, verify the merkle roots match for the account and proceed to the next block and repeat the process.
4. Deal with complications like rapidly changing accounts, byzantine peers, etc

[defnotpaul]

Moving some of the conversation we've had to this GH issue:

Partially-synced state

We're running with the assumption that nodes operating in this mode will potentially always be in a partially synced state. E.g. accounts that don't have any activity after the initially synced block will never have their state replicated to the node. Is that correct? Will we also pull all the accounts associated with follow actions that occur in each block? That seems useful, but we'd still be left with gaps in the social graph for past follow actions - e.g. Alice followed Bob before the initial sync block, but Alice followed Charlie in the initial sync block. After syncing the initial block, we'd have data on Alice and Charlie, but not Bob?

@sanjayprabhu:

Hopefully not always. They will be in a partially synced state until they catch up, but eventually, they should sync all accounts, even ones that didn't change recently. It does mean that the network at any point will have nodes that have both partial and full state, and we need to handle syncing from both kinds of nodes.

I think it's better for the network to ensure that any node that's not actively syncing has full account state. It's possible that in the future we want to allow node operators flexibility on which accounts to sync, but we don't have to solve for that now.

Sync strategy

Roughly speaking, it seems like we'd have a couple paths for syncing accounts in this mode: one for accounts that we've never seen (fetch all the account state via a new API), and then incrementally applying state changes for those that exist (the existing method for updates), but correct me if I'm wrong.

@sanjayprabhu:

Yes, though most accounts are quite small (median account has 200 messages), so maybe the first cut of this treats both the same.

As for the API that fetches state for "unknown" accounts at each successive block, do you have any thoughts on how we'd deal with the scenario where my local node is at height N, and a peer node is at some other height (N +/- M)? I think the N - M case is fairly trivial as a peer node could just return some error/result indicating that it hasn't caught up that far, but the N + M case feels a bit trickier. Is data stored in such a way that we can query state at a particular block height?

@sanjayprabhu:

Yes, this is the tricky part. Account state is not tagged with block height currently. We probably need to start doing that. Another option is starting a rocksdb read transaction (snapshot) at the time the api is first hit, and keeping that open for a while until the client can sync. Most accounts don't change every block, so block height being off may not be a problem as long as the last block the account merkle root changed is the same. For cases where accounts do change every block, then we need to get the entire state as of one block (may not be feasible for large accounts) or keep the transaction open so we have a view of the account as of a particular block.

Follow-up questions/thoughts

Syncing large accounts

@sanjayprabhu, you mentioned that some of the larger accounts may not be feasibly synced in a single request. Do you have a sense of the scale of these accounts? What may be challenging here for a node that's undergoing this sync process is that it won't know ahead of time the size of an account's state.

Knowing when you're "done" syncing

This strategy also comes with the challenge of knowing when a node has reached a state that's fully synced. I need to dig in a bit deeper, but I'm curious to know if you have any thoughts on how we might understand that we've achieved this state. I imagine that if we're able to locate accounts that haven't been synchronized yet, we can likely determine a node's status in terms of partial/complete sync, but I may be missing something.

Broadening the sync surface area via follows

In order to deal with the partial sync issue, do we think it's worth exploring a strategy that employs some kind of traversal through the network graph to sync accounts? For example, after we do a sync of an account for a new block, we could enqueue accounts that the synced account follows to sync.

This may have some challenges in terms of latency, and may need to be throttled so that the node can continue ingesting new blocks. We also likely don't want to flood peers with too many requests all at once as part of this process.

Servicing requests as a partially-synced node

As a node that's in a partially synced state, how do we expect it to behave when servicing requests over the API?

Some example cases where this might be noticeable:

castsByParent, castsByMention, (and others) - in these types of API calls the node may have sufficient data to service the request (e.g. the cast or resource being referenced exists due to backfilling an account), but will only have a partial view of the state due to only having synced a subset of all accounts.

Would we want the API to continue servicing these requests with partial data, or wait until fully synced?

[sanjayprabhu]

Syncing large accounts

I believe the really big accounts have on the order of 10s of thousands of messages. I don't think there are any that have 100k+ but it's possible. Basically, as long as the user is willing to pay for it via storage units, they can store as much as they wish. The merkle trie has a num_messages field at every node, and you can query the tree (very cheap) at the account level to get the total number of messages it has. See example

snapchain/src/storage/store/stores.rs

Lines 236 to 240 in 42dbfa1

	let count = self.trie.get_count(
	&self.db,
	txn_batch,
	&TrieKey::for_message_type(fid, each_message_type.into_u8()),
	) as u32;

Knowing when you're "done" syncing

I suspect we'll have to modify the merkle tree to handle this somehow. I think we'll need to mark accounts that are not sync'd yet and distinguish them from accounts that have no data. When we're syncing partial accounts, we need to fetch the sibling branches and other top level nodes so the merkle root can be correctly validated. So the tree needs to have a concept of being partially full anyway. So, seems like the obvious place to keep track of other accounts.

There may be other alternatives as well. Account ids right now are simple monotonic numbers. So we could just keep track of accounts ids we have sync'd and the fill in gaps.

Broadening the sync surface area via follows

I don't think the sync logic should care about the actual data being sync'd. This should operate a level above the messages. The follow messages may not be that useful anyway because a) the fids are sharded, and sync on one shard shouldn't affect another shard, and b) the accounts that need to be sync'd first are likes ones that changed most recently and follows are probably uncorrelated to this (or even if they were, it would be too noisy).

Servicing requests as a partially-synced node

Good question. I think in getInfo, we should return sync status, and then if you query for an unsync'd fid (any api with an explicit fid in the request), we can return an error (since we're tracking them anyway as per above). For other apis where it's harder (like castsByParent), I think it's ok to return partial data.