📚 课程目录第4章权限校验的核心算法

4. 权限校验的核心算法：从角色树中计算用户有效权限集合

用户在系统中的最终权限，并非直接来自其被授予的角色，而是需要沿着角色树向上递归合并所有父角色所拥有的权限，再与用户本身可能持有的直接权限进行并集运算。本章将深入讲解这一核心算法的原理、实现、缓存策略与优化方法。

4.1 算法原理

假设角色树是一个有向无环图（DAG），每个角色节点包含一组权限（例如：读、写、删除）。用户关联到若干角色（通常为叶子角色或中间角色）。有效权限集合定义为：从用户关联的所有角色节点出发，向上遍历所有祖先节点（包括自身），取其权限的并集。

  关键公式：
  P_user = ∪ (P_role ∪ P_parent ∪ ... ∪ P_root) for each assigned role

由于角色树可能存在多个路径，重复权限只需保留一份。算法的核心是深度优先或广度优先的递归向上合并，并利用缓存避免重复计算相同的角色子树。

4.2 算法实现流程

获取用户关联的角色列表（通常从数据库中查询用户-角色映射表）。
对每个关联角色，执行递归向上获取权限：传入角色ID，查找其父角色，若父角色权限缓存未命中，则递归计算父角色的有效权限。
合并权限：将当前角色自身权限与父角色有效权限做并集，存入该角色的缓存。
汇总用户所有关联角色的有效权限，再次取并集，得到用户最终有效权限集合。
缓存用户权限：以用户ID为key，存放到本地内存缓存或Redis，设置合理TTL。

4.3 代码实现（Python 示例）

class RoleBasedAccessControl:
    def __init__(self):
        self.role_permissions = {}      # role_id -> set of permissions
        self.role_parents = {}          # role_id -> parent_role_id (or None)
        self.role_effective_cache = {}  # role_id -> effective permissions (cached)
        self.user_effective_cache = {}  # user_id -> set of permissions

    def get_effective_permissions_for_role(self, role_id):
        if role_id in self.role_effective_cache:
            return self.role_effective_cache[role_id]

        own_perms = self.role_permissions.get(role_id, set())
        parent_id = self.role_parents.get(role_id)
        if parent_id:
            parent_perms = self.get_effective_permissions_for_role(parent_id)
            combined = own_perms | parent_perms
        else:
            combined = own_perms

        self.role_effective_cache[role_id] = combined
        return combined

    def get_user_permissions(self, user_id, user_roles):
        if user_id in self.user_effective_cache:
            return self.user_effective_cache[user_id]

        user_perms = set()
        for role_id in user_roles:
            user_perms |= self.get_effective_permissions_for_role(role_id)

        self.user_effective_cache[user_id] = user_perms
        return user_perms

4.4 缓存策略

缓存层级	Key	Value	TTL 建议	失效触发
角色有效权限	role_id	权限集合（位图或set）	10~30分钟	角色权限变更、角色父子关系变更
用户最终权限	user_id	权限集合	5~15分钟	用户角色分配变更、关联角色有任何权限变更

缓存更新可使用事件驱动机制：当角色权限或关系修改时，主动清除受影响的角色及所有下层角色的缓存，并清除相关用户的缓存。

4.5 调试与验证

打印角色树：可视化输出每个角色的权限和父角色，检查是否有循环引用。
单元测试：构造小型角色树（3~5个节点），断言用户权限符合预期。
日志：在递归计算时记录调用栈，便于排查栈溢出或无限递归。

调试技巧：在开发环境可以临时禁用缓存，每次重新计算权限，便于对比结果是否正确。待验证通过后再启用缓存。

4.6 常见错误与避坑

循环继承：角色A的父角色是B，B的父角色是A，导致无限递归。解决方案：在递归入口记录访问过的节点，发现重复即抛出异常。
缓存穿透：大量请求同一个不存在权限的角色，导致频繁访问数据库。解决方案：缓存空值并设置短暂TTL。
缓存未及时失效：修改角色权限后，已缓存的用户权限仍为旧值。应建立缓存失效订阅机制。

4.7 性能优化

权限位图：将权限映射到bit位，使用位运算代替集合操作，减少内存占用并提升合并速度。
LRU淘汰：为角色有效权限缓存设置最大条目数，使用LRU算法淘汰不常用的角色。
预计算：在系统启动或角色变更时，预计算所有角色的有效权限并刷新缓存，避免首次请求的冷启动延迟。
路径压缩：对于深度很大的角色树，可将每个角色的有效权限直接表示为从根到自己的路径权限并集，一次性加载。

4.8 架构要点 SVG 图

警告：递归深度过大的角色树（超过100层）可能导致栈溢出。生产环境建议使用迭代栈代替递归，或者设置递归深度限制并转为迭代。

4.9 部署与监控要点

缓存容量监控：监控角色缓存与用户缓存的内存占用，设置最大条目数。
缓存命中率：低于90%需要检查缓存失效策略是否合理。
冷启动预热：在服务启动脚本中调用 precompute_all_roles() 预加载所有角色的有效权限。

本章详细介绍了权限校验的核心算法，从原理、递归合并实现、缓存策略到性能优化，并结合SVG流程图展示了权限向上合并的过程。掌握这些内容后，即可将算法应用到实际的RBAC系统中。