victoriaMetrics庫(kù)布隆過(guò)濾器初始化及使用詳解
代碼路徑:/lib/bloomfilter
概述
victoriaMetrics的vmstorage組件會(huì)接收上游傳遞過(guò)來(lái)的指標(biāo),在現(xiàn)實(shí)場(chǎng)景中,指標(biāo)或瞬時(shí)指標(biāo)的數(shù)量級(jí)可能會(huì)非??植?,如果不限制緩存的大小,有可能會(huì)由于cache miss而導(dǎo)致出現(xiàn)過(guò)高的slow insert。
為此,vmstorage提供了兩個(gè)參數(shù):maxHourlySeries和maxDailySeries,用于限制每小時(shí)/每天添加到緩存的唯一序列。
唯一序列指表示唯一的時(shí)間序列,如metrics{label1="value1",label2="value2"}屬于一個(gè)時(shí)間序列,但多條不同值的metrics{label1="value1",label2="value2"}屬于同一條時(shí)間序列。victoriaMetrics使用如下方式來(lái)獲取時(shí)序的唯一標(biāo)識(shí):
func getLabelsHash(labels []prompbmarshal.Label) uint64 {
bb := labelsHashBufPool.Get()
b := bb.B[:0]
for _, label := range labels {
b = append(b, label.Name...)
b = append(b, label.Value...)
}
h := xxhash.Sum64(b)
bb.B = b
labelsHashBufPool.Put(bb)
return h
}
限速器的初始化
victoriaMetrics使用了一個(gè)類(lèi)似限速器的概念,限制每小時(shí)/每天新增的唯一序列,但與普通的限速器不同的是,它需要在序列級(jí)別進(jìn)行限制,即判斷某個(gè)序列是否是新的唯一序列,如果是,則需要進(jìn)一步判斷一段時(shí)間內(nèi)緩存中新的時(shí)序數(shù)目是否超過(guò)限制,而不是簡(jiǎn)單地在請(qǐng)求層面進(jìn)行限制。
hourlySeriesLimiter = bloomfilter.NewLimiter(*maxHourlySeries, time.Hour) dailySeriesLimiter = bloomfilter.NewLimiter(*maxDailySeries, 24*time.Hour)
下面是新建限速器的函數(shù),傳入一個(gè)最大(序列)值,以及一個(gè)刷新時(shí)間。該函數(shù)中會(huì):
- 初始化一個(gè)限速器,限速器的最大元素個(gè)數(shù)為
maxItems - 則啟用了一個(gè)goroutine,當(dāng)時(shí)間達(dá)到
refreshInterval時(shí)會(huì)重置限速器
func NewLimiter(maxItems int, refreshInterval time.Duration) *Limiter {
l := &Limiter{
maxItems: maxItems,
stopCh: make(chan struct{}),
}
l.v.Store(newLimiter(maxItems)) //1
l.wg.Add(1)
go func() {
defer l.wg.Done()
t := time.NewTicker(refreshInterval)
defer t.Stop()
for {
select {
case <-t.C:
l.v.Store(newLimiter(maxItems))//2
case <-l.stopCh:
return
}
}
}()
return l
}
限速器只有一個(gè)核心函數(shù)Add,當(dāng)vmstorage接收到一個(gè)指標(biāo)之后,會(huì)(通過(guò)getLabelsHash計(jì)算該指標(biāo)的唯一標(biāo)識(shí)(h),然后調(diào)用下面的Add函數(shù)來(lái)判斷該唯一標(biāo)識(shí)是否存在于緩存中。
如果當(dāng)前存儲(chǔ)的元素個(gè)數(shù)大于等于允許的最大元素,則通過(guò)過(guò)濾器判斷緩存中是否已經(jīng)存在該元素;否則將該元素直接加入過(guò)濾器中,后續(xù)允許將該元素加入到緩存中。
func (l *Limiter) Add(h uint64) bool {
lm := l.v.Load().(*limiter)
return lm.Add(h)
}
func (l *limiter) Add(h uint64) bool {
currentItems := atomic.LoadUint64(&l.currentItems)
if currentItems >= uint64(l.f.maxItems) {
return l.f.Has(h)
}
if l.f.Add(h) {
atomic.AddUint64(&l.currentItems, 1)
}
return true
}
上面的過(guò)濾器采用的是布隆過(guò)濾器,核心函數(shù)為Has和Add,分別用于判斷某個(gè)元素是否存在于過(guò)濾器中,以及將元素添加到布隆過(guò)濾器中。
過(guò)濾器的初始化函數(shù)如下,bitsPerItem是個(gè)常量,值為16。bitsCount統(tǒng)計(jì)了過(guò)濾器中的總bit數(shù),每個(gè)bit表示某個(gè)值的存在性。bits以64bit為單位的(后續(xù)稱(chēng)之為slot,目的是為了在bitsCount中快速檢索目標(biāo)bit)。計(jì)算bits時(shí)加上63的原因是為了四舍五入向上取值,比如當(dāng)maxItems=1時(shí)至少需要1個(gè)unit64的slot。
func newFilter(maxItems int) *filter {
bitsCount := maxItems * bitsPerItem
bits := make([]uint64, (bitsCount+63)/64)
return &filter{
maxItems: maxItems,
bits: bits,
}
}
為什么bitsPerItem為16?這篇文章給出了如何計(jì)算布隆過(guò)濾器的大小。在本代碼中,k為4(hashesCount),期望的漏失率為0.003(可以從官方的filter_test.go中看出),則要求總存儲(chǔ)和總元素的比例為15,為了方便檢索slot(64bit,為16的倍數(shù)),將之設(shè)置為16。
if p > 0.003 {
t.Fatalf("too big false hits share for maxItems=%d: %.5f, falseHits: %d", maxItems, p, falseHits)
}

下面是過(guò)濾器的Add操作,目的是在過(guò)濾器中添加某個(gè)元素。Add函數(shù)中沒(méi)有使用多個(gè)哈希函數(shù)來(lái)計(jì)算元素的哈希值,轉(zhuǎn)而改變同一個(gè)元素的值,然后對(duì)相應(yīng)的值應(yīng)用相同的哈希函數(shù),元素改變的次數(shù)受hashesCount的限制。
- 獲取過(guò)濾器的完整存儲(chǔ),并轉(zhuǎn)換為以bit單位
- 將元素
h轉(zhuǎn)換為byte數(shù)組,便于xxhash.Sum64計(jì)算 - 后續(xù)將執(zhí)行hashesCount次哈希,降低漏失率
- 計(jì)算元素h的哈希
- 遞增元素
h,為下一次哈希做準(zhǔn)備 - 取余法獲取元素的bit范圍
- 獲取元素所在的slot(即uint64大小的bit范圍)
- 獲取元素所在的slot中的bit位,該位為1表示該元素存在,為0表示該元素不存在
- 獲取元素所在bit位的掩碼
- 加載元素所在的slot的數(shù)值
- 如果
w & mask結(jié)果為0,說(shuō)明該元素不存在, - 將元素所在的slot(
w)中的元素所在的bit位(mask)置為1,表示添加了該元素 - 由于
Add函數(shù)可以并發(fā)訪(fǎng)問(wèn),因此bits[i]有可能被其他操作修改,因此需要通過(guò)重新加載(14)并通過(guò)循環(huán)來(lái)在bits[i]中設(shè)置該元素的存在性
func (f *filter) Add(h uint64) bool {
bits := f.bits
maxBits := uint64(len(bits)) * 64 //1
bp := (*[8]byte)(unsafe.Pointer(&h))//2
b := bp[:]
isNew := false
for i := 0; i < hashesCount; i++ {//3
hi := xxhash.Sum64(b)//4
h++ //5
idx := hi % maxBits //6
i := idx / 64 //7
j := idx % 64 //8
mask := uint64(1) << j //9
w := atomic.LoadUint64(&bits[i])//10
for (w & mask) == 0 {//11
wNew := w | mask //12
if atomic.CompareAndSwapUint64(&bits[i], w, wNew) {//13
isNew = true//14
break
}
w = atomic.LoadUint64(&bits[i])//14
}
}
return isNew
}
看懂了Add函數(shù),Has就相當(dāng)簡(jiǎn)單了,它只是Add函數(shù)的縮減版,無(wú)需設(shè)置bits[i]:
func (f *filter) Has(h uint64) bool {
bits := f.bits
maxBits := uint64(len(bits)) * 64
bp := (*[8]byte)(unsafe.Pointer(&h))
b := bp[:]
for i := 0; i < hashesCount; i++ {
hi := xxhash.Sum64(b)
h++
idx := hi % maxBits
i := idx / 64
j := idx % 64
mask := uint64(1) << j
w := atomic.LoadUint64(&bits[i])
if (w & mask) == 0 {
return false
}
}
return true
}
總結(jié)
由于victoriaMetrics的過(guò)濾器采用的是布隆過(guò)濾器,因此它的限速并不精準(zhǔn),在源碼條件下, 大約有3%的偏差。但同樣地,由于采用了布隆過(guò)濾器,降低了所需的內(nèi)存以及相關(guān)計(jì)算資源。此外victoriaMetrics的過(guò)濾器實(shí)現(xiàn)了并發(fā)訪(fǎng)問(wèn)。
在大流量場(chǎng)景中,如果需要對(duì)請(qǐng)求進(jìn)行相對(duì)精準(zhǔn)的過(guò)濾,可以考慮使用布隆過(guò)濾器,降低所需要的資源,但前提是過(guò)濾的結(jié)果能夠忍受一定程度的漏失率。
以上就是victoriaMetrics庫(kù)布隆過(guò)濾器初始化及使用詳解的詳細(xì)內(nèi)容,更多關(guān)于victoriaMetrics庫(kù)布隆過(guò)濾器的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Go開(kāi)發(fā)環(huán)境搭建詳細(xì)介紹
由于目前網(wǎng)上Go的開(kāi)發(fā)環(huán)境搭建文章很多,有些比較老舊,都是基于 GOPATH的,給新入門(mén)的同學(xué)造成困擾。以下為2023 版 Go 開(kāi)發(fā)環(huán)境搭建,可參照此教程搭建Go開(kāi)發(fā)環(huán)境,有需要的朋友可以參考閱讀2023-04-04
golang利用unsafe操作未導(dǎo)出變量-Pointer使用詳解
這篇文章主要給大家介紹了關(guān)于golang利用unsafe操作未導(dǎo)出變量-Pointer使用的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2018-08-08
詳解Go語(yǔ)言中Get/Post請(qǐng)求測(cè)試
這篇文章主要為大家詳細(xì)介紹了Go語(yǔ)言中的環(huán)境安裝以及Get和Post請(qǐng)求接口的測(cè)試,文中的示例代碼講解詳細(xì),感興趣的可以跟隨小編一起學(xué)習(xí)一下2022-06-06
Golang中處理import自定義包出錯(cuò)問(wèn)題的解決辦法
最近開(kāi)始使用Go/GoLand在import自定義包時(shí)出現(xiàn)各種狀況,下面這篇文章主要給大家介紹了關(guān)于Golang中處理import自定義包出錯(cuò)問(wèn)題的解決辦法,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11
Go語(yǔ)言中的錯(cuò)誤處理最佳實(shí)踐詳解
這篇文章主要為大家詳細(xì)介紹了Go語(yǔ)言中的錯(cuò)誤處理的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),對(duì)我們深入了解Go語(yǔ)言有一定的幫助,需要的可以參考下2023-08-08
go語(yǔ)言中fallthrough的用法說(shuō)明
這篇文章主要介紹了go語(yǔ)言中fallthrough的用法說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-05-05
一文帶你掌握Go語(yǔ)言I/O操作中的io.Reader和io.Writer
在?Go?語(yǔ)言中,io.Reader?和?io.Writer?是兩個(gè)非常重要的接口,它們?cè)谠S多標(biāo)準(zhǔn)庫(kù)中都扮演著關(guān)鍵角色,下面就跟隨小編一起學(xué)習(xí)一下它們的使用吧2025-01-01

