Like pphysch said, using RBAC generally gets you 90% or more of the way there on this, and a good intro to this concept is the Tailscale post: https://tailscale.com/blog/rbac-like-it-was-meant-to-be/
In most cases (even with many 100s of thousands or millions of users), there are far fewer _roles_. So you can generally answer the question of "which users can access this resource" by answering the questions "which roles can access this resource", and "which users have those roles". If you're using SQL to store roles and role assignments, your query for all users becomes:
select * from users
join user_roles on user_roles.user_id = users.id
where user_roles.role_id in [... small list ...]
All that being said, I think there's definitely more to be written here. Keep a lookout -- we might do some more writing about the topic.
If you use something like a bitmap index (e.g. Roaring Bitmaps), you can easily manage roles in-line on each user row if the role membership is typically sparse.
You can still maintain a separate Roles table as a canonical reference, but you would no longer need to join on it to determine who has what.
This all assuming you don't need to make queries along the axis of "give me every user with role X".
But yeah, that's the cleanest way to go, if you can.
This is actually a really hard problem and depends on the systems with which you are integrating. We call this problem "ACL filtering"[2] and there are two general strategies: pre and post filtering.
We have a blog post[3] describing our API for pre-filtering which can stream results that you can then use build a SQL query or data-structures like bloom filters/bitmaps. We currently have a proposal on GitHub[4] for an extension to that strategy adding a denormalization/caching layer (which is applying a similar strategy to the Leopard Indexing system internally at Google).
You might also be surprised at the performance you can achieve with post-filtering by building an iterator in your programming language of choice that will batch together permission checks and amortize the cost of filtering those results from the set of all results that you pull out of your database.
Additionally, if you're interested deeper database specific integrations, there are hooks into various components such as Postgres's Row Level Security, but that typically means eschewing a cloud service to operate your database for you (e.g. RDS) so that you can install your own plugins.
[0]: https://github.com/authzed/spicedb
[1]: https://authzed.com/blog/what-is-zanzibar/
[2]: https://docs.authzed.com/reference/glossary#acl-filtering
The key insight is to define policies as purely virtual; a policy never refers to real users or real resources. Instead, it refers to virtual users (via "roles") or virtual resources (via "tags"), which can then be associated with real users/resources without modifying the policy.
It also wouldn't work in the scenarios I've mentioned in other comments.
What if you sell reporting on location based data with access control, and customers want fine grain control on who sees what? Then you also can't always use groups. Example: I'm a Healthcare provider with 15k locations. Manager X is responsible for 5k locations, so when we create reports we filter all the data by those 5k locations first. Same with viewing any data in the product.
Just curious how others approached this. You could obviously do grouping somehow.
We can obviously manage this still with careful optimization but I'm not sure if this is kind unlimitedly scalable say for 1M+ consumers. I wonder if this can only be handled by reframing business requirements (like location as you are using) or someone has better design/ideas.
I think the best solution potentially is to have the system monitor the "whale" users and have a special case where you turn their list of resources into a single group/tag behind the scenes and add this single identifier to all the relevant objects. It'd be hell to get right and keep consistent but it'd be fast.
The users are authorized on consumer (a set of consumer + a set of roles or action they can do). We have been able to move the role aspect to app layer very cheaply. User A is doing X say running a report, we know role R is needed for it, we then ask the system run the report for the customers user A has access to it with index on consumer for all resources in system allowing fast query. But if your consumer list is too large the efficiency falls.
We can't make auto groups at system level because adding a group column in resource level and updating would be too expensive. There's no just large grouping. Some users say have access to consumer 1..100K where another has random 100K from 1..1M.
I tend to keep admin RBAC simple and group-oriented. It's mostly for direct data access permissions (per table, etc), but can add others too. Different groups for different departments. Mainly for internal CRUD apps at first (e.g. Django Admin).
OTOH, User-facing RBAC is project-oriented and uses the virtual policy system described by Tailscale. The users themselves, in a project-manager role, can manage their own policies, memberships, and resources tags. I like to provide sane defaults and support for modifying policies should they even need it. Importantly, one user can have membership in different projects with different roles.
You'd create a project with the 15K resources, add the customer to it in a manager role, and then they choose the policies, tags, and roles to make it work for their organization.
Ofc, admins can also be users. Simply create one or more projects for internal use.
https://research.google/pubs/pub48190/
"This paper presents the design, implementation, and deployment of Zanzibar, a global system for storing and evaluating access control lists. Zanzibar provides a uniform data model and configuration language for expressing a wide range of access control policies from hundreds of client services at Google, including Calendar, Cloud, Drive, Maps, Photos, and YouTube. Its authorization decisions respect causal ordering of user actions and thus provide external consistency amid changes to access control lists and object contents. Zanzibar scales to trillions of access control lists and millions of authorization requests per second to support services used by billions of people. It has maintained 95th-percentile latency of less than 10 milliseconds and availability of greater than 99.999% over 3 years of production use."
If you use a webhook you don't have to worry about this, since the user doesn't get to see what you forward as the authorization claims payload. But if you're using a JWT to hold state, since JWT's are publicly viewable it has to be non-obvious and non-deterministic.
IE, something like:
{ "user_id": 5316, "$2a$09$ckHFIEsR8Sjveh1ynOLKguynRDGjEfMCZz0vsUk/Jtm/cW1SxibaK": "$2a$09$pCyjFN6perhHNspS1NFj0eScZ4.ZlOzzPMXhoMrYVmNLMx3MvXdYK" }
Probably you would want to choose more obscure/uncommon words. I'm not familiar with the details of hashing but it seems like a good idea.
Then you can attach the role (or other identifying) metadata to each request in a way that isn't immediately obvious what it's for.
Disclaimer: I'm not a security expert, possible (probable?) there is a gaping hole in this and it's an awful idea.
This is not exactly an answer but it's worth remembering that the lower the selectivity of a condition is the more likely it'll turn out that brute force and ignorance will actually work out better - loading data in batches and filtering out the ones that are disallowed by a secondary positive index lookup (assuming you've pre-materialised your 'is disallowed' list) could easily turn out to be a better option for a lot of cases than trying to be more clever than that.
The more general question is of course rather more complicated and interesting, but other people already had better answers than I do there in other replies.
I don't understand why you can't use groups to organize access control. Is this a customer-enforced restriction? Or a technical one?
One place for example sold location-based software, so users could have access to say 10k out of 100k locations, but those locations might not always be next to each other. Data would be stored with a location id, and to do things like "show the average star rating for the locations this user has access to", we'd do "aggregate star rating where location id IN [....]"
CREATE TABLE locations (
location_id INT PRIMARY KEY,
rating INT
);
CREATE TABLE authorized_locations (
user_id INT REFERENCES users (user_id),
location_id INT REFERENCES locations (location_id)
);
CREATE INDEX authorized_locations_user_id_idx ON authorized_locations (user_id);
CREATE INDEX authorized_locations_location_id_idx ON authorized_locations (location_id);
SELECT AVG(rating) FROM locations JOIN authorized_locations USING (location_id) WHERE user_id = $1;A better example would be:
Product {LocationID, Rating} User{id} UserLocations{UserID, locationID)
However, let's say you have an architecture where you have 100s of these "product" tables, since every piece of the app restricts access by location. So not only do you have Product but maybe you have FormResult{LocationID}, Feedback{LocationID} etc.
So for a service to find out what a user has access to, first they call the User service to get a list of locations, and then they pass the big list of ids to their own DB, whatever that DB is.
I guess this is one case where a monolith and good ol SQL would win. :)
I suppose you could use some sort of bloom filter, or create/maintain groups behind the scenes somehow, but haven't seen many articles cover this.