JP2019128960A - Data storage system, and method for accessing objects of key-value pair - Google Patents

Abstract

An object of the present invention is to provide a highly reliable data storage system that efficiently stores different objects (hereinafter abbreviated as OBs) that are adapted to the characteristics of KV_SSD. A plurality of data storage devices (hereinafter, abbreviated as DSD) for storing a plurality of OBs of a key-value pair, and a data replication method and an erasure coding method based on the OB size of each of the plurality of OBs. Includes virtual storage layers that apply different data reliability schemes. The plurality of OBs each include a first OB and a second OB having a first size and a second size larger than the first size, and the virtual storage layer classifies the first OB into a small OB and applies a data replication method, A single OB or a plurality of DSDs are stored, while the second OB is classified into a huge OB, divided into one or more chunks of the same size, and an erasure coding method is applied to store the plurality of OBs. Singly or multiple chunks are distributed and stored across the DSDs. [Selection diagram] Fig. 1

Description

  The present invention relates to data storage systems, and more particularly to methods for accessing large key value objects in data storage systems.

Data reliability is a core requirement of data storage systems. The reliability of data using a conventional block device is implemented or studied using various data replication techniques such as erasure coding and RAID (Redundant Array of Independent Disks). RAID spreads (or replicates) data over a set of data storage devices to prevent permanent data loss for a particular drive. RAID is roughly classified into two categories. That is, a category in which a complete mirror image of the data is maintained in the second drive, or a parity block is added to the data block, so that the failed data block can be recovered in a fail situation. It is a category.
Erasure coding adds a bunch of blocks similar to parity using a complex algorithm that provides strong data protection and recovery that can tolerate high levels of failure. For example, erasure coding can create virtual drives that can be physical drive virtualized and distributed across multiple physical drives to achieve fast recovery. Replicating data using RAID is too expensive to replicate large objects, and erasure coding can waste storage space for small objects.

  Key-value solid-state drives (KV_SSD) have different interfaces and semantics (compared to traditional block devices such as hard disk drives (HDD) and solid-state drives (SSD)). storage) is a new type of storage. KV_SSD can directly store the data value of the key-value pair. The data values stored on the KV_SSD can be huge or small, depending on the application and data characteristics. Therefore, there is a need for an efficient data reliability model that efficiently stores objects of different sizes without performance bottlenecks and space constraints.

Patent Literature 1: US Patent No. 9417963B2 Patent Literature 2: US Patent No. 9594633B2 Patent Literature 3: US Patent No. 9539268B2

  The object of the present invention is thus to efficiently store different objects without performance bottlenecks and space constraints, so as to conform to the characteristics of KV_SSD having interfaces and semantics different from conventional memory types. It is an object of the present invention to provide a data storage system that embodies a high quality model.

According to one embodiment, a data storage system includes a plurality of data storage devices that store a plurality of objects of a key-value pair, and a data duplication method and an erasure coding method based on the object size of each of the plurality of objects. A virtual storage layer that applies different data reliability schemes, wherein the plurality of objects include a first object having a first size and a second object having a second size larger than the first size. The virtual storage layer classifies the first object as a small object and applies the data replication scheme, and the small object is spread over any one or more of the plurality of data storage devices. Store the virtual storage layer The second object is classified as a giant object, the giant object is divided into one or more chunks of the same size, and the erasure coding scheme is applied to the one or more data storage devices. Distributed and store more chunks.

  According to another embodiment, a method of accessing an object of a key-value pair comprises: receiving a plurality of objects of a key-value pair, wherein the plurality of objects comprises a first object having a first size; Including a second object having a second size greater than the first size, classifying the first object as a small object, applying a data replication scheme to the small object, and Storing over any one or more of the data storage devices, classifying the second object as a giant object, and dividing the giant object into one or more chunks of the same size And the huge object Comprising applying a coding scheme, and storing said one or more distributed across the chunks to the plurality of data storage devices (distributedly) to a removed by.

  The foregoing and other suitable features, including various new descriptions of event implementations and combinations, will be described in further detail with reference to the accompanying drawings and set forth in the claims. The particular systems and methods described herein are illustrated for the purpose of description only and the invention is not limited thereto. It should be understood by those skilled in the art that the theory and features described herein can be embodied in various embodiments without departing from the spirit of the invention.

  By determining the size of the object, the data replication method is applied to the small object, and the erasure coding method is applied to the large object after dividing the chunk, so that a plurality of objects having different sizes can be efficiently managed and stored.

  The accompanying drawings, which are included as part of the detailed specification of the present invention, illustrate the presently preferred embodiments, and together with the general description given above and the detailed description of the preferred embodiments provided below. It will serve to explain and teach the principles of the invention described.

FIG. 1 shows a conceptual diagram of objects stored in an exemplary data storage device according to one embodiment. FIG. 2 shows an exemplary internal key including a user key according to one embodiment. FIG. 3 shows an example of object retrieval using group features according to one embodiment. FIG. 4 shows an example of group-free object collection according to one embodiment. FIG. 5 illustrates an example of erasure coding without a dedicated parity device according to one embodiment. FIG. 6 shows an example of erasure coding using one or more dedicated parity devices according to one embodiment. FIG. 7 illustrates an exemplary replication scheme of small objects through one or more data storage devices without a parity device, according to one embodiment. FIG. 8 shows an exemplary flow chart for writing an object according to one embodiment. FIG. 9 illustrates some sub-processes of an exemplary flowchart for writing an object according to one embodiment. FIG. 10 shows an exemplary flow chart for reading an object according to one embodiment. FIG. 11 illustrates some sub-processes of an exemplary flow chart leading object according to one embodiment. FIG. 12 illustrates another portion of the sub-process of the exemplary flow chart leading an object according to one embodiment.

  For the sake of brevity throughout the drawings, the drawings are not necessarily drawn to scale, and elements of similar structure or function are generally indicated by similar reference numerals. The drawings are only intended to facilitate the description of the various embodiments described in the text. The drawings do not describe all the ideas of the teachings disclosed in the text and do not limit the scope of the claims.

  Each of the features and teachings described herein may be used in conjunction with other features and teachings or individually to store objects in data storage systems and data storage systems that efficiently store objects having different sizes. We can provide a way. Representative embodiments that use various additional features and teachings separately or in combination will be described in further detail with reference to the accompanying drawings. This detailed description is merely to teach one of ordinary skill in the art to practice the inventive concepts, and is not intended to limit the scope of the claims. Thus, the combination of features disclosed above in the detailed description may, in the broadest sense, not be essential to the practice of the present invention, and merely describes a particularly representative embodiment of the present invention. To be taught.

  In the following description, certain nomenclature is used to aid in the overall understanding of the present invention for the convenience of explanation. However, it will be apparent to those skilled in the art that such specific descriptions are not essential to embody the teachings of the present disclosure.

  Part of the detailed description in the text is provided in the form of algorithmic and symbolic representations of operations on data bits in computer memory. Such algorithmic descriptions and representations are used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is expressed in the text, but also generally, as a consistent series of steps leading to an intended result. The steps are steps in which physical quantities have to be physically manipulated. Generally, but not necessarily, such physical quantities have the form of electrical or magnetic signals that can be stored, broadcast (broadcast), combined, compared, and transformed differently. It has often been proven convenient to refer to such signals as bits, values, elements, symbols, features, terms, numbers, etc., mainly because they are commonly used in common. There is.

  However, these and similar terms should all be associated with the appropriate physical quantities and are only convenient labels applied to such physical quantities. As will become apparent in the following description, unless otherwise stated, the terms "processing", "computing", "calculating" and "determination" are used throughout the detailed description. Descriptions using terms such as "determining", "displaying", etc. refer to data expressed as physical (electronic) quantities in the computer system or in the register and memory of the computer system, Fig. 6 illustrates the operation and processing of a similar electronic computing device, broadcast or display device that transforms and broadcasts different data that are similarly represented as physical quantities in a memory, register or other information storage.

Furthermore, the various features of the exemplary embodiments and subclaims are combined in a manner not necessarily specific and explicitly recited to additionally provide useful embodiments of the present invention. .
The range of all values, or the designation of a group of entities, is all for the purpose of limiting the simultaneously claimed configuration requirements (Subject_matter) for the purpose of the original disclosure. It is specified here that it discloses the possible intermediate values or intermediate objects of. The shape and dimensions of the components shown in the drawings are designed merely to assist in understanding the manner in which the present invention is embodied, and are limited to the dimensions and shapes illustrated in the examples, including the present invention. There is no intention to do, it is also stated here.

  The present disclosure describes a data storage system and method for storing large key value objects in a data storage system. The data storage system of the present invention can store highly reliable data in one or more data storage devices. In particular, the data storage system of the present invention can store objects differently based on their size, reducing cost and storage space, and achieving high reliability. Data associated with large objects can be split into small pieces and stored in one or more data storage devices. Here, if the data stored in the data storage device is a data array associated with a key-value pair (key-value_pair), the data storage device is a key-value solid state drive (KV_SSDs: key-value solid state drives May be referred to as

  An object (e.g., the value of a key-value pair) can be split into a plurality of chunks of the same size, i.e., multiple pieces. Chunk size can be determined on a per-object basis dynamically during runtime. Depending on its size, an object can contain different numbers and sizes of chunks.

  A group is defined as a set of data storage devices for implementing target data reliability. A group may include one or more data storage devices in or via a box (eg, chassis or rack), and may be hierarchically or non-hierarchically structured be able to.

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 groups to user applications as a single virtual storage unit as a whole. The virtual storage layer can be used to manage multiple drivers that control one or more data storage devices. The number of data storage devices managed by the virtual storage layer can be configured based on a reliability target.
For erasure coding, the total number of data storage devices may be the sum of the data device (D) and the parity device (P) in order to accept P failures.
For replication, the total number of data storage devices that tolerate P failures may be P + 1. The storage capacities of data storage devices may be substantially similar in erasure coding or replication. The storage capacity of virtual storage can be determined by the sum of data storage space of all data storage devices in the group.

  According to one embodiment, the virtual storage layer can manage one or more groups of data storage devices in a stateless manner. That is, the virtual storage layer does not maintain or need to maintain any mapping information or key information between objects and data storage devices. However, the virtual storage layer dynamically caches the required metadata at one or more data storage devices of the number of objects, available storage capacity, and / or similar types, It can be maintained.

  Data storage devices such as KV_SSD have implementation specific limitations on operations on objects and processable objects. The virtual storage layer of the data storage system can recognize the size of the minimum value and the maximum value that each data storage device can support, and can determine the size of the minimum value and the maximum value.

同様に、ＶＭＡＸ_ｉが第ｉ番目のＫＶ＿ＳＳＤの最大バリューのサイズである場合、仮想ストレージの最大バリューのサイズ（ＶＭＡＸ＿ＶＳ）は、グループ内の個々のＫＶ＿ＳＳＤの全ての最大バリューのサイズの中の最小バリューによって定義されることができる。

一実施例で、ＲＳ（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）コードのようなＭＤＳ（ｍａｘｉｍｕｍ ｄｉｓｔａｎｃｅ ｓｅｐａｒａｂｌｅ）アルゴリズムが、消去コーディング（ｅｒａｓｕｒｅ ｃｏｄｉｎｇ）のために使用されることができる。 For example, if VMIN _i is the size of the minimum value of the ith KV_SSD, then the minimum value size of virtual storage (VMIN_VS) is defined by the maximum value among the sizes of all the minimum values of the individual KV_SSDs in the group Can be done.

Similarly, if VMAX _i is the size of the largest value of the ith KV_SSD, then the size of the largest value of virtual storage (VMAX_VS) is the smallest value among the sizes of all the largest values of the individual KV_SSDs in the group. Can be defined by

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

According to one embodiment of the present invention, the system and method of the present invention provide a hybrid data reliability mechanism that leverages both replication and erasure coding based on the size of the object. . Data replication can be fast for small objects and can be computationally intensive. However, data replication may consume more storage space for large objects when compared to erasure coding. Erasing coding typically consumes less storage space for large objects than data replication, but can restore such large objects while affecting multiple data storage devices.
However, since multiple chunks are required from multiple data storage devices, erasure coding generally can be time consuming to restore small objects with heavy computations. This is a non-hierarchical way of duplicating data after performing erasure coding of the data. Instead, the system and method of the present invention provide flexible decisions about the choice 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 either be data replication or erasure coding at runtime based on data reliability determination, ie not only the size of the object but also the overhead of the overall space for storing the object. Can decide to apply.

According to one embodiment, the system and method of the present invention does not involve read-modify-write overhead when an object is updated. Conventional erasure coding or data replication for block devices involves a lot of overhead, even when partial updates exist. Even if a small portion of the data is updated, all of the blocks for erasure coding must be read and updated, and after the update the parity block is recomputed and rewritten (write back) to the data storage device There must be. In other words, an object update requires a series of read-modify-write processes because one block can be shared by multiple objects.
In contrast, the systems and methods of the present invention can provide reliability based on an object and its characteristics, eg, size. When an object is updated, only the updated object needs to be overwritten (write-over) without the overhead of read-modify-write.

  According to one embodiment of the present invention, the system and method of the present invention support a wide range of object sizes under a unified framework. If the object is very large (or huge) beyond 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 (hereinafter referred to as chunks). The present disclosure discusses how objects are divided into chunks and rebuilt from the divided chunks based on the capacity of the data storage device. For example, the systems and methods of the present invention provide a variety of partitioning and restoration mechanisms based on group feature support for data storage devices, as discussed in more detail below.

  The system and method of the present invention provide object reliability that is not based on fixed blocks. Data replication and erasure coding is mixed and combined to embody the object's target reliability for a single disk group by bifurcating the object based on the size of the object. Such methods are different from conventional data reliability techniques that include hierarchical structure (i.e., duplicates to erasure coded objects). The system and method of the present invention have space efficiency as a primary concern, and performance is a secondary factor to determine the reliability mechanism that is appropriate for a particular object. The storage of objects is stateless. No additional information needs to be stored for any one of duplication or erasure coding. No read-modify-write overhead is required for updates regardless of the size of the object.

  In the text, an object indicates static data having a fixed value (fixed value) between input and output (I / O) operations. An object can be associated with a key of a key-value pair. In such a case, the object corresponds to the value of the key-value pair. Objects can be divided into multiple chunks of the same size, and the size of the chunks can be determined dynamically on an object-by-object basis during runtime. Each object, when stored on one or more data storage devices, can contain different numbers and different sized chunks.

  Without data reliability, the smallest set of chunks of object data stored all at once across one or more data storage devices (eg, KV_SSD) is referred to in the text as a slice. For example, a slice corresponds to a plurality of chunks of an object stored separately in one or more data storage devices. The smallest set of data chunks of an object that embodies data reliability (e.g., duplication or erasure coding) is called a "band". The number of chunks in the band may be more than the number of chunks of a slice because of parity chunks. A set of chunks of objects stored on one data storage device among one or more data storage devices in a group can be referred to as a split.

A slice can contain only one chunk (of the target object) for duplication of data (i.e., duplicate copies of the original object). On the other hand, a slice can contain D chunks containing target objects for erasure coding. On the other hand, a band may contain P duplicate chunks and one original chunk for data duplication, while it contains P parity chunks and D data chunks for erasure coding. Can do. The number of slices or bands corresponds to the total number of chunks in the split.
Split size (ie, the number of chunks stored in one data device) and band size (ie, the number of data chunks and parity chunks contained in one object stored in one or more data storage devices ) Can be varied according to the size of the original object and the chunk. For example, the split size may be the original size for data replication, while the split size is the size obtained by dividing the total number of chunks by the number of chunks per band for erasure coding.

  FIG. 1 illustrates a conceptual diagram of objects stored in an exemplary data storage system, according to one embodiment. Object 110 may be divided into multiple chunks. For example, the object 110 is 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 different numbers, and the object 110 may not be divided into multiples of three. Object 110 can be classified as a very large or huge object, as described in detail below. The split chunks can be distributed in virtual storage across one or more data storage devices. In the 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 the embodiment of the present invention, S and D are identical.

According to one embodiment, the virtual storage layer of the data storage system distributes the chunks by either a split first (prioritized) method (split first distribution) or a first band (first priority) method (band first distribution). Can do.
In the split first method, the virtual storage layer stores chunks (Chunk_1, Chunk_2, Chunk_3) in the first data storage device (Disk_1) in the virtual storage 120, and chunks (Chunk_4, Chunk_5, Chunk_6) as the second data storage. The data is stored in the device (Disk_2), and the chunks (Chunk_3D-2, Chunk_3D-1, Chunk_3D) are similarly stored in the Dth 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 priority method, in the virtual storage 121, the virtual storage layer stores chunks (Chunk_1 to Chunk_D) in data storage devices (Disk_1 to Disk_D) and chunks (Chunk_D + 1 to Chunk_2D) as data storage devices (Disk_1 to Disk_D) Similarly, chunks (Chunk_2D + 1 to Chunk_3D) are stored in the data storage devices (Disk_1 to Disk_D), respectively. The split 151 includes chunks of data (Chunk_1, Chunk_D + 1, Chunk_2D + 1). The parity chunks (Parity_1 to Parity_P) are stored in parity disks (Disk_D + 1 to Disk_D + P).
In the present embodiment, for convenience of explanation, both virtual storage 120 and virtual storage 121 are shown to store parity chunks in the band priority system, but storage of parity chunks deviates from the concept of the present invention. It will be appreciated that it may be performed in a split-first manner without the need.

  The I / O operations can be performed in a band first manner regardless of what chunk distribution method is used. In such a case, I / O operations for chunks (Chunk_1, Chunk_4,..., Parity_P) are accessed in parallel even in the split priority scheme.

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

The number of chunks per device (NC _Oi ) is an object (across data disks (ie, data storage devices referenced as Disk_1-Disk_D)) if the maximum chunk size (VMAX _VS ) is used. O _i ) is the minimum number of chunks per split to store. If the size of the object is not aligned with the unit of data storage device allocation or alignment, the additional space allocated for the object in the band can be padded with zeros.

If the largest chunk size is used, storage space tends to be wasted using too much padding. Thus, the actual chunk size of the object (O _i ) is more strictly determined by Equation 4. SZ _meta is the size of the metadata if additional metadata is stored with the data per chunk. If the data storage device supports group features, some metadata may be stored in each chunk, such as a group identifier (group_ID) and the total number of chunks. If the data storage device does not support the group feature, there is no metadata stored (ie, SZ _meta = 0). For replication, the actual chunk size may be identical to the size of the original object (ie, C _Oi = SZ _Oi ).

最終的に、データストレージデバイスに亘って一度にライト（書込み）されるデータの全体の総量、即ち、バンドサイズは、数学式６によって定義される。複製についてＤは１と同じである。

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

Finally, the total amount of data written at one time across the data storage device, ie, the band size, is defined by Equation 6. For replication D is the same as 1.

As mentioned above, the data storage device has a limit on the size of objects that the data storage device can store. Some data storage devices may not be able to 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 can apply different data reliability schemes based on the size of the stored objects . According to one embodiment, the virtual storage layer of the data storage system of the present invention divides objects into four types based on the size of the objects: huge, large, medium, and Classified as small.
When multiple bands are used to store an object, the object is classified as huge. If a band is used almost entirely to store an object, the object is classified as being large. If a small fraction of the band is used to store the object, the object is classified as being small. Finally, if the object can be classified as small or large, the object is classified as medium. Therefore, chunks having different sizes can coexist not only in the same virtual storage but also in individual data storage devices forming the virtual storage.

An object is classified as small if the space overhead of replication for the object is smaller than the space overhead of erasure coding of the object. In this case, the choice of replication scheme is appropriate as it provides better performance for reads and is easier to manage updates than complex erasure coding schemes. This choice is reasonable in situations where application metadata tends to be small. In one embodiment, a small object (O _i ) having size SZ _Oi satisfies mathematical equation 7.

大型のオブジェクトは、図１と類似した構成になれるが、１つのバンドだけ、即ち、１つのスプリット内には１つのチャンクだけ包含できる。 An object is classified as large if the space overhead of erasure coding for the object is smaller than the space overhead of data replication for the object. In this case, the choice of the erasure coding scheme is appropriate as it has less space. In particular, large objects satisfy mathematical equation 8.

A large object can be configured similar to FIG. 1, but can contain only one band, ie, one chunk in one split.

巨大オブジェクトは、図１と類似するように構成されることができるが、スプリット内に複数のチャンク又は複数のバンドを包含できる。 If an object contains one or more chunks in a split, the object is classified as huge. In this case, erasure coding is appropriate. In particular, huge objects satisfy the mathematical expression 9.

Giant objects can be configured to be similar to FIG. 1, but can include multiple chunks or multiple bands in a split.

このような場合には、データの複製又は消去コーディングの中の何れか１つが使用されることができる。性能がより重要であり、オブジェクトが頻繁にアップデートされる場合、データ複製がよりよい選択であり得る。この場合、中型のオブジェクトは、小型のものに分類されることができる。空間効率性がより重要な場合には、消去コーディングが使用されることができる。このような場合、中型のオブジェクトは、大型のものに分類されることができる。 There can be a range of object sizes that can not be classified as either small or large. That is, objects satisfying mathematical expression 10 are classified as medium-sized objects.

In such a case, any one of data duplication or erasure coding can be used. If performance is more important and objects are updated frequently, data replication may be a better choice. In this case, the medium-sized object can be classified as a small object. If space efficiency is more important, erasure coding can be used. In such cases, medium-sized objects can be classified as large ones.

The virtual storage layer may need to split large objects into smaller data chunks in order to store the objects and use split data chunks to reconstruct the objects and retrieve the large objects. Thus, an internal key generated from a user (eg, a user application running on a host computer) key can be used to make the virtual storage layer stateless.
According to one embodiment, the virtual storage layer reserves a few bytes in a device-supported key space supported by the device for internal use to distribute chunks and reserves the rest of the key space. Open to users. In this case, the user-specific object key represents a group of internal keys for one or more split chunks of the object.

  FIG. 2 illustrates an exemplary internal key that includes the user's key, according to one embodiment. The internal key 200 includes a first portion user key 201 and a second portion band identifier (ID) 202. The internal key 200 can be used to identify a portion of a chunk for the corresponding object or an entire group of chunks. 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 present 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. It is. The virtual storage layer informs the user that the maximum key length available is L-G.

  For small or large objects, the G-byte band ID (202) can be padded with (by_default) 0 basically. For large objects, the virtual storage layer can calculate the number of bands in the object. Individual bands can be identified using internal key 201. Bands can be written to one or more data storage devices assigned to store objects one by one according to a split priority or band priority scheme.

According to one embodiment, a data storage device can support group features. The virtual storage layer can identify the split stored in the data storage device by specifying the group based on the user key 201. In this case, additional metadata may not be required (SZ_meta = 0). The virtual storage layer sends a band ID (202) and user key 201 filled with "do_not_care" bits (arbitrary data bits, for example, 0xFF) to all data storage devices, thereby for the object. All chunks can be collected.
If the band ID is "do_not_care", the band ID field is ignored. It can be assumed that the data storage device efficiently embodies the features of the group. For example, a trie structure can easily identify an object having a given prefix given a user key 201, while a hash table can be used when the metadata field is fixed. You can only discover objects from hash buckets using a user key. The virtual storage layer arranges the returned object chunks in ascending order based on the band ID 202 for each device, reconstructs the band and the object, and returns the object together with the user key 201.

FIG. 3 illustrates an example of object retrieval using group features, according to one embodiment. Each of the data storage devices assigned to store the objects (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 as "do_not_care" so as to ignore the band ID (302). The virtual storage layer uses the user key 301 to collect the chunks belonging to the band 350 (that is, data chunks 1, 2,..., D and parity chunks 1 to P) and Reconstruct the first slice containing Chunk_1 to Chunk_D).
Thereafter, the virtual storage layer collects the remaining chunks and reconstructs the remaining slices in order. If all slices have been configured, the virtual storage layer reconstructs an object 310 that contains chunks of data (Chunk_1 to 3D) from the slices. In the case of erasure coding, the virtual storage layer further reconstructs parity blocks from parity chunks (parity chunks 1 to P). While the present embodiment shows a band priority scheme for splitting chunks, it will be appreciated that the split priority scheme can be applied to chunk splitting and object retrieval without departing from the spirit of the invention. .

FIG. 4 shows an example of the collection of objects without group features according to one embodiment. In this case, the virtual storage layer attaches additional metadata to the large or huge objects, since the data storage devices assigned to store the objects do not support group features (ie, SZ_meta ≠ 0). ). Each chunk can be identified by a band ID 402 having a length of 1 byte. In the current embodiment, there can be three bands (Band_1, Band_2, Band_3) so that the number of bands can be adapted to a length of 1 byte.
The virtual storage layer can configure slices one by one using the band ID 402. First, the virtual storage layer broadcasts the user key 401 to all data storage devices together with band 0 whose band ID is 0 (BID = 0). The virtual storage layer receives chunks for band 0 (Band_0) from all data storage devices, and collects band information from the chunks belonging to band 0 (Band_0) in the received chunks. Based on the received band information, the virtual storage layer recognizes the number of bands and collects the object. If the object is large, only one band can exist, so the virtual storage layer can reconstruct the entire object from the chunks in that band.
Since there are more than one chunk for a huge object, the virtual storage layer needs to retrieve multiple bands (eg, Band_1 and Band_2) one by one. In this case, the virtual storage layer broadcasts the collection request by adjusting the band ID (for example, BID = 1 or BID = 2) until all chunks are collected. If the virtual storage layer has configured all slices, then the virtual storage layer can reconfigure the object 410. Small objects may not have metadata, regardless of whether the device supports the features of the group. By checking the chunk size, the virtual storage layer can use Equation 7 and Equation 10 to determine if the object 410 is small.

In order to write huge objects to one or more data storage devices, the large objects can be divided into NC _Oi × D chunks of the same size (ie, _NCOi slices). The last data chunk (for example, data 4a (Data_4a) of object 510a and data 4b (Data_4b) of object 510b in FIG. 5) can be padded to 0 (zero) in consideration of an array request, P parity chunks can be generated from D chunks of data per slice.

FIG. 5 shows an example of erasure coding without a dedicated parity device according to one embodiment. FIG. 6 illustrates an example of erasure coding using one or more dedicated parity devices according to one embodiment. The total of (D + P) chunks, including D data chunks and P parity chunks per band, is distributed to one or more data storage devices and all NC _Oi bands are written . The parity chunks may be stored distributed on some of the D + P devices (e.g. SSD4 to SSD6 in FIG. 5) or stored on P dedicated devices (e.g. SSD5 and SSD6 in FIG. 6) be able to.
The primary data storage device is selected using the hash value of the user key (hereinafter referred to as “Hash (user_key)” (hash (user key)) without band ID on the data storage device it can. All or some of the (D + P) devices can be selected in the embodiment of FIG. 5, and D devices can be selected in the embodiment of FIG. The start device can be determined by Hash (user_key)% (D + P) if there is no dedicated parity device, or by Hash (user key)% D if there is a dedicated parity device.
Subsequent chunks are assigned to the next device (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) It can be sequentially written sequentially. Such an operation is a per band operation, and the virtual storage layer repeats such a procedure for all NC _Oi bands to write a chunk of the object. The hash value of the user key needs to be calculated once for each object.

If the data storage device does not support the group feature, the chunk includes additional metadata for the total number of bands and band ID, as illustrated in FIG. The number of bands can be determined by Equation 3. Band chunks can contain (band ID, NC _Oi ) pairs as metadata.

  Referring to FIG. 5, the virtual storage layer stores data chunks (Data_1a to Data_4a) and parity chunks (Parity_1a and Parity_2a) of the object 510a through data storage devices (SSD1 to SSD6). The virtual storage layer stores data chunks (Data_1b to Data_4b) and parity chunks (Parity_1b and Parity_2b) of the other objects 510b through the data storage devices (SSD1 to SSD6). The start device (eg, SSD1 for object 510a and SSD6 for object 510b) can be determined by the hash value of the user key, as described above. Because there is no dedicated parity device, the virtual storage layer can distribute data chunks and parity chunks to data storage devices (SSD1 to SSD6) without distinguishing between data chunks and parity chunks. In the current embodiment, SSD 4 and SSD 6 contain all data chunks and parity chunks.

  Referring to FIG. 6, the virtual storage layer stores the data chunk (Data_1a to Data_4a) and the parity chunk (Parity_1a and Parity_2a) of the object 610a through the data storage devices (SSD1 to SSD6). Similarly, the virtual storage layer stores (Parity_1b and Parity_2b) in the data chunk (Data_1b to Data_4b) and the parity chunk of the object 610b across the data storage devices (SSD1 to SSD6). Since SSD5 and SSD6 were assigned to parity devices, SSD5 and SSD6 contain only parity chunks.

To write a large object to one or more data storage devices, the large object can be divided into NC _Oi × D chunks of the same size. Large objects are managed like large objects, except that they can be one band to the object (ie, NCOi = 1).

  In order to store small objects, (P + 1) duplicate objects can be generated for the objects. Given the alignment, including padding, duplicate objects can be distributed to (P + 1) devices. The main device can be selected on the (D + P) device (where D = 1) using the hash value of the user key. The P replicated objects can be selected deterministically based on various factors such as storage organization, performance, and the like. For example, the duplicate object is (Hash (key) +1)% (D + P), (Hash (key) +2)% (D + P),. . . , (Hash (key) + P)% (D + P), or can be simply stored in different nodes or racks with or without dedicated parity devices. If a dedicated parity device or node exists, then the duplicate object is (Hash (key) +1)% D, (Hash (key) +2)% D,. . . , (Hash (key) + P)% D can be stored. Small objects do not contain metadata, regardless of device capacity.

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

  FIG. 8 illustrates an exemplary flowchart for writing an object, according to one embodiment. The virtual storage layer of the data storage system receives a write request to write an object (801). The write request received from the user (or the user application running on the host computer) can include the user's key. The virtual storage layer determines whether the object is huge or large using, for example, Equation 8 and Equation 9 (802). For large or large objects, the virtual storage layer determines the chunk size per chunk and per band and the number of chunks, eg, using Equation 3 and Equation 4 (811), across data storage devices Write data to one or more bands (812) and complete the write procedure (815).

  If the virtual storage layer determines that the object is neither large nor large, the virtual storage layer determines 803 whether the object is small using, for example, Equation (7). For small objects, the virtual storage layer determines (813) one or more storage devices for storing data, including original data and replicated data, based on the distribution policy (813), Write data across one or more devices (814) and complete the write procedure (815). For example, a virtual storage layer can use a band priority policy (distributing data across multiple data storage devices). The virtual storage layer can determine the start device using the hash value of the user's key.

  If the virtual storage layer determines that the object is neither large nor large nor small, the virtual storage layer treats the object as medium sized (804) and includes original data and replicated data based on the distribution policy Determine one or more data storage devices for storing data (813), write data to one or more devices in the band (814), and complete the write procedure (815) .

The procedure (812) of writing data to one or more bands through the data storage device can include several sub-processes.
Referring to FIG. 9, first, the virtual storage layer determines whether there is a slice for writing (820). If a slice for writing does not exist, the virtual storage layer stores an error log, completes the operation, and broadcasts a request for writing an object. The user application and / or the host computer operating on the host computer Inform the operating system. If a slice for writing exists, the virtual storage layer creates a slice of the object and generates an internal key for the chunk of the slice (821).
The virtual storage layer checks if this is the last slice for writing (822). For the last slice, the virtual storage layer adds paddings to the chunks of data if the slice can not fill the band full, and uses an erasure coding algorithm to P parity chunks for the band Calculate (824). The virtual storage layer omits the padding procedure 823 for other slices other than the last slice. 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 any one of split priority or band priority policy. The virtual storage layer writes 826 the data and parity chunks in the band along with the internal key generated at 821 to one or more storage devices.

  Because the virtual storage layer does not maintain object metadata, such as user keys and value sizes, does the virtual storage layer have small, large, or large objects to read? Can not recognize Accordingly, the virtual storage layer broadcasts a read request to all data storage devices (eg, (D + P) data storage devices) of the virtual storage 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 characteristics of the groups supported by the data storage device, the virtual storage layer can handle read and write operations in different ways.

Giant objects can be leaded in different ways based on the support of group features by the data storage device. If the virtual storage data storage device supports the group feature, the virtual storage layer broadcasts the user key to all the data storage devices with BID = “do_not_care”. In response, if there is no error in response to the broadcast, each of the (D + P) data storage devices returns the NC _Oi chunks for that split. Thereafter, the virtual storage layer classifies the received chunks into a total of NC _Oi bands per their band ID, and arranges the bands in ascending order of band IDs.
As long as the virtual storage layer receives D chunks of the same size for each band, the virtual storage layer can reconfigure the bands. If the total number of chunks received for the band is less than the number of data storage devices (D) or the chunk sizes are not the same, an error occurs. This error may be generated by a read of non-existent object, or by an unrecoverable error if all data storage devices return a "NOT_EXIST" error. it can. The virtual storage layer reassembles bands one by one and then reassembles objects from the bands.

  If the virtual storage data storage device does not support the group feature, the virtual storage layer broadcasts the user key with BID = 0 to all data storage devices to read the huge object. In response, each of the (D + P) data storage devices returns one chunk from the first band (Band_0). The virtual storage layer can identify the number of bands for an object by checking the metadata stored with part of the received chunks. The virtual storage layer subsequently reconstructs all the bands one by one in ascending order of band ID and reconstructs the object using the bands. In some embodiments, the virtual storage layer can reconstruct objects as if the group is supported by requesting all of the remaining bands asynchronously.

The procedure for reading large objects is similar to the procedure for reading large objects, except that the band is single. If the data storage device supports the group feature, the virtual storage layer broadcasts the user key to all data storage devices with BID = “do_not_care”. In response, each of the (D + P) data storage devices returns one chunk of that split.
As long as the virtual storage layer receives D chunks of the same size, the virtual storage layer can reconfigure the band or object. If the total number of chunks received for the band is less than the number of data chunks (D) or the chunk sizes are not the same, an error occurs. This error can be caused by a read of a non-existing object where all data storage devices return a “NOT-EXIST” (non-existing) error, or an unrecoverable error. .

  If the virtual storage data storage device does not support the group feature, the virtual storage layer broadcasts the user key with BID = 0 to all data storage devices to read large objects. In response, each of the (D + P) data storage devices returns one chunk in the band (BID = 0). The virtual storage layer identifies the existence of only one band for large objects by checking the metadata stored with the received chunks, and reconstructs the objects by reconstructing the bands. It can be configured.

  The procedure for reading small objects is similar to the procedure for reading large objects except that it depends on duplication. If the data storage device supports group features, the virtual storage layer broadcasts the user key to all data storage devices with BID = “do_not_care”. In response, each of the (D + P) data storage devices returns a response. Because the object is small, some data storage devices can return a “NOT_EXIST” error, while other data storage devices return chunks. The virtual storage layer uses the chunks received from one or more data storage devices to receive valid chunks that can reconfigure the object. If all data storage devices return a "NOT_EXIST" error, the object identified by the read request may be an absent object or an unrecoverable error may occur.

  If the virtual storage data storage device does not provide group features, the virtual storage layer broadcasts the user key with BID = 0 to all data storage devices to lead small objects. In response, each of the (D + P) data storage devices returns a response. The virtual storage layer can use several valid chunks received from any data storage device to identify if the object is small. Small objects do not maintain additional metadata.

  FIG. 10 shows an exemplary flow chart for leading an object, according to one embodiment. The virtual storage layer receives a read request for an object (901). The read request received from a user (or a user application operating on a host computer) may include the user's 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 objects. If group features are supported, the virtual storage layer broadcasts a read request to all data devices with an internal key with BID = "do_not_care" (903), otherwise BID = 0 for all. Set to the data storage device (904). The virtual storage layer receives chunks from any one of the data storage devices (905). If there is an error in the received chunk (906), the virtual storage layer determines if the group feature is supported (907), and if the group feature is not supported, it recovers the chunk metadata (908) If the group feature is supported, the virtual storage layer continues to determine the size of the object.

  If the virtual storage layer determines that the object is huge or large (909), the virtual storage layer further checks if the entire object has been reconstructed (910), one or more data storage devices Continue to restructure slices one by one (912), using the chunks received from C, until the entire object is rebuilt, to complete the read procedure (913). For small objects, the virtual storage layer restructures the object using chunks received from one or more data storage devices (911).

The procedure (911) for reconstructing small objects may include several sub-processes.
Referring to FIG. 11, the virtual storage layer first checks 921 if the received chunk is small. The virtual storage layer anticipates small chunks for small objects, but if large chunks are received, the virtual storage layer generates an error (924). If the virtual storage layer determines that the received chunk is valid (922), the virtual storage layer uses the received chunk to reconstruct a small object (923), otherwise The virtual storage layer receives chunks from other data storage devices (925).

The procedure for reconstructing a slice (912) may include several sub-processes.
Referring to FIG. 12, the virtual storage layer checks if all D chunks for reconfiguring a slice have been received (931). If so, the virtual storage layer reconstructs the slice using the erasure coding algorithm with D chunks (935). If not, the virtual storage layer checks if 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 to receive them from other data storage devices (933) and repeats the procedure until it has received all D chunks that reconfigures the slice . If the received chunk is not for a large object or a large object (eg, if the chunk is for a small object), the virtual storage layer generates an error (936).

According to one embodiment, a data storage system includes a plurality of data storage devices that store a plurality of objects of key-value pairs, and an erasure coding scheme and a data replication scheme based on the object size of each of the plurality of objects. It includes virtual storage layers that apply different data reliability schemes. The plurality of objects includes a first object having a first size and a second object having a second size larger 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 across any one or more of the plurality of data storage devices.
The virtual storage layer classifies the second object as a giant object, divides the giant object into one or more chunks of the same size, and applies the erasure coding scheme to the one or more chunks. Chunks are distributed and stored across the plurality of data storage devices.

  The distribution scheme is such that the virtual storage layer splits the one or more chunks of the giant object to each of the plurality of data storage devices, and the plurality of data storage devices are spread over the plurality of data storage devices. There may be a split priority distribution scheme that stores one or more of the split chunks in each of the data storage devices.

  The distribution scheme is different from the split priority distribution described above, in the virtual storage layer until the one or more chunks of the giant project are all stored in the one or more data storage devices. In each of a plurality of data storage devices, there may be a band-first distribution scheme in which one chunk of the huge object is stored.

  The virtual storage layer can further classify a third object having a third size as a large object, divide the large object into one or more chunks of the same size, apply the erasure coding scheme, and The divided one or more chunks are distributed and stored across multiple data storage devices. The third size is larger than the first size and smaller than the second size. The large object contains only one band, ie only one chunk in one split.

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

  Each of the above objects 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 each band among a plurality of bands. Each of the plurality of bands includes any one of one or more chunks distributed across the plurality of data storage devices.

  The virtual storage layer may use start data for writing or reading a first chunk of the one or more chunks of the plurality of data storage devices using a hash value of the user key. Identify storage devices.

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

  The plurality of data storage devices can support the feature of the group, and the virtual storage layer sets the band identifier to a bit of arbitrary data when reading the giant object, and goes to the plurality of data storage devices Can be broadcast.

  The plurality of data storage devices may not support a group feature, in which case the virtual storage layer identifies the band identifier as unique when reading the giant object. A band identifier can be set and broadcast to the plurality of data storage devices.

  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 accessing an object of a key-value pair comprises: receiving a plurality of objects of a key-value pair, wherein the plurality of objects comprises a first object having a first size; Including a second object having a second size greater than the first size, classifying the first object as a small object, applying a data replication scheme to the small object, and converting the small object to a plurality of data Storing over any one or more of the storage devices, classifying the second object as a giant object, and dividing the giant object into one or more chunks of the same size And the huge object Comprising applying a coded scheme, and storing said plurality of data the over the storage device one or more chunks dispersing the, the.

  The method comprises the steps of receiving a write request to the object, determining whether the object is the giant object, and determining a chunk size and number of chunks for the giant object. The method may further comprise the steps of: 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 generates a slice including one chunk for each of the plurality of data storage devices of the one or more chunks, and the one or more chunks included in the slice. Generating, for each, an internal key using a user key with a band identifier attached, and the one or more chunks corresponding to the slice, using the erasure coding scheme, and Generating a band including one or more parity chunks; determining the plurality of data storage devices storing the band based on one of a split priority scheme and a distributed scheme including a band priority scheme; And write the one or more chunks to the band along with the internal key. Tsu and up, the further can include.

  The method includes any one of a step of receiving a write request to the object, a step of determining whether the object is the small object, and a distributed method including a split priority method and a band priority method. Determining a subset to store the one or more chunks of the small object of the plurality of data storage devices based on the plurality of data storage devices; and the small object in the subset of the plurality of data storage devices Writing the one or more chunks of

  The method includes receiving a read request to the object including the user key; determining whether the plurality of data storage devices support group features; and the internal key Broadcasting the read request towards the plurality of data storage devices.

  If the group feature is supported, the band identifier of the internal key may be set to an arbitrary data bit.

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

  The method comprises the steps of receiving at least one chunk from each of the plurality of data storage devices, and re-slicing slices from the at least one chunk received from the plurality of data storage devices using the erasure coding scheme. And B. further comprising the steps of:

  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 illustrate various embodiments embodying data storage systems capable of efficiently storing objects having different sizes and methods 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. The matters intended from the technical idea of the present invention are described in the following claims.

  The present invention is useful for highly reliable data storage systems that efficiently store objects of different sizes without performance limitations or space limitations.

110, 310, 410, 510, 610, 710 Object 120, 121, 321 Virtual storage 151 Split 200 Internal key 201, 301, 401 User key 202, 402 Band identifier 302 Band identifier (= 'do_not_care')
350 bands

Claims (20)

A data storage system,
Multiple data storage devices that store multiple objects of key-value pairs;
A virtual storage layer applying different data reliability schemes, including a data replication scheme and an erasure coding scheme, based on the object size of each 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 scheme, stores the small object across any one or more of the plurality of data storage devices,
The virtual storage layer classifies the second object as a giant object, divides the giant object into one or more chunks of the same size, and applies the erasure coding scheme to the plurality of data storage devices. A data storage system, characterized in that it stores the one or more chunks in a distributed manner throughout. The virtual storage layer stores the one or more chunks of the giant object across the plurality of data storage devices in a split priority manner;
In the split priority scheme, the virtual storage layer stores some of the one or more chunks of the giant object in any one of the plurality of storage devices, and the giant object The other one (others) of the one or more chunks is stored in another one of the plurality of storage devices. Data storage system as described in. The virtual storage layer stores the one or more chunks of the giant object across the plurality of data storage devices in a band first manner;
The band priority scheme is configured such that the virtual storage layer stores one chunk of the huge object until the virtual storage layer stores all the one or more chunks of the huge object in the plurality of data storage devices. The data storage system according to claim 1, wherein the data storage system is a method of storing data in each of the data storage devices. The virtual storage layer further classifies a third object having a third size as a large object, divides the large object into one or more chunks of the same size, applies the erasure coding scheme, Storing one or more chunks distributed among the plurality of data storage devices,
The third size is larger than the first size and smaller than the second size, and the large object includes only one band, that is, only one chunk in one split. The data storage system according to claim 1. The virtual storage layer further classifies a fourth object having a fourth size as a medium-sized object,
The fourth size is larger than the first size and smaller than the third size,
5. The data storage system according to claim 4, wherein the virtual storage layer applies any one of the data duplication method and the erasure coding method. Each of the plurality of objects is identified using a user key;
The virtual storage layer generates an internal key including a band identifier for the giant object and the user key,
The band identifier is used to identify each band among a plurality of bands, and each of the bands is distributed over the plurality of data storage devices. The data storage system of claim 1, comprising any one of the one or more chunks.   The virtual storage layer uses a hash value of the user key to read or write a first chunk of the one or more chunks, and a start data storage device among the plurality of data storage devices The data storage system according to claim 6, characterized in that   The data storage system of claim 1, wherein the plurality of data storage devices comprises one or more dedicated parity data storage devices that store parity chunks associated with the large objects. .   The plurality of data storage devices support group features, and the virtual storage layer sets the band identifier to a bit of arbitrary data toward the plurality of data storage devices when reading the giant object. 7. A data storage system according to claim 6, characterized in that it is broadcasted.   Without supporting the group feature of the plurality of data storage devices, the virtual storage layer sets the band identifier to a unique band identifier toward the plurality of data storage devices when reading the giant object. 7. A data storage system according to claim 6, characterized in that it is broadcast. The data storage system according to claim 1, wherein each of the plurality of data storage devices is a key-value solid-state drive (KV_SSD: key-value solid-state drive).
A method of accessing an object of a key-value pair,
Receiving a plurality of objects of the key-value pair;
Here, the plurality of objects include a first object having a first size and a second object having a second size larger than the first size,
Classifying the first object as a small object;
Applying a data replication scheme to the small object;
Storing the small object across any one or more of a plurality of data storage devices;
Classifying the second object as a giant object;
Dividing the giant object into one or more chunks of the same size;
Applying an erasure coding scheme to the giant object;
Storing the one or more chunks in a distributed manner across the plurality of data storage devices. Receiving a write request to the object;
Determining whether the object is the giant object;
Determining a chunk size and the number of chunks for the huge object;
The method according to claim 12, further comprising writing the one or more chunks of the huge object to the plurality of data storage devices based on the chunk size and the number of chunks. The method described. Generating a slice containing one chunk for each of the plurality of data storage devices of the one or more chunks, and for each of the one or more chunks included in the slice Generating an internal key using a user key with a band identifier attached,
Generating a band comprising the one or more chunks corresponding to the slice and one or more parity chunks using erasure coding;
Determining a plurality of data storage devices to store the band based on any of a split priority scheme and a distributed scheme including a band priority scheme;
The method of claim 13, further comprising: writing the one or more chunks in the band with the internal key. Receiving a write request for the object;
Determining whether 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 any of a distributed scheme including a split priority scheme and a band priority scheme;
The method of claim 12, further comprising writing the one or more chunks of the small object to the subset of the plurality of data storage devices. Receiving a read request for the object including the user key;
Determining whether the plurality of data storage devices support group features;
Broadcasting the read request with the internal key towards the plurality of data storage devices.   The method according to claim 16, wherein the band identifier of the internal key is set to an arbitrary data bit if the group feature is supported.   The method according to claim 16, wherein if the group feature is not supported, the band identifier of the internal key is set to a unique band identifier. Receiving at least one chunk from each of the plurality of data storage devices;
The method of claim 16, further comprising reconstructing a slice from at least one chunk received from the plurality of data storage devices using the erasure coding scheme. The method of claim 12, wherein each of the plurality of data storage devices is a key-value solid-state drive (KV_SSD).

Images