Synchronizable transactional database method and system
First Claim
Patent Images
1. A method of minimizing network traffic during the process of synchronizing a local transaction database with a remote transaction database, comprising:
- receiving from the remote transaction database a single summary hash computed for database records lying in an interval in the remote transaction database;
comparing the single summary hash to a local single summary hash computed for database records lying in a same interval in the local transaction database; and
when the single summary hash does not match the local summary hash, partitioning the interval into at least a first and a second sub-interval and requesting from the remote transaction database a first sub-interval summary hash and a second sub-interval summary hash, the first sub-interval summary hash computed for database records lying in the first sub-interval in the remote transaction database and the second sub-interval summary hash computed for database records lying in the second sub-interval in the remote transaction database,whereby the database can avoid updating database records in a sub-interval at the occurrence of a match between a local sub-interval summary hash and a sub-interval summary hash received from the remote transaction database.
3 Assignments
0 Petitions
Accused Products
Abstract
A database system that can synchronize all or a part of its contents over a limited bandwidth link is described. The lowest layer of the system, the bedrock layer, implements a transactional block store. On top of this is a B+-tree that can efficiently compute a digest (hash) of the records within any range of key values in O(log n) time. The top level is a communication protocol that directs the synchronization process such that minimization of bits communicated, rounds of communication, and local computation are simultaneously addressed.
-
Citations
13 Claims
-
1. A method of minimizing network traffic during the process of synchronizing a local transaction database with a remote transaction database, comprising:
-
receiving from the remote transaction database a single summary hash computed for database records lying in an interval in the remote transaction database; comparing the single summary hash to a local single summary hash computed for database records lying in a same interval in the local transaction database; and when the single summary hash does not match the local summary hash, partitioning the interval into at least a first and a second sub-interval and requesting from the remote transaction database a first sub-interval summary hash and a second sub-interval summary hash, the first sub-interval summary hash computed for database records lying in the first sub-interval in the remote transaction database and the second sub-interval summary hash computed for database records lying in the second sub-interval in the remote transaction database, whereby the database can avoid updating database records in a sub-interval at the occurrence of a match between a local sub-interval summary hash and a sub-interval summary hash received from the remote transaction database. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer implemented synchronizable transactional database comprising:
-
a database; an interval hash value computing module coupled to the database and configured to compute a summary hash of a plurality of hash values, each hash value associated with a database record lying in an interval of the database; and a synchronization module coupled to the database and to the interval hash value computing module, the synchronization module configured to identify database records that need synchronization by comparing a summary hash from the interval hash value computing module computed for database records lying in an interval of the database with a remote summary hash received from a remote transaction database, the synchronization module further configured to partition an interval into at least a first and a second subinterval when a summary hash for the interval in the database does not match a remote summary hash so as to seek remote summary hashes for the first and second sub-intervals from the remote transaction database, whereby the database can avoid updating database records in a sub-interval at the occurrence of a match between a local sub-interval summary hash and a sub-interval summary hash received from the remote transaction database. - View Dependent Claims (9, 10, 11, 12, 13)
-
Specification