Data deletion in multi-tenant database

Patent metadata

Field	Value
Publication number	US-12086100-B2
Application number	US-202117171879-A
Country	US
Kind code	B2
Filing date	Feb 9, 2021
Priority date	Feb 9, 2021
Publication date	Sep 10, 2024
Grant date	Sep 10, 2024

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Stripe Inc

Inventors

• Wang Sheng
• Doan Tuan

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/162

  Delete operations (erasing in storage systems G06F3/0652) · CPC title

• G06F16/128

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title

• G06F16/215

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title