面試官：如何設計羣聊消息的已讀未讀功能?

一朋友和我討論他前段時間面試某大公司的一題目 ：

企業 IM 比如企業微信、釘釘裏面的羣消息的有個已讀未讀的功能，發送者剛發出消息時，當前羣裏其他羣成員都是未讀狀態，陸陸續續有人看了這個消息，這時候消息的詳情變成 x 人已讀，y 人未讀，如下圖所示，有具體的已讀未讀列表（萬惡的功能，看到同事 or 老闆的消息不能假裝沒看到了），每條消息對應一個唯一的 messageid（uint64_t），每個用戶對應一個唯一的 userid（uint64_t）, 應該如何保存這個消息對應的已讀未讀詳情呢？

我第一時間給出一個很簡單粗暴的方案：

對於每一個 messageid，存當前 readids + unreadids，當羣成員 A 已讀某一條消息時，把 A userid 從 unreadids 移除寫到 readids 上就好了，客戶端更新到 messageid 對應的詳情列表，就可以展示 m 人已讀，n 人未讀

顯然這麼簡單粗暴的方案面試官是不會滿意的，追問有沒有更好的方案呢？

仔細分析，按照目前的設計，每一條消息，已讀未讀詳情就要佔用 8B * 羣成員數的內存，如果一個活躍的 200 人大羣，每發一條消息，已讀未讀就要 1600B，如果平均每天消息量是 1k，那每個這樣的羣，每天就要 1.6MB 磁盤空間，對於客戶端來說，特別是手機端，佔用磁盤空間是用戶不能接受的，又不能把工作消息刪了，對於服務器端來說，用戶羣體如果特別大，那數據庫存儲這個成本也不小

其實未讀已讀就是一個 0/1 的標記而已，可以維護一個 bitmap 來實現呢？具體應該怎麼做呢？

羣元信息保存 userid 到自增 mapid 的映射

struct UserInfo 
{ 
 uint64_t userid;
 uint32_t mapid;
};

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

這樣羣成員每加入一個羣裏，就有 mapid<->usreid 的雙向映射了，假如羣裏有 5 個成員 ABCDE, 那就對應 mapid 1-5，messageid 對應的消息詳情存儲就可以設計成

{ uint32_t maxid, uint8_t readbit[]}

如上面的案例就是 {5, readbit[0] =bin(0000 0000)}; 就佔用了 5B(4+1),A 發消息，D 已讀消息時，就更新成 {5,readbit[0]= bin(0000 1000)}, 其餘 4 人都已讀消息時 更新爲 {5, readbit[0]=bin(0001 1110)}

這是個粗略的方案，裏面還有一些細節值得思考：

  1. 退出的成員呢？比如 C 退出羣，發消息時 maxid 還是 5，已讀 + 未讀總人數應該是 3(不包括髮消息者本人)，目前信息只有 5 個 bit（0/1），識別不出來誰已經退出羣聊了

  2. 退出羣聊的成員如何處理？從 GruopMetaInfo 裏面刪除麼？退出羣聊成員重新加入又如何分配 id 呢？

首先 2 這個點，退出羣聊的成員只能標記刪除，不能物理刪除，不然客戶端展示已讀未讀詳情時，通過 mapid 找不到對應的 userid，退出的成員又重新加入羣聊這個就好辦了，把標記刪除改成非標記刪除，還是用舊的 mapid.

至於 1 呢？我目前想到比較好的方式就是再加多一個 bitmap，記錄成員在消息發送時是否已經退出羣聊了，退出羣聊就置爲 1, 所以最終方案就是

羣信息增加 userid，自增 mapid 雙向映射，退出羣聊成員標記刪除，messageid 已讀未讀詳情存儲 {maxid, readbit[], quitbit[]}

新的方案帶來怎樣的收益呢？

  1. 增加自增 mapid 字段，一個羣聊維護一份，成本幾乎可以忽略不計

  2. 每個成員已讀未讀由 8B（64bit）優化成 2bit，減少 62/64, 200 人已讀未讀舊的方案 1600B, 現在只需要 (200/8) * 2 + 4 = 54 ， 每條消息節約 95%+

如果 maxid 如果到百萬甚至千萬級別，那豈不是災難？一般實際場景，羣聊是會限制人數的，就算不斷踢人加新人，那 maxid 最多也只能到企業人數。如果 maxid 達到一個特別大數字，已讀未讀對應的存儲可以增加多一個 flag，如果 bitmap 存儲成本遠超過最初的方案，可以用最初的方案來實現，客戶端提前埋好兼容邏輯就可以了

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ipM6wG2MXExmg2xmJJR8Fw

猜你喜歡