In this paper we present a generic -CRDT framework for arbitrary JSON data called the Document Chain. In contrast to similar approaches based on explicit update operations, the proposed solution is able to automatically determine changesets for nested data structures. Data can be stored on diferent backends, and replication can be performed without locking and with non-destructive conflict resolution. The Document Chain is meant to support the development of collaborative applications by exploiting existing communication and storage solutions, such as shared folders or file sharing platforms in the cloud. An evaluation of the performance in terms of storage overhead, replication cost and computation time indicates that the proposed framework compares favorably with other solutions, and is therefore suitable for implementing collaboration features into existing applications.
Many collaborative applications enable users to concurrently create and modify content on the web. Some applications provide real-time collaboration and continuous synchronization of the users’ activity within a live environment, where each user sees changes made by other users. An alternative approach employs asynchronous replication, which allows for implementing ofline-first (or local-first) solutions that can operate even without network connectivity. In order to replicate updates made while ofline, when the system is online the application will connect to a server or to another instance, submit updates made to its local replica and possibly retrieve remote changes made on other replicas. The synchronization process itself would normally be performed in a synchronous manner: both the local system and the remote one need to be online at the same time. Furthermore, the synchronization logic must deal with conflicts that arise when the same data is concurrently modified by diferent users while ofline: in this regard, applications not only need to store all the updates and changes made by the user, but must also implement algorithms to safely integrate third-party changes into the data model.
An interesting approach to this problem is provided by conflict-free replicated data types
(CRDTs) [
In [
In this paper we present an approach based on deltas called Document Chain, which can be used on JSON documents: delta updates are determined by comparing full states, and are subsequently grouped into blocks which are linked together as a chain. The chain structure keeps changes ordered and ensures consistency. Document Chains are useful as an alternative to state-based CRDTs for arbitrary JSON documents because they reduce the storage requirements for each update while allowing arbitrarily complex documents to be synchronized. As with any CRDT, users can update a Document Chain independently, without the need for locks or any explicit conflict management mechanism. Document Chains follow an eventual consistency model: each sequence of blocks can be used to reconstruct a specific version of the document. Conflicts are dealt with in a non destructive manner by keeping all versions inside the Document Chain and by electing a winning version using a deterministic algorithm. Document Chains can be stored on a filesystem, on a cloud storage, inside a database or just kept in memory: changes can be merged irrespective of the underlying storage technology.
This works improves and extends the one presented in [
The implementation of the Document Chain comprises two key elements: a suitable CRDT data model and a high-level API for accessing the document chain and enabling the use of diferent types of storage backends. In this section both elements will be presented and discussed.
At the lowest level the CRDT employed in our solution improves on the work presented in
[
The framework implements a two-step diference detection algorithm to determine the
changes between the input data (an arbirary JSON document) and the latest available state of
the CRDT. In the first step (called flattening [
Objects extracted during the flattening procedure are stored within pack files: each object is uniquely identified by the hash value of its contents to avoid duplicates. To eficiently enumerate the objects contained in a pack file and retrieve their content, a corresponding index file is also generated. The index maps the hash value of an object to a position inside the pack file. Pack files and the corresponding indices share the same stem (the name of the file without the extension), which is generated by hashing the contents of the pack file. For redundancy purposes, pack ifles can also be parsed as collections of JSON documents (since they represents a JSON array), therefore the corresponding indices can be recovered if necessary. Indices also provide an advantage in a distributed environment, since they are smaller in size than the corresponding packs, can be cached locally (since they are immutable) and allow for determining the available content without the need for downloading the data packs.
Revision update records store a log of all changes made to a particular object: more specifically, they record a transition between the previous and the next revision of one or more objects. Since revision strings contain the hash value of the contents of an object, it is trivial to recover the actual data by fetching the corresponding pack file. Records are grouped inside blocks, which correspond to a specific commit point made to the application data. Blocks also store the identifier of all related pack files created for the same commit point, and optional metadata such as the author and date of the update or digital signatures to prove the authenticity of the block. Blocks are identified by a key obtained by computing the hash value of their content. To keep track of dependencies between subsequent commit points and determine the order in which blocks need to be processed, each block also stores references to one or more previous blocks (referred to as anchors). If concurrent edits happen, multiple blocks might reference the same anchors: this situation won’t afect the consistency of the chain, because conflicts are dealt with by a deterministic algorithm.
The history of all changes made to the application’s own JSON document, as recognized by
the library, is stored as a collection of linked revision update blocks and data packs called
Document Chain (as shown in Figure 2). To obtain the latest version of the client’s data, the
changes recorded in all update record blocks are replayed and data packs are read to source the
required revisions for each object. The unflattening procedure [
Figure 1 illustrates the data structures used inside a Document Chain (data packs, indices and revision update record blocks). It should be noted that those structures can reside on diferent kinds of storage, such as the local filesystems, shared folders in a company’s intranet, databases or cloud platforms, and can be updated independently by each participant without locking.
The Document Chain supports lock free concurrent modifications as long as the backend storage (which will be discussed in the forthcoming section) allows for concurrent appending of new data. The replication process can also be performed without any locking mechanism: chains can be replicated by simply merging two or more collections of blocks, packs and indices together. For example, if blocks and packs are stored as files inside a directory, replication to a target chain is achieved by simply copying files between the two locations. Because files are named after the hash value of their content, files that already exist in the target directory can be ignored. At any time, the integrity of the chain can be verified: thanks to hash references inside blocks it is possible to determine wheter the chain is complete or not, and identify the missing or corrupted blocks or packs. If digital signatures are employed, the authenticity of the data can also be verified.
The functionalities of the underlying CRDT are exposed through a high-level API which implements methods to read and update data, navigate the underlying Document Chain (to retrieve previous versions, or states), fork new chain or merge the current state into another chain. In order to provide a flexible way of storing data on diferent backends, the low-level task of reading or writing the elements of the chain is fulfilled by pluggable adapters, which can interface with several backends. We are currently experimenting with a filesystem adapter (which stores blocks and packs as files), adapters for cloud sharing services (such as Dropbox and Nextcloud), a database adapter (for storing data inside relational databases such as MariaDB or SQLite), and an in-memory adapter.
Using the Document Chain a single-user application can be seamlessly converted into a collaborative application by implementing some additional operations to serialize and deserialize the existing data model into a JSON document. As shown in Figure 3, it is possible to employ diferent Document Chains (in the example, a shared one and local ones) to exchange modifications made by diferent users. The serialized data from the model is compared against the local chain in order to determine the changeset which is subsequently committed to the local chain. The push changes operation merges changes from the local Document Chain into the shared one, whereas the pull changes operation merges changes from the shared chain into the local one. Finally, the local chain can be read and deserialized in order to obtain an updated model.
As replication does not enforce any specific communication channel, a particularly costefective way to exchange updates between multiple clients/participants is through cloud-based ifle sharing platforms. As discussed in the introduction, the use of such infrastructure can reduce the overall maintenance costs for the developer while ensuring that data is stored according to the end-user requirements. Since Document Chains are based on immutable elements (which are identified by the hash value of their contents) it is easy to implement a caching mechanism to reduce network trafic in remote replication.
To evaluate the Document Chain solution we present an experiment derived from [
Listing 1: Sample JSON document V1
The evaluation is comprised of 1000 steps, each comprising several edits to the data structure. More specifically, document version V N is modified to produce a new version (denoted as V N+1) by performing the following changes: first, a new object is added to the transactions array, and second, the value of the currency field of two existing objects is replaced with new data (specifically with the ”EUR” or ”USD” string). Moreover the value of the field txcount is updated to reflect the size (number of elements) of the transactions array. With automerge, new versions of the document are generated by passing the required update operations to the change method (since it is an operation-based CRDT): each changeset in then saved to a separate file; on the contrary, with the Document Chain the new version of the whole document is processed by the update logic, which will automatically devise the corresponding changeset. Moreover, each step entails a commit of the chain, which relies on the filesystem adapter to produce three files: a revision update record block, a data pack and the corresponding index. To evaluate the impact of the hashing function used to generate revision strings and block/pack names inside the chain, we consider both SHA256 (with a 256 bit digest) and xxHash (with a 64 bit digest). To keep the evaluation scenario as simple as possible, digital signatures are omitted. All tests are performed on an AMD PhenomTM II X4 965 processor with 16 GiB of RAM running Ubuntu 20.10. For automerge, version 0.14.2 running on Node.js version 12.18.2 is used.
The first measurement concerns the overhead due to the additional information required for maintaining a history of all updates made to the data structure. Concerning the Document Chain we consider the total size of the data, which comprises pack files, the corresponding indices and the revision update blocks; for automerge we compute the cumulative size of all changesets obtained using the getChanges method (which returns an array of operations to be applied to version VN in order to obtain VN+1).
As shown in Figure 4 the Document Chain approach results in an overhead comparable to automerge, nonetheless depending on the hashing algorithm used for generating revision strings, a slight diference is observable. It should be noted that automerge records changes made to single fields whereas the Document Chain stores full JSON objects for each revision: the former might therefore produce better results for small changes in large objects, whereas the latter ensures the inner consistency of each object. The size of the input document is reported as Full state: since both CRDTs record and enable access to the whole history of the document, we report both the size of a single version of the full state as well as the cumulative size including all previous states. In this regard, both CRDTs allow for maintaining the full history of a document with considerably less storage overhead.
Changesets group a series of updates that need to be applied to version VN in order to obtain version VN+1. In a distributed scenario the size of a changeset determines the amount of data that needs to be exchanged between participants in order to update their current state. As can be observed in Figure 5, both CRDTs provide an eficient way of replicating changes, with a resulting cost which is orders of magnitude less than transmitting the full state at each update.
Manipulating large JSON data structures can be expensive in terms of memory, in particular on resource constrained devices. Accordingly we measure the maximum resident set size (RSS) during each experiment to evaluate the memory used by the CRDTs while reconstructing the full state based on the changesets available at each step. For the Document Chain, measurements have been obtained using the time command, whereas for automerge we employ the built-in process.memoryUsage().rss. As shown in Figure 6, automerge requires more memory than the Document Chain. This diference can be explained by the fact that all changesets produced and replayed by automerge need to be loaded in memory (those also contain the edited values), whereas the Document Chain keeps data inside packs which remain solely on disk until they are needed during the reconstruction process. Furthermore, automerge is a Javascript library which depends on the garbage collector of Node.js, whereas the Document Chain is a native library written in C/C++ which performs manual memory management.
Reconstructing the full state requires replaying all changesets. For the Document Chain, we evaluate the time required by this operation using the time command, whereas for automerge we employ Date.now() to obtain the time before and after the process (therefore the initialization time of the Node.js runtime is ignored). As shown in Figure 7, automerge takes considerably more time compared to Document Chain (either using the SHA256 algorithm or xxHash). In this regard, an important contributing factor is that with the former all changesets need to be loaded and replayed, whereas with the latter only revision update record blocks and indices need to be fully processed, as only the relevant packs (those that contain referenced objects) need to be subsequently read.
In this paper, we presented the concept of Document Chain, which implements a -CRDT
framework for arbitrary JSON data. The proposed solution supports the development of
collaborative applications by exploiting existing communication and storage solutions, such
as shared folders or cloud services. The chain can be replicated and independently modified
by multiple users: the replication process is eficient and ensures non-destructive conflict
management. Moreover, since the full history of all the changes made to the document is
recorded into the chain, it is possible to retrieve previous versions with ease. The Document
Chain compares favorably with similar CRDTs, such as automerge, while ofering a simpler
interface which does not require explicit updates to the document to determine state changes.
Future work includes the integration of an adapter for the SOLID infrastructure [
This work has been financially supported by the Swiss Innovation Agency, Project nr. 42832.1 IP-ICT and by Banana.ch SA.