KR102460568B1 - System and method for storing large key value objects - Google Patents

Abstract

A data storage system according to an embodiment of the present invention includes a plurality of data storage devices for storing a plurality of objects of a key-value pair, and other data including a data replication method and an erasure coding method based on the object size of the plurality of objects. Includes a virtual storage layer that applies reliability schemes. The plurality of objects includes a first object having a first size and a second object having a second size greater than the first size. The virtual storage layer classifies the first object as a small object, applies a data replication method, and stores the small object through one or more of a plurality of data storage devices. The virtual storage layer classifies the second object as a large object, divides the large object into one or more chunks of the same size, applies an erasure coding scheme, and stores the one or more chunks through a plurality of data storage devices. distributed and stored

Description

SYSTEM AND METHOD FOR STORING LARGE KEY VALUE OBJECTS

The present invention relates to data storage systems, and more particularly, to a method of storing large key value objects in a data storage system.

Data reliability is a key requirement for data storage systems. Data reliability using conventional block devices has been implemented or studied through various data replication techniques such as erasure coding and RAID (Redundant Array of Independent Disks). RAID prevents permanent data loss on a particular drive by distributing (or duplicating) data over a set of data storage devices. RAID is largely classified into two categories. A complete mirror image of the data may be maintained on the second drive or parity blocks may be added as data to recover failed blocks in a fail situation. Erasure coding adds chunks of parity-like blocks using complex algorithms that provide robust data protection and recovery that can tolerate high levels of failing. For example, erasure coding can virtualize physical drives to create virtual drives that are more distributed than physical drives to achieve fast restores. Data replication using RAID is expensive to replicate large objects, and erasure coding can waste storage space for small objects.

Key-value solid-state drives (KV SSDs) have different interfaces and semantics ( It is a new form of storage with semantics. The KV SSD can directly store data values of key-value pairs. The data values stored in the KV SSD may appear large or small depending on the application and the characteristics of the data. There is a need for an efficient data reliability model that efficiently stores objects of different sizes without performance or space constraints.

According to an embodiment, the data storage system includes: a plurality of data storage devices storing a plurality of objects of a -value pair; and a virtual storage layer that applies other data reliability methods including a data replication method and an erasure coding method based on the object sizes of the plurality of objects, wherein the plurality of objects include a first object having a first size and the second object. a second object having a second size greater than one size, wherein the virtual storage layer classifies the first object as a small object, applies the data replication method, and converts the small object to the plurality of data storage devices storing through one or more of the above, the virtual storage layer classifies the second object as a large object, divides the large object into one or more chunks of the same size, and applies the erasure coding scheme and distributes and stores the one or more chunks through the plurality of data storage devices.

According to another embodiment, a method of writing an object of a key-value pair includes: receiving a plurality of objects of a key-value pair, wherein the plurality of objects include a first object having a first size and the first object a second object having a second size greater than the size; classifying the first object as a small object; applying a data replication method to the small object; storing the small object through one or more plurality of data storage devices; classifying the second object as a giant object; dividing the large object into one or more chunks of the same size; applying an erasure coding scheme to the large object; and distributing and storing the one or more chunks through the plurality of data storage devices.

The foregoing and other suitable features, including various novel descriptions of implementations and combinations of events, will be described in greater detail with reference to the accompanying drawings and will be referred to in the claims. The specific systems and methods described herein are shown for illustrative purposes only, and the present invention is not so limited. It will be understood by those skilled in the art that the theories and features described herein may be embodied in various embodiments without departing from the spirit of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings, which are included as part of the detailed description of the present invention, show suitable embodiments of the invention, such as the detailed description of suitable embodiments provided below for teaching and explaining the principles set forth in the general description and text set forth above.
1 shows a conceptual diagram of an object stored in an exemplary data storage device according to an embodiment.
2 shows an exemplary internal key including a user key according to an embodiment.
3 illustrates an example of object retrieval using a group feature, according to an embodiment.
4 illustrates an example of retrieving an object without a group feature, according to an embodiment.
5 shows an embodiment of erasure coding without a dedicated parity device according to an embodiment.
6 shows an embodiment of erasure coding using one or more dedicated parity devices according to an embodiment.
7 illustrates an exemplary replication method of a small object through one or more data storage devices without a parity device, according to an embodiment.
8 shows an exemplary flowchart of writing an object according to an embodiment.
9 shows an exemplary flowchart of reading an object according to an embodiment.
Throughout the drawings, for the sake of brevity, the drawings are not necessarily to scale, and elements of similar structures or functions are generally referred to by like reference numerals. The drawings are only intended to facilitate the description of the various embodiments described herein. The drawings do not depict all the spirits of the teachings described herein and do not limit the scope of the claims.

Each of the features and teachings described herein can be used individually or in conjunction with the other features and teachings to provide a data storage system that efficiently stores objects having different sizes and a method of storing objects in the data storage system. have. Representative embodiments using various additional features and teachings individually or in combination are described in greater detail with reference to the accompanying drawings. The detailed description is merely intended to enable those skilled in the art to practice the spirit of the present invention, and is not intended to limit the scope of the claims. Therefore, combinations of features described above in the detailed description may not be essential to the practice of the present invention in the broadest sense, but are described merely for describing specific representative embodiments of the present invention.

In the following description, simply for convenience of description, specific nomenclature is used to help the general understanding of the present invention. However, it will be understood by those skilled in the art that these detailed descriptions are not essential to implementing the teachings of the present invention.

Some of the detailed descriptions herein are presented as algorithms and symbolic representations of operations on bits of data within a computer memory. These algorithmic descriptions and representations are used by those skilled in the data processing arts to readily explain their work to others skilled in the art. An algorithm is expressed in the text and generally as a coherent sequence of steps leading to an intended result. Steps are steps in which physical quantities must be physically manipulated. Generally, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transmitted, combined, compared, and otherwise transformed. It has proven convenient, for reasons of common usage, to refer to these signals as bits, values, elements, symbols, features, terms, numbers, or the like.

However, all these and similar terms may be associated with the appropriate physical quantities, and are merely convenient labels applied to these quantities. As published in the description below, unless specifically stated otherwise, throughout the detailed description, "processing," "computing," "calculating," "determining," Descriptions using terms such as "displaying" and the like refer to data represented as physical (electronic) quantities in a computer system or registers and memories of a computer system in computer system memories or registers or other information storage. Refers to the operations and processes of similar electronic computing devices, transmission or display devices that transform and transmit other data similarly expressed in physical quantities.

Moreover, various features in the representative embodiments and the dependent claims may be combined in ways not specifically and explicitly listed to provide further useful embodiments of the invention. References to groups of objects or ranges of all values disclose all possible intermediate values or intermediate objects not only as originally described, but also for the purpose of limiting the claims. The shapes and areas of the configurations shown in the drawings are designed to aid understanding of how the present invention may be implemented, and are not intended to limit the areas and shapes shown in the embodiments.

The present invention shows a data storage system and method for storing large key-value objects in the data storage system. The data storage system of the present invention can store data having high reliability in one or more data storage devices. In particular, the data storage system of the present invention can store objects differently based on their sizes, thereby reducing cost and storage space and achieving high reliability. Data associated with a large object may be divided into small pieces and stored in one or more data storage devices. Here, when data stored in the data storage devices is a data array associated with key-value pairs, the data storage devices may be referred to as key-value solid state drives (KV SSDs).

An object (eg, a value of a key-value pair) may be split into chunks of the same size or multiple pieces. The size of the chunk may be dynamically determined in units of objects during run-time. Depending on its size, an object may contain chunks of different numbers and sizes.

A group is defined as a set of data storage devices for implementing target data rliability. A group may include one or more data storage devices in or through boxes (eg, a chassis or rack) and may be structured in a hierarchical or non-hierarchical manner.

The data storage system of the present invention includes a virtual storage layer that manages the grouping of one or more data storage devices and provides the group to user applications as a whole as a single virtual storage unit. A virtual storage layer may be used to manage a plurality of drivers that control one or more data storage devices. The number of data storage devices managed by the virtual storage layer may be configured based on a reliability target. For erasure coding, the total number of data storage devices may be the sum of data devices D and parity devices P to tolerate P failes. For replication, the total number of data storage devices tolerating P failures may be P+1. The storage capacity of data storage devices may be nearly similar in erasure coding or duplication. The storage capacity of the virtual storage may be determined by the sum of data storage spaces of all data storage devices in the group.

According to an embodiment, the virtual storage layer may manage a group of one or more data storage devices in a stateless manner. That is, the virtual storage layer does not or does not need to maintain any mapping information or key information between objects and data storage devices. However, the virtual storage layer may dynamically maintain and cache, at runtime, essential metadata of one or more data storage devices, such as number of objects, available storage capacity, and/or the like.

A data storage device, such as a KV SSD, includes implementation-specific restrictions on objects and operations on objects that can be managed. The virtual storage layer of the data storage system may recognize the minimum and maximum value sizes that each data storage device can support, and may determine the minimum and maximum value sizes.

For example, VMIN _i is the minimum value size of the i-th KV SSD. The minimum value size (VMIN_VS) of the virtual storage may be defined by the maximum value among all the minimum value sizes of individual KV SSDs in the group.

Similarly, VMAX _i is the maximum value size of the i-th KV SSD. The maximum value size of the virtual array (VMAX_VS) may be defined by the smallest value among all the maximum value sizes of individual KV SSDs in the group.

In an embodiment, a maximum distance separable (MDS) algorithm such as a Reed-Solomon (RS) code may be used for erasure coding.

According to an embodiment of the present invention, the system and method of the present invention provide a hybrid data reliability mechanism that affects both replication and erasure coding based on the size of an object. Data replication can be fast and lightweight for small objects. However, data replication may consume more storage space for large objects when compared to erasure coding. Erasure coding may consume less storage space than data duplication for large objects, and may restore these large objects by affecting multiple data storage devices. However, since it requires a plurality of chunks from a plurality of data storage devices, erasure coding generally involves excessive computation and can be time consuming to recover small objects. This is a non-hierarchical method of duplicating data after erasure coding is performed on the data. Instead, the systems and methods of the present invention provide a flexible decision between data replication and erasure coding based on the size of the object. In other words, the system and method of the present invention can determine to apply data duplication or erasure coding at run-time based on data reliability judgment, that is, not only the size of the object but also the burden of the total space to store the object.

According to one embodiment, the systems and methods of the present invention do not involve read-modify-write overhead when an object is updated. Conventional erasure coding or data duplication for block devices involves a lot of overhead when there is a partial update. If a small piece of data is updated, all of the blocks for erasure coding must be read and updated, and after the update the parity blocks must be recomputed and written back to the data storage devices. In other words, since a block can be shared with multiple objects, updating of an object requires a series of read-transform-write processes. In contrast, the systems and methods of the present invention can provide reliability based on an object and its characteristics, such as size. When an object is updated, only the updated object needs to be overwritten, without incurring a read-transform-write burden.

According to an embodiment of the present invention, the system and method of the present invention support a wide range of object sizes in a unified framework. If the object is very large (or huge), exceeding the storage capacity limit of the data storage device, the data storage device may not be able to store the object as a whole. In this case, the object needs to be divided into small pieces (referred to in the text as chunks). The detailed description of the present invention describes a method in which objects are partitioned into chunks based on the capacity of data storage devices, and rebuilt from the partitioned chunks. For example, the system and method of the present invention provide various partitioning and restoration mechanisms based on group feature support of data storage devices, as described in more detail below.

The systems and methods of the present invention provide for the reliability of objects that are not based on fixed blocks. Data duplication and erasure coding can be combined to implement target reliability of an object for a single disk group by bifurcating the objects based on their size. This approach differs from conventional data reliability techniques that include a hierarchical structure (ie, replication over erasure coded objects). The systems and methods of the present invention have space efficiency as a primary concern, and performance is a secondary factor for determining the appropriate reliability mechanism for a particular object. The storage of objects is stateless. No additional information needs to be stored for either replication or erasure coding. No read-transform-write burden is required for updates regardless of object size.

In this context, an object refers to static data having a fixed value during input and output (I/O) operations. An object may be associated with a key of a key-value pair. In this case, the object corresponds to the value of a key-value pair. The object may be divided into a plurality of chunks of the same size, and the size of the chunks may be determined based on a dynamic unit object at run-time. Each object, when stored in one or more data storage devices, may contain different numbers and sizes of chunks.

The minimal set of data chunks of an object that are all stored at once via one or more data storage devices (eg, KV SSDs) without data reliability is referred to herein as a slice. For example, a slice corresponds to the number of chunks of an object partitioned into one or more data storage devices. The minimum set of data chunks of an object that implements data reliability (eg, replication or erasure coding) is referred to as a "band." The number of chunks in a band may be greater than the number of chunks in a slice due to parity chunks. A set of chunks of an object stored on one of the one or more data storage devices in the group may be referred to as a split.

A slice can contain only one chunk (of the target object) for a data replica (ie, a duplicated copy of the original object). For erasure coding, a slice may contain D chunks containing a target object. On the other hand, a band may contain P replica chunks and one original chunk for data replication, or P parity chunks and D data chunks for erasure coding. The number of slices or bands corresponds to the total number of chunks in the split. The split size (ie, the number of chunks stored in one data device) and the band size (ie, the number of chunks stored in one or more data storage devices) may vary according to the size of the original object and the chunks. For example, the split size may be the original size for data duplication, but the split size is the chunk size multiplied by the number of chunks per band, for erasure coding.

1 shows a conceptual diagram of an object stored in an exemplary data storage system, according to an embodiment. The object 110 may be divided into a plurality of chunks. For example, the object 110 may be divided into 3S chunks (Chunk 1 to Chunk 3S) (where S is a natural number). The total number of chunks 3S is exemplary, and the total number of chunks of the object 110 may be another number, and the object 110 does not need to be divided by a multiple of three. Objects 110 may be classified as very large or huge objects, as described in detail below. The partitioned chunks may be distributed to virtual storage through one or more data storage devices. In an embodiment of the present invention, the virtual storage space includes D data storage devices (Disk 1 to Disk D) and P parity devices (Disk D+1 to Disk D+P). In an embodiment of the present invention, S and D are the same.

According to an embodiment, the virtual storage layer of the data storage system may distribute chunks in a split-first manner (split-first distribution) or in a band-first manner (band-first distribution). In the split-first scheme, the virtual storage layer stores chunks Chunk 1 , Chunk 2 , and Chunk 3 in the virtual storage 120 in the first data storage device Disk 1 , and stores chunks Chunk 4 , Chunks 5 and 6) are stored in the second data storage device (Disk 2), and similarly, chunks (Chunk 3D-2, Chunk 3D-1, and Chunk 3D) are stored in the D-th data storage device (Disk D). . The band 150 includes chunks (Chunk 1, Chunk 4, ..., Chunk 3D-2) and parity chunks (Parity 1 to Parity P). In the band-first method, the virtual storage layer stores chunks (Chunk 1 to Chunk D) in the data storage devices (Disk 1 to Disk D), respectively, in the virtual storage 121 , and chunks (Chunk D+). 1 to Chunk 2D) are stored in the data storage devices (Disk 1 to Disk D), respectively, and the chunks (Chunk 2D+1 to Chunk 3D) are respectively stored in the data storage devices (Disk 1 to Disk D), respectively. . The split 151 includes data chunks Chunk 1, Chunk D+1, and Chunk 2D+1. Parity chunks Parity 1 to Parity P are stored in parity disks Disk D+1 to Disk D+P. Although, for convenience of explanation, both virtual storage 120 and virtual storage 121 are shown as storing parity chunks in a band-first manner, the storage of parity chunks is split- It will be understood that this may be performed in a preferred manner.

I/O operations may be performed in a band-first manner regardless of which chunk distribution schemes are used. In this case, I/O operations for chunks (Chunk 1, Chunk 4, ..., Parity P) are stored in parallel even in the split-first scheme.

According to an embodiment, erasure coding is applied to the object based on the size of the object. For an ith object O _i having a size SZ _Oi , the number of chunks per device, ie, a split NC _Oi , is defined by Equation 3 below. For replication, the number of chunks per device may be 1 (ie, NC _Oi = 1).

The number of chunks per device (NC _Oi ) stores an object (O _i ) through data disks (ie, data storage devices referenced as Disk 1 to Disk D) when the maximum chunk size (VMAX _VS ) is used. The minimum number of chunks per split to When the object size is not aligned with the allocation or alignment unit of the data storage device, the additional space allocated for the object in the band may be padded with zeros.

If the maximum chunk size is used, storage space tends to be wasted using too much padding. Therefore, the actual chunk size of the object O _i is more strictly determined by Equation (4). SZ _meta is the metadata size when additional metadata is stored along with the data per chunk. When the data storage device supports the group feature, some metadata such as a group identifier (group ID) and the total number of chunks may be stored in each chunk. If the data storage devices do not support the group feature, no metadata is stored (ie, SZ _meta =0). For a clone, the actual chunk size may be equal to its original object size (ie C _Oi =SZ _Oi ).

Equation 4 determines the chunk size that is in the range between VMIN _VS and VMAX _VS but close to VMAX _VS . The chunk size determined by Equation 4 may minimize the number of I/O operations while maximizing I/O bandwidth. The total amount of data stored by each data storage device (ie, the split size) is defined by Equation (5).

Finally, the total amount of data written at one time through the data storage devices, ie, the band size, is defined by Equation (6). For replication, D equals 1.

As mentioned above, data storage devices have limitations on the size of objects that data storage devices can store. Some data storage devices may not support very large large objects or very small small objects. In order to achieve reliable and efficient storage of objects having different sizes, the data storage system of the present invention may apply different data reliability schemes based on the size of objects to be stored. According to an embodiment, the virtual storage layer of the data storage system of the present invention divides objects into four types, aka, huge, large, medium, and small based on the size of the objects. small). When multiple bands are used to store an object, the object is classified as large. An object is classified as large if one band is used almost entirely to store the object. An object is classified as small if a small fraction of the band is used to store the object. Finally, if an object can be classified as small or large, the object is classified as medium-sized. Therefore, chunks of different sizes can coexist in the same virtual storage as well as individual data storage devices forming the virtual storage.

If the spatial burden of replication on the object is less than that of erasure coding on the object, the object is classified as small. In this case, replication is appropriate because better performance is provided for reads and update management is easier than complex erasure coding schemes. This makes sense in situations where application metadata tends to be small. In an embodiment, the small object Oi having SZ _Oi satisfies Equation (7).

If the spatial burden of erasure coding on the object is less than the spatial burden of data replication on the object, the object is classified as large. In this case, erasure coding is appropriate because it has a smaller space. In particular, the large object satisfies Equation (8).

A large object may be configured similarly to FIG. 1 , but may include only one chunk or one band in a split.

An object is classified as large if it contains one or more chunks within a split. In this case, erasure coding is appropriate. In particular, the giant object satisfies Equation (9).

The large object may be configured similarly to FIG. 1 , but may include a plurality of chunks or a plurality of bands in a split.

There may be a range of object sizes that can be classified as either small or large. An object satisfying Equation 10 is classified as medium-sized.

In this case, either data duplication or erasure coding may be used. If performance is more important, and objects are updated frequently, data replication may be a better choice. In this case, medium-sized objects may be classified as small. When space efficiency is more important, erasure coding can be used. In this case, medium-sized objects may be classified as large.

The virtual storage layer may require partitioning the large object into small data chunks in order to store the object and retrieve the large object by using the partitioned data data chunks to restore the object. To this end, an internal key generated from a user's (eg, a user application running on a host computer) key may be used to create a virtual storage layer steerless. According to one embodiment, the virtual storage layer reserves several bytes of device-supported key space for internal use of distributing chunks, and presents the remainder of the key space to the user. In this case, the user-specific object key represents a group of internal keys for one or more partitioned chunks of the object.

2 shows an exemplary internal key including a user key, according to an embodiment. The inner key 200 includes a user key 201 of a first portion and a band identifier (ID) 202 of a second portion. The internal key 200 may be used to identify a portion of chunks or an entire group of chunks for a corresponding object. In this case, the object corresponds to the value of the key-value pair including the internal key 200 as the key of the key-value pair. In the current embodiment, the maximum key length supported by the virtual storage layer and/or data device is L, and the number of bytes reserved for group specification is G. The virtual storage layer advertises that the maximum key length the user can use is L-G.

For small or large objects, the band ID 202 of G bytes may be padded with zeros by default. For large objects, the virtual storage layer can compute the number of bands for the object. Individual bands can be identified using an internal key 201 . A band may be written to one or more data storage devices allocated to store objects one by one in a split-first or band-first manner.

According to an embodiment, the data storage device may support a group feature. The virtual storage layer may identify the split stored in the data storage device by specifying a group based on the user key 201 . In this case, additional metadata may not be required (SZ_meate=0). The virtual storage layer notifies all data storage devices of the band ID 202 and user key 201 filled with "don't care" bits (any data bits, eg 0xFF), so that the object is You can retrieve all the chunks for If the band ID is "don't care", the band ID field is ignored. It can be assumed that the data storage device effectively implements the group feature. For example, a trie structure can easily identify objects with a given predetermined prefix of the user key 201, whereas a hash table can only identify the user key if the metadata fields are fixed. can be used to find objects in a hash bucket. The virtual storage layer sorts the returned object chunks in ascending order based on the band ID 202 per device, reorganizes the bands and objects, and returns the objects with the user key 201 .

3 shows an example of object retrieval using a group feature, according to an embodiment. Each of the data storage devices allocated to store an object (ie, Disk 1 to Disk D, and Disk D+1 to Disk P) supports a group feature. In this case, the band ID 302 is set to "don't care," which is referred to as disregarding the band ID 302 . The virtual storage layer uses the user key 301 to collect chunks belonging to the band 350 (ie, data chunks 1, 2, ..., parity chunks 1 to P), and chunks from the band 350 . The first slice including (Chunk 1 ~ Chunk D) is reconstructed. After that, the virtual storage layer collects the remaining chunks and reconstructs the remaining slices in order. When all slices are configured, the virtual storage layer reconstructs the object 310 including data chunks Chunks 1 to 3D from the slices. In the case of erasure coding, the virtual storage layer further reconstructs parity block(s) from parity chunks 1 to P. Although the present embodiment shows a band-first approach for splitting chunks, it will be understood that the split-first approach may be applied to chunking and object retrieval without departing from the spirit of the present invention.

4 shows an example of object retrieval without a group feature, according to an embodiment. In this case, since the data storage devices allocated to store the object do not support the group feature, the virtual storage layer attaches additional metadata as a large or large object (ie, SZ_meta ≠ 0). Each chunk may be identified by a band ID 402 having a 1-byte length. In the current embodiment, three bands (Band 1, Band 2, and Band 3) may exist so that the number of bands can fit a 1-byte length. The virtual storage layer may configure the slices one by one using the band ID 402 . First, the virtual storage layer sends the user key 401 with a band ID equal to 0 (BID=0) to all data storage devices. The virtual storage layer receives chunks for band 0 (Band 0) from all data storage devices, and recovers band information from chunks belonging to band 0 among the received chunks. Based on the received band information, the virtual storage layer recognizes the number of bands and retrieves the object. If the object is large, there can be only one band, and the virtual storage layer can reconstruct the entire object from chunks in the band. If there are more than one chunk for a large object, the virtual storage layer needs to reclaim more bands (eg, Band 1 and Band 2) one by one. In this case, the virtual storage layer sends redemption requests by adjusting the band ID (eg, BID=1 or BID=2) until all chunks are reclaimed. When the virtual storage layer configures all slices, the virtual storage layer may reconstruct the object 410 . A small object may contain no metadata regardless of whether the devices support the group feature. By checking the chunk size, the virtual storage layer can determine whether the object 410 is small or not using equations (7) and (10).

To write a large object to one or more data storage devices, the large object may be divided into NC _Oi *D chunks of the same size (ie, NC _oi slices). The last data chunk (eg, data 4a of object 510a in FIG. 5 and data 4b of object 510b in FIG. 5 ) may be padded with 0 (zero) in consideration of arrangement requirements, and P parity Chunks may be created from D data chunks per slice.

5 shows an example of erasure coding without a dedicated parity device, according to an embodiment. 6 shows an example of erasure coding using one or more dedicated parity devices, according to an embodiment. All (D+P) chunks including D data chunks and P parity chunks for each band are distributed to one or more data storage devices to write all NC _Oi bands. Parity chunks may be distributed across D+P devices (eg, SSD4 to SSD6 in FIG. 5 ) or may be stored in P dedicated devices (eg, SSD5 and SSD6 in FIG. 6 ). The primary data storage device may be selected using a hash value of the user key (hereinafter referred to as a “Hash (user key)”) without a band ID on the data storage devices. All or part of (D+P) devices may be selected in the embodiment of FIG. 5 , and D devices may be selected in the embodiment of FIG. 6 . The starting device may be determined by Hash(user key)%(D+P) when there is no dedicated parity device, or by Hash(user key)%D when dedicated parity devices exist. Subsequent chunks are the following devices (eg (Hash(user key) + 1)%(D+P), (Hash(user key)+2)%(D+P), …(Hash(user key) +D+P-1)%(D+P) or (Hash(user key)+1)%D, (Hash(user key)+2)%D, …(Hash(user key)+D-1) %D) can be written sequentially. This operation is a per-band operation, and the virtual storage layer repeats this procedure for all NC _Oi bands to write chunks of the object. The hash value of the user key needs to be computed once for each object.

If the data storage devices do not support the group feature, the chunks contain additional metadata about the total number of bands and the band ID, as shown in FIG. 4 . The number of bands can be determined by Equation (3). Chunks of a band may include a pair of (band ID, NC _Oi ) as metadata.

Referring to FIG. 5 , the virtual storage layer stores the data chunks Data 1a to Data 4a and the patch key chunks Parity 1a and Parity 2a of the object 510a through the data storage devices SSD1 to SSD6. . The virtual storage layer stores data chunks (Data 1b to Data 4b) and patch key chunks (Parity 1b and Parity 2b) of another object 510b through data storage devices SSD1 to SSD6. The initiating device (eg, SSD1 for object 510a and SSD6 for object 510b) may be determined by the hash value of the user key, as described above. Since there is no dedicated parity device, the virtual storage layer may distribute the data chunks and the parity chunks to the data storage devices SSD1 to SSD6 without distinguishing between the data chunks and the parity chunks. In the current embodiment, SSD4 and SSD6 contain both data chunks and parity chunks.

Referring to FIG. 6 , the virtual storage layer stores data chunks Data 1a to Data 4a and parity chunks Parity 1a and Parity 2a of an object 610a through data storage devices SSD1 to SSD6. . Similarly, the virtual storage layer stores data chunks Data 1b to Data 4b and parity chunks Parity 1b and Parity 2b of the object 610b through the data storage devices SSD1 to SSD6. Since SSD5 and SSD6 are allocated as parity devices, SSD5 and SSD6 include only parity chunks.

To write a large object to one or more data storage devices, the large object may be divided into NC _Oi *D chunks of equal size. Large objects are managed similarly to large objects, except that there can be only one band for the object (ie, NC _Oi =1).

To store a small object, (P+1) duplicate objects can be created for the object. Considering alignment including padding, duplicate objects can be distributed among (P+1) devices. The primary device may be selected using the hash value of the user key, on (D+P) devices. P replica objects may be selected deterministically based on various factors such as storage organization, performance, etc. For example, duplicate objects are (Hash(key)+1)%(D+P), (Hash(key)+2)%(D+P), ... It can be simply stored in (Hash(key)+P)%(D+P) or in other nodes, racks, regardless of whether there is a dedicated parity device. If dedicated parity devices or nodes exist, duplicate objects are (Hash(key)+1)%D, (Hash(key)+2)%D, ... It can be stored in (Hash(key)+P)%D. Regardless of the device's capacity, small objects contain no metadata.

7 illustrates an exemplary replication method of a small object through one or more data storage devices without a parity device, according to an embodiment. The virtual storage layer may store the small object 710a (Object 1) through the data storage devices SSD1 , SSD2 , and SSD3 . The virtual storage layer may store small object 710b (Object 2) chunks through data storage devices SSD3, SSD4, and SSD5. Small objects 710a and 710b are not divided into smaller data chunks. The starting device for storing the objects 710a and 710b may be determined by the hash value of the corresponding user key. In the current embodiment, the starting device for the object 710a is SSD1, and the starting device for the object 710b is SSD3. In the current embodiment, the total number of duplicate objects for each of the objects 710a and 710b is 3 (ie, P=2).

8 shows an exemplary flowchart of writing an object, according to an embodiment. The virtual storage layer of the data storage system receives a write request to write an object ( 801 ). A write request received from a user (or a user application running on the host computer) may include a user key. The virtual storage layer determines (802) whether the object is large or large, eg, using equations (8) and (9). For large or large objects, the virtual storage layer determines (811) the chunk size and number of chunks per split and per band, e.g., using equations 3 and 4, one or Data is written ( 812 ) to the higher bands, and the write procedure is completed ( 815 ).

When the virtual storage layer determines that the objects are not large and not large, the virtual storage layer determines whether the objects are small, for example, using Equation 7 (803). For the small object, the virtual storage layer determines ( 813 ) one or more storage devices for storing data including original data and duplicate data based on a distribution policy, and one or more of the bands. Writes data through the devices (814) and completes the write procedure (815). For example, the virtual storage layer may use a band-first policy (distributing data across multiple data storage devices). The virtual storage layer can use the hash value of the user key to determine the originating device.

If the virtual storage layer determines that the object is not large, not large, and not small, the virtual storage layer treats the object as medium-sized (804) and includes original data and duplicate data based on the distribution policy. Determines one or more data storage devices for storing the data to be used (813), writes data to one or more devices of the band (814), and completes the write procedure (815).

The procedure 812 of writing data to one or more bands via data storage devices may include various sub-processes. First, the virtual storage layer determines whether a slice for writing exists ( 820 ). If the slice for writing does not exist, the virtual storage layer saves the error log, terminates the operation, and sends a request to write the object to the user application running on the host computer and/or the host computer's operating system. inform The virtual storage layer creates a slice for the object and generates internal keys for chunks of the slice ( 821 ). The virtual storage layer checks 822 if this is the last slice for writing. For the last slice, the virtual storage layer adds paddings to the data chunks if the slice cannot fill the band full, and computes P parity chunks for the band using an erasure coding algorithm (824). ). For slices other than the last slice, the virtual storage layer omits the padding procedure 823 . The virtual storage layer further determines devices for data and parity chunks based on the distribution policy (825). For example, the distribution policy may be either a split-first or a band-first policy. The virtual storage layer writes ( 826 ) data and parity chunks to one or more storage devices in a band along with the internal keys generated at 821 .

Because object metadata such as user key and value size is not maintained, the virtual storage layer cannot know whether the object being read is small, large, or large. Therefore, the virtual storage layer sends a read request to all data storage devices in the virtual storage (eg (D+P) data storage devices) using the user key of the object, and based on the classification of the object size, Determine the appropriate way to reconstruct the object. Depending on the group characteristics supported by the data storage devices, the virtual storage layer may handle read and write operations differently.

A large object may be read differently based on the support of the group feature by the data storage devices. If the data storage devices of the virtual storage support the group feature, the virtual storage layer sends the user key with BID="don't care" to all data storage devices. In response, each of the (D+P) data storage devices returns NC _Oi chunks of its split if there is no error responding to the transmission. Then, the virtual storage layer sorts the received chunks into total of NCOi bands per their band ID, and sorts the bands in ascending order of band ID. While the virtual storage layer receives D chunks of the same size for each band, the virtual storage layer can reconstruct the band. If the total number of received chunks for a band is less than the number D of data storage devices or the chunks are not the same size, an error occurs. When all storage devices return a NOT_EXIST error, an error may occur due to a read of non-existing object or an unrecoverable error. The virtual storage layer reconstructs the bands one by one, and then reconstructs the object from the bands.

If the data storage devices of the virtual storage do not support the group feature, the virtual storage layer sends the user key with BID=0 to all data storage devices to read the large object. In response, each of the (D+P) data storage devices returns one chunk in the first band (Band 0). The virtual storage layer may identify the number of bands for an object by checking the metadata stored along with some of the received chunks. The virtual storage layer then reconstructs all bands one by one in ascending order of band ID, and reconstructs the object using the bands. In some embodiments, the virtual storage layer may asynchronously request all of the remaining bands to reconstruct the object similar to the group supported case.

The read procedure of a large object may be similar to that of a large object, except for one band. If the data storage devices support the group feature, the virtual storage layer sends the user key with BID="don't care" to all data storage devices. In response, each of the (D+P) data storage devices returns one chunk in its split. While the virtual storage layer receives D chunks of the same size, the virtual storage layer may reconstruct the object. If the total number of received chunks for a band is less than the number D of data chunks or the size of the chunks is not the same, an error occurs. When all data storage devices return a NOT-EXIST error, an error may occur due to an unrecoverable error or read of a non-existing object.

If the data storage devices of the virtual storage device do not support the group feature, the virtual storage layer sends the user key with BID=0 to all data storage devices to read the large object. In response, each of the (D+P) data storage devices returns one chunk in the band (BID=0). The virtual storage layer can identify that there is only one band for a large object by checking the metadata stored with the received chunks, and reconstruct the object by reconstructing the band.

The procedure for reading a small object may be similar to that of reading a large object, except that it relies on replication. If the data storage devices support the group feature, the virtual storage layer sends the user key with BID="don't care" to all data storage devices. In response, each of the (D+P) data storage devices returns a response. Because the object is small, some data storage devices may return an error of NOT_EXIST, while others return chunks. The virtual storage layer receives valid chunks that can reconstruct an object using chunks received from one or more data storage devices. When all data storage devices return a NOT_EXIST error, the object identified by the read request may not exist or an unrecoverable error may occur.

If the data storage devices of the virtual storage do not provide the group feature, the virtual storage layer sends the user key with BID=0 to all data storage devices to read the small object. In response, each of the (D+P) data storage devices returns a response. The virtual storage layer may identify whether an object is small using any valid chunks received from which data storage device. Small objects do not maintain additional metadata.

9 shows an exemplary flowchart of reading an object, according to an embodiment. The virtual storage layer receives a read request for the object ( 901 ). A read request received from a user (or a user application running on a host computer) may include a user key. The virtual storage layer determines ( 902 ) whether the group feature is supported by one or more data storage devices that store one or more chunks of the object. If the group feature is supported, the virtual storage layer sends a read request to all data devices (903) with an internal key with BID="don't care"; otherwise, BID=0 to all data storage Set to devices (904). The virtual storage layer receives 905 a chunk from one of the data storage devices. If there are no errors in the received chunk (906), the virtual storage layer determines if the group feature is supported (907), retrieves the chunk's metadata (908), otherwise the virtual storage layer determines the size of the object continue to determine

When the virtual storage layer determines that the object is large or large ( 909 ), the virtual storage layer further checks whether the entire object has been reconstructed ( 910 ), and uses the chunks received from one or more data storage devices to It continues to reconstruct the slices one by one until the object is reconstructed (912), and the read procedure is completed (913). For a small object, the virtual storage layer reconstructs ( 911 ) the object using chunks received from one or more data storage devices.

The procedure 911 for reconstructing the small object may include a plurality of sub-procedures. The virtual storage layer first checks whether the received chunk is small (921). If the virtual storage layer expects a small chunk for the small object but receives the large chunk, the virtual storage layer generates an error ( 924 ). If the virtual storage layer determines (922) that the received chunk is valid, then the virtual storage layer reconstructs the small object using the received chunk(s) (923); Receive a chunk from the devices (925).

The procedure 912 for reconstructing a slice may include a plurality of auxiliary procedures. The virtual storage layer checks whether all D chunks for reconstructing a slice have been received (931). If so, the virtual storage layer reconstructs 935 the slice using an erasure coding algorithm with the D chunks. If not, the virtual storage layer checks whether all chunks of the current band have been received (932). If all chunks of the band have been received, the virtual storage layer generates an error ( 936 ) because at least one of the received chunks may not be valid. If there are more chunks to be received, the virtual storage layer continues receiving them from the other data storage device (933) and repeats the procedure until it has received all D chunks to reconstruct the slice. If the received chunks are not large, and are not large (eg, if the chunk is for a small object), the virtual storage layer throws an error 936 .

According to an embodiment, 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 other data reliability schemes including an erasure coding scheme and a data duplication scheme based on the object sizes of the plurality of objects. The plurality of objects include a first object having a first size and a second object having a second size greater than the first size. The virtual storage layer classifies the first object as a small object, applies the data replication method, and stores the small object through one or more of the plurality of data storage devices. The virtual story layer classifies the second object as a giant object, divides the giant object into one or more chunks of the same size, applies the erasure coding scheme, and divides the one or more chunks into the plurality of chunks. Distributed and stored through data storage devices of

The distributed scheme is such that the virtual storage layer divides the one or more chunks of the giant object into the plurality of data storage devices, and stores the one or more chunks through the plurality of data storage devices. A split-first distribution that stores more chunks.

The distributed scheme is such that the virtual storage layer distributes one of the giant object to each of the plurality of data storage devices until the one or more chunks of the giant object are completely stored to the one or more data storage devices. It is a band-first distributed scheme that stores junk.

The virtual storage layer may further classify a third object having a third size into a large object, dividing the large object into one or more chunks of the same size, applying the erasure coding scheme, and The one or more chunks are distributed and stored through the data storage devices of The third size is larger than the first size and smaller than the second size. The large object contains only one chunk or one band in the split.

The virtual storage layer may further classify a fourth object having a fourth size as a medium object. The fourth size is larger than the first size and smaller than the third size. The virtual storage layer applies one of the data replication scheme and the erasure coding scheme.

The object can be identified using a user key. The virtual storage layer may generate an internal key including a band identifier for the giant object and the user key. The band identifier is used to identify a band among a plurality of bands. Each of the bands of the plurality of bands includes one chunk of one or more chunks distributed through the plurality of data storage devices.

The virtual storage layer may use the hash value of the user key to identify a starting data storage device for writing or reading a first chunk of the one or more chunks of the plurality of data storage devices.

The plurality of data storage devices may include one or more dedicated parity data storage devices for storing parity chunks associated with the large object.

The plurality of data storage devices may support a group feature, and when reading the giant object, the virtual storage layer may set the band identifier to arbitrary data bits and transmit it to the plurality of data storage devices. .

The plurality of data storage devices may not support a group feature, and the virtual storage layer may set the band identifier as a unique band identifier and transmit it to the plurality of data storage devices when reading the large object. .

Each of the plurality of data storage devices may be a key-value solid-state drive (KV SSD).

According to another embodiment, a method of writing an object of a key-value pair includes: receiving a plurality of objects of a key-value pair, wherein the plurality of objects include a first object having a first size and the first object a second object having a second size greater than the size; classifying the first object as a small object; applying a data replication method to the small object; storing the small object via one or more of a plurality of data storage devices; classifying the second object as a giant object; dividing the large object into one or more chunks of the same size; applying erasure coding to the large object; and distributing and storing the one or more chunks through the plurality of data storage devices.

The method includes: receiving a write request for the object; determining whether the object is the giant object; determining a chunk size and the number of chunks for the giant object; and writing the one or more chunks of the giant object to the plurality of data storage devices based on the chunk size and the number of chunks.

The method includes: creating a slice including one chunk for each of the plurality of data storage devices among the plurality of chunks, and a user having a band identifier attached to each of the one or more chunks included in the slice generating an internal key using the key; generating a band including the one or more chunks and one or more parity 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 method; and writing the one or more chunks to the band together with the inner key.

The method includes: receiving a write request for the object; determining whether the object is the small object; determining a portion of the plurality of data storage devices to store the one or more chunks of the small object based on a distribution method; and writing the one or more chunks of the small object to the portion of the plurality of data storage devices.

The method includes: receiving a read request for the object including the user key; determining whether the plurality of data storage devices support a group feature; and transmitting the read request together with the internal key to the plurality of data storage devices.

If the group feature is supported, the band identifier of the inner key may be set to bits of arbitrary data.

If the group feature is not supported, the band identifier of the inner key may be set as a unique band identifier.

The method includes 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.

Each of the plurality of data storage devices may be a key-value solid-state drive (KV SSD).

The above-described exemplary embodiments are intended to describe various embodiments of implementing a data storage system capable of efficiently storing objects having different sizes and a method of storing objects in the data storage system. Various modifications from the described exemplary embodiments can be readily made by those skilled in the art. Matters intended in the technical spirit of the present invention are described in the claims below.

Claims (20)

A data storage system comprising:
a plurality of data storage devices storing a plurality of objects of a key-value pair;
a virtual storage layer that controls the plurality of data storage devices and applies other data reliability methods including a data replication method and an erasure coding method based on the size of the objects of the plurality of objects,
The plurality of objects include a first object having a first size and a second object having a second size greater than the first size,
the virtual storage layer classifies the first object as a small object, applies the data replication method, stores the small object through one or more of the plurality of data storage devices,
The virtual storage layer classifies the second object as a large object, divides the large object into one or more chunks of the same size, applies the erasure coding scheme, and uses the plurality of data storage devices to Distributed storage of one or more chunks,
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 the classification of the plurality of objects.
The method of claim 1,
the virtual storage layer stores the one or more chunks of the giant object through the plurality of data storage devices in a split-first manner;
The split-first scheme is such that the virtual storage layer stores some of the one or more chunks of the giant object in one of the plurality of storage devices, and the other of the one or more chunks of the giant object. A data storage system, wherein a portion is stored in another one of the plurality of storage devices. The method of claim 1,
the virtual storage layer stores the one or more chunks of the giant object through the plurality of data storage devices in a band-first manner;
In the band-first scheme, the virtual storage layer stores one chunk of the large object in the plurality of data storage devices until the one or more chunks of the large object are all stored in the plurality of data storage devices. A data storage system that stores each of them. The method of claim 1,
The virtual storage layer further classifies a third object having a third size into a large object, divides the large object into one or more chunks of the same size, applies the erasure coding scheme, and the plurality of data distributedly store the one or more chunks through storage devices;
the third size is larger than the first size and smaller than the second size;
wherein the large object includes only one chunk or only one band in a split.
5. The method of claim 4,
The virtual storage layer classifies a fourth object having a fourth size as an intermediate object,
The fourth size is larger than the first size and smaller than the third size,
and the virtual storage layer applies one of the data replication method and the erasure coding method.
The method of claim 1,
the object is identified using a user key, and the virtual storage layer generates an internal key including a band identifier for the large object and the user key;
wherein the band identifier is used to identify a band of a plurality of bands, each of the bands of the plurality of bands comprising a chunk of the one or more chunks distributed through the plurality of data storage devices data storage system. 7. The method of claim 6,
and the virtual storage layer identifies a starting data storage device of the plurality of data storage devices using the hash value of the user key to read or write a first chunk of the one or more chunks. The method of claim 1,
and the plurality of data storage devices includes one or more dedicated parity data storage devices for storing parity chunks associated with the large object. 7. The method of claim 6,
The plurality of data storage devices support a group feature, and the virtual storage layer transmits the band identifier to the plurality of data storage devices by setting arbitrary data bits when the large object is read. system. 7. The method of claim 6,
A data storage system in which the plurality of data storage devices do not support the group feature, and the virtual storage layer transmits the band identifier as a unique band identifier to the plurality of data storage devices when the large object is read. . The method of claim 1,
Each of the plurality of data storage devices is a key-value solid-state drive (KV SSD) data storage system. A method of writing an object of a key-value pair, comprising:
receiving a plurality of objects of a key-value pair, wherein the plurality of objects include a first object having a first size and a second object having a second size greater than the first size;
classifying the first object as a small object;
applying a data replication method to the small object;
storing the small object through one or more plurality of data storage devices;
classifying the second object as a giant object;
dividing the large object into one or more chunks of the same size;
applying an erasure coding scheme to the large object; and
and distributing the one or more chunks across the plurality of data storage devices.
13. The method of claim 12,
receiving a write request for the object;
determining whether the object is the giant object;
determining a chunk size and the number of chunks for the giant object; and
and writing the one or more chunks of the large object to the plurality of data storage devices based on the chunk size and the number of chunks. 14. The method of claim 13,
A slice including one chunk for each of the plurality of data storage devices among the one or more chunks is generated, and a user key to which a band identifier for each of the one or more chunks included in the slice is attached. generating an internal key using;
generating a band including the one or more chunks and 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 method; and
writing the one or more chunks to the band with the internal key.
13. The method of claim 12,
receiving a write request for the object;
determining whether the object is the small object;
determining a part of the plurality of data storage devices to store the one or more chunks of the small object based on a distribution method; and
and writing the one or more chunks of the small object to the some of the data storage devices.
15. The method of claim 14,
receiving a read request for the object including the user key;
determining whether the plurality of data storage devices support a group feature; and
and sending the read request along with the internal key to the plurality of data storage devices. 17. The method of claim 16,
If the group feature is supported, the band identifier of the inner key is set to bits of arbitrary data. 17. The method of claim 16,
If the group feature is not supported, the band identifier of the inner key is set as a unique band identifier. 17. The method of claim 16,
receiving at least one chunk from each of the plurality of data storage devices; and
and reconstructing a slice from the at least one chunk received from the plurality of data storage devices using the erasure coding scheme. 13. The method of claim 12,
wherein each of the plurality of data storage devices is a key-value solid-state drive (KV SSD).

Images