KEY VALUE SSD

• US 20200133770A1
• Filed: 12/24/2019
• Published: 04/30/2020
• Est. Priority Date: 03/20/2017
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ki, Yang Seok
• Granted Patent: US 11,288,119 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: G11C 7/24 Memory cell safety or protection circuits, e.g. arrangements for preventing inadvertent reading or writing; Status cells; Test cells
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

A storage device includes: a plurality of memory devices configured as a virtual device utilizing stateless data protection; and a virtual device layer configured to manage the virtual device to store objects by applying a first data protection to some of the objects and a second data protection to other ones of the objects depending on respective sizes of the objects.

Claims

1. A storage device comprising:

a plurality of memory devices, each of the memory devices being configured as a virtual device and having a minimum size value allowable, which is the minimum object size that the memory device is configured to store; and

a virtual device layer configured to manage the virtual device to store an object by applying one of a first data protection and a second data protection to the object, based, at least in part, on the size of the object,

wherein the virtual device layer is configured to;

apply the first data protection to the object based on a space overhead of the first data protection for the object being less than a space overhead of the second data protection for the object;

apply the second data protection to the object based on the space overhead of the first data protection for the object being greater than the space overhead of the second data protection for the object.

2. The storage device of claim 1, wherein the virtual device layer is configured to:

apply one of the first data protection or the second data protection to the object when the space overhead of the first data protection for the object is equivalent to the space overhead of the second data protection for the object.

3. The storage device of claim 1, wherein the memory devices are configured as one or more data devices and one or more parity devices.

4. The storage device of claim 3, wherein the parity devices are a fixed subset of the memory devices.

5. The storage device of claim 3, wherein the parity devices comprise a changing subset of the memory devices, and wherein each of the plurality of memory devices is configured to operate as both a data device and as a parity device.

6. The storage device of claim 1, wherein the first data protection comprises erasure coding and the second data protection comprises replication.

7. The storage device of claim 6, wherein the space overhead of the erasure coding for the object is less than that of the replication for the object when ((P+1)*O>

(S+P)*m AND O>

=S*m), wherein O refers to an object size;

P refers to a number of parity devices;

S refers to a number of data devices; and

m refers to a maximum value of the minimum size value allowable from among the respective minimum size value allowable of the plurality of memory devices.

8. The storage device of claim 6, wherein the space overhead of the replication for the object is less than that of the erasure coding for the object when ((P+1)*O=<

(S+P)*m)), wherein O refers to an object size;

P refers to a number of parity devices;

S refers to a number of data devices; and

m refers to a maximum value of the minimum size value allowable from among the respective minimum size value allowable of the plurality of memory devices.

9. The storage device of claim 6, wherein when the space overhead of the erasure coding for the object is equivalent to the space overhead of the replication for the object, either the first data protection or the second data protection is utilized for data protection based on one or more of space available on the plurality of memory devices, access time for the object when stored on the virtual device, and how frequently the object is accessed.

10. The storage device of claim 6, wherein the space overhead of the erasure coding for the object is equivalent to the space overhead of the replication for the object when ((P+1)*O>

(S+P)*m)>

S*m>

O), wherein O refers to an object size;

P refers to a number of parity devices;

S refers to a number of data devices; and

m refers to a maximum value of the minimum size value allowable from among the respective minimum size value allowable of the plurality of memory devices.

11. The storage device of claim 1, wherein the memory devices comprise solid state drives.

12. A method of utilizing a virtual device layer to store objects in a virtual device comprising a plurality of memory devices, each of the memory devices having a minimum size value allowable, which is the minimum object size that the memory device is configured to store, the method comprising:

receiving by the virtual device layer an object to be stored;

determining by the virtual device layer a space overhead for either erasure coding or replicating the object for storage based on O, P, S and m,

wherein O refers to the object size, P refers to a number of parity devices, S refers to a number of data devices, and m refers to a maximum value of the minimum size value allowable from among the respective minimum size value allowable of the plurality of memory devices;

when the space overhead of the erasure coding for the object is less than the space overhead of the replication for the object;

determining a chunk size for the erasure coding and an amount of padding of a data chunk of the object;

partitioning the object into a plurality of data chunks each having the chunk size for the erasure coding;

calculating P parity chunks using the erasure coding;

determining the memory devices to store the data and parity chunks; and

writing the data and parity chunks to the memory devices, and

when the space overhead of the erasure coding for the object is greater than the space overhead of the replication for the object;

determining the memory devices for data and replicas; and

writing the data and the replicas to the memory devices.

13. The method of claim 12, wherein, when the space overhead of the erasure coding for the object is equivalent to the space overhead of the replication for the object, the replication or the erasure coding is applied based on one or more of space available on the plurality of memory devices, access time for the object when stored on the virtual device, and how frequently the object is accessed.

14. The method of claim 12, wherein the parity chunks corresponding to the object are stored on a fixed subset of the memory devices.

15. The method of claim 12, wherein the parity chunks corresponding to the object are stored on a variable subset of the memory devices.

16. The method of claim 12, wherein the data and the replicas corresponding to the object are stored on different ones of the memory devices.

17. The method of claim 12, wherein at least one of the data chunks is padded with zeros.

18. A method of reading an object, wherein the object has a space overhead for a first data protection and a space overhead for a second data protection based on O, P, S, and m, with a key by a virtual device layer from a virtual device comprising a plurality of memory devices, each of the memory devices having a minimum size value allowable, which is the minimum object size that the memory device is configured to store, wherein 0 refers to the object size, P refers to a number of parity devices, S refers to a number of data devices, and m refers to a maximum value of the minimum size value allowable from among the respective minimum size value allowable of the plurality of memory devices, the method comprising:

receiving by the virtual device layer a key corresponding to a data read request;

sending by the virtual device layer to all of the memory devices a request to read; and

receiving by the virtual device layer responses from the memory devices, wherein

when a space overhead of the first data protection for the object is less than or equal to a space overhead of the second data protection for the object, a data chunk and a parity chunk are received by the virtual device layer to rebuild the object utilizing the first data protection, and

when the space overhead of the first data protection for the object is greater than the space overhead of the second data protection for the object, the received response is the object or is a replica of the object.

19. The method of claim 18, wherein the first data protection comprises erasure coding and the second data protection comprises replication.

20. The method of claim 18, wherein the key comprises a hash(key) for determining a start device or a primary device from among the plurality of devices.

21. A storage device comprising:

a plurality of memory devices, each of the memory devices being configured as a virtual device and having a minimum size value allowable, which is the minimum object size that the memory device is configured to store; and

a virtual device layer configured to manage the virtual device to store a first object and a second object, wherein the first object is larger than the second object, by applying one of a first data protection and a second data protection to each of the first object and the second object,

wherein the virtual device layer is configured to;

apply the first data protection to the first object; and

apply the second data protection to the second object.

22. The method of claim 21, wherein the virtual device layer is further configured to apply either the first data protection or the second data protection to a third object that is larger than the second object and smaller than the first object.