大數(shù)據(jù)|阿里實時計算|Flink
一、海量數(shù)據(jù)實時去重說明
借助redis的Set,需要頻繁連接Redis,如果數(shù)據(jù)量過大, 對redis的內(nèi)存也是一種壓力;使用Flink的MapState,如果數(shù)據(jù)量過大, 狀態(tài)后端最好選擇 RocksDBStateBackend; 使用布隆過濾器,布隆過濾器可以大大減少存儲的數(shù)據(jù)的數(shù)據(jù)量。
二、海里書實時去重為什么需要布隆過濾器
如果想判斷一個元素是不是在一個集合里,一般想到的是將集合中所有元素保存起來,然后通過比較確定。鏈表、樹、散列表(又叫哈希表,Hash table)等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。
但是隨著集合中元素的增加,我們需要的存儲空間越來越大。同時檢索速度也越來越慢,上述三種結(jié)構(gòu)的檢索時間復(fù)雜度分別為。
布隆過濾器即可以解決存儲空間的問題, 又可以解決時間復(fù)雜度的問題.
布隆過濾器的原理是,當一個元素被加入集合時,通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點,把它們置為1。檢索時,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點有任何一個0,則被檢元素一定不在;如果都是1,則被檢元素很可能在。這就是布隆過濾器的基本思想。
三、布隆過濾基本概念
布隆過濾器(Bloom Filter,下文簡稱BF)由Burton Howard Bloom在1970年提出,是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)。它專門用來檢測集合中是否存在特定的元素。
它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。
實現(xiàn)原理
布隆過濾器的原理是,當一個元素被加入集合時,通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點,把它們置為1。檢索時,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點有任何一個0,則被檢元素一定不在;如果都是1,則被檢元素很可能在。這就是布隆過濾器的基本思想。
BF是由一個長度為m比特的位數(shù)組(bit array)與k個哈希函數(shù)(hash function)組成的數(shù)據(jù)結(jié)構(gòu)。位數(shù)組均初始化為0,所有哈希函數(shù)都可以分別把輸入數(shù)據(jù)盡量均勻地散列。
當要插入一個元素時,將其數(shù)據(jù)分別輸入k個哈希函數(shù),產(chǎn)生k個哈希值。以哈希值作為位數(shù)組中的下標,將所有k個對應(yīng)的比特置為1。
當要查詢(即判斷是否存在)一個元素時,同樣將其數(shù)據(jù)輸入哈希函數(shù),然后檢查對應(yīng)的k個比特。如果有任意一個比特為0,表明該元素一定不在集合中。如果所有比特均為1,表明該集合有(較大的)可能性在集合中。為什么不是一定在集合中呢?因為一個比特被置為1有可能會受到其他元素的影響(hash碰撞),這就是所謂“假陽性”(false positive)。相對地,“假陰性”(false negative)在BF中是絕不會出現(xiàn)的。
下圖示出一個m=18, k=3的BF示例。集合中的x、y、z三個元素通過3個不同的哈希函數(shù)散列到位數(shù)組中。當查詢元素w時,因為有一個比特為0,因此w不在該集合中。
優(yōu)點
1.不需要存儲數(shù)據(jù)本身,只用比特表示,因此空間占用相對于傳統(tǒng)方式有巨大的優(yōu)勢,并且能夠保密數(shù)據(jù);
2.時間效率也較高,插入和查詢的時間復(fù)雜度均為, 所以他的時間復(fù)雜度實際是
3.哈希函數(shù)之間相互獨立,可以在硬件指令層面并行計算。
缺點
1.存在假陽性的概率,不適用于任何要求100%準確率的情境;
2.只能插入和查詢元素,不能刪除元素,這與產(chǎn)生假陽性的原因是相同的。我們可以簡單地想到通過計數(shù)(即將一個比特擴展為計數(shù)值)來記錄元素數(shù),但仍然無法保證刪除的元素一定在集合中。
使用場景
所以,BF在對查準度要求沒有那么苛刻,而對時間、空間效率要求較高的場合非常合適.
另外,由于它不存在假陰性問題,所以用作“不存在”邏輯的處理時有奇效,比如可以用來作為緩存系統(tǒng)(如Redis)的緩沖,防止緩存穿透。
假陽性概率的計算
假陽性的概率其實就是一個不在的元素,被k個函數(shù)函數(shù)散列到的k個位置全部都是1的概率。可以按照如下的步驟進行計算: p = f(m,n,k)
其中各個字母的含義:
1.n :放入BF中的元素的總個數(shù);
2.m:BF的總長度,也就是bit數(shù)組的個數(shù)
3.k:哈希函數(shù)的個數(shù);
4.p:表示BF將一個不在其中的元素錯判為在其中的概率,也就是false positive的概率;
A.BF中的任何一個bit在第一個元素的第一個hash函數(shù)執(zhí)行完之后為 0的概率是:
B.BF中的任何一個bit在第一個元素的k個hash函數(shù)執(zhí)行完之后為 0的概率是:
C.BF中的任何一個bit在所有的n元素都添加完之后為 0的概率是:
D.BF中的任何一個bit在所有的n元素都添加完之后為 1的概率是:
E.一個不存在的元素被k個hash函數(shù)映射后k個bit都是1的概率是:
結(jié)論:在哈數(shù)函數(shù)個數(shù)k一定的情況下
1.比特數(shù)組m長度越大, p越小, 表示假陽性率越低
2.已插入的元素個數(shù)n越大, p越大, 表示假陽性率越大
經(jīng)過各種數(shù)學(xué)推導(dǎo):
對于給定的m和n,使得假陽性率(誤判率)最小的k通過如下公式定義:文章來源:http://www.zghlxwxcb.cn/news/detail-728547.html
四、使用布隆過濾器實現(xiàn)去重
Flink已經(jīng)內(nèi)置了布隆過濾器的實現(xiàn)(使用的是google的Guava)文章來源地址http://www.zghlxwxcb.cn/news/detail-728547.html
package com.lyh.flink12;
import com.atguigu.flink.java.chapter_6.UserBehavior;
import org.apache.flink.api.common.eventtime.SerializableTimestampAssigner;
import org.apache.flink.api.common.eventtime.WatermarkStrategy;
import org.apache.flin
到了這里,關(guān)于大數(shù)據(jù)-玩轉(zhuǎn)數(shù)據(jù)-Flink 海量數(shù)據(jù)實時去重的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!