面試官：如何設(shè)計(jì)群聊消息的已讀未讀功能?

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

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

我第一時(shí)間給出一個(gè)很簡單粗暴的方案：

對于每一個(gè)messageid，存當(dāng)前readids + unreadids，當(dāng)群成員A已讀某一條消息時(shí)，把A userid從unreadids移除寫到readids上就好了，客戶端更新到messageid對應(yīng)的詳情列表，就可以展示m人已讀，n人未讀

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

仔細(xì)分析，按照目前的設(shè)計(jì)，每一條消息，已讀未讀詳情就要占用8B * 群成員數(shù)的內(nèi)存，如果一個(gè)活躍的200人大群，每發(fā)一條消息，已讀未讀就要1600B，如果平均每天消息量是1k，那每個(gè)這樣的群，每天就要1.6MB磁盤空間，對于客戶端來說，特別是手機(jī)端，占用磁盤空間是用戶不能接受的，又不能把工作消息刪了，對于服務(wù)器端來說，用戶群體如果特別大，那數(shù)據(jù)庫存儲(chǔ)這個(gè)成本也不小。

其實(shí)未讀已讀就是一個(gè)0/1的標(biāo)記而已，可以維護(hù)一個(gè)bitmap來實(shí)現(xiàn)呢？具體應(yīng)該怎么做呢？

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

struct?UserInfo?
{?
?uint64_t?userid;
?uint32_t?mapid;
};

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

這樣群成員每加入一個(gè)群里，就有mapid<->usreid的雙向映射了，假如群里有5個(gè)成員ABCDE, 那就對應(yīng)mapid 1-5，messageid對應(yīng)的消息詳情存儲(chǔ)就可以設(shè)計(jì)成：

{?uint32_t?maxid,?uint8_t?readbit[]}

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

這是個(gè)粗略的方案，里面還有一些細(xì)節(jié)值得思考：

1. 退出的成員呢？比如C退出群，發(fā)消息時(shí)maxid還是5，已讀+未讀總?cè)藬?shù)應(yīng)該是3(不包括發(fā)消息者本人)，目前信息只有5個(gè)bit（0/1），識(shí)別不出來誰已經(jīng)退出群聊了
2. 退出群聊的成員如何處理？從GruopMetaInfo里面刪除么？退出群聊成員重新加入又如何分配id呢？

首先2這個(gè)點(diǎn)，退出群聊的成員只能標(biāo)記刪除，不能物理刪除，不然客戶端展示已讀未讀詳情時(shí)，通過mapid找不到對應(yīng)的userid，退出的成員又重新加入群聊這個(gè)就好辦了，把標(biāo)記刪除改成非標(biāo)記刪除，還是用舊的mapid。

至于1呢？我目前想到比較好的方式就是再加多一個(gè)bitmap，記錄成員在消息發(fā)送時(shí)是否已經(jīng)退出群聊了，退出群聊就置為1, 所以最終方案就是：

群信息增加userid，自增mapid雙向映射，退出群聊成員標(biāo)記刪除，messageid 已讀未讀詳情存儲(chǔ) {maxid, readbit[], quitbit[]}。

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

1. 增加自增mapid字段，一個(gè)群聊維護(hù)一份，成本幾乎可以忽略不計(jì)
2. 每個(gè)成員已讀未讀由8B（64bit）優(yōu)化成2bit，減少62/64, 200人已讀未讀舊的方案1600B, 現(xiàn)在只需要(200/8) * 2 + 4 = 54 ， 每條消息節(jié)約95%+

如果maxid如果到百萬甚至千萬級(jí)別，那豈不是災(zāi)難？一般實(shí)際場景，群聊是會(huì)限制人數(shù)的，就算不斷踢人加新人，那maxid最多也只能到企業(yè)人數(shù)。如果maxid達(dá)到一個(gè)特別大數(shù)字，已讀未讀對應(yīng)的存儲(chǔ)可以增加多一個(gè)flag，如果bitmap存儲(chǔ)成本遠(yuǎn)超過最初的方案，可以用最初的方案來實(shí)現(xiàn)，客戶端提前埋好兼容邏輯就可以了。

作者：小袁學(xué)習(xí)筆記

來源：www.toutiao.com/i6686735232772604429/

（完）

PS：如果覺得我的分享不錯(cuò)，歡迎大家隨手點(diǎn)贊、在看。
?關(guān)注公眾號(hào)：Java后端編程，回復(fù)下面關(guān)鍵字?

要Java學(xué)習(xí)完整路線，回復(fù)??路線?
缺Java入門視頻，回復(fù)：?視頻?
要Java面試經(jīng)驗(yàn)，回復(fù)??面試?
缺Java項(xiàng)目，回復(fù)：?項(xiàng)目?
進(jìn)Java粉絲群：?加群?

PS：如果覺得我的分享不錯(cuò)，歡迎大家隨手點(diǎn)贊、在看。
（完）




加我"微信"?獲取一份 最新Java面試題資料
請備注：666，不然不通過～

最近好文

1、再見了，收費(fèi)的XShell，我改用國產(chǎn)良心工具！
2、給IDEA換個(gè)酷炫的主題，真的太好看了！
3、SpringBoot快速開發(fā)利器：Spring Boot CLI
4、基于SpringBoot 的CMS系統(tǒng)，拿去開發(fā)企業(yè)官網(wǎng)
5、本機(jī)號(hào)碼一鍵登錄原理與應(yīng)用


最近面試BAT，整理一份面試資料《Java面試BAT通關(guān)手冊》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：關(guān)注公眾號(hào)并回復(fù)?java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
明天見(??ω??)??