# US 12,007,956 B1 · Time reservations for ensuring consistent reads in a distributed database without logging > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,007,956 B1 - Document ID: US12007956B1 - Status: Granted - Kind: B1 - Application number: 17/965,212 - Filed: 2022-10-13 - Granted: 2024-06-11 - Earliest claimed: 2012-07-25 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Wilson Cheng-Yi Hsieh; Eric Hugh Veach; Michael James Boyer Epstein; Alexander Lloyd - Web page: https://patentgrep.com/patent/US12007956B1 ## CPC - G06F 16/20: of structured data, e.g. relational data - G06F 16/2322: {using timestamps} - G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details} - G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor - G06F 16/273: {Asynchronous replication or reconciliation} - G06F 16/951: Indexing; Web crawling techniques - H04L 69/04: Protocols for data compression, e.g. ROHC - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract The subject matter described herein provides techniques to ensure that queries of a distributed database observe a consistent read of the database without locking or logging. In this regard, next-write timestamps uniquely identify a set of write transactions whose updates can be observed by reads. By publishing the next-write timestamps from within an extendable time lease and tracking a “safe timestamp,” the database queries can be executed without logging read operations or blocking future write transactions, and clients issuing the queries at the “safe timestamp” observe a consistent view of the database as it exists on or before that timestamp. Aspects of this disclosure also provide for extensions, done cheaply and without the need for logging, to the range of timestamps at which read transactions can be executed. ## Claims ### Claim 1 A method for servicing transactions in a database, the method comprising: reserving, by one or more processors, a time lease; receiving, by the one or more processors, a transaction; maintaining, by the one or more processors, a first timestamp indicating a next time data is allowed to be committed to the database, the first timestamp being selected from within the time lease; and executing, by the one or more processors, the transaction at a second timestamp from within the time lease based on the first timestamp. ### Claim 2 (depends on 1) The method of claim 1, further comprising determining, by the one or more processors, the transaction is a write transaction. ### Claim 3 (depends on 2) The method of claim 2, further comprising: selecting, by the one or more processors, the second timestamp from within the time lease, wherein the second timestamp is greater than the first timestamp; and associating, by the one or more processors, the second timestamp with the write transaction. ### Claim 4 (depends on 2) The method of claim 2, further comprising obtaining, by the one or more processors, a current-time interval from within the time lease. ### Claim 5 (depends on 1) The method of claim 1, further comprising determining, by the one or more processors, the transaction is a read transaction. ### Claim 6 (depends on 5) The method of claim 5, further comprising: determining, by the one or more processors, the second timestamp is less than the first timestamp; and waiting, by the one or more processors, a period of time for a safe timestamp to meet or exceed the second timestamp; wherein the read transaction is executed after the period of time. ### Claim 7 (depends on 5) The method of claim 5, further comprising: determining, by the one or more processors, the second timestamp is greater than or equal to the first timestamp; selecting, by the one or more processors, a next-write timestamp from within the time lease; publishing, by the one or more processors, the next-write timestamp; and waiting, by the one or more processors, a period of time for a safe timestamp to meet or exceed the second timestamp; wherein the read transaction is executed after the period of time. ### Claim 8 (depends on 1) The method of claim 1, wherein the first timestamp is a next-write timestamp and the second timestamp is one of a commit timestamp or a read timestamp. ### Claim 9 A system for servicing transactions, comprising: a database; and one or more processors in communication with the database, the one or more processors being configured to: reserve a time lease; receive a transaction; maintain a first timestamp indicating a next time data is allowed to be committed to the database, the first timestamp being selected from within the time lease; and execute the transaction at a second timestamp from within the time lease based on the first timestamp. ### Claim 10 (depends on 9) The system of claim 9, wherein the processors are further configured to determine the transaction is a write transaction. ### Claim 11 (depends on 10) The system of claim 10, wherein the processors are further configured to: select the second timestamp from within the time lease, wherein the second timestamp is greater than the first timestamp; and associate the second timestamp with the write transaction. ### Claim 12 (depends on 10) The system of claim 10, wherein the processors are further configured to obtain a current-time interval from within the time lease. ### Claim 13 (depends on 9) The system of claim 9, wherein the processors are further configured to determine the transaction is a read transaction. ### Claim 14 (depends on 13) The system of claim 13, wherein the processors are further configured to: determine the second timestamp is less than the first timestamp; and wait a period of time for a safe timestamp to meet or exceed the second timestamp, wherein the read transaction is executed after the period of time. ### Claim 15 (depends on 13) The system of claim 13, wherein the processors are further configured to: determine the second timestamp is greater than or equal to the first timestamp; select a next-write timestamp from within the time lease; publish the next-write timestamp; and wait a period of time for a safe timestamp to meet or exceed the second timestamp, wherein the read transaction is executed after the period of time. ### Claim 16 (depends on 9) The system of claim 9, wherein the first timestamp is a next-write timestamp and the second timestamp is one of a commit timestamp or a read timestamp. ### Claim 17 A non-transitory computer readable medium for storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations for servicing transactions in a database, the operations comprising: reserving a time lease; receiving a transaction; maintaining a first timestamp indicating a next time data is allowed to be committed to the database, the first timestamp being selected from within the time lease; and executing the transaction at a second timestamp from within the time lease based on the first timestamp. ### Claim 18 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the operations further comprise: determining the transaction is a write transaction; selecting the second timestamp from within the time lease, wherein the second timestamp is greater than the first timestamp; and associating the second timestamp with the write transaction. ### Claim 19 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the operations further comprise: determining the transaction is a read transaction; determining the second timestamp is less than the first timestamp; and waiting a period of time for a safe timestamp to meet or exceed the second timestamp, wherein the read transaction is executed after the period of time. ### Claim 20 (depends on 17) The non-transitory computer readable medium of claim 17, wherein the operations further comprise: determining the transaction is a read transaction; determining the second timestamp is greater than or equal to the first timestamp; selecting a next-write timestamp from within the time lease; publishing the next-write timestamp; and waiting a period of time for a safe timestamp to meet or exceed the second timestamp, wherein the read transaction is executed after the period of time.