Part 5 of 8 · 3 min read
Messages
A chat history key: one conversation together, ordered by time.
Think of a postbox for each conversation. A reader who opens a conversation wants the latest messages in order and nothing from other conversations.
The book "System Design Interview" has a chat design with this problem. It notes the facts: chat data is enormous (it cites a study that Facebook Messenger and WhatsApp process 60 billion messages a day); only recent chats are read often; some features need random access, such as search, mentions or jumping to a message; and the read-to-write ratio is about 1 to 1 for one-to-one chat. It recommends a key-value store for chat history, since key-value stores scale horizontally, give low latency, and handle the long tail of old data better than relational databases whose large indexes make random access expensive. Facebook Messenger uses HBase and Discord uses Cassandra.
Its data model:
- One-to-one chat: the primary key is
message_id, which decides the order of messages.created_atis not used for order because two messages can be created at the same time. - Group chat: a composite primary key
(channel_id, message_id). The book states thatchannel_idis the partition key, because all queries in a group chat operate within one channel. - Message id: must be unique and sortable by time, so that new rows have higher ids than old ones. Auto-increment is not available in most NoSQL stores, so another way (a time-based unique id generator) is needed.
Partition key and clustering (sort) key
In a compound key, the partition key decides the shard, and the sort key orders records within the shard.
Example: (channel_id, message_id): channel_id picks the shard, and message_id sorts the messages inside it.
Why this is a good key:
- Locality. "The latest 50 messages of channel 9" goes to one shard and reads a range of 50 sorted rows.
- Order. Messages of a channel are in one place in time order. That also gives a consistent prefix (module 2): a reply cannot be seen before the question in the same channel.
- Even spread. Many channels, so hashed channel ids spread evenly.
The weak points:
- Giant channels. A channel with 1,000,000 members and 500 messages a second is a hot key. Remedies: split a channel's storage by time bucket,
(channel_id, bucket)with the bucket being a day or a week, so that a channel's data spreads over many shards over time and each shard holds a bounded amount. Reading the latest messages then reads the newest bucket (and the previous one if needed). - One-to-one chats. The conversation id is derived from the two users, for example the smaller user id then the larger, so both participants use the same key.
- "All messages from user 5 in any channel." Not local. Use a secondary index (module 5) or a separate store keyed by user.
A worked example. 10 million channels, 40 messages per channel per day on average, 300 bytes per message. Daily data: 10,000,000 × 40 × 300 = 120,000,000,000 bytes = 120 GB per day, 43.8 TB a year. A shard handles 2 TB, so about 22 shards a year, rising. With the bucket (channel_id, week), a channel's year of data covers up to 52 buckets across shards, and no single partition grows without bound. Without the bucket, a very active channel with 500 messages per second produces 500 × 86,400 = 43,200,000 messages a day, or about 13 GB a day at 300 bytes. All of it piles up on one shard, which fills 2 TB in about 150 days.
Check yourself:
- Why is channel_id the partition key for group chat, and message_id the sort key?
- How does a time bucket help a very active channel?