Document storage in my clojure document database

With core storage implemented, document storage becomes the trivial matter of a few pure functions

What is a document

A document in this database is going to be anything that can be deserialized into a clojure object (so binary edn). This includes

Maps
Vectors/Lists/Etc
Primitives

Often document databases assume some sort of "id" property as part of the document, but in experience this often ends up to be a hindrance as you end up having to implement conventions/etc deep inside the database for managing the id property. Leaving this to clients to figure out, it's much easier to simply associate a document with an id and keep the tracking of that id to the user (they're free to put it on the document however, if the structure supports it).

As part of each document, a version or synctag is kept (a global incremented number) - in the distributed set-up which I never got around to finishing, this would have been generated by the primary node - but regardless, it needs storing with each document.

For indexing, we also need to store a bunch of secondary indexes against each document so we can look them up by other means, without duplicating the data in storage.

By Id
By Synctag (write order)
By Conflicts (in an MVCC set-up)
Document metadata

Therefore, we keep a few built-in prefixes around to determine how these documents are stored

(def synctags-to-docs-prefix "synctags-to-docs-")
(def conflict-prefix "conflict-")
(def document-prefix "doc-")
(def last-synctag-key "last-synctag")
(def docs-to-metadata-prefix "docs-to-metadata-")

Thus, writing is actually the addition of multiple entries to the underlying key-value store. I have a few helper methods for determining whether an entry in the underlying storage is a specific type of key/value pair. Note: I know, these are using reflection and I should be using the built in string methods - I never got around to updating this code :)

(defn is-document-key [^String k]
  (.startsWith k document-prefix))
(defn is-document-key-prefixed-with [prefix entry]
  (.startsWith (entry :k) (str document-prefix prefix)))
(defn is-synctags-to-docs-key [k]
  (.startsWith k synctags-to-docs-prefix))
(defn is-synctag-docs-entry [m]
  (is-synctags-to-docs-key (:k m)))
(defn is-conflict-entry [m]
  (.startsWith (:k m) conflict-prefix))
(defn is-conflict-entry-for [m doc-id]
  (.startsWith (:k m) (str conflict-prefix doc-id)))

Storing a document is just a repeated application of chnages to the underlying transaction as described in previous entries

(defn store-document
  [db id document metadata]
  (-> db
    (s/store (str document-prefix id) document)
    (s/store (str synctags-to-docs-prefix (:synctag metadata)) id)
    (s/store (str docs-to-metadata-prefix id) metadata)))

Likewise, deletion is a similar story

(defn delete-document
  [session id metadata]
  (-> session
    (s/delete (str document-prefix id))
    (s/store (str synctags-to-docs-prefix (:synctag metadata)) id)
    (s/store (str docs-to-metadata-prefix id) metadata)))

Not that while we delete the actual document and data, we associate this operation with metadata and a version regardless, we we can resolve this appropriately if a conflict arises.

Registration of conflicts is managed externally to all of this, and thus there is also a store-conflict function surfaced.

(defn store-conflict [db id document metadata]
  (s/store db (str conflict-prefix id (:synctag metadata))
          {
            :id id
            :data document
            :metadata metadata }))

Getting all the conflicts from the document storage, is just a matter of opening an appropriate iterator and reading entries until one is not a conflict

(defn conflicts
  ([db] (conflicts db ""))
  ([db prefix]
      (with-open [iter (s/get-iterator db )]
        (s/seek iter (str conflict-prefix prefix))
        (doall (->> (s/as-seq iter)
            (take-while #(is-conflict-entry-for %1 prefix))
            (map :v))))))

This is not lazy, we can see a with-open block and a do-all, I guess if I'd fleshed out the MVCC set-up then the iterator control would have been passed up to a higher layer.

For convenience, the documents also surface some convenience methods for reading through documents from a specific key or order. Unlike conflicts, these take in an iterator and it is assumed that the utiliser will take care of evaluation and the closing of that iterator in the appropriate manner.

(defn iterate-documents-prefixed-with [iter prefix]
  (s/seek iter (str document-prefix prefix))
  (->> (s/as-seq iter)
    (take-while (partial is-document-key-prefixed-with prefix))
    (map (comp edn/read-string :v))) )

(defn iterate-synctags-after [iter synctag]
  (s/seek iter (str synctags-to-docs-prefix (next-synctag synctag)))
  (->> (s/as-seq iter) (take-while is-synctag-docs-entry) (map :v) (distinct)))

That's actually the entire implementation of document storage listed out in this blog entry. Clojure can be very terse at timess due to the data-oriented nature of this code - and in my opinion doesn't lose legibility in this case for that sake.

Note that all functions in this are actually pure, they take in one map, and return a new map with changes applied to it. (Or as pure as they can be, the underlying storage mechnism can do all sorts of weird things with atoms and we wouldn't even know.)

Related Files

documents.clj