Sync Concepts

the realtime end user transactional data generated by your app can be disseminated across devices through three different methods centralized — a small peer device establishes a direct internet enabled connection to the big peer cloud deployment decentralized — a small peer device establishes a mesh network connection with nearby small peer devices using any and all communication transport types available to them by default hybrid — if one or multiple small peer devices connected in the mesh network gain access to the internet, not only do those devices with internet access upload their local ditto store to the big peer cloud, but every nearby offline small peer device as well for instructions on enabling and disabling transport types, see docid\ iic3gevlppflwzt1sbljr video overview syncing with big peer the big peer supports both bidirectional sync and unidirectional data sync before you can establish a peer to peer mesh network and exchange data directly with nearby peers, you must connect to the big peer at least once to set up your communication infrastructure when you connect to the big peer for the first time, you obtain your access credentials and ensure you have the latest data and are up to date with the rest of the peers for more information, see docid\ gulmsvyg3oltps43d4vt any small peer that has access to the internet automatically establishes a connection with the big peer to sync data across the big peer and, by way of multihop data sync, all connected small peers for more information, see docid wxhye kktuvenblaxkf , as follows syncing across peers the multiple replicas that result from a single partition are spread across virtual and relevant physical server nodes; that is, the big peer cloud deployment and local ditto stores of subscribing small peers by default, ditto does not automatically replicate data to peers instead, peers subscribe to changes and, using a live query, indicate the data they're interested in watching for changes once a change is observed somewhere in the mesh, only the delta matching the live query replicates to subscribing peers in simpler terms, sync involves a subscribing peer selectively "pulling" data from other peers, rather than remote peers automatically "pushing" data to it greedy and selfish data sync the big peer and small peer approach data sync in different ways the big peer uses a greedy sync model — automatically subscribing to everything and, when possible, replicating complete document objects across peers small peers use a selfish sync model — replicating only the data that they explicitly query for and that has undergone changes to their local ditto store multihop data replication when all peers connected in the mesh need to share the same view of the data, ditto automatically initiates the flooding replication process to multihop data from one connected peer to another connected peer by way of intermediate “hops” along a given path as illustrated in the following graphic, for multihop to occur , all peers within the chain must observe the same data the benefits of multihop sync technology include the following guarantee a consistent offline first sync of critical data, ensuring data remains consistent even when connectivity is intermittent enhance the overall responsiveness of your app, resulting in faster interactions reduce costs by optimizing data operations since, when feasible, you can read and write data to a nearby peer instead of traversing a very fragile, low‑bandwidth data source flooding the mesh to ensure that all connected peers subscribing to the same query share the same view of the data, ditto automatically initiates flood fill, or flooding for short flooding is a replication process common in distributed systems involving having each peer multihop updates to the peers they are connected to until all peers in the mesh have the data change multihopping to the big peer ditto links if at any time a peer connected in the mesh gains access to the internet, all mesh generated data gets automatically exchanged with the big peer by way of multihop ditto’s multihop big peer connection allows a small peer to have a secure and encrypted connection to the big peer through one or more intermediate peers when a peer establishes a mesh network connection with another peer, it first establishes encrypted internal tls tunnels, or ditto links , that nearby peers use for transmission similar in function to a virtual private network (vpn), ditto links are virtual private connections that utilize the noise protocol to establish secure and protected connections the noise protocol is a cryptographic framework for advanced security protections for more information, see the official documentation at http //noiseprotocol org/ concurrency conflicts a challenge arises in offline scenarios when two or more peers make edits independently and the data values stored by each peer diverge over time referred to as conflict resolution , ditto's process of addressing concurrency conflicts involves a combination of a docid wxhye kktuvenblaxkf and docid wxhye kktuvenblaxkf metadata database each peer individually maintains its own metadata database the metadata database serves as a storage repository of information essential in resolving conflicts that arise during the process of merging concurrent changes within this metadata database is the version vector the version vector manages the following essential details for a particular peer the current state of sync a record of the data previously sent and received the sequence of updates the timestamp of last write operation guiding principles ditto adheres to the following strategies to ensure that all peers ultimately reach the same value for a particular data item deterministic — as part of the strategy of eventual consistency, regardless of the order in which updates from different peers are received and merged, all peers ultimately converge to the same single value predictable and meaningful — instead of arbitrarily resolving conflicting registers to a predefined value, the resulting merge accurately represents the original input and some rational interpretation of that input the following scenario provides a walkthrough of the mechanics of version vectors, their role in determining merging behavior, and how different peers contribute to data sync eventual consistency example scenario the hlc uses the uint128 data type to represent the site id and 64bit timestamp in ditto; however, for simplicity, the following scenario uses basic string and number types instead local peer a document 123abc links to a version vector that indicates its locally stored document is currently at vector version 5 the most recent incoming remote peer b changes were incorporated and merged at version 1 the remote peer c changes were incorporated and merged at vector version 4 documentid "123abc" version vector { "a" 5, "b" 1, "c" 4 } local peer a receives document changes from remote peer b the incoming document's version vector indicates the remote peer b incoming version vector is value 4 the most recent incoming remote peer b changes were of version 1 ; a value less than the incoming document version vector value of 4 since 4 is greater than 1 , the local peer a determines that the changes are new and should be incorporated and merged in order to remain consistent documentid "123abc" version vector { "a" 5, "b" 1, //merge in {"b" 4} because 4 > 1 "c" 4 } hybrid logical clock each document in each peer contains a hidden metadata map of a site id and a hlc the hlc stands for a hybrid logical clock this hlc is used to determine whether a change has "happened before" it might be tempting to use physical clocks to resolve conflicts when attempting to merge concurrent data changes however, it's essential to know that even quartz crystal based physical clocks can skew forward or backward in time almost every device regularly attempts to synchronize with an ntp synchronized clock server but even then, the round trip time from the request to the server's response adds additional variability in addition, there are limitations to nature and physics that will never allow two measurements of physical time to align precisely thus, these conditions led us to determine that physical clocks were not reliable in a distributed mesh network although we decided that we could not build a system that resolved conflicts based purely on physical time, we needed to preserve the notion of physical time so as not to confuse users of collaborative applications however, each peer still needs a deterministic way to resolve conflicts in other words, each peer when sharing crdt deltas needs to always resolve conflicts the same way this requirement still needs logical ordering this requirement led us to implement the version vector with a hybrid logical clock (often referred to as hlc) expand to learn more about hlc in ditto's distributed system, the hlc is a 64 bit timestamp comprised of 48 bits of a physical timestamp and 16 bits of a monotonically increasing logical clock ditto is a distributed system where data changes occur across devices this can be hard to reason about because changes can occur concurrently in mathematics, this is described as a “partial order” meaning that not all the data change events have a “happened before” relationship with each other if you use git, you experience this when you create a branch any changes you make on the branch are related to the prior changes on that branch, but subsequent changes to the main branch are not directly related it is possible to resolve a partial order into a “total order” where all events are related, but this involves then establishing “happened before” relationships across all changes again with git, this occurs when you merge a branch back into the main branch changes are merged into a total order either automatically or with manual resolution in the same way, ditto has the functionality to track a partial order of all data change events that occur across devices and then an automatic mechanism to merge the events into a total order each ditto document includes a version vector the replication system uses the version vector to capture local and observed edits from other peers when a peer incorporates changes from other peers, the local peer can use the incoming remote peer’s version vectors to determine whether the changes are new or old in other words, a peer can distinguish from another peer’s incoming version vectors if the incoming data has “happened before” or not this is called a “logical clock” if every change across devices happened after observing all other changes, a logical clock would be sufficient to track the total order of events however, reality doesn’t work that nicely! events will occur concurrently with each other across devices creating a partial order, so we must rely on something else beyond the logical clock to order concurrent events we choose to rely on the physical timestamp of the change as recorded by the device it occurred on to order concurrent events however, it’s essential to know that even quartz crystal based physical clocks can skew forward or backward in time almost every device regularly attempts to synchronize with an ntp synchronized clock server but even then, the round trip time from the request to the server’s response adds additional variability in addition, there are limitations to nature and physics that will never allow two measurements of physical time to align precisely as a result, while we generally trust physical clocks, we also need to manage inevitable clock skew a version vector utilizes a monotonically increasing counter traditionally, a physical timestamp can’t be used for the counter because it is not guaranteed to be monotonic instead, we use a “hybrid logical clock” (hlc) within the version vector a hlc is a 64 bit timestamp comprised of 48 bits of a physical timestamp and 16 bits of a monotonically increasing logical clock the logical part ensures that it is always monotonically increasing even if the physical clock skews to the past, the next observation will be higher than the last one in addition, timestamps from other devices are incorporated as events are exchanged, ensuring that clocks always move forward the net result is that the clock skew becomes bounded as long as changes from other sites are observed before subsequent changes, we can track the total order independent of the physical timestamp if the changes are concurrent and we have a partial order, then we order the changes based on the hlc value, which is formed in part by the physical timestamp from the device that created the change, creating a total order if a user were to change their device’s clock, hlc guards against going in the past, since it must be monotonic however, moving a device clock forward would allow that change to win over a concurrent change (assuming the other clock is still relatively synchronized) however subsequent changes after observing the skewed clock won’t necessarily be affected because the hlc will “fast forward” by observing the skewed clock, and any new change will get an hlc value ahead of it thus the use of hlc protects clock skew in reverse and also prevents skew into the future from rendering changes that are logically happening later from losing out clock accuracy ditto requires that all devices participating in the mesh have the time and date configured accurately it is recommended to synchronize the clock automatically with an internet time server this feature is built into most platforms including ios and android this will be sufficiently accurate for ditto’s needs if a device has a significantly incorrect clock, outcomes may include failing to connect to a peer because it thinks their certificate isn’t valid yet or has already expired unintuitive conflict resolution in certain situations when concurrently editing documents version vectors each peer has its own version of the documents that multiple peers can work on concurrently they keep track of their respective document changes in a data structure known as a version vector the version vectors that each document links to contain a snapshot of essential metadata, such as the given document's current state, as well as a record of the data previously sent and received incrementing version vectors when a peer directly updates its own locally stored document, the document version vector increments by a value of one determining newness local peers use document version vectors to assess local and observed edits and ensure data consistency accurately before a peer incorporates and merges incoming changes into its document state, the peer compares its existing version vector value with the receiving version vector value to determine whether the incoming changes are new (or old) relative to its current document state if the incoming version vector is a value greater than the existing version vector value, the incoming changes are new and must be incorporated and merged for its document state to remain consistent managing time based operations the version vector pinpoints the chronological order of events and determines the exact timing of the most recent write operation for a specific peer utilizing a combination of temporal timestamp and the hybrid logical clock ( hlc ) the temporal timestamp is a component associated with an individual peer that tracks the chronological order of its local events the hlc is a higher level component that combines both physical time and logical clocks to create a unified timestamp that tracks the chronological order of events for the entire distributed system