# US 2025/0165498 A1 · Identifying Changes Between Source and Destination Databases using Snapshots of Source Database and Invertible Bloom Filters

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

- Number: US 2025/0165498 A1
- Document ID: US20250165498A1
- Status: Published application
- Kind: A1
- Application number: 19/030,065
- Filed: 2025-01-17
- Published: 2025-05-22
- Earliest claimed: 2020-11-19
- Assignees: Fivetran Inc.
- Applicants: Fivetran Inc.
- Inventors: Jason Nochlin
- Web page: https://patentgrep.com/patent/US20250165498A1

## CPC

- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 11/1446: Point-in-time backing up or restoration of persistent data
- G06F 16/2255: {Hash tables}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/24534: {Query rewriting; Transformation}
- G06F 16/252: {between a Database Management System and a front-end application}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A centralized database management system performs data synchronization with lower bandwidth consumption and higher efficiency. The system manages data synchronization and data reconciliation across multiple databases managed by multiple DBMS across different client servers. The system generates and sends instructions that encode each data table into an invertible bloom filter and identifies differences between the two databases by performing a subtraction operation on the two invertible bloom filters. The system may generate a third invertible bloom filter comprising information associated with differences between the two data tables. The system may send instructions to the source and the destination databases, where a first and a second invertible bloom filters are encoded for the source and the destination databases, respectively. The system may decode the third invertible bloom filter, identify the different elements, and generate instructions to the source and/or the destination database.

## Claims

### Claim 1

A method comprising:
retrieving a source data table and a destination data table;
transforming each row of data in the source data table into a source row representation;
transforming each row of data in the destination data table into a destination row representation;
generating a first invertible bloom filter for the source data table using the respective source row representations and a second invertible bloom filter for the destination data table using the respective destination row representations, wherein generating the first invertible bloom filter and the second invertible bloom filter comprises:
determining a size for both the first invertible bloom filter and the second invertible bloom filter based on an estimated number of changes to the source data table, wherein a size of an invertible bloom filter is associated with a space occupied in a computer memory,
determining a difference between the estimated number of changes and an actual number of changes to the source data table, and
adjusting the size responsive to the determined difference meeting a threshold;
generating a third invertible bloom filter by subtracting the second invertible bloom filter from the first invertible bloom filter;
identifying a difference between a row of data in the source data table and a row of data in the destination data table by decoding the third invertible bloom filter; and
transmitting information associated with the identified difference to synchronize the destination data table with the source data table by updating the row of data in the destination data table based on the row of data in the source data table.

### Claim 2 (depends on 1)

The method of claim 1, wherein determining the size for both the first invertible bloom filter and the second invertible bloom filter further comprises:
iteratively adjusting the size responsive to additional changes to the source data table.

### Claim 3 (depends on 1)

The method of claim 1, wherein adjusting the size responsive to the determined difference meeting the threshold comprises: decreasing the size responsive to the determined difference being smaller than the threshold.

### Claim 4 (depends on 1)

The method of claim 1, further comprising responsive to the first and the second invertible bloom filters including a number of empty cells, compressing the first invertible bloom filter into a compressed invertible bloom filter by reducing the size.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating the first invertible bloom filter and the second invertible bloom filter further comprises:
generating a backup invertible bloom filter for the first invertible bloom filter; and
activating the backup invertible bloom filter responsive to the determined difference meeting the threshold.

### Claim 6 (depends on 1)

The method of claim 1, wherein the identified difference between a row of data in the source data table and a row of data in the destination data table is identified without accessing data entries of the source data table.

### Claim 7 (depends on 1)

The method of claim 1, wherein the size for both the first invertible bloom filter and the second invertible bloom filter is determined as a constant that is larger than a threshold value.

### Claim 8

A non-transitory computer-readable storage medium storing executable computer instructions that, when executed by one or more processors, cause the one or more processors to perform operations, the instructions comprising instructions to:
retrieve a source data table and a destination data table;
transform each row of data in the source data table into a source row representation;
transform each row of data in the destination data table into a destination row representation;
generate a first invertible bloom filter for the source data table using the respective source row representations and a second invertible bloom filter for the destination data table using the respective destination row representations, wherein generating the first invertible bloom filter and the second invertible bloom filter comprises:
determining a size for both the first invertible bloom filter and the second invertible bloom filter based on an estimated number of changes to the source data table, wherein a size of an invertible bloom filter is associated with a space occupied in a computer memory,
determining a difference between the estimated number of changes and an actual number of changes to the source data table, and
adjusting the size responsive to the determined difference meeting a threshold;
generate a third invertible bloom filter by subtracting the second invertible bloom filter from the first invertible bloom filter;
identify a difference between a row of data in the source data table and a row of data in the destination data table by decoding the third invertible bloom filter; and
transmit information associated with the identified difference to synchronize the destination data table with the source data table by updating the row of data in the destination data table based on the row of data in the source data table.

### Claim 9 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the instructions to determine the size for both the first invertible bloom filter and the second invertible bloom filter comprise instructions to:
iteratively adjust the size responsive to additional changes to the source data table.

### Claim 10 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the instructions to adjust the size responsive to the determined difference meeting the threshold comprise instructions to: decrease the size responsive to the determined difference being smaller than the threshold.

### Claim 11 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the instructions further comprise instructions to responsive to the first and the second invertible bloom filters including a number of empty cells, compress the first invertible bloom filter into a compressed invertible bloom filter by reducing the size.

### Claim 12 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the instructions to generate the first invertible bloom filter and the second invertible bloom filter comprise instructions to:
generate a backup invertible bloom filter for the first invertible bloom filter; and
activate the backup invertible bloom filter responsive to the determined difference meeting the threshold.

### Claim 13 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the identified difference between a row of data in the source data table and a row of data in the destination data table is identified without accessing data entries of the source data table.

### Claim 14 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the size for both the first invertible bloom filter and the second invertible bloom filter is determined as a constant that is larger than a threshold value.

### Claim 15

A computing system comprising:
one or more processors; and
a non-transitory computer-readable storage medium storing instructions for database synchronization, the instructions when executed by the processors cause the processors to perform operations including:
retrieving a source data table and a destination data table;
transforming each row of data in the source data table into a source row representation;
transforming each row of data in the destination data table into a destination row representation;
generating a first invertible bloom filter for the source data table using the respective source row representations and a second invertible bloom filter for the destination data table using the respective destination row representations, wherein generating the first invertible bloom filter and the second invertible bloom filter comprises:
determining a size for both the first invertible bloom filter and the second invertible bloom filter based on an estimated number of changes to the source data table, wherein a size of an invertible bloom filter is associated with a space occupied in a computer memory,
determining a difference between the estimated number of changes and an actual number of changes to the source data table, and
adjusting the size responsive to the determined difference meeting a threshold;
generating a third invertible bloom filter by subtracting the second invertible bloom filter from the first invertible bloom filter;
identifying a difference between a row of data in the source data table and a row of data in the destination data table by decoding the third invertible bloom filter; and
transmitting information associated with the identified difference to synchronize the destination data table with the source data table by updating the row of data in the destination data table based on the row of data in the source data table.

### Claim 16 (depends on 15)

The computing system of claim 15, wherein determining the size for both the first invertible bloom filter and the second invertible bloom filter further comprises:
iteratively adjusting the size responsive to additional changes to the source data table.

### Claim 17 (depends on 15)

The computing system of claim 15, wherein adjusting the size responsive to the determined difference meeting the threshold comprises: decreasing the size responsive to the determined difference being smaller than the threshold.

### Claim 18 (depends on 15)

The computing system of claim 15, wherein the operations further comprise:
responsive to the first and the second invertible bloom filter including a number of empty cells, compressing the first invertible bloom filter into a compressed invertible bloom filter by reducing the size.

### Claim 19 (depends on 15)

The computing system of claim 15, wherein generating the first invertible bloom filter and the second invertible bloom filter further comprises:
generating a backup invertible bloom filter for the first invertible bloom filter; and
activating the backup invertible bloom filter responsive to the determined difference meeting the threshold.

### Claim 20 (depends on 15)

The computing system of claim 15, wherein the size for both the first invertible bloom filter and the second invertible bloom filter is determined as a constant that is larger than a threshold value.
