Optimized log storage for asynchronous log updates

Patent metadata

Field	Value
Publication number	US-10534768-B2
Application number	US-201514981540-A
Country	US
Kind code	B2
Filing date	Dec 28, 2015
Priority date	Dec 2, 2013
Publication date	Jan 14, 2020
Grant date	Jan 14, 2020

Abstract

A log-structured data store may implement optimized log storage for asynchronous log updates. In some embodiments, log records may be received indicating updates to data stored for a storage client and indicating positions in a log record sequence. The log records themselves may not be guaranteed to be received according to the log record sequence. Received log records may be stored in a hot log portion of a block-based storage device according to an order in which they are received. Log records in the hot log portion may then be identified to be moved to a cold log portion of the block-based storage device in order to complete a next portion of the log record sequence. Log records may be modified, such as compressed, or coalesced, before being stored together in a data block of the cold log portion according to the log record sequence.

First claim

What is claimed is:

1. A system, comprising:
a network interface;
a non-volatile storage device;
at least one processor; and
a memory, that stores program instructions that when executed by the at least one processor causes the at least one processor to:
responsive to receiving individual ones of a plurality of log records from a storage client via the network interface and storing the individual ones of the plurality of log records in an unordered portion of a log in the non-volatile storage device, send respective storage acknowledgements of the individual ones of the plurality of log records to the storage client;
wherein log records stored in the log describe updates to data stored in a data store, wherein at least one of the log records is stored out-of-order with respect to a log record sequence for the log; and
subsequent to the sending of at least one of the storage acknowledgments, update an ordered portion of the log to store an ordered version of one or more of the log records from the unordered portion of the log including the at least one log record.

2. The system of claim 1 , wherein to update the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log, the program instructions cause the at least one processor to update an index for the ordered portion of the log to identify one or more data blocks that store the ordered version of the one or more log records.

3. The system of claim 2 ,
wherein the program instructions further cause the at least one processor to update an index for the unordered portion of the log as the log records are stored in the unordered portion of the log to identify respective storage locations for the log records in the unordered portion of the log; and
wherein to update the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log further the program instructions cause the at least one processor to evaluate the index for the unordered portion of the log to identify the one or more log records to be stored in the ordered portion of the log.

4. The system of claim 1 , wherein to update the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log, the program instructions cause the at least one processor to generate the ordered version of the one or more log records according to a compression technique.

5. The system of claim 1 ,
wherein the program instructions further cause the at least one processor to determine that a number of log records in the unordered portion of the log linked in a dependency chain exceeds a coalesce threshold;
wherein the update to the ordered portion of the log is performed in response to the determination that the number of log records in the unordered portion of the log linked in the dependency chain exceeds the coalesce threshold; and
wherein to update the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log, the program instructions cause the at least one processor to coalesce the log records linked in the dependency chain into a single log record to include as part of the ordered version of the one or more log records.

6. The system of claim 1 , wherein the system is a storage node of a network-based distributed storage service, and wherein the storage client is a network-based database service configured to access the data stored for a database.

7. A method, comprising:
performing, by one or more computing devices:
responsive to receiving individual ones of a plurality of log records from a storage client and storing in an unordered portion of a log, sending respective storage acknowledgements of the individual ones of the plurality of log records to the storage client;
wherein log records stored in the log describe updates to data stored in a data store, wherein at least one of the log records is stored out-of-order with respect to a log record sequence for the log; and
subsequent to sending the storage acknowledgments, updating an ordered portion of the log to store an ordered version of one or more of the log records from the unordered portion of the log including the at least one log record.

8. The method of claim 7 , wherein updating the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log comprises updating an index for the ordered portion of the log to identify one or more data blocks that store the ordered version of the one or more log records.

9. The method of claim 8 ,
wherein the method further comprises updating an index for the unordered portion of the log as the log records are stored in the unordered portion of the log to identify respective storage locations for the log records in the unordered portion of the log; and
wherein updating the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log further comprises evaluating the index for the unordered portion of the log to identify the one or more log records to be stored in the ordered portion of the log.

10. The method of claim 7 , wherein updating the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log comprises generating the ordered version of the one or more log records according to a compression technique.

11. The method of claim 7 ,
wherein the method further comprises determining that a number of log records in the unordered portion of the log linked in a dependency chain exceeds a coalesce threshold;
wherein the updating the ordered portion of the log is performed in response to determining that the number of log records in the unordered portion of the log linked in the dependency chain exceeds the coalesce threshold; and
wherein updating the ordered portion of the log to store the ordered version of the one or more log records from the unordered portion of the log comprises coalescing the log records linked in the dependency chain into a single log record to include as part of the ordered version of the one or more log records.

12. The method of claim 7 , wherein the acknowledging and the updating are performed by a storage node of a network-based distributed storage service, and wherein the plurality of log records are received from a network-based database service configured to access the data stored for a database.

13. The method of claim 12 , further comprising:
receiving a request from another storage node of the network-based distributed storage service for select log records of the log stored at the storage node, wherein the select log records include the ordered version of the one or more log records stored in the ordered portion of the log;
sending the select log records from the storage node to the other storage node; and
storing the select log records in an ordered portion of the log maintained at the other storage node.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:
responsive to receiving individual ones of a plurality of log records from a storage client and storing in an unordered portion of a log, sending respective storage acknowledgements of the individual ones of the plurality of log records to the storage client;
wherein log records stored in the log describe updates to data stored in a data store, wherein at least one of

Assignees

• Amazon Tech Inc

Inventors

• Madhavarapu Pradeep Jnana
• Mittal Raman
• Tobler Benjamin
• Corey James Mcclellan
• Leshinsky Yan Valerie
• Mckelvie Samuel James
• Gupta Anurag Windlass

Classifications

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/273 Primary

  Asynchronous replication or reconciliation · CPC title