位运算实战：从 Bitmap 索引到高性能权限系统

Paul 收录于 Go

2021-01-11 约 2027 字预计阅读 5 分钟

位运算不只是面试题。从 Redis 的 Bitmap、Kafka 的 ACL 到 Linux 的文件权限，位运算是高性能系统的基础。这篇文章通过实战案例，展示位运算在真实系统中的应用。

一、位运算快速回顾

1.1 基本操作

操作	符号	示例	结果
AND	&	1010 & 1100	1000
OR	\|	1010 \| 1100	1110
XOR	^	1010 ^ 1100	0110
NOT	~	~1010	0101
左移	«	0001 « 2	0100
右移	»	1000 » 2	0010

1.2 常用技巧

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 设置第 n 位为 1
x |= (1 << n)

// 清除第 n 位
x &= ^(1 << n)

// 切换第 n 位
x ^= (1 << n)

// 检查第 n 位
(x >> n) & 1

// 获取最低位的 1
x & (-x)

// 清除最低位的 1
x & (x - 1)

二、案例一：Linux 文件权限

2.1 权限模型

1
2
3
4
5
6
7
8
9
-rwxr-xr--  1 user group  4096 Dec 10 10:00 file.txt
 ^^^
 421 (owner: read + write + execute = 7)
    ^^^
    421 (group: read + execute = 5)
       ^^^
       421 (others: read = 4)

# 权限值: 754

2.2 Go 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type Permission uint32

const (
    PermRead    Permission = 1 << 0  // 001 = 1
    PermWrite   Permission = 1 << 1  // 010 = 2
    PermExecute Permission = 1 << 2  // 100 = 4
)

// 检查权限
func (p Permission) Has(perm Permission) bool {
    return p&perm == perm
}

// 添加权限
func (p *Permission) Grant(perm Permission) {
    *p |= perm
}

// 移除权限
func (p *Permission) Revoke(perm Permission) {
    *p &= ^perm
}

// 使用示例
func main() {
    var perm Permission = PermRead | PermWrite  // 011 = 3
    
    fmt.Println(perm.Has(PermRead))     // true
    fmt.Println(perm.Has(PermExecute))  // false
    
    perm.Grant(PermExecute)
    fmt.Printf("%03b\n", perm)  // 111
    
    perm.Revoke(PermWrite)
    fmt.Printf("%03b\n", perm)  // 101
}

三、案例二：RBAC 权限系统

3.1 场景分析

假设一个 SaaS 系统有以下权限：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const (
    PermViewDashboard   uint64 = 1 << 0
    PermEditProfile     uint64 = 1 << 1
    PermCreateProject   uint64 = 1 << 2
    PermDeleteProject   uint64 = 1 << 3
    PermInviteUser      uint64 = 1 << 4
    PermRemoveUser      uint64 = 1 << 5
    PermManageBilling   uint64 = 1 << 6
    PermAccessAdmin     uint64 = 1 << 7
    // ... 最多 64 种权限
)

// 预定义角色
const (
    RoleViewer uint64 = PermViewDashboard
    
    RoleEditor uint64 = PermViewDashboard | 
                        PermEditProfile | 
                        PermCreateProject
    
    RoleAdmin uint64 = PermViewDashboard | 
                       PermEditProfile | 
                       PermCreateProject | 
                       PermDeleteProject |
                       PermInviteUser | 
                       PermRemoveUser
    
    RoleOwner uint64 = 0xFFFFFFFFFFFFFFFF  // 全部权限
)

3.2 高性能权限检查

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
type User struct {
    ID          int64
    Permissions uint64  // 只需 8 字节存储全部权限！
}

// O(1) 权限检查
func (u *User) Can(perm uint64) bool {
    return u.Permissions&perm == perm
}

// 检查多个权限（全部满足）
func (u *User) CanAll(perms ...uint64) bool {
    var required uint64
    for _, p := range perms {
        required |= p
    }
    return u.Permissions&required == required
}

// 检查多个权限（满足任一）
func (u *User) CanAny(perms ...uint64) bool {
    var required uint64
    for _, p := range perms {
        required |= p
    }
    return u.Permissions&required != 0
}

3.3 与传统实现对比

传统方式（关系表）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
-- 查询用户权限
SELECT p.name 
FROM user_roles ur
JOIN role_permissions rp ON ur.role_id = rp.role_id
JOIN permissions p ON rp.permission_id = p.id
WHERE ur.user_id = ?

-- 检查权限
SELECT COUNT(*) 
FROM user_roles ur
JOIN role_permissions rp ON ur.role_id = rp.role_id
WHERE ur.user_id = ? AND rp.permission_id = ?

性能对比：

方面	关系表	Bitmap
存储	3 张表 + 索引	1 个 uint64 字段
检查权限	JOIN 查询	位运算 O(1)
添加权限	INSERT	OR 运算
网络开销	多次 DB 往返	无（已加载到内存）

3.4 数据库存储

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 存储到数据库
func (u *User) Save(db *sql.DB) error {
    _, err := db.Exec(
        "UPDATE users SET permissions = ? WHERE id = ?",
        u.Permissions,  // 直接存 uint64
        u.ID,
    )
    return err
}

// 从数据库加载
func LoadUser(db *sql.DB, id int64) (*User, error) {
    var u User
    err := db.QueryRow(
        "SELECT id, permissions FROM users WHERE id = ?",
        id,
    ).Scan(&u.ID, &u.Permissions)
    return &u, err
}

四、案例三：Bitmap 索引

4.1 场景：用户标签系统

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 用户标签（最多 64 种）
const (
    TagPremium      uint64 = 1 << 0
    TagVerified     uint64 = 1 << 1
    TagNewUser      uint64 = 1 << 2
    TagHighValue    uint64 = 1 << 3
    TagChurningRisk uint64 = 1 << 4
    // ...
)

type UserIndex struct {
    // 每个标签对应一个 bitmap
    // bitmap[i] 的第 j 位表示第 j 个用户是否有标签 i
    bitmaps [64][]uint64
    userCount int
}

4.2 快速筛选

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 找出所有 "Premium AND Verified AND NOT ChurningRisk" 的用户
func (idx *UserIndex) Query(must, mustNot uint64) []int {
    var result []int
    
    // 计算每个 block 的匹配情况
    blocks := (idx.userCount + 63) / 64
    for b := 0; b < blocks; b++ {
        var match uint64 = 0xFFFFFFFFFFFFFFFF
        
        // AND 条件
        for i := 0; i < 64; i++ {
            if must&(1<<i) != 0 {
                match &= idx.bitmaps[i][b]
            }
        }
        
        // NOT 条件
        for i := 0; i < 64; i++ {
            if mustNot&(1<<i) != 0 {
                match &= ^idx.bitmaps[i][b]
            }
        }
        
        // 提取匹配的用户 ID
        for match != 0 {
            pos := bits.TrailingZeros64(match)
            result = append(result, b*64+pos)
            match &= match - 1  // 清除最低位的 1
        }
    }
    
    return result
}

4.3 性能分析

假设 1000 万用户，64 个标签：

方案	存储	查询复杂度
传统表	10M × 64 行	O(n) 扫描
Bitmap	64 × 1.25MB = 80MB	O(n/64) 位运算

实际速度：现代 CPU 一次可以处理 64 位，配合 SIMD 可以更快。

五、案例四：布隆过滤器

5.1 原理

布隆过滤器用多个 hash + bitmap 实现"可能存在"的高效判断：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type BloomFilter struct {
    bits    []uint64
    numHash int
}

func (bf *BloomFilter) Add(item string) {
    for i := 0; i < bf.numHash; i++ {
        hash := bf.hash(item, i)
        idx := hash / 64
        bit := hash % 64
        bf.bits[idx] |= 1 << bit
    }
}

func (bf *BloomFilter) MayContain(item string) bool {
    for i := 0; i < bf.numHash; i++ {
        hash := bf.hash(item, i)
        idx := hash / 64
        bit := hash % 64
        if bf.bits[idx]&(1<<bit) == 0 {
            return false  // 一定不存在
        }
    }
    return true  // 可能存在
}

5.2 应用场景

Redis：判断 key 是否存在
数据库：跳过不含目标数据的 SSTable
爬虫：URL 去重
推荐系统：过滤已推荐内容

六、实战技巧

6.1 超过 64 种权限

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
type LargePermission struct {
    bits []uint64
}

func (p *LargePermission) Set(n int) {
    idx := n / 64
    bit := n % 64
    // 动态扩容
    for len(p.bits) <= idx {
        p.bits = append(p.bits, 0)
    }
    p.bits[idx] |= 1 << bit
}

func (p *LargePermission) Has(n int) bool {
    idx := n / 64
    bit := n % 64
    if idx >= len(p.bits) {
        return false
    }
    return p.bits[idx]&(1<<bit) != 0
}

6.2 原子操作（并发安全）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import "sync/atomic"

type AtomicPermission struct {
    bits uint64
}

func (p *AtomicPermission) Grant(perm uint64) {
    for {
        old := atomic.LoadUint64(&p.bits)
        new := old | perm
        if atomic.CompareAndSwapUint64(&p.bits, old, new) {
            return
        }
    }
}

func (p *AtomicPermission) Has(perm uint64) bool {
    return atomic.LoadUint64(&p.bits)&perm == perm
}

6.3 序列化为 JSON

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
type Permission uint64

func (p Permission) MarshalJSON() ([]byte, error) {
    // 转为权限名列表，更可读
    names := []string{}
    if p&PermRead != 0 {
        names = append(names, "read")
    }
    if p&PermWrite != 0 {
        names = append(names, "write")
    }
    // ...
    return json.Marshal(names)
}

七、总结

应用场景	位运算优势
权限系统	O(1) 检查，8 字节存储 64 种权限
标签/分类	快速筛选，支持复合条件
布隆过滤器	空间效率极高的存在性判断
状态机	多状态并存的紧凑表示

核心收获：

位运算把 CPU 指令级优化带入应用层
空间压缩 + 时间常数 = 双赢
适合"多选一"或"多选多"的场景
配合原子操作可实现无锁并发

目录