公开(公告)号：US11061903B1

公开(公告)日：2021-07-13

申请号：US15280613

申请日：2016-09-29

Applicant: Amazon Technologies, Inc.

Inventor： Niket Goel ,  Tengiz Kharatishvili ,  Alexandre Olegovich Verbitski ,  Stefano Stefani ,  Alok Nikhil ,  Saileshwar Krishnamurthy ,  Kamal Kant Gupta

IPC: G06F16/2455 ,  G06F3/06 ,  G06F16/22

Abstract: Systems, methods, and computer-readable media are disclosed for an improved database. The systems, methods, and computer-readable media described herein may enhance the response time of databases and improve user experiences. In an example method described herein, a database may receive a search request for data stored in the database. The database may be stored in association with a b-tree to facilitate searching and retrieving data from the database. The method may include allocating a portion of a first memory for read ahead operations and performing the read ahead operations, wherein the read ahead operations comprise loading, into the portion of the first memory, data associated with one or more siblings of a current node, wherein the one or more siblings of the current node are one or more nodes that have a same number of parent nodes as the current node.

公开(公告)号：US11379463B1

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

申请号：US16586563

申请日：2019-09-27

Applicant: Amazon Technologies, Inc.

Inventor： Tengiz Kharatishvili ,  Alexandre Olegovich Verbitski ,  Justin Levandoski ,  Niket Goel ,  Kamal Kant Gupta ,  Xiaofeng Bao ,  Punit Rajgaria

IPC: G06F16/00 ,  G06F16/23 ,  G06F9/46

Abstract: Systems and methods are disclosed to implement, in a database system, a database engine node that generates write tracking transactions to atomically enforce cross-page constraints for write operations. In embodiments, the database system may include multiple database engine nodes that optimistically perform page writes without checking for potential conflicts at a shared storage system. The storage system is configured to detect and report conflicting writes on the same page. To cause the storage system to report cross-page conflicts for a write, the database engine node creates a transaction that includes the write and a write tracker (WT) operation for a tracked page. The WT operation will cause the storage system to report any conflicting writes to the tracked page before the actual write is accepted by the storage system. If a reported conflict is not favorably resolved, the database engine node will abort the entire transaction, including the actual write.

公开(公告)号：US20240012813A1

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

申请号：US18473152

申请日：2023-09-22

Applicant: Amazon Technologies, Inc.

Inventor： Niket Goel ,  Gopi Krishna Attaluri ,  Kamal Kant Gupta ,  Tengiz Kharatishvili ,  Stefano Stefani ,  Alexandre Olegovich Verbitski

IPC: G06F16/2453

CPC classification number: G06F16/24534 ,  G06F16/2246

Abstract: Methods, systems, and computer-readable media for dynamic prefetching for database queries are disclosed. A query of a database is started according to a first prefetch policy. Before completing the query, the first prefetch policy is changed to a second prefetch policy. A portion of the query is performed according to the second prefetch policy.

公开(公告)号：US11366802B1

公开(公告)日：2022-06-21

申请号：US16586355

申请日：2019-09-27

Applicant: Amazon Technologies, Inc.

Inventor： Tengiz Kharatishvili ,  Alexandre Olegovich Vebitski ,  Justin Levandoski ,  Niket Goel ,  Xiang Peng ,  Kamal Kant Gupta ,  Xiaofeng Bao

IPC: G06F16/23 ,  G06F16/18

Abstract: Batch processing of undo log records may be performed for rolling back a database transaction. When a rollback operation for a database transaction is performed, undo log records from an undo log to rollback the database transaction are divided into different groups of undo log records. Different requests for the different undo log records are sent to a storage system to be performed. If a conflict is detected for an undo log record in a group, an indication of the conflicting undo log record may be provided to indicate the conflict. The group of undo log records may be resent with a request to reapply the undo log records in the group. When all groups have been identified as successfully completed, then the rollback operation may be considered completed.

公开(公告)号：US11816103B1

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

申请号：US15909886

申请日：2018-03-01

Applicant: Amazon Technologies, Inc.

Inventor： Niket Goel ,  Gopi Krishna Attaluri ,  Kamal Kant Gupta ,  Tengiz Kharatishvili ,  Stefano Stefani ,  Alexandre Olegovich Verbitski

IPC: G06F16/245 ,  G06F16/2453 ,  G06F16/22

CPC classification number: G06F16/24534 ,  G06F16/2246

Abstract: Methods, systems, and computer-readable media for dynamic prefetching for database queries are disclosed. A query of a database is started according to a first prefetch policy. Before completing the query, the first prefetch policy is changed to a second prefetch policy. A portion of the query is performed according to the second prefetch policy.

公开(公告)号：US11080262B1

公开(公告)日：2021-08-03

申请号：US16586497

申请日：2019-09-27

Applicant: Amazon Technologies, Inc.

Inventor： Justin Levandoski ,  Niket Goel ,  Tengiz Kharatishvili ,  Alexandre Olegovich Verbitski ,  Kamal Kant Gupta ,  Xiaofeng Bao

IPC: G06F16/23 ,  G06F16/22 ,  G06F16/2455

Abstract: Systems and methods are disclosed to implement, in a database system, database engine nodes that implement multi-page writes as an atomic operation. In embodiments, the database system may include multiple database engine nodes that optimistically perform page writes locally without checking for potential conflicts at a shared storage system. The storage system will detect and report conflicting writes on a single page. To ensure that a group of writes to multiple pages occur atomically, the database engine node maintains a transaction context for the group, so that if a page conflict is later detected for any write in the group, the entire group will be rolled back at the database engine node and the storage system. In embodiments, the transaction context will track subsequent writes generated by the node to any page written by the group, so that these subsequent writes are also rolled back with the group.

公开(公告)号：US11914571B1

公开(公告)日：2024-02-27

申请号：US15926983

申请日：2018-03-20

Applicant: Amazon Technologies, Inc.

Inventor： Xiaofeng Bao ,  Murali Brahmadesam ,  Yi Ding ,  Niket Goel ,  Anurag Windlass Gupta ,  Kamal Kant Gupta ,  Changan Han ,  Tiffany Jianto ,  Tengiz Kharatishvili ,  Saileshwar Krishnamurthy ,  Bohan Liu ,  Saleem Mohideen ,  Punit Rajgaria ,  Joseph Andrew Tucek ,  Alexandre Olegovich Verbitski

IPC: G06F16/23 ,  G06F16/17 ,  G06F16/176

CPC classification number: G06F16/2315 ,  G06F16/1734 ,  G06F16/1767

Abstract: Optimistic concurrency may be implemented for multiple writers to a database. Writes to a database from different writers may succeed unless a conflict is detected at the data store for the database. For detected conflicts, a request to resolve the conflict between writes may be submitted to a primary writer, which may determine and provide a resolution of the conflict to the conflicting writers. The data store may then be updated to commit the selected write identified by the resolution of the conflict.

公开(公告)号：US11874796B1

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

申请号：US16586235

申请日：2019-09-27

Applicant: Amazon Technologies, Inc.

Inventor： Tengiz Kharatishvili ,  Alexandre Olegovich Verbitski ,  Justin Levandoski ,  Niket Goel ,  Kamal Kunt Gupta ,  Xiaofeng Bao

IPC: G06F15/16 ,  G06F16/16 ,  G06F16/18 ,  G06F16/17 ,  G06F16/176

CPC classification number: G06F16/162 ,  G06F16/1734 ,  G06F16/1767 ,  G06F16/1873

Abstract: Systems and methods are disclosed to implement, in a multi-writer database system, a database engine node that optimistically sends queued purge operations to a backend storage system without waiting for acknowledgement of previous operations from the storage system. If a conflict is later detected for a particular operation, the database engine node may retry some portion of the purge operations in the queue. In embodiments, the purge operations are performed as part of a garbage collection phase of a multi-version concurrency control (MVCC) protocol, where unneeded versions of objects previously generated for isolated snapshots are deleted. In embodiments, the operations in the queue may be grouped so that a rejection of one operation in the group will cause the entire group to be retried. Because these purge operations are idempotent and directed to objects that are invisible, they may be freely retried in arbitrary order, without maintaining any rollback state.