日記/2007/10/31/YakiBikiのACLメモ

日記 / 2007 / 10 / 31 / YakiBikiのACLメモ

id: 80 所有者: msakamoto-sf 作成日: 2007-10-31 13:00:51
カテゴリ: YakiBiki

ACLキャッシュに関するあれこれ。
各タイミングにおけるACLキャッシュ再構築の詳細
2008年12月時点での追記

ACLキャッシュに関するあれこれ。

当初は U2A 、つまり「ユーザーID(と、アクセスレベル)を元に対応するACL IDを取得する」インデックスを作成する予定だった。これについては諸々の思考の後も変わらない。但しインデックスではなく、「ACLキャッシュ」という独立した概念となり、daoやidxとしては実装されない。恐らく、yb直下、つまりYakiBiki内の機能を横断する位置づけとなるだろう。まぁ実際、YakiBikiのデータ操作の殆どに関わってくるので、この扱いでも良いだろう。

ACLキャッシュの機能

ACLキャッシュは、次のような機能を提供する。

入力（ユーザーID, アクセスレベル）に対して、対応するACL ID群を返却する(出力)。
上記I/Oを素早く処理する為、独自のキャッシュデータを保持する。
上記キャッシュデータを再構築する。

現在既に、ACL IDに対応するDataIDを取得する"A2D"インデックスが存在する。これとACLキャッシュを組み合わせることで、次の手順で、アクセスが許可されるデータIDを取得可能になる。

1. ログイン中のユーザーIDと、アクションに対応するアクセスレベルから、ACLキャッシュより対応するACLID群を取得する。
2. 1.で取得したACLID群より、各々対応するデータID群をA2Dインデックスより取得し、重複IDを除去する。

例えばトップ画面になるであろう一覧表示であれば、この結果とカテゴリやキーワード検索のインデックス取得結果を併せ、更新ソートインデックスにフィルタとして適用することで、現在ログイン中のユーザーがアクセス可能なデータの検索結果を取得できる。
また、編集画面や単一表示画面などある一つのIDに対して追跡したい場合は、逆にデータを先に取得しそのACL-IDが、1.の結果に含まれているかで対象となる操作のallow/denyを判別可能となる。

ACLキャッシュ再構築タイミングについて

ACLキャッシュはあくまでもキャッシュである為、ユーザー・グループ・ACLに変更が生じた場合適宜再構築する必要がある。
具体的にどのタイミングで再構築が必要となるのか。その前にまず、ユーザー・グループ・ACLに変更が生ずるタイミングを確認する。

ユーザー・グループ・ACL変更タイミング

user
- create, update, delete
group
- create, update, delete
add users to groups
remove users from groups
acl
- create, update, delete

以上が変更タイミングとなる。注意点として、ACLのupdateには例えばPolicy(Negative/Positive)だけの修正や、権限リストだけの修正も含まれる。

さて、ここで実際にACLキャッシュが「無効」となり、再構築が必要となるタイミングを絞り込んでみる。結論から言うと以下に絞り込まれる。

delete { user | group }
{ add | remove } users { to | from } groups
{ create | update | delete } acl

以下に、これら以外がなぜ除外されたのか理由を述べる。

{ create | update } user が除外された理由
- create の時点ではまだいかなるACLにもそのユーザーIDは存在しない為、ACLは影響を受けない。よって除外。
- update において変更されるのはユーザーID以外のユーザー情報である。ACLはユーザーIDのみを取り扱う為、影響を受けない。よって除外。
{ create | update } group が除外された理由
- user に同じ。

ちなみに、delete { user | group } の処理には当然 add / remove も含まれている。しかし、処理のI/Fとしてメソッド（ロジック）を分割してしまっている為、別タイミングとして挙げている。
またACLのcreateタイミングに於いては、create時点で既に権限リストが初期データとして渡される可能性がある為、再構築の要有りと判断している。

ACLデータからACLキャッシュへの変換概要

各ACLキャッシュ再構築タイミングでの詳細を述べる前に、ACLデータを以下にして「キャッシュ」にconvertするのかその概要を、現状の段階でメモしておく。

まず、ACLデータの構成を改めて確認する。

ACLデータの構成

owner (ACL作成者のUserID)
name (ACLの名前："友達オンリー", "家族専用", "秘密の日記", "部長以上" など)
policy (allow/denyの優先順位：権限リストと併せて後述)
権限リスト
- { user | group } ID とアクセスレベルのペアのリスト

アクセスレベル とはアクセス権限を表す整数値・・・今のところは、である。現時点では以下の3つのうちいずれかの値を取る。

0 : アクセス禁止
1 : 読み込みのみ許可
2 : 読み・書きの両方を許可

policy と権限リストについて

policyは二つの値を持つ。 Positive と Negative である。POSI/NEGAとも省略する。以下に、policyがどのように権限リストの評価に影響するのかをまとめてみる。

次のような権限リストを想定してみる。

group1(user1, user3) : Level2
group2(user1, user2) : Level1
user1 : Level0
user2 : Level2
user3 : Level0

権限リストの評価に於いては、一旦グループを、その所属するユーザーに展開する。従って上記リストは次のように変形される。

user1 : Level0, Level1, Level2
user2 : Level1, Level2
user3 : Level0, Level2

このように、一つのUserIDに対して、グループを展開したことにより複数のアクセスレベルが同居する事になる。この優先順位を決定するのがpolicyとなる。
なお、権限リスト中のアイテムの上下関係は優先順位とは影響しない。つまり、上下関係は処理上なんら意味を持たない。

Positive policy の場合

Positive policy とは一言で言えば、要求されたアクセスレベル 以上が一つでもあれば許可 するポリシーである。

例1. 入力： user1, Level2 → 許可
- user1にはLevel2があるため、「以上」に該当し、許可される。
例2. 入力： user3, Level1 → 許可
- user3にはLevel2があるため、「以上」に該当し、許可される。

Negative policy の場合

Negative policy とは一言で言えば、要求されたアクセスレベル 未満が一つでもあれば拒否 するポリシーである。

例1. 入力： user1, Level1 → 拒否
- user1にはLevel0があるため、「未満」に該当し、拒否される。
例2. 入力： user2, Level2 → 拒否
- user2にはLevel1があるため、「未満」に該当し、拒否される。

ACLキャッシュの原理

ACLデータと実際の許可・拒否の判定基準は上記のような評価によって定められる。今のところは。

ACLキャッシュの原理は、ACLデータに登録されているユーザーの分だけ、上記評価結果を何らかの物理ファイルとしてキャッシュしておく仕組みである。
基本的には他のインデックス系と似たようなデータファイル構造を取る。

ディレクトリ構成（予想）

cache/
    acl/
        1.idx (UserID = 1)
        2.idx (UserID = 2)
        3.idx (UserID = 3)
        ...

各"*.idx"ファイル内容(実際は","や"|"や"&"ではなく特殊なコントロールコードで分割される)

#ACLID,LEVEL|OK_NG&LEVEL|OK_NG&LEVEL|OK_NG&...
100,1|1&2|0
200,1|0&2|0
300,1|1&2|1
...

なおLEVELについては、"0"は登録されない。LEVEL 0 は評価時に使われる。外部から「Level0についてこのユーザーが許可されているACLを取得したい」というケースはあり得ない。なぜなら、Level0はアクセス禁止を表しているからである。

ACLキャッシュに必要とされる（であろう）I/Fの予想

概要	入力	出力
許可されるACL ID群の取得	ユーザーID, アクセスレベル	一つ以上のACL ID
ユーザーと関わるACL ID群の無条件取得	ユーザーID	一つ以上のACL ID
ユーザーIDのエントリの作成, 削除	ユーザーID	処理の成否
キャッシュの新規作成・更新	ユーザーID, ACL ID	処理の成否
キャッシュの削除	ユーザーID, ACL ID	処理の成否

「エントリ」と呼んでいるのは、"ユーザーID.idx"ファイルの事である。つまり物理ファイルそれ自体の作成・削除操作である。
「キャッシュ」というのが、各idxファイルの中の実際のレコードである。ユーザーIDとACL IDのペアに対する、各アクセスレベルの評価結果のキャッシュデータである。

（以上は現時点での暫定予想。）

各タイミングにおけるACLキャッシュ再構築の詳細

ACLキャッシュの原理と、権限リストとpolicyの評価の仕組みを踏まえた上で、各再構築タイミングにおける処理の詳細を考えてみる。
その前に、処理の簡略化のため、新たに G2A という1:Nインデックスを追加する。これは、 アクセスレベルに関わらず 権限リストに登録されているグループと、ACL IDを結びつけるためのものである。詳細は後述。

ACLの作成・変更・削除 [#tb9348d9]

1. 実際にACLの本体データを操作する前に、ACLが既存の場合、以下の処理を行う。
- a. ACLの権限リストを展開し、UserID群を取得する。
- b. 各UserID群に対し、操作対象となるACL IDのキャッシュを削除する。
2. ACLの本体データを操作した後、権限リストを展開してUserID群を取得する。
3. 各UserID群に対し、操作対象となるACL IDのキャッシュを更新する。

ユーザーの削除

まずユーザーを削除できるための条件を確認しておく。そのユーザーがownerとなっているGroup, Category, Data, Acl が全て0件となっていることが必須条件である。実際はこの条件を満たすための確認作業が面倒くさいため、結局、ステータスを「ログイン禁止」にして無効化する措置が採られるとは思うのだけれど・・・。さておき。

1. ユーザーを削除する前に、該当UserIDを権限リストに含んでいるACL IDを、キャッシュのI/F機能により取得する。
2. 各ACL IDに対して、権限リストから該当UserIDを除去する。
3. 該当UserIDのキャッシュエントリ(=UserID.idxファイル)を削除する。
4. ユーザーの削除を実行する。

グループの削除

グループの削除条件は特に無い。なぜならグループIDが他と関係するのは、UserIDとのリレーションと、このACL権限リストだけだからである。

1. グループを削除する前に、該当GroupIDを権限リストに含んでいるACL ID群を、 G2Aインデックスより取得 し、以下の処理を行う。
- a. 各ACL毎の権限リストを展開し、UserID群を取得する。
- b. 各ACLの各UserID群に対し、ACL IDのキャッシュを削除する。
2. 各ACL IDに対して、権限リストから該当GroupIDを除去する。
3. ユーザーの削除を実行する。
4. 1. で取得した各ACL, User群に対し、ACL IDのキャッシュを更新する。

グループとユーザーのリレーションが変化する場合

これについては先に例を挙げた方が分かりやすい。ユーザーがグループより脱ける場合、グループに入る場合のそれぞれを考えてみる。

ユーザーがグループから脱ける場合

以下のような権限リストを持つACLを考えてみる。

group1 ( user1, user2 ) : Level 1
group2 ( user2, user3 ) : Level 2
user1 : Level 2
user2 : Level 0

ここで、user1がgroup1から脱けるとする。その場合、 キャッシュとして 影響するのは、user1のエントリのみである。user2が、user1と同じくgroup1に所属しているが、 user2の評価結果はなんら変化しない。 このため、キャッシュを更新するのはuser1のエントリに絞ることが可能となる。

ユーザーがグループに入る場合

以下のような権限リストを持つACLを考えてみる。

group1 ( user1, user3 ) : Level 1
user1 : Level 2
user2 : Level 0

ここで、user2がgroup1に入るとする。その場合、 キャッシュとして 影響するのは、user2のエントリのみである。user1やuser3が、同じくgroup1に所属しているが、 user1, user3の評価結果はなんら変化しない。 このため、キャッシュを更新するのはuser2のエントリに絞ることが可能となる。

まとめると

addもremoveも、次のような処理で共通になることが分かった。

1. 対象ユーザーの関連するACL ID群を無条件に、ACLキャッシュより取得する。
2. 対象グループを権限リストに含むACL ID群を G2A インデックスより取得する。
3. 1.と2.のANDを取得する。これが、ユーザー脱会により影響を受けるACL ID群である。
4. 対象ユーザーIDの、3.で取得したACL ID群に関してACLキャッシュを削除する。
5. 脱会処理を行う。
6. 対象ユーザーIDの、3.で取得したACL ID群に関してACLキャッシュを更新する。

2008年12月時点での追記

まだまだ悩みまくっていた時のメモ。
ここから大分変わってしまっていて、ACL絡みのインデックスも今では acl_to_data の１つしかない。
U2AやG2Aは結局不要となってしまって消えた。

ACLの再構築タイミングは殆どそのまま。
ACLの評価については、現時点では yb_AclCache クラスの normalize_permlist() と evaluate() メソッドに集約されている。仕様についてはテストケースを参照。まぁ評価の内実については上記メモからあまり変わっていない。グループからユーザを展開して、衝突についてはPolicyで解決するという流れ。

alpha-2の段階ではACLがグループの操作やカテゴリ操作、記事スレッドの操作にも及んでいたのだけれど、面倒くさくなったので alpha-3の時にマスタ管理は個別のroleに持たせて、記事スレッドの概念も削除。記事の作成権限を別途roleに含ませる事でその辺を管理するように直したりしている。

プレーンテキスト形式でダウンロード

現在のバージョン : 1
更新者: msakamoto-sf
更新日: 2008-12-23 13:20:42
md5:4724a341705570fe9d1726168cf7b25b
sha1:e2ce6ce8a3cc1de6e375ec43c0041a8fa4e434e6