# US 2021/0240674 A1 · Reducing requests using probabilistic data structures

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0240674 A1
- Document ID: US20210240674A1
- Status: Published application
- Kind: A1
- Application number: 16/777,872
- Filed: 2020-01-30
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: salesforce.com, inc.
- Applicants: salesforce.com, inc.
- Inventors: Atish Agrawal; Jameison Bear Martin
- Web page: https://patentgrep.com/patent/US20210240674A1

## CPC

- G06F 16/212: {with details for data modelling support}
- G06F 16/24539: {using cached or materialised query results}
- G06F 12/0804: with main memory updating (G06F12/0806 takes precedence)
- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/24552: {Database cache management}
- G06F 2212/601: Reconfiguration of cache memory
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques are disclosed relating to providing and using probabilistic data structures to at least reduce requests between database nodes. In various embodiments, a first database node processes a database transaction that involves writing a set of database records to an in-memory cache of the first database node. As part of processing the database transaction, the first database node may insert, in a set of probabilistic data structures, a set of database keys that correspond to the set of database records. The first database node may send, to a second database node, the set of probabilistic data structures to enable the second database node to determine whether to request, from the first database node, a database record associated with a database key.

## Claims

### Claim 1

A method, comprising:
receiving, by a database node, a request to perform a database transaction that involves writing a set of database records to an in-memory cache of the database node and inserting a corresponding set of database keys into probabilistic data structures; and
performing, by the database node, the database transaction, including by:
for each probabilistic data structure in which at least one database key is inserted for the database transaction, registering the database transaction with that probabilistic data structure, wherein the registering is performed to prevent that probabilistic data structure from being deleted while the database transaction is registered;
determining that a duration of the database transaction exceeds a specified amount of time; and
in response to the determining, unregistering the database transaction from each probabilistic data structure for which the database transaction was previously registered.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
in response to the determining, the database node delaying insertion of database keys for the database transaction into probabilistic data structures until a pre-commit phase of the database transaction by the database node.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
in response to initiating the pre-commit phase for the database transaction, the database node restarting insertion of the set of database keys of the database transaction into a set of probabilistic data structures.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
before committing the database transaction, the database node deleting at least one of the probabilistic data structures from which the database transaction was unregistered.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
in response to initiating a pre-commit phase the database transaction, the database node inserting the set of database keys of the database transaction into a set of probabilistic data structures.
sending, by the database node to another database node, the set of probabilistic data structures to enable the other database node to determine whether to request, from the database node, a database record associated with a particular database key.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
in response to the determining, the database node inserting remaining database keys of the set of database keys into a single probabilistic data structure.

### Claim 7 (depends on 1)

The method of claim 1, wherein a particular one of the probabilistic data structures includes metadata that specifies a number of active transactions for which database keys have been inserted in the particular probabilistic data structure, wherein the particular probabilistic data structure is prevented from being deleted while the metadata indicates that there is at least one active transaction.

### Claim 8 (depends on 7)

The method of claim 7, wherein performing the database transaction includes inserting at least one database key in the particular probabilistic data structure, and wherein registering the database transaction with the particular probabilistic data structure includes updating the metadata to increment the number of active transactions.

### Claim 9 (depends on 8)

The method of claim 8, wherein unregistering the database transaction from the particular probabilistic data structure includes updating the metadata to decrement the number of active transactions, and wherein the method further comprises:
after determining that unregistering the database transaction from a probabilistic data structure has caused the metadata to be updated to reflect that there are no active transaction, the database node deleting the particular probabilistic data structure.

### Claim 10

A non-transitory computer-readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:
receiving a request to perform a database transaction that involves writing a set of database records to an in-memory cache of the computer system and inserting a corresponding set of database keys into probabilistic data structures; and
performing the database transaction, including by:
for each probabilistic data structure in which at least one database key is inserted for the database transaction, registering the database transaction with that probabilistic data structure such that that probabilistic data structure is prevented from being deleted while the database transaction is registered;
making a first insertion cutoff determination that completing performance of the database transaction exceeds a specified amount of time; and
in response to the first insertion cutoff determination, unregistering the database transaction from each probabilistic data structure for which the database transaction was previously registered.

### Claim 11 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the operations further comprise:
making a second insertion cutoff determination that a specified number of probabilistic data structures have been written to as a part of performing the database transaction; and
in response to the second insertion cutoff determination, unregistering the database transaction from each probabilistic data structure for which the database transaction was previously registered.

### Claim 12 (depends on 10)

The non-transitory computer-readable medium of claim 10,
delaying insertion of database keys for the database transaction into probabilistic data structures until a pre-commit phase for the database transaction has been initiated.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the operations further comprise:
after initiating the pre-commit phase for the database transaction in relation to in-memory cache, inserting the set of database keys of the database transaction into a set of probabilistic data structures; and
in response to a request for a database record, sending a response to the request that includes the set of probabilistic data structures.

### Claim 14 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the operations further comprise:
storing, for a particular probabilistic data structure, metadata that specifies a number of active transactions that have inserted at least one database key into the particular probabilistic data structure, and wherein registering the database transaction with the particular probabilistic data structure includes updating the number of active transactions.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the operations further comprise:
before committing the database transaction in relation to in-memory cache, deleting the particular probabilistic data structure for which the database transaction had been previously registered.

### Claim 16

A method, comprising:
receiving, by a database node, a request to perform a database transaction that involves writing a set of database records to an in-memory cache of the database node and inserting a corresponding set of database keys into probabilistic data structures; and
performing, by the database node, the database transaction, including by:
for each probabilistic data structure in which at least one database key is inserted for the database transaction, registering the database transaction with that probabilistic data structure such that that probabilistic data structure is prevented from being deleted while the database transaction is registered;
determining that a specified number of probabilistic data structures have been written to as a part of performing the database transaction; and
in response to the determining, unregistering the database transaction from each probabilistic data structure for which the database transaction was previously registered.

### Claim 17 (depends on 16)

The method of claim 16, wherein registering the database transaction with a particular probabilistic data structure includes incrementing an active transaction count associated with the particular probabilistic data structure, and wherein the active transaction count prevents the particular probabilistic data structure from being deleted while the active transaction count satisfies a particular condition.

### Claim 18 (depends on 16)

The method of claim 16, further comprising:
halting, by the database node, database key insertions for the database transaction into the probabilistic data structures until a pre-commit phase for the database transaction has been initiated.

### Claim 19 (depends on 18)

The method of claim 18, further comprising:
after initiating the pre-commit phase for the database transaction, the database node resuming insertion of the set of database keys into a set of probabilistic data structures.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
prior to flushing the set of database records from the in-memory cache to a persistent storage that is shared between the database node and another database node, the database node sending the set of probabilistic data structures to the other database node.
after flushing the set of database records from the in-memory cache to the persistent storage, the database node deleting the set of probabilistic data structures.
