Designing Efficient Read/Unread Tracking for Group Chat Messages Using Bitmaps

A friend asked about a typical interview question: how to store read/unread status for each message in a large group chat where each message has a unique uint64_t messageid and each user a unique uint64_t userid .

The naive solution keeps two lists per message (readids and unreadids) and moves a user ID from unread to read when they view the message. This approach quickly becomes memory‑heavy: for a 200‑member group each message would need 1600 bytes, leading to >1.6 MB per day.

Observing that read/unread is a binary flag, the author suggests using a bitmap. First, map each user to a sequential mapid within the group:

struct UserInfo {
    uint64_t userid;
    uint32_t mapid;
};

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

With this mapping, a message can store a compact structure:

{ uint32_t maxid, uint8_t readbit[] }

For a group of 5 members the bitmap starts as 0000 0000 . When user D reads the message the bitmap becomes 0000 1000 ; when all four other members have read it, it becomes 0001 1110 . This reduces per‑message storage from 8 bytes × N to roughly 2 bits per user.

Additional considerations include handling members who leave the group. Instead of physically deleting them, they are marked as deleted so their mapid can be reused when they re‑join, and a separate quitbit bitmap records whether a member has exited before a given message.

The final storage format for a message becomes { maxid, readbit[], quitbit[] } , allowing the system to ignore deleted members while still tracking read status efficiently.

Benefits of this design:

Adding the auto‑increment mapid field incurs negligible cost.

Memory per user drops from 8 bytes to about 2 bits, achieving >95 % reduction (e.g., 200 members need only ~54 bytes instead of 1600 bytes per message).

If maxid grows to millions, the bitmap size could become large; however, typical group size limits keep maxid manageable, and a fallback to the original scheme can be used when necessary.

The article concludes with a call for discussion and invites readers to join a community of architects.