Io redirection methods with cost estimation

Patent metadata

Field	Value
Publication number	US-2017123700-A1
Application number	US-201615336772-A
Country	US
Kind code	A1
Filing date	Oct 27, 2016
Priority date	Nov 3, 2015
Publication date	May 4, 2017
Grant date	—

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

First claim

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 analyz

Assignees

• Samsung Electronics Co Ltd

Inventors

• Sinha Vikas K
• Marripudi Gunneswara Rao
• Huo Jianjian
• Yagaty Ajit

Classifications

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/702

  Conservative garbage collection · CPC title