schism
A batteries included library of CRDT implementations of Clojure's core data types: Sets, Maps, Vectors, and Lists with support for distributed modification and eventual consistency.
Dependency Information
Latest release: 0.1.0
Leiningen and Boot dependency information:
[com.holychao/schism "0.1.0"]
Motivation
Clojure is one of a handful of languages which can be authored and executed in both a high performance server environment and in a web browser. This strength affords many benefits, one of which the language does not cover is allowing for concurrent modification of data with rich synchronization semantics.
There are some other efforts similar to this. Schism's aims are:
- To minimize the locus of concerns outside of collection data structures.
- To provide collection data structures with inferior performance to Clojure's own persistent data structures, but which only incur sub-linear cost increases, available through the same interfaces.
- To provide collection data structures with greater storage, and serialization costs than Clojure's own persistent data structures, which grow with an upper bound of the number of elements in the collection, independent of the number of operations against that collection.
- Allow for a Clojure and ClojureScript processes executing on separate nodes to maintain convergent data.
Limitations
Because schism refuses to use tombstones, some convergence operations will have different results than structures which will embrace the costs of tombstones.
For example, Schism's set may drop a recently added element during convergence with certain vector clock states. While this quality is undesirable, I accept it more readily than monotonically increasing storage requirements for data explicitly intended for communication between nodes. Future work may pursue allowing for the convergence operation to have some configurability so that vector clocks will retain information more eagerly to reduce the incidence of this phenomena.
Usage
schism.core
contains functions for generating new collections,
e.g. schism.core/convergent-set
. These functions accept arguments
much like their Clojure core equivalents, so (convergent-set :a :b :c)
creates a set equivalent to #{:a :b :c}
These collections support Clojure's collection operations with the same semantic consequences (save for above mentioned performance and storage costs). Any divergence between a schism collection's behavior and a Clojure collection's behavior is a bug. Please file a report, as these should be relatively fast and easy to fix.
String coercion of a schism collection is identical to that of a
Clojure collection, e.g. a convergent set will coerce to a string as
#{:a :b :c}
. However, pr-str
will generate a longer
tagged literal containing all synchronization data for the structure
to operate correctly. Schism eagerly enables edn readers for its
structures, so synchronization can be as simple as sending the results
of pr-str
over the wire, reading on the receiving side and
converging with the receiver's local copy.
Convergence is done with schism.core/converge
. It accepts two
collections, which it assumes are both copies of the same replicated
collection, and returns a single collection: the result of
convergence. Converge replicates the metadata of its first argument
into its return value, if present.
Each CLJ and CLJS process working with any shared schism collection is
a node in a distributed computing cluster. Each node should have an
identity in order for synchronization to operate correctly. You may
invoke schism.core/initialize-node!
with no arguments to initialize
the current process to have a randomly generated UUID as its node
identifier. You may use any serializable value as the node identifier
by passing that value to initialize-node. If you can create stable
node identifiers, that can lead to some minor reduction in the storage
requirements for schism's data structures. If two nodes operate on a
replicated collection independently and do NOT have distinct node
identifiers, schism's convergence behavior is undefined. (Don't do
this). If you do not explicitly invoke initialize-node!
, it is left
at the value nil
.
Further work
- Property based tests
- Configurable convergence
- Other good ideas as the community provides them
Contributing
I don't use CA's or other such things. Bugfixes are welcome and appreciated.
I reserve the right to dismiss feature requests in the guise of PRs.
All work will be evaluated in light of conformance with motivations as stated in this document.
License
Copyright © 2018 Alex Redington
Distributed under the MIT License