Documentation
¶
Overview ¶
Package sketch 提供监控/风控常用的概率数据结构:用极小、常量级内存换取"近似但够用"的答案。
- HyperLogLog:基数估计(去重计数)——UV、独立 IP、活跃用户;几 KB 估计到百万级,误差 ~1%;
- CountMin:频率估计——热 key / Top-N / 限流分桶;常量内存,只会高估不会低估;
- Reservoir:蓄水池采样——从未知长度的流里等概率抽 K 条(日志/trace 采样、限流下采样)。
均为纯标准库。哈希用固定的 FNV-1a + splitmix64 收敛器(确定性,故 HLL 可跨实例 Merge)。
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CountMin ¶
type CountMin struct {
// contains filtered or unexported fields
}
CountMin(Count-Min Sketch)用常量内存估计每个 key 的累计频率:d 行 × w 列计数器, 每个 key 在每行哈希到一个计数器并累加,查询取各行最小值。只会**高估、不会低估** (碰撞使计数偏大),适合"热 key / Top-N / 限流分桶"这类"宁可高估"的场景。并发不安全。
func NewCountMin ¶
NewCountMin 按 width×depth 直接创建。width/depth<=0 会被夹到 1。
func NewCountMinWithError ¶
NewCountMinWithError 按误差目标创建:估计值以概率 (1-delta) 不超过真实值 + epsilon*总量。 width=ceil(e/epsilon),depth=ceil(ln(1/delta))。例如 epsilon=0.001,delta=0.01 → ~2718×5。
type HyperLogLog ¶
type HyperLogLog struct {
// contains filtered or unexported fields
}
HyperLogLog 估计集合基数(去重元素个数)。用 m=2^precision 个 6-bit 寄存器(这里每个用一个 uint8)记录哈希尾部前导零的最大值,据此估算基数。precision=14 时约 16KB 内存,标准误差 ~0.81%, 可估计到数十亿量级。并发不安全(需要并发时由调用方加锁,或每 goroutine 一个再 Merge)。
func NewHyperLogLog ¶
func NewHyperLogLog(precision int) *HyperLogLog
NewHyperLogLog 创建 HLL。precision 取值 [4,16],越大越精确也越占内存(寄存器数=2^precision)。 越界会被夹到区间内;precision=0 用默认 14。
func (*HyperLogLog) AddHash ¶
func (h *HyperLogLog) AddHash(x uint64)
AddHash 加入一个已算好的 64 位哈希(调用方自带高质量哈希时用)。
func (*HyperLogLog) Merge ¶
func (h *HyperLogLog) Merge(other *HyperLogLog) error
Merge 把 other 并入当前 HLL(逐寄存器取最大)。要求二者 precision 相同。
type Reservoir ¶
type Reservoir[T any] struct { // contains filtered or unexported fields }
Reservoir 蓄水池采样:从长度未知的流里等概率抽取至多 k 个元素(算法 R)。任意时刻已见 n 个元素时, 池中每个元素都以 k/n 的概率留存,且无需预先知道 n、无需缓存整条流。适合日志/trace 采样、 限流下采样等"边流边采"场景。并发安全。
func NewReservoir ¶
NewReservoir 创建容量为 k 的蓄水池(k<=0 会被夹到 1)。
Source Files