Model user-to-resource access permissions in a graph database and migrate to it

Design how to store which people can access which resources in a graph database, and how to answer access questions from it. The access data currently lives in an existing database, so the design must also cover moving it to the graph database. The interviewer focused on three areas: the graph schema, how the design scales, and how to migrate from the existing database. ### Constraints and Clarifications - The reported question does not define the access model. Settle how access is granted, for example directly to a person, through groups or roles, or inherited through a hierarchy of resources, before designing the schema. - The existing database's technology, the data volumes and the latency targets are not given. Ask, or state your assumptions. ### Clarifying Questions - Is access granted directly to people, through groups or roles, or both? Can groups contain other groups? - Are resources nested, for example folders inside projects, and does access to a parent imply access to its children? - Are there several access levels, such as read, write and admin, and can access be explicitly denied? - How many people, groups, resources and grants exist, and how many access checks per second happen compared with permission changes? - How fast must an access check be, and how quickly must a revoked permission take effect? - What database holds the data today, and must the migration happen without downtime? ### Part 1 — Graph schema and access queries Design the vertices, edges and properties that represent people, resources and the permissions between them. Show how the schema answers "can this person access this resource?" and "which resources can this person access?". ```hint What a permission is in the graph Decide whether a permission is best stored as an edge, as a vertex or as a property, and what each choice means for the two queries above and for recording who granted it and when. ``` ```hint Bound the walk An access check that follows group memberships and resource nesting could wander through a large part of the graph. Decide which paths it must follow, in which direction, and how long they may be. ``` #### What This Part Should Cover - Vertex and edge types, with properties such as access level, expiry and audit fields - The traversal for an access check and for listing a person's resources - How groups or roles, nested resources and any explicit denials are represented - Indexes that make the starting vertices and the permission lookups fast ### Part 2 — Scalability How does the design hold up as the number of people, resources and access checks grows? ```hint Vertices with millions of edges A group that every employee belongs to, or a folder that holds millions of documents, has an enormous number of edges. Think about what that does to traversals and to splitting the graph across machines. ``` ```hint Reads dwarf writes Use the ratio of access checks to permission changes to decide what to cache or precompute, then work out what that means when a permission is revoked. ``` #### What This Part Should Cover - Access-check latency, with caching or precomputation and their invalidation - Partitioning or replicating the graph, and the cost of traversals that cross machines - Handling of very high-degree vertices - The write path for grants and revocations, and how quickly changes become visible ### Part 3 — Migration from the existing database How would you move the permission data, and the services that read and write it, from the existing database to the graph database? ```hint Two stores at once For a while, both stores will hold permission data. Decide which one is authoritative at each step and how you would notice that they disagree. ``` ```hint Prove it before relying on it Think about how to show that the graph answers real access checks exactly as the old system does before any request depends on its answer. ``` #### What This Part Should Cover - Mapping the existing tables to vertices and edges, and the initial bulk load - Keeping both stores in sync during the transition - Verifying the graph's answers before cutover - A staged cutover with a rollback path ### What a Strong Answer Covers - A clear reason to use a graph database for this access model, weighed against staying relational - A schema whose traversals match the access rules agreed at the start - Predictable access-check latency at scale, including high-degree vertices and revocation under caching - A migration with no downtime, verification against the old system, and rollback - An audit trail of who granted or revoked access, when, and through which path a person has access ### Follow-up Questions - A person is removed from a group. How do you make sure they lose access promptly when access checks are cached? - How would you answer "who can access this resource, and through which path?" for an auditor? - How do you stop a cycle in group nesting from making traversals loop? - During the migration, shadow comparisons show the graph granting access that the old system denies for a small fraction of checks. How do you investigate?