フォルダ/ファイルシステムのパーミッションの効率的な継承

Question

宿題のためにJavaで仮想ファイルシステムを作成しています。私は、読み取り、変更、削除の3つのアクセス許可のみで構成された非常に単純なアクセス許可ルールを設計します。ファイルシステムツリーが拡張されているため、ユーザーは任意のレベルの任意のファイル/フォルダを選択できます。ユーザーがフォルダのアクセス許可を変更すると、このフォルダ内のすべてのファイル/フォルダも変更内容を継承し、独自のアクセス許可を更新する必要があります。しかし、下のすべてのノードを更新することは、ツリーが本当に深くなったり、例えば息子ノードのアクセス権が変更された後に父親の許可が変更されたときには非効率的になることがあります。変更されたノードのすべてのブランチを更新するだけでなく、どのようにすれば効率的にすることができますか？

Answer 1

権限の更新を行うコストとオブジェクトの有効なアクセス許可を計算するコストとの間にはトレードオフがあります。

たとえば、アクセス許可とアクセス許可のタイムスタンプを保存することで、アクセス許可の更新を高速化できます。次に、ノードとそのすべての祖先のパーミッション/タイムスタンプのペアを調べることにより、ノードの実効パーミッションを計算します。新しいタイムスタンプを持つものが優先されます。もちろん、これは、ノードの有効なアクセス権の計算が遅いことを意味します。

（あなたはその後、ディレクトリのパーミッション/タイムスタンプのペアのメモリ内のLRUキャッシュを速く効果的なアクセス許可の計算を行うことができます。）