GO?CountMinSketch計(jì)數(shù)器(布隆過(guò)濾器思想的近似計(jì)數(shù)器)
簡(jiǎn)介
CountMinSketch
是一種計(jì)數(shù)器,用來(lái)統(tǒng)計(jì)一個(gè)元素的計(jì)數(shù),它能夠以一個(gè)非常小的空間統(tǒng)計(jì)大量元素的計(jì)數(shù),同時(shí)保證高的性能及準(zhǔn)確性。
與布隆過(guò)濾器類似,由于它是基于概率的,因此它所統(tǒng)計(jì)的計(jì)數(shù)是有一定概率存在誤差的,也就是可能會(huì)比真實(shí)的計(jì)數(shù)大。比如一個(gè)元素實(shí)際的計(jì)數(shù)是10,但是計(jì)算器的計(jì)算結(jié)果可能比10大。因此適合能夠容忍計(jì)數(shù)存在一定誤差的場(chǎng)景,比如社交網(wǎng)絡(luò)中推文的訪問(wèn)次數(shù)。
它一秒能夠進(jìn)行上百萬(wàn)次操作(主要取決于哈希函數(shù)的速度),并且如果我們每天有一個(gè)長(zhǎng)度為100億的數(shù)據(jù)流需要進(jìn)行計(jì)數(shù),計(jì)數(shù)值允許的誤差范圍是100,允許的錯(cuò)誤率是0.1%,計(jì)數(shù)器大小是32位,只需要7.2GB內(nèi)存,這完全可以單機(jī)進(jìn)行計(jì)數(shù)。
原理
數(shù)據(jù)結(jié)構(gòu)
CountMinSketch計(jì)數(shù)器的數(shù)據(jù)結(jié)構(gòu)是一個(gè)二維數(shù)組
,每一個(gè)元素都是一個(gè)計(jì)數(shù)器,計(jì)數(shù)器可以使用一個(gè)數(shù)值類型進(jìn)行表示,比如無(wú)符號(hào)int
:
增加計(jì)數(shù)
每個(gè)元素會(huì)通過(guò)不同的哈希函數(shù)映射到每一行的某個(gè)位置,并增加對(duì)應(yīng)位置上的計(jì)數(shù):
估算計(jì)數(shù)
估算計(jì)數(shù)也是如上圖流程,根據(jù)哈希映射到每一行的對(duì)應(yīng)位置,然后讀取所有行的計(jì)數(shù),返回其中最小的一個(gè)。
返回最小的一個(gè)是因?yàn)槠渌渌匾部赡軙?huì)映射到自身所映射位置上面,導(dǎo)致計(jì)數(shù)比真實(shí)計(jì)數(shù)大,因此最小的一個(gè)計(jì)數(shù)最可能是真實(shí)計(jì)數(shù):
比如上圖元素123
映射到了元素abc
第一行的相同位置,因此這個(gè)位置的計(jì)數(shù)累加了元素abc和元素123的計(jì)數(shù)和。但是只要我們?nèi)∪欣锩孀钚〉囊粋€(gè)計(jì)數(shù),那么就能容忍這種情況。
當(dāng)然,如果一個(gè)元素的每一行的對(duì)應(yīng)位置都被其他元素所映射,那么這個(gè)估算的計(jì)數(shù)就會(huì)比真實(shí)計(jì)數(shù)大。
哈希函數(shù)
CountMinSketch計(jì)數(shù)器里面的哈希函數(shù)需要是彼此獨(dú)立且均勻分布(類似于哈希表的哈希函數(shù)),而且需要盡可能的快,比如murmur3就是一個(gè)很好的選擇。
CountMinSketch計(jì)數(shù)器的性能嚴(yán)重依賴于哈希函數(shù)的性能,而一般哈希函數(shù)的性能則依賴于輸入串(一般為字節(jié)數(shù)組)的長(zhǎng)度,因此為了提高CountMinSketch計(jì)數(shù)器的性能建議減少輸入串的長(zhǎng)度。
下面是一個(gè)簡(jiǎn)單的性能測(cè)試,單位是字節(jié),可以看到時(shí)間的消耗隨著元素的增大基本是線性增長(zhǎng)的:
pkg: github.com/jiaxwu/gommon/counter/cm cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz BenchmarkAddAndEstimate/1-8 2289142 505.9 ns/op 1.98 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/2-8 2357380 513.7 ns/op 3.89 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/4-8 2342382 496.9 ns/op 8.05 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/8-8 2039792 499.7 ns/op 16.01 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/16-8 2350281 526.8 ns/op 30.37 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/32-8 2558060 444.3 ns/op 72.03 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/64-8 2540272 459.5 ns/op 139.29 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/128-8 1919720 538.6 ns/op 237.67 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/256-8 1601738 720.6 ns/op 355.28 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/512-8 950584 1599 ns/op 320.18 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/1024-8 363592 3169 ns/op 323.17 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/2048-8 187500 5888 ns/op 347.81 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/4096-8 130425 8825 ns/op 464.15 MB/s 0 B/op 0 allocs/op BenchmarkAddAndEstimate/8192-8 67198 17460 ns/op 469.18 MB/s 0 B/op 0 allocs/op
數(shù)組大小、哈希函數(shù)數(shù)量、錯(cuò)誤范圍、錯(cuò)誤率
數(shù)組大小、哈希函數(shù)數(shù)量、錯(cuò)誤范圍和錯(cuò)誤率之間是互相影響的,如果我們想減少錯(cuò)誤率和錯(cuò)誤范圍,則需要更大的數(shù)組和更多的哈希函數(shù)。但是我們很難直觀的計(jì)算出這些參數(shù),還好有兩個(gè)公式可以幫助我們計(jì)算出準(zhǔn)確的數(shù)值:
在我們可以確定我們的數(shù)據(jù)流大小
和能夠容忍的錯(cuò)誤范圍
和錯(cuò)誤率
的情況下,我們可以根據(jù)下面公式計(jì)算數(shù)組大小
和哈希函數(shù)數(shù)量
:
n = 數(shù)據(jù)流大小 m = 數(shù)組大小 k = 哈希函數(shù)數(shù)量 eRange = 錯(cuò)誤范圍(ErrorRange) eRate = 錯(cuò)誤率(ErrorRate) ceil() = 向上取整操作 E = 2.718281828459045(自然常數(shù)) m = ceil(E/(eRange/n)) k = ceil(ln(1/eRate))
應(yīng)用
TopK(海量數(shù)據(jù)計(jì)數(shù)器)
對(duì)于海量數(shù)據(jù)流中頻率最高的K個(gè)數(shù),如果使用常規(guī)的map<key, uint>
,由于內(nèi)存大小限制,一般情況下單機(jī)無(wú)法完成計(jì)算,需要把數(shù)據(jù)路由到多臺(tái)機(jī)器上進(jìn)行計(jì)數(shù)。
而如果我們使用CountMinSketch
則能夠在單機(jī)情況下處理大量的數(shù)據(jù),比如開(kāi)頭所提到對(duì)于一個(gè)長(zhǎng)度為100億的數(shù)據(jù)流進(jìn)行計(jì)數(shù),只需要7.2GB內(nèi)存。這個(gè)計(jì)數(shù)結(jié)果可能存在一定誤差,不過(guò)我們可以在這個(gè)基礎(chǔ)上再進(jìn)行過(guò)濾。
TinyLFU
TinyLFU是一個(gè)緩存淘汰策略,它里面有LFU策略的思想,LFU是一個(gè)基于訪問(wèn)頻率的淘汰策略,因此需要統(tǒng)計(jì)每個(gè)元素被訪問(wèn)的次數(shù)。如果對(duì)每個(gè)元素使用一個(gè)獨(dú)立的計(jì)數(shù)器,那么這個(gè)成本會(huì)很大,而且對(duì)于一個(gè)緩存淘汰策略來(lái)說(shuō),我們并不需要這個(gè)計(jì)數(shù)器非常大且非常準(zhǔn)確。
因此TinyLFU使用一個(gè)計(jì)數(shù)器長(zhǎng)度為4位的CountMinSketch
計(jì)數(shù)器統(tǒng)計(jì)每個(gè)元素的頻率,減少計(jì)數(shù)所消耗的內(nèi)存空間,同時(shí)還引入了計(jì)數(shù)衰減機(jī)制避免某些之前熱門但是當(dāng)前已經(jīng)很少被訪問(wèn)的元素很難被淘汰。
實(shí)現(xiàn)
這里給出一個(gè)Golang的泛型實(shí)現(xiàn),這個(gè)實(shí)現(xiàn)支持uint8
、uint16
、uint32
、uint64
等基本類型計(jì)數(shù)器,實(shí)際上還可以實(shí)現(xiàn)比如長(zhǎng)度為2bit
、4bit
、6bit
的計(jì)數(shù)器,但是代碼會(huì)稍微復(fù)雜一點(diǎn)(特別是非2的次方的計(jì)數(shù)器)。
package cm import ( "math" "github.com/jiaxwu/gommon/hash" mmath "github.com/jiaxwu/gommon/math" "github.com/jiaxwu/gommon/mem" "golang.org/x/exp/constraints" ) // Count-Min Sketch 計(jì)數(shù)器,原理類似于布隆過(guò)濾器,根據(jù)哈希映射到多個(gè)位置,然后在對(duì)應(yīng)位置進(jìn)行計(jì)數(shù) // 讀取時(shí)拿對(duì)應(yīng)位置最小的 // 適合需要一個(gè)比較小的計(jì)數(shù),而且不需要這個(gè)計(jì)數(shù)一定準(zhǔn)確的情況 // 可以減少空間消耗 // https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.591.8351&rep=rep1&type=pdf type Counter[T constraints.Unsigned] struct { counters [][]T countersLen uint64 // 計(jì)數(shù)器長(zhǎng)度 hashs []*hash.Hash // 哈希函數(shù)列表 maxCount T // 最大計(jì)數(shù)值 } // 創(chuàng)建一個(gè)計(jì)數(shù)器 // size:數(shù)據(jù)流大小 // errorRange:計(jì)數(shù)值誤差范圍(會(huì)超過(guò)真實(shí)計(jì)數(shù)值) // errorRate:錯(cuò)誤率 func New[T constraints.Unsigned](size uint64, errorRange T, errorRate float64) *Counter[T] { // 計(jì)數(shù)器長(zhǎng)度 countersLen := uint64(math.Ceil(math.E / (float64(errorRange) / float64(size)))) // 哈希個(gè)數(shù) hashsCnt := int(math.Ceil(math.Log(1.0 / errorRate))) hashs := make([]*hash.Hash, hashsCnt) counters := make([][]T, hashsCnt) for i := 0; i < hashsCnt; i++ { hashs[i] = hash.New() counters[i] = make([]T, countersLen) } return &Counter[T]{ counters: counters, countersLen: countersLen, hashs: hashs, maxCount: T(0) - 1, } } // 增加元素的計(jì)數(shù) func (c *Counter[T]) Add(b []byte, val T) { for i, h := range c.hashs { index := h.Sum64(b) % c.countersLen if c.counters[i][index]+val <= c.counters[i][index] { c.counters[i][index] = c.maxCount } else { c.counters[i][index] += val } } } // 增加元素的計(jì)數(shù) // 等同于Add(b, 1) func (c *Counter[T]) Inc(b []byte) { c.Add(b, 1) } // 增加元素的計(jì)數(shù) // 字符串類型 func (c *Counter[T]) AddString(s string, val T) { c.Add([]byte(s), val) } // 增加元素的計(jì)數(shù) // 等同于Add(b, 1) // 字符串類型 func (c *Counter[T]) IncString(s string) { c.Add([]byte(s), 1) } // 估算元素的計(jì)數(shù) func (c *Counter[T]) Estimate(b []byte) T { minCount := c.maxCount for i, h := range c.hashs { index := h.Sum64(b) % c.countersLen count := c.counters[i][index] if count == 0 { return 0 } minCount = mmath.Min(minCount, count) } return minCount } // 估算元素的計(jì)數(shù) // 字符串類型 func (c *Counter[T]) EstimateString(s string) T { return c.Estimate([]byte(s)) } // 計(jì)數(shù)衰減 // 如果factor為0則直接清空 func (c *Counter[T]) Attenuation(factor T) { for _, counter := range c.counters { if factor == 0 { mem.Memset(counter, 0) } else { for j := uint64(0); j < c.countersLen; j++ { counter[j] /= factor } } } }
數(shù)據(jù)結(jié)構(gòu)
這里的數(shù)據(jù)結(jié)構(gòu)核心是一個(gè)k*m的二維數(shù)組counters
,k是哈希函數(shù)數(shù)量,m是數(shù)組每一行的長(zhǎng)度;countersLen其實(shí)就是m;hashs是哈希函數(shù)列表;maxCount是當(dāng)前類型的最大值,比如uint8就是255,下面的計(jì)算需要用到它。
type Counter[T constraints.Unsigned] struct { counters [][]T countersLen uint64 // 計(jì)數(shù)器長(zhǎng)度 hashs []*hash.Hash // 哈希函數(shù)列表 maxCount T // 最大計(jì)數(shù)值 }
初始化
我們首先使用上面提到的兩個(gè)公式計(jì)算數(shù)組每一行長(zhǎng)度和哈希函數(shù)的數(shù)量,然后初始化哈希函數(shù)列表和二維數(shù)組。
// 創(chuàng)建一個(gè)計(jì)數(shù)器 // size:數(shù)據(jù)流大小 // errorRange:計(jì)數(shù)值誤差范圍(會(huì)超過(guò)真實(shí)計(jì)數(shù)值) // errorRate:錯(cuò)誤率 func New[T constraints.Unsigned](size uint64, errorRange T, errorRate float64) *Counter[T] { // 計(jì)數(shù)器長(zhǎng)度 countersLen := uint64(math.Ceil(math.E / (float64(errorRange) / float64(size)))) // 哈希個(gè)數(shù) hashsCnt := int(math.Ceil(math.Log(1.0 / errorRate))) hashs := make([]*hash.Hash, hashsCnt) counters := make([][]T, hashsCnt) for i := 0; i < hashsCnt; i++ { hashs[i] = hash.New() counters[i] = make([]T, countersLen) } return &Counter[T]{ counters: counters, countersLen: countersLen, hashs: hashs, maxCount: T(0) - 1, } }
增加計(jì)數(shù)
對(duì)于一個(gè)元素,我們需要把它根據(jù)每個(gè)哈希函數(shù)計(jì)算出它在每一行數(shù)組的位置,然后增加對(duì)應(yīng)位置計(jì)數(shù)器的計(jì)數(shù)值。
這里需要注意的是,計(jì)數(shù)值可能會(huì)溢出,因此我們首先判斷是否溢出,如果溢出則設(shè)置為最大值。
// 增加元素的計(jì)數(shù) func (c *Counter[T]) Add(b []byte, val T) { for i, h := range c.hashs { index := h.Sum64(b) % c.countersLen if c.counters[i][index]+val <= c.counters[i][index] { c.counters[i][index] = c.maxCount } else { c.counters[i][index] += val } } }
估算計(jì)數(shù)
同增加計(jì)數(shù)原理,把元素根據(jù)哈希函數(shù)映射到每一行數(shù)組的對(duì)應(yīng)位置,然后選擇所有行中最小的那個(gè)計(jì)數(shù)值。
// 估算元素的計(jì)數(shù) func (c *Counter[T]) Estimate(b []byte) T { minCount := c.maxCount for i, h := range c.hashs { index := h.Sum64(b) % c.countersLen count := c.counters[i][index] if count == 0 { return 0 } minCount = mmath.Min(minCount, count) } return minCount }
到此這篇關(guān)于GO CountMinSketch計(jì)數(shù)器(布隆過(guò)濾器思想的近似計(jì)數(shù)器)的文章就介紹到這了,更多相關(guān)GO CountMinSketch內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Golang并發(fā)操作中常見(jiàn)的讀寫(xiě)鎖詳析
Golang中的鎖機(jī)制主要包含互斥鎖和讀寫(xiě)鎖互斥鎖互斥鎖是傳統(tǒng)并發(fā)程序?qū)蚕碣Y源進(jìn)行控制訪問(wèn)的主要手段,這篇文章主要給大家介紹了關(guān)于Golang并發(fā)操作中常見(jiàn)的讀寫(xiě)鎖的相關(guān)資料,需要的朋友可以參考下2021-08-08Go并發(fā)原語(yǔ)之SingleFlight請(qǐng)求合并方法實(shí)例
本文我們來(lái)學(xué)習(xí)一下 Go 語(yǔ)言的擴(kuò)展并發(fā)原語(yǔ):SingleFlight,SingleFlight 的作用是將并發(fā)請(qǐng)求合并成一個(gè)請(qǐng)求,以減少重復(fù)的進(jìn)程來(lái)優(yōu)化 Go 代碼2023-12-12基于HLS創(chuàng)建Golang視頻流服務(wù)器的優(yōu)缺點(diǎn)
HLS 是 HTTP Live Streaming 的縮寫(xiě),是蘋果開(kāi)發(fā)的一種基于 HTTP 的自適應(yīng)比特率流媒體傳輸協(xié)議。這篇文章主要介紹了基于 HLS 創(chuàng)建 Golang 視頻流服務(wù)器,需要的朋友可以參考下2021-08-08Go編寫(xiě)定時(shí)器與定時(shí)任務(wù)詳解(附第三方庫(kù)gocron用法)
當(dāng)需要每天執(zhí)行定時(shí)任務(wù)的時(shí)候就需要定時(shí)器來(lái)處理了,周期任務(wù),倒計(jì)時(shí)任務(wù),定點(diǎn)任務(wù)等,下面這篇文章主要給大家介紹了關(guān)于Go編寫(xiě)定時(shí)器與定時(shí)任務(wù)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-07-07go語(yǔ)言的工作空間和GOPATH環(huán)境變量介紹
這篇文章主要介紹了go語(yǔ)言的工作空間和GOPATH環(huán)境變量介紹,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12