概述​

结构化资源是我们在实际生产中常见的一种资源组织方式，例如公司的文件/夹结构 、组织结构 都是属于结构化资源(见下图)，各节点之间存在一种层级和关联关系。

文件夹结构是由文件夹、文件构成的标准的树型数据结构，树结构中的任意节点只能有一个父节点。

组织结构是由单位、部门、人员构成的一种具有上下层级的类似树型的数据结构，而在组织中人员可以同时隶属于多个部门或单位，这打破了树型结构的定义，形成一种被称为有向无环图（Directed Acyclic Graph，简称 DAG）的数据结构。

当一个有限权力的用户需要访问文件/夹或组织结构时，通常也只能看到部分节点显示，其他无权访问的节点则不能给用户呈现出来。这需要一种鉴权方法根据一定的策略可灵活配置用户的访问范围。由于每个用户的可访问范围不同，因此最终鉴权机制将针对每个用户的配置策略生成其特有的资源访问视图，简称为访问图。

以上面的结构图为实例，如果用户小明的配置策略为：

1. 拒绝 小明 访问 办公软件 文件夹
2. 拒绝 小明 查看 市场部 中的人员

则小明实际看到的访问图应该是：

通过上面的例子，我们对鉴权有了一个基本的了解，但实际生产环境下，情况要复杂的多，因此我们专门研究了一种访问鉴权机制来解决这个问题。由于树结构也是一种有向无环图(DAG)，因此我们将解决DAG的访问鉴权作为实现目标，要求在具有上百万节点的DAG中通过策略快速生成访问图，海量节点和计算效率是重要的考虑因素，因为文件/夹结构可能会包含数百万个节点，而用户登录系统后肯定希望在最短的时间(2秒内)看到访问图。

鉴权过程​

概念定义​

完整图 是拥有完全节点的DAG，例如企业中需要共享的所有文件/夹结构，以及企业的完整组织架构。

访问图是用户可访问节点构成的DAG，可访问节点是基于完整图的基础上由访问鉴权机制根据策略计算得出。

访问图由允许节点、拒绝节点和桥节点构成：

允许节点 策略作用为允许的节点。

拒绝节点 策略作用为拒绝，且子孙中没有允许节点的节点。

桥节点 不受任何策略作用或策略作用为拒绝的节点，但在子孙节点中存在允许节点。

在访问图中，节点拥有以下特性：

允许节点可见、可操作。

拒绝节点不可见、不可操作。

桥节点可见、不可操作，仅为子孙的允许节点提供可见的访问路径。

算法实现​

现有一个完整图，通过算法根据用户的策略列表，生成该用户特有的访问图。

遍历策略，按如下描述确认节点类型：

根据策略信息，在完整图中找到对应的资源节点，如果策略的作用为允许，则当前节点的类型为允许节点，其所有父节点中的拒绝节点将强制更新为桥节点。如果策略的作用为拒绝则节点的类型为拒绝节点，但需要注意有子孙节点的拒绝节点，有可能被子孙节点的策略(作用为允许)更新为桥节点。

依次完成所有策略的处理后，将为拥有这些策略的用户生成一个特有的访问图。由于用户包含的策略数通常不会很多，通过遍历策略进行访问图的计算，可以控制过程复杂度在可接受范围。

用户故事​

存在如下组织结构，作为一种结构化资源可被小明访问，现在通过制定访问策略，限制小明对该组织结构的访问范围。

组织结构完整图定义：

访问策略：

资源节点	行为	作用
研发部（2）	查看	允许
产品部（3）	查看	拒绝
研发一部（4）	查看	拒绝
产品二部（6）	查看	允许
006	查看	允许
007	查看	允许

通过上述的算法可为小明生成的访问图：

参考链接​

有向无环图