Стратегии для быстрого прохождения ACL

Question

В настоящее время мы работаем над проектом, в котором основными объектами домена являются узлы контента, и мы используем систему, подобную ACL, в которой каждый узел в иерархии может содержать правила, которые переопределяют или дополняют правила их родителей. Например, все основано на ролях и действиях.

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

В этом случае правила будут читаться по порядку сверху вниз, поэтому Узел 3 может просматривать только Role2. Это не очень сложно в концепции.

Извлечение правил для одного узла может привести к некоторым запросам, получению всех родителей, а затем воссозданию списка правил и их оценке, но этот процесс может быть громоздким, поскольку иерархия может стать довольно глубокой и может быть много правил на каждом узле.

Я размышлял над подготовкой таблицы с предварительно рассчитанными правилами для каждого узла, которую можно было воссоздать при каждом изменении разрешения и распространении на все конечные узлы обновленного.

Думаете ли вы о какой-либо другой стратегии для ускорения поиска и расчета правил? В идеале это должно быть сделано в одном запросе, но деревья не являются лучшими структурами для этого.

Answer 1

Я думаю, что Шаблон наблюдателя может быть адаптирован.

Идея заключается в том, что каждый Node поддерживает предварительно вычисленный список и просто уведомляется своим родителем о любом обновлении, чтобы он мог пересчитать этот список.

Это можно сделать двумя разными способами:

1. уведомить, что произошло изменение, но ничего не пересчитывать
2. пересчитывать при каждом обновлении

Я бы посоветовал перейти с 1, если это возможно, так как он не требует пересчета всего мира при обновлении root, а только пересчета при необходимости (фактически, lazy eval), но вы можете предпочесть второй вариант, если вы обновляете редко но нужно использовать быстрый быстрый поиск (хотя есть и другие проблемы с параллелизмом).

Давайте проиллюстрируем Решение 1:

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

Теперь, для начала, никто из них ничего не вычислил заранее (все находятся в грязном состоянии), если я попрошу правила Node2A:

• Node2A понимает, что это грязно: он запрашивает Node2 правила
• Node2 понимает, что это грязно: он запрашивает Root
• Root не имеет родителя, поэтому он не может быть грязным, он отправляет свои правила на Node2
• Node2 кэширует ответ от Root, объединяет свои правила с правилами, полученными от Root и очищает грязный бит, отправляет результат слияния (кэшированный сейчас) в Node2A
• Node2A кэширует, объединяет, очищает грязный бит и возвращает результат

Если я впоследствии запрашиваю Node2B правил:

• Node2B грязно, он запрашивает Node2
• Node2 чисто, отвечает
• 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,, но я не знаю, помогут ли эти ссылки или нет.