METHOD AND APPARATUS FOR LOW DELAY ACCESS TO KEY-VALUE BASED STORAGE SYSTEMS USING FEC TECHNIQUES

• US 20150149870A1
• Filed: 03/13/2013
• Published: 05/28/2015
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Kozat, Ulas C.
• Granted Patent: US 9,426,517 B2
• Time in Patent Office: Days
• US Class Current: 714/772
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0048 in conjunction with detection of multiuser or interfering signals, e.g. iteration between CDMA or MIMO detector and FEC decoder for spatial equalizer H04L25/03286
• CPC Class Codes: H04N 21/4334 Recording operations recording of a television signal H04N5/76; arrangements for recording or accumulating broadcast information or broadcast-related information H04H60/27
• CPC Class Codes: H04N 21/4408 involving video stream encryption, e.g. re-encrypting a decrypted video stream for redistribution in a home network

Abstract

A method and apparatus is disclosed herein for low delay access to key-value based storage systems. In one embodiment, the method for putting data into a key-value store comprising dividing the data 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 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; sending the N write requests to write blocks of data to the storage system, where each block is assigned a unique key in the key-value store.

Claims

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.

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

dividing each of a plurality of objects into a plurality of portions, wherein each of the plurality of objects is associated with a delay target;

applying erasure coding to the plurality of portions of each of the plurality of objects, including adapting the erasure coding in order to apply a different erasure coding to at least two objects of the plurality of objects based on differences between delay targets associated with the at least two objects; and

sending erasure coded data that resulted from applying the erasure coding to portions of the plurality of objects to the storage system.