Data deletion in multi-tenant database
In an example embodiment, data in a multi-tenant database is organized as a graph representing the relationships among all documents and tenants. Specifically, each document is represented as a node in the graph and each tenant also is represented as a node. The relationships between the documents themselves, or between a document and a graph, are then represented as edges in the graph. A list of tenants whose data should be marked for deletion (e.g., former customers who no longer have a relationship with the entity maintaining the database) may be maintained. Periodically (e.g., once a week), this list of tenants and the relationship graph are fed as input into a graph search algorithm that generates smaller relationship graphs comprised only of documents associated with those accounts.
1. A method comprising:
obtaining a document graph of a multi-tenant database, the document graph having a first plurality of nodes, a second plurality of nodes, and edges connecting nodes in the first plurality of nodes and the second plurality of nodes, each node in the first plurality of nodes representing a document stored in the multi-tenant database, each node in-the second plurality of nodes representing a tenant of the multi-tenant database, each edge connecting a node in the first plurality of nodes to a node in the second plurality of nodes representing ownership of a corresponding document by a corresponding tenant, and each edge connecting a node in the first plurality of nodes to another node in the first plurality of nodes indicating a relationship between respective documents, the document graph having one or more cycles, each edge having a direction from a source node to a target node;
obtaining a list of one or more closed tenants, wherein a closed tenant is a former customer who no longer has a relationship with an entity associated with the multi-tenant database;
building a subgraph for each of the one or more closed tenants, each subgraph being an acyclical graph formed by iteratively traversing the document graph in a backwards direction through-each edge beginning at a node in the second plurality of nodes corresponding to a closed tenant of the one or more closed tenants and proceeding to a root node of the document graph, wherein at each iteration visited nodes are marked as visited and processing of the iteration stops when a node previously marked as visited is reached, and wherein each iteration begins at all source nodes for an edge traversed in an immediately preceding iteration, the subgraph including a first group of the first plurality of nodes, the closed tenant excluded from the multi-tenant database;
traversing each subgraph in a forward direction through each edge having a source node visited during building of the subgraph to identify tenant nodes corresponding to the documents among the first group of the first plurality of nodes;
identifying, for all of the documents among the first group of the first plurality of nodes, corresponding auto-delete edges of the subgraph for at least one of the closed tenants;
traversing, for at least one of the one or more closed tenants, all of the auto-delete edges for the subgraph; and
deleting, for the at least one of the one or more closed tenants and with the traversing all of the auto-delete edges, all documents from the multi-tenant database linked with the corresponding auto-delete edges, the plurality of documents each corresponding to a second group of the first plurality of nodes from the subgraph that excludes documents corresponding to the identified tenant nodes.
2. The method of claim 1 , further comprising forming the document graph by:
obtaining a set of foreign keys in a collections database;
generating metadata from the set of foreign keys; and
generating the document graph using documents in the collections database and the metadata.
3. The method of claim 2 , wherein the metadata indicates, for a collection of documents in the collections database, all foreign keys for each document in the collection of documents.
4. The method of claim 3 , wherein the metadata further indicates that a role corresponding to a foreign key among the foreign keys indicated by the metadata is optional.
5. The method of claim 3 , wherein the metadata further indicates which foreign keys are a backedge.
6. The method of claim 3 , wherein the metadata further indicates which foreign keys represent corresponding auto-delete edges.
7. The method of claim 2 , further comprising indexing each edge in the document graph using an inverted index.
8. The method of claim 2 , wherein the collections database is in the form of shard snapshots.
9. A system comprising:
a network;
one or more processors; and
a memory storing instructions that, when executed by at least one processor among the one or more processors, cause the at least one processor to perform operations comprising:
obtaining a document graph of a multi-tenant database, the document graph having a first plurality of nodes, a second plurality of nodes, and edges connecting nodes in the first plurality of nodes and the second plurality of nodes, each node in the first plurality of nodes representing a document stored in the multi-tenant database, each node in the second plurality of nodes representing a tenant of the multi-tenant database, each edge connecting a node in the first plurality of nodes to a node in the second plurality of nodes representing ownership of a corresponding document by a corresponding tenant, and each edge connecting a node in the first plurality of nodes to another node in the first plurality of nodes indicating a relationship between respective documents, the document graph having one or more cycles, each edge having a direction from a source node to a target node;
obtaining a list of one or more closed tenants, wherein a closed tenant is a former customer who no longer has a relationship with an entity associated with the multi-tenant database;
building a subgraph for each of the one or more closed tenants, each subgraph being an acyclical graph formed by iteratively traversing the document graph in a backwards direction through each edge beginning at a node in the second plurality of nodes corresponding to a closed tenant of the one or more closed tenants and proceeding to a root node of the document graph, wherein at each iteration visited nodes are marked as visited and processing of the iteration stops when a node previously marked as visited is reached, and wherein each iteration begins at all source nodes for an edge traversed in an immediately preceding iteration, the subgraph including a first group of the first plurality of nodes, the closed tenant excluded from the multi-tenant database;
traversing each subgraph in a forward direction through each edge having a source node visited during building of the subgraph to identify tenant nodes corresponding to the documents among the first group of the first plurality of nodes;
identifying, for all of the documents among the first group of the first plurality of nodes, corresponding auto-delete edges of the subgraph for at least one of the closed tenants;
traversing, for at least one of the one or more closed tenants, all of the auto-delete edges for the subgraph; and
deleting, for the at least one of the one or more closed tenants and with the traversing all of the auto-delete edges, all documents from the multi-tenant database linked with the corresponding auto-delete edges, the plurality of documents each corresponding to a second group of the first plurality of nodes from the subgraph that excludes documents corresponding to the identified tenant nodes.
10. The system of claim 9 , wherein the operations further comprise forming the document graph by:
obtaining a set of foreign keys in a collections database;
generating metadata from the set of foreign keys; and
generating the document graph using documents in the collections database and the metadata.
11. The system of claim 10 , wherein the metadata indicates, for a collection of documents in the collections database, all foreign keys for each document in the collection of documents.
12. The system of claim 11 , wherein the metadata further indicates that a role corresponding to a foreign key among the foreign keys indicated by the metadata is optional.
13. The system of claim 11 , wherein the metadata further indicates which foreign keys are a backedge.
14. The system of claim 11 , wherein the metadata further indicates which foreign keys represent corresponding auto-delete edges.
15. The system of claim 10 , further comprising indexing each edge in the document graph using an inverted index.
16. The system of claim 10 , wherein the collections database is in the form of shard snapshots.
17. A non-transitory machine-readable medium comprising instructions which, when read by a machine, cause the machine to perform operations comprising:
obtaining a document graph of a multi-tenant database, the document graph having a first plurality of nodes, a second plurality of nodes, and edges connecting nodes in the first plurality of nodes and the second plurality of nodes, each node in the first plurality of nodes representing a document stored in the multi-tenant database, each node in the second plurality of nodes representing a tenant of the multi-tenant database, each edge connecting a node in the first plurality of nodes to a node in the second plurality of nodes representing ownership of a corresponding document by a corresponding tenant, and each edge connecting a node in the first plurality of nodes to another node in the first plurality of nodes indicating a relationship between respective documents, the document graph having one or more cycles, each edge having a direction from a source node to a target node;
obtaining a list of one or more closed tenants, wherein a closed tenant is a former customer who no longer has a relationship with an entity associated with the multi-tenant database;
building a subgraph for each of the one or more closed tenants, each subgraph being an acyclical graph formed by iteratively traversing the document graph in a backwards direction through each edge beginning at a node in the second plurality of nodes corresponding to a closed tenant of the one or more closed tenants and proceeding to a root node of the document graph, wherein at each iteration visited nodes are marked as visited and processing of the iteration stops when a node previously marked as visited is reached, and wherein each iteration begins at all source nodes for an edge traversed in an immediately preceding iteration, the subgraph including a first group of the first plurality of nodes, the closed tenant excluded from the multi-tenant database;
traversing each subgraph in a forward direction through each edge having a source node visited during building of the subgraph to identify tenant nodes corresponding to the documents among the first group of the first plurality of nodes;
identifying, for all of the documents among the first group of the first plurality of nodes, corresponding auto-delete edges of the subgraph for at least one of the closed tenants;
traversing, for at least one of the one or more closed tenants, all of the auto-delete edges for the subgraph; and
deleting, for the at least one of the one or more closed tenants and with the traversing all of the auto-delete edges, all documents from the multi-tenant database linked with the corresponding auto-delete edges, the plurality of documents each corresponding to a second group of the first plurality of nodes from the subgraph that excludes documents corresponding to the identified tenant nodes.
18. The non-transitory machine-readable medium of claim 17 , wherein the operations further comprise forming the document graph by:
obtaining a set of foreign keys in a collections database;
generating metadata from the set of foreign keys; and
generating the document graph using documents in the collections database and the metadata.
19. The non-transitory machine-readable medium of claim 18 , wherein the metadata indicates, for a collection of documents in the collections database, all foreign keys for each document in the collection of documents.
20. The non-transitory machine-readable medium of claim 19 , wherein the metadata further indicates that a role corresponding to a foreign key among the foreign keys indicated by the metadata is optional.