位圖的使用
當(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）：

圖片.png

操作：統(tǒng)計(jì)（bitcount）和查找（bitpos）：

圖片.png

以上就是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）：

圖片.png

大家看了會(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)用場景，建議使用。