代码之家 › 专栏 › 技术社区 › Marc Climent

快速遍历ACL的策略

acl tree algorithm performance

Marc Climent · 技术社区 · 14 年前

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

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

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

检索单个节点的规则可能会导致一些查询、获取所有父节点,然后重新创建规则列表并对其进行评估,但此过程可能会比较麻烦,因为层次结构可能会变得很深,并且每个节点上可能有很多规则。

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

你有没有考虑其他加快规则检索和计算的策略?理想情况下,它应该在单个查询中完成,但是树并不是最好的结构。

2 回复 | 直到 14 年前

Matthieu M. 14 年前

我会认为 Observer Pattern 可能会被改编。

我们的想法是 Node 维护一个预先计算的列表,并且它的父级会简单地通知任何更新,以便它可以重新计算此列表。

这可以通过两种不同的方式实现:

通知发生了更改,但不要重新计算任何内容
每次更新时重新计算

我建议和你一起去 1 如果可能的话,因为它不涉及在根目录更新时重新计算整个世界,并且只在需要时重新计算(实际上是懒惰的eval),但是如果您很少更新,但需要快速检索(尽管有更多并发问题),您可能更喜欢第二个选项。

让我们举例说明解决方案1:

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

现在,首先,如果我要求的话,他们中没有人预先计算过任何东西(所有人都处于肮脏的状态)。 Node2A 规则:

NoDE2A 意识到它是脏的:它查询 Node2 规则
NoDE2 意识到它是脏的:它查询 Root
根 没有任何父级,因此它不能是脏的,它将其规则发送到 NoDE2
NoDE2 缓存来自的答案 根 ,将其规则与从接收的规则合并 根 并清除脏位,它将合并(现在缓存)的结果发送到 NoDE2A
NoDE2A 缓存、合并、清除脏位并返回结果

如果我随后要求 Node2B 规则:

NoDE2B 是脏的,它查询 NoDE2
NoDE2 很干净,它回答说
NoDE2B 缓存、合并、清除脏位并返回结果

注意 NoDE2 没有重新计算任何内容。

在更新案例中:

我更新 Node1 我用的是 根 缓存规则以重新计算新规则并将节拍发送到 Node1A 和 Node1B 通知他们他们的缓存已过时
NoDE1A 和 NoDE1B 设置他们的脏位,如果他们有孩子,他们也会传播此通知

注意,因为我缓存了 根 规则我不必查询 根 对象,如果这是一个足够简单的操作,那么您可能根本不希望缓存它们:如果您不在这里播放分布式操作和查询 根 只涉及一次记忆往返旅行,你可能不喜欢复制它,以节省一些记忆和簿记。

希望它能让你前进。

mcdowella 14 年前

您的预计算版本似乎存储了与每个节点上的每个角色相关的所有权限。您可以通过遍历树、在到达节点时对其编号,并为每个角色生成一个节点编号数组和权限更改(仅针对与该角色相关的权限更改的节点),从而节省一些时间和空间。这只产生输入树大小的线性输出(包括注释)。然后,当您来检查节点上角色的权限时,使用该节点的编号搜索数组,以查找数组中表示在巡更期间访问该节点时权限最新更改的点。

这可能在某种程度上与 http://en.wikipedia.org/wiki/Range_Minimum_Query 和 http://en.wikipedia.org/wiki/Lowest_common_ancestor 但是我不知道这些推荐信是否有帮助。