Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
3.9 kB · 71 lines
Go
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172// Package reposync implements a verifiable, resumable, prefix-bounded walk of a// remote atproto repository's Merkle Search Tree (MST).//// The motivating problem: streamplace only cares about the `place.stream.*`// records in an account's repo, but the only "repair" primitive atproto gives us// out of the box is `com.atproto.sync.getRepo`, which downloads the entire repo// as a CAR. Because MST keys are `collection/rkey` strings sorted bytewise, every// record we care about lives in one contiguous key range, so we can instead walk// only the subtrees that overlap that range: O(records-we-want + log n) blocks// instead of O(repo).//// # Verification//// Every block is dag-cbor addressed by CID. A [BlockFetcher] must check that the// bytes it returns hash to the CID that was requested, so the whole walk is// chained to the CID in the signed commit ([FetchVerifiedHead]). A remote PDS// therefore cannot forge record contents, nor can it silently omit a record from// the walked range: an omission shows up as a missing block, which is an error.//// # Semantics//// - Completeness. When [Walker.WalkPrefix], [Walker.WalkRanges] or// [Walker.Resume] return nil, the set of records passed to the visitor is// exactly the set of in-range keys in the tree rooted at the given root.// A block the server does not return is an error ([ErrMissingBlock]), never// a skip. This is deliberately unlike indigo's partial-tolerant// mst.LoadTreeFromStore.//// - At-least-once emission. A walk checkpoints its [Frontier] only after the// records for that step have been handed to the visitor. Interrupting a walk// and resuming from the last checkpoint therefore re-emits the records of the// step that was in flight. Visitors must be idempotent, keyed by// (path, record CID).//// - Key order. Records are emitted in ascending bytewise key order across the// whole walk, not merely within a step.//// - Deletions are not observable from a single walk; a caller detects them by// diffing two walks (see [Walker.CollectPrefix] and [DiffCollections]).//// # Transient failures//// Walking a large repo is hundreds of sequential getBlocks calls, so a single// rate limit or restarting host must not end it: [XRPCBlockFetcher] and// [FetchVerifiedHead] retry 429s, 5xx and dropped connections with a jittered// exponential backoff ([RetryPolicy]). Everything else -- 4xx, verification// failures, a cancelled context -- fails immediately.//// Guessing at the backoff is the last resort, not the first: a host that// answers 429 or 503 usually says when to come back, and [BackoffHints] is how// that gets read. Install its [BackoffHints.Transport] on the http.Client behind// the xrpc.Client and point [RetryPolicy.Hints] at the same registry; waits then// honor Retry-After and ratelimit-reset instead of a ladder. Without it the// headers are simply lost -- indigo's xrpc client keeps a status code and// discards the response headers.//// One 4xx in particular is worth knowing about: a walk pins a root and then// reads it over many round trips, while the host garbage-collects blocks that// only superseded commits referenced. A repo that commits mid-walk can leave// blocks unfetchable ([ErrMissingBlock], or a host-specific BlockNotFound /// "Could not find cids"). Retrying cannot help; the caller has to re-read the// head and walk the new tree, reusing its [CachedFetcher] so the second pass// only pays for what changed.//// # Resuming//// A [Frontier] is the complete state of an in-progress walk and is JSON// serializable, so it can be persisted and picked up in another process. Pair a// resumed walk with a [CachedFetcher] over a warm [BlockCache] and the already// walked part of the tree costs no network traffic at all.package reposync