Table and index communications channels

• US 10,102,228 B1
• Filed: 02/17/2014
• Issued: 10/16/2018
• Est. Priority Date: 02/17/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Huang, Xianglong, Lu, Yijun, Xiao, Wei, Zheng, Jiandan
• Primary Examiner(s): Meng, Jau-Shya
• Application Number:
  US14/182,248
• Time in Patent Office: 1,702 Days
• Field of Search: None
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

One or more table partitions may communicate with one or more index partitions. A communications channel may be dedicated to each combination of table partition and index partition. The communications channel may act as a queue of messages corresponding to updates to data maintained in a table partition that have yet to be processed by a corresponding index partition. Upon splitting a table partition, communications channels may be duplicated including unprocessed messages. Connections between new table partitions and an index may be finalized upon the index'"'"'s receipt of a message indicative of the new table partition.

Claims

1. A system comprising:

one or more computing nodes that at least;

maintain a table on a first table partition, the first table partition comprising a plurality of items; and

maintain a first index on a first index partition, the first index corresponding to the plurality of items; and

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

store one or more messages in a first buffer, the one or more messages indicative of one or more updates to the plurality of items, wherein messages in the first buffer are sent to the first index partition;

form a second buffer in response to receiving information indicative of a forming of a second table partition comprising a subset of the plurality of items, the second buffer containing the one or more messages, wherein messages in the second buffer are sent to the first index partition;

add a first additional message to the second buffer upon receiving information indicative of an update of a first item of the subset of the plurality of items, the first additional message indicative of the update to the first item;

add a second additional message to a buffer other than the second buffer upon receiving information indicative of an update of another item not of the subset of the plurality of items; and

send the one or more messages and the first additional message in the second buffer to the first index partition, wherein the first index partition processes at least the first additional message to update the index.

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

add to the second buffer a message indicative of forming the second table partition; and

send the message indicative of forming the second table partition to the first index partition.

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

initiate communication between the second buffer on the second table partition and a receiving buffer on the first index partition.

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

maintain a first receiving buffer on the first index partition, the system configured to store messages from the first table partition in the first receiving buffer; and

form a second receiving buffer on the first index partition upon receiving information indicative of forming the second table partition.

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

accumulate new messages in the first buffer upon receiving information indicative of the first index partition being unable to process a message in the first buffer; and

send the new messages accumulated in the first buffer to a second index partition upon receiving information indicative of a second index partition being able to process the message in the first buffer.

6. A computer-based method comprising:

adding, by one or more processors of a computer, one or more messages to a first queue, the first queue storing messages for transmission over a first communications channel between a first table partition on a first computing node and a first index partition on a second computing node, the one or more messages indicative of one or more updates to a plurality of items maintained in the first table partition;

forming, by the one or more processors, a second queue in response to receiving information indicative of a forming of a second table partition, the second table partition based on the first table partition, the second table partition comprising a subset of the plurality of items;

adding, by the one or more processors, the one or more messages to the second queue; and

sending, by the one or more processors, from the second queue to the first index partition, the one or more messages and an additional message indicative of an update to an item of the subset of the plurality items, wherein messages indicative of updates to items not of the subset of the plurality of items are sent from the first queue to the first index partition, and wherein the first index partition processes at least the additional message to update the index.

7. The method of claim 6, further comprising:

adding a message indicative of the forming of the second table partition to the first queue.

8. The method of claim 7, further comprising:

forming a second communications channel upon receiving, at the first index partition, the message indicative of forming the second table partition, the second communications channel between the second table partition and the first index partition.

9. The method of claim 6, wherein the first communications channel comprises the first queue.

10. The method of claim 6, further comprising:

suspending communication between the first table partition and the first index partition upon receiving information indicative of a second index partition being formed from the first index partition.

11. The method of claim 10, further comprising:

receiving a first log sequence number from the second index partition; and

sending messages with logs sequence numbers greater than the first log sequence number to the second index partition.

12. The method of claim 6, further comprising:

forming a third table partition from the second table partition;

forming a third communications channel comprising a third queue; and

adding unprocessed messages in the second queue to the third queue.

13. The method of claim 6, further comprising:

forming the second queue on the second table partition.

14. The method of claim 13, further comprising:

sending information indicative of the one or more messages in the first queue from the first table partition to the second table partition.

15. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:

add one or more messages to a first queue, the first queue configured to store messages for transmission over a first communications channel between a first table partition and a first index partition, the one or more messages indicative of one or more updates to a plurality of items maintained in the first table partition;

form a second queue in response to receiving information indicative of a forming of a second table partition, the second table partition based on the first table partition, the second table partition comprising a subset of the plurality of items;

add the one or more messages to a second queue associated with a second communications channel; and

send, from the second queue to the first index partition, the one or more messages and an additional message indicative of an update to an item of the subset of the plurality items, wherein messages indicative of updates to items not of the subset of the plurality of items are sent from the first queue to the first index partition, and wherein the first index partition processes at least the additional message to update the index.

16. The non-transitory computer-readable medium of claim 15, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

add a message indicative of the forming of the second table partition to the first queue.

17. The non-transitory computer-readable medium of claim 16, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

form the second communications channel upon receiving, at the first index partition, the message indicative of forming the second table partition, the second communications channel between the second table partition and the first index partition.

18. The non-transitory computer-readable medium of claim 15, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

form the second queue on the second table partition, wherein forming the second queue comprises transmitting log information from a first computing node associated with the first queue to a second computing node associated with the second queue.

19. The non-transitory computer-readable medium of claim 15, wherein the second queue is formed from the first queue.

20. The non-transitory computer-readable medium of claim 15, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

suspend communication between the first table partition and the first index partition upon receiving information indicative of a second index partition being formed from the first index partition.