快速遍历ACL的策略

Question

我们目前正在开发一个项目，其中主要域对象是内容节点，并且我们正在使用类似 ACL 的系统，其中层次结构中的每个节点都可以包含覆盖或补充其父节点的规则。例如，一切都基于角色和行动。

Node 1 - {Deny All, Allow Role1 View}
\- Node 2 - {Allow Role2 View}
   \- Node 3 - {Deny Role1 View}

在这种情况下，规则将按从上到下的顺序读取，因此节点 3 只能由角色 2 看到。它的概念并不复杂。

检索单个节点的规则可能会导致一些查询，获取所有父节点，然后重新创建规则列表并评估它们，但此过程可能很麻烦，因为层次结构可能会变得非常深，并且可能有很多规则每个节点。

我一直在考虑为每个节点准备一张预先计算规则的表，每当权限更改时都可以重新创建该表并将其传播到更新的节点的所有叶节点。

您认为还有其他策略来加速规则的检索和计算吗？理想情况下，它应该在单个查询中完成，但树并不是最好的结构。

Answer 1

我认为可能会采用 观察者模式。

这个想法是，每个节点维护一个预先计算的列表，并且只需由其父节点通知任何更新，以便它可以重新计算该列表。

这可以通过两种不同的方式完成：

1. 通知发生了更改，但不要重新计算任何内容
2. 在每次更新时重新

计算我建议如果可能的话使用 1，因为它不涉及重新计算整个世界当 root 更新时，并且仅在需要时重新计算（实际上是惰性评估），但如果您很少更新但需要极快的检索（尽管存在更多并发问题），您可能更喜欢第二个选项。

让我们来说明解决方案 1：

Root ___ Node1 ___ Node1A
     \         \__ Node1B
      \_ Node2 ___ Node2A
               \__ Node2B

现在，首先，它们都没有预先计算任何内容（都处于脏状态），如果我要求 Node2A 规则：

• Node2A 实现它是脏的：它查询 Node2 规则
• Node2 意识到它是脏的：它查询 Root
• Root 没有任何父级，因此它不能是脏的，它将其规则发送到 Node2
• Node2 缓存来自 Root 的答案，将其规则与从 Node2 接收到的规则合并code>Root 并清除脏位，它将合并结果（现在已缓存）发送到 Node2A
• Node2A 缓存、合并、清除脏位并返回结果

如果我随后询问 Node2B 规则：

• Node2B is dirty，它查询 Node2
• Node2 is clean，它回复
• Node2B 缓存、合并、清除脏位并返回结果。

请注意，Node2 没有重新计算任何内容。

在更新情况下：

• 我更新 Node1：我使用 Root 缓存规则重新计算新规则并向 Node1A 和 发送节拍>Node1B 通知它们的缓存已过时
• Node1A 和 Node1B 设置了脏位，如果它们有子节点，它们也会传播此通知

请注意，因为我缓存的 Root 规则 我不必查询 Root 对象，如果它是一个足够简单的操作，您可能不希望根本不缓存它们：如果您不这样做在这里进行分布式播放，查询 Root 仅涉及内存往返，您可能不希望重复它，以节省一些内存和簿记。

希望它能让你继续前进。

Answer 2

您的预计算版本似乎存储了与每个节点上的每个角色相关的所有权限。您可以通过遍历树，在到达节点时对节点进行编号，并为每个角色生成节点编号和权限更改的数组（仅针对与该角色相关的权限发生变化的节点）来节省一些时间和空间。 。这会产生仅与输入树（包括其注释）大小成线性关系的输出。然后，当您要检查节点上某个角色的权限时，请使用该节点的编号来搜索数组，以找到数组中代表您在游览期间访问该节点时最近一次权限更改的点。

这可能以某种方式与 http://en.wikipedia.org/wiki/Range_Minimum_Query 和 http://en.wikipedia.org/wiki/Lowest_common_ancestor，但我不真的不知道这些参考资料是否有帮助。