System and method for storing very large key value objects

• US 10,552,062 B2
• Filed: 04/30/2018
• Issued: 02/04/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
• Primary Examiner(s): Tsui, Daniel D
• Application Number:
  US15/967,302
• Publication Number:
  US 20190114094A1
• Time in Patent Office: 645 Days
• 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/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A data storage system includes: a plurality of data storage devices for storing a plurality of objects of a key-value pair; and a virtual storage layer that applies different data reliability schemes including a data replication scheme and an erasure coding scheme based on a size of an object of the plurality of objects. The plurality of objects includes a first object having a first size and a second object having a second size that is larger than the first size. The virtual storage layer classifies the first object as a small object, applies the data replication scheme, and stores the small object across one or more of the plurality of data storage devices. The virtual storage layer classifies the second object as a huge object, splits the huge object into one or more chunks of a same size, applies the erasure encoding scheme, and distributedly stores the one or more chunks across the plurality of data storage devices.

Claims

1. A data storage system comprising:

a plurality of data storage devices for storing a plurality of objects of a key-value pair; and

a virtual storage layer that manages device drivers for controlling the plurality of data storage devices and applies different data reliability schemes including a data replication scheme and an erasure coding scheme based on a size of an object of the plurality of objects,

wherein the plurality of objects includes a first object having a first size and a second object having a second size that is larger than the first size,

wherein the virtual storage layer classifies the first object as a small object, applies the data replication scheme, and stores the small object across one or more of the plurality of data storage devices, and

wherein the virtual storage layer classifies the second object as a huge object, splits the huge object into one or more chunks of a same size, applies the erasure encoding scheme, and distributedly stores the one or more chunks across the plurality of data storage devices, and

wherein the virtual storage layer provides a virtual storage unit to an application running on a host computer by grouping one or more data storage devices among the plurality of data storage devices based on classification of the plurality of objects.

2. The data storage system of claim 1, wherein the distribution scheme is a split-first distribution in which the virtual storage layer stores splits the one or more chunks of the huge object to each of the plurality of data storage devices and stores the one more chunks in each of the one or more chunks across the plurality of data storage devices.

3. The data storage system of claim 1, wherein the distribution scheme is a band-first distribution scheme in which the virtual storage layer stores one chunk of the huge object to each of the plurality of data storage devices until the one or more chunks of the huge object is completely stored in the one or more data storage devices.

4. The data storage system of claim 1, wherein the virtual storage layer further classifies a third object having a third size as a large object, splits the large object into one or more chunks of a same size, applies the erasure encoding scheme, and distributedly stores the one or more chunks across the plurality of data storage devices, wherein the third size is larger than the first size and is smaller than the second size, and wherein the large object has only one band or only one chunk within a split.

5. The data storage system of claim 4, wherein the virtual storage layer further classifies a fourth object having a fourth size as a medium object, wherein the fourth size is larger than the first size and is smaller than the third size, and wherein the virtual storage layer applies one of the data replication scheme and the erasure coding scheme.

6. The data storage system of claim 1, wherein the object is identified with a user key, and the virtual storage layer creates an internal key including the user key and a band identifier for the huge object, wherein the band identifier is used to identify a band among a plurality of bands, and each of the band of the plurality of bands includes one chunk of the one or more chunks distributed across the plurality of data storage devices.

7. The data storage system of claim 6, wherein the virtual storage layer identifies a start data storage device among the plurality of data storage devices using a hash value of the user key for writing or reading a first chunk of the one or more chunks.

8. The data storage system of claim 1, wherein the plurality of data storage devices includes one or more dedicated parity data storage devices that store parity chunks associated with the huge object.

9. The data storage system of claim 6, wherein the plurality of data storage devices supports a group feature, and the virtual storage layer broadcasts to the plurality of data storage devices with the band identifier is set to bits of arbitrary data when reading the huge object.

10. The data storage system of claim 6, wherein the plurality of data storage devices does not support a group feature, and the virtual storage layer broadcasts to the plurality of data storage devices with the band identifier is set to a unique band identifier when reading the huge object.

11. The data storage system of claim 1, wherein each of the plurality of data storage devices is a key-value solid-state drive (KV SSD).

12. A method for writing an object of a key-value pair, the method comprising:

receiving a plurality of objects of a key-value pair, wherein the plurality of objects includes a first object having a first size and a second object having a second size that is larger than the first size;

classifying the first object as a small object;

applying a data replication scheme on the small object;

storing the small object across one or more of a plurality of data storage devices;

classifying the second object as a huge object;

splitting the huge object into one or more chunks of a same size;

applying an erasure coding scheme on the huge object; and

distributedly storing the one or more chunks across the plurality of data storage devices.

13. The method of claim 12, further comprising:

receiving a write request for the object;

determining that the object is the huge object;

determining a chunk size and a chunk count for the huge object; and

writing the one or more chunks of the huge object to the plurality of data storage devices based on the chunk size and the chunk count.

14. The method of claim 13, further comprising:

creating a slice that includes one chunk for each of the plurality of data storage devices among the one or more chunks and creating an internal key using a user key appended with a band identifier for each of the one more chunks included in the slice;

creating a band that includes one or more parity chunks and the one or more chunks corresponding to the slice using the erasure coding scheme;

determining the plurality of data storage devices to store the band based on a distribution scheme; and

writing the one or more chunks in the band with the internal key.

15. The method of claim 12, further comprising:

receiving a write request for the object;

determining that the object is the small object;

determining a subset of the plurality of data storage devices to store the one or more chunks of the small object based on a distribution scheme; and

writing the one or more chunks of the small object to the subset of the plurality of data storage devices.

16. The method of claim 14, further comprising:

receiving a read request for the object including the user key;

determining whether the plurality of data storage devices supports a group feature; and

broadcasting the read request with the internal key to the plurality of data storage devices.

17. The method of claim 16, wherein the band identifier of the internal key is set to bits of arbitrary data if the group feature is supported.

18. The method of claim 16, wherein the band identifier of the internal key is set to a unique band identifier if the group feature is not supported.

19. The method of claim 16, further comprising:

receiving at least one chunk from each of the plurality of data storage devices; and

reconstructing a slice from the at least one chunk received from the plurality of data storage devices using the erasure coding scheme.

20. The method of claim 12, wherein each of the plurality of data storage devices is a key-value solid-state drive (KV SSD).