Io redirection methods with cost estimation

Abstract

A distributed storage system node ( 125, 130, 135 ) is disclosed. The distributed storage system node ( 125, 130, 135 ) may include at least one storage device ( 140, 145, 150, 155, 160, 165, 225, 230 ), which may act as the primary replica ( 2315 ) for data subject to an Input/Output (I/O) request ( 905 ). A cost analyzer ( 2310 ) may calculate a local estimated time required ( 3305 ) to complete the I/O request ( 905 ) at the primary replica, and a remote estimated time required ( 3710 ) to complete the I/O request ( 905 ) at a secondary replica ( 2320, 2325 ) of the data. An I/O redirector ( 215 ) may direct the I/O request ( 905 ) to either the primary replica ( 2315 ) or the secondary replica ( 2320, 2325 ) based on the local estimated time required ( 3305 ) and the one remote estimated time required ( 3710 ).

What is claimed is: 
     
         1 . A distributed storage system node ( 125 ,  130 ,  135 ), comprising:
 at least one storage device ( 140 ,  145 ,  150 ,  155 ,  160 ,  165 ,  225 ,  230 ), the at least one storage device ( 140 ,  145 ,  150 ,  155 ,  160 ,  165 ,  225 ,  230 ) including a primary replica ( 2315 ) of data;   a cost analyzer ( 2310 ) to calculate a local estimated time required ( 3305 ) to complete an Input/Output (I/O) request ( 905 ) at the primary replica ( 2315 ) and at least one remote estimated time required ( 3710 ) to complete the I/O request ( 905 ) at least one secondary replica ( 2320 ,  2325 ) of the data; and   an I/O redirector ( 215 ) to direct the I/O request ( 905 ) to one of the primary replica ( 2315 ) and the at least one secondary replica ( 2320 ,  2325 ) responsive to the local estimated time required ( 3305 ) and the at least one remote estimated time required ( 3710 ).   
     
     
         2 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 1 , wherein the distributed storage system node ( 125 ,  130 ,  135 ) is drawn from a set including a Network Attached Solid State Drive (SSD) and an Ethernet SSD. 
     
     
         3 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 1 , wherein the I/O redirector ( 215 ) is operative to redirect the I/O request ( 905 ) only if the at least one storage device ( 140 ,  145 ,  150 ,  155 ,  160 ,  165 ,  225 ,  230 ) is currently undergoing garbage collection. 
     
     
         4 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 3 , wherein:
 the cost analyzer ( 2310 ) includes a local time estimator ( 2405 ) to calculate the local estimated time required ( 3305 ) to process the I/O request ( 905 ) at the primary replica ( 2315 ); and   the I/O redirector ( 215 ) includes:
 storage ( 2505 ) for a threshold time ( 2525 ); and 
 a first comparator ( 2510 ) to compare the local estimated time required ( 3305 ) with the threshold time ( 2525 ). 
   
     
     
         5 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 4 , wherein the local time estimator ( 2405 ) includes:
 a local garbage collection time calculator ( 2605 ) to calculate a local garbage collection time ( 2820 );   a local predicted garbage collection time calculator ( 2610 ) to calculate a local predicted garbage collection time ( 2905 );   storage ( 2620 ) for a local garbage collection weight ( 2635 ) and a predicted garbage collection weight ( 2640 ); and   a local estimated time required calculator ( 2625 ) to calculate a local estimated time required ( 3305 ) from the local garbage collection time ( 2820 ), the local predicted garbage collection time ( 2905 ), the local garbage collection weight ( 2635 ), and the predicted garbage collection weight ( 2640 ).   
     
     
         6 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 5 , wherein:
 the cost analyzer ( 2310 ) further comprises:
 query logic ( 2415 ) to query the primary replica ( 2315 ) for an actual number of free pages ( 2805 ); and 
 reception logic ( 2420 ) to receive from the primary replica ( 2315 ) the actual number of free pages ( 2805 ); and 
   the local garbage collection time calculator ( 2605 ) is operative to calculate a difference by subtracting the actual number of free pages ( 2805 ) from a threshold number of free pages ( 2810 ) for the primary replica ( 2315 ) and to calculate the local garbage collection time ( 2820 ) by multiplying ( 4160 ) the difference by an local average garbage collection time ( 2815 ).   
     
     
         7 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 6 , wherein the local garbage collection time calculator ( 2605 ) is further operative to add a delay ( 2825 ) associated with Programming valid pages in each erase block to the local garbage collection time ( 2820 ). 
     
     
         8 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 5 , wherein the cost analyzer ( 2310 ) further includes:
 a database ( 2425 ) storing information including at least one of historical local garbage collection information ( 3105 ) for the primary replica ( 2315 ), a worst case estimate for local garbage collection ( 3110 ) on the primary replica ( 2315 ), an average case estimate for local garbage collection ( 3115 ) on the primary replica ( 2315 ), historical processing time information ( 3120 ) for the primary replica ( 2315 ), a worst case estimate for processing time ( 3125 ) on the primary replica ( 2315 ), and an average case estimate for processing time ( 3130 ) on the primary replica ( 2315 ); and   a local predictive analyzer ( 2430 ) to calculate a predicted local time ( 3205 ) for the primary replica ( 2315 ) from the information stored in the database ( 2425 ).   
     
     
         9 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 4 , wherein:
 the cost analyzer ( 2310 ) further includes a remote time estimator ( 2410 ) to calculate the at least one remote estimated time required ( 3710 ) to process the I/O request ( 905 ) at the at least one secondary replica ( 2320 ,  2325 ); and   the I/O redirector ( 215 ) further includes:
 a second comparator ( 2515 ) to compare the local estimated time required ( 3305 ) with the at least one remote estimated time required ( 3710 ); and 
 a selector ( 2520 ) to select one of the primary replica ( 2315 ) and the at least one secondary replica ( 2320 ,  2325 ) to process the I/O request ( 905 ) with a minimum time from the local estimated time required ( 3305 ) and the at least one remote estimated time required ( 3710 ). 
   
     
     
         10 . A distributed storage system node ( 125 ,  130 ,  135 ) according to  claim 9 , wherein the remote time estimator ( 2410 ) includes:
 a communication time calculator ( 2705 ) to calculate a communication time ( 3410 ) between the distributed storage system node ( 125 ,  130 ,  135 ) and at least one secondary storage system node ( 125 ,  130 ,  135 ) including the at least one secondary replica ( 2320 ,  2325 );   a remote processor time calculator ( 2710 ) to calculate a remote processor time ( 3515 ) for the at least one secondary storage system node ( 125 ,  130 ,  135 );   a remote garbage collection time calculator ( 2715 ) to calculate a remote garbage collection time ( 3705 ) for the at least one secondary replica ( 2320 ,  2325 );   storage ( 2720 ) for a communication time weight ( 2735 ), a remote processor time weight ( 2740 ), and a remote garbage collection time weight ( 2745 ); and   a remote estimated time required calculator ( 2725 ) to calculate the remote estimated time required ( 3710 ) from the communication time ( 3410 ), the remote processor time ( 3515 ), the remote garbage collection time ( 3705 ), the communication time weight ( 2735 ), the remote processor time weight ( 2740 ), and the remote garbage collection time weight ( 2745 ).   
     
     
         11 . A cost analyzer ( 2310 ), comprising:
 a local time estimator ( 2405 ) to calculate the local estimated time required ( 3305 ) to process an Input/Output (I/O) request ( 905 ) at a primary replica ( 2315 ) of data, the primary replica ( 2315 ) included on a storage device ( 140 ,  145 ,  150 ,  155 ,  160 ,  165 ,  225 ,  230 ); and   a remote time estimator ( 2410 ) to calculate at least one remote estimated time required ( 3710 ) to process the I/O request ( 905 ) at at least one secondary replica ( 2320 ,  2325 ) of the data,   wherein the cost analyzer ( 2310 ) enables an I/O redirector ( 215 ) to direct the I/O request ( 905 ) to one of the primary replica ( 2315 ) and the at least one secondary replica ( 2320 ,  2325 ) responsive to the local estimated time required ( 3305 ) and the at least one remote estimated time required ( 3710 ).   
     
     
         12 . A cost analyzer ( 2310 ) according to  claim 11 , wherein the cost analyzer ( 2310 ) is activated only if the primary replica ( 2315 ) is performing garbage collection. 
     
     
         13 . A cost analyzer ( 2310 ) according to  claim 12 , wherein the remote time estimator ( 2410 ) includes:
 a communication time calculator ( 2705 ) to calculate a communication time ( 3410 ) between the distributed storage system node ( 125 ,  130 ,  135 ) and at least one secondary storage system node ( 125 ,  130 ,  135 ) including the at least one secondary replica ( 2320 ,  2325 );   a remote processor time calculator ( 2710 ) to calculate a remote processor time ( 3515 ) for the at least one secondary storage system node ( 125 ,  130 ,  135 );   a remote garbage collection time calculator ( 2715 ) to calculate a remote garbage collection time ( 3705 ) for the at least one secondary replica ( 2320 ,  2325 );   storage ( 2720 ) for a communication time weight ( 2735 ), a remote processor time weight ( 2740 ), and a remote garbage collection time weight ( 2745 ); and   a remote estimated time required calculator ( 2725 ) to calculate the remote estimated time required ( 3710 ) from the communication time ( 3410 ), the remote processor time ( 3515 ), the remote garbage collection time ( 3705 ), the communication time weight ( 2735 ), the remote processor time weight ( 2740 ), and the remote garbage collection time weight ( 2745 ).   
     
     
         14 . A cost analyzer ( 2310 ) according to  claim 13 , wherein the communication time calculator ( 2705 ) includes ping logic ( 3405 ) to ping the at least one secondary storage system node ( 125 ,  130 ,  135 ) to measure the communication time ( 3410 ). 
     
     
         15 . A cost analyzer ( 2310 ) according to  claim 13 , wherein:
 the cost analyzer ( 2310 ) further includes:
 query logic ( 2415 ) to query the at least one secondary storage system node ( 125 ,  130 ,  135 ) for a remote processor load ( 3505 ) on the at least one secondary storage system node ( 125 ,  130 ,  135 ); and 
 reception logic ( 2420 ) to receive from the at least one secondary storage system node ( 125 ,  130 ,  135 ) the remote processor load ( 3505 ); and 
   the remote processor time calculator ( 2710 ) is operative to calculate the remote processor time ( 3515 ) responsive to the remote processor load ( 3505 ).   
     
     
         16 . A cost analyzer ( 2310 ) according to  claim 15 , wherein:
 the query logic ( 2415 ) is operative to query the at least one secondary storage system node ( 125 ,  130 ,  135 ) for a remote software stack load ( 3510 ) on the at least one secondary storage system node ( 125 ,  130 ,  135 );   the reception logic ( 2420 ) is operative to receive from the at least one secondary storage system node ( 125 ,  130 ,  135 ) the remote software stack load ( 3510 ); and   the remote processor time calculator ( 2710 ) is operative to calculate the remote processor time ( 3515 ) responsive to the remote processor load ( 3505 ) and the remote software stack load ( 3510 ).   
     
     
         17 . A cost analyzer ( 2310 ) according to  claim 13 , further comprising:
 a database ( 2425 ) storing information including at least one of historical communication time information ( 3135 ) with the at least one secondary replica ( 2320 ,  2325 ), a worst case estimate ( 3140 ) for communication time ( 3410 ) with the at least one secondary replica ( 2320 ,  2325 ), an average case estimate ( 3145 ) for communication time ( 3410 ) with the at least one secondary replica ( 2320 ,  2325 ), historical remote processor time information ( 3150 ) for the at least one secondary replica ( 2320 ,  2325 ), a worst case estimate ( 3155 ) for remote processor time ( 3515 ) on the at least one secondary replica ( 2320 ,  2325 ), an average case estimate ( 3160 ) for remote processor time ( 3515 ) on the at least one secondary replica ( 2320 ,  2325 ), historical remote garbage collection information ( 3165 ) for the at least one secondary replica ( 2320 ,  2325 ), a worst case estimate for remote garbage collection ( 3170 ) on the at least one secondary replica ( 2320 ,  2325 ), and an average case estimate for remote garbage collection ( 3175 ) on the at least one secondary replica ( 2320 ,  2325 ); and   a remote predictive analyzer ( 2435 ) to calculate a predicted remote time ( 3605 ) for the at least one secondary replica ( 2320 ,  2325 ) from the information ( 3135 ,  3140 ,  3145 ,  3150 ,  3155 ,  3160 ,  3165 ,  3170 ,  3175 ) stored in the database ( 2425 ).   
     
     
         18 . A method, comprising:
 receiving ( 3905 ) at a distributed storage system node ( 125 ,  130 ,  135 ) an Input/Output (I/O) request ( 905 ), the I/O request ( 905 ) requesting data from a primary replica ( 2315 ) at the distributed storage system node ( 125 ,  130 ,  135 ), the primary replica ( 2315 ) including a storage device ( 140 ,  145 ,  150 ,  155 ,  160 ,  165 ,  225 ,  230 );   calculating ( 3920 ) a local estimated time required ( 3305 ) to complete the I/O request ( 905 );   calculating ( 3940 ) at least one remote estimated time required ( 3710 ) for at least one secondary replica ( 2320 ,  2325 ) storing the requested data;   comparing ( 3950 ) the local estimated time required ( 3305 ) with the at least one remote estimated time required ( 3710 );   selecting ( 3955 ) one of the primary replica ( 2315 ) and the at least one secondary replica ( 2320 ,  2325 ) responsive to the lowest of the local estimated time required ( 3305 ) and the at least one remote estimated time required ( 3710 ); and   directing ( 3960 ) the I/O request ( 905 ) to the selected one of the primary replica ( 2315 ) and the at least one secondary replica ( 2320 ,  2325 ).   
     
     
         19 . A method according to  claim 18 , wherein the distributed storage system node ( 125 ,  130 ,  135 ) is drawn from a set including a Network Attached Solid State Drive (SSD) and an Ethernet SSD. 
     
     
         20 . A method according to  claim 18 , further comprising performing ( 3910 ) the method only if the primary replica ( 2315 ) is performing garbage collection. 
     
     
         21 . A method according to  claim 20 , wherein calculating ( 3920 ) a local estimated time required ( 3305 ) to complete the I/O request ( 905 ) includes:
 calculating ( 4005 ) a local garbage collection time ( 2820 );   calculating ( 4010 ) a local predicted garbage collection time ( 2905 );   calculating ( 4030 ) the local estimated time required ( 3305 ) from the local garbage collection time ( 2820 ), the local predicted garbage collection time ( 2905 ), a local garbage collection weight ( 2635 ), and a predicted garbage collection weight ( 2640 ).   
     
     
         22 . A method according to  claim 20 , wherein calculating ( 3940 ) at least one remote estimated time required ( 3710 ) for at least one secondary replica ( 2320 ,  2325 ) storing the requested data includes:
 calculating ( 4505 ) a communication time ( 3410 ) for the at least one secondary replica ( 2320 ,  2325 );   calculating ( 4510 ) a remote processor time ( 3515 ) for the at least one secondary replica ( 2320 ,  2325 );   calculating ( 4515 ) a remote garbage collection time ( 3705 ) for the at least one secondary replica ( 2320 ,  2325 ); and   calculating ( 4530 ) the at least one remote estimated time required ( 3710 ) from the communication time ( 3410 ), the remote processor time ( 3515 ), the remote garbage collection time ( 3705 ), a communication time weight ( 2735 ), a remote processor time weight ( 2740 ), and a remote garbage collection time weight ( 2745 ).