README
¶
sync package
Overview
This package implements a client and server that allows for the syncing of a MerkleDB. The servers have an up to date version of the database, and the clients have an out of date version of the database or an empty database.
It's planned that these client and server implementations will eventually be compatible with Firewood.
Messages
There are four message types sent between the client and server:
SyncGetRangeProofRequestRangeProofSyncGetChangeProofRequestSyncGetChangeProofResponse
These message types are defined in avalanchego/proto/sync.proto.
For more information on range proofs and change proofs, see their definitions in avalanchego/merkledb/proof.go.
SyncGetRangeProofRequest
This message is sent from the client to the server to request a range proof for a given key range and root hash. That is, the client says, "Give me the key-value pairs that were in this key range when the database had this root." This request includes a limit on the number of key-value pairs to return, and the size of the response.
RangeProof
This message is sent from the server to the client in response to a SyncGetRangeProofRequest.
It contains the key-value pairs that were in the requested key range when the database had the requested root,
as well as a proof that the key-value pairs are correct.
If a server can't serve the entire requested key range in one response, its response will omit keys from the
end of the range rather than the start.
For example, if a client requests a range proof for range [requested_start, requested_end] but the server
can't fit all the key-value pairs in one response, it'll send a range proof for [requested_start, proof_end] where proof_end < requested_end,
as opposed to sending a range proof for [proof_start, requested_end] where proof_start > requested_start.
SyncGetChangeProofRequest
This message is sent from the client to the server to request a change proof between the given root hashes. That is, the client says, "Give me the key-value pairs that changed between the time the database had this root and that root." This request includes a limit on the number of key-value pairs to return, and the size of the response.
SyncGetChangeProofResponse
This message is sent from the server to the client in response to a SyncGetChangeProofRequest.
If the server had sufficient history to generate a change proof, it contains a change proof that contains
the key-value pairs that changed between the requested roots.
If the server did not have sufficient history to generate a change proof, it contains a range proof that
contains the key-value pairs that were in the database when the database had the latter root.
Like range proofs, if a client requests a change proof for range [requested_start, requested_end] but
the server can't fit all the key-value pairs in one response,
it'll send a change proof for [requested_start, proof_end] where proof_end < requested_end,
as opposed to sending a change proof for [proof_start, requested_end] where proof_start > requested_start.
Algorithm
For each proof it receives, the sync client tracks the root hash of the revision associated with the proof's key-value pairs.
For example, it will store information that says something like, "I have all of the key-value pairs that
are in range [start, end] for the revision with root root_hash" for some keys start and end.
Note that root_hash is the root hash of the revision that the client is trying to sync to, not the
root hash of its own (incomplete) database.
Tracking the revision associated with each downloaded key range, as well as using data in its own
(incomplete) database, allows the client to figure out which key ranges are not up to date and need to be synced.
The hash of the incomplete database on a client is never sent anywhere because it does not represent a root hash of any revision.
When the client is created, it is given the root hash of the revision to sync to. When it starts syncing, it requests from a server a range proof for the entire database. (To indicate that it wants no lower bound on the key range, the client doesn't provide a lower bound in the request. To indicate that it wants no upper bound, the client doesn't provide an upper bound. Thus, to request the entire database, the client omits both the lower and upper bounds in its request.) The server replies with a range proof, which the client verifies. If it's valid, the key-value pairs in the proof are written to the database. If it's not, the client drops the proof and requests the proof from another server.
A range proof sent by a server must return a continuous range of the key-value pairs, but may not
return the full range that was requested.
For example, a client might request all the key-value pairs in [requested_start, requested_end]
but only receive those in range [requested_start, proof_end] where proof_end < requested_end.
There might be too many key-value pairs to include in one message, or the server may be too busy to provide any more in its response.
Unless the database is very small, this means that the range proof the client receives in response to
its range proof request for the entire database will not contain all of the key-value pairs in the database.
If a client requests a range proof for range [requested_start, requested_end] but only receives
a range proof for [requested_start, proof_end] where proof_end < requested_end
it recognizes that it must still fetch all of the keys in [proof_end, requested_end].
It repeatedly requests range proofs for chunks of the remaining key range until it has all of the
key-value pairs in [requested_start, requested_end].
The client may split the remaining key range into chunks and fetch chunks of key-value pairs in parallel, possibly even from different servers.
Additional commits to the database may occur while the client is syncing. The sync client can be notified that the root hash of the database it's trying to sync to has changed. Detecting that the root hash to sync to has changed is done outside this package. For example, if the database is being used to store blockchain state then the sync client would be notified when a new block is accepted because that implies a commit to the database. If this occurs, the key-value pairs the client has learned about via range proofs may no longer be up to date.
We use change proofs as an optimization to correct the out of date key-value pairs.
When the sync client is notified that the root hash to sync to has changed, it requests a change proof
from a server for a given key range.
For example, if a client has the key-value pairs in range [start, end] that were in the database
when it had root_hash, then it will request a change proof that provides all of the key-value changes
in range [start, end] from the database version with root hash root_hash to the database version with root hash new_root_hash.
The client verifies the change proof, and if it's valid, it applies the changes to its database.
If it's not, the client drops the proof and requests the proof from another server.
A server needs to have history in order to serve a change proof.
Namely, it needs to know all of the database changes between two roots.
If the server does not have sufficient history to generate a change proof, it will send a range proof for
the requested range at revision new_root_hash instead.
The client will verify and apply the range proof. (Note that change proofs are just an optimization for bandwidth and speed.
A range proof for a given key range and revision has the same information as a change proof from
old_root_hash to new_root_hash for the key range, assuming the client has the key-value pairs
for the key range at the revision with old_root_hash.)
Change proofs, like range proofs, may not contain all of the key-value pairs in the requested range.
This is OK because as mentioned above, the client tracks the root hash associated with each range of
key-value pairs it has, so it knows which key-value pairs are out of date.
Similar to range proofs, if a client requests the changes in range [requested_start, requested_end],
but the server replies with all of the changes in [requested_start, proof_end] for some proof_end < requested_end,
the client will repeatedly request change proofs until it gets remaining key-value pairs (namely in [proof_end, requested_end]).
Eventually, by repeatedly requesting, receiving, verifying and applying range and change proofs, the client will have all of the key-value pairs in the database. At this point, it's synced.
Diagram
Assuming you have Root Hash r1 which has many keys, some of which are k25, k50, k75,
approximately 25%, 50%, and 75% of the way into the sorted set of keys, respectively,
this diagram shows an example flow from client to server:
sequenceDiagram
box Client/Server
participant Server
participant Client
end
box New Revision Notifier
participant Notifier
end
Note right of Client: Normal sync flow
Notifier->>Client: CurrentRoot(r1)
Client->>Server: RangeProofRequest(r1, all)
Server->>Client: RangeProofResponse(r1, ..k25)
Client->>Server: RangeProofRequest(r1, k25..)
Server->>Client: RangeProofResponse(r1, k25..k75)
Notifier-)Client: NewRootHash(r2)
Client->>Server: ChangeProofRequest(r1, r2, 0..k75)
Server->>Client: ChangeProofResponse(r1, r2, 0..k50)
Client->>Server: ChangeProofRequest(r1, r2, k50..k75)
Server->>Client: ChangeProofResponse(r1, r2, k50..k75)
Note right of Client: client is @r2 through (..k75)
Client->>Server: RangeProofRequest(r2, k75..)
Server->>Client: RangeProofResponse(r2, k75..k100)
TODOs
- Handle errors on proof requests. Currently, any errors that occur server side are not sent back to the client.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( ErrAlreadyStarted = errors.New("cannot start a Manager that has already been started") ErrAlreadyClosed = errors.New("Manager is closed") ErrNoRangeProofClientProvided = errors.New("range proof client is a required field of the sync config") ErrNoChangeProofClientProvided = errors.New("change proof client is a required field of the sync config") ErrNoDatabaseProvided = errors.New("sync database is a required field of the sync config") ErrNoLogProvided = errors.New("log is a required field of the sync config") ErrZeroWorkLimit = errors.New("simultaneous work limit must be greater than 0") ErrFinishedWithUnexpectedRoot = errors.New("finished syncing with an unexpected root") )
var (
ErrMinProofSizeIsTooLarge = errors.New("cannot generate any proof within the requested limit")
)
Functions ¶
This section is empty.
Types ¶
type DB ¶ added in v1.10.4
type DB interface {
merkledb.Clearer
merkledb.MerkleRootGetter
merkledb.ProofGetter
merkledb.ChangeProofer
merkledb.RangeProofer
}
type GetChangeProofHandler ¶ added in v1.11.12
type GetChangeProofHandler struct {
// contains filtered or unexported fields
}
func NewGetChangeProofHandler ¶ added in v1.11.12
func NewGetChangeProofHandler(log logging.Logger, db DB) *GetChangeProofHandler
type GetRangeProofHandler ¶ added in v1.11.12
type GetRangeProofHandler struct {
// contains filtered or unexported fields
}
func NewGetRangeProofHandler ¶ added in v1.11.12
func NewGetRangeProofHandler(log logging.Logger, db DB) *GetRangeProofHandler
type Manager ¶ added in v1.10.4
type Manager struct {
// contains filtered or unexported fields
}
func NewManager ¶ added in v1.10.4
func NewManager(config ManagerConfig, registerer prometheus.Registerer) (*Manager, error)
func (*Manager) Close ¶ added in v1.10.4
func (m *Manager) Close()
Close will stop the syncing process
func (*Manager) UpdateSyncTarget ¶ added in v1.10.4
type ManagerConfig ¶ added in v1.10.4
type ManagerConfig struct {
DB DB
RangeProofClient *p2p.Client
ChangeProofClient *p2p.Client
SimultaneousWorkLimit int
Log logging.Logger
TargetRoot ids.ID
BranchFactor merkledb.BranchFactor
StateSyncNodes []ids.NodeID
// If not specified, [merkledb.DefaultHasher] will be used.
Hasher merkledb.Hasher
}
TODO remove non-config values out of this struct
type SyncMetrics ¶
type SyncMetrics interface {
RequestFailed()
RequestMade()
RequestSucceeded()
}
func NewMetrics ¶
func NewMetrics(namespace string, reg prometheus.Registerer) (SyncMetrics, error)
Source Files
Directories