公开(公告)号：US20220138071A1

公开(公告)日：2022-05-05

申请号：US17085576

申请日：2020-10-30

Applicant: Google LLC

Inventor： Pavan Edara ,  Reuven Lax ,  Yi Yang ,  Gurpreet Singh Nanda

IPC: G06F11/30 ,  G06F11/07 ,  G06F12/02 ,  G06F9/30 ,  G06F9/46

Abstract: A method for processing data exactly once using transactional stream writes includes receiving, from a client, a batch of data blocks for storage on memory hardware in communication with the data processing hardware. The batch of data blocks is associated with a corresponding sequence number and represents a number of rows of a table stored on the memory hardware. The method also includes partitioning the batch of data blocks into a plurality of sub-batches of data blocks. For each sub-batch of data blocks, the method further includes assigning the sub-batch of data blocks to a buffered stream; writing, using the assigned buffered stream, the sub-batch of data blocks to the memory hardware; updating a storage log with an intent to commit the sub-batch of data blocks using the assigned buffered stream; and committing the sub-batch of data blocks to the memory hardware.

公开(公告)号：US11880290B2

公开(公告)日：2024-01-23

申请号：US18165257

申请日：2023-02-06

Applicant: Google LLC

Inventor： Pavan Edara ,  Reuven Lax ,  Yi Yang ,  Gurpreet Singh Nanda

IPC: G06F11/14 ,  G06F11/30 ,  G06F9/30 ,  G06F9/46 ,  G06F11/07 ,  G06F12/02

CPC classification number: G06F11/3034 ,  G06F9/30047 ,  G06F9/467 ,  G06F11/0757 ,  G06F11/0772 ,  G06F11/1402 ,  G06F12/0246 ,  G06F12/0253 ,  G06F2201/84

Abstract: A method for processing data exactly once using transactional stream writes includes receiving, from a client, a batch of data blocks for storage on memory hardware in communication with the data processing hardware. The batch of data blocks is associated with a corresponding sequence number and represents a number of rows of a table stored on the memory hardware. The method also includes partitioning the batch of data blocks into a plurality of sub-batches of data blocks. For each sub-batch of data blocks, the method further includes assigning the sub-batch of data blocks to a buffered stream; writing, using the assigned buffered stream, the sub-batch of data blocks to the memory hardware; updating a storage log with an intent to commit the sub-batch of data blocks using the assigned buffered stream; and committing the sub-batch of data blocks to the memory hardware.

公开(公告)号：US11762868B2

公开(公告)日：2023-09-19

申请号：US17445422

申请日：2021-08-19

Applicant: Google LLC

Inventor： Pavan Edara ,  Yi Yang

IPC: G06F16/24 ,  G06F16/245 ,  G06F16/2458 ,  G06F16/2455

CPC classification number: G06F16/2477 ,  G06F16/24558

Abstract: A method for managing metadata for a transactional storage system include receiving a query request at a snapshot timestamp. The query request requests return of at least one data block from a plurality of data blocks. Each data block includes a corresponding write epoch timestamp and a corresponding conversion indicator indicating whether the data block is active or has been converted at a respective conversion timestamp. The method also includes setting a read epoch timestamp equal to the earliest one of the write epoch and determining whether any of the respective conversion timestamps occurring at or before the snapshot timestamp occur after the read epoch timestamp. The method also includes determining the at least one data block requested by the query request by scanning each of the data blocks including corresponding write epoch timestamps occurring at or after the read epoch timestamp.

公开(公告)号：US20230185688A1

公开(公告)日：2023-06-15

申请号：US18165257

申请日：2023-02-06

Applicant: Google LLC

Inventor： Pavan Edara ,  Reuven Lax ,  Yi Yang ,  Gurpreet Singh Nanda

IPC: G06F11/30 ,  G06F9/30 ,  G06F9/46 ,  G06F11/07 ,  G06F12/02 ,  G06F11/14

CPC classification number: G06F11/3034 ,  G06F9/30047 ,  G06F9/467 ,  G06F11/0757 ,  G06F11/0772 ,  G06F12/0246 ,  G06F12/0253 ,  G06F11/1402 ,  G06F2201/84

Abstract: A method for processing data exactly once using transactional stream writes includes receiving, from a client, a batch of data blocks for storage on memory hardware in communication with the data processing hardware. The batch of data blocks is associated with a corresponding sequence number and represents a number of rows of a table stored on the memory hardware. The method also includes partitioning the batch of data blocks into a plurality of sub-batches of data blocks. For each sub-batch of data blocks, the method further includes assigning the sub-batch of data blocks to a buffered stream; writing, using the assigned buffered stream, the sub-batch of data blocks to the memory hardware; updating a storage log with an intent to commit the sub-batch of data blocks using the assigned buffered stream; and committing the sub-batch of data blocks to the memory hardware.

公开(公告)号：US11442911B2

公开(公告)日：2022-09-13

申请号：US17007495

申请日：2020-08-31

Applicant: Google LLC

Inventor： Pavlo Padinker ,  Pavan Edara ,  Bigang Li

IPC: G06F16/215 ,  G06F16/22 ,  G06F16/23 ,  G06F12/0804

Abstract: The present disclosure describes a service which provides primary in-line deduplication. A streaming application program interface (API) may allow for streaming records into a storage system with high throughput and low latency. As part of this process, the API allows user to add identifiers as a field used for data deduplication. The deduplication service keeps a moving window of the identifiers in memory and does in-line deduplication by quickly determining whether data is a duplicate. Keeping only deduplication keys in memory reduces the cost of running the service. Moreover, the real-time nature of the moving window approach allows for storing deduplication information alongside the data and accessing it immediately on read. In this regard, read after write consistency is supported, and costs are reduced.

公开(公告)号：US20210349648A1

公开(公告)日：2021-11-11

申请号：US16872238

申请日：2020-05-11

Applicant: Google LLC

Inventor： Seyed Omid Fatemieh ,  Mikhail Entin ,  Adrian Baras ,  Pavan Edara ,  Aleksandras Surna

IPC: G06F3/06

Abstract: A method for execution-time dynamic range partitioning includes receiving user data including a partitioning key and a clustering key. The user data includes a respective number of total rows defining a total data size for the user data. The method also includes identifying storage constraints for the data storage system. The storage constraints include a target file size and a target number of rows per file. The method further includes determining a plurality of split points for the user data based on the storage constraints. The method also includes generating partitioning quantiles from the plurality of split points that define a range between each split point of the plurality of split points. The method further includes range partitioning each row of the user data into files using the partitioning quantiles.

公开(公告)号：US20210319044A1

公开(公告)日：2021-10-14

申请号：US16848810

申请日：2020-04-14

Applicant: Google LLC

Inventor： Hua Zhang ,  Pavan Edara ,  Nhan Nguyen

IPC: G06F16/28 ,  G06F21/64

Abstract: A method for shuffle-less reclustering of clustered tables includes receiving a first and second group of clustered data blocks sorted by a clustering key value. A range of clustering key values of one or more the data blocks in the second group overlaps with the range of clustering key values of a data block in the first group. The method also includes generating split points for partitioning the first and second groups of clustered data blocks into a third group. The method also includes partitioning using the split points, the first and second groups into the third group. Each data block in the third group includes a range of clustering key values that do not overlap with any other data block in the third group. Each split point defines an upper limit or lower limit for the range of clustering key values a data block in the third group.

公开(公告)号：US20250156391A1

公开(公告)日：2025-05-15

申请号：US18508730

申请日：2023-11-14

Applicant: Google LLC

Inventor： Zhaozhe Song ,  Pavan Edara ,  Bigang Li

IPC: G06F16/22 ,  G06F13/16

Abstract: A method for a single writer B-tree architecture on disaggregated memory includes receiving a write request for a distributed database that requests the data processing hardware update the distributed database. The distributed database is indexed using a B-tree stored on a plurality of servers. Each server of the plurality of servers stores a portion of the B-tree. The method includes modifying, using the write request, a portion of a fixed-size buffer pool. The fixed-size buffer pool is stored at local memory of a primary server of the plurality of servers and corresponds to a portion of the B-tree. The method includes, in response to modifying the portion of the fixed-size buffer pool, writing, to a respective server of the plurality of servers that stores the corresponding portion of the B-tree, the modified portion of the fixed-size buffer pool.

公开(公告)号：US11762821B2

公开(公告)日：2023-09-19

申请号：US17876660

申请日：2022-07-29

Applicant: Google LLC

Inventor： Pavlo Padinker ,  Pavan Edara ,  Bigang Li

IPC: G06F16/215 ,  G06F16/22 ,  G06F16/23 ,  G06F12/0804

CPC classification number: G06F16/215 ,  G06F12/0804 ,  G06F16/2282 ,  G06F16/235 ,  G06F16/2322

Abstract: The present disclosure describes a service which provides primary in-line deduplication. A streaming application program interface (API) may allow for streaming records into a storage system with high throughput and low latency. As part of this process, the API allows user to add identifiers as a field used for data deduplication. The deduplication service keeps a moving window of the identifiers in memory and does in-line deduplication by quickly determining whether data is a duplicate. Keeping only deduplication keys in memory reduces the cost of running the service. Moreover, the real-time nature of the moving window approach allows for storing deduplication information alongside the data and accessing it immediately on read. In this regard, read after write consistency is supported, and costs are reduced.

公开(公告)号：US11579778B2

公开(公告)日：2023-02-14

申请号：US17098306

申请日：2020-11-13

Applicant: Google LLC

Inventor： Pavan Edara ,  Jonathan Forbes

IPC: G06F3/06 ,  G06F11/14 ,  G06F11/30

Abstract: A method for synchronous replication of stream data includes receiving a stream of data blocks for storage at a first storage location associated with a first geographical region and at a second storage location associated with a second geographical region. The method also includes synchronously writing the stream of data blocks to the first storage location and to the second storage location. While synchronously writing the stream of data blocks, the method includes determining an unrecoverable failure at the second storage location. The method also includes determining a failure point in the writing of the stream of data blocks that demarcates data blocks that were successfully written and not successfully written to the second storage location. The method also includes synchronously writing, starting at the failure point, the stream of data blocks to the first storage location and to a third storage location associated with a third geographical region.