STATIC SORTED INDEX REPLICATION

• US 20150169658A1
• Filed: 02/23/2015
• Published: 06/18/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.
• Granted Patent: US 10,853,340 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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-25. -25. (canceled)

26. 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 tree-based replicas, wherein individual one of the tree-based replicas are implemented as respective data structures in a memory tree;

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

sequentially store the received data in a static sorted index of the partitioned distributed data store.

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

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

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

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

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

purge the memory tree of the first replica;

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

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

compressing the single static sorted index.

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

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

in response to receipt of the request, perform the range query on the static sorted index.

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

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

determine a type of the query; and

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

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

after said sequential store of the received data in the static sorted index;

receive and store other data in the respective memory tree of one of the plurality of replicas, and

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

generate a new replica to replace a failed replica. Wherein to generate the new replica the program instructions are further executable by the one or more processors to apply 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.

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

prior to said sequential store of the received data in the static sorted index, store an indication of the received data in one or more transaction logs; and

purge the one or more transaction logs after performing said sequential store of the received data in the static sorted index.

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

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

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

35. The system of claim 26, wherein the static sorted index is implemented as a log structured merge (LSM) tree.

36. 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 tree-based replicas, wherein individual ones of the tree-based replicas are implemented as respective data structures in a memory tree;

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

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

37. The method of claim 36, further comprising:

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

38. The method of claim 37, 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.

39. The method of claim 37, further comprising:

compressing the single static sorted index.

40. The method of claim 36, 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.

41. The method of claim 36, 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.

42. The method of claim 36, 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.

43. The method of claim 36, 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.

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

45. 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 tree-based replicas, wherein individual ones of the tree-based replicas are implemented as respective data structures in a memory tree;

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

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