# US 12,602,399 B2 · Database synchronization using resizable invertible bloom filters with database snapshots > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,399 B2 - Document ID: US12602399B2 - Status: Granted - Kind: B2 - Application number: 18/980,968 - Filed: 2024-12-13 - Published: 2025-04-03 - Granted: 2026-04-14 - Earliest claimed: 2021-11-18 - Assignees: Fivetran Inc. - Applicants: Fivetran Inc. - Inventors: Jason Nochlin - Web page: https://patentgrep.com/patent/US12602399B2 ## CPC - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - G06F 16/2255: {Hash tables} - G06F 16/2365: {Ensuring data consistency and integrity} - 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 using a resizable invertible bloom filter. The system may include a resizable invertible bloom filter module that constructs and maintains invertible bloom filters that are resizable based on a number of differences between different snapshots. The resizable invertible bloom filter module may maintain a list of possible sizes for a resizable invertible bloom filter. The resizable invertible bloom filter module may determine and maintain a list of applicable partition sizes, each partition size being a product of a divisor and a resizing factor. If the number of differences exceeds the number of expected differences and results in failure in decoding, the system may retry a larger size in a set of predetermined sizes. The system may continue to try larger sizes until a minimal size required for successful decoding is found. ## Claims ### Claim 1 A method comprising: generating a first resizable invertible bloom filter of a source data table based on information of the source data table at a first point in time, the first resizable invertible bloom filter having a first size that is determined based on an estimated number of changes in the source data table between the first point in time and a second point in time; generating a second resizable invertible bloom filter for the source data table based on information of the source data table at the second point in time, the second resizable invertible bloom filter also having the first size; determining an actual number of changes in the source data table between the first point in time and the second point in time; responsive to the actual number of changes being smaller than the estimated number of changes, determining a second size for the first and the second resizable invertible bloom filters, the second size being smaller than the first size; updating the first resizable invertible bloom filter and the second resizable invertible bloom filter to have the second size; identifying changes in the source data table that occurred between the first point in time and the second point in time based on the updated first resizable invertible bloom filter and the updated second resizable invertible bloom filter; and sending instructions to a destination data table, the instructions comprising information to perform an operation that synchronizes the destination data table with the source data table based on the identified changes. ### Claim 2 (depends on 1) The method of claim 1, wherein the first and second sizes are determined based on mathematical constraints. ### Claim 3 (depends on 1) The method of claim 1, wherein the first and second sizes are determined based on a set of prime divisors and a set of resizing factors, and wherein each size is a product of a prime divisor of the set of prime divisors and a resizing factor of the set of resizing factors. ### Claim 4 (depends on 3) The method of claim 3, wherein each resizing factor of the set of resizing factors is a prime number. ### Claim 5 (depends on 4) The method of claim 4, wherein each prime divisor of the set of prime divisors is multiplied by each resizing factor of the set of resizing factors in descending order. ### Claim 6 (depends on 3) The method of claim 3, wherein each prime divisor in the set of prime divisors has a same value, and wherein each prime divisor of the set of prime divisors is multiplied by each resizing factor of the set of resizing factors. ### Claim 7 (depends on 1) The method of claim 1, wherein identifying the changes in the source data table further comprises: generating a third resizable invertible bloom filter by subtracting the updated second resizable invertible bloom filter from the updated first resizable invertible bloom filter, the third resizable invertible bloom filter comprising information associated with a change in the source data table that occurred between the first point in time and the second point in time. ### Claim 8 (depends on 7) The method of claim 7, further comprising identifying the changes by decoding the third invertible bloom filter. ### Claim 9 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: generate a first resizable invertible bloom filter of a source data table based on information of the source data table at a first point in time, the first resizable invertible bloom filter having a first size that is determined based on an estimated number of changes in the source data table between the first point in time and a second point in time; generate a second resizable invertible bloom filter for the source data table based on information of the source data table at the second point in time, the second resizable invertible bloom filter also having the first size; determine an actual number of changes in the source data table between the first point in time and the second point in time; responsive to the actual number of changes being smaller than the estimated number of changes, determine a second size for the first and the second resizable invertible bloom filters, the second size being smaller than the first size; update the first resizable invertible bloom filter and the second resizable invertible bloom filter to have the second size; identify changes in the source data table that occurred between the first point in time and the second point in time based on the updated first resizable invertible bloom filter and the updated second resizable invertible bloom filter; and send instructions to a destination data table, the instructions comprising information to perform an operation that synchronizes the destination data table with the source data table based on the identified changes. ### Claim 10 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein the first and second sizes are determined based on mathematical constraints. ### Claim 11 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein the first and second sizes are determined based on a set of prime divisors and a set of resizing factors, and wherein each size is a product of a prime divisor of the set of prime divisors and a resizing factor of the set of resizing factors. ### Claim 12 (depends on 11) The non-transitory computer-readable storage medium of claim 11, wherein each resizing factor of the set of resizing factors is a prime number. ### Claim 13 (depends on 12) The non-transitory computer-readable storage medium of claim 12, wherein each prime divisor of the set of prime divisors is multiplied by each resizing factor of the set of resizing factors in descending order. ### Claim 14 (depends on 11) The non-transitory computer-readable storage medium of claim 11, wherein each prime divisor in the set of prime divisors has a same value, and wherein each prime divisor of the set of prime divisors is multiplied by each resizing factor of the set of resizing factors. ### Claim 15 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein identifying the changes in the source data table further comprises: generating a third resizable invertible bloom filter by subtracting the updated second resizable invertible bloom filter from the updated first resizable invertible bloom filter, the third resizable invertible bloom filter comprising information associated with a change in the source data table that occurred between the first point in time and the second point in time. ### Claim 16 (depends on 15) The non-transitory computer-readable storage medium of claim 15, wherein the instructions comprising instructions to identify the changes by decoding the third invertible bloom filter. ### Claim 17 A computing system comprising: a processor; and a non-transitory computer-readable storage medium storing instructions, the instructions when executed by the processor cause the processor to perform steps including: generating a first resizable invertible bloom filter of a source data table based on information of the source data table at a first point in time, the first resizable invertible bloom filter having a first size that is determined based on an estimated number of changes in the source data table between the first point in time and a second point in time; generating a second resizable invertible bloom filter for the source data table based on information of the source data table at the second point in time, the second resizable invertible bloom filter also having the first size; determining an actual number of changes in the source data table between the first point in time and the second point in time; responsive to the actual number of changes being smaller than the estimated number of changes, determining a second size for the first and the second resizable invertible bloom filters, the second size being smaller than the first size; updating the first resizable invertible bloom filter and the second resizable invertible bloom filter to have the second size; identifying changes in the source data table that occurred between the first point in time and the second point in time based on the updated first resizable invertible bloom filter and the updated second resizable invertible bloom filter; and sending instructions to a destination data table, the instructions comprising information to perform an operation that synchronizes the destination data table with the source data table based on the identified changes. ### Claim 18 (depends on 17) The system of claim 17, wherein the first and second sizes are determined based on a set of prime divisors and a set of resizing factors, and wherein each size is a product of a prime divisor of the set of prime divisors and a resizing factor of the set of resizing factors. ### Claim 19 (depends on 17) The system of claim 17, wherein identifying the changes in the source data table further comprises: generating a third resizable invertible bloom filter by subtracting the updated second resizable invertible bloom filter from the updated first resizable invertible bloom filter, the third resizable invertible bloom filter comprising information associated with a change in the source data table that occurred between the first point in time and the second point in time. ### Claim 20 (depends on 19) The system of claim 19, wherein the steps further include identifying the changes by decoding the third invertible bloom filter.