In this paper, we present libJoTS, a C/C++ library that provides asynchronous o ine replication of arbitrary JSON data with a minimal footprint. The primary use case for this library is to easily replicate changes made to a JSON le by di erent users. The replication process is based on multi-version concurrency control (MVCC) to ensure non-destructive con ict management, but in contrast to other popular databases, libJoTS has no runtime dependencies, supports hierarchical documents with nested objects, and stores all synchronizable data into a le. The library is self-contained, and provides a simple API for C/C++ programs as well as bindings for other languages, such as Java and Python. As such it can be easily linked into any application, allowing end-users to replicate changes to data asynchronously and ofine. By using les, data sharing between users does not depend on any speci c technology, and can be achieved either with an online le-sharing service or o ine, thus ensuring full control on data privacy.
Nowadays, many popular applications that once ran natively (o ine) on
personal computers are being pushed to the cloud. At user level, one of the most
signi cant improvements brought by cloud applications is the ability to easily
share data with other people and to work online in a collaborative fashion. In this
regard, replication protocols [1{3] are the cornerstone of those multi-user
applications, allowing updates made to each replica to be consistently merged together.
Replication can be either synchronous or asynchronous. With synchronous
replication, often simply referred to as synchronization, there is a continuous ow
of information that propagates changes to all replicas: as soon as new data is
being created or updated, data is (atomically) replicated to all remote copies.
With asynchronous replication, changes are not propagated in realtime, and
the system might even tolerate temporary divergence between replicas. While
the synchronous approach ensures that each replica always contains the same
data, the overall performance and availability is a ected by network availability,
reliability and speed. Concerning cloud applications, developers are currently
advised to develop software that is able to work even when there is no
connectivity: in this context asynchronous replication mechanisms play an important
role in allowing users to work on local data, while enabling synchronization with
a remote server when online. Beside technical aspects, sharing data on the cloud
and storing potentially sensitive data on someone else's computer, introduce
privacy, security and legal concerns [
Data replication and synchronization technologies are the cornerstone of
distributed storage systems and cloud-based content editing applications (for
example Google Docs™). Although there exist di erent algorithms and protocols
to keep data synchronized [
With libJoTS we aim at supporting the development of distributed applications that rely on synchronized data without the need for a dedicated server or a speci c cloud platform, by enabling information sharing regardless of the type of communication channel (for example, shared folder, e-mail or portable storage). Each user is in control of the data and can decide when to share its own version or merge changes from other users. In the following two use cases are presented. 3.1
We consider a desktop or mobile application that lets users edit documents o ine on their device and later share their work with other people. User A produces the rst version of document X; this version is sent to users B and C through a cloud-based le sharing service. Both user A, B and C make their changes to the document. Subsequently, user B sends its own updated version to User A by email, who can then merge the changes made by B in its copy. At the same time https://www.couchbase.com https://pouchdb.com https://tools.ietf.org/html/rfc6902 user C sends its own version to B by email. User B integrates the changes made by C, merges incoming updates from A and then forwards its nal version of the document to C (Figure 1). Users can perform arbitrary editing and replication, and the process can be scaled to an even larger group of users. Moreover, each user can store copies of synchronizable les for archival or backup purposes: those le can be later processed by the library in order to restore data in the application's own format or to peform synchronization. A common problem in distributed systems is con guration management. Conguration updates need to be replicated from a central server to a multitude of nodes. By means of synchronizable JSON les, libJoTS can be used to create mergeable con guration updates: because con ict handling is non-destructive, local changes are preserved while updates to global settings can be seamlessly integrated. Con guration updates can also be stored on disk to be merged later, and the authenticity of an update can be veri ed by means digital signatures. 4
libJoTS Data Model The data model used by libJoTS is based on JSON documents. Similar to CouchDB the basic unit of replication is a JSON object: the replication algorithm compares two collections of JSON objects and determines the ones missing on each collection. Whereas, CouchDB and other document-oriented databases (like PouchDB) require the application to organize its data into separate JSON objects, libJoTS accepts either a collection of separate objects or an arbitrary JSON document (with a nested hierarchy of objects), and can seamlessly replicate their changes. Therefore, from an application's point of view, if JSON is already employed as a data interchange format, little to no change is required to make use of the synchronization capabilities of the library. The proposed approach for dealing with hierarchical JSON documents is to automatically transform an arbitrary input (for example, Listing 1.1) into a collection of objects which can be synchronized independently. {" data ":{" transactions ":[ {" _id ":"391...32 c" ," currency ":" CHF " ," value ":22412 ," from ":"13465 -45566" , " to ":"34655 -67554"}]} ," info ":{" txcount ":1}}
The output of such a data transformation (Listing 1.2) is a attened collection where array of objects from the input document have been replaced by a string reference, and their contents have been promoted to rst-level objects. Optionally, nested objects can be promoted too. [{" _id ":"391...32 c" ," currency ":"! CHF " ," from ":"!13465 -45566" ," to ":"!34655 -67554" ," value ":22412} ,{" _id ":" @123 ...8 b1 -u" ,"s ":["391473 a1 - bb89 -4 dbf - af93 -7 a8cc1ebc32c "]} ,{" _id ":" root " ," data ":{" transactions ":" @123 ...8 b1 "} ," info ":{" txcount ":1}}]
We call this procedure attening : each promoted object is associated with a
unique identi er, which can be either created using rules speci ed by the user
or automatically generated by the library using a hash algorithm such as
SHA256 [
4.1
A Synchronizable JSON le contains a attened collection of JSON objects along with versioning information. Similar to MultiVersion Concurrency Control (MVCC), concurrent updates and replication never overwrite existing data, but https://cyan4973.github.io/xxHash https://blake2.net simply create a new revision for the concerned objects. The revision string is computed by hashing the contents of the object. All revisions but the rst one have an ancestor : for each object, we maintain the history of revisions (also known as the revision tree), which is stored inside the Synchronizable JSON ). By consulting the revision tree it is possible to determine the order of each update and thus the most recent revision (known as the winning revision), which coincides with the tip of the longest branch of the tree. The Synchronizable JSON data corresponding to Listing 1.1 is shown in Listing 1.3. The value associated with the key d (for documents ) is a dictionary of all objects' identi ers and the corresponding revision trees, whereas the value corresponding to o (for objects) is a dictionary with the contents of each revisions. Finally, the r key points to the identi er of the root element (which is needed to reconstruct the original JSON document).
The replication algorithm implemented in libJoTS merges all changes found
in a source document into a target document. Given two collections of versioned
documents C1 and C2, the replication of C1 to C2 will copy all the documents
and revisions of C1 that are missing in C2. At the same time, the revision tree
for each document will be updated accordingly. If more than one revision shares
the same ancestor a con ict will arise: in that case, a deterministic algorithm
will choose the winning revision based on the longest revision branch and
lexicographical comparison. This algorithm achieves replica convergence and eventual
consistency using MVCC, as in [
{" data ":{" transactions ":[ {" _id ":"391...32 c" ," currency ":" USD " ," value ":22412 ," from ":"13465 -45566" , " to ":"34655 -67554"}]} ," info ":{" txcount ":1}}
As an example of the whole replication process, consider the two updated documents in Listings 1.4 and 1.5. Both have been produced starting from version 1: in version 2a, the value associated with key currency has been changed from CHF to EUR, in version 2b the value has been changed to USD.
The corresponding synchronizable documents can be merged together to produce a new version (Listing 1.6). Both the data contained in version 2a and in version 2b are present in the resulting document, and the revision tree for 391...32c contains a reference to both revisions. The deterministic con ict resolution algorithm will choose either one of the revisions as winner (in this example, the result corresponds to Listing 1.5). {" d ":{ "391...32 c ":[" d29 ... d0b " ,["151...4 cf_d295e90 " ,"8 be ...7 cb_d295e90 "]] , " @123 ...8 b1 -u ":["3 fc ... e82 "] , " root ":[" cc6 ...5 d6 "]} , "o ":{ "151...4 cf ":{" currency ":"! EUR " ," from ":"!13465 -45566" ," to ":"!34655 -67554" , " value ":22412} ,
Because each revision is kept inside the Synchronizable JSON le, the more the data is updated, the bigger the size of the le becomes. This problem can be mitigated by enabling the built-in compression of the Synchronizable JSON le. To further limit this growth, we make use of pruning to delete the value associated with old revisions. More speci cally, the pruning operation removes stale (i.e. non-winning) branches in each revision tree and deletes unreferenced revision objects. The client application can select the depth of the pruning operation in order to maintain an historical record of previous data values (for example, to provide an undo functionality). 5
API To support the basic operations related to Synchronizable JSON les, the public API provides four core functions : { sync json update updates or creates a Synchronizable JSON document from an arbitrary JSON object (in the application's own format). Since the library is stateless, the Synchronizable JSON object must be stored (i.e. saved to a le) by the application itself. { sync json read reads a Synchronizable JSON document and converts it back into an application-compatible JSON document. { sync json replicate replicates changes from a source Synchronizable JSON document to a target one. { sync json prune removes historical information (i.e. old revisions) from a
Synchronizable JSON document. 5.1
To better understand how the library is meant to be used by an application, in the following we present the expected work ow covering both the creation of Synchronizable JSON documents and o ine replication of changes.
chronizable JSON document, the application needs to provide the input JSON le to the sync json update. The output document contains all synchronization information required for subsequent replications and can be shared with other
users. In order to update a Synchronizable JSON it is necessary to provide a Synchronizable JSON to the sync json update function, along with the updated JSON data. In a distributed scenario several Synchronizable JSON documents can be updated in parallel, independently from each other, without loosing the ability to later replicate their changes. In this regard, each document represents a di erent branch in the version tree.
verted back to the application's own format using the sync json read function. By means of additional procedures provided by the library, speci c revisions of the data can also be obtained.
Replicating a Synchronizable JSON le Using the sync json replicate function it is possible to replicate changes made to a source Syncronizable JSON le into a target le: we refer to this process as o ine replication. Because each element of the document is versioned, the replication process does not lose any data (non-destructive con ict management). The user can also query for the di erences between the new and the old version, as well as con icting data. 5.2
Provided that both the source and the target peers are online at the same time (or are able to directly communicate), it is possible to optimize the replication process by sending only bits of modi ed data. Although not directly implemented by the library, two approaches are proposed: a di /patch mechanism, and an interactive replication protocol.
JSON Patch approach The JSON Patch solution requires a RFC6902 compliant di and patch tool to produce a sequence of operations to apply to a target JSON le (at version VM) in order to update its structure to be equal to a source version VN. As mentioned previously, patching the application's JSON does not provide a robust solution to the replication problem, since data might be inadvertently overwritten or corrupted due to con icting modi cations; therefore we consider generating patches against Synchronizable JSON les in order to maintain the full revision history. The target peer needs to communicate its version VM of the data to the source peer. The source peer then employs a JSON di function to produce a patch needed to update VM to VN. Unfortunately, such an approach makes synchronization di cult (if not impossible) in a multimaster scenario, where multiple versions of a document with di erent replication histories arise from concurrent o ine synchronizations made by di erent users: in this situation patches might not apply cleanly leading to data corruption.
Interactive replication protocol If both the source and the target peers are online, a more e cient replication can be implemented through an interactive protocol.The source peer sends an o er message to the target, containing a list of document identi ers and their associated winning revision. The target replies with an array of identi ers of documents that are either unknown or whose latest revision is older than the one proposed by the source. Finally, the source provides a Synchronizable JSON document with just the missing information. Compared to the JSON Patch solution, an interactive replication protocol generates more tra c but does not require the source peer to keep all previous versions of a document. Moreover, it can replicate changes between di erent branches (i.e. Synchronizable JSON documents that have a di erent revision history). The library also provides methods to migrate data to and from CouchDB-compatible servers, hence replication through another database is also possible. 6
We evaluate the performance of our library by considering a stepwise editing work ow of a JSON document. The evaluation process begins with version V1 of a simple JSON document containing an array of objects (Listing 1.1). We subsequently create a new version by performing some changes to the data. More speci cally, version VN is modi ed to produce version VN+1 as follows: a new object is added to the transaction array, and the contents of an existing object (except the id eld) are replaced with new data. Moreover the value of the eld txcount is updated to re ect the size (number of elements) of the transaction array. At each step, version VN of the Synchronizable JSON and version VN+1 of the application JSON are processed by the sync json update function to produce version VN+1 of the Synchronizable JSON. The resulting document is pruned to remove all but the latest revision of the internal data. The last version of the Synchronizable JSON is subsequently replicated on the secondlast version using sync json replicate, and the replication result is converted back to the application's own format using sync json read. The execution of all operations is pro led in order to measure the required time, the maximum amount of main memory used during the process (maximum RSS), and the resulting le size (for both the Synchronizable JSON and the application JSON). The library was con gured to use the SHA-256 hashing algorithm for generating revision hashes and compression was disabled (unless otherwise speci ed). All tests were repeated 10 times on a 64-bit Ubuntu Linux machine with an Intel© Core™ i7-6500U CPU running at 2.50GHz with 16GB or memory. The library was compiled with gcc version 9.2.1: the actual size of the library is less than 900 KB, with dependencies only against the standard library and the pthreads library. For comparison, a minimal install of CouchDB 2.3.1 takes about 40 MB, whereas version 7.1.1 of PouchDB (without JS runtime) is 123 KB.
6.1
As shown in Figure 2, the time required to process JSON data using the library grows linearly with respect to the size of the le. In this regard, we note that the size of the nal version of the le (containing a total of 1000 sub-objects) is about 133 KB, and that the total includes also the time spent loading the le from disk. As expected, reading Synchronizable JSON back into the application's own format is the least expensive operation, whereas updating or replicating data takes almost the same time. The growth in each graph is marked by a series of steps due to the allocation of memory for the internal structures of the library.
Additional testing allowed us to assess the scalability of the replication
algorithm with respect to the input le size: on the same hardware, generating a
Synchronizable JSON document from a 65.5 MB le with 335,389 sub-objects
requires about 18 seconds (with the attening process taking about 80% of the
time), and produces a 110 MB output le. Merging two Synchronizable JSON
les of such a size (where one le contains 479 updated objects with respect
to the other) takes about 12 seconds, while converting the result back to the
application's un attened format requires about 10 seconds. With large les the
total cost is clearly dominated by parsing the input JSON, which is a known
problem when dealing with this format [
Concerning memory allocation, Figure 3 illustrates the memory required for updating, reading and replicating data using the library. In each case the growth follows the increase in the size of the input document. Replication requires the largest amount of memory, since data from both input les need to be stored at the same time; as expected, reading takes the least memory amount. Unfortunately JSON parsing is memory intensive, and very high requirements are to be expected when dealing with large les: with the previously mentionend 110 MB Synchronizable JSON les, replication requires almost 3 GB of memory.
Figure 4 takes into consideration the cost for o ine synchronization, by
comparing the le size of both the original JSON le (application JSON) and
Synchronizable JSON. The graph also shows the di erence between two hashing
algorithms (SHA-256 and xxHash) which can be used to generate object and
revision identi ers. Even though pruning was used to limit the amount of historical
information kept with the le, Synchronizable JSON clearly takes more space
on disk compared to application JSON, because of the additional information
required to support o ine replication (namely, revision trees). It is interesting
to note that xxHash allows for more compact synchronizable les compared to
SHA-256, because it generates 64 bit hashes instead of 256 bit ones. If
Synchronizable JSON les are not meant to be processed outside the library, built-in
compression (based on the de ate [
In order to asses the bene t of online replication (either using the di /patch approach or the interactive replication protocol ) we repeated the experiment discussed in the previous section assuming that new versions are generated on a source peer while measuring the amount of data that needs to be sent to a target peer in order to keep both replicas synchronized.
Fig. 5. Amount of exchanged data vs replication approach.
As shown in Figure 5, exchanging the full synchronizable JSON le consumes more bandwith than online protocols; the tra c generated using the RFC6902 approach is also signi cantly lower than the interactive protocol, because only a small amount of information needs to be sent to the target. However, such an approach would not work in a multi-master scenario, where multiple branches need to be synchronized. Although not shown in the graph, the resulting tra c is not meaningfully a ected by the hashing algorithm, with xxHash producing the same amount of data as SHA-256. 7
In this paper, we presented libJoTS, a C/C++ library that provides asynchronous o ine replication of arbitrary JSON data. The primary use case is to easily replicate changes asynchronously and independently made to a JSON document by di erent users. The replication process is based on multi-version concurrency control (MVCC) to ensure non-destructive con ict management. The proposed approach draws inspiration from popular document databases with built-in support for replication, but provides a standalone lightweight solution targeting o ine replication of small to moderately sized JSON documents. Synchronizable JSON les can be stored on disk, digitally signed and exchanged with any type of communication technology in order to be later merged on a remote system. The API focuses on an o ine- rst approach, allowing for exchanging synchronizable les using any technology, but also enables online replication using a simple protocol. The library, which we plan to release in the forthcoming months, is self-contained and can be easily integrated into any desktop or mobile application. Future work will focus on implementing an on-disk storage back-end to reduce memory usage (at the expense of processing time), and abstractions to ease integration with cloud based le sharing platforms.