策略快速遍歷ACL

Question

我們目前工作的一個項目，其中主要的域對象是內容節點，我們使用的是ACL-like系統，其中層次結構中的每個節點都可以包含覆蓋或補充那些對父母的規則。例如，一切都基於角色和行爲。

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

在這種情況下，規則將從上到下依次讀取，因此節點3只能由Role2查看。這個概念並不複雜。

檢索單個節點的規則可能會導致一些查詢，獲取所有父級，然後重新創建規則列表並對其進行評估，但是此過程可能非常麻煩，因爲層次結構可能會變得非常深，並且可能會有一個每個節點上都有很多規則。

我一直在思考與準備每當權限更改並將其傳播到一個更新的所有葉子節點可能被重新創建每個節點預先計算規則的表。

你認爲任何其他戰略，加快規則的檢索和計算的？理想情況下，它應該在單個查詢中完成，但樹並不是最好的結構。

Answer 1

我認爲一個Observer Pattern可能會進行調整。

這個想法是，每個Node維護一個預先計算的列表，並且只是通知其父任何更新，以便它可以重新計算這個列表。

這可以通過兩種不同的方式來完成：

1. 通知發生了變化，但在每次更新

我會建議與1會不會重新計算任何

重新計算如果可能的話，因爲它不涉及重新計算整個世界時，根被更新，僅在需要時重新計算（其實是懶惰EVAL），但如果你更新很少，但需要極快的檢索你可能更喜歡第二個選項（有更多的人贊成rency問題雖然）。

讓我們來說明解決方案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相關聯，但我真的不知道這些引用是否有幫助。