Zanzibar-style authorization service

Design a centralized authorization service (Zanzibar-style) for a document collaboration product with 200M documents, deeply nested folders, and group-based sharing where a single 'can user U view doc D?' check may traverse thousands of relationship tuples. Target: p99 check latency under 10ms at 500K checks/sec, and a guarantee that a user who was just removed from a folder cannot still read its children. How do you store relationships, evaluate nested checks fast, and avoid the 'new enemy' problem where stale caches leak access after a revoke?