Database Syncing

Patent metadata

Field	Value
Publication number	US-2020372000-A1
Application number	US-202016993210-A
Country	US
Kind code	A1
Filing date	Aug 13, 2020
Priority date	Dec 14, 2017
Publication date	Nov 26, 2020
Grant date	—

Abstract

A method for database syncing is provided. The method includes receiving database change indicators indicating changes to a database. For each database change indicator, the method also includes determining whether the respective change to the database corresponds to a single change to a single version of the database, one of multiple changes to a common version of the database, or one of multiple changes to different versions of the database. The method further includes generating a change log compaction data structure comprising entries. Each entry includes an exact entry defining a corresponding single change to a corresponding single version of the database, a range entry defining corresponding multiple changes to a corresponding common version of the database, or an interval entry defining corresponding multiple changes to corresponding different versions of the database.

First claim

What is claimed is:

1 . A method comprising:
receiving, at data processing hardware, database change indicators indicating changes to a distributed database, each change indicator indicating an addition, a deletion, or a modification to the distributed database; generating, by the data processing hardware, a change log structure comprising entries, each entry defining one or more charges to the distributed database; receiving, at the data processing hardware, a synchronization query from a client device associated with the distributed database, the synchronization query requesting synchronization between the distributed database and another database; and transmitting, by the data processing hardware, a query response to the other database based on the change log structure, the query response configured to cause the other database to synchronize with the distributed database.

2 . The method of claim 1 , wherein the change log structure comprises an index space and a data space, and wherein any negative space of the index space comprises known space having no changes to the distributed database.

3 . The method of claim 1 , further comprising, for each database change indicator, determining, by the data processing hardware, whether the respective change to the distributed database corresponds to:
a single change to a single version of the distributed database; one of multiple changes to a common version of the distributed database; or one of multiple changes to different versions of the distributed database.

4 . The method of claim 3 , wherein each entry of the change log structure comprises:
an exact entry defining a corresponding single change to a corresponding single version of the distributed database; a range entry defining corresponding multiple changes to a corresponding common version of the distributed database; or an interval entry defining corresponding multiple changes to corresponding different versions of the distributed database.

5 . The method of claim 4 , wherein the different versions of the distributed database corresponding to the interval entry span a continuous interval of time.

6 . The method of claim 1 , wherein the database change indicators comprise a commit log entry.

7 . The method of claim 1 , wherein the query response comprises a bloom filter.

8 . The method of claim 1 , wherein the synchronization query indicates a set of data ranges and an interval of time.

9 . The method of claim 8 , further comprising, when at least one entry of the change log structure satisfies the synchronization query, returning, by the data processing hardware, the corresponding at least one entry to the client device.

10 . The method of claim 9 , wherein the query response comprises at least one of
a database change indicator, a database change log entry, or a change corresponding to the at least one entry.

11 . A system comprising
data processing hardware; and memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving database change indicators indicating changes to a distributed database, each change indicator indicating an addition, a deletion, or a modification to the distributed database;
generating a change log structure comprising entries, each entry defining one or more changes to the distributed database;
receiving a synchronization query from a client device associated with the distributed database, the synchronization query requesting synchronization between the distributed database and another database; and
transmitting a query response to the other database based on the change log structure, the query response configured to cause the other database to synchronize with the distributed database.

12 . The system of claim 11 , wherein the change log structure comprises an index space and a data space, and wherein any negative space of the index space comprises known space having no changes to the distributed database.

13 . The system of claim 11 , wherein the operations further comprise, for each database change indicator, determining whether the respective change to the distributed database corresponds to:
a single change to a single version of the distributed database; one of multiple changes to a common version of the distributed database; or one of multiple changes to different versions of the distributed database.

14 . The system of claim 13 , wherein each entry of the change log structure comprises:
an exact entry defining a corresponding single change to a corresponding single version of the distributed database; a range entry defining corresponding multiple changes to a corresponding common version of the distributed database; or an interval entry defining corresponding multiple changes to corresponding different versions of the distributed database.

15 . The system of claim 14 , wherein the different versions of the distributed database corresponding to the interval entry span a continuous interval of time.

16 . The system of claim 11 , wherein the database change indicators comprise a commit log entry.

17 . The system of claim 11 , wherein the query response comprises a bloom filter.

18 . The system of claim 11 , wherein the synchronization query indicates a set of data ranges and an interval of time.

19 . The system of claim 18 , further comprising, when at least one entry of the change log structure satisfies the synchronization query, returning the corresponding at least one entry to the client device.

20 . The system of claim 19 , wherein the query response comprises at least one of
a database change indicator, a database change log entry, or a change corresponding to the at least one entry.

Assignees

• Google Llc

Inventors

• Fuller Alfred

Classifications

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title

• G06F16/40

  of multimedia data, e.g. slideshows comprising image and additional audio data (retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70) · CPC title

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/1734

  Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs · CPC title

• G06F16/2228

  Indexing structures · CPC title