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

/sync is how you usually receive events. A client usually should call /sync in a loop. This request will block until a new event arrives at the server. This is usually called long polling. Once /sync returns, you will want to persist the new events. Usually you do that in a loop over every room and then loop over each message. You can distinguish the following kinds of messages:

  1. Redactions: When a message gets redacted, a redaction is sent to every client. Clients generally should then remove the content key of the redacted event, so that the event is not displayed to the user anymore. With our event store this is fairly straightforward. Just read the event with the id specified unter the redacts field, strip out the content and write it again. You also want to inform the UI to rerender that event, if it is currently displayed to the user.
  2. "Normal" messages, that should be displayed to the user. Those will need to be added to the events database. As those events should be shown to the user, you will want to add their event_id to the message <-> order databases as well as the event <-> order databases.
  3. "Hidden" events: Some events should not be shown to the user. Those should generally still be added to then events and event <-> order databases, but you will not want to add them to the message <-> order database.
  4. Related events: These can be messages from 2. or 3.. These events may not be displayed or they are, but they also affect the rendering of other events. You will, in addition to handling 2. or 3., you will also want to add those events or rather their event ids to the related database. That way you can render for example reactions or edits. Replies work the other way around. Threads may work both ways, depending on how you want to display them. Don't forget to notify the UI, that the related events changed, so edits can update the message text or new reactions do get added and similar.

Additionally to storing the events, you will also want to update room state, sync token, presence and such. This is out of scope of this document though. Make sure to not accidentally store the same sync response twice, i.e. after reconnecting because of a network issue. You can easily dedup /sync responses by verifying the sync token matches what you currently are expecting.

If your sync response contains a limited field and this is set to true, you will have a gap in your event store. There are multiple ways to handle that: You can throw away all other messages or you store the gap and fill it, when the user views the room/gap. The former is rather easy to implement, the latter is rather complicated, but may lead to nicer results.

Paginating via /messages

Paginating is pretty much the reverse operation of long polling. This is what happens, when a user requests older history than currently stored, or when you need to fill a gap (which can happen in forward and backward direction). When paginating backwards, you can handle events pretty similar to /sync, with a few, small differences. You will not really need to handle redactions. Servers should not return you a redaction for an event you didn't receive yet or at least they should never return you the full event, which was redacted, and you will have to handle the redaction then. Rather you may receive the event with content redacted or you don't receive it at all. Also you want to add the event ids to the top of the timeline of course, when you are paginating backwards instead of to the bottom. Furthermore you may receive related events, where the event it relates to was not received yet. Make sure to handle that correctly.

One thing to remember: You are not allowed to use a /sync token to paginate. While some homeservers, like synapse, tend to allow this, others don't. Always use the prev_batch token from /sync or from /messages.

Filling in missing events

Sometimes you may want to have an additional event available to render another event, but you have neither received it via /sync nor via pagination. In those cases you can use the /<room_id>/event endpoint to fetch specific events. This can be useful to render replies or membership events nicely and similar. Usually you don't know, where those events are positioned, so you only want to add them to the events database, until you actually receive them while syncing or paginating.

Pending messages and local echo

Usually you want to show pending messages to the user, even though they haven't arrived over /sync yet. There are 2 ways to do that: Either you keep them in memory, rendering them after all other messages or you store them in the database as a normal message under their transaction id instead of event id and then replace it, once it arrives over /sync (or you use the event id returned by /send). How to keep track of the pending messages, queue them properly, etc, is left as an exercise to the reader.

Limitations

This is a rather simple implementation of an event store. For this reason it does not handle gappy timelines that well. Relations are also not stored that optimized, you may want to store the actual reactions to a message instead of only related events and iterating. This also limits /sync responses to the disk or database speed. As such this may have more CPU and IO overhead, than an event store, which is mostly kept in RAM. This can be somewhat mitigated via caches, but not completely. You also lose some of the power SQL databases can give you. You will need to implement those higher level features yourself.

Benefits

Closing thoughts

I hope you found this small introduction to Nhekos event store interesting. If you have any questions or ideas, come discuss them in #nheko:matrix.org. Maybe you have ideas on how to improve it or you want to compare or introduce your own event store? I'm interested in how other clients handle their events and store them for rendering to users. Thank you for your attention!

Impressum