企业官网建设流程全解析

在 Go 中使用 bitset 位集：从基础操作到高性能集合运算与序列化

【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki

导读

bitset是 Go 语言生态中用于「非负整数 → 布尔值」映射的高性能位集库，相比map[uint]bool在内存占用与运算速度上均有数量级优势。本仓库（Grafana Loki）以依赖形式引入了github.com/bits-and-blooms/bitset（v1.25.0），在布隆过滤器、索引与查询的位级过滤等场景中作为底层数据结构使用。阅读本文后，你将掌握位集的创建、增删改查、集合运算、遍历、序列化与并发安全边界，并能直接在 Go 项目中落地这套方案。

位集是什么：为什么比map[uint]bool更高效

包级文档对位集的定义非常直白："Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool."其核心思路是把布尔值按位紧凑地存储，而不是为每个元素单独分配一个 bool。

从源码看，BitSet的内部结构只有两个字段（vendor/github.com/bits-and-blooms/bitset/bitset.go#L86-L90）：

const wordSize = 64 const wordBytes = wordSize / 8 type BitSet struct { length uint set []uint64 }

即底层是[]uint64数组，每个 64 位字（word）可表示 64 个布尔位；length记录当前逻辑位长度。因此「N 位所需内存至少为 N/8 字节」，且数组只增长到「最大已设置位的下标 + 1」对应的字数，按需分配（extendSet负责扩容）。相比map[uint]bool每个条目至少占用一个指针槽位和一个 bool 值（通常数十字节），位集在密集整型集合场景下内存可缩减一个数量级以上，同时得益于math/bits的硬件指令级位运算（见popcnt.go中基于bits.OnesCount64的种群计数实现），集合基数统计（Count）与各类集合运算都能以 word 粒度并行推进。

Loki 仓库在 go.mod#L185 中以间接依赖形式引入github.com/bits-and-blooms/bitset v1.25.0，位集正是这类日志索引/过滤系统中布隆过滤器等位密集型数据结构的常用底层载体。

快速上手：安装与第一个示例

安装方式（v1.25.0 对应本仓库 vendor 目录中锁定的版本）：

go get github.com/bits-and-blooms/bitset

原文档给出了一个非常经典的「Go Fish」示例——用它模拟抽牌与配对判断，同时演示Set、Test、Clear三个最基础的原子操作：

package main import ( "fmt" "math/rand" "github.com/bits-and-blooms/bitset" ) func main() { fmt.Printf("Hello from BitSet!\n") var b bitset.BitSet // play some Go Fish for i := 0; i < 100; i++ { card1 := uint(rand.Intn(52)) card2 := uint(rand.Intn(52)) b.Set(card1) if b.Test(card2) { fmt.Println("Go Fish!") } b.Clear(card1) } }

注意这里var b bitset.BitSet直接使用了零值——文档与源码均明确「零值即长度为 0 的空集合」，safeSet会在首次使用时自动将set初始化为非 nil（bitset.go#L95-L101）。

创建带初始容量提示的位集使用bitset.New(length)，其实现为make([]uint64, wordsNeeded(length))，即按(length+63)/64个字预分配，避免后续频繁扩容。此外还有MustNew（panic 版本）、From/FromWithLength（从既有[]uint64字数组直接构造，适合高级用户零拷贝复用内存）等构造函数。

核心操作速查：设置、清除、翻转与测试

位集对单个整数提供四类最基础的原子方法，且Set、Clear、Flip返回*BitSet支持链式调用：

从实现看，Test通过wordsIndex(i)定位字、uint64(1) << (i & wordMask)计算掩码后做与运算；Set则先extendSet(i)确保容量足够，再对目标字做或运算。链式调用的典型用法：

b.Set(10).Set(11) // 同时设置第 10、11 位 b.Flip(3).Clear(7) // 翻转第 3 位，再清除第 7 位 if b.Test(10) { // 判断第 10 位是否被设置 // ... }

此外还有面向区间的SetRange(start, end)、FlipRange(start, end)，以及全量操作的SetAll()/ClearAll()。针对长度收缩，Shrink(lastbitindex)可以按给定下标裁剪位集，Compact()则会裁剪尾部多余的零字——文档明确位集「从不自动收缩」，在高频增删场景下这两个方法用于手动归还内存。

遍历置 1 的位有两种方式。经典写法配合NextSet从指定起点向后扫描：

for i, e := b.NextSet(0); e; i, e = b.NextSet(i+1) { fmt.Println("The following bit is set:", i) }

如果使用 Go 1.23 及以上，则可以直接用 range-over-func 语法：

for i := range b.EachSet() {}

EachSet定义在 vendor/github.com/bits-and-blooms/bitset/bitset_iter.go#L19-L31，它以bits.TrailingZeros64逐字跳过连续 0 位，按升序 yield 每个置 1 位的下标；提前 break 会停止迭代。该文件带有//go:build go1.23构建标签，因此只在 Go 1.23+ 编译环境中生效。反向遍历则可用PreviousSet/PreviousClear。对于需要批量消费的场景，NextSetMany(i, buffer)可以一次填充一个[]uint缓冲，减少逐位调用开销。

集合运算：交集、并集、差集、补集与对称差

位集真正的价值在于把集合运算转化为 word 级位的按位与/或/异或/取反，这是map无法比拟的。完整的方法族如下：

原文档中的示例验证了交集语义：

if b.Intersection(bitset.New(100).Set(10)).Count() == 1 { fmt.Println("Intersection works.") } else { fmt.Println("Intersection doesn't work???") }

实现细节上（bitset.go#L1010-L1065 附近）：返回新集合的版本会先按长度对两个操作数排序，再以较短的集合为基准进行位运算，从而减少遍历字数；原地版本则把结果写回调用者。基数版本（如IntersectionCardinality）不会物化中间结果，直接逐字bits.OnesCount64累加，适合「只想知道交叠数量」的判断场景——例如布隆过滤器多块之间做存在性验证时只关心交集是否非空。

集合查询方法还包括：

• Any()— 是否存在置 1 的位
• All()— 是否全部位均为 1
• None()— 是否没有任何置 1 的位
• IsSuperSet(other)/IsStrictSuperSet(other)— 是否为（严格）超集
• Equal(other)— 两个位集是否相等
• Clone()/Copy(c)/CopyFull(c)— 拷贝（Copy返回被复制的位数，CopyFull保证长度一致）
• Rank(index)/Select(index)— 前 index 位的置 1 计数 / 第 index 个置 1 位的下标（见 bitset.go#L1459-L1498），是位集上「双向映射」的经典加速手段
• DumpAsBits()— 以 '0'/'1' 字符串输出全部位，便于调试

另一个值得一提的高级接口是Words()（替代已废弃的Bytes()）与SetBitsetFrom(buf []uint64)：前者直接暴露内部[]uint64字数组（非拷贝，改动会影响位集），后者可用外部字数组就地填充位集，两者均标注「面向高级用户」，可用于零拷贝集成其他位级结构。

序列化：WriteTo / ReadFrom 与编码选项

位集可以安全、可移植地序列化为字节流。写入的典型模式（原文档示例）：

const length = 9585 const oneEvery = 97 bs := bitset.New(length) // Add some bits for i := uint(0); i < length; i += oneEvery { bs = bs.Set(i) } var buf bytes.Buffer n, err := bs.WriteTo(&buf) if err != nil { // failure } // Here n == buf.Len()

读取回来：

// Read back from buf bs = bitset.New() n, err = bs.ReadFrom(&buf) if err != nil { // error } // n is the number of bytes read

从实现看（bitset.go#L1332-L1405），WriteTo的流格式为：先写一个uint64长度（按当前字节序），随后写wordCount()个 64 位字；ReadFrom反向读取，若当前实例容量不足会自动扩展（extendSetMaybe），并且尽力复用既有实例的内存以减少分配——这正是ReadFrom设计为方法而非构造函数的原因。返回值是写入/读取的字节数。

关于字节序与编码，包提供了全局配置函数：

• BigEndian()/LittleEndian()/BinaryOrder()— 二进制序列化字节序，默认binary.BigEndian
• Base64StdEncoding()— 切换 JSON 编解码的 base64 编码方式，默认base64.URLEncoding

这两个开关分别由包级变量binaryOrder与base64Encoding控制（bitset.go#L67-L71），注意它们是包级全局状态，修改会影响包内所有实例的序列化行为。除io.Writer/io.Reader流接口外，位集还实现了标准接口encoding.BinaryMarshaler（MarshalBinary/UnmarshalBinary）与encoding/json（MarshalJSON/UnmarshalJSON，JSON 形式为 base64 字符串），可直接用于json.Marshal与gob等场景。BinaryStorageSize()可预估二进制存储所需的字节数。

性能提示：当写入/读取目标是文件或网络连接时，建议先用bufio包装，减少系统调用次数：

f, err := os.Create("myfile") w := bufio.NewWriter(f) f, err := os.Open("myfile") r := bufio.NewReader(f)

内存模型与压缩位集的选择

内存上需要牢记两个约束：

1. N 位的位集至少占用 N/8 字节；
2. 位集长度始终≥「已访问的最大位下标 + 1」——也就是说，Set(1<<31)一次就会触发数 GB 级的扩容。文档明确警告："it is possible to run out of memory while using a bitset"。

因此对「位稀疏」的大整数集合，直接使用bitset可能并不划算，更合适的选择是压缩位图 Roaring bitmap 及其 Go 实现RoaringBitmap/roaring。两者可相互转换：

mybitset := roaringbitmap.ToBitSet() // Roaring -> 常规位集 newroaringbitmap := roaring.FromBitSet(mybitset) // 常规位集 -> Roaring

roaring库以分段压缩方式表达稀疏集合，在保留集合运算能力的同时大幅降低稀疏场景的内存占用。选型建议：位域较密集或下标范围紧凑时用bitset直接获得最大吞吐；位域稀疏、跨度极大时用 Roaring；需要两者结合时通过上述 API 在运行时互转。

关于 Goroutine 安全

文档明确：位集默认不做任何同步，跨 goroutine 并发访问同一实例是不安全的（"they are unsynchronized for performance"）。如果确实需要多 goroutine 共享，两种官方建议：

1. 通道传递所有权：遵循 Go 惯例，通过 channel 把*BitSet在 goroutine 间传递，保证任意时刻只有一个持有者；
2. sync.Mutex串行化：用互斥锁包裹所有对位集的操作，牺牲并发换取安全。

从源码看，set []uint64的读写、extendSet的扩容均未加锁，因此任何形式的并发读写（包括并发Test）都可能造成数据竞争。需要频繁共享时应优先考虑「每 goroutine 私有位集 + 周期性合并」的分治模式（例如并行分段计算后InPlaceUnion汇总），既规避锁竞争又保留位集运算的高吞吐。

测试与验证

原文档要求提交前运行测试与覆盖率检查：

go test go test -cover

本仓库 vendor 目录下的位集源码（vendor/github.com/bits-and-blooms/bitset）包含bitset.go（核心实现，约 1800 行）、bitset_iter.go（Go 1.23+ 迭代器）、select.go（Rank/Select 支持）、popcnt.go（种群计数）以及pext.gen.go（生成的位抽取指令封装）等文件，配合仓库根目录 go.mod 中锁定的v1.25.0版本即可复现文档所述全部行为。位集相关功能在 Loki 中通常位于布隆过滤器、索引结构等存储路径（如 pkg/storage 下的 bloom/tsdb 相关实现），可作为位集在真实大规模日志系统中的应用参考。

小结

围绕「非负整数 ↔ 布尔值」这一核心抽象，bitset提供了完整的方法矩阵：单点操作的Set/Clear/Flip/Test/SetTo，区间与全量的SetRange/FlipRange/SetAll/ClearAll，集合层面的交集/并集/差集/补集/对称差及其基数与原地变体，迭代层面的NextSet/NextSetMany/PreviousSet/EachSet，序列化层面的WriteTo/ReadFrom/MarshalBinary/MarshalJSON，以及内存管理层面的Shrink/Compact/Clone/Copy。将其内化到自己的工具箱，你可以在布隆过滤器、位图索引、权限标记、IP 分配、去重标记等大量位密集型场景中，以远低于map[uint]bool的内存与时间成本完成集合建模与运算。

【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki