很可惜 T 。T 您現(xiàn)在還不是作者身份，不能自主發(fā)稿哦～
如有投稿需求，請把文章發(fā)送到郵箱tougao@appcpx.com，一經(jīng)錄用會有專人和您聯(lián)系
咨詢?nèi)绾纬蔀榇河鹱髡哒埪?lián)系：鳥哥筆記小羽毛（ngbjxym）
這是我的第51篇原創(chuàng)
你在刷抖音的時候，有沒有發(fā)現(xiàn)，抖音從來不會給你推送相同內(nèi)容的視頻？你可能會想，這有啥難的，給每個人都存一個記錄，以后推送的時候避開就好了呀。nononono！可沒有這么簡單哈！
這是一個非常嚴肅的問題。
在互聯(lián)網(wǎng)領(lǐng)域，重復(fù)推送是一件非常影響用戶體驗的行為。一旦出現(xiàn)重復(fù)內(nèi)容，會大大增加用戶跳出的幾率。
搞數(shù)據(jù)庫的同學(xué)會說：這還不簡單？反正有用戶日志，我們給每個人都存一個訪問日志表，推送之前exists一下就好了。怎么說呢，如果用戶量只有你們公司幾百號人，這個方案是沒問題的。但是抖音、快手動輒幾億人，每天都刷，這得存多少份log？？每一個用戶的log有多大？每一個推送都要從這個大log里exists一下，得耗多少時間？等你exists一下，用戶早就跑了好么？
所以在抖音、快手動輒幾億日活，每人每天最少看幾百個短視頻的情況，如何快速推送不重復(fù)的內(nèi)容是非常困難的事情。
需求：幾億個用戶，每個用戶有1~幾萬（甚至更多）個已看記錄，快速判斷下一個推送給用戶的視頻是否已經(jīng)看過。
解決方案1-表級處理：每個用戶一張表，存視頻id，推薦之后，展示之前，過濾一下。這個表太多，表里的數(shù)據(jù)也太多，過濾效率太慢了。信息得進一步壓縮，速度要再快點才行。
解決方案2-圖計算：把每個用戶與每個視頻發(fā)生的關(guān)系都存到圖數(shù)據(jù)庫。推薦的時候直接通過關(guān)系過濾掉。這個雖然不用建N張表，只是存用戶和視頻的關(guān)系就行了。但是用過圖數(shù)據(jù)庫的人就知道，節(jié)點太多了，計算效果也是非常的慢。不行，信息還得進一步壓縮。還能咋壓縮?。?/span>
解決方案3-位圖：之前分享過一篇《10億用戶量，連續(xù)7天登錄的用戶標簽該怎么打？》，其中就介紹了位圖法，把所有用戶當天是否登錄的信息映射到一張位圖中，這樣我們就能迅速通過某個位是0還是1快速判定這個用戶當天是否登錄過系統(tǒng)。假如說我們同樣使用位圖，把每個用戶是否看過這個視頻映射到位圖中，是不是就可以通過某個位是0還是1快速判定這個用戶是否看過這個視頻呢？哆啦A夢告訴我們：可以！而且有更完善的方法--布隆過濾器！
布隆過濾器：1970年由布隆提出的一種方法，由隨機映射函數(shù)和二進制向量組成，可以快速檢索一個元素是否在一個集合中。
布隆過濾器原理（初級形態(tài)）
如布隆過濾器的描述，其實就是隨機映射函數(shù)（hash散列）+二進制向量（位圖）組成的。我們把任意需要存儲的內(nèi)容，經(jīng)過hash散列映射成為一個隨機數(shù)字，然后存在這張超大的位圖中，將對應(yīng)的位上的值由0改成1就可以了。這樣我們就能知道這個這個事情是否發(fā)生過。
上圖中，用戶A看了視頻B，hash后的值是5，那么第5位的值就變成1了。如果我們想判斷用戶A是否看了視頻B，只要看看第5位是不是1就可以了。
但是hash有個問題，當數(shù)據(jù)量超大的時候，就有可能會重復(fù)（碰撞）。幸好布隆早就想到了，他是這么解決的：
布隆過濾器原理（完全形態(tài)）
多hash幾次就好了，這樣就能就大大降低了重復(fù)（碰撞）的問題?？偛豢赡苓B續(xù)好幾次hash都是一樣的結(jié)果吧？
原理有了，那么就可以開始設(shè)計了。
這里我們可以看到，有兩個實體：用戶和視頻。簡單組合一下，就有三種方法：
1、給每個用戶建一個看過視頻的布隆過濾器，推薦系統(tǒng)推送的內(nèi)容使用布隆過濾器過濾一下，把不在列表里的讓客戶可見即可；
2、給每個視頻建一個觀看列表的布隆過濾器，推薦系統(tǒng)給用戶推送的時候使用布隆過濾器過濾一下，不在列表里的才能推送即可；
3、建一個大的布隆過濾器，把每個用戶的觀看記錄都放在這個過濾器中，推薦系統(tǒng)給用戶推送的時候到大布隆過濾器中過濾一下，不在列表里的才能推送。
以上三種方法都可以，我也不太清楚抖音用的是那種方法，我猜是第一種，因為視頻總比用戶多，而一個大布隆過濾器的話，又太大了。
不過即便是每個用戶一個布隆過濾器，數(shù)據(jù)量還是太大了。任何事情都會引發(fā)量變引起質(zhì)變的問題。所以布隆過濾器誤判的問題仍然是存在的。比如：
用戶A看視頻B，3次hash散列結(jié)果是2、5、6；
用戶A看視頻D，3次hash散列結(jié)果是5、7、8；
用戶A看視頻F，3次hash散列結(jié)果是1、9、3；
這時候，位圖中的1、2、3、5、7、8、9都被打上1了。
而我們需要詢問布隆過濾器用戶A是否看過視頻H的時候就出現(xiàn)了：
用戶A看視頻H，3次hash散列結(jié)果是3、8、9，
布隆過濾器里3、8、9的結(jié)果內(nèi)容里已經(jīng)被打上1了，也就是說布隆過濾器告訴我們，這個視頻已經(jīng)被看過了（實際上并沒有看）。那我們怎么解決這個問題呢？
簡單的兩招：
1、增加位圖的位數(shù)（或者減少原始數(shù)據(jù)量）；
2、適當增加hash次數(shù)；
布隆大大早就給我們算好了，最佳的原始數(shù)據(jù)和位圖位數(shù)比是1:20，經(jīng)過8次hash，誤判率會在千分之一左右。如果把hash次數(shù)提高，誤判率會更低。
不過，我們的應(yīng)用是要知道這個用戶沒看過的，那就不用咋優(yōu)化了。因為布隆過濾器告訴我們看過，可能是誤判，但是如果告訴我們沒看過，那就肯定是沒看過
。
看抖音本來就夠無聊的，再研究這個事情，就更無聊了，是吧
往期精彩回顧
熱文 | 徹底搞定數(shù)據(jù)產(chǎn)品選型
本文為作者獨立觀點，不代表鳥哥筆記立場，未經(jīng)允許不得轉(zhuǎn)載。
《鳥哥筆記版權(quán)及免責(zé)申明》 如對文章、圖片、字體等版權(quán)有疑問，請點擊 反饋舉報
我們致力于提供一個高質(zhì)量內(nèi)容的交流平臺。為落實國家互聯(lián)網(wǎng)信息辦公室“依法管網(wǎng)、依法辦網(wǎng)、依法上網(wǎng)”的要求，為完善跟帖評論自律管理，為了保護用戶創(chuàng)造的內(nèi)容、維護開放、真實、專業(yè)的平臺氛圍，我們團隊將依據(jù)本公約中的條款對注冊用戶和發(fā)布在本平臺的內(nèi)容進行管理。平臺鼓勵用戶創(chuàng)作、發(fā)布優(yōu)質(zhì)內(nèi)容，同時也將采取必要措施管理違法、侵權(quán)或有其他不良影響的網(wǎng)絡(luò)信息。
一、根據(jù)《網(wǎng)絡(luò)信息內(nèi)容生態(tài)治理規(guī)定》《中華人民共和國未成年人保護法》等法律法規(guī)，對以下違法、不良信息或存在危害的行為進行處理。
1. 違反法律法規(guī)的信息，主要表現(xiàn)為：
1)反對憲法所確定的基本原則；
2)危害國家安全，泄露國家秘密，顛覆國家政權(quán)，破壞國家統(tǒng)一，損害國家榮譽和利益；
3)侮辱、濫用英烈形象，歪曲、丑化、褻瀆、否定英雄烈士事跡和精神，以侮辱、誹謗或者其他方式侵害英雄烈士的姓名、肖像、名譽、榮譽；
4)宣揚恐怖主義、極端主義或者煽動實施恐怖活動、極端主義活動；
5)煽動民族仇恨、民族歧視，破壞民族團結(jié)；
6)破壞國家宗教政策，宣揚邪教和封建迷信；
7)散布謠言，擾亂社會秩序，破壞社會穩(wěn)定；
8)宣揚淫穢、色情、賭博、暴力、兇殺、恐怖或者教唆犯罪；
9)煽動非法集會、結(jié)社、游行、示威、聚眾擾亂社會秩序；
10)侮辱或者誹謗他人，侵害他人名譽、隱私和其他合法權(quán)益；
11)通過網(wǎng)絡(luò)以文字、圖片、音視頻等形式，對未成年人實施侮辱、誹謗、威脅或者惡意損害未成年人形象進行網(wǎng)絡(luò)欺凌的；
12)危害未成年人身心健康的；
13)含有法律、行政法規(guī)禁止的其他內(nèi)容；
2. 不友善：不尊重用戶及其所貢獻內(nèi)容的信息或行為。主要表現(xiàn)為：
1)輕蔑：貶低、輕視他人及其勞動成果；
2)誹謗：捏造、散布虛假事實，損害他人名譽；
3)嘲諷：以比喻、夸張、侮辱性的手法對他人或其行為進行揭露或描述，以此來激怒他人；
4)挑釁：以不友好的方式激怒他人，意圖使對方對自己的言論作出回應(yīng)，蓄意制造事端；
5)羞辱：貶低他人的能力、行為、生理或身份特征，讓對方難堪；
6)謾罵：以不文明的語言對他人進行負面評價；
7)歧視：煽動人群歧視、地域歧視等，針對他人的民族、種族、宗教、性取向、性別、年齡、地域、生理特征等身份或者歸類的攻擊；
8)威脅：許諾以不良的后果來迫使他人服從自己的意志；
3. 發(fā)布垃圾廣告信息：以推廣曝光為目的，發(fā)布影響用戶體驗、擾亂本網(wǎng)站秩序的內(nèi)容，或進行相關(guān)行為。主要表現(xiàn)為：
1)多次發(fā)布包含售賣產(chǎn)品、提供服務(wù)、宣傳推廣內(nèi)容的垃圾廣告。包括但不限于以下幾種形式：
2)單個帳號多次發(fā)布包含垃圾廣告的內(nèi)容；
3)多個廣告帳號互相配合發(fā)布、傳播包含垃圾廣告的內(nèi)容；
4)多次發(fā)布包含欺騙性外鏈的內(nèi)容，如未注明的淘寶客鏈接、跳轉(zhuǎn)網(wǎng)站等，誘騙用戶點擊鏈接
5)發(fā)布大量包含推廣鏈接、產(chǎn)品、品牌等內(nèi)容獲取搜索引擎中的不正當曝光；
6)購買或出售帳號之間虛假地互動，發(fā)布干擾網(wǎng)站秩序的推廣內(nèi)容及相關(guān)交易。
7)發(fā)布包含欺騙性的惡意營銷內(nèi)容，如通過偽造經(jīng)歷、冒充他人等方式進行惡意營銷；
8)使用特殊符號、圖片等方式規(guī)避垃圾廣告內(nèi)容審核的廣告內(nèi)容。
4. 色情低俗信息，主要表現(xiàn)為：
1)包含自己或他人性經(jīng)驗的細節(jié)描述或露骨的感受描述；
2)涉及色情段子、兩性笑話的低俗內(nèi)容；
3)配圖、頭圖中包含庸俗或挑逗性圖片的內(nèi)容；
4)帶有性暗示、性挑逗等易使人產(chǎn)生性聯(lián)想；
5)展現(xiàn)血腥、驚悚、殘忍等致人身心不適；
6)炒作緋聞、丑聞、劣跡等；
7)宣揚低俗、庸俗、媚俗內(nèi)容。
5. 不實信息，主要表現(xiàn)為：
1)可能存在事實性錯誤或者造謠等內(nèi)容；
2)存在事實夸大、偽造虛假經(jīng)歷等誤導(dǎo)他人的內(nèi)容；
3)偽造身份、冒充他人，通過頭像、用戶名等個人信息暗示自己具有特定身份，或與特定機構(gòu)或個人存在關(guān)聯(lián)。
6. 傳播封建迷信，主要表現(xiàn)為：
1)找人算命、測字、占卜、解夢、化解厄運、使用迷信方式治??；
2)求推薦算命看相大師；
3)針對具體風(fēng)水等問題進行求助或咨詢；
4)問自己或他人的八字、六爻、星盤、手相、面相、五行缺失，包括通過占卜方法問婚姻、前程、運勢，東西寵物丟了能不能找回、取名改名等；
7. 文章標題黨，主要表現(xiàn)為：
1)以各種夸張、獵奇、不合常理的表現(xiàn)手法等行為來誘導(dǎo)用戶；
2)內(nèi)容與標題之間存在嚴重不實或者原意扭曲；
3)使用夸張標題，內(nèi)容與標題嚴重不符的。
8.「飯圈」亂象行為，主要表現(xiàn)為：
1)誘導(dǎo)未成年人應(yīng)援集資、高額消費、投票打榜
2)粉絲互撕謾罵、拉踩引戰(zhàn)、造謠攻擊、人肉搜索、侵犯隱私
3)鼓動「飯圈」粉絲攀比炫富、奢靡享樂等行為
4)以號召粉絲、雇用網(wǎng)絡(luò)水軍、「養(yǎng)號」形式刷量控評等行為
5)通過「蹭熱點」、制造話題等形式干擾輿論，影響傳播秩序
9. 其他危害行為或內(nèi)容，主要表現(xiàn)為：
1)可能引發(fā)未成年人模仿不安全行為和違反社會公德行為、誘導(dǎo)未成年人不良嗜好影響未成年人身心健康的；
2)不當評述自然災(zāi)害、重大事故等災(zāi)難的；
3)美化、粉飾侵略戰(zhàn)爭行為的；
4)法律、行政法規(guī)禁止，或可能對網(wǎng)絡(luò)生態(tài)造成不良影響的其他內(nèi)容。
二、違規(guī)處罰
本網(wǎng)站通過主動發(fā)現(xiàn)和接受用戶舉報兩種方式收集違規(guī)行為信息。所有有意的降低內(nèi)容質(zhì)量、傷害平臺氛圍及欺凌未成年人或危害未成年人身心健康的行為都是不能容忍的。
當一個用戶發(fā)布違規(guī)內(nèi)容時，本網(wǎng)站將依據(jù)相關(guān)用戶違規(guī)情節(jié)嚴重程度，對帳號進行禁言 1 天、7 天、15 天直至永久禁言或封停賬號的處罰。當涉及欺凌未成年人、危害未成年人身心健康、通過作弊手段注冊、使用帳號，或者濫用多個帳號發(fā)布違規(guī)內(nèi)容時，本網(wǎng)站將加重處罰。
三、申訴
隨著平臺管理經(jīng)驗的不斷豐富，本網(wǎng)站出于維護本網(wǎng)站氛圍和秩序的目的，將不斷完善本公約。
如果本網(wǎng)站用戶對本網(wǎng)站基于本公約規(guī)定做出的處理有異議，可以通過「建議反饋」功能向本網(wǎng)站進行反饋。
(規(guī)則的最終解釋權(quán)歸屬本網(wǎng)站所有)