IO REDIRECTION METHODS WITH COST ESTIMATION

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 ).