-
公开(公告)号：US20240037085A1
公开(公告)日：2024-02-01
申请号：US18376255
申请日：2023-10-03
Applicant: Google LLC
Inventor： Alexander Khesin , Alexander Lloyd , Sebastian Kanthak
IPC: G06F16/22 , G06F16/27 , G06F16/2458
CPC classification number: G06F16/2282 , G06F16/27 , G06F16/2477
Abstract: The technology relates to cosharding tables within a distributed storage system. A data table including one or more rows may be received. Each row in the data table may include an identifier key and pics of data. Each piece of data in the data table may be indexed into individual rows of an index table, wherein each row in the index table includes data associated with the identifier key of the data table from which the piece of data in the respective row was indexed. The index table may be sharded into splits, wherein the sharding includes assigning each row of the index table into one of the splits based on the identifier key of the data table from which the piece of data in the respective row was indexed. The splits may be more stored into two or more or more portions of the distributed storage system.
-
公开(公告)号：US10558625B2
公开(公告)日：2020-02-11
申请号：US15665273
申请日：2017-07-31
Applicant: Google LLC
Inventor： Wilson Chang-Yi Hsieh , Alexander Lloyd , Eric Hugh Veach
Abstract: The various embodiments described herein include methods, devices, and systems for reading and writing data from a database table. In one aspect, a method of reading and writing data from a database table, includes: (1) initiating a write transaction to write data to a first non-key column of a row of the database table, the database table having a plurality of rows, each row comprising a primary key and a plurality of non-key columns; (2) locking the first non-key column; and (3) in accordance with a determination that the second non-key column is not locked, initiating a read transaction to read data from the second non-key column, where initiation of the read transaction occurs prior to completion of the write transaction.
-
公开(公告)号：US20250086200A1
公开(公告)日：2025-03-13
申请号：US18800428
申请日：2024-08-12
Applicant: Google LLC
Inventor： Wilson Cheng-Yi Hsieh , Alexander Lloyd
IPC: G06F16/27 , G06F16/23 , H04L67/1095
Abstract: Paxos transactions are pipelined in a distributed database formed by a plurality of replica servers. A leader server is selected by consensus of the replicas, and receives a lock on leadership for an epoch. The leader gets Paxos log numbers for the current epoch, which are greater than the numbers allocated in previous epochs. The leader receives database write requests, and assigns a Paxos number to each request. The leader constructs a proposed transaction for each request, which includes the assigned Paxos number and incorporates the request. The leader transmits the proposed transactions to the replicas. Two or more write requests that access distinct objects in the database can proceed simultaneously. The leader commits a proposed transaction to the database after receiving a plurality of confirmations for the proposed transaction from the replicas. After all the Paxos numbers have been assigned, inter-epoch tasks are performed before beginning a subsequent epoch.
-
公开(公告)号：US11953938B1
公开(公告)日：2024-04-09
申请号：US17740688
申请日：2022-05-10
Applicant: Google LLC
Inventor： Peter Hochschild , Alexander Lloyd , Wilson Cheng-Yi Hsieh , Robert Edman Felderman , Michael James Boyer Epstein
CPC classification number: G06F1/12 , G01S19/01 , H04J3/0661 , H04J3/0667 , H04L7/0008 , H04L7/0012 , H04L7/0016 , H04L43/106 , H04L67/10 , G06F11/1675
Abstract: The present technology proposes techniques for generating globally coherent timestamps. This technology may allow distributed systems to causally order transactions without incurring various types of communication delays inherent in explicit synchronization. By globally deploying a number of time masters that are based on various types of time references, the time masters may serve as primary time references. Through an interactive interface, the techniques may track, calculate and record data relative to each time master thus providing the distributed systems with causal timestamps.
-
公开(公告)号：US20220012264A1
公开(公告)日：2022-01-13
申请号：US17485905
申请日：2021-09-27
Applicant: Google LLC
Inventor： Wilson Cheng-Yi Hsieh , Alexander Lloyd
Abstract: Paxos transactions are pipelined in a distributed database formed by a plurality of replica servers. A leader server is selected by consensus of the replicas, and receives a lock on leadership for an epoch. The leader gets Paxos log numbers for the current epoch, which are greater than the numbers allocated in previous epochs. The leader receives database write requests, and assigns a Paxos number to each request. The leader constructs a proposed transaction for each request, which includes the assigned Paxos number and incorporates the request. The leader transmits the proposed transactions to the replicas. Two or more write requests that access distinct objects in the database can proceed simultaneously. The leader commits a proposed transaction to the database after receiving a plurality of confirmations for the proposed transaction from the replicas. After all the Paxos numbers have been assigned, inter-epoch tasks are performed before beginning a subsequent epoch.
-
Patent Agency Ranking
公开(公告)号：US10775837B1
公开(公告)日：2020-09-15
申请号：US15877845
申请日：2018-01-23
Applicant: Google LLC
Inventor： Peter Hochschild , Alexander Lloyd , Wilson Cheng-Yi Hsieh , Robert Edman Felderman , Michael James Boyer Epstein
Abstract: The present technology proposes techniques for generating globally coherent timestamps. This technology may allow distributed systems to causally order transactions without incurring various types of communication delays inherent in explicit synchronization. By globally deploying a number of time masters that are based on various types of time references, the time masters may serve as primary time references. Through an interactive interface, the techniques may track, calculate and record data relative to each time master thus providing the distributed systems with causal timestamps.
-
公开(公告)号：US10042881B1
公开(公告)日：2018-08-07
申请号：US15358428
申请日：2016-11-22
Applicant: Google LLC
Inventor： Wilson Cheng-Yi Hsieh , Alexander Lloyd , Peter Hochschild , Michael James Boyer Epstein , Sean Quinlan
Abstract: The present technology proposes techniques for ensuring globally consistent transactions. This technology may allow distributed systems to ensure the causal order of read and write transactions across different partitions of a distributed database. By assigning causally generated timestamps to the transactions based on one or more globally coherent time services, the timestamps can be used to preserve and represent the causal order of the transactions in the distributed system. In this regard, certain transactions may wait for a period of time after choosing a timestamp in order to delay the start of any second transaction that might depend on it. The wait may ensure that the effects of the first transaction are not made visible until its timestamp is guaranteed to be in the past. This may ensure that a consistent snapshot of the distributed database can be determined for any past timestamp.
-
公开(公告)号：US11556375B2
公开(公告)日：2023-01-17
申请号：US16895132
申请日：2020-06-08
Applicant: Google LLC
Inventor： Brian Frank Cooper , Alexander Lloyd , Sebastian Kanthak , Andrew Fikes , Christopher Taylor
Abstract: In a distributed system where a client's call to commit a transaction occurs outside the transaction's lock-hold interval, computation of timestamp information for the transaction is moved to a client library, while ensuring that no conflicting reads or writes are performed between a time of the computation and acquiring all locks for the transaction. The transaction is committed in phases, with each phase being initiated by the client library. Timestamp information is added to the locks to ensure that timestamps are generated during lock-hold intervals. An increased number of network messages is thereby overlapped with a commit wait period in which a write in a distributed database is delayed in time to ensure concurrency in the database.
-
公开(公告)号：US20220398227A1
公开(公告)日：2022-12-15
申请号：US17824348
申请日：2022-05-25
Applicant: Google LLC
Inventor： Wilson Cheng-Yi Hsieh , Alexander Lloyd , Eric Hugh Veach
Abstract: The various embodiments described herein include methods, devices, and systems for reading and writing data from a database table. In one aspect, a method includes: (1) initiating a read transaction to read from a first non-key column of a row in the database table, the database table having a plurality of rows, each row comprising a primary key and a plurality of non-key columns, the initiating including: (a) determining that a write transaction holds a lock on a second non-key column of the row in the database table, and (b) determining that no lock is held on the first non-key column; and (2) in response, concurrently reading data from the first non-key column and writing a new column value to the second non-key column; where each non-key column includes a last-write timestamp that indicates when the last write occurred for the respective non-key column.
-
公开(公告)号：US11442925B1
公开(公告)日：2022-09-13
申请号：US16023326
申请日：2018-06-29
Applicant: Google LLC
Inventor： Wilson Cheng-Yi Hsieh , Alexander Lloyd , Peter Hochschild , Michael James Boyer Epstein , Sean Quinlan
IPC: G06F16/23 , G06F16/14 , G06F9/46 , G06F16/2458
Abstract: The present technology proposes techniques for ensuring globally consistent transactions. This technology may allow distributed systems to ensure the causal order of read and write transactions across different partitions of a distributed database. By assigning causally generated timestamps to the transactions based on one or more globally coherent time services, the timestamps can be used to preserve and represent the causal order of the transactions in the distributed system. In this regard, certain transactions may wait for a period of time after choosing a timestamp in order to delay the start of any second transaction that might depend on it. The wait may ensure that the effects of the first transaction are not made visible until its timestamp is guaranteed to be in the past. This may ensure that a consistent snapshot of the distributed database can be determined for any past timestamp.
-
-
-
-
-
-
-
-
-
Search Results
30
records
(took 0.014 seconds)
