why
面對(duì)海量的請(qǐng)求孔厉，如何計(jì)算UV墓律？
How
一蒂窒、基于Bitmap
Bitmap是一串連續(xù)的2進(jìn)制數(shù)字（0或1）躁倒，每一位所在的位置為偏移(offset)荞怒，在bitmap上可執(zhí)行AND,OR,XOR以及其它位操作。
為了統(tǒng)計(jì)今日登錄的用戶數(shù)秧秉，我們建立了一個(gè)bitmap,每一位標(biāo)識(shí)一個(gè)用戶ID褐桌。當(dāng)某個(gè)用戶訪問我們的網(wǎng)頁(yè)或執(zhí)行了某個(gè)操作，就在bitmap中把標(biāo)識(shí)此用戶的位置為1象迎。在Redis中獲取此bitmap的key值是通過用戶執(zhí)行操作的類型和時(shí)間戳獲得的荧嵌。
這個(gè)簡(jiǎn)單的例子中，每次用戶登錄時(shí)會(huì)執(zhí)行一次redis.setbit(daily_active_users, user_id, 1)砾淌。將bitmap中對(duì)應(yīng)位置的位置為1啦撮，時(shí)間復(fù)雜度是O(1)。統(tǒng)計(jì)bitmap結(jié)果顯示有今天有9個(gè)用戶登錄汪厨。Bitmap的key是daily_active_users赃春，它的值是1011110100100101。
因?yàn)槿栈钴S用戶每天都變化劫乱，所以需要每天創(chuàng)建一個(gè)新的bitmap织中。我們簡(jiǎn)單地把日期添加到key后面，實(shí)現(xiàn)了這個(gè)功能衷戈。例如狭吼，要統(tǒng)計(jì)某一天有多少個(gè)用戶至少聽了一個(gè)音樂app中的一首歌曲，可以把這個(gè)bitmap的redis key設(shè)計(jì)為play:yyyy-mm-dd-hh脱惰。當(dāng)用戶聽了一首歌曲搏嗡，我們只是簡(jiǎn)單地在bitmap中把標(biāo)識(shí)這個(gè)用戶的位置為1，時(shí)間復(fù)雜度是O(1)拉一。
二、基于BloomFilter
Bloom Filter是由Bloom在1970年提出的一種多哈希函數(shù)映射的快速查找算法旧乞。通常應(yīng)用在一些需要快速判斷某個(gè)元素是否屬于集合蔚润，但是并不嚴(yán)格要求100%正確的場(chǎng)合。
1尺栖、初始狀態(tài)時(shí)嫡纠，Bloom Filter是一個(gè)包含m位的位數(shù)組，每一位都置為0:
2延赌、當(dāng)來了一個(gè)元素 a除盏，進(jìn)行判斷，使用兩個(gè)哈希函數(shù)挫以，計(jì)算出該元素對(duì)應(yīng)的Hash值為1和5者蠕，然后到Bloom Filter中判斷第1位和第5位的值，上面全部為0掐松，因此a不在Bloom Filter內(nèi)踱侣，將 a 添加進(jìn)去:
3粪小、隨著元素的插入，Bloom filter 中修改的值變多抡句，出現(xiàn)誤判的幾率也隨之變大探膊，當(dāng)新來一個(gè)元素時(shí)，滿足其在Bloom Filter內(nèi)的條件待榔，即所有對(duì)應(yīng)位都是 1 逞壁，這樣就可能有兩種情況，一是這個(gè)元素就在集合內(nèi)锐锣，沒有發(fā)生誤判猾担；還有一種情況就是發(fā)生誤判，出現(xiàn)了哈希碰撞刺下，這個(gè)元素本不在集合內(nèi)绑嘹。
4、基于bloom filter的邏輯很簡(jiǎn)單
判斷該請(qǐng)求不在bloom filter里面橘茉，把該用戶加入bloom filter 同時(shí)UV++
5工腋、其他方法
參考文章https://blog.csdn.net/firenet1/article/details/77247649
