IM Systems in Depth

Chapter 40

Community servers

A community has 100,000 members and 50 channels, and most members drop by once or twice a week. The trunk updates a conversation record for every member and pushes to every online device. How much work is one message here?

This chapter is a first draft. The author is still checking it, and its text and numbers may change.

The app adds something new: communities. An outdoor brand opens the “Shanye” community, and 100,000 people join. It has 50 channels: #announcements, #routes, #gear, #second-hand… Each channel is a conversation. Everyone can read its history and post in it, as far as their permissions allow. Discord calls such a community a “server”, hence this chapter’s title; below it is always “community”, so as not to confuse it with a machine.

Ana joins too. She opens it twice a week and has only ever looked at 3 channels. Most of the other 100,000 are like her: they joined and rarely come. On a busy evening the whole community sends 10 messages a second.

This chapter starts from v3 (chapter 32) and asks: when the trunk’s design meets a community like this, what stays and what changes? Chapters 11, 12 and 13 all said “groups of tens of thousands do not go this way”. This chapter is that way.

1. How a community differs from a group

The hiking group (trunk) Shanye community
Members 500 100,000
Conversations one group, one conversation one community, 50 channels
Who is looking many people look every day of those online, most are looking elsewhere
Who sees what members see everything by role: some channels only admins can see, in some only long-time members can post
History for a newcomer the last 100 messages before joining (chapter 12) all of a channel’s history, given permission

The last two rows are new needs. The first three are scale. Scale first.

2. The trunk’s design: how much work one message is

With 100,000 members and the book’s assumption that 10% are online at peak, 10,000 are online. Discord has said that in large servers about 90% of user-server connections are “passive”: the person is online but has not clicked into that server (Discord, 2023). At that ratio about 1,000 are looking, 9,000 are online elsewhere, and 90,000 are offline.

When the v3 trunk receives one message in the community, it does this:

  • Update conversation records (chapter 11): write the latest seq on every member’s row and bump their record versionrecord version记录版本A per-person number that goes up with each change to their conversation records; it is taken under a lock on that person’s users row, so version order is commit order. The phone keeps the version it has and asks “what changed after this” on return; a group it was added to, or a chat with new messages, shows up here.See the glossary. 100,000 updates for one message, each a small transaction writing two rows (the member’s version and the record). At 10 a second that is 1,000,000 updates, 2,000,000 rows a second: at least 100 storage nodes (one takes 20,000 rows a second), and 10.8 times all of v3’s conversation-record writes (about 185,000 rows a second).
  • Look up online routes (chapter 20): one lookup per member to find their gateway, 1,000,000 a second, 10.8 times all of v3’s route lookups.
  • Push to every online device (chapter 16): 10,000 pushes per message (counting one device per person; at the book’s 1.5 it would be more), 100,000 a second. That is two gateways’ entire push budget (a gateway pushes 50,000 a second, chapter 22), and 72% of all of v3’s pushes.
  • Notify the offline (chapter 17): at most one per conversation per minute. But a community never goes quiet: every busy channel sends one a minute to each of 90,000 offline members, 1,500 a second per channel.
  • Read positions (chapter 14): one per member per channel, 5,000,000 rows.
  • The member list (chapter 13): in full, 100,000 × 40 bytes = 4 MB. With 1,000 joins and leaves a day, the member version moves every 86 seconds on average, so a phone has something to fetch almost every time it opens.
  • Joins and leaves take a seq (chapter 12): 1,000 “so-and-so joined” messages a day, each sent to 100,000 people.

This is not a dumb design built to fail: it is the trunk, and in a 500-member group every line above is affordable. What breaks is the size. Discord described the shape: everyone in a server says something, and everything goes to everyone, so the work grows with the square of the size. If 1,000 people online each say one thing, that is 1,000,000 deliveries; with 10,000, 100,000,000; with 100,000, 10,000,000,000.

Some things do not break. Note them first:

  • One seq per channel (chapter 5) and one message server owning each channel (chapter 28): 10 a second is far from the 5,000 one message server handles (chapter 28’s assumption).
  • The message log (chapter 29) and the gateways (chapters 20–24): one message is still one message.
  • Messages stored once (chapters 6, 10): this was read fan-outread fan-out读扩散Keep one copy in the conversation’s timeline, and each reader fetches it from there. Few writes, more reads; suits big groups. All of v1’s and v2’s messages are kept this way (chapters 6, 10); it needs the server to build the chat list and devices to sync it.See the glossary already, stored per channel.

3. The decision: store once, push to whoever is looking

Community channels no longer write anything per member. A message does three things:

  1. It is stored once, and the channel’s latest seq moves (one number in the cache).
  2. It is pushed to the devices looking at the community. A device that opens the community subscribes: it tells the server “I am looking at Shanye”, and unsubscribes when it switches away or goes to the background. This is chapter 21’s presence rule again: tell only those who are looking. The subscriber list, about 1,000 devices, lives in memory on the server that owns the community. Pushing follows the list, with no route lookup for each of 100,000 members: 10,000 pushes a second, 90% fewer than the trunk and 20% of one gateway.
  3. Online devices that are not looking get at most one frame a minute saying “Shanye has news”, enough to light a dot on the community’s icon. 9,000 devices, 150 frames a second.

So how does someone who was not looking learn which channels have news? They fetch it when they come in. Ana opens Shanye and her phone asks once for the latest seq of all 50 channels: 50 × 12 bytes = 600 bytes. That is chapter 6’s latest-seq sweeplatest-seq sweep最新 seq 一览On return the phone asks for the latest seq of all its conversations at once; the server reads them from a cache in one batch, one key per conversation. Any conversation whose seq is above the phone’s has new messages. Its reads grow with the number of conversations, not with the number of new messages.See the glossary, over this one community only. If every online member opens the community once an hour, that is about 2.8 visits a second, 50 numbers each: 139 cache reads a second.

“Which communities Ana has joined” is still a conversation record (chapters 10, 11): one row per person per community, changed when she joins, leaves or changes a setting, never when a message arrives. A new phone copies these records over, as before.

Notifications change too: by default a community sends a system push only when someone @s me. Other messages send none. An @ writes one row, for the person mentioned, not one for every member.

Telegram’s supergroups follow the same idea: each has its own event sequence; clients poll for updates only for the supergroups the user is currently viewing, at most 10 at a time, and stop when the user closes them; the server may send fewer updates, or none, for some of them (updates).

4. Unread only for channels a member opened

Chapter 14 keeps one read position per person per conversation. In the community that is 100,000 × 50 = 5,000,000 rows, most of which will never move.

Instead, the row is created on the first read. Only when Ana first opens #routes does she get a row (member, channel, read position, @ count). If members have opened 3 channels on average, that is 300,000 rows, 6% of 5,000,000; at about 24 bytes a row, 7.2 MB instead of 120 MB.

  • A channel she has opened: on entering the community she gets its latest seq; if it is above her read position, the channel is shown in bold; the @ count is shown on its own.
  • A channel she has never opened: there is no row. If the channel’s latest message is newer than the time she joined the community, it is bold, with no number.

Why no exact unread count any more? Chapter 14’s exact count relies on the server writing “the count so far” into every member’s conversation record for every message. The community does not write those, so what is left is “something new” and “how many @s”. And with 300 unread in a channel, those two are all Ana wants to know.

Read reports work as in chapter 14: they only move up, at most once a second. Only people looking send them: at most 1,000 writes a second, 5% of one storage.

@everyone was 500 rows in the trunk; here it would be 100,000. Instead, the channel keeps one row: “message N @’d everyone”. When Ana’s sweep finds that message newer than her read position, her @ count goes up by one. Whether someone may use @everyone at all is itself a permission (section 6).

5. Members loaded on demand

In chapter 13 the phone keeps the whole member list, with a version. In the community the whole list is 4 MB and never stops changing.

Instead, fetch only what the screen needs:

  • The member list in the sidebar: the current screen, 100 rows × 40 bytes = 4 KB; scroll down, fetch the next. Presence is subscribed only for that screen (chapter 21, unchanged).
  • Typing @: a prefix search returning at most 100, about 4 KB.
  • Names on messages: only the senders of the page of messages on screen. Matrix’s lazy loading of members works this way (mentioned in chapter 13).

Discord’s gateway API for bots has the same shape: above a threshold (large_threshold, 50 to 250 members) it stops sending offline members on connect; members are then requested by prefix, at most 100, or in chunks of up to 1,000 (Gateway Events).

Joining or leaving the community is no longer a system message to everyone; it only changes the member table.

6. Permissions per channel: roles

In the trunk, a member can see and post (chapter 12). A community needs much finer rules: only admins post in #announcements; only long-time members can see #old-hands.

A yes-or-no per person per channel would be 5,000,000 switches, and adding one channel would write 100,000 rows. Communities use roles instead:

  1. The community defines a few roles (admin, moderator, long-time member…), each with a set of permissions, and each member has a few roles.
  2. Each channel can allow or deny a few extra things for a role or for one person. These are called overwrites.
  3. What a person may do in a channel is computed: start from everyone’s permissions, add those of each of their roles; then, on the channel, apply in turn the denies and allows for everyone, for their roles, and for them personally.

Discord’s developer docs give exactly this order. Permissions are a set of bits, combined with bitwise OR and AND, and the administrator permission skips every channel overwrite (Permissions).

With 20 roles and 50 channels there are at most 1,000 overwrites, plus a few for single people. Making a channel private changes one overwrite, not 100,000 rows.

Permissions are used in three places:

  • Sending: chapter 12 checks “is she a member?” inside the transaction that takes the seq; here it checks “may she post in this channel?”.
  • Pushing: before pushing to a subscriber, check that they may see the channel. 10,000 checks a second, a few bit operations each.
  • Reading history: chapter 12 works out the visible range from the moment of joining; in a community it is permission instead: whoever can see the channel and has the read-history permission sees all of it.

7. The trunk’s decisions: keep, change, drop

Layer The trunk’s decision Community
Connection gateways, online routes, heartbeats, admission, accounts (20–25) keep
Message ACK, dedup, seq per conversation, conversation owners, message log (3–5, 28, 29) keep, with channels as conversations
Dispatch update every member’s conversation record for every message (11) drop: records only say which communities you joined
Dispatch push to every member’s every online device (16) change: only to subscribers; at most one frame a minute for the rest
Dispatch offline: one notification per conversation per minute (17) change: by default only for @ me
Dispatch presence only for those looking (21) keep, subscribed for one screen
Storage messages stored once (6, 10) keep
Storage one read position per person per conversation, exact unread count (14) change: created on first read; bold plus @ count
Storage in groups, tap a message to count who read it (15) drop
Business joins and leaves take a seq; visible history from the moment of joining (12) change: only the member table; visibility by permission
Business the whole member list on the phone, with a version (13) change: by screen, by search, by sender
Business recall and edit (18) keep: moderators delete messages all the time
Business — add: roles and channel overwrites
Client local database, one SDK (7, 30) keep, caching only opened channels

8. What it costs

  • Those not looking learn late. The dot on the community’s icon can be a minute late; which channel has news is known only after clicking in.
  • Unread is coarser. Bold and an @ count, no exact number. For never-opened channels, “newer than when you joined” compares times, but a message’s time is taken when it is written, not when it is stored (the hole from chapter 11’s “other answers”): Ana joins at 9:00:00, a message takes its time at 8:59:59 and is stored at 9:00:01, so it counts as before she joined and the channel is not bold. For a dot it does not matter; the next message lights it.
  • Reads that arrive together. An announcement goes out and thousands open #announcements at once, all reading the same page. Identical reads must be merged into one. Discord’s data services do this: “If multiple users are requesting the same row at the same time, we’ll only query the database once” (Discord, 2023).
  • Two paths. Below a few thousand members keep the trunk, with exact unread counts and the whole member list; only above that threshold use this chapter. Twice the code and tests, and a group that grows must be able to switch over. Telegram’s public API has two kinds of group too: a basic group holds at most 200 members, a supergroup up to 200,000, and a group that grows has to be upgraded across (chapter 10, Channels, supergroups and groups).
  • Permission changes must take effect at once. When a channel goes private, subscribers without permission must stop receiving pushes immediately, and their phones should drop its history.
  • The subscriber list is in one server’s memory. A community with a million people online at once does not fit on one, and must be split again (the relays in the next section).

9. Other answers

  • How Discord evolved. Early on, each server was one process that fanned out every event to every connected session; publishing an event in a large server took 0.9 to 2.1 seconds (Discord, 2017). Later, connections that had not clicked in were kept in a separate list, making fan-out 90% cheaper; then a layer of relays went between the server process and the connections, each fanning out with permission checks to up to 15,000 sessions (Discord, 2023).
  • Discord’s read states: one per user per channel, billions of them (Discord, 2020). Messages are partitioned by channel and time bucket (Discord, 2017); the channel object carries the ID of its last message (last_message_id), which plays the role of this chapter’s channel latest seq (Channel).
  • Slow mode: when a community talks too fast, each person may post only every few seconds. Discord’s channels have rate_limit_per_user, 0 to 21,600 seconds (Channel); it is chapter 34’s per-device send limit, set per person and per channel.

10. The decision in this chapter

In a community most people are not looking, so pushing to whoever is looking is enough. The live room in the next chapter is the opposite: 1,000,000 people in one room, and every one of them is watching.

Comments

Comments live in GitHub Discussions and need a GitHub account.