Dynamic utilization of bandwidth for a quorum-based distributed storage system

Patent metadata

Field	Value
Publication number	US-9699017-B1
Application number	US-201314036783-A
Country	US
Kind code	B1
Filing date	Sep 25, 2013
Priority date	Sep 25, 2013
Publication date	Jul 4, 2017
Grant date	Jul 4, 2017

Abstract

A storage client and a quorum-based distributed storage system may implement dynamic utilization of bandwidth for a quorum-based distributed storage system. An update at a storage client may be received, and storage nodes of a protection group may be sent a write request indicating the update. In some embodiment, storage nodes that receive the write request may determine whether other storage nodes have not received the update and send the write request to be completed at those other storage nodes. In some embodiments, if a latency threshold is exceeded other storage nodes in the protection group not previously sent the write request may be identified and sent the write request. Based on acknowledgements received from storage nodes in the distributed storage system, it may be determined whether a write quorum requirement is met for a write request.

First claim

What is claimed is:

1. A system, comprising:
a plurality of storage nodes of a distributed storage system implementing a protection group storing data for a storage client, wherein each storage node includes a corresponding processor; and
the storage client implementing a client-side storage driver module via a storage client processor, wherein the client-side storage driver module is configured to:
in response to receiving an update to the data:
send a write request indicating the update to different ones of the plurality of storage nodes sufficient to satisfy a write quorum requirement for the write request, wherein one or more remaining storage nodes of the protection group are not sent the write request;
determine that one or more acknowledgements received from the different ones of the plurality of storage nodes do not satisfy the write quorum requirement;
in response to said determination, send the write request to at least one of the one or more remaining storage nodes of the protection group in order to satisfy the write quorum requirement; and
based, at least in part, on the one or more acknowledgements received from the different ones of the plurality of storage nodes and one or more acknowledgments received from the one or more remaining storage nodes, determine that the write quorum requirement for the write request is satisfied; and
in response to said determination that the write quorum requirement for the write request is satisfied, acknowledge the write request as durable.

2. The system of claim 1 , wherein to determine that the one or more acknowledgements received from the different ones of the plurality of storage nodes do not satisfy the write quorum requirement, the client-side storage driver module is further configured to detect that a write pending time for the write request exceeds a latency threshold.

3. The system of claim 1 , wherein the client-side storage driver module is further configured to, based at least in part on one or more storage system health or cost indicators, identify the different ones of the plurality of storage nodes implementing the protection group to send the write request.

4. The system of claim 3 ,
wherein system further comprises a storage bandwidth analysis module implemented as part of the distributed storage system that monitors the storage nodes implementing the distributed storage system including the plurality of storage nodes of the protection group and the storage client, and is configured to detect at least one change in the distributed storage system, wherein the at least one change is:
a change in network utilization among one or more of the plurality of storage nodes;
a change in network utilization at the storage;
a change in write performance of one or more of the plurality of storage nodes; or
collected health or cost data of one or more of the plurality of storage nodes exceeding an obsolescence threshold; and

in response to detecting the at least one change, send to the client-side storage driver module the one or more health or cost indicators that indicate the detected at least one change in order to identify storage nodes of the protection group for subsequent write requests.

5. The system of claim 1 ,
wherein the storage client is a database node implemented as part of a network-based distributed database service, wherein the data is stored for a database, wherein the distributed storage system is implemented as part of a multi-tenant, network-based, distributed storage service, wherein the write request is a log record;
wherein, to send the write request to the different ones of the plurality of storage nodes, the client-side storage driver module is configured to send the log record to the different ones of the plurality of storage nodes; and
wherein each of the plurality of storage nodes is further configured to persist received log records in a log-structured data store for the data stored for the database.

6. A method, comprising:
performing, by one or more computing devices:
in response to receiving an update to data at a storage client:
sending a write request indicating the update to at least two storage nodes of a plurality of storage nodes of a distributed storage system implementing a protection group storing the data for the storage client, wherein a write quorum requirement for the write request includes completion of the write request to more than two storage nodes, wherein the at least two storage nodes sent the write request comprise less than the entire plurality of storage nodes implementing the protection group;
receiving one or more acknowledgments from one or more of the at least two storage nodes indicating at least one other storage node that completes the write request, wherein the at least one other storage node is one of the plurality of storage nodes that did not receive the write request from the storage client;
based, at least in part, on the acknowledgments, determining that the write quorum requirement is satisfied for the write request; and
identifying the write request as durable.

7. The method of claim 6 , further comprising:
detecting that a write pending time for the write request exceeds a latency threshold; and
in response to said detecting, sending the write request to the at least one other storage node in the protection group not previously sent the write request;
wherein said determining that the write request satisfies the write quorum requirement for the write request is further based on one or more acknowledgements received from the at least one other storage node.

8. The method of claim 7 , further comprising dynamically determining the latency threshold based, at least in part, on one or more of:
network utilization among the plurality of storage nodes implementing the protection group;
network utilization at the storage client; or
past latency determinations for prior write requests.

9. The method of claim 6 , further comprising based, at least in part, on a change in storage system health or costs for the plurality of storage nodes or the storage client, identify the at least two storage nodes to send the write request.

10. The method of claim 6 , wherein one of the at least two storage nodes is implemented in a different availability zone than the other one of the at least two storage nodes.

11. The method of claim 6 , further comprising performing said sending, said receiving, said determining, and said identifying in response to receiving another update, wherein one of the at least two nodes of the protection group sent write request for the other update is different from the at least two nodes of the protection group sent the write request for the update.

12. The method of claim 6 , wherein the database is implemented as part of a network-based storage service, and wherein the distributed storage system is a multi-tenant, network-based storage service.

13. A non-transitory, computer-readable storage medium, storing program instructions that when performed by one or more computing devices cause the one or more computing devices to implement:
in response to receiving an update at a storage client:
sending a write request indicating the update to at least one storage node of a plurality of storage nodes of a distributed storage system implementing a protection group storing data for the storage client, wherein a write quorum requirement for the write request includes completion of the write request to more than one storage node, wherein the at least one storage node sent the write request comprises less than the entire plurality of storage nodes implementing the protection group;
detecting that a

Assignees

• Amazon Tech Inc

Inventors

• Gupta Anurag Windlass
• Madhavarapu Pradeep Jnana
• Mckelvie Samuel James
• Leshinsky Yan Valerie

Classifications

• H04L29/08072

  Electricity · mapped topic

• H04L29/08549 Primary

  Electricity · mapped topic

• G06F16/27

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

• H04L67/1097 Primary

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L65/40

  Support for services or applications · CPC title