I'm currently implementing a new event store for Nheko. This blog post should explain, why this is necessary, what is required of the new event store and how this actually turns out in practice. This post will be a bit more technical in nature, but I hope I can make it easy enough to understand.
What is an event store?
The life of a client dev basically consists of the following parts (simplified):
- Reading the spec.
- Implementing handling for different event types in the client.
- Answering questions from users and looking at their bug reports.
- Cursing at Synapse, the Spec and other Clients and complaining about their brokenness.
I may have left out most of the things you actually do and have blown some parts way out of proportion, but the important take away is: Matrix is a giant distributed event database and most features require you to parse, send, store, relate or otherwise handle events.
You have a few ways to receive events. The most important ones are:
- Regular event updates by long polling
- Paginating backwards in history by calling
- Fetching missing events via
All persistent events can be addressed by their
event_id and for each
pagination token stream there is basically one order the events can be in. By
/sync in a loop, you will receive events usually in the order your
server receives them in. For example consider the flow:
- Your sync is up to date
- Someone sends the message A
- You call
- You send the message B
- You call
If you ignore all the effects of network latency, other rooms, etc, your first sync should contain the message A and the second message should contain the message B, both in the timeline section for that specific room.
A message may be a reply or a reaction, edit or otherwise related to some event.
In some of those cases you may decide to fetch a related event by event id via
If your user scrolls up, they may want to see messages you do not have available
at the moment. To load messages before a certain point, you would call
/messages with the
prev_batch token you got from
/sync. Be careful, while
synapse allows you to use your sync token here, this is not required by the spec
and other servers may not be as lenient! Messages you fetch by paginating
backwards may not neccessarily be ordered by arrival order on the server. They
may be ordered by their logical order you get from the federation DAG, which I
don't want to go into here. It's just something to be aware of (for now).
Now that is all well and good, but you need to do something with those events. While you can render them to the screen and then throw them away, that means your memory usage will grow proportionally to the amount of events you received. You may alleviate that a bit, by throwing away older rendered messages, but in any case you will need to fetch events from the server again, if the client gets restarted.
Alternatively you may want to store (some) events on disk, so that after a
restart you can show some events until
/sync returns with the up to date
state. This is what this blog post is about. How do you store them efficiently
and how do you access those stored/cached events?
Requirements for the event store
Note: We are talking about an event store form the "Timeline", which shows the messages. This post will not go into how you can store the room state for fast and easy access. Usually a key-value store of state events works well enough for that.
- Events need to be easily accessible by their id. If you need a related event, you just want to store the id for the relation, not the full event.
- You need to store the order of events. If you naively sort them by
origin_server_ts, they will not be ordered by arrival time. If you couple that with lazily rendering events from the event store, the events will not be appearing at the bottom of the timeline, if an old server comes online, leading to weird notifications and a timeline, that not reflects
- If you want to have a 1:1 mapping of a visible event to an event in the database, you need to somehow store the order of visible events as well as the order of all events relative to each other.
- If you receive or send an event, that relates to another event, this event
will have a key to which event it relates to (usually called
m.relates_to). The event, that is the target of this relationship, doesn't know about there stalkers (the related events) though, since you received it, before the relations were even sent (usually). On the other hand, in many cases you want to render the event, that is being related to, differently, depending on its related events (think reactions, edits, etc). For that it makes sense to store a relation mapping with all the events relating to a certain
- To paginate further backwards, you need to persist the
prev_batchtoken. While only the most recent token is neccessary, it may be useful to persist all of them, if you ever want to shrink your event store and drop old events.
Overview of Nhekos implementation
This implementation is specific to Nheko. Specifically, Nheko uses lmdb (a key value store/B-Tree database). While the ideas can probably also be mapped to relational databases, it may not be efficient and there may be a better implementation for those databases.
This database is very simple. There is one of those per room and it simply
stores the mapping
event, where the first one is a string and
the second one is the full json of the event as it was received.
These are actually two databases (per room). The order of an event is a simple, 64-bit integer. Since you usually don't receive the first event in a room first, you need to be able to insert events before and after an already stored event (but not in between). This means an unsigned integer should start with half of the maximum, that can be represented. (While that limits the maximum number of messages, that can be stored, it is very unlikely you will ever reach that, without receiving a limited response in between, since you would need to receive many messages per nanosecond.)
You then store a mapping of that
order integer to the
event_id, so that you
can iterate events in order and you also store the reverse mapping, so that you
can easily figure out, where an event is positioned.
Additionally you store next to the
event_id the last batch_token of the
currently handled response, so that you can paginate backwards if needed.
This database is very Nheko-specific. Basically the idea is as follows: You
don't need to render all messages at once. You can just render them, when the
message at a certain position is shown. You could calculate the
event_id mapping on demand from the
event_order store, but this may be
expensive, if you don't want to render reactions, edits and other related events
at the "time" where they arrived, but rather at the location of the event they
relate to. So you need to store an additional order key for "visible" messages
instead of all messages. This is the
message_order database and
order_message is the inverse mapping.
Matrix has the concept of related events. These can be replies, reactions,
redactions, edits, in chat verifications, call events and probably more in the
future. Most of those have the
event_id they relate to in
easily access related events, we will store the related event ids as a value
event_id they relate to as the key.
This makes it very easy to show for example reactions. You just have to iterate over the related events of each event and if they are a reaction, show them in a little bubble under that event. Similarly you could show edits that way, verification history as a single event or even implement basic threading on demand, i.e. have a button that focuses the timeline on all events that are a reply to the current event or where the current event is a reply to (transitively until a certain depth is reached).