Future write in distributed system maintaining data storage integrity

Abstract

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.

What is claimed is: 
     
         1 . A method for performing a write operation in a distributed storage system, the method comprising:
 receiving a time-stamped write request from a client at a proxy server;   responsive to a determination that the time-stamped write request has been retried over a threshold number of times, setting a status for the time-stamped rite request as a future write and adding a first offset to a timestamp of the time-stamped write request;   transmitting the time-stamped write request to a storage server comprising a reorder buffer and a future buffer, 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 from the storage server, responsive to a determination at the storage server that 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 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 time-stamped write request from a client;   responsive to a determination that the time-stamped write request has been retried over a threshold number of times, changing a status for the time-stamped write request to a future write and adding a first offset to a timestamp for the time-stamped write request;   transmitting the time-stamped write request to a storage server comprising a reorder buffer and a future buffer, 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 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 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 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 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 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 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 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;   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 time-stamped write request from a client; 
 responsive to a determination that the time-stamped write request has been retried over a threshold number of times, change a status for the time-stamped write request to a future write and adding a first offset to a timestamp for the time-stamped write request; 
 transmit the time-stamped write request to a storage server comprising a reorder buffer and a future buffer, 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 time-stamped 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.