Hello! Original author of Mentat here.
The use of SQLite for Mentat was intended to be an accelerant for development: by leveraging SQLite we could ignore large parts of the tricky problem of getting bits on disk across platforms, and also get things like transactionality and full-text search for free.
We used the same leverage trick when we built the first proof of concept using Clojure and ClojureScript — we could run it in a JVM locally, compare to Datomic, and test in Node, and entirely avoid having to build parsers and lexers. This allowed us to focus on the problem of representing a datom/log/index data model in SQLite.
The downside of using SQLite was a large amount of time writing code to compile queries — which were written in much the same language as Datomic’s — into SQL for execution. That Datomic compatibility also pushed us towards building an EDN parser in Rust, and we found some under-specified parts of Datomic, too.
Portability to the web itself was not an initial goal, but it was something we thought about. With adequate resourcing, and the benefit of hindsight, we would have instead built a chunk-based backing store abstraction, using something like rkv/LMDB for embedded use and indexeddb on the web. We did not feel like we had the engineering capacity to take on building a truly portable, battle-tested storage layer like SQLite’s *and* a bits-on-disk query executor — I’ve done it in the past, and it takes a lot of time and is hard to get right.
Mentat attempted to address a number of things that you didn’t cover in your brief post. A robust definition of identity, end-to-end encryption, and evolution of schema (even simple schema like cardinality and uniqueness constraints on attributes, which are the foundation of identity) are three such. Schema evolution becomes tremendously important when you have multiple teams using the same storage, or a long-lived product — the more useful the database is, the more likely you are to need this feature!
Those three things cascade into the problem of synchronization, which was my focus for a number of years.
Synchronization is a hard problem. Doing it without server assistance is even harder, but is necessary for a portable and secure product. Synchronization of generic data — that is, data where the synchronization tool itself doesn’t have its own model of the world — is extremely tricky: everything from identifiers through to basic constraints needs to be aware of the possibility of change, and naturally it’s an iterative and distributed situation. Most of the approaches I found rely on a server and are for systems that omit schema, and are typically incomplete: e.g., detecting conflicts on individual attributes, leading to nonsensical results, and offload to the developer the problem of separately handling stable identifiers.
I still have a persistent itch to start with a clean slate and solve this problem. No large company has the right incentives to solve the much harder problems faced by a truly secure store, most hobbyists lack the understanding of the importance of managing change and concurrent collaboration over time, and the current trend is towards using ‘dumb’ object/key-value stores or specialist systems like time-series databases, so I think it’s unlikely that anybody else is going to tackle all three in the same solution. Here’s hoping!
Richard Newman <rnewman@twinql.com> writes:
> Hello! Original author of Mentat here.
Hi there! You wouldn't be suprised if I told I recognize you by name,
would you?
Great job on Mentat, and please write more installments on "Thinking
about Syncing" if possible ☺️
> The use of SQLite for Mentat was intended to be an accelerant for> development: by leveraging SQLite we could ignore large parts of the> tricky problem of getting bits on disk across platforms, and also get> things like transactionality and full-text search for free.
For your goal of supporting other teams working on Firefox, SQLite is a
perfectly reasonable choice.
> We used the same leverage trick when we built the first proof of> concept using Clojure and ClojureScript — we could run it in a JVM> locally, compare to Datomic, and test in Node, and entirely avoid> having to build parsers and lexers. This allowed us to focus on the> problem of representing a datom/log/index data model in SQLite. >> The downside of using SQLite was a large amount of time writing code> to compile queries — which were written in much the same language as> Datomic’s — into SQL for execution. That Datomic compatibility also> pushed us towards building an EDN parser in Rust, and we found some> under-specified parts of Datomic, too.
Hmm, I'd be interested in learning more about those under-specified
pitfalls to try to avoid them if possible.
> Portability to the web itself was not an initial goal, but it was> something we thought about. With adequate resourcing, and the benefit> of hindsight, we would have instead built a chunk-based backing store> abstraction, using something like rkv/LMDB for embedded use and> indexeddb on the web. We did not feel like we had the engineering> capacity to take on building a truly portable, battle-tested storage> layer like SQLite’s *and* a bits-on-disk query executor — I’ve done it> in the past, and it takes a lot of time and is hard to get right.
I don't expect to match SQLite's robustness for quite some time, and
having plugable storage APIs makes me consider having a SQLite storage
API to have as a correctness reference.
What do you mean by "chunk-based backing store abstraction"? Could you
elaborate further?
> Mentat attempted to address a number of things that you didn’t cover> in your brief post. A robust definition of identity, end-to-end> encryption, and evolution of schema (even simple schema like> cardinality and uniqueness constraints on attributes, which are the> foundation of identity) are three such. Schema evolution becomes> tremendously important when you have multiple teams using the same> storage, or a long-lived product — the more useful the database is,> the more likely you are to need this feature!
What do you mean by "identity"? As in ":db.unique/value" and
":db.unique/identity"? Couldn't you just use UUIDs for
":db.unique/identity" values?
For schema evolution wouldn't the "Grow your schema, and never break
it"[0] approach be enough?
On encryption, my first approach would be to see if git-remote-gcrypt[1]
functionality can be translated, and have the local database be ignorant
of all encryption whatsoever. However, I haven't explored it enough to
be able to declare it to be possible, so I would welcome a more mature
view on the subject.
[0]: https://blog.datomic.com/2017/01/the-ten-rules-of-schema-growth.html
[1]: https://spwhitton.name/tech/code/git-remote-gcrypt/> Those three things cascade into the problem of synchronization, which> was my focus for a number of years. >> Synchronization is a hard problem. Doing it without server assistance> is even harder, but is necessary for a portable and secure product.> Synchronization of generic data — that is, data where the> synchronization tool itself doesn’t have its own model of the world —> is extremely tricky: everything from identifiers through to basic> constraints needs to be aware of the possibility of change, and> naturally it’s an iterative and distributed situation. Most of the> approaches I found rely on a server and are for systems that omit> schema, and are typically incomplete: e.g., detecting conflicts on> individual attributes, leading to nonsensical results, and offload to> the developer the problem of separately handling stable identifiers.
If sound and robust, what's the downside of detecting conflicts on
individual attributes?
If an Datomic-like entity with 10 attributes has 4 of them change by
different database instances, but only 1 change is on the same
attribute, would this type of detection offer more granularity instead?
Wouldn't the 5-tuple be the equivalent of a single line of code on git,
and aggregates are built on top of it?
> Hi there! You wouldn't be suprised if I told I recognize you by name,> would you?> > Great job on Mentat, and please write more installments on "Thinking> about Syncing" if possible ☺️
One day I do hope to return to them! Thank you for the kind words.
> Hmm, I'd be interested in learning more about those under-specified> pitfalls to try to avoid them if possible.
Mostly the usual stuff you get when a thing is defined by its implementation:
https://github.com/mozilla/mentat/pull/665https://github.com/mozilla/mentat/issues/412
There are probably more if you poke around the issue tracker.
> What do you mean by "chunk-based backing store abstraction"? Could you> elaborate further?
I'm familiar with the way AllegroGraph does storage, and fairly familiar with how Datomic does it.
In short, a datom store like this consists of the log (all datoms, with retractions, ordered by ID), and some current state (which Mentat called `datoms`), which consists of all current asserted datoms.
The current state is typically stored in a number of redundant permutations to support querying. In AllegroGraph (subject, predicate, object, graph, id), it would maintain multiple indices: `spogi`, `posgi`, etc. Each of these store the same datoms in different orders.
If we have the data
```
:bob foaf:knows :alice
:alice foaf:name "Alice"
:bob foaf:name "Bob"
:bob foaf:age 26
:alice foaf:age 30
```
it might appear in the `spogi` index as:
```
:alice foaf:age 30
:alice foaf:name "Alice"
:bob foaf:age 26
:bob foaf:knows :alice
:bob foaf:name "Bob"
```
and in the `posgi` index as:
```
foaf:age 26 :bob
foaf:age 30 :alice
foaf:name "Alice" :alice
foaf:name "Bob" :bob
foaf:knows :alice :bob
```
Naturally these would be using efficient (interned) sortable representations of each term, with rows of fixed size, memory mapped on disk.
This allows you to implement query pattern execution as an index walk.
`SELECT ?s WHERE ?s foaf:name 'Alice'`
for example turns into a walk on `posgi`: you find the spot that corresponds to `foaf:name`, find the next place which is `Alice`, and then read out the `s`.
When you insert data, you typically don't want to immediately regenerate all of these indices. Instead you accrue new *chunks*, which are just all of the datoms asserted in some window of time, or within a particular transaction. The query engine walks all of the relevant chunks and merges the results together. One chunk might have Bob's name, and one might have Alice's.
Typically _metaindices_ are used to help the query engine navigate which chunks to use.
AllegroGraph periodically merges chunks together: a fully merged store is faster to query. Datomic goes the other way: it builds new merged chunks and keeps the old ones around, because those old chunks represent the state of the database at a point in time! This is how you efficiently query past states in Datomic: it trades space in your Cassandra cluster for the ability to grab the right chunks for any query.
You can easily imagine that any system that allows you to put a name on some region of data can be used to store these chunks, and their metaindices, and the log itself. The only requirement is that the chunk store be durable, and ideally replicated and relatively fast to read from.
> What do you mean by "identity"? As in ":db.unique/value" and> ":db.unique/identity"? Couldn't you just use UUIDs for> ":db.unique/identity" values?
If on Computer A I visit https://aclu.org, and on Computer B I visit https://aclu.org, my two computers will each give the same history item a different internal identifier — 1234 and 4567, say.
When I sync them, I need the data store to know that the visits I made to each page _were visits to the same thing_.
There is more value to it than that (e.g., Datomic's "lookup refs"), but it's important to recognize that identity is _domain specific_, and it is often _compound_ and even contextual or conditional.
A large part of synchronization, and a large part of data modeling in general, consists of figuring out exactly what it is you're trying to record data about, and how to identify it. It's tremendously important in NoSQL systems because there is no foreign key constraint to help you, and changing an identifier later is difficult. It's just as important in syncing systems because these identifiers are the only thing you have to help you merge data — to zip two graphs together.
> For schema evolution wouldn't the "Grow your schema, and never break> it"[0] approach be enough?
It definitely helps; this is how teams generally try to work with DynamoDB, for example, though there the schema is implicit rather than explict.
However, you inevitably have data migrations to worry about… not to mention that syncing makes this a distributed system, and so you cannot easily coordinate schema changes in more than one place, and they will race with new data!
There's also the argument that coordinating change in consumers and engineers is sometimes harder than evolving a vocabulary!
It's a complicated topic.
> On encryption, my first approach would be to see if git-remote-gcrypt[1]> functionality can be translated, and have the local database be ignorant> of all encryption whatsoever. However, I haven't explored it enough to> be able to declare it to be possible, so I would welcome a more mature> view on the subject.
I have been relatively happy with SQLCipher, and I think the idea of block-level encryption is a good place to put the abstraction. The thing you lose with any of these mechanisms is, by definition, the ability for a central entity to help you with conflict resolution. The best you can get is ordering of opaque chunks and collision detection.
> If sound and robust, what's the downside of detecting conflicts on> individual attributes?
It relies on extensive reification to achieve the property that we want: that each semantically conflicting write results in a conflicting attribute change.
As a contrived example example: notes have both a title and a body.
A user has two computers.
On Computer A, the user decides to change their first note to something else, updating both the title and body.
On Computer B, they do the same thing to a different title and body.
With attribute-based conflict resolution it is possible to end up with a note that has a combination of A's title and B's body — a combination that never existed on either computer.
This gets even worse when you treat deletion specially, when new assertions don't conflict but do alter domain semantics, or when some of the conflicts affect the way the rest of the data is interpreted (e.g., when you have an identity property or a lookup ref).
The only data modeling solution to this case is to introduce an immutable 'note node', and have the _change_ be to have Note One point to a different note node — one attribute change!
In a JSON-ish system like Pouch you'd swap an entire JS object within the same attribute, rather than having two different attributes.
Developers — at least, non-Clojure developers — rarely think in these terms, and now everywhere else you need to make really careful decisions about whether you point to the 'note' or the 'node'. Getting it wrong means dangling pointers.
Using per-attribute automatic merging without having an expert ontologist model your domain is a recipe for weird edge-case conflict resolution bugs that result in data soup or data loss.
> If an Datomic-like entity with 10 attributes has 4 of them change by> different database instances, but only 1 change is on the same> attribute, would this type of detection offer more granularity instead?
My thinking is mostly: you need some kind of schema mechanism to be able to recognize which properties can be reconciled safely, and you also cannot examine each tuple independently in many cases. It's complicated. Something like Dropbox's datastore conflict resolution (if I remember right) is fine much of the time, but wrong some of the time.
> Wouldn't the 5-tuple be the equivalent of a single line of code on git,> and aggregates are built on top of it?
Even source code merging isn't this simple, no? A conceptual operation like "add this line underneath this other line" is the thing you're trying to represent, but that line has _context_ — it might have moved, the file might have been renamed, or someone else already put a line there.
You've probably seen this with b0rked merges in software version control, where the result of a merge won't compile because of duplicate identifiers thanks to hunks moving around…
But trying to apply text-based merging to semantic data only works if there are no constraints in your data, or if you have fast-forward merges — merging can violate uniqueness properties in all kinds of ways.
This is some rich discussion, thanks for engaging!
Richard Newman <rnewman@twinql.com> writes:
> Mostly the usual stuff you get when a thing is defined by its> implementation:>> https://github.com/mozilla/mentat/pull/665> https://github.com/mozilla/mentat/issues/412>> There are probably more if you poke around the issue tracker.
Thanks for the references.
> I'm familiar with the way AllegroGraph does storage, and fairly> familiar with how Datomic does it.
I've used Common Lisp a lot before, and I heard a lot about
AllegroGraph, but I've never worked with it. Would you recommed it as a
place to take inspirations from?
> In short, a datom store like this consists of the log (all datoms,> with retractions, ordered by ID), and some current state (which Mentat> called `datoms`), which consists of all current asserted datoms.>> The current state is typically stored in a number of redundant> permutations to support querying. In AllegroGraph (subject, predicate,> object, graph, id), it would maintain multiple indices: `spogi`,> `posgi`, etc. Each of these store the same datoms in different orders.>> If we have the data>> ```> :bob foaf:knows :alice> :alice foaf:name "Alice"> :bob foaf:name "Bob"> :bob foaf:age 26> :alice foaf:age 30> ```>> it might appear in the `spogi` index as:>> ```> :alice foaf:age 30> :alice foaf:name "Alice"> :bob foaf:age 26> :bob foaf:knows :alice> :bob foaf:name "Bob"> ```>> and in the `posgi` index as:>> ```> foaf:age 26 :bob> foaf:age 30 :alice> foaf:name "Alice" :alice> foaf:name "Bob" :bob> foaf:knows :alice :bob> ```
These look just like the EAVT and AVET indexes in Datomic.
> Naturally these would be using efficient (interned) sortable> representations of each term, with rows of fixed size, memory mapped> on disk.>> This allows you to implement query pattern execution as an index walk.>> `SELECT ?s WHERE ?s foaf:name 'Alice'`>> for example turns into a walk on `posgi`: you find the spot that> corresponds to `foaf:name`, find the next place which is `Alice`, and> then read out the `s`.>> When you insert data, you typically don't want to immediately> regenerate all of these indices. Instead you accrue new *chunks*,> which are just all of the datoms asserted in some window of time, or> within a particular transaction. The query engine walks all of the> relevant chunks and merges the results together. One chunk might have> Bob's name, and one might have Alice's.>> Typically _metaindices_ are used to help the query engine navigate> which chunks to use.>> AllegroGraph periodically merges chunks together: a fully merged store> is faster to query. Datomic goes the other way: it builds new merged> chunks and keeps the old ones around, because those old chunks> represent the state of the database at a point in time! This is how> you efficiently query past states in Datomic: it trades space in your> Cassandra cluster for the ability to grab the right chunks for any> query.>> You can easily imagine that any system that allows you to put a name> on some region of data can be used to store these chunks, and their> metaindices, and the log itself. The only requirement is that the> chunk store be durable, and ideally replicated and relatively fast to> read from.
The most intriguing part of this for me is trying to mimic Datomic's
implementation of those merged chunks, specifically how Rich Hickey
describes it as an equivalent of persistent data structures used for
storage, with sharing of previous versions, etc. I believe he calls it
"durable persistent" datastructure, like making things on disk to be
a bit similar on how they are on memory.
In fact, that's exactly where I'm focused at right now: deepening my
grasp on persistent data structures to enable me to navigate this
subject with more fluidity, and try to implement such durable persistent
data structures.
The merging of the AllegroGraph that you describe sounds like the flat
files merge of indexes that RH describes, and contrasts with his
proposal. I'll try to find this quote, and re-read the paper he mentions
on the talk (IIRC it's the BigTable one).
I was considering having all indexes be derived from the raw data
transported between instances, but it might get computationally
expensive, and making those indexes replicable sounds like a good idea.
> If on Computer A I visit https://aclu.org, and on Computer B I visit> https://aclu.org, my two computers will each give the same history> item a different internal identifier — 1234 and 4567, say.>> When I sync them, I need the data store to know that the visits I made> to each page _were visits to the same thing_.
Isn't that a domain-specifc problem of identity?
I would solve this by allowing those two entries to cooexist without any
conflict, and do aggregation queries to answers those questions,
something like (pseudo-SQL):
SELECT DISTINCT(url) FROM urls;
...to show the all the visited URLs, and:
SELECT SUM(1) from URLS GROUP BY url
...to show the visit count for each URL.
WDYT?
> It definitely helps; this is how teams generally try to work with> DynamoDB, for example, though there the schema is implicit rather than> explict.>> However, you inevitably have data migrations to worry about… not to> mention that syncing makes this a distributed system, and so you> cannot easily coordinate schema changes in more than one place, and> they will race with new data!>> There's also the argument that coordinating change in consumers and> engineers is sometimes harder than evolving a vocabulary!>> It's a complicated topic.
On migrations:
I used to share your view on needing a migration scape hatch, but I
don't anymore. On the company I work those kind of database migrations
never really occur. People either create a new attribute, copy data from
a database to another, process it using ETL, compute things on the fly
with functions, and many other strategies. We've already had to comply
with excisions in production, but never on schema, only on data itself.
So I don't think that's an actual issue, and I would insist that the
"Grow your schema" approach actually does work at scale, on the long
run, for multiple scenarios.
> I have been relatively happy with SQLCipher, and I think the idea of> block-level encryption is a good place to put the abstraction. The> thing you lose with any of these mechanisms is, by definition, the> ability for a central entity to help you with conflict resolution. The> best you can get is ordering of opaque chunks and collision detection.
I believe that's not what I meant by comparing it to git-remote-gcrypt,
but maybe I misunderstood your point.
Here's a code snippet to try to highlight what I was referring to:
--8<---------------cut here---------------start------------->8---
$ pushd $(mktemp -d)
/tmp/tmp.iapFd5iBCr ~/
$ mkdir repo-1
$ cd repo-1/
$ git init
$ echo 'a' > file
$ git add file
$ git commit -m commit-a
[master (commit racine) c4112e4] commit-a
1 file changed, 1 insertion(+)
create mode 100644 file
$ git init --bare ../remote/
Dépôt Git vide initialisé dans /tmp/tmp.iapFd5iBCr/remote/
$ git remote add origin gcrypt::../remote
$ git push origin
gcrypt: Repository not found: ../remote
gcrypt: Setting up new repository
gcrypt: Remote ID is :id:KjDStP/7m18wJagDO0/o
Énumération des objets: 3, fait.
Décompte des objets: 100% (3/3), fait.
Total 3 (delta 0), réutilisés 0 (delta 0), réutilisés du pack 0
gcrypt: Encrypting to: --throw-keyids --default-recipient-self
gcrypt: Requesting manifest signature
To gcrypt::../remote
* [new branch] master -> master
$ cd ..
$ git clone gcrypt::remote repo-2
Clonage dans 'repo-2'...
gcrypt: Decrypting manifest
gpg: selecting card failed: No such device
gpg: Signature faite le mer. 02 sept. 2020 03:43:12 -03
gpg: avec la clef RSA 5BDAE9B8B2F6C6BCBB0D6CE581F90EC3CD356060
gpg: Bonne signature de « EuAndreh <eu@euandre.org> » [ultime]
gcrypt: Remote ID is :id:KjDStP/7m18wJagDO0/o
Réception d'objets: 100% (3/3), fait.
$ cd repo-2/
$ echo 'b' > file
$ git add file
$ git commit -m commit-b
[master a5f5f0b] commit-b
1 file changed, 1 insertion(+), 1 deletion(-)
$ git remote set-url origin gcrypt::../remote
$ git push origin
gcrypt: Decrypting manifest
gpg: selecting card failed: No such device
gpg: Signature faite le mer. 02 sept. 2020 03:43:12 -03
gpg: avec la clef RSA 5BDAE9B8B2F6C6BCBB0D6CE581F90EC3CD356060
gpg: Bonne signature de « EuAndreh <eu@euandre.org> » [ultime]
Énumération des objets: 3, fait.
Décompte des objets: 100% (3/3), fait.
Total 3 (delta 0), réutilisés 0 (delta 0), réutilisés du pack 0
gcrypt: Encrypting to: --throw-keyids --default-recipient-self
gcrypt: Requesting manifest signature
To gcrypt::../remote
c4112e4..a5f5f0b master -> master
$ cd ../repo-1/
$ echo 'c' > file
$ git add file
$ git commit -m commit-c
[master 3d71137] commit-c
1 file changed, 1 insertion(+), 1 deletion(-)
--8<---------------cut here---------------end--------------->8---
At this point, repo-1 has changes that conflict with repo-2, and remote
doesn't know about it, but we can resolve it locally:
--8<---------------cut here---------------start------------->8---
$ git pull origin master
gcrypt: Decrypting manifest
gpg: selecting card failed: No such device
gpg: Signature faite le mer. 02 sept. 2020 03:44:34 -03
gpg: avec la clef RSA 5BDAE9B8B2F6C6BCBB0D6CE581F90EC3CD356060
gpg: Bonne signature de « EuAndreh <eu@euandre.org> » [ultime]
Depuis gcrypt::../remote
* branch master -> FETCH_HEAD
Fusion automatique de file
CONFLIT (contenu) : Conflit de fusion dans file
La fusion automatique a échoué ; réglez les conflits et validez le résultat.
$ cat file
<<<<<<< HEAD
c
=======
b
>>>>>>> a5f5f0b6c780a7ab3f7e28f373b06fa9a10c443f
--8<---------------cut here---------------end--------------->8---
This is just the general behaviour that I'm aiming towards, but that is
really just a long shot, I still need to reasearch more on it.
At a glance I can't really tell if that is what you mean when citing
SQLCipher.
>> If sound and robust, what's the downside of detecting conflicts on>> individual attributes?>> It relies on extensive reification to achieve the property that we> want: that each semantically conflicting write results in a> conflicting attribute change. >> As a contrived example example: notes have both a title and a body. >> A user has two computers.>> On Computer A, the user decides to change their first note to> something else, updating both the title and body. >> On Computer B, they do the same thing to a different title and body. >> With attribute-based conflict resolution it is possible to end up with> a note that has a combination of A's title and B's body — a> combination that never existed on either computer. >> This gets even worse when you treat deletion specially, when new> assertions don't conflict but do alter domain semantics, or when some> of the conflicts affect the way the rest of the data is interpreted> (e.g., when you have an identity property or a lookup ref). > > The only data modeling solution to this case is to introduce an> immutable 'note node', and have the _change_ be to have Note One point> to a different note node — one attribute change! > > In a JSON-ish system like Pouch you'd swap an entire JS object within> the same attribute, rather than having two different attributes. >> Developers — at least, non-Clojure developers — rarely think in these> terms, and now everywhere else you need to make really careful> decisions about whether you point to the 'note' or the 'node'. Getting> it wrong means dangling pointers. >> Using per-attribute automatic merging without having an expert> ontologist model your domain is a recipe for weird edge-case conflict> resolution bugs that result in data soup or data loss.
TBH I'm not aiming for automatic conflict resolution.
Why not use the granularity of attributes to detect conflict, but not to
resolve them?
Let me add to the scenario you presented: notes have a title, a body and
an author.
A user has two computers.
On Computer A, the user decides to change their first note to
something else, updating both the title and body.
On Computer B, they do the same thing to a different title and body.
On both cases, the author stays the same.
When the DB instance on Computer A gets data from Computer B, the query:
SELECT * FROM notes WHERE id = 1234;
would return both, and some metadata saying that it has a conflict. Now
the programmer needs to decide how to deal with these: use timestamps,
pick a winning device, sort by revision ID and pick the first, show them
on a UI to the user to resolve, etc.
Either way, the DB knows that the note has the title and body attributes
in conflict, but the author is fine. The aggregate entity itself isn't
in conflict, but some of it's attributes.
The situation that you describe where one would end up with a note that
is a combination of A's title and B's body would only happen if the DB
tried to solve things "automagically".
However, I agree on the costly constant reification being required, and
for long disconnected histories to be merged together this might be
expensive.
>> If an Datomic-like entity with 10 attributes has 4 of them change by>> different database instances, but only 1 change is on the same>> attribute, would this type of detection offer more granularity instead?>> My thinking is mostly: you need some kind of schema mechanism to be> able to recognize which properties can be reconciled safely, and you> also cannot examine each tuple independently in many cases. It's> complicated. Something like Dropbox's datastore conflict resolution> (if I remember right) is fine much of the time, but wrong some of the> time.
Couldn't you leverage the schema for that? If the said conflicting
attribute has:
- cardinality one and both DBs changed it, we have a conflict;
- cardinality many and both changed the same attribute, we have a
conflict;
- cardinality may and Computer A changed an entry and Computer B changed
another one, we don't have a conflict.
and so on.
I wouldn't build it with an exaustive search, but just leverage the
schema to make those decisions.
I don't know Dropbox's datastore, is this[0] the one you're refferring
to?
[0]: https://dropbox.tech/developers/how-the-datastore-api-handles-conflicts-part-1-basics-of-offline-conflict-handling> Even source code merging isn't this simple, no? A conceptual operation> like "add this line underneath this other line" is the thing you're> trying to represent, but that line has _context_ — it might have> moved, the file might have been renamed, or someone else already put a> line there. >> You've probably seen this with b0rked merges in software version> control, where the result of a merge won't compile because of> duplicate identifiers thanks to hunks moving around… >> But trying to apply text-based merging to semantic data only works if> there are no constraints in your data, or if you have fast-forward> merges — merging can violate uniqueness properties in all kinds of> ways.
Yep, that was an oversimplification.
<hr />
Again, thanks for engaging, this discussion feels like a golden nugget.
> I've used Common Lisp a lot before, and I heard a lot about> AllegroGraph, but I've never worked with it. Would you recommed it as a> place to take inspirations from?
Helping to build it was a very formative experience for me. twinql was the name of my first SPARQL query engine, which became the genesis of AllegroGraph's, and it stuck as a domain name!
Some of AllegroGraph's performance is the result of decades of experience (Steve Haflich comes to mind) and having some of the same exceptional developers work on it as worked on the compiler, so its internals are excellent inspiration. The UPI (how EAV are represented) is a good idea executed well. AllegroGraph is also a good example of how important tooling is for exploring this kind of semi-structured data.
> These look just like the EAVT and AVET indexes in Datomic.
Yes, exactly! It's a very natural way to model a fixed-width tuple store.
> I was considering having all indexes be derived from the raw data> transported between instances, but it might get computationally> expensive, and making those indexes replicable sounds like a good idea.
It depends where you're replicating. In Datomic's case each of the query nodes gets a replicated copy of the index chunks it needs (and you can thus control cache warmth by routing queries to different nodes), because those nodes are meant to be fungible, and reads from S3 (or wherever) are cheap, so there's no sense doing the work twice.
If you were to stand up a hot spare, you would probably just stream the log and have the far end create its own indices. That's particularly true if the other store needs different indices, or is materializing views.
Sidenote: it surprises me that Datomic Cloud stores its log in DynamoDB. It's hard to imagine a good primary key scheme that wouldn't at some point exhaust write capacity, and DDB makes different availability and durability tradeoffs than S3. I'm curious how that decision was made.
Obligatory disclaimer: I work at AWS, but the above is not a statement on behalf of AWS!
>> When I sync them, I need the data store to know that the visits I made>> to each page _were visits to the same thing_.> > Isn't that a domain-specifc problem of identity?
Yes, absolutely. I take the position that the goal of a database is to help me efficiently, accurately, and ergonomically represent my domain. If it doesn't, every developer has to solve that problem at the application level, and that limits interoperability, correctness, performance, and expressiveness.
The ability for this data layer to be able to help you with problems like syncing also relies on its ability to leverage some information about your domain — compare to when you check in an image file or a tarball to Git, and it can't help you detect or resolve conflicts at anything more granular than the containing file, even if that file has its own internal structure.
> I would solve this by allowing those two entries to cooexist without any> conflict, and do aggregation queries to answers those questions,> something like (pseudo-SQL):> > SELECT DISTINCT(url) FROM urls;> > ...to show the all the visited URLs, and:> > SELECT SUM(1) from URLS GROUP BY url> > ...to show the visit count for each URL.> > WDYT?
The advantage is indeed that you have removed the ability for data to conflict.
The disadvantage is that you have pushed a domain identity and merging into application code, where:
* Every query needs to implement this kind of unification in multiple places, which is more expensive and horrendously difficult to get right, not to mention very hard for developers to read.
* Application developers can get it wrong (e.g., deleting from History needs to retract every entry with a given URL), and you make domain operations more complex as a result. Sometimes this adds value — e.g., this kind of accumulative storage gives you magic properties like lifetime undo! — but I suspect that putting that in the log is better.
* You lose some conveniences like lookup refs, because you've removed the concept of a 1:1 lookup altogether.
* You lose the trivial ability to detect and model _changes_, which I find is natural for developers: this approach essentially makes the log part of the datom state. You can still do retract/assert locally, for a particular entity, but if you want to e.g., get the latest title for a page, you need to reduce over the log with some ordering.
I agree with your position in principle: the idea of figuring out the current state dynamically by rolling up history from different machines is very event-sourcey and is theoretically pleasant. Every device would simply append new non-conflicting _observations_ to the log. I do advocate for this in some circumstances.
However, in practice we usually have some stable idea of what we want current state to be (particularly of schema itself!), and some domain concepts around identity and cardinality that we want to enforce and use to build concepts like change, conflict, and merging, and we need that maintained state to be fast and obvious because we use it when making new assertions.
In essence, the problem I was trying to solve with syncing in Mentat was: how do I allow developers to talk about their schema in such a way that they could get syncing for nearly free? That a sync engine could, in most cases, automatically figure out which entities were the same, decide on a stable ordering of operations, and rewrite history to produced the expected merged state, such that in the above example all the visits stitch together, we know the latest title, and the log has all the historical titles?
Using observation-structured storage to remove conflict is definitely a valuable tool in the toolbox for doing that: the more you can structure your data as new observations about stably identified things, the easier time you have with syncing. I believe, but have not proved, that a system with only identity properties and cardinality-many properties, perhaps with some additional restrictions on retraction and uniqueness, will never have conflicts when merging.
But I also think that the best developer ergonomics are actually slightly _more_ expressive than even Datomic or Mentat — developers told me that they wanted cardinality-N, and to be able to express types or domain restrictions on properties, and nesting, and so on — and delivering those ergonomics means taking care of turning the log into a simple, concrete current state for them to query.
Phrased differently: in the above, your developers want some way to write
SELECT url, title FROM pages
and
SET title FOR page WITH url 'foo.com' TO 'whatever'
Whether you do that by figuring out at sync time the current title for pages with a given URL, or whether you give them some affordance to dynamically roll that up from the log, gets to be the same thing if you think of Mentat's 'datoms' table and schema as a way for developers to describe how Mentat should roll up current state from the log!
> I used to share your view on needing a migration scape hatch, but I> don't anymore. On the company I work those kind of database migrations> never really occur. People either create a new attribute, copy data from> a database to another, process it using ETL, compute things on the fly> with functions, and many other strategies. We've already had to comply> with excisions in production, but never on schema, only on data itself.
I actually view what you describe as migration: the point at which you're defining a new attribute and storing things twice, or doing a batch job to move things over, is exactly a data migration, if perhaps smeared over space and time!
These still have all the problems that traditional schema migrations have: dealing with data that doesn't conform, and dealing with clients that don't know about the new format.
> So I don't think that's an actual issue, and I would insist that the> "Grow your schema" approach actually does work at scale, on the long> run, for multiple scenarios.
I agree. I also think that one of the ways it does so is by pushing the work of tracking versions and vocabulary into application code, either formally or informally (e.g., checking for the existence of a property, coordinating the upgrade of client code, etc.) — the clients need to know how to work with the schema as it grows!
This was the motivation for me spending time on vocabulary management, which we did end up building:
https://github.com/mozilla/mentat/wiki/Proposal:-application-schema-coordination-and-versioning> At a glance I can't really tell if that is what you mean when citing> SQLCipher.
Ah, we were talking about two different kinds of encryption!
We were using SQLCipher for local block-level encryption.
At Mozilla we would additionally use Firefox Account encryption to end-to-end encrypt data as it passed through Sync. The two are complementary. Sync acts exactly as you demonstrate with git-remote-gcrypt: two local devices can access cleartext and are responsible for resolving conflicts, and the service itself sees only ciphertext and does not involve itself in how conflicts are resolved.
My point in bringing this up is that many systems have a central entity that can help in resolving conflicts; if the central entity can only ever see ciphertext, it's limited to whatever ordering or collision properties you enable via the envelope. For that Git system I imagine it tracks refs, and the Git object store is opaque.
> TBH I'm not aiming for automatic conflict resolution.> > Why not use the granularity of attributes to detect conflict, but not to> resolve them?
In short:
* End user software is no longer built (as iSync was) to present data conflicts to end users for resolution. The goal is conflict resolution.
* You cannot leave a store in an inconsistent state until conflicts have been addressed, because you still need to handle local writes. You cannot disconnect a device until conflicts have been addressed; users expect continuity of service. Whenever you are able, you have to do _something_.
* _Someone_ has to write the code to resolve conflicts. Eventually you're going to have some dev come up with the bright idea of annotating "data objects" with some kind of conflict resolution attributes, and then have an automated "conflict resolver"… at which point you've Greenspun yourself a sync engine and schema language. This works much better when it's part of the storage and sync later, and can participate in transaction boundaries and annotate writes.
This is the doc I wrote to outline the motivations for Mentat at Mozilla:
https://mozilla.github.io/firefox-browser-architecture/text/0008-sync-and-storage-review-packet.html
The Lay Summary in particular is worth a read.
When we built Firefox for iOS we managed to put storage and syncing inside the same component, so finally we were in a position to track changes during writes, and could get it right. Mentat was the next logical step: how do we let other teams use a storage system that will still do a good job of syncing their data without them having to get elbow deep in how a sync engine works, and without them having to put all the syncing gunk — timestamps/versions, UUIDs, etc. — in their data model?
What does Mentat need to know, schema-wise, to be able to do that kind of declarative conflict resolution? We didn't finish answering that question, but I think the intended outcome is still valid.
> Either way, the DB knows that the note has the title and body attributes> in conflict, but the author is fine. The aggregate entity itself isn't> in conflict, but some of it's attributes.
This is what Couch/Pouch do, I think. Well, it actually resolves the conflict and leaves a conflict marker… no idea whether anyone actually writes code to check that!
> Couldn't you leverage the schema for that? If the said conflicting> attribute has:> > - cardinality one and both DBs changed it, we have a conflict;> - cardinality many and both changed the same attribute, we have a> conflict;> - cardinality may and Computer A changed an entry and Computer B changed> another one, we don't have a conflict.> > and so on.
Yes, that's exactly the approach we were taking. The important difference is that you also need to zip together identities during this process — for example, two assertions of a cardinality-one attribute are not a conflict if the two entities at the other end turn out to be the same. Couch etc. don't have that concept.
(In an open-world system like OWL-DL, this cardinality conflict actually becomes implication of equality!)
> I don't know Dropbox's datastore, is this[0] the one you're refferring> to?
Yep! It's a really great bit of thinking.
I started quoting many parts of your email, and things started to get
confusing. Each answer that I gave was referring to each other, and I
almost made a loop.
So I've rewritten everything as a single piece of prose. I added some
snippets of your text to better contextualize what I was talking about,
but I tried to address what you said directly. Here it goes.
# On migrations
I still don't think that I've insisted enough on *strict* schema growth.
The wiki page you pointed to reinforces that: it talks a lot about how
to coordinate attributes that changed their names, change in vocabulary,
shared ownership of changes in schema and even schema versioning!
All of them are the opposite of what I want, and they're "schema
breakage", not "schema growth".
What I mean by that is the same thing that Rich Hickey proposes as a
what growth and breakage means in his talk "Spec-ulation"[0].
All of those forms of schema change are instances of breakage, which
should have no place here. They're all sources of undesired
incompatibility. I'm not sure if Datomic allows you to change the type
of an attribute, and if it does this can't be copied, since we don't
have a transactor to coordinate such change.
If you want to rename an attribute, don't! Create a new one! Maybe you
could retract schema and assert back the same schema, but you shouldn't
overwrite it with an incompatible name, or attribute type. This is a
trap that you shoudln't put yourself in, and maybe even this could be
enforced.
This model of an ever-growing vocabulary is how HTML works. At some
point people realised that using <b> to mark something as bold was not
such a good idea, since it coupled semantics with presentation. So a new
tag was created, <strong>, which only represents the semantic part of
<b>. And <b> still continues to exist, and that's fine.
The same can be said about JavaScript. I've written a fair share of it
in the past 2 years, and I don't think I ever used the 'var' keyword,
only 'let' and 'const'. And yet, every JavaScript runtime still
recognizes it, and even transpiler emit it as their output, and that's
also fine.
Maybe a linter or the browser tooling would warn you against the usage
of those old features, but they continue to work. If an equivalent of a
"vocabulary change" happened, web pages would be brittle by design more
brittle, and old pages would stop working as time passes. That isn't a
principle I would like to adopt.
When more than one database instance can add data, the programmer needs
to think of it as an open world, where new things are accrued, but old
things don't disapper. Changing the vocabulary mid-air only makes this
open world brittle so "migrations" can be performed.
I see no reason for having this type of migration you describe, and
insist on *strict* schema growth, it being a saner, more robust and
completly fine alternative.
[0]: https://www.youtube.com/watch?v=oyLBGkS5ICk
# On conflicts and ergonomics
You mentioned ergonomics thrice on your message, and I believe that your
insistence of it is a sign of the coupling of two different layers of
the database, and makes ease of use drive the fundamentals. I also think
that your statement on conflict resolution being a requirement is not a
good idea. Let me expand on that.
I'd argue that conflict resolution is inherit complexity [1] of creating
a decentralized client-side application that can sync data.
That means that the responsability to solve conflicts is not the
database's, but the application's responsability, and making decisions
of conflict resolution on the database limits its application, and I
wouldn't consider it to be general purpose.
When two offline database instances change the same field, there's no
escaping from the bottom reality, which is: there is a conflict, and it
needs to be resolved somewhere. There's no layer of ergonomics that can
change this fact, and picking a strategy for conflict resolution is
undoubtly domain-specific.
You mentioned that I proposed a solution on URL history tracking that
fowards all of the responsability to the programmer, but I was only
giving a simple example, and that same problem could be tackled in many
different ways, and the person creating the application has a decision
to make on it.
Let's expand on the URL history on the browser example from earlier, and
explore how to handle identity.
The application developer now has to decide what they want to consider a
URL being "the same" as another, and that's what I think you meant when
you talked about pushing domain identity to the application.
What does the programmer wants the identity of a URL to be? Is it a
UUID attributed to it when asserting the entitiy on the database? If so,
you would need to do things like the SELECT DISTINCT and SELECT SUM I
proposed, inevitably. The programmer may otherwise try to avoid this by
always starting from an existing database, so the history could be
common whenever a new database instance starts. One would just not
simply 'git init', they would 'git clone' in order to work with shared
identities that are created in a distributed way.
Is the identity of a URL its string? If so, the URL would have to be
treated as an URI, and that string would be effectively global, and
updates would have to be handled with lots of care.
The database *can't* make those decision. What it *can* do is provide
tools that allow the programmer to work with this inherent complexity.
And I see no way around it. No amout of ergonomics can solve this, and
removing the ability to have 1:1 lookups is the nature of decentralized
client-side applications, it's not me trying to forward a problem that
the database should solve to the programmer.
A simple comparison is: whenever we talk about code, we use SHAs to
pinpoint which piece of code we mean. What does a SHA say about the
existence of other branches that disagree? Nothing! You can't ever
assume that the commit you're on is the latest version of a file, or
even is the only version of a file. While you were not looking, any
number of new versions could have been created, which means that when
you fetch, there isn't a single README. There are *at least* two of
them: README from master, and README from origin/master. They may be the
same, and they may not be the same, but saying just "the README file" is
an incomplete depiction of it: you either say "my README file" or talk
about both of them, which do coexist.
There's no denial that this model is much more complex than the usual
1:1 lookup we're used to, but trying to hide this in the database
implementation somehow would be a bad idea. The programmer brought this
to themself when they choose to build a decentralized client-side
application.
However, with a solid foundation, there are still lots of room for work
on ergonomics, like:
1. diffing algorithms for text like you mention would totally
make sense to be in a "contrib/" directory, so that people could pick
different diffing algorithms for different string fields.
2. whenever a 'dev comes up with the bright idea of annotating "data
objects" with some kind of conflict resolution', I could point them to a
"IConflictResolutionStrategy" interface for they to implement. Their
implementation could even end-up under said "contrib/" directory. Even
better if "IConflictResolutionStrategy" could be composed! A programmer
would then pick different strategies for different entities in their
domain, like in a buffet.
3. offer some low-level building blocks that can be applied to different
domains, like tombstones, max(a.last-modified, b.last-modified), etc.
...and so on.
The point is: the database is not in a position to make this type of
decision. Only the programmer is, and they must be aware of it.
You said that:
> the goal of a database is to help me efficiently, accurately, and> ergonomically represent my domain
For me, the crucial part is the accurately comes first, and ergonomics
comes second. No accuracy should be sacrificed in name of ergonomics,
since the inherent complexity is already too big to be dealt with.
The syncing part is not free.
[1]: As defined in http://curtclifton.net/papers/MoseleyMarks06a.pdf
# On history rewriting
You talked about how Mentat was trying to reconcile changes by rewriting
the history in a stable and consistent order.
I'd argue that instead of a linear log where things are rebased, a DAG
log where things are merged is a more flexible approach. Let me show you
where I'm coming from first.
You said that:
> Phrased differently: in the above, your developers want some way to> write>> SELECT url, title FROM pages>> and>> SET title FOR page WITH url 'foo.com' TO 'whatever'
This may still be true, but with a caveat: you'd be asserting facts to
the local "timeline", in a somewhat similar way that the Mentat wiki
describes[2] (I feel funny giving you a link to Mentat's wiki).
What I'd do differently is to don't try so hard to make everyone
converge on the same thing always, and represent timelines in a more
flexible way.
Instead of having two types of timelines, α and β, there would be a
multitude of timelines, one for each instance of the database. Let's say
we have 3 of them for the purpose of explanation.
Instead of adding an extra 'timeline_id' identifier, I'd add a
':db/txParent' to the transaction entity, with cardinality many, and the
database instance would always know it's latest local parent. This is
effectivelly like a branch, but not a shared one, and transations with
more than one ':db/txParent' represent merges. Those would only happen
when explicitly solving conflicts, and any given database instances
could know about a multitude of timelines.
This way, how can one know the current state of the database?
From the first root datom, the database would rollup every datom taking
the timelines and merges in consideration, and it would be the sum of
data from all timelines. When a conflict exists, the local timeline is
always picked so the database can still serve writes, and the conflict
would be presented when serving reads.
The obvious problem of always favouring the local timeline is that each
timeline would show different "primary" answers, but that's sounds
somewhat reasonable to me to enable the database to keep working while
offline, and while the conflict isn't resolved.
This also means that "sync" are two distinct things: exchanging timeline
data, and reconciling that data locally. The only part that's online is
the "exchange", and instances resolve conflict locally. This way, the
database is always available, even when offline, and even when conflict
is present.
But how would queries over history behave? No clue yet 😬.
I tried not to sound too hand wavy, and I've only prototyped a small
part of this in the past, so there are probably many more problems with
this approach. I don't claim this is a sound solution yet, but it does
handle some of the problems that Mentat faced in a different way. I'd be
interested to see you poking holes on it.
When combined with strict schema growth, new data always comes after
it's schema declaration, so the application doesn't have to coordinate
around distributed schema evolution.
[2]: https://github.com/mozilla/mentat/wiki/Multiple-timeline-support
# On CouchDB/PouchDB's entity conflicts
CouchDB/PouchDB's most fundamental value is the document. This means
that a single document write is atomic (not true for clustered CouchDB),
but you end up rewritting the full document ([3], on time 3:35). If you
represent an entity as a document, the whole entity is in conflict, not
the attribute that changed.
So it doesn't know the difference between two changes on unrelated
attributes and full rewrites of the full document: everything is a
conflict in CouchDB/PouchDB's view.
On another talk ([4] on time 5:30, also by Joan Touzet), she mentions
the desire to add partial updates to CouchDB, but I don't know if it was
pursued.
Checking for conflicts on revisions is considered good practice ([1], on
time 10:21) on the community.
[3]: https://www.youtube.com/watch?v=BKQ9kXKoHS8
[4]: https://www.youtube.com/watch?v=0gAZHIYBh-g
# On zipping identities together
👍
# Misc
TIL: I didn't know you worked on AllegroGraph.
P.S.: I haven't reviewed this text too much, and it might have gotten a
bit confusing. I'm happy to clarify any points, and I'll consider
writing a more formal version of this braindump later. I chose to send
this like this over taking more time and letting the discussion cool
down.
I better get a POC so I can stop talking in "what ifs".
I was more focused on the storage implementation side of it, but I'm
considering not implementing a storage backend for this and just using
SQLite instead (more detailed in [0]).
Building durable persistent data structures on top of SQLite backed
storage is still a bit distant, but the model I presented could benefit
from a POC.
I'll try starting that instead of giving so much focus on storage, and
share it later.
[0]: https://euandre.org/2020/08/31/the-database-i-wish-i-had.html#fn:posix-sqlite
> The obvious problem of always favouring the local timeline is that each> timeline would show different "primary" answers, but that's sounds> somewhat reasonable to me to enable the database to keep working while> offline, and while the conflict isn't resolved.
Also a possible ergonomics layer that can be built on top of some lower level
primitive:
Suppose we want to add a profile page to an app, but the user will be
able to edit their profile while offline.
Such profile page contains 3 parts: name, bio and links. Here's how it
could look like:
{:profile/name "Foo Bar"
:profile/links #{{:link/title "Personal webpage"
:link/position 0
:link/address #uri "https://example.com"}
{:link/title "Mastodon profile"
:link/position 1
:link/address #uri "https://example.org"}
{:link/title "Photo album"
:link/position 2
:link/address #uri "https://example.net"}}
:profile/bio "My lengthy bio (...)"}
For each of those attributes, one could want to handle conflicts in a different
way:
1. For the :profile/name, you could want to be fully conservative, and never
resolve any conflict whatsoever. If the user changes their name to "Foo Bax"
in one device and to "Foo Baz" in another, you may choose to not solve this
conflict on the application. Instead you could just pick one of them to show
to the user on their profile page, say "Foo Baz", but add an exclamation mark
icon ❗️ beside it. When the user touches the icon, the app asks: "do you want
to keep 'Foo Baz' or would you like to change it to 'Foo Bax'?". This could
be done multiple times for multiple concurrent conflicts, and when user
confirms their choice, that's a merge that resolves the conflict for all
instances when propagated.
The upside is that the app doesn't try to be smart about reconciling the
:profile/name, showing things like "Foo Baxz" or "Foo BazFooBax". The
downside is that if the app doesn't handle this explicitly, they'll be
perpetually inconsistent.
2. For the :profile/links, specifically the :link/position attribute, you might
try an intermediate approach. Say you want to handle reordering less
conservatively. Say the user changes the position of the "Photo album" link
to 1 in a device, and to 0 on another device, and that is their actual
desired final position for this link. You could solve it by doing
something trivial, like picking the transaction UUID with the lowest
alphanumerical value. This gives you consistent choices across instances, and
a potential nuisance for the user: if the winning final state is with "Photo
album" a 0, nothing needs to be done, and all instances agree with this. If
it isn't, then the user should reorder again, and all instances would still agree.
The upside of this is that this conflict resolution strategy allows you to
never stay conflicted for this particular attribute, and you could have 1:1
lookups back. The downside is that this assumes that the transactions that
are reordering links contain only :link/position attribute asserts.
3. For the :profile/bio, you could be extremely optimistic, and try to combine
all edits. This could be done by modeling it using commutative edits, similar
to how in [0], and let everything always converge. Maybe even adopt the
binary enconding of edits proposed in [1], and encode all of the edit history
in the database itself. They talk a lot about the metadata overhead of the
edit history, and recording every edit as they come in would also add a
datom-related overhead, too. It might be more advantegeous to accumulate the
edit history, and when the app closes or a relevent event occurs, all edits
are combined into a single binary, and that would be a single datom entry.
This would remove the datom-related overhead while still persisting the full
edit history.
The upside of this is that the text could always converge, you would get
1:1 lookups back and you wouldn't have to deal with diffs on a huge string,
neither would the user. The downside is that you'll need a layer on top of the
transactions to actually derive the text, and querying would get trickier.
The database would give you the ordered list of all binary enconding things,
and a function would turn that into text.
Another downside is that this is very much an open research problem, and
probably has a lot of maturity to be gained. It would be very powerful if
this could be built on top of some database primitive, without the database
having to explicitly support it.
All of that to handle the conflicts of *each attribute*, and they're all
the programmer's responsability to choose.
If the database was versatile enough, an ideal world the programmer could write:
;; schema definition
[{:db/ident :profile/name
:db/valueType :db.type/string
:db/cardinality :db.cardinality/one
:db/conflict-strategy :db.conflict-strategy/none}
{:db/ident :link/position
:db/valueType :db.type/long
:db/cardinality :db.cardinality/one
:db/conflict-strategy :db.conflict-strategy/simple-winner}
{:db/ident :profile/bio
:db/valueType :db.type/string
:db/cardinality :db.cardinality/one
:db/conflict-strategy :db.conflict-strategy/automerge}
...]
And be done with it.
If those :db/conflict-strategy fields could be open and extensible, the database
could learn new algorithms to deal with conflict without changing it's
internals, and people could teach how translate the :profile/bio from
:db.type/string the actual :db.type/bytes that would be actually stored.
Also, I think this is what I was trying to say with "coupling two differente
layers of the database". However, I haven't tested any of this yet.
[0]: https://doi.org/10.1016/j.jpdc.2010.12.006
[1]: https://github.com/automerge/automerge-perf/tree/master/columnar
Ah, thank you for the conversation refactor!
> The wiki page you pointed to reinforces that: it talks a lot about how> to coordinate attributes that changed their names, change in vocabulary,> shared ownership of changes in schema and even schema versioning!> > All of them are the opposite of what I want, and they're "schema> breakage", not "schema growth".
My two observations are these:
On the one hand, front-end developers tend to think in terms of change — "this thing's title was X and is now Y" — and states — "give me a list of things and their current titles so I can search them or show them in a table".
That view of change extends to schema/data, because the schema stretches most of the way towards the front-end itself, sometimes all the way to a "view model" in the MVVM sense.
And it involves migration, because no front-end developer (or back-end developer, for that matter) wants to have to write queries that accommodate all of the different ways a particular concept might have been represented in the last ten years. Doing so is mentally taxing, is very difficult to test, and results in wildly variable performance. They want to fix their data once, or define how to roll it up into a single state once, and make sure the old representation never gets used again. And these representations do change, often significantly; making sure they don't requires tremendous up-front deep thought (for example, my modeling attempt for embedded videos), and results in something that is often normalized to the point of non-viability (already a concern with tuple stores).
On the other hand, storage/syncing developers learn to love immutable logs, because it makes a ton of sense. Syncable storage systems should be based on an immutable timeline of appended observations of the world.
There is obvious conflict between these two. Resolving that conflict involves some complexity, and I felt it better to address that complexity once, inside the storage system.
I didn't feel that it was worthwhile to build a storage system that required front-end developers to adjust their mental model so far from what they're trying to achieve on a daily basis, because they have a choice in which tools they use.
From my perspective, the primary goal has to be to give them a system they're willing to use (a clear, current-focused schema and the ability to represent change), with the additional goal of a useful log and better formalisms underneath to support syncing. Putting it the other way 'round would simply lead to them using SQLite or JSON files, omitting syncing, building bad ad hoc sync solutions, and otherwise continuing in the way that Mozilla had been doing things.
Mentat, like Datomic, is a stateful layer on top of log-structured data, with the current schema — like the current state of the world! — being materialized from the log.
> When more than one database instance can add data, the programmer needs> to think of it as an open world, where new things are accrued, but old> things don't disapper. Changing the vocabulary mid-air only makes this> open world brittle so "migrations" can be performed.
I am a fan of open-world systems — I spent 7+ years working on semantic web stuff! — but I'm not aware of any client applications with any degree of adoption that use the open-world model. Having multiple components share state doesn't require an open world per se.
Being able to evolve the representation of existing data, just like being able to 'change' the state of the world, is regarded as a *feature* by developers, and they typically would rather sacrifice interoperability than take on the burden of dealing with a pile of data that only gets more crufty over time. In the 'schemaless' world (e.g., DynamoDB), developers take a mix of painful approaches (ranging from adding version tags that drive switches in application code, to doing manual migrations between tables) to clean up old data when the previous representation cannot stretch far enough.
I tried with Mentat to strike a balance here: to design a system that would allow multiple teams to interact, defining their vocabularies in an ever-growing way, with specific transformation steps as needed, and being able to detect and handle conflicting vocabulary usage within that closed world. You can absolutely use Mentat as a system with no vocabulary modification ever, complicating your queries to accommodate, but it would not have met the needs of its audience:
D: "So, I realized that having a page -> visit timestamp property doesn't actually do what we want; we need to be able to mark each visit with which device visited the page. How do I change the schema and the existing data?"
R: "You can't; make a new property. Every time you want to retrieve the visits for the page, everywhere in your app, your queries need to look at both properties."
D: "Can I write some function that seamlessly transforms the old data to the new format and works with syncing?"
R: "I wrote a doc about that, but we decided that purity was better. You can write code to manually retract the old stuff, but other syncing devices can still mess you up. Sorry."
Resolving conflicts and supporting sync was a core part of Mentat's charter. The last thing I wanted was for developers to think the system was hard to use, or to build a second storage layer on top to maintain a snapshot of the current data in an app-centric format.
> You mentioned ergonomics thrice on your message, and I believe that your> insistence of it is a sign of the coupling of two different layers of> the database, and makes ease of use drive the fundamentals.
Yes, exactly. The goal of Mentat wasn't to build a pure log-structured store: it was to build a store with a developer interface that wasn't too alien to an engineer who might store data in JSON or SQLite, but with internals that made sharing data, syncing data, and evolving data easier and safer.
> I also think> that your statement on conflict resolution being a requirement is not a> good idea. Let me expand on that.> > I'd argue that conflict resolution is inherit complexity [1] of creating> a decentralized client-side application that can sync data.> > That means that the responsability to solve conflicts is not the> database's, but the application's responsability, and making decisions> of conflict resolution on the database limits its application, and I> wouldn't consider it to be general purpose.
Ah, here's an interesting point.
There are two positions here: am I vending a database, or am I vending a storage solution for a client app?
Building Firefox, Firefox for Android, and Firefox for iOS convinced me that implementing a synchronization solution that is not tightly coupled with the storage layer — that is, one that is just another consumer of the same storage interface that the rest of the app uses — is difficult and error-prone. Sync needs to see writes as they happen, and synchronization has particular implications for how data is stored.
I also found that offloading the difficulties in syncing — conflict resolution, tracking change, merging identities, etc. — to application developers leads to worse outcomes.
My feeling is that it should be possible for the application to educate the storage layer about how to handle most of the conflicts it encounters, and to model its data in a way that makes conflicts meaningful and minimal, without sacrificing the kinds of data representations with which developers feel comfortable.
> When two offline database instances change the same field, there's no> escaping from the bottom reality, which is: there is a conflict, and it> needs to be resolved somewhere. There's no layer of ergonomics that can> change this fact, and picking a strategy for conflict resolution is> undoubtly domain-specific.
The approach I was taking for syncing in Mentat involved rewriting (or permanently associating) identifiers based on uniqueness constraints. That is, as a developer I could transact a schema fragment:
{:history/url :db/unique :db.unique/value}
and thereafter say things like
{:history/url "https://foo.com/"
:history/title "Today's title"}
If the log already contains this, with a local ID:
[1234 :history/url "https://foo.com/"]
the new transact would add to the log something like:
[1234 :history/title "Today's title"]
Another device can record similar data:
{:history/url "https://foo.com/"
:history/title "A different title"}
which would transact
[4567 :history/title "A different title"]
A query on either platform can omit the ID, using a lookup ref instead:
[[:history/url "https://foo.com/"] :history/title ?title]
In both cases we get a 1:1 association between a URL and a 'page'. The use of lookup refs and the schema definition allows the developer to use the [attribute, URL] pair as an external identifier in this context, while using an efficient identifier internally.
When the two transaction logs are merged, it follows from the schema definition that B(4567) === A(1234), and that identity can be used in the store to zip the two graphs together in a way that is seamless to the developer: the 1:1 association is preserved. In practice we found that holding on to those numeric IDs, which can change during syncing, in application code was rarely or never necessary.
This example is what I mean by 'teaching' the database about domain definitions of identity. In a relational database, the schema is largely used to define structure and constraints. The way it feels to write a schema in Datomic/Mentat is much closer to 'explaining' how various kinds of new assertions and sync behaviors will interact with the existing data — the schema constraints are so often used to drive lookup refs and updates, and of course there's no tabular structure.
This can get a merge all the way down to "this page's title changed from X to Y at time T on one device and from X to Z on another at time Y; which do you want?" which is _also_ something that you can teach the database to automatically resolve — annotate the schema to say that a conflict takes the time-latest value.
> They may be the> same, and they may not be the same, but saying just "the README file" is> an incomplete depiction of it: you either say "my README file" or talk> about both of them, which do coexist.
I actually used this as an example when explaining Mentat — timelines are branches, but the `datoms` table (the data you actually work with) is a Git "working tree". Developers (and end users) need a working tree and a single state of the world.
> The point is: the database is not in a position to make this type of> decision. Only the programmer is, and they must be aware of it.
Which kinds of programmers are your audience?
In my experience, most developers are (a) not aware of the difficulties here, (b) do not have the time to dig in to the details, and (c) would rather take reasonable defaults (e.g., latest wins) or even data duplication or corruption than sacrifice simplicity to get it right. That is: if you presented them with the option of a distributed sync system where they had to handle multiple timelines, use pluggable conflict-resolution modules, and write complicated queries to deal with that complexity, they are instead going to use JSON files.
It would not be inaccurate to say that Mentat is/was _already_ way too much of a shift for most developers; a tuple store with a log is expensive and confusing in ways that a key-value store is not.
> You said that:> >> the goal of a database is to help me efficiently, accurately, and>> ergonomically represent my domain > > For me, the crucial part is the accurately comes first, and ergonomics> comes second. No accuracy should be sacrificed in name of ergonomics,> since the inherent complexity is already too big to be dealt with.
To broaden your point a little bit, my position on that has shifted over the years, after working on systems that prioritized correctness over adoption or user experience (e.g., Firefox Sync's perfect crypto, which caused _so many users_ to lose data because they weren't prepared to manage long-lived secure keys, and couldn't understand the setup flow…).
A system that is perfect but that people — developers or end users — don't use it is _worse_ than a system that makes compromises and gets some adoption. As Guy Steele put it about Java:
"We were not out to win over the Lisp programmers; we were after the C++ programmers. We managed to drag a lot of them about half-way to Lisp."
I think a brief tangent into ontology would be interesting. I know your point here is about accurately modeling change, but a similar set of positions exists when modeling information itself.
The 'correct' way to model the world is as a time-series sequence of independent observations, with everything else being materialized from it through a carefully designed ontological lens, such that one doesn't have to accidentally make false statements in order to say something true.
At one end is the kind of ontology I drew on a whiteboard once, nearly twenty years ago, in which the concept of a music "album" is broken down into issuances, releases, track orders, renditions, recordings, performers, names, identities, collectives, etc. — it's incredibly complex how one recording of a group of people in a room might be recorded multiple times, remastered over the years, edited for various releases, and appear on multiple formats in different versions, and how different versions of songs might have different bands or people playing different parts.
Music nerds really care about this, though perhaps not down to the level of detail to which I modeled it.
At the other end is how this kind of metadata is really represented in the real world.
Title: "Landslide"
Artist: "Fleetwood Mac"
Play Count: 15
Track Number: 2
The theoretically pure way to model all this stuff makes it possible to say "this recording of Landslide is of a performance by a band named Fleetwood Mac — the particular instance of Fleetwood Mac that included Stevie Nicks, not the one that included Bob Welch". Let's not even get into the fact that there are two albums recorded by Fleetwood Mac titled "Fleetwood Mac" — (title, artist) isn't compound-unique!
But no user wants to say "Alexa, play Fleetwood Mac" and have her reply "do you mean the band 'Fleetwood Mac' that recorded songs released by Warner Bros, or the band 'Fleetwood Mac' that recorded songs released by Blue Horizon"? They will exchange a certain amount of precision to cast a wider and more usable net.
Put bluntly: apps have trouble getting the darn play counts on two devices to add up to the same number, let alone this degree of precision. I would rather make it _possible_ for them to model data at a reasonable degree of accuracy, with no more difficulty than they would have writing a CREATE TABLE statement, and help them get their play counts right when they sync two devices, rather than force them to take an extreme position on accuracy and leave them to figure out how to list how many times the user played a song.
> This way, how can one know the current state of the database? > > From the first root datom, the database would rollup every datom taking> the timelines and merges in consideration, and it would be the sum of> data from all timelines. When a conflict exists, the local timeline is> always picked so the database can still serve writes, and the conflict> would be presented when serving reads. > > The obvious problem of always favouring the local timeline is that each> timeline would show different "primary" answers, but that's sounds> somewhat reasonable to me to enable the database to keep working while> offline, and while the conflict isn't resolved.
My view is that end users expect all of their devices to present the same canonical view of their data, and manual conflict resolution should be rare/unnecessary/modeled as an explicit change or an explicit state (a write like any other).
Further, developers expect queries to be fast and writes and queries to behave the same when devices are synced, regardless of which device performs the write or runs the query.
That makes it difficult to either diverge between devices for long periods, or to expect routine manual involvement in conflicts.
It seems to me that the longer these distinct timelines exist, the more conflicts will breed, as writes reflect different local states, and so the difficulty of presenting a coherent view increases over time.
I expected probably one place to do manual conflict resolution in Firefox: password management. Even there it might be better to turn every conflict into an explicit "previous passwords" entry, or to expose the log as a dynamic list of previous passwords — that data is valuable for detecting website breaches. That is, it's better to surface the alternative data as a normal change and reach agreement with other devices, rather than preserving some kind of pending conflict.
By modeling rebases or merges as a coherent set of retractions of conflicting data, it's still possible to implement log-oriented features like querying *every* title a page has ever had, but eagerly reach a shared timeline. ("Show me that news article I remember reading".)
> This also means that "sync" are two distinct things: exchanging timeline> data, and reconciling that data locally.
Agreed.
> The only part that's online is> the "exchange", and instances resolve conflict locally. This way, the> database is always available, even when offline, and even when conflict> is present.
The difference IMO is that the goal of conflict resolution is that every device converges on the same canonical timeline, and does so as quickly as possible.
> But how would queries over history behave? No clue yet 😬.> > I tried not to sound too hand wavy, and I've only prototyped a small> part of this in the past, so there are probably many more problems with> this approach. I don't claim this is a sound solution yet, but it does> handle some of the problems that Mentat faced in a different way. I'd be> interested to see you poking holes on it.
It's a really difficult problem! My suspicion is that querying history is either broadly a union ("these pages all had this title at some point") or very much an expert feature, analogous to browsing your own 'undo' tree. But note that the union approach can benefit from identifier rewriting to represent derived equality at a particular point in time, even in the presence of conflicts.
> When combined with strict schema growth, new data always comes after> it's schema declaration, so the application doesn't have to coordinate> around distributed schema evolution.
Yes, that's broadly the position I took with Mentat: by definition, data on each timeline comes after its schema declaration, so we have an ordered mechanism for merging and also for migrating data as the schema evolves.
> TIL: I didn't know you worked on AllegroGraph.
Seems like every few years I end up back on data modeling and graph storage :D
> If the database was versatile enough, an ideal world the programmer could write:> > ;; schema definition> [{:db/ident :profile/name> :db/valueType :db.type/string> :db/cardinality :db.cardinality/one> :db/conflict-strategy :db.conflict-strategy/none}
Yes, that's pretty much where we were headed with Mentat. My key observations were that (a) you need really good tree-zipping, and frequent syncs, to minimize conflicts; (b) tree-zipping and merges practically require that internal identifiers be rewritten when identity is determined; (c) it is undesirable to stop the world, and so when a conflict is detected you end up with continuing divergence which will be even harder to merge later; (d) because this is a single graph, a conflict _must_ be resolved in some way before you can merge two heads; (e) lossy merges (squash then rebase or squash then merge) can help.
I see what to mean by being accessible, and it does make sense.
If done properly this might be the reality, where nobody chooses to
handle conflicts manually because they'd rather have a consistent view
by picking one of the possible algorithms that are available for them to
pick for each attribute. I'll experiment with this a bit, and if
feasible, the "perpetual inconsistency" might be an internal view, and
something available for those who choose to customize their conflict
resolution strategy. This would be ideal, and perfectly aligned with
what you said on "the application educating the storage layer about how
to handle most of the conflicts it encouters". The unique URL you showed
is a tempting challenge to reach, and the domain identity being
teachable sounds indeed really powerful.
This also means that with those defaults the desired 1:1 lookups would
be restored. I don't think that doing manual resolution for each
attribute is desired, and I wouldn't impose this on the programmer. In
fact, I'd want to use it myself most of the time.
That would also mean an intersection between the two conflicting forces
you mentioned, where both sides would get what they wanted: a developer
could use it to quickly prototype something by picking the suggested
defaults and not finding many surprises, while allowing another
developer to fine tune their strategy when desired.
It's a database, with a robust storage solution inside it, but primarily
a database.
If not possible, I tend to err on the side of less ease. Not because I
want to be a purist, but because I want to do this for myself 😬. The
title of the article was actually honest on this, and I've actually had
this exact though a few times: "I'm struggling with this database, but
there must be more people like me with the same struggles. I bet someone
has already solved, or will solve soon enough". I'm the target audience,
and if I do something that solves my problem, than I would consider it a
success :). It may not be widespread but I'd feel better knowing that
I've built something that works over something that works most of the
time. Again, I don't want to be a purist, I just want to create a
database that I'd want for myself, and whoever sees themselves on the
same position could benefit. If ease can be added on top of it with some
choices made for you, great! From your comment, I think you'd agree with
that last part.
I'm not trying to convert anyone on this, though. I'd be happy to share
the code and learning, and welcome those who are interested and
attracted to this, but broad adoption and world domination are not
goals.
The applications that I tried to write using the existing solutions were
just good enough to get me started, but I always felt abandoned when I
wanted to evolve it somehow, or add some specific functionality without
losing data, or some similar trade-off. Most of those times I'd rather
deal with that complexity than choose an easier path.
Today whenever I see a client-side database that syncs, I go to the
documentation and search for "conflict". I'll either get a page with
some in-depth explanation, or there will be a list of choices they made
for me with no way out of it, like last write win, and permanent
deletion tombstones. Sure those are valuable, but I'd rather be able to
choose them myself. I already know by now that I will need some tweaked
conflict resolution someday, and they won't be able to provide it for
me without an ad-hoc approach.
If someone would value something more familiar and more
fragile/opinionated over something very different and more sound, then
maybe they're correct to pick SQLite or some JSON files, and having data
loss in some edge cases would be just fine in the problem they're
solving. I'd encourage them to stick to SQLite, even, its a great piece
of software.
Also, there's something more profound on this, I believe:
Having a solid foundation could potentially help people reason about the
problem with good tools, instead of looking like a solid foundation that
will crack if you step on the wrong place. Instead of helping, it could
be hurting the application, and the superficial ease that many solutions
offer sometimes feel more like a trap for me to figure out myself later.
To me it's like someone saying: "have this relational fully ACID
performant database!", and only later I realize that it isn't actually
ACID by default, and if all change all the knobs to make it ACID, it
becomes unusuably slow (or maybe even those knobs aren't there at all).
I'd argue that such approach may look weirder and more foreign to any
developer, but it would actually be "easier". This reminds me of
"Simple Made Easy" [0]
[0]: https://www.infoq.com/presentations/Simple-Made-Easy/
Back on schema growth: one doesn't have to make a perfect plan of the
data models so no mental tax gets to them later.
The solution you mentioned sounds just fine: write a function that
transforms the old data and feed it to the new attribute, and retract
everything else. From that point on, you've effectively migrated the
data, and you'll only need to consider the historical schema when doing
historical queries. Nothing broke on the process, and people might just
forget about how it used to be in the past. No mental tax, unless you
want to dig history.
The existence of the new attribute serves the same purpose that the
version tag does.
You still have an immutable log, and you've evolved your schema to
better represent the domain. I don't see how those conflict here. The
biggest objection would probably be the "wasted storage" of the old
data.
But changing schema types and versioning them is something else. It
might even be possible to implement, doing rollups of the schema just
like what's done with the rest of the data like you mentioned, but I
just don't like this idea overall, I think it has brittleness written
all over it. Maybe I'm just being grumpy.
About your album ontology: I like it! Coincidence or not, I did 5 years
of music major before dropping out of college, so I'd consider myself a
"music nerd"! But I agree that one needs the database to help them model
the domain in a useful way, and I wouldn't force everybody to have a
particular view of it. Ultimately the database should be a useful tool
to solve a problem.