Check는 질문 하나를 던진다. 이 사용자는 이 스냅샷에서 이 유저셋에 속하는가. 이에 답하려면 여러 서버에 걸친 수십 건의 읽기가 필요할 수 있다. 이 페이지는 Check 하나를 안쪽에서 따라간다. 그것이 되는 불리언 표현식, 그 부분들이 실행되는 순서, 일찍 멈출 수 있는 시점, 캐시에 남기는 것, 그리고 포기하는 지점이다.
인접한 내용은 다른 두 페이지가 다룬다. 관계 튜플과 유저셋은 같은 질문을 그래프 탐색으로서 가지 하나씩 따라간다. 아키텍처는 서버들을 가로지르는 요청을 따라간다. 일관된 해싱, 캐시 트리, 락 테이블, 읽기 풀링, 헤징이다. 이 페이지는 평가 내부에 머문다.
Check는 불리언 표현식이다
논문은 재작성 규칙이 없는 경우에서 시작한다. “Zanzibar evaluates ACL checks by converting check requests to boolean expressions”(Zanzibar는 검사 요청을 불리언 표현식으로 변환하여 ACL 검사를 평가한다)(§3.2.3). 사용자 U와 유저셋 ⟨object#relation⟩에 대해 논문의 식은 다음과 같다.
CHECK(U, ⟨object#relation⟩) = ∃ tuple ⟨object#relation@U⟩
∨ ∃ tuple ⟨object#relation@U′⟩, where
U′ = ⟨object′#relation′⟩ s.t. CHECK(U, U′)
첫 줄은 직접 일치다. 저장된 튜플이 그 사용자를 지정한다. 둘째 줄은 재귀다. 저장된 튜플이 다른 유저셋을 지정하고, 사용자가 그 유저셋에 속한다. 논문은 이러한 참조를 따라가는 것을 “포인터 추적(pointer chasing)“이라고 부르며, 이것이 “works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide”(대부분의 ACL 및 그룹 유형에서 잘 작동하지만, 간접 ACL이나 그룹이 깊거나 넓으면 비용이 커질 수 있다)라고 지적한다(§3.2.3). 재작성 규칙도 같은 표현식에 합류한다. “Userset rewrite rules are also translated to boolean expressions as part of check evaluation.”(유저셋 재작성 규칙도 검사 평가의 일부로 불리언 표현식으로 변환된다.)
논문의 그림 1에 있는 doc 설정을 보자(§2.3.1). viewer는 자신의 튜플, editor, 그리고 상위 폴더의 열람자의 합집합이고, editor는 자신의 튜플과 owner의 합집합이다. 다른 페이지들과 마찬가지로 folder#viewer에 재작성 규칙이 없다고 가정하고 Chen과 readme에 대해 풀어 쓰면 다음과 같다.
viewer(readme, chen) = this(readme#viewer, chen)
∨ editor(readme, chen)
∨ ∃ parent tuple readme#parent@folder:X : viewer(folder:X, chen)
editor(readme, chen) = this(readme#editor, chen)
∨ this(readme#owner, chen)
각 this(…)는 튜플 조회이고, 각 ∨는 트리의 노드다. “Chen은 doc:readme를 열람할 수 있는가?“는 어떤 하위 문제로 나뉘는가?
번호는 순서가 아니라 하위 문제의 이름이라는 점에 주목하라. 리프 ②, ④a, ④b, ⑥은 readme 자신의 튜플만 필요하다. 논문이 포워딩 키를 객체로 정하는 이유가 이것이다(§3.2.5). 이들은 모두 doc:readme를 담당하는 서버가 답할 수 있다. ⑦은 다른 객체에 대한 새로운 Check이므로 folder:A의 서버로 포워딩되며, 그 자체가 트리이고 여기서는 _this 조회 하나다.
모든 리프를 한꺼번에, 그리고 취소
리프는 어떤 순서로 실행되는가? 논문은 트리를 차례로 걷지 않는다. “To minimize check latency, we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.”(검사 지연 시간을 최소화하기 위해, 우리는 불리언 표현식 트리의 모든 리프 노드를 동시에 평가한다. 한 노드의 결과가 하위 트리의 결과를 결정하면 그 하위 트리의 다른 노드 평가는 취소된다.)(§3.2.3)
Chen의 검사에서 이것은 시간에 따라 어떻게 보이는가?
지연 시간은 가장 느린 리프가 아니라 결정적인 답에 이르는 가장 빠른 경로가 정한다는 점에 주목하라. parent 가지가 느렸고 Chen이 열람자가 아니었다면, 루트는 모든 자식이 거짓이라고 말할 때까지 기다려야 했을 것이다.
취소는 일을 줄이지만 틈을 남긴다. 취소된 하위 검사는 결과를 캐시에 쓰지 않으며, 다른 요청이 락 테이블에서 그 결과를 기다리고 있을 수 있다. 논문은 바로 이 문제에 부딪혔다. “indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated.”(상위 ACL 검사의 결과가 이미 결정되면 간접 ACL 검사가 자주 취소된다. 그러면 캐시 키가 채워지지 않은 채로 남는다.) 그 해결책은 이것이다. “we delay eager cancellation when there are waiters on the corresponding lock table entry”(해당 락 테이블 항목에 대기자가 있으면 조기 취소를 늦춘다)(§3.2.5).
각 연산자는 언제 일찍 멈출 수 있는가
논문은 하위 표현식을 결합하는 세 가지 방법, “union, intersection, and exclusion”(합집합, 교집합, 차집합)을 들고(§2.3.1), 그 모두에 하나의 취소 규칙을 서술한다. 하위 트리가 언제 “결정”되는지는 연산자에 따라 다르다. 각 연산자에는 어떤 답 하나면 충분한가?
비대칭에 주목하라. 각 연산자에는 일찍 도착할 수 있는 답 하나와 모든 자식이 필요한 답 하나가 있다. 합집합에서 일찍 오는 답은 예이고, 교집합과 차집합에서는 아니요다. 따라서 합집합으로 작성된 권한은 가장 빠른 경로만큼 빠르게 “허용”이라고 답하지만, 교집합이나 차집합이 있는 권한은 필요한 부분 중 가장 느린 것만큼만 빠르게 “허용”이라고 답한다. 표로 정리하면 다음과 같다.
| 연산자 | 일찍 결정되는 경우 | 모든 자식이 말해야 하는 것 |
|---|---|---|
합집합 A ∪ B |
자식 하나라도 참 → 참 | 거짓이라고 답하려면 거짓 |
교집합 A ∩ B |
자식 하나라도 거짓 → 거짓 | 참이라고 답하려면 참 |
차집합 A − B |
기준이 거짓, 또는 제외 대상이 참 → 거짓 | 참이라고 답하려면 기준은 참이고 제외 대상은 거짓 |
제품들도 같은 논리를 따른다. OpenFGA의 check.go(v1.22.1)에서 합집합 리듀서는 첫 허용 결과에서 반환하고(“Short-circuit success”), 교집합 리듀서는 첫 불허 결과에서 반환하며(“Short-circuit failure”), 차집합 리듀서는 기준과 빼는 쪽을 동시에 실행하고 “base is false”(기준이 거짓)이거나 “subtract is true”(빼는 쪽이 참)일 때 불허를 반환한다. 교집합과 차집합에 관한 AuthZed의 글(2022-03-03)은 이 연산자들에 대해 “SpiceDB can only partially short-circuit the subproblems”(SpiceDB는 하위 문제를 부분적으로만 단락시킬 수 있다)라고 하며, 그 예에서는 교집합의 한 가지가 아니요라고 하자 “SpiceDB was able to cancel the other check immediately”(SpiceDB는 다른 check를 즉시 취소할 수 있었다). 합집합에 대해서는 그 이전 글(2021-03-17)이 간단히 말한다. “any path found suffices to grant permission!”(경로를 하나라도 찾으면 권한을 부여하기에 충분하다!)
하위 결과를 스냅샷 단위로 캐시하기
트리의 모든 노드는 답이 있는 질문이며, 논문은 그 모두를 캐시한다. 서버들은 “form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing”(포인터 추적 중에 평가된 중간 검사 결과를 포함하여, 읽기와 검사 평가 모두를 위한 분산 캐시를 형성한다)(§3.2.5). 위의 ⑦, “Chen은 folder:A#viewer에 속하는가”가 그런 중간 결과다. 나중에 같은 질문에 도달하는 검사는 이를 재사용할 수 있다.
재사용을 안전하게 만드는 것은 무엇인가? 결과는 특정 스냅샷에서만 참이다. 논문은 스냅샷을 키에 넣는다. “We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys.”(우리는 스냅샷 타임스탬프를 캐시 키에 인코딩하여 다른 스냅샷에서 평가된 결과의 재사용을 피한다.) 그런 다음 평가 타임스탬프를 “to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies”(요청 zookie의 오래된 정도 제약을 준수하면서 1초나 10초 같은 거친 단위로) 올림하여, 대부분의 검사가 같은 몇 개의 타임스탬프에 놓이게 한다(§3.2.5. 올림은 일관성 페이지에 그려져 있다).
캐시된 하위 결과는 언제 도움이 되고, 언제 미스가 되는가?
무효화 단계가 없다는 점에 주목하라. 스냅샷을 키로 하는 항목은 결코 틀린 값이 될 수 없다. 13 s 시점의 데이터는 바뀌지 않기 때문이다. 평가가 나중 타임스탬프로 옮겨 가면 그 항목은 더 이상 요청되지 않을 뿐이다. SpiceDB의 같은 방식에 관한 AuthZed의 글(2023-05-10)도 같은 생각을 밝힌다. “For any given problem or sub-problem, at a specified time, the result to the check is immutable”(어떤 문제나 하위 문제든 지정된 시각에서 검사 결과는 불변이다), 그리고 “if we were to change the evaluation timestamp, the cache keys would change as well”(평가 타임스탬프를 바꾸면 캐시 키도 바뀐다).
§3.2.5의 메커니즘 두 가지가 이 캐시를 둘러싸고 있으며, 둘 다 아키텍처 페이지에 그려져 있다. “at both the caller and the callee of internal RPCs”(내부 RPC의 호출자와 피호출자 양쪽에서) 캐시하여 형성되는 캐시 트리, 그리고 “Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.”(같은 캐시 키를 공유하는 요청 중 하나만 처리를 시작하고, 나머지는 캐시가 채워질 때까지 대기한다.)인 락 테이블이다.
제품에서는 다음과 같다.
- SpiceDB는
--datastore-revision-quantization-interval(기본값5s)이 정하는 구간으로 리비전을 올림하고(dsconfig/config.go, v1.57.1), 디스패처를singleflight계층으로 감싸 “dispatch requests that were single flighted”(single flight된 디스패치 요청)를 센다. 이 계층이 락 테이블의 역할을 한다. - OpenFGA의 검사 캐시는 기본적으로 꺼져 있다(
checkQueryCache.enabled는false, 켜면 TTL10s)(configuration). 그 항목은 스냅샷에 속하는 대신 TTL이 지나면 만료되며, 그래서 OpenFGA는 캐시를 건너뛰기 위한HIGHER_CONSISTENCY모드가 필요하다(consistency. TrueTime 없이 순서 정하기 참조).
읽기는 검사별로 풀링된다
리프 ②, ④a, ④b, ⑥은 모두 doc:readme의 행을 읽는다. 각 읽기를 따로 보내는 대신 “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner”(우리는 Spanner로 가는 읽기 RPC 수를 최소화하기 위해 같은 ACL 검사에 대한 읽기를 묶는 풀링 메커니즘을 적용한다)(§3.2.3). 논문은 이 문장 이상으로 메커니즘을 설명하지 않는다. 아키텍처 페이지는 네 읽기가 한 서버에서 만나는 것을 그린다. 객체와 관계 순으로 정렬된 저장소 배치(§3.1.1)가 이 읽기들을 인접한 행에 대한 범위 읽기로 만들 수 있게 한다.
얼마나 깊이 갈 수 있는가
CHECK(U, U′)의 재귀에는 내장된 한계가 없다. 그룹은 그룹을 포함하는 그룹을 포함할 수 있고, 데이터 모델의 어떤 것도 순환을 금지하지 않는다. 검사가 순환을 만나면 무엇을 하는가?
논문은 수치를 정하지 않는다. 깊고 넓은 중첩은 “selected namespaces that exhibit such structure”(그러한 구조를 보이는 일부 선택된 네임스페이스)에 대해 Leopard로 처리하며(§3.2.4. Leopard 페이지 참조), §5는 “safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups)”(잠재적으로 깊은 재귀(예: 계층적 그룹에 대한 멤버십 검사)에도 불구하고 안전한 포인터 추적)을 주장하지만 무엇이 그것을 안전하게 하는지는 그 이상 말하지 않는다. §3.2.6의 클라이언트별 한도는 CPU와 처리 중인 RPC를 제한할 뿐 깊이를 제한하지 않는다. 제품들은 명시적인 한도를 정한다.
| 시스템 | 한도 | 기본값 | 도달했을 때 | 출처 |
|---|---|---|---|---|
| 논문 | 명시 없음 | 없음 | 기술되지 않음 | §3.2.4, §5 |
| SpiceDB | --dispatch-max-depth |
50 | 오류: “the check request has exceeded the allowable maximum depth of 50” | Cyclical relationships and traversal limits, serve.go |
| OpenFGA | resolveNodeLimit |
25 | 오류. 순환은 먼저 감지되어 불허로 답한다 | configuration, check.go |
| OpenFGA | resolveNodeBreadthLimit |
10 | “how many nodes on a given level can be evaluated concurrently”(한 수준에서 동시에 평가할 수 있는 노드 수)를 제한 | configuration |
| Ory Keto | limit.max_read_depth |
5 | 전역 최댓값. 요청은 이를 낮추기만 할 수 있다 | config.schema.json |
SpiceDB 문서에 따르면 SpiceDB에는 별도의 순환 감지기가 없다. 순환은 깊이 제한에 걸릴 때까지 실행되어 매우 깊은 계층과 같은 오류를 반환하며, 문서는 방문한 객체를 추적하는 방식을 의미론과 성능상의 이유로 피했다고 설명한다(recursion and max depth). OpenFGA의 LocalChecker는 요청마다 방문한 튜플 키의 집합을 유지하고, 키가 반복되면 CycleDetected와 함께 불허를 반환한다(check.go, hasCycle). 두 한도 모두 한 경로를 따른 홉 수를 세며, 이는 첫 번째 그림의 트리 깊이에 해당한다. 논문의 “evaluate all leaf nodes … concurrently”(모든 리프 노드를 … 동시에 평가)를 제한하는 것은 이 가운데 resolveNodeBreadthLimit뿐이다.
출처
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.3.1, §3.1.1, §3.2.3, §3.2.4, §3.2.5, §3.2.6, §5.
- AuthZed, Check it out: How permissions are answered in SpiceDB and Authzed, 2021-03-17 (vendor blog).
- AuthZed, Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed, 2022-03-03 (vendor blog).
- AuthZed, Hotspot Caching in Google Zanzibar and SpiceDB, 2023-05-10 (vendor blog).
- AuthZed, Cyclical Relationships and Traversal Limits, SpiceDB docs.
- SpiceDB v1.57.1 source:
pkg/cmd/serve.go,pkg/cmd/datastore/dsconfig/config.go,internal/dispatch/singleflight/singleflight.go. - OpenFGA, Configuring OpenFGA and Query Consistency Modes.
- OpenFGA v1.22.1 source:
internal/graph/check.go. - Ory Keto,
.schema/config.schema.json(limit.max_read_depth).