Nhekos Event Store V2

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):

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:

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 calling /sync in a loop, you will receive events usually in the order your server receives them in. For example consider the flow:

  1. Your sync is up to date
  2. Someone sends the message A
  3. You call /sync
  4. You send the message B
  5. You call /sync

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 the /event endpoint.

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.

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.

Database events

This database is very simple. There is one of those per room and it simply stores the mapping event_id -> event, where the first one is a string and the second one is the full json of the event as it was received.

Databases event_order and order_event

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.

Databases message_order and order_message

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 index to 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.

Database related

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 m.relates_to. To easily access related events, we will store the related event ids as a value under the 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).

Handling /sync