Somewhat contrived schema designing for a new chat system

[This is post 5 about designing a new chat system. Have a look at the first post in the series for more context!]

This post follows on from the previous one in the series¹, wherein I had a shot at designing / specifying what state – persistent information, shared amongst all servers in a federated system – in group chats should look like. To summarize, we ended up with the group chat state containing three important things:

• a set of roles, which are a way of grouping together capabilities available to users with said roles
  • Remember, capabilities are simple keywords like speak or change-topic that represent actions users can take
• a list of memberships (users in the chat), together with the role for each chat member
• non-user-related state, like the chatroom topic, which sort of follows a key-value store
  • We figured out that allowing arbitrary stuff to be stored in a room’s state was a bad idea, so this just contains…some random fields we’ll specify more formally later².

In this post, we’ll look into how this state will be represented in server databases, and spec out a database schema for our server implementations to use³.

Unpacking our group chat state object

We could just store the group chat state as a big JSON blob in the database (indeed, if we were using something like MongoDB, that would be commonplace). However, this probably isn’t a good idea – for a number of reasons:

• we’d have to retrieve the whole thing every time we wanted to access information about it, which is suboptimal performance-wise
• things in the blob could quietly become inconsistent with the rest of the database if we didn’t check it all the time
• the database wouldn’t be able to enforce any schemas; we’d have to do that in our application code
• unless we (ab)use something like PostgreSQL’s native JSON support, our group chat state would be completely opaque from the database’s point of view – meaning it’d be hard to draw links between things in there (e.g. user IDs) and the rest of the database

These concerns are similar to the concerns third-normal form (3NF), a way of structuring database schemas from 1971, hopes to address. Under 3NF, you store your data in a set of database tables representing various objects, with each table having a primary key (an identifier or set of identifiers uniquely identifying that object). 3NF then states that other information in each table must only tell you something about the primary key, and nothing else; they aren’t allowed to depend on anything other than the value of the primary key.

As a more concrete example, let’s say we have a User table representing a user of our chat system, where the primary key is a combination of a username and the user’s home server. If I wanted to add a column describing what channels they’re in, for example, that would be fine – but if I wanted to also add the most recent messages for each channel, say (let’s imagine you’re designing a UI like WhatsApp’s, with a homescreen that shows this information), that wouldn’t be valid under 3NF, because the most recent messages are a property of the channel, not the user. We could end up having two users in the same channel, and forget to keep this ‘recent messages sent’ property consistent, which would lead to confusion!

So, using 3NF seems like a pretty good idea – and that’s exactly what we’re going to do! Our group chat state object doesn’t fit 3NF as one large blob, so we’re going to need to decompose it into a set of database tables that store the same information.

Let’s do some schema designing!

groupchats: our starting point

Of course, we need some object to represent a group chat. Since group chats are going to be shared across different servers, we have to choose some identifier that’s always going to be unique – we can’t just give them textual names, otherwise they’d be a possibility of them clashing. Instead, we’ll use a universally unique identifier (UUID) – it does what it says on the tin!

Our set of group chat state (for now) is in the list below. I’ve also put 🚫 next to things we can’t put in the groupchats table directly due to 3NF, and explained why.

• topic / subject
  • This is purely a property of the group chat itself, and it doesn’t depend on anything else.
• list of users 🚫
  • This one technically could be a property of the group chat, but making it one isn’t a great idea.
  • Firstly, that’d mean we’d have to use an array, which is generally frowned upon; it makes it harder to do things like database table JOINs when the users are stuck in an array attribute.
  • Also, we probably want to associate some information with a user’s membership, like their role. Doing that in the groupchats table would be a big 3NF violation.
• list of defined roles 🚫
  • Roles have capabilities associated with them, so they should be their own thing.
  • Said otherwise, our primary key is the channel’s UUID, not (channel UUID, role), so storing capabilities (which depend on those two things) would be a 3NF violation.
• mapping of users to what roles they have 🚫
  • Similarly to the last item, this mapping introduces a 3NF violation.
  • We’ll probably end up doing this one in a separate object, as discussed above.
• list of servers involved in this group chat, as well as whether they’re sponsoring or not 🚫
  • Ditto, really.
• current state version
  • We need to keep track of what state version we’re on (remember, the state version is a monotonically incrementing integer), for the purposes of our consensus algorithm.

So, now that that’s all clear, we’re left with group chat UUID, subject, and current state version. Here’s the SQL DDL:

CREATE TABLE groupchats (
    uuid UUID PRIMARY KEY,
    state_ver INT NOT NULL,
    subject VARCHAR -- can be null, if a group chat is unnamed.
);

(We’ll include the DDL for each table in our schema.)

groupchat_roles and groupchat_role_capabilities: storing group chat role information

Before we can actually express user memberships, we need something to store group chat role information; what roles exist, and what capabilities are associated with them. Behold:

CREATE TABLE groupchat_roles (
    role_id SERIAL PRIMARY KEY,
    groupchat_uuid UUID NOT NULL REFERENCES groupchats,
    role_name VARCHAR NOT NULL,
    UNIQUE(group chat_uuid, role_name)
);

CREATE TABLE groupchat_role_capabilities (
    role_id INT NOT NULL REFERENCES groupchat_roles,
    capability VARCHAR NOT NULL,
    UNIQUE(role_id, capability)
);

A row in the groupchat_roles table represents a role name in a group chat. Role names are unique per group chat, so the 2-tuple (groupchat_uuid, role_name) is unique; the only bit of information associated with a role is a list of capabilities, but we aren’t going to use arrays (q.v.), so the separate groupchat_role_capabilities table represents capabilities granted to users with a given role.

We’ve given roles an internal integer ID (role_id) just to make the primary key less annoying; the ‘real’ primary key should be (groupchat_uuid, role_name), but that’d be a real pain to refer to in the groupchat_role_capabilities table (we’d have to store both the UUID and the role name! So much wasted space!⁴), so we just use an integer instead.

groupchat_memberships: associating users with group chats

Now that we’ve got a group chat table, and a way of expressing user roles, we want a way to express the set of users that are in said group chats, along with the role they have. This is very simple – we have a (groupchat, user) primary key, and a role foreign key.

CREATE TABLE groupchat_memberships (
    groupchat_uuid UUID NOT NULL REFERENCES groupchats,
    user_id INT NOT NULL REFERENCES users,
    role_id INT NOT NULL REFERENCES groupchat_roles,
    PRIMARY KEY(groupchat_uuid, user_id)
);

I’m deliberately not going to mention what’s in the users table yet; we’re going to discuss that in another blog post.

groupchat_sponsoring_servers: associating sponsoring servers with group chats

We also need to associate servers with groups somehow. This is done for us partially, in that users reside on servers, and so naturally the set of servers associated with a given group chat are just the servers on which the members reside – but that doesn’t take into account the fact that some of these servers might be sponsoring servers for the purposes of federation.

Enter the groupchat_sponsoring_servers table:

CREATE TABLE groupchat_sponsoring_servers (
    groupchat_uuid UUID NOT NULL REFERENCES groupchats,
    server_id INT NOT NULL REFERENCES servers,
    PRIMARY KEY(groupchat_uuid, server_id)
)

Again, there’s this mysterious servers table we haven’t got to.

Next steps

We’ve now established what principles we’re going to use to design our schema (3NF), and we’ve got 5 lovely tables that express all the group chat state stuff we’ve been jabbering on about for the last two blog posts in proper SQL DDL that we could actually use!

We now need to tackle the other two important parts of our schema; we’ve done group chats, but messages and users are yet to be specified. We’ll need to discuss a few important points about how we design our protocol to fit both of these, as there’s more to it than you might think! (For example, a user might seem simple – just someone on a server somewhere, right? – but what about them having a profile picture, or a bit of ‘status’ text describing what they’re up to, or things like that?)

All of that will come in the next blog post in the series, coming (hopefully quite) soon to a website near you!

Hey, those deadlines really are quite scary. Wouldn’t it be lovely if we had a roadmap, with nice intermediate dates on it, so we could actually plan stuff?