Designing a Space‑Efficient Read/Unread Store for Large Group Chats

A friend discussed a recent interview question about storing read/unread details for group messages in enterprise IM apps (e.g., WeChat Work, DingTalk). Each message has a unique messageid and each user a unique userid. The naive solution stores two lists of IDs per message, which quickly becomes memory‑intensive.

For each messageid , keep current readids and unreadids . When a member reads the message, move their userid from unreadids to readids . The client then shows the counts of read and unread users.

This approach is too simplistic for an interview; a more efficient design is needed.

Analyzing memory usage: each read/unread flag is 8 bytes per member. In a 200‑person active group, each message consumes 1 600 bytes. With 1 000 messages per day, that’s 1.6 MB per day per group, which is unacceptable for mobile clients and costly for servers.

Since read/unread is a binary flag, a bitmap can represent it. The design introduces a mapping from userid to an auto‑incremented mapid:

struct UserInfo {
    uint64_t userid;
    uint32_t mapid;
};

struct GroupMetaInfo {
    vector<UserInfo> members;
    string name;
    uint32_t maxid;
    // other info
};

With this mapping, a message’s read status can be stored as: { uint32_t maxid, uint8_t readbit[] } For a group of five members, the storage becomes {5, readbit[0]=0000 0000} (5 bytes). When member D reads, it updates to {5, readbit[0]=0000 1000}. When all four non‑sender members have read, it becomes {5, readbit[0]=0001 1110}.

Handling member exits requires additional considerations. Exited members should be marked as deleted rather than physically removed, preserving their mapid for possible re‑entry. To track whether a member has left at the time a message is sent, a second bitmap ( quitbit) is added.

The final schema stores per‑message details as { maxid, readbit[], quitbit[] }, with the group maintaining the userid ↔ mapid mapping and deletion flags.

Benefits of the new scheme:

Adding the auto‑increment mapid field incurs negligible cost.

Read/unread storage shrinks from 8 bytes per user to roughly 2 bits per user, reducing a 200‑member group’s per‑message overhead from 1 600 bytes to about 54 bytes (over 95% savings).

If maxid grows to millions, the bitmap size could become large; in such extreme cases, the system can fall back to the original approach with a compatibility flag.