大數(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通過如下公式定義：

四、使用布隆過濾器實現(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)！