Skip to content

Latest commit

 

History

History
104 lines (71 loc) · 5.63 KB

store_sync_prolly_tree_rfc.md

File metadata and controls

104 lines (71 loc) · 5.63 KB

Sync store is a protocol that enables a nodes to synchronize itself with messages that it may have missed due to any reason, from one of its peers. This is an efficient method for the nodes present in the network to stay synchronized while sharing minimal information with each other.

Abstract

This specification explains the Sync store protocol and how it is used to synchronize the nodes in the network. It also explains the various components of the protocol and how they interact with each other. The detailed explanation of the protocol is given in the research doc.

Motivation

Nodes who want to synchronize with each other should be able to do so with minimal amount of communication and bandwidth usage. Node that wants to Sync sends a request to the peer node and peer node send the response to the request node. Resulting will be a list values (message_hashes) that the requesting node needs to sync with the peer node. These hashes can be used by other parts of the Store to make sure the related full messages are wired to the requesting node and stored in the Store, making the requesting node fully synchronized with the peer node.

Protobuf

syntax = "proto3";

package prollytree;

message Node {
    string data = 1;              // The data stored in the node
    int64 timestamp = 2;          // Timestamp or other unique identifier
    string node_hash = 3;         // Hash of the node
    int32 level = 4;              // Level of the node in the tree
    string merkel_hash = 5;       // Merkel hash of the node
    bool is_tail = 6;             // Flag indicating if it's a tail node

    // Relationships (IDs or indices of related nodes)
    // Note: Relationships like left, right, up, and down are typically represented using references
    // (like indices or IDs) rather than directly embedding the objects to avoid deep nesting.
    // In our case we can use the key of the node itself and figure out the level based on the current node level.
    int32 left = 7;               // Reference to the left node
    int32 right = 8;              // Reference to the right node
    int32 up = 9;                 // Reference to the parent node
    int32 down = 10;              // Reference to the child node
}

// Request message for GetRoot RPC. No fields needed for this example.
message GetRootRequest {
}

// Response message for GetRoot RPC
message GetRootResponse {
    Node root = 1;  // The root node of the ProllyTree
    // Add additional fields if necessary, e.g., a status message or an error code.
}

// Request message for GetIntermediateNode to resolve the reference indices as mentioned above
message GetIntermediateNodeRequest {
    int32 node_id = 1;  // ID of the node to fetch
    int32 level = 2;    // Level of the node, if necessary for retrieval
}

// Response message for GetIntermediateNode
message GetIntermediateNodeResponse {
    Node node = 1;  // The requested node
}


// Request message for GetRootAtHeight RPC
message GetRootAtHeightRequest {
    int32 height = 1;  // The desired height
}

// Request message for non boundary nodes
message GetNonBoundaryNodesRequest {
    repeated Node start_nodes = 1;  // Nodes from which to start searching
}

// Response message for GetNonBoundaryNodes RPC
message GetNonBoundaryNodesResponse {
    repeated Node non_boundary_nodes = 1;  // Non-boundary nodes found
}

GetRootRequest

This message is sent by the node that wants to sync with the peer node. It contains no fields. The peer node if using the Sync store protocol will respond with the GetRootResponse message. It sends the root node of the tree to the requesting node.

GetRootResponse

This message is sent by the peer node in response to the GetRootRequest message. It contains the root node of the tree. The requesting node can then use this node to traverse the tree and find the nodes that it needs to sync with the peer node.

GetRootAtHeightRequest

This message is sent by the node that wants to sync with the peer node. It contains the height of the tree that the requesting node wants to sync with the peer node. The peer node if using the Sync store protocol will respond with the GetRootResponse message. It sends the root node of the tree to the requesting node.

GetIntermediateNodeRequest

This message is sent by the node that wants to sync with the peer node. It contains the node id/key and the level of the Prolly tree, uisng this information peer node searches and in response send back the subjected node. The peer node if using the Sync store protocol will respond with the GetIntermediateNodeResponse message. It sends the node of the tree to the requesting node.

GetIntermediateNodeResponse

This message is sent by the peer node in response to the GetIntermediateNodeRequest message. It contains an intermediate node of the tree. The requesting node can then use this node to traverse the tree and find the missing nodes.

GetNonBoundaryNodesRequest

This message is sent by the node that wants to sync with the peer node. It contains the start nodes from which the peer node will start searching for the non boundary nodes. The peer node if using the Sync store protocol will respond with the GetNonBoundaryNodesResponse message. It sends the non boundary nodes of the tree to the requesting node.

GetNonBoundaryNodesResponse

This message is sent by the peer node in response to the GetNonBoundaryNodesRequest message. It contains the non boundary nodes of the tree. The requesting node can then use this nodes to traverse the tree and find the missing nodes.

Copyright

Copyright and related rights waived via CC0.