詳解Golang如何實現(xiàn)一個環(huán)形緩沖器
背景
環(huán)形緩沖器（ringr buffer）是一種用于表示一個固定尺寸、頭尾相連的緩沖區(qū)的數(shù)據(jù)結構，適合緩存數(shù)據(jù)流。
在使用上，它就是一個固定長度的FIFO隊列：
在邏輯上，我們可以把它當成是一個環(huán)，上面有兩個指針代表當前寫索引和讀索引：
在實現(xiàn)上，我們一般是使用一個數(shù)組去實現(xiàn)這個環(huán)，當索引到達數(shù)組尾部的時候，則重新設置為頭部：
kfifo實現(xiàn)
kfifo是Linux內(nèi)核的隊列實現(xiàn)，它具有以下特性：
- 固定長度：長度是固定的，而且是向上取最小的2的平方，主要是為了實現(xiàn)快速取余。
- 無鎖：在單生產(chǎn)者和單消費者的情況下，是不需要加鎖的。主要是因為索引in和out是不回退的，一直往前。
- 快速取余：我們都直到到達隊列末尾的時候，索引需要回退到開頭。最簡單的實現(xiàn)方式就是對索引取余，比如索引in現(xiàn)在是8，隊列長度是8，
in%len(q)即可回退到開頭，但是取余操作%還是比較耗時的，因此kfifo使用in&mask實現(xiàn)快速取余，其中mask=len(q)-1。
無鎖
上面我們說到，這個無鎖是有條件的，也就是必須在單生產(chǎn)者單消費者情況下。這種情況下，同一時刻最多只可能會有一個寫操作和一個讀操作。但是在某一個讀操作（或?qū)懖僮鳎┑钠陂g，可能會有多個寫操作（或讀操作）發(fā)生。
因為索引in和out是不回退的，因此in一直會在out前面（或者重合）。而且in只被寫操作修改，out只被讀操作修改，因此不會沖突。
這里可能有人會擔心索引溢出的問題，比如in到達math.MaxUint64，再+1則回到0。但是其實并不影響in和out之間的距離：
package main
import (
"fmt"
"math"
)
func main() {
var in uint = math.MaxUint64
var out uint = math.MaxUint64 - 1
fmt.Println(in - out) // 1
in++
fmt.Println(in - out) // 2
out++
fmt.Println(in - out) // 1
}當然如果連續(xù)兩次溢出，就會出現(xiàn)問題。但是由于數(shù)組長度是int類型，因此也沒辦法超過math.MaxUint64，也就是in和out之間的距離最多也就是2^62，因為math.MaxInt64是2^63-1，沒辦法向上取2的平方了。因此也不會出現(xiàn)溢出兩倍math.MaxUint64的情況，早在溢出之前就隊列滿了。
快速取余
前面提到取余是通過in&mask實現(xiàn)的，這有一個前提條件，也就是長度必須是2的次方，因此在創(chuàng)建數(shù)組的時候，長度會向上取最小的2的平方。例如一個長度為8的kfifo，在二進制表示下：
len = 0000 1000 // 十進制8，隊列長度 mask = 0000 0111 // 十進制7，掩碼 in = 0000 0000 // 十進制0，寫索引 in & mask => 0000 0000 // 十進制0，使用 & mask in % len => 0000 0000 // 十進制0，使用 % len in = 0000 0001 // 十進制1，寫索引 in & mask => 0000 0001 // 十進制1，使用 & mask in % len => 0000 0001 // 十進制1，使用 % len in = 0000 0001 // 十進制1，寫索引 in & mask => 0000 0001 // 十進制1，使用 & mask in % len => 0000 0001 // 十進制1，使用 % len in = 0000 1000 // 十進制8，寫索引 in & mask => 0000 0000 // 十進制0，使用 & mask in % len => 0000 0000 // 十進制0，使用 % len in = 0001 0001 // 十進制17，寫索引 in & mask => 0000 0001 // 十進制1，使用 & mask in % len => 0000 0001 // 十進制1，使用 % len
可以看到，使用& mask的效果是和% len一樣的。
然后我們做一個簡單的性能測試：
package main
import "testing"
var (
Len = 8
Mask = Len - 1
In = 8 - 5
)
// % len
func BenchmarkModLen(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = In % Len
}
}
// & Mask
func BenchmarkAndMask(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = In & Mask
}
}測試結果：
BenchmarkModLen-8 1000000000 0.3434 ns/op
BenchmarkAndMask-8 1000000000 0.2520 ns/op
可以看到& mask性能確實比% len好很多，這也就是為什么要用& Mask來實現(xiàn)取余的原因了。
數(shù)據(jù)結構
數(shù)據(jù)結構和上面介紹的一樣，in、out標識當前讀寫的位置；mask是size-1，用于取索引，比%size更加高效；
type Ring[T any] struct {
in uint64 // 寫索引
out uint64 // 讀索引
mask uint64 // 掩碼，用于取索引，代替%size
size uint64 // 長度
data []T // 數(shù)據(jù)
}Push()
Push()操作很簡單，首先r.in & r.mask得到寫索引，讓寫索引前進一格，然后存入數(shù)據(jù)。
// 插入元素到隊尾
func (r *Ring[T]) Push(e T) {
if r.Full() {
panic("ring full")
}
in := r.in & r.mask
r.in++
r.data[in] = e
}Pop()
Pop()操作同理，根據(jù)r.out & r.mask得到讀索引，讓讀索引前進一格，然后讀取數(shù)據(jù)。
// 彈出隊頭元素
func (r *Ring[T]) Pop() T {
if r.Empty() {
panic("ring emtpy")
}
out := r.out & r.mask
r.out++
return r.data[out]
}性能測試
Round實現(xiàn)是使用& mask，同時長度會向上取2的平方；Fix實現(xiàn)是使用% size保持參數(shù)的長度。
測試代碼是不斷的Push()然后Pop()：
func BenchmarkRoundPushPop(b *testing.B) {
for i := 0; i < b.N; i++ {
r := New[int](RoundFixSize)
for j := 0; j < RoundFixSize; j++ {
r.Push(j)
}
for j := 0; j < RoundFixSize; j++ {
r.Pop()
}
}
}測試結果：& mask的性能明顯好于% size。
BenchmarkRoundPushPop-8 2544 405621 ns/op // & mask
BenchmarkFixPushPop-8 678 1740489 ns/op // % size
無界環(huán)形緩沖器
我們可以在寫數(shù)據(jù)的時候判斷是否空間已滿，如果已滿我們可以進行動態(tài)擴容，從而實現(xiàn)一個無界環(huán)形緩沖器。
Push()
在Push()時檢查到空間滿時，調(diào)用grow()擴展空間即可：
// 插入元素到隊尾
func (r *Ring[T]) Push(e T) {
if r.Full() {
// 擴展空間
r.Grow(r.Cap() + 1)
}
in := r.in % r.size
r.in++
r.data[in] = e
}grow()
擴容一般是擴展為當前容量的兩倍，然后把原來數(shù)據(jù)copy()到新的數(shù)組，更新字段即可：
// 擴容
func (r *Ring[T]) Grow(minSize uint64) {
size := mmath.Max(r.size*2, minSize)
if size > MaxSize {
panic("size is too large")
}
if size < 2 {
size = 2
}
// 還沒容量，直接申請，因為不需要遷移元素
if r.size == 0 {
r.data = make([]T, size)
r.size = size
return
}
data := make([]T, size)
out := r.out % r.size
len := r.Len()
copied := copy(data[:len], r.data[out:])
copy(data[copied:len], r.data)
r.out = 0
r.in = len
r.size = size
r.data = data
}線程安全性
由于可能會動態(tài)擴容，需要修改out、in指針，因此需要加鎖保證安全。
代碼地址
https://github.com/jiaxwu/gommon/tree/main/container/ringbuffer
到此這篇關于詳解Golang如何實現(xiàn)一個環(huán)形緩沖器的文章就介紹到這了,更多相關Golang環(huán)形緩沖器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了創(chuàng)建Go工程化項目布局詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
這篇文章主要介紹了Golang連接Redis數(shù)據(jù)庫的方法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
這篇文章主要為大家詳細介紹了golang中單機鎖的具體實現(xiàn)的相關知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2025-03-03
Go語言保證了既能到達靜態(tài)編譯語言的安全和性能，又達到了動態(tài)語言開發(fā)速度和易維護性，有人形容Go語言：Go=?C?+?Python?,?說明Go語言既有C靜態(tài)語言程序的運行速度，又能達到Python動態(tài)語言的快速開發(fā)，這篇文章主要介紹了Go介紹和環(huán)境配置,需要的朋友可以參考下2022-07-07
Go 的運行時的當前設計，假定程序員自己負責檢測何時終止一個 goroutine 以及何時終止該程序。有時候我們需要的是使程序阻塞在這一行，本文就來詳細的介紹一下，感興趣的可以了解一下2021-12-12
Go簡單實現(xiàn)協(xié)程池的實現(xiàn)示例
本文主要介紹了Go簡單實現(xiàn)協(xié)程池的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
本文介紹一款工具?go-callvis,它能夠?qū)?Go?代碼的調(diào)用關系可視化出來,并提供了可交互式的?web?服務,在接手他人代碼或調(diào)研一些開源項目時,如果能夠理清其中的代碼調(diào)用鏈路,這將加速我們對實現(xiàn)的理解2024-01-01
Zap是我個人比較喜歡的日志庫，是uber開源的，有較好的性能，在項目開發(fā)中，經(jīng)常需要把程序運行過程中各種信息記錄下來，有了詳細的日志有助于問題排查和功能優(yōu)化，但如何選擇和使用性能好功能強大的日志庫，這個就需要我們從多角度考慮2023-03-03
本文我們來使用client-go實現(xiàn)一個自定義控制器，通過判斷service的Annotations屬性是否包含ingress/http，如果包含則創(chuàng)建ingress，如果不包含則不創(chuàng)建，對client go自定義控制器相關知識感興趣的朋友一起看看吧2022-05-05
這篇文章主要為大家介紹了Golang官方限流器庫使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08