Future write in distributed system maintaining data storage integrity
A method for performing a write operation in a distributed storage system is disclosed. The method comprises receiving a first time-stamped write request from a proxy server. Further, the method comprises determining if the first time-stamped write request is within a time window of a reorder buffer and if the first time-stamped write request overlaps with a second time-stamped write request in the reorder buffer. Responsive to a determination that the first time-stamped write request is outside the time window or that the first time-stamped write request is within the time window but has an older time-stamp than the second time-stamped write request, the method comprises rejecting the first time-stamped write request. Otherwise, the method comprises inserting the first time-stamped write request in the reorder buffer in timestamp order and transmitting an accept to the proxy server.
1. A method for performing a write operation in a distributed storage system, the method comprising:
receiving a write request from a client at a proxy server, wherein the proxy server is disposed between one or more clients and one or more storage servers as an intermediary, and wherein the proxy server is configured to receive read requests and write requests from the one or more clients and distribute the read requests and the write requests to the one or more storage servers;
augmenting the write request with a timestamp at the proxy server;
responsive to a determination at the proxy server that the time-stamped write request has been retried over a threshold number of times, setting a status for the time-stamped write request as a future write and adding a first offset to the timestamp of the time-stamped write request, wherein the proxy server is configured to augment the time-stamped write request with a status indication indicating that the time-stamped write request comprises a future write;
transmitting the time-stamped write request from the proxy server to a storage server of the one or more storage servers, wherein the storage server comprises a reorder buffer and a future buffer, wherein the reorder buffer is a timestamp ordered data structure for holding the read requests and the write requests while timestamps associated therewith are examined, wherein the reorder buffer maintains a time window comprising an interval of time into a past from a current time and an interval of time into a future from the current time, and wherein a time window of the future buffer starts at a future time where the time window of the reorder buffer ends;
receiving an accept at the proxy server from the storage server responsive to a determination at the storage server that the timestamp including the first offset associated with the time-stamped write request is within the time window of the future buffer, wherein the accept originates from the storage server in response to the storage server inserting the time-stamped write request into the future buffer.
2. The method of claim 1 , wherein the first offset is equal to at least a duration of the time window of the reorder buffer.
3. The method of claim 1 , further comprising:
receiving a reject from the storage server responsive to a determination at the storage server that the time-stamped write request is not within the time window of the reorder buffer;
sending an abort to all storage servers in a cluster receiving the time-stamped write request; and
re-trying the time-stamped write request with a second offset, wherein the second offset is larger than the first offset.
4. The method of claim 1 , further comprising:
sending a commit to the storage server responsive to receiving an accept from all storage servers in a cluster receiving the time-stamped write request, wherein the storage server is operable to mark the time-stamped write request in the future buffer as committed, and wherein further the time-stamped write request has not yet been promoted to the reorder buffer.
5. The method of claim 1 , further comprising:
sending a commit to the storage server responsive to receiving an accept from all storage servers in a cluster receiving the time-stamped write request, wherein the storage server is operable to mark the time-stamped write request in the reorder buffer as committed, and wherein further the time-stamped write request has been promoted to the reorder buffer.
6. The method of claim 1 , further comprising:
sending an abort to the storage server responsive to receiving a reject from any one of the storage servers in a cluster receiving the time-stamped write request, wherein the storage server is operable, responsive to the abort, to delete the time-stamped write request from the future buffer if the time-stamped write request has not yet been promoted to the reorder buffer or from the reorder buffer if the time-stamped write request has been promoted to the reorder buffer.
7. The method of claim 4 , further comprising:
receiving a committed signal from the storage server; and
responsive to receiving a committed signal from all storage servers in the cluster, sending a write acknowledgment to the client.
8. The method of claim 5 , further comprising:
receiving a committed signal from the storage server, wherein the storage server is operable to transmit the committed signal after the time-stamped write request has been promoted from the future buffer to the re-order buffer; and
responsive to receiving a committed signal from all storage servers in the cluster, sending a write acknowledgment to the client.
9. The method of claim 1 , wherein a timestamp for the time-stamped write request comprises a time indication derived from a current time signal output from a time source, wherein the time source is selected from a group consisting of: Network Time Protocol (NTP) clocks, Precision Time Protocol (PTP) blocks, GPS receivers, traditional atomic clocks, or single-chip, atomic-clock-quality frequency generators.
10. A non-transitory computer-readable storage medium having stored thereon, computer executable instructions that, if executed by a proxy server cause the proxy server to perform a method for performing a write operation in a distributed storage system, the method comprising:
receiving a write request from a client at the proxy server, wherein the proxy server is disposed between one or more clients and one or more storage servers as an intermediary, and wherein the proxy server is configured to receive read requests and write requests from the one or more clients and distribute the read requests and the write requests to the one or more storage servers;
augmenting the write request with a timestamp:
responsive to a determination that the time-stamped write request has been retried over a threshold number of times, changing a status for the timestamped write request to a future write and adding a first offset to the timestamp for the time-stamped write request, wherein the proxy server is configured to augment the time-stamped write request with a status indication indicating that the time-stamped write request comprises a future write;
transmitting the time-stamped write request to a storage server of the one or more storage servers, wherein the storage server comprises a reorder buffer and a future buffer, wherein the re-order buffer is a timestamp ordered data structure for holding the read requests and the write requests while timestamps associated therewith are examined, wherein the reorder buffer maintains a time window comprising an interval of time from a current time into a past and an interval of time into a future from the current time, and wherein the future buffer starts a time window at a future time where the time window of the reorder buffer ends;
receiving an accept from the storage server responsive to a determination at the storage server that the timestamp including the first offset associated with the time-stamped write request is within the time window of the future buffer, wherein the accept originates from the storage server in response to the storage server inserting the time-stamped write request into the future buffer.
11. The non-transitory computer-readable medium as described in claim 10 , wherein first offset is equal to at least a duration of the time window of the reorder buffer.
12. The non-transitory computer-readable medium as described in claim 10 , wherein the method further comprises:
receiving a reject from the storage server, responsive to a determination at the storage server that the time-stamped write request is not within the time window of the reorder buffer;
sending an abort to all storage servers in a cluster receiving the time-stamped write request; and
re-trying the time-stamped write request with a second offset, wherein the second offset is larger than the first offset.
13. The non-transitory computer-readable medium as described in claim 10 , wherein the method further comprises: responsive to receiving an accept from all storage servers in a cluster receiving the time-stamped write request, sending a commit to the storage server, wherein the storage server is operable to mark the time-stamped write request in the future buffer as committed, wherein the time-stamped write request has not yet been promoted to the reorder buffer.
14. The non-transitory computer-readable medium as described in claim 10 , wherein the method further comprises:
responsive to receiving an accept from all storage servers in a cluster receiving the time-stamped write request, sending a commit to the storage server, wherein the storage server is operable to mark the time-stamped write request in the reorder buffer as committed and, wherein further the time-stamped write request has been promoted to the reorder buffer.
15. The non-transitory computer-readable medium as described in claim 10 , wherein the method further comprises:
responsive to receiving a reject from any one of the storage servers in a cluster receiving the time-stamped write request, sending an abort signal to the storage server, wherein the storage server is operable to delete the time-stamped write request from the future buffer if the time-stamped write request has not yet been promoted to the reorder buffer or from the reorder buffer if the time-stamped write request has been promoted to the reorder buffer.
16. The non-transitory computer-readable medium as described in claim 10 , wherein a timestamp for the time-stamped write request comprises a time indication derived from a current time signal output from a time source, wherein the time source is selected from a group consisting of: Network Time Protocol (NTP) clocks, Precision Time Protocol (PTP) blocks, GPS receivers, traditional atomic clocks, or single-chip, atomic-clock-quality frequency generators.
17. A proxy server for performing a write operation in a distributed storage system, said proxy server comprising:
a memory comprising instructions for a protocol to perform a write operation;
a communicative interface operable to allow communication between a plurality of storage servers and a plurality of clients, wherein the proxy server is disposed between the plurality of storage servers and the plurality of clients as an intermediary;
a controller comprising a processor, wherein the processor is coupled to the memory and the communicative interface, and wherein the processor is configured to:
receive a write request from a client; augment the write request with a timestamp:
responsive to a determination that the time-stamped write request has been retried over a threshold number of times, change a status for the timestamped write request to a future write and adding a first offset to the timestamp for the time-stamped write request, wherein the proxy server is configured to augment the time-stamped write request with a status indication indicating that the time-stamped write request comprises a future write;
transmit the time-stamped write request to a storage server comprising a reorder buffer and a future buffer, wherein the re-order buffer is a timestamp ordered data structure for holding the read requests and the write requests while timestamps associated therewith are examined, wherein the reorder buffer comprises a time window comprising an interval of time into a past from a current time and an interval of time into a future from the current time, and wherein a time window of the future buffer starts at a future time where the time window of the reorder buffer ends;
receive an accept from the storage server responsive to a determination at the storage server that the timestamp including the first offset associated with the timestamped write request is within a time window of the future buffer, wherein the accept originates from the storage server in response to the storage server inserting the time-stamped write request into the future buffer.
18. The proxy server described in claim 17 , wherein the first offset is equal to at least a duration of the time window of the reorder buffer.
19. The proxy server as described in claim 17 , wherein the processor is further configured to:
receive a reject from the storage server responsive to a determination at the storage server that the time-stamped write request is not within the time window of the reorder buffer;
send an abort to all storage servers in a cluster receiving the time-stamped write request; and
re-try the time-stamped write request with a second offset, wherein the second offset is larger than the first offset.
20. The proxy server as described in claim 17 , wherein the processor is further configured to:
send a commit to the storage server responsive to receiving an accept from all storage servers in a cluster receiving the time-stamped write request, wherein the storage server is operable to mark the time-stamped write request in the future buffer as committed, wherein the time-stamped write request has not yet been promoted to the reorder buffer.