In my experience, there are two kinds of Dolt users:

• Users who have an existing database use case and want to add version control capabilities.
• Users who are interested in decentralized platforms and have some novel use case that requires a decentralized database.

Both groups of users are important to us. Dolt is the first version-controlled SQL database, and that opens a lot of very cool doors, both for adding value to conventional database needs and for enabling entirely new systems. Sometimes our messaging focuses on one or the other, but both groups matter for Dolt’s future.

Last week, Tim talked about when to NOT use Dolt as your database. A lot of the examples he gives are about the logistical limitations of adding Dolt to an existing project or organization. This week, I want to take a look at the other side of that conversation: when is Dolt the right tool to build something entirely new?

That’s a tougher question to answer because it’s asking about new frontiers that aren’t totally understood yet. But it’s an important question that people ask us semi-regularly since we often get users who are trying to tackle some previously unsolved problem and want to know whether Dolt is the missing piece of the puzzle.

Usually we encourage people to join our Discord so we can chat about whether Dolt is the right tool for the job. But how can we develop a good intuition for when Dolt adds value to a system, especially if you’re trying to make something novel?

For instance, last month thrudhame on GitHub asked us if we thought there was value in using Dolt as the backend for a Matrix homeserver. They didn’t have a specific proposal for how this would help but a intuition that it might. This got my attention, because I’d explored similar ideas before. I wanted to help them pull on this thread. Even if it turned out that Dolt wasn’t the right tool here, it would be a good exercise in honing our intuition.

First, some context. Matrix is a federated chat platform, where anyone can self-host a server called a homeserver. Every account belongs to a homeserver, and users from different homeservers can still message each other and even participate in large group chats. This is possible because each homeserver keeps its own database of messages, and the messages for a group chat get replicated across every homeserver that has a user in the chat.

For anyone using Dolt, this immediately sounds familiar. Dolt is a replicated database that allows every node to store its own copy of the tables. These replicas need not be identical: just like Git, each version can be its own branch, and version control operations like merging and rebasing can be used to apply changes from one branch onto another.

At a first glance, this seems like a perfect match. Matrix requires efficiently replicating and reconciling state across nodes, and Dolt’s version control capabilities do exactly that. Thus, intuition suggests that building a Matrix server on top of Dolt would provide an obvious benefit.

In addition, both Dolt and Matrix have similarities in their data model: both Dolt tables and Matrix rooms are built out of content-addressed objects that reference each other by their hash, and the state of the system can be represented by one or more hashes that form the root of a Directed Acyclic Graph. This led thrudhame to wonder if their data models might even be interoperable in some sense.

Enter the Matrix#

Our intuitions told us there might be something there, but do these intuitions hold? The main claim has two parts:

• Matrix has a need that is not currently being met or could be improved.
• Dolt meets that need, or is an improvement on existing solutions.

On one hand, Matrix exists. It works. There are multiple homeserver implementations in use. That might suggest that there’s no problem here for Dolt to solve. But one thing to keep in mind is that the purpose of Databases isn’t to make the impossible possible but to improve the efficiency of data operations. You don’t need a database to filter data, but you need a database in order to scale. A novel use case for Dolt might be something that is theoretically possible without it but would be impractical due to time complexity. It’s possible that Matrix federation could have scaling issues that Dolt could help with. But we can’t prove that one way or another without understanding exactly how Matrix federation works.

This is the federation API for the current version of Matrix. It describes the behavior that Matrix homeservers need to support in order to peer with each other. There’s a lot to absorb there, but the most important parts are the sections on Persistent Data Units and Retrieving Events.

PDUs are the data model used to describe events, the most important building block of Matrix, and are described in full here. Everything that happens in Matrix is an event, which includes stuff like:

• creating a room
• sending a message in a room
• changing a user’s permissions in a room
• and so on

Every event has a source, which is the homeserver that originally created it. Because Matrix is decentralized, there’s no total ordering on events: two servers might both send each other an event around the same time and disagree about which happened first. But events can reference the content hash of previous events, which creates a partial ordering.

If there’s a way for Matrix to benefit from Dolt, it would most likely be because Dolt’s data model enables something in the above documents to be computed more efficiently.

What Does Dolt Bring to the Table#

Dolt’s big novel idea is how it uses Prolly Trees to store tables. Feel free to read some of our other blog posts if you want a deeper dive, but the important part is that Prolly Trees provide a really efficient solution to something called the set reconciliation problem: if you have two different ordered sets or maps, you can represent them as Prolly Trees in a way that makes them very efficient to compare to each other.

Prolly Trees have other valuable properties too, such as structural sharing (storing multiple Prolly Trees automatically deduplicates the parts that are the same) and history independence (two sets with the same elements have the same representation, even of those two sets were created on different machines).

Most of Dolt’s advances are due to creative use of this data structure. It’s what makes version control fast and space-efficient. Dolt excels in systems that are able to take advantage of this. This means that there are two main cases where Dolt provides value:

1. You specifically want version control for your application, because version control is an explicit feature that you’re providing.

2. You want to be able to efficiently diff two versions of the database that may have different histories.

A decentralized chat application like Matrix doesn’t really need the first case, but it absolutely needs the second case. Being able to quickly reconcile changes between two nodes is an absolute requirement for something like Matrix to be viable. And it sounds like Dolt can probably help do this.

The question is, can Dolt do this better than how Matrix already does it? Does Matrix in its current state have scaling issues that Dolt would solve? To answer that we need to dive a bit deeper into how Matrix maintains its state.

Can Dolt Improve Matrix’s Message Retrieval?#

When a homeserver joins a room, it needs to request all messages pertaining to that room. If a homeserver recovers from an offline period, it needs to request all new messages pertaining to that room, ideally without having to re-process messages it already has. Similarly, a server that receives a request for updates from a peer wants to be able to send only the new messages and needs to efficiently compute which messages are new. At first this sounds exactly like the set reconciliation problem mentioned above, with Dolt is really good at. And indeed, if a Matrix server were to store every event in order in a Dolt database table, then Dolt’s DOLT_DIFF and DOLT_MERGE functions would allow for the state of the two homeservers to be quickly compared, and missing events can be quickly identified and sent.

But it’s important to remember that events in Matrix aren’t simply an ordered set of unrelated records: they’re a partially ordered set of records that reference each other and form a DAG. And that turns out to be really important, because it both imposes limitations and creates opportunities.

Suppose a homeserver knows an event ID and wants to make sure that they have that event and every event referenced by it, directly or indirectly. They can accomplish this pretty easily:

• Add the event ID to a “todo” queue
• While the “todo” queue is empty:
  • Pop an event_id from the “todo” queue
  • Request event event_id from the other homeservers in the room
  • Scan the received event for any references to other events, and add each of those referenced events to the “todo” queue unless they already have the referenced event.

Using this process, if a server can get the ID of the most recent event in a room, they can request every missing event without ever having to process an event they already have.

This leaves out some details, such as the fact that there may be more than one “most recent event” that don’t reference each other or that the homeserver may already have one event in their database but may be missing events that come before it. The actual approach is slightly more complicated and requires keeping track of both “roots” (events that have no other event referencing them) and “holes” (event IDs that the server has seen references to but does not have). But as long as the size of both of those sets is reasonably constrained, this approach still works. And without getting too deep into the weeds here, it suffices to say that Matrix in practice does limit both of these, ensuring that for each room, the number of roots does not exceed the number of homeservers in the room.

So while Dolt branches could be used to fetch updates for a given room, Matrix doesn’t need Dolt to do this.

There’s another problem trying to use Dolt for this to, which is that in order to solve the set reconciliation problem, Dolt requires that the items being compared have a total order, which Matrix messages don’t. Matrix does define a couple a of ways to order messages in a room (see “Reverse topological power ordering” and “Mainline ordering” here), but it’s not obbious that either of these orderings is guaranteed to be stable. We could always define an arbitrary ordering that is stable, like ordering events by their hash, but this would cause new events to be uniformly distributed in the ordering, but Dolt’s performs best when changes to the data are clustered, with uniform distribution resulting in the worst case behavior.

In the end, I concluded that using Dolt as a backend for Matrix wouldn’t unlock any capabilities that Matrix wasn’t already good at. To hone our intuition further, let’s look at a very similar platform where we can make a much stronger case.

Nostr#

Nostr is a message protocol with a very interesting approach to peering: it doesn’t.

More specifically, the protocol only specifies how clients exchange messages with servers. Peering between servers is deliberately unspecified: servers are allowed to share messages with each other but must figure out how to do so on their own.

When I first saw this, it baffled me. It felt like cutting off your legs before the race had even begun. But the more I thought about it, the more I came around to it.

See, peering is hard. It’s probably the hardest problem in decentralized platform design, along with federated search… and federated search is mainly hard because peering is hard. So Nostr decided that instead of making promises it couldn’t keep, it would simply punt on the problem and see what could be accomplished without any peering guarantees.

The end result is that Nostr looks a lot like Git: the network topology is a spoke-and-hub model where clients connect to a small number of known servers, sometimes a single server. Content is replicated across multiple servers only when a client explicitly pushes it there. Clients can manually replicate that they aren’t the author of, like a Git user cloning from GitHub and pushing a fork to GitLab.

That’s how Dolt works too, and it works just fine. If Dolt users want replication, they can push their database to DoltHub or host their own DoltLab. So once I started thinking about Nostr as “Git for messaging”, the more I was convinced that their lack of peering made sense.

Then it got me wondering: Can Dolt be used to make Nostr’s intractable peering problem tractable?

Nostr is very similar to Matrix, in that all messages are content-addressed and can reference other messages by their hash. But there are also key differences, stemming from the fact that Nostr is less of a chatroom platform and more of a public blogging platform:

• Messages on Nostr aren’t organized into rooms like Matrix, and thus can’t make the same guarentees about the shape of the DAG.
• While Matrix rooms may be access controlled, messages on Nostr are typically public and can be freely shared across relays.
• Nostr messages are often tagged, and relays are expected to index messages by tags and support tag filtering and sorting.

This means there’s a common operation on Nostr that simply doesn’t exist on Matrix. A Nostr user might connect to a relay and request all messages by a certain author, or request all messages with a certain tag newer than a certain timestamp. And the Nostr relay can provide that, because it uses a database with indexes.

Now suppose the user connects to a second relay and runs the same query, but they only want to download messages that they don’t already have. Or suppose two Nostr relays want to peer with each other, exchanging messages with each other so that each server has a record of every message seen by either server. This requires efficiently identifying which messages are on one node but not the other, which is the exact problem that Dolt solves. And the use of indexes imposes a stable ordering on messages too.

If a Nostr relay used Dolt as the backing database, it would become possible for it to efficiently peer with other such relays. Clients could theoretically fetch indexes from the relay and efficiently compare to their own local index, identifying which messages already exist on both machines and which don’t.

Conclusion#

While exploring this, I kept going back and forth on whether or not Dolt would actually provide value in either of these examples, which shows how hard it is to reason about this. And given how similar the platforms are, I was expecting to come to same conclusion for both. So I was shocked that two platforms that appear very similar in their design actually end up having completely different implications for Dolt.

The original question suggested that Dolt might be a good fit with Matrix or Nostr because they all use content-addressed records arranged in a DAG, aka a Merkle Tree. Given this, I was surprised that in the end, Dolt’s potential value-add actually had nothing to do with the fact that Matrix and Nostr use Merkle Trees. Trying to leverage that didn’t actually actually help us.

I’m no longer convinced that using Dolt would unlock new capabilities for Matrix. But I’m more convinced that ever that using Dolt would unlock new capabilities for Nostr. Maybe at some point someone will build a Dolt-powered Nostr homeserver and we can see. It’s always really exciting to see people build cool new things with emerging technology.

That’s it for now. As always, if you have thoughts about databases or decentralized tech, if you think I’ve overlooked something or have your own two cents to add, or if you just want to hang out and chat, stop by our Discord and say hi! We’re always looking for people who are as enthusiastic about this as we are.