位圖的使用
當(dāng)接到這樣的需求時(shí)，第一時(shí)間我想到的就是使用Redis來應(yīng)對(duì)這樣的需求祭饭，用戶一年的簽到記錄芜茵， 簽了是 1，沒簽是 0倡蝙，要記錄 365 天九串。如果使用普通的 key/value，每個(gè)用戶要記錄 365 個(gè)寺鸥，當(dāng)用戶上億的時(shí)候猪钮，需要的存儲(chǔ)空間是驚人的。而這時(shí)Redis的位圖數(shù)據(jù)結(jié)構(gòu)就派上用場了胆建，這樣每天的簽到記錄只占據(jù)一個(gè)位烤低， 365 天就是 365 個(gè)位，一個(gè)字節(jié)是8位笆载，也就是一個(gè)用戶簽到一年扑馁，差不多46 個(gè)字節(jié)就可以完全容納下，這就大大節(jié)約了存儲(chǔ)空間宰译。
位圖不是特殊的數(shù)據(jù)結(jié)構(gòu)檐蚜，它的內(nèi)容其實(shí)就是普通的字符串，也就是 byte 數(shù)組沿侈。我們可以使用普通的 get/set 直接獲取和設(shè)置整個(gè)位圖的內(nèi)容闯第，也可以使用位圖操作 getbit/setbit 等將 byte 數(shù)組看成「位數(shù)組」來處理。
操作：設(shè)置（setbit）和獲茸菏谩（getbit）：
操作：統(tǒng)計(jì)（bitcount）和查找（bitpos）：
以上就是Redis提供給我們位圖的數(shù)據(jù)結(jié)構(gòu)咳短，當(dāng)然還是其他操作填帽，這里就不再贅述，下面來講一下另外一個(gè)需求咙好，那就是統(tǒng)計(jì)網(wǎng)站的UV數(shù)據(jù)篡腌，當(dāng)接到這樣一個(gè)需求時(shí)，相信大部分程序員都會(huì)漏出自信的微笑勾效，我用一個(gè)Redis的計(jì)數(shù)器就可以實(shí)現(xiàn)了嘹悼，其實(shí)不然，如果統(tǒng)計(jì) PV 那非常好辦层宫，給每個(gè)網(wǎng)頁一個(gè)獨(dú)立的 Redis 計(jì)數(shù)器就可以了杨伙，這個(gè)計(jì)數(shù)器 的 key 后綴加上當(dāng)天的日期。這樣來一個(gè)請(qǐng)求萌腿，incrby 一次限匣，最終就可以統(tǒng)計(jì)出所有的 PV 數(shù)據(jù)。但是 UV 不一樣毁菱，它要去重米死，同一個(gè)用戶一天之內(nèi)的多次訪問請(qǐng)求只能計(jì)數(shù)一次。這就 要求每一個(gè)網(wǎng)頁請(qǐng)求都需要帶上用戶的 ID贮庞，無論是登陸用戶還是未登陸用戶都需要一個(gè)唯一 ID 來標(biāo)識(shí)峦筒。可能你會(huì)想到另外一個(gè)簡單的方案贸伐，那就是為每一個(gè)頁面一個(gè)獨(dú)立的 set 集合來存儲(chǔ)所有當(dāng)天訪問過此頁面的用戶 ID勘天。當(dāng)一個(gè)請(qǐng)求過來時(shí)，我們使用 sadd 將用戶 ID 塞進(jìn)去就可 以了捉邢。通過 scard 可以取出這個(gè)集合的大小脯丝，這個(gè)數(shù)字就是這個(gè)頁面的 UV 數(shù)據(jù)。不錯(cuò)伏伐，這也是一個(gè)實(shí)現(xiàn)方案宠进，但這個(gè)方案也有缺點(diǎn)，那就是數(shù)據(jù)量比較大時(shí)藐翎，如果你的頁面訪問量非常大材蹬，比如一個(gè)爆款頁面幾千萬的 UV，你需要一個(gè)很大 的 set 集合來統(tǒng)計(jì)吝镣，這就非常浪費(fèi)空間堤器。
鋪墊了那么久，其實(shí)就是為了引出這個(gè)解決方案的主角末贾，那就是HyperLogLog闸溃，Redis 提供了 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)就是用來解決 這種統(tǒng)計(jì)問題的。HyperLogLog 提供不精確的去重計(jì)數(shù)方案，雖然不精確但是也不是非常不精確辉川，標(biāo)準(zhǔn)誤差是不到1%表蝙，這樣的精確度已經(jīng)可以滿足上面的 UV 統(tǒng)計(jì)需求了。
操作：增加（pfadd）和統(tǒng)計(jì)（pfcount）：
大家看了會(huì)說乓旗，這部挺準(zhǔn)確的府蛇，添加了3個(gè)，統(tǒng)計(jì)出來的就是3個(gè)屿愚，量大了就不行了
HyperLogLog 主要的應(yīng)用場景就是進(jìn)行基數(shù)統(tǒng)計(jì)汇跨。這個(gè)問題的應(yīng)用場景其實(shí)是十分廣泛的。例如：對(duì)于 Google 主頁面而言妆距，同一個(gè)賬戶可能會(huì)訪問 Google 主頁面多次扰法。于是，在諸多的訪問流水中毅厚，如何計(jì)算出 Google 主頁面每天被多少個(gè)不同的賬戶訪問過就是一個(gè)重要的問題。那么對(duì)于 Google 這種訪問量巨大的網(wǎng)頁而言浦箱，其實(shí)統(tǒng)計(jì)出有十億 的訪問量或者十億零十萬的訪問量其實(shí)是沒有太多的區(qū)別的吸耿，因此，在這種業(yè)務(wù)場景下酷窥，為了節(jié)省成本咽安，其實(shí)可以只計(jì)算出一個(gè)大概的值，而沒有必要計(jì)算出精準(zhǔn)的值蓬推。
對(duì)于上面的場景妆棒，可以使用HashMap、BitMap和HyperLogLog 來解決沸伏。對(duì)于這三種解決方案糕珊，這邊做下對(duì)比：
-
HashMap：算法簡單，統(tǒng)計(jì)精度高毅糟，對(duì)于少量數(shù)據(jù)建議使用红选，但是對(duì)于大量的數(shù)據(jù)會(huì)占用很大內(nèi)存空間； -
BitMap：位圖算法姆另，統(tǒng)計(jì)精度高喇肋，雖然內(nèi)存占用要比HashMap少，但是對(duì)于大量數(shù)據(jù)還是會(huì)占用較大內(nèi)存迹辐； -
HyperLogLog：存在一定誤差蝶防，占用內(nèi)存少，穩(wěn)定占用 12k 左右內(nèi)存明吩，可以統(tǒng)計(jì) 2^64 個(gè)元素间学，對(duì)于上面舉例的應(yīng)用場景，建議使用。
