Index Update Pipeline

• US 20140344236A1
• Filed: 05/20/2013
• Published: 11/20/2014
• Est. Priority Date: 05/20/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Xiao, Wei, Rath, Timothy Andrew, Stefani, Stefano, Ng, Clarence Wing Yin, Dhawan, Medhavi
• Granted Patent: US 11,841,844 B2
• Time in Patent Office: Days
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27

Abstract

Distributed database management systems may maintain collections of items spanning multiple partitions. Index structures may correspond to items on one partition or to items on multiple partitions. Item collections and indexes may be replicated. Changes to the data maintained by the distributed database management system may result in updates to multiple index structures. The changes may be compiled into an instruction set applicable to the index structures. In-memory buffers may contain the instructions prior to transmission to affected partitions. Replication logs may be combined with an acknowledgment mechanism for reliable transmission of the instructions to the affected partitions.

Claims

1. A distributed database management system comprising:

a first computing node comprising a first one or more storage devices, the first one or more storage devices having stored thereon a log file and a first collection of items corresponding to a first index;

a second computing node comprising a memory and a second one or more storage devices, the second one or more storage devices having stored thereon a second index, the second index corresponding to a version of at least a subset of the first collection;

one or more memories having stored thereon computer readable instructions that, upon execution, cause the system at least to;

write, to the log file, an instruction corresponding to a first operation on the first index, the first operation corresponding to a first request to modify the first collection of items;

send the instruction from the log file to the second computing node, based at least in part on a record of a last instruction received from the first computing node and performed by the second computing node on the second index; and

perform, by the second computing node, a second operation on the second index, the second operation based at least in part on the instruction.

2. The system of claim 1, further comprising one or more memories having stored thereon computer readable instructions that, upon execution, cause the system at least to:

receive, by the first computing node, an acknowledgment from the second computing node, the acknowledgment based at least in part on performing the second operation.

3. The system of claim 1, further comprising one or more memories having stored thereon computer readable instructions that, upon execution, cause the system at least to:

store the instruction in the memory of the second computing node; and

remove the instruction from the memory when the instruction is performed.

4. The system of claim 1, wherein the last instruction performed was performed prior to a system failure, further comprising one or more memories having stored thereon computer readable instructions that, upon execution, cause the system at least to:

cause the instruction to be sent to the second computing node upon recovering from the system failure.

5. A computer-implemented method for storing and retrieving data, the method comprising:

recording, in a log file of a first computing node, information indicative of an instruction corresponding to a first operation on a first index of a first collection of items, the first operation corresponding to a first request to modify the first collection of items;

sending, by the first computing node, the information indicative of the instruction to a second computing node based at least in part on a record of a last instruction performed by the second computing node; and

performing, by the second computing node, a second operation on a second index, the second index corresponding to a version of at least a subset of the first collection, the second operation based at least in part on the information indicative of the instruction.

6. The method of claim 5, further comprising:

receiving, by the first computing node, an acknowledgment from the second computing node, the acknowledgment based at least in part on performing the second operation.

7. The method of claim 6, wherein the acknowledgement corresponds to an error condition.

8. The method of claim 6, further comprising:

upon receiving the acknowledgment, removing the information indicative of the instruction from a data structure in a memory of the first computing node.

9. The method of claim 5, further comprising:

locating one or more unacknowledged instructions in the log file.

10. The method of claim 9, further comprising:

performing steps comprising one or more of removing the instruction from the log file, marking the instruction as performed, and marking the instruction with an indication of an error condition.

11. The method of claim 5, wherein the last instruction performed was performed prior to a system failure.

12. The method of claim 5, further comprising sending, by the second computing node, a request to receive instructions from the first computing node, the request to receive instructions comprising the record of the last instruction performed by the second computing node.

13. The method of claim 5, further comprising storing the information indicative of the instruction in a memory of the second computing node.

14. The method of claim 13, further comprising removing the information indicative of the instruction from the memory of the second computing node upon performing the instruction.

15. The method of claim 5, further comprising receiving at the first computing node indicative of a maximum number of instructions to send before receiving an acknowledgement.

16. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by a computing device, cause the computing device at least to:

receive, from a first computing node, information indicative of an instruction, the instruction corresponding to a first operation on a first index, the first operation corresponding to a first request to modify a first collection of items;

perform a second operation on a second index, the second operation based at least in part on the information indicative of the instruction, the second index corresponding to a version of at least a subset of the first collection of items; and

update a record of a last instruction performed on the computing device, the record comprising an indication of the first computing node.

17. The computer-readable storage medium of claim 16, comprising further instructions that, upon execution by the computing device, cause the computing device at least to:

perform the second operation, wherein performing the operation is based at least in part on a first capacity indication associated with the first computing node and a second capacity indication associated with the second computing node.

18. The computer-readable storage medium of claim 16, comprising further instructions that, upon execution by the computing device, cause the computing device at least to:

send to the first computing node an indication of a maximum number of unacknowledged instructions that can be received by the second computing node.

19. The computer-readable storage medium of claim 18, wherein the maximum number is based at least in part on provisioned capacity.

20. The computer-readable storage medium of claim 16, wherein the record of a last instruction performed comprises information indicating that the first computing node sent the instruction.

21. The computer-readable storage medium of claim 16, wherein the version of at least the subset of the first collection of items comprises replicated data from the first collection of items.

22. A system for storing and retrieving data, the system comprising:

a first computing node comprising a first memory and a first one or more storage devices, the first one or more storage devices having stored thereon a first index associated with a first collection of items;

a second computing node comprising a second memory and a second one or more storage devices, the second one or more storage devices having stored thereon a second index; and

one or more processors configured to receive a request to change an item in the first collection of items;

one or more processors configured to determine one or more instructions based at least in part on the request, the one or more instructions indicative of one or more operations on the first index;

one or more processors configured to update the first index on the first computing node, based at least in part on the one or more instructions; and

one or more processors configured to update the second index on the second computing node, based at least in part on the one or more instructions.

23. The system of claim 22, further comprising:

one or more processors configured to store information indicative of the instruction in the first memory prior to sending the information indicative of the instruction to the second computing node;

one or more processors configured to store the information indicative of the instruction in the second memory prior to updating the second index on the second computing node; and

one or more processors configured to receive, at the first computing node, an acknowledgement indicative of the second index being updated.

24. The system of claim 22, wherein the first index corresponds to a collection of items and the second index corresponds to a version of at least a subset of the collection of items.

25. The system of claim 22, wherein the first index corresponds to a first subset of a collection of items and the second index corresponds to a second subset of the collection of items.

26. The system of claim 22, further comprising:

one or more processors configured to store the one or more instructions in a log file; and

one or more processors configured to perform steps comprising one or more of removing the one or more instructions from the log file, marking the one or more instructions as completed, and marking the one or more instructions as unacknowledged.