bjmayor 发布于 2025-11-09

comments

权限系统设计：从 RBAC 到图权限，再到列表查询的性能难题

一、权限系统的本质

权限系统的核心是三元组：实体、资源、操作

以 Linux 文件系统为例：

实体（Who）: 用户（User）
资源（What）: 文件（File）
操作（How）: rwx（读、写、执行）

# 示例：用户 alice 对文件 /data/report.txt 有读写权限
alice (实体) -> /data/report.txt (资源) -> rw- (操作)

二、权限模型的演进

2.1 ACL（访问控制列表）- 最原始的方式

直接定义 “谁对什么有什么权限”：

alice   -> /data/report.txt  -> read, write
bob     -> /data/report.txt  -> read
charlie -> /data/secret.txt  -> read, write

问题：

用户多了管理困难（每个用户都要单独配置）
权限变更成本高（要改 100 个用户的权限就要改 100 次）

2.2 用户组（Group）- 对实体的包装

引入"组"的概念，批量管理用户：

组: managers = [alice, bob, charlie]
组: developers = [david, eve, frank]

managers    -> /data/reports/*  -> read, write
developers  -> /data/code/*     -> read, write, execute

改进：

新增用户只需加入组
调整组的权限即可影响所有成员

仍然不够：权限类型（read, write, execute）仍然散落各处，难以复用

2.3 RBAC（基于角色的访问控制）- 对操作的包装

引入"角色"的概念，封装一组操作：

角色定义:
  - 角色: admin        -> 操作: [read, write, delete, grant]
  - 角色: editor       -> 操作: [read, write]
  - 角色: viewer       -> 操作: [read]

用户分配:
  - alice   -> 角色: admin    (on /data/reports/*)
  - bob     -> 角色: editor   (on /data/reports/*)
  - charlie -> 角色: viewer   (on /data/reports/*)

优点：

权限管理清晰：用户 -> 角色 -> 资源
易于扩展：新增角色即可，无需修改用户配置
Go 语言推荐库：Casbin (支持 RBAC/ABAC/RESTful 等多种模型)

2.4 RBAC 的局限性

RBAC 适合：

✅ 静态的组织结构（角色相对固定）
✅ 权限与角色强相关（如：管理员、编辑、访客）
✅ 资源类型有限（如：文档、订单、用户）

RBAC 不适合：

❌ 动态的权限继承（领导自动继承下属权限）
❌ 复杂的关系链（A 的上级的上级也有权限）
❌ 资源之间有依赖（文件夹权限影响子文件）

三、权限继承的难题：Google Zanzibar

3.1 真实场景：组织层级权限

场景:
  - Alice 是 Bob 的领导
  - Bob 对资源 C 有权限
  - 期望: Alice 自动继承 Bob 的权限（领导能看下属的所有资源）

传统 RBAC 解决不了这个问题，因为：

Bob 的权限可能很多，手动给 Alice 分配不现实
Bob 的下属可能变化（离职、调岗），需要实时更新
权限是间接的、传递的

阅读全文 »

bjmayor 发布于 2025-11-07

comments

最大化最小值 / 最小化最大值 - 算法套路总结

一、什么是"最大化最小值"问题？

在算法题中，经常会遇到这样的描述：

“让所有工人的最大工作量尽可能小”
“让所有城市的最小电量尽可能大”
“让木材切割后的最小长度尽可能大”
“让学生分配到的最大任务数尽可能小”

这类问题有个共同特点：求在某种约束条件下，某个极值指标的最优值。

乍一看这类问题很难直接求解，但有一个巧妙的思路：把"求最优值"转换为"判断某个值是否可行"。

二、核心思想：二分答案法

2.1 为什么要二分答案？

直接思路的困境：
假设要求"分配任务后，学生们的最大任务量的最小值"，如果直接枚举所有可能的分配方案，复杂度会是指数级的，根本无法接受。

转换思路：
我们换个角度问问题：

原问题：“最优答案是多少？”（不知道怎么求）
新问题：“答案能否达到 X？”（相对容易判断）

如果能高效判断"答案是否能达到 X"，那我们就可以用二分搜索在所有可能的答案中找到最优的那个！

2.2 为什么二分法有效？关键在于单调性

二分答案法之所以可行，是因为这类问题有一个关键性质：单调性。

以"最大化最小值"为例：

如果"让所有城市电量都达到 10"可以实现，那么"让所有城市电量都达到 9、8、7…"肯定也可以实现（要求更低了）
如果"让所有城市电量都达到 10"无法实现，那么"让所有城市电量都达到 11、12、13…"肯定也无法实现（要求更高了）

这种单调性意味着：存在一个临界值 M，小于等于 M 的都可以实现，大于 M 的都无法实现。

答案值:  0   1   2   3   4   5   6   7   8   9   10  11  12
是否可行: ✓   ✓   ✓   ✓   ✓   ✓   ✓   ✓   ✗   ✗   ✗   ✗   ✗
                                      ↑
                                   我们要找的最优答案

这正是二分搜索的应用场景！我们要找的就是那个"从可行到不可行"的临界点。

三、解题框架（四步走）

第一步：识别问题类型

看到以下关键词就要想到二分答案法：

“最大化最小值”
“最小化最大值”
“在…约束下，求…的最优值”
“让…尽可能大/小”

第二步：确定二分搜索范围

需要确定答案的可能范围 [left, right]：

left（最小可能值）：通常是理论最小值，比如 0，或者初始状态下已有的最小值
right（最大可能值）：通常是理论最大值，比如所有资源之和，或者题目给定的上限

第三步：设计 check(mid) 函数

这是最关键的一步！

check(mid) 函数的作用：判断答案能否达到 mid。

返回 true：说明 mid 这个答案可以实现，真正的最优答案 ≥ mid
返回 false：说明 mid 这个答案无法实现，真正的最优答案 < mid

设计 check 函数时，通常会用到贪心、滑动窗口、差分数组等技巧。

第四步：二分搜索主循环

def solve():
    left, right = 确定搜索范围
    
    while left < right:
        mid = (left + right + 1) // 2  # 对于"最大化最小值"问题
        
        if check(mid):  # mid 可行
            left = mid  # 尝试更大的值
        else:  # mid 不可行
            right = mid - 1  # 尝试更小的值
    
    return left  # 最终 left == right，就是答案

注意：

"最大化最小值"问题：mid = (left + right + 1) // 2，可行时 left = mid
"最小化最大值"问题：mid = (left + right) // 2，可行时 right = mid

阅读全文 »

bjmayor 发布于 2025-11-07

comments

分库分表最佳实践

引言

随着业务的快速增长，单一数据库面临的性能瓶颈和存储限制问题日益突出。分库分表作为一种经典的数据库扩展方案，已经成为大规模互联网应用的标准实践。本文将从实际场景出发，探讨分库分表的演进过程、面临的挑战以及应对方案。

⚠️ 核心认知：分库分表的本质

分库分表不是性能优化的银弹，而是用"系统复杂度"换"单机性能突破"的妥协方案。

分库分表解决了什么？

✅ 解决单机硬件瓶颈：

CPU 瓶颈：单机 CPU 核心数有限，分库后多机并行处理
内存瓶颈：单机内存有限，分库后每个实例的工作集更小
磁盘瓶颈：单机 IOPS 有限，分库后 IO 分散到多个磁盘
网络瓶颈：单机网卡带宽有限（如 10Gbps），分库后总带宽提升

✅ 解决单表数据量问题：

索引深度降低（B+Tree 层级减少，查询更快）
单表数据量小，全表扫描更快
备份恢复时间缩短

分库分表带来了什么问题？

❌ 性能不一定提升，某些场景反而降低：

场景	单库性能	分库性能	说明
按主键查询	1ms	1-2ms	分库增加路由开销
带分片键的查询	5ms	3-5ms	只查一个分片，性能相当
不带分片键的查询	10ms	80ms	需要查 8 个分片并合并
跨表 JOIN	5ms	禁止	无法跨库 JOIN
分布式事务	1ms	50-500ms	2PC/TCC 性能极差
分页查询（全局）	10ms	80ms+	需要从每个分片取数据合并

网络开销示例：

单库查询:
应用 -> MySQL (1次网络往返, ~1ms)

分库查询（不带分片键）:
应用 -> 8个 MySQL (8次网络往返并发, ~2-5ms)
应用层聚合 (CPU 排序、去重, ~5ms)
总耗时: ~10ms (比单库慢 10 倍)

❌ 维护成本指数级增长：

运维复杂度：

单库:
- 监控: 1 个实例
- 备份: 1 个库，1TB 数据，1 小时
- 恢复: 1 个库，1 小时
- 扩容: 垂直扩容（加 CPU/内存）
- 故障处理: 切换 1 个主从

分库分表 (8 库):
- 监控: 8 个实例 × 64 张表 = 512 个对象
- 备份: 8 个库，8TB 数据，需要 8 小时（串行）或复杂的并行方案
- 恢复: 需要恢复 8 个库，协调一致性
- 扩容: 数据迁移（75% 数据需要移动，停服或双写）
- 故障处理: 可能需要切换多个实例，影响面更大

开发复杂度：

// 单库: 简单直接
order := db.Query("SELECT * FROM orders WHERE id = ?", orderID)

// 分库: 需要路由逻辑
shard := shardRouter.GetShard(orderID)  // 路由
order := shard.Query("SELECT * FROM orders_" + getTableSuffix(orderID) + " WHERE id = ?", orderID)

// 单库: 支持事务
db.Transaction(func(tx) {
    tx.Exec("UPDATE accounts SET balance = balance - 100 WHERE user_id = ?", 1)
    tx.Exec("UPDATE accounts SET balance = balance + 100 WHERE user_id = ?", 2)
})

// 分库: 需要分布式事务或最终一致性方案（代码量 10 倍）
saga := NewSaga()
saga.AddStep(step1, compensate1)
saga.AddStep(step2, compensate2)
saga.Execute()  // 100+ 行代码

❌ 灵活性大幅降低：

不能随意加字段做查询（必须考虑是否包含分片键）
不能随意 JOIN（需要提前设计好数据冗余）
业务迭代困难（表结构变更需要改 64 张表）
A/B 测试困难（数据隔离复杂）

什么时候才应该分库分表？

单库能撑就别分！先尝试这些优化：

阶段 1: SQL 优化 (成本: 0, 收益: 10-100x)
├── 添加索引
├── 优化慢查询
└── 去除不必要的 SELECT *

阶段 2: 读写分离 (成本: 低, 收益: 3-5x)
├── 1 主 3 从
├── 读请求走从库
└── 缓存热点数据 (Redis)

阶段 3: 垂直拆分 (成本: 中, 收益: 2-3x)
├── 按业务模块拆分数据库
├── 大字段拆分到独立表
└── 冷热数据分离

阶段 4: 分库分表 (成本: 高, 收益: 5-10x，但复杂度 +100x)
├── 单表 > 2000 万
├── 单库 QPS > 5000
└── 单库存储 > 1TB

真实成本对比：

项目	单库	分库分表 (8 库 64 表)
开发成本	1 个月	3-6 个月（路由、聚合、迁移）
硬件成本	1 台 (16C64G) = $1000/月	8 台 × $1000 = $8000/月
运维人力	1 人	2-3 人（监控、巡检、应急）
故障恢复时间	1 小时	4-8 小时（多库协调）
新人上手时间	1 周	1-2 个月（理解路由逻辑）