• rationale
• db structure
• about implementation
• track changes
• materialised views
• lazy views

rationale

one of the biggest challenges when working on the front end is state management. re-frame was one of the first solutions to propose one central app-db, one source of truth. solution works great, but as the application grows, there is a problem with data denormalization and fatigue with multiple nested maps.

the ideal solution seems to be datascript, but there have been several attempts to incorporate it into the re-frame ecosystem, eg. posh and re-posh, and in my humble opinion, despite much desire and hard work, the transplant has failed. datascript seems to be too heavy for the frontend, especially for mobile. also big inconvenience is that datascript is built around its own data types. re-frame has a whole bunch of tools with re-frame-10x that allow you to preview app-db in real time.

doxa is an attempt to create a db that can be treated as a simple hashmap, which makes it possible to use a whole set of Clojure functions on it, from filter to transreducers, but also using transactions similar to datascript, datalog query and pull query.

db structure

db is a simple map with two levels of nesting.

{[?table-id ?entity-id :as ref] {?key ?value}}

example

{[:person/id 1] {:person/id 1 :name "ivan" :age 18 :_friend #{[:person/id 2]}}
 [:person/id 2] {:person/id 2 :name "petr" :age 24 :friend #{[:person/id 1]}}}

reference, is always a two-element vector. table-id must be a keyword where (name ?k) returns id, i.e db/id, people/id, etc. in the case of several keys that satisfy a condition, the behaviour will be unpredictable.

entity-id can by any value, which allows a great flexibility, and importantly is descriptive, e.g [:country/id :andora], [:people/id [:marketing "zbyszek.nowak@gmail.com"]].

references and back references are a own implementation of ordered/set based on flatland/ordered. unfortunately flatland it doesn’t support cljs, so i decided to rewrite it. the use of ordered/set ensures distinct values, while preserving the order of insertion.

about implementation

no special deftype is used, but the implementation is based on protocols, which allows doxa to be used together with any kv store, like redis, firestore or lmdb.

in the standard implementation hashmap is extended, and doxa keeps all the necessary stuff in the map metadata, including index, last transaction, cache etc.

doxa has been optimised to work on relatively small amounts of data and if you mostly query the database using multiple joins, a probably better choice would be to use another db like datascript or asami. test before you choose.

doxa uses one index on table-id. i tested the use of multiple indexes, but such a db exists and is called datascript and asami. creating the same thing a second time, only worse, is pointless. one index affects the datalog query where the search uses simple bruteforce however, all loops are as tight as possible and clojure/script protocols or java interfaces are used directly. for most queries excluding this with multiple joins, doxa is the fastest available db for clojurescript. nevertheless, this single index allows to reduce the amount of data searched, which can speed up queries by an order of magnitude and the overall result is really good.

track changes

due to the db structure, [ref k v] each change in the db can be represented by a datom, e.g [[:db/id 1] :+/:- :name "Ivan" 1646520008503]. :+ and :- means addition and deletion of the key respectively. swapping a value under a key is successively deleting and then adding a new value. theoretical duplication of representation may be needed for more complex queries.

during each transaction the original document is compared with the modified document using ribelo.doxa/-diff-entity and for each difference it produces a DoxaDBChange type as above. such a collection shall be stored in the metadata under key :ribelo.doxa/tx. full transaction history is not stored, only the latest transaction.

materialised q query uses the parsed :where as a key under which the result is stored in the cache. in the case of materialised pull, the entire query is first converted into a sequence of datoms, which takes time.

after each transaction, if a cache exists, each key is matched with the changes made after the transaction. if match, the stored result is deleted from the cache. the comparison is made in the most pessimistic way and there is no possibility of false negatives, false positives are possible. this means that in the worst case the query will recalculate, but there will never be a case that despite changes in the DB you will get an old outdated result.

at the moment it is not possible to use materialised pull inside q or materialised q, but this can be achieved by combining both functions.

the use of pull inside materialised q query can lead to false negative results.

materialised views

in addition, doxa has the ability to cache both pull and q results. each transaction is broken down into a sequence of datoms which are compared with the stored queries in the cache and if they match, the result is deleted. this results in a recalculation of only those queries whose result will be changed. clearing the cache during a transaction rather than before a search makes returning materialised results as fast as picking from a map.

the cache implementation uses a protocol, and the functions are standard hit & miss. i did not use clojure/cache because there is no cljs version. instead, the implementation available in ptaoussanis/encore was adopted, and supports either ttl, cache-size and gc. peter is a king and his contribution to clojure is invaluable.

lazy views

doxa has the ability to return a lazy document as well as a lazy query result. this is especially useful for implementations that retrieve data from an external source, e.g. lmdb. reify is returned, which has all the basic map protocols implemented, allowing the retrieval of data to be delayed until needed. lazy view can also be denormalised, thats allowing you to move along the edges of a graph using, for example, portal. cyclic graphs do not cause buffer overflow despite denormalisation.