Chained replication techniques for large-scale data streams

Patent metadata

Field	Value
Publication number	US-9639589-B1
Application number	US-201314136645-A
Country	US
Kind code	B1
Filing date	Dec 20, 2013
Priority date	Dec 20, 2013
Publication date	May 2, 2017
Grant date	May 2, 2017

Abstract

A replication chain comprising one or more replication nodes of a multi-tenant stream management system is assigned to store data records of a partition of a particular data stream. A data record of the partition is received at a selected replication node of the replication chain. In a sequential order, a respective replica of the data record is stored at each replication node of the chain. An acknowledgement of a successful storage of the data record is provided after the replications are completed.

First claim

What is claimed is:

1. A system, comprising:
one or more computing devices configured to:
assign, to store respective replicas of data records of a partition of a particular data stream, a replication chain comprising three or more replication nodes of a multi-tenant stream management system, wherein the replication chain comprises a head replication node and a tail replication node, and wherein at least one replication node of the plurality of replication nodes is implemented at least in part using a resource shared with a different replication node assigned to a different partition of a different data stream;
receive, at an ingestion node of the stream management system assigned to the first partition, a submission request indicating a particular data record of the first partition;
receive the data record at the head replication node from the ingestion node;
store, in a sequential order starting from the head replication node and ending at the tail replication node, a replica of the data record at a respective local storage device at each of the three or more replication nodes of the replication chain;
subsequent to storing the replica of the data record at each of the three or more replication nodes in the sequential order, transmit, from the tail replication node to the ingestion node, an indication that replication of the data record has been completed; and
provide, to a source of the submission request, a response indicating that the data record has been successfully stored at the stream management system.

2. The system as recited in claim 1 , wherein the replication chain is assigned based at least in part on one or more of: (a) an expected temporal distribution of data record submissions to the partition, (b) an expected temporal distribution of data record retrievals from the partition, (c) one or more performance metrics of resources configurable to implement replication nodes, (d) input/output performance characteristics of storage devices accessible from replication nodes, (e) budget constraints associated with the particular data stream, or (f) a resource usage balancing policy.

3. The system as recited in claim 1 , wherein the head replication node is implemented at a first data center, and the tail replication node is implemented at a different data center.

4. The system as recited in claim 1 , wherein the one or more computing devices are further configured to:
assign at least a particular replication node of the three or more replication nodes to store replicas of data records of a different partition of a different data stream.

5. The system as recited in claim 1 , wherein to store a particular replica of the data record, the one or more computing devices are further configured to:
accumulate a plurality of data records of the partition, including the data record, in a volatile memory buffer at a particular replication node; and
flush the plurality of data records to a particular non-volatile local storage device of the particular replication node using one or more sequential write operations.

6. A method, comprising:
performing, by one or more computing devices:
assigning, to store respective replicas of data records of a partition of a particular data stream, a replication chain comprising three or more replication nodes of a multi-tenant stream management system;
receiving, at a selected replication node of the replication chain, a data record of the partition submitted to the stream management system by a data producer;
storing, in a sequential order, a replica of the data record at a respective local storage device at each replication node of the replication chain; and
providing, subsequent to said storing the replica of the data record at each replication node of the replication chain in the sequential order, an acknowledgement of a successful storage of the data record at the stream management system.

7. The method as recited in claim 6 , wherein the local storage device at a particular replication node of the replication chain comprises non-volatile storage.

8. The method as recited in claim 6 , wherein said assigning is based at least on part on one or more of: (a) a partitioning policy associated with the particular data stream, (b) an expected temporal distribution of data record submissions, (c) an expected temporal distribution of data record retrievals, (d) one or more performance metrics obtained from resources configurable to host replication nodes, (e) input/output performance characteristics of replication nodes of the replication chain, (f) budget constraints associated with the particular data stream, or (g) a resource usage balancing policy.

9. The method as recited in claim 6 , wherein the three or more replication nodes include a first replication node implemented at a first data center, and a second replication node implemented at a different data center.

10. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
assigning at least a particular replication node of the replication chain to store replicas of data records of a different partition of the particular data stream.

11. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
assigning at least a particular replication node of the replication chain to store replicas of data records of a different partition of a different data stream.

12. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
instantiating a particular replication node of the replication chain at a particular computing resource; and
instantiating, at the particular computing resource, a different replication node of a different replication chain assigned to a different partition of a different data stream.

13. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
accumulating a plurality of data records of the partition, including the data record, in a volatile memory buffer at a particular replication node; and
flushing the plurality of data records to a particular non-volatile local storage device of the particular replication node using one or more sequential write operations.

14. The method as recited in claim 6 , wherein the replication chain comprises a plurality of replication nodes, further comprising performing, by the one or more computing devices:
designating a particular replication node of the replication chain as a head replication node configured to receive the data record from an ingestion node of the stream management service, and a different replication node of the replication chain as a tail replication node configured to transmit an acknowledgement to the ingestion node after a plurality of replicas of the data record have been stored.

15. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
receiving a retrieval request for the data record;
selecting, based at least in part on a retrieval workload distribution policy for the partition, a particular replication node of the replication chain from which contents of the data record are to be read; and
providing contents of the data record from the particular replication node.

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:
determine, based at least in part on a partitioning policy associated with a particular data stream of a multi-tenant stream management service, three or more replication nodes to be assigned

Assignees

• Amazon Tech Inc

Inventors

• Theimer Marvin Michael
• Mercier Benjamin Warren
• Glass Nathaniel Martin
• Ghare Gaurav D

Classifications

• G06F11/2028

  eliminating a faulty processor or activating a spare · CPC title

• G06F11/3006

  where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50) · CPC title

• G06F11/1464

  for networked environments · CPC title

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F2201/835

  Timestamp · CPC title