Method and apparatus for low delay access to key-value based storage systems using FEC techniques

1. A method for use in a key-value based storage system, the method comprising:

dividing an object into K portions, where K is an integer;

selecting an erasure coding to apply to the K portions as a function of delay performance of the key-value based storage system including determining a number of parity blocks to generate to satisfy one or both of a delay target of putting the object into the key-value store and a delay target of subsequent read requests, where both delay targets are based on an offline performance simulation of delay performance when different numbers of parity blocks are used given the delay distributions obtained through measurements for different request types and object sizes;

applying the erasure coding to the K portions to create N blocks of data; and

sending the N blocks of data using separate transfers to the storage system.

2. The method defined in claim 1 further comprising:

measuring the delay performance of putting objects to and getting objects from the storage system; and

creating the offline performance simulation based on results of measuring the delay performance.

3. The method defined in claim 1 wherein selecting the erasure coding to apply is based on a cumulative distribution function of the delay performance.

4. The method defined in claim 1 wherein selecting the erasure coding to apply is based on the delay performance associated with the operation to be performed.

5. The method defined in claim 1 wherein selecting the erasure coding to apply is based on the object's size.

6. The method defined in claim 1 wherein the erasure coding comprises forward error correction (FEC) coding.

7. The method defined in claim 1 wherein sending the N blocks of data over distinct connections to the storage system comprises sending at least two of the N blocks in parallel over two of the distinct connections.

8. The method defined in claim 1 further comprising:

assigning a distinct key to each of the K portions;

assigning a distinct key to each of N blocks of data resulting from applying the erasure coding to the K portions;

ordering the keys assigned to the K portions and the keys assigned to the N blocks; and

wherein sending the N blocks of data using N separate transfers to the storage system comprises sending all N blocks in parallel on separate connections to the key-value store, including cancelling any of the N separate transfers that haven't been completed successfully after K of the N separate transfers have completed successfully.

9. The method defined in claim 1 further comprising:

generating a plurality of individual requests, each request for requesting one of the N blocks of data from storage;

applying erasure decoding as each of N blocks are received;

cancelling N−K requests that remain outstanding after receiving K out of N blocks; and

returning the object to a requester.

10. The method defined in claim 1 wherein N is the number of available threads.

11. The method defined in claim 1 wherein the separate transfers comprise a combination of parallel and serial transfers.

12. The method defined in claim 1 further comprising cancelling any of the N separate transfers that haven't been completed successfully after K of the N separate transfers have completed successfully.

13. An apparatus for use in a key-value based storage system, the apparatus comprising:

a communication interface for coupling to a network, the communication interface operable to receive an object from the network;

a memory coupled to the communication interface to store the object; and

a processor coupled to the memory and the communication interface, the processor operable to

divide the object into K portions, where K is an integer,

select an erasure coding to apply to the K portions as a function of delay performance of the key-value based storage system, by, at least in part, determining a number of parity blocks to generate to satisfy one or both of a delay target of putting the object into the key-value store and a delay target of subsequent read requests, where both delay targets are based on an offline performance simulation of delay performance when different numbers of parity blocks are used given the delay distributions obtained through measurements for different request types and object sizes; and

apply the erasure coding to the K portions to create N blocks of data; and wherein the processor operates with the communication interface to send the N blocks of data using separate transfers to the storage system.

14. The apparatus defined in claim 13 wherein the processor further operable to:

measure the delay performance of putting objects to and getting objects from the storage system; and

create the offline performance simulation based on results of measuring the delay performance.

15. The apparatus defined in claim 13 wherein the processor selects the erasure coding to apply based on a cumulative distribution function of the delay performance.

16. The apparatus defined in claim 13 wherein the processor selects the erasure coding to apply based on the delay performance associated with the operation to be performed.

17. The apparatus defined in claim 13 wherein the processor selects the erasure coding to apply based on the object's size.

18. The apparatus defined in claim 13 wherein the erasure coding comprises forward error correction (FEC) coding.

19. The apparatus defined in claim 13 wherein the communication interface sends the at least two of the N blocks in parallel over two of the distinct connections.

20. The apparatus defined in claim 13 wherein the processor is further operable to:

assign a distinct key to each of the K portions;

assign a distinct key to each of N blocks of data resulting from applying the erasure coding to the K portions;

order the keys assigned to the K portions and the keys assigned to the N blocks; and

wherein the communication interface sends the N blocks of data using N separate transfers in parallel on separate connections to the key-value store, and cancels any of the N separate transfers that haven't been completed successfully after K of the N separate transfers have completed successfully.

21. The apparatus defined in claim 13 wherein the processor is further operable to:

generate a plurality of individual requests, each request for requesting one of the N blocks of data from storage;

apply erasure decoding as each of N blocks are received;

cancel N−K requests that remain outstanding after receiving K out of N blocks; and

return the object to a requester.

22. An article of manufacture having one or more non-transitory computer readable storage media storing instructions which, when executed by a system, causes the system to perform a method comprising:

dividing an object into K portions, where K is an integer;

selecting an erasure coding to apply to the K portions as a function of delay performance of a key-value based storage system, including determining a number of parity blocks to generate to satisfy one or both of a delay target of putting the object into the key-value store and a delay target of subsequent read requests, where both delay targets are based on an offline performance simulation of delay performance when different numbers of parity blocks are used given the delay distributions obtained through measurements for different request types and object sizes;

applying the erasure coding to the K portions to create N blocks of data; and

sending the N blocks of data using separate transfers to the storage system.

23. The article of manufacture defined in claim 22 further comprising:

measuring the delay performance of putting objects to and getting objects from the storage system; and

creating the offline performance simulation based on results of measuring the delay performance.

24. The article of manufacture defined in claim 22 wherein selecting the erasure coding to apply is based on a cumulative distribution function of the delay performance.