dset

A Clojure library designed to provide a distributed converging triple store. You can assert or retract triples into a local copy of a the store, which generates deltas that can be shared with other nodes to keep their copies of the store up to date.

This is useful for structured ephemeral replicated data where eventually consistency is acceptable. For example for a chat system if you don't want to store presence information in a central database.

The triple store is ontop of a AWORSET CRDT

Usage

Lein

[com.manigfeald/dset "1.0.0"]

deps.edn

com.manigfeald/dset {mvn/version "1.0.0"} or com.manigfeald/dset {:git/url "https://github.com/hiredman/dset" :sha "..."}}}

Asserting, Retracting, Querying

Triples are vectors of count 3. The elements of a triple can be anything that is comparable via clojure's compare function.

a triple can be asserted in to the store with assert-triple

(dset/assert-triple store replica-id [1 2 3])

a triple can be retracted with retract-triple

(dset/retract-triple store replica-id [1 2 3])

the store can be queried using query, giving it an example triple, with nils for blanks

(-> store
  (assert-triple replica-id [1 2 3])
  (assert-triple replica-id [1 4 5])
  (assert-triple replica-id [2 4 5])
  (query [1 nil nil]))

;;=> ([1 2 3] [1 4 5])

Converging Distributed Replicas

A rough pattern is:

1. make a triple store on all your replicas
2. wrap the triple store in some clojure reference type
3. make deltas to the triple store in the reference type
4. broadcast the triple store deltas to other replicas
5. when you recieve deltas apply them to your triple store
6. from time to time pick another replica and merge their triple store with yours

eg

;; really you should request a full store from another node at start
;; up and merge it in
(def s (atom (dset/make)))

(future
  (loop []
    (Thread/sleep 1000)
    (if (> 0.05 (rand))
      (swap! s join (request-random-full-from-replica))
      (loop []
        (let [sv @s]
          (if (compare-and-set! s sv (without-delta sv))
            (broadcast-to-replicas (delta sv))
            (recur)))))
    (recur)))

(defn receive-delta [delta]
  (swap! s apply-delta delta))

License

Copyright © 2018 Kevin Downey

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.