Synchronizing Entities in Replicated Log-Structured Databases with Disconnected Operation
Original Publication Date: 2003-Jul-24
Included in the Prior Art Database: 2003-Jul-24
In distributed and/or replicated systems, there is often the need for one system to get updated information from others. For this reason, there is a node notation introduced, in which each node has a unique ID of an ID tree. The root node (the first node in the system) has a zero-length name. Whenever an additional node joins, it gets the name of the introducing node as a prefix, followed by a unique symbol which the parent has not yet appended.
Synchronizing Entities in Replicated Log -Structured Databases with Disconnected Operation
In distributed and/or replicated systems, there is often the need for one system to get updated information from others. This is complicated when, e.g., number of nodes is very large, not every node reliably knows all others (e.g., during join/leave situations), some nodes are not always reachable (disconnected operation or network problem), the nodes are connected through an overlay network which may change its topology or contain unreliable nodes.
There are well-known optimal solutions for some of the trivial cases, such when the number of peers is limited (e.g., maintaining a backlog for the unreachable peers), there is only a single node (or small number of nodes) which create(s) new information (e.g., keeping a table with the highest sequence number of a change for each node), or when the number of documents kept at each node is small (e.g., hashes or hash trees).
The present idea provides a new means for distributing and synchronizing information efficiently when the above adverse issues are present. It additionally requires some transport protocol as a means for distribution; practical mechanisms might include epidemic-based rumor spreading or distribution through an overlay network.
The solution is based on the following considerations:
Every piece of information (including every change to this information) is associated with a unique "localized sequence number", consisting of a tuple (nodeID, sequenceNumber). NodeID is the globally unique identifier of the node that created this information. sequenceNumber is a monotonically increasing sequence number in the domain of the nodeID, i.e., each update performed by our node gets assigned the next higher sequence number. Sequence numbers of different nodes have no direct relationship, each node's sequence number indicates the number of updates this node has injected into the database/network. Each node will try to spread any new information (whether locally generated or remotely received) to some other nodes according to the transport mechanism. When two nodes enter into a "relationship" (aka "synchronization connection"), they compare their set of (nodeID, sequenceNo) tuples and request/transfer the information that is missing on either side.
This mechanism does not work well when the set of (nodeID, sequenceNo) tuples is large, as transmitting the information to be exchanged when entering into a relationship is potentially huge.
The key to our solution is to have the node IDs to follow a specific pattern, as follows:
Each node has a unique ID of an ID tree. The root node (the first node in the system) has a zero-length name. Whenever an additional node joins, it gets the name of the introducing node as a prefix, followed by a unique symbol which the parent has not yet
In the simplest case, these symbols are of fixed length, say eight bits, each represented here b...