Static sorted index replication

• US 8,965,849 B1
• Filed: 08/06/2012
• Issued: 02/24/2015
• Est. Priority Date: 08/06/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Goo, Almann T.
• Primary Examiner(s): Girma, Anteneh
• Application Number:
  US13/567,947
• Time in Patent Office: 932 Days
• US Class Current: 707/634
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

Static sorted index replication is described. A method may include receiving data to store in a memory tree of a replica in a partitioned distributed data store. The method may also include storing the received data in the respective memory tree of one of a plurality of replicas. The method may further include storing the received data sequentially in a static sorted index.

Claims

1. A system, comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to;

receive data to store in a partitioned distributed data store, wherein the partitioned distributed data store includes a plurality of b-tree based replicas, wherein each b-tree based replica is implemented as a data structure in a b-tree;

store the received data in one of the b-trees;

store an indication of the received data in a transaction log associated with the one b-tree; and

store the received data sequentially in a log structured merge (LSM)-based replica of the partitioned distributed data store, wherein the LSM-based replica is implemented as a data structure in an LSM tree, wherein after the data is stored in the LSM-based replica, the data stored in the LSM-based replica is read only.

2. The system of claim 1, wherein the program instructions are further executable by the one or more processors to:

merge the LSM-based replica with a previously generated LSM-based replica into a merged LSM-based replica;

provide sequential data from the merged LSM-based replica to a new b-tree based replica; and

purge one or more b-tree based replicas of the plurality of b-tree based replicas.

3. The system of claim 1, wherein the program instructions are further executable by the one or more processors to:

store other received data in the one b-tree;

store an indication of the other received data in the transaction log associated with the one b-tree; and

generate a new b-tree based replica to replace a failed b-tree based replica of the plurality of b-tree based replicas by copying data from the LSM-based replica and applying updates corresponding to the stored data and stored other data indicated in the transaction log to the copied data.

4. A method, comprising:

performing, by one or more computers;

receiving data to store in a partitioned distributed data store, wherein the partitioned distributed data store includes a plurality of b-tree based replicas, wherein each b-tree based replica is implemented as a data structure in a memory tree;

storing the received data in the respective memory tree of one of the plurality of replicas;

sequentially storing the received data in a static sorted index of the partitioned distributed data store; and

after said sequentially storing;

receiving and storing other data in the respective memory tree of one of the plurality of replicas, and

storing an indication of the other data in one or more transaction logs; and

generating a new replica to replace a failed replica by applying updates corresponding to the stored other data indicated in the one or more transaction logs to a copy of the sequentially stored data from the static sorted index.

5. The method of claim 4, further comprising:

merging the static sorted index with another static sorted index into a single static sorted index.

6. The method of claim 5, further comprising:

generating another memory tree for a first replica of the plurality of replicas;

storing the single static sorted index in the other memory tree for the first replica; and

purging the memory tree of the first replica;

wherein subsequently received data is storable in the other memory tree for the first replica.

7. The method of claim 5, further comprising:

compressing the single static sorted index.

8. The method of claim 4, further comprising:

receiving a request to perform a range query on the partitioned distributed data store; and

in response to receiving the request, performing the range query on the static sorted index.

9. The method of claim 4, further comprising:

receiving a request to perform a query on the partitioned distributed data store;

determining a type of the query; and

selecting the static sorted index or one of the plurality of replicas on which to perform the query, wherein said selecting is based on the determined type of query.

10. The method of claim 4, further comprising:

prior to said sequential storing, storing an indication of the received data in one or more transaction logs; and

purging the one or more transaction logs after performing said sequential storing.

11. The method of claim 4, further comprising:

storing other received data in the respective memory tree of one of the respective replicas; and

sequentially storing the other received data into the static sorted index as part of the sequential storing of the received data into the static sorted index.

12. The method of claim 4, wherein the static sorted index is implemented as a log structured merge (LSM) tree.

13. A non-transitory computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

receiving data to store in a partitioned distributed data store, wherein the partitioned distributed data store includes a plurality of index data structures, wherein each index data structure is implemented as a b-tree based memory tree;

storing the received data in the respective memory tree of one of the plurality of index data structures; and

storing the received data sequentially in a log structured merge (LSM)-based index data structure, wherein the LSM-based index data structure is implemented as an LSM tree, wherein after the received data is stored sequentially in the LSM-based index data structure, the received data in the LSM-based index data structure is read only.

14. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions are further computer-executable to implement:

storing other received data in the respective memory tree of one of the plurality of index data structures; and

storing the other received data sequentially in another LSM-based index data structure, wherein the other LSM-based index data structure is implemented as an LSM tree, wherein after the other received data is stored sequentially in the other LSM-based index data structure, the other received data in the other LSM-based index data structure is read only.

15. The non-transitory computer-readable storage medium of claim 14, wherein the program instructions are further computer-executable to implement:

merging the LSM-based index data structure with the other LSM-based index data structure into a merged LSM-based index data structure.

16. The non-transitory computer-readable storage medium of claim 15, wherein the program instructions are further computer-executable to implement:

providing sequential data from the merged LSM-based index data structure to a memory tree of a new index data structure; and

purging one or more of the plurality of index data structures.

17. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions are further computer-executable to implement:

receiving a request to perform a range query on the partitioned distributed data store; and

in response to receiving the request, performing the range query on the LSM-based index data structure.

18. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions are further computer-executable to implement:

prior to said storing the received data sequentially in the LSM-based index data structure, storing an indication of the received data in a transaction log; and

generating a new index data structure to replace a failed index data structure of the plurality of index data structures by applying updates corresponding to the stored data indicated in the transaction log to a copy of the sequentially stored data from the LSM-based index data structure.

19. The non-transitory computer-readable storage medium of claim 13, wherein the program instructions are further computer-executable to implement:

before performing said storing the data sequentially in the LSM-based index data structure, storing at least some other received data in the respective memory tree of one of the plurality of index data structures;

wherein said storing the data sequentially in the LSM-based index data structure also includes storing the other received data sequentially in the LSM-based index data structure.

20. A method, comprising:

performing, by one or more computers;

receiving data to store in a partitioned distributed data store, wherein the partitioned distributed data store includes a plurality of b-tree based replicas, wherein each b-tree based replica is implemented as a data structure in a memory tree;

storing the received data in the respective memory tree of one of the plurality of replicas;

receiving other data to store in the partitioned data store;

storing the other received data in the respective memory tree of one of the plurality of replicas;

generating a read only sorted replica, wherein said generating includes storing the received data and other data sequentially in the read only sorted replica, wherein the read only sorted replica is read only after the received data and other data are sequentially stored;

performing said generating one or more additional times for additional received data resulting in one or more additional read only sorted replicas; and

after reaching a threshold quantity of read only sorted replicas, merging the read only sorted replica and the one or more additional read only sorted replicas into a single merged read only sorted replica.

21. The method of claim 20, further comprising:

providing sequential data from the single merged read only sorted replica to a memory tree of a new replica; and

purging one or more of the plurality of replicas.

22. The method of claim 20, further comprising:

prior to said storing the received data and other data sequentially in the read only sorted replica, storing a respective indication of the received data and other data in a transaction log; and

generating a new replica to replace a failed replica of the plurality of replicas by applying updates corresponding to the stored data and other data indicated in the transaction log to a copy of the sequentially stored data from the read only sorted replica.

23. The method of claim 20, further comprising:

receiving a request to perform a range query on the partitioned distributed data store; and

in response to receiving the request, performing the range query on the read only sorted replica.