Full disclosure: I'm a founder of Authzed (YC W21)[0], which is a productized Zanzibar system.
> just want to understand what makes it "highly scalable", as it isn't clear from the article.
While this post might not cover in depth why their system is scalable, the Zanzibar paper[1] and this post[2] about Zanzibar covers why similar systems are scalable. A oversimplification would be to say that finding a path between two nodes in a graph can be recursively broken down and performed in parallel -- the Authzed implementation looks roughly similar to a map reduce.
>Are ALL permissions stored as an Object::relation pair? i.e. do you need to register permissions for all new entities relationships, or do you have some way of storing more dynamic permissions?
Zanzibar implementations do have graph schemas (called Namespace Configs in the paper) which offer set operations for computing dynamic relationships. When you create a new user or object in your app, you typically also write a few relationships into Zanzibar and the rest of their permissions are implicitly granted through the computed definitions in your schema.
If you're interested in learning more about Zanzibar, we're giving a PapersWeLove talk that will be streamed on Twitch next week: https://www.meetup.com/papers-we-love/events/278148236/
[0]: https://authzed.com
[1]: https://research.google/pubs/pub48190/
[2]: https://authzed.com/blog/what-is-zanzibar/