KR102306672B1 - Storage System Performing Data Deduplication and Operating Method of Storage System and Data Processing System - Google Patents

Abstract

Disclosed are a storage system that performs data deduplication, a storage system, and a method of operating a data processing system. A storage system according to an aspect of the inventive concept receives an index generated from the data together with data from a storage device and a host for storing data, mapping information between the index and a physical address, and corresponding to the index a controller including a memory for storing a reference count, wherein the controller determines the mapping information read from the memory or the reference count according to the index received from the host so that the data received from the host corresponds to duplicate data Deduplication processing is performed by determining whether to do so, and updating the reference count when the received data corresponds to duplicate data.

Description

Storage System Performing Data Deduplication and Operating Method of Storage System and Data Processing System

The technical idea of the present disclosure relates to a storage system, and more particularly, to a storage system for performing data deduplication, a storage system, and an operating method of the data processing system.

Data deduplication technology determines whether data to be stored in the storage system is previously stored in the storage system, and when it is determined that the data is stored as redundant, the duplicate data is not stored in the system but is converted to already stored data. It is a technology that enables efficient use of storage space by managing only the links of Since such deduplication technology can improve the use efficiency of the storage system, it is required for a storage system for large-capacity data.

However, in order to use the deduplication technology, various information such as data (or hash index) and a storage location (eg, logical/physical address) of data corresponding thereto must be managed, and it is necessary to manage the information for deduplication. The problem of increasing resources arises.

US Patent Registration Publication US 8,751,763 US Patent Application Publication No. US 2017/0249327

SUMMARY OF THE INVENTION An object of the present invention is to provide a storage system, a storage system, and an operating method of a data processing system capable of reducing a management burden of information related to deduplication.

In order to achieve the above object, a storage system according to an aspect of the technical idea of the present disclosure receives an index generated from the data together with data from a storage device and a host for storing data, and includes an index and a physical address a controller comprising a memory for storing mapping information of and a reference count corresponding to the index, wherein the controller determines the mapping information or the reference count read from the memory according to the index received from the host, whereby the host It is characterized in that by determining whether the received data corresponds to duplicate data, and by updating the reference count when the received data corresponds to duplicate data, deduplication processing is performed.

Meanwhile, in an operating method of a storage system according to an aspect of the technical concept of the present disclosure, receiving first data and a first index generated from the first data from a host; Determining whether the index is the same as the index corresponding to the data previously stored in the system, and when the same index as the first index exists, the reference stored in the storage system in advance without writing the first data according to data deduplication updating a count and providing the updated reference count to the host.

On the other hand, in the operating method of the data processing system according to an aspect of the technical idea of the present disclosure, the data processing system includes a storage system, an index generated using data from an external system and a storage location of the data Storing mapping information of the indicated physical address in the storage system; receiving a write request including data and an index corresponding to the data in the storage system; in the storage system, the write request is duplicated determining whether the write request for data is a write request; and when it is determined that the write request is a write request for redundant data, performing deduplication processing by updating a reference count stored in the storage system. do.

According to the operating method of the storage system, the storage system, and the data processing system of the technical idea of the present invention, by reducing the amount of information managed in relation to data deduplication, it is possible to reduce the memory for storing information, and also It has the effect of improving the processing speed.

In addition, according to the operating method of the storage system, the storage system, and the data processing system of the technical idea of the present invention, since the subject of the determination of deduplication and the determination of data collision can be set in various ways, there is an effect that the method of operating the system can be diversified. .

1 is a block diagram illustrating a data processing system according to an exemplary embodiment of the present invention.
2 and 3 are block diagrams illustrating specific implementation examples of a data processing system.
4 is a block diagram illustrating an example of functions performed by a host of the data processing system of the present invention.
5 is a block diagram illustrating an implementation example of a storage system according to an embodiment of the present invention.
6 is a block diagram illustrating an example of various modules stored in the operation memory of FIG. 5 .
7A and 7B are diagrams illustrating examples of information managed by a host and a storage system according to embodiments of the present invention.
8 is a block diagram illustrating an example of data write and read operations of the data processing system according to an embodiment of the present invention.
9 is a flowchart illustrating a method of operating a host according to an exemplary embodiment of the present invention.
10 is a flowchart illustrating a method of operating a storage system according to an exemplary embodiment of the present invention.
11 to 18 are diagrams illustrating examples of communication between a host and a storage system in the data processing system of the present invention.
19 is a block diagram illustrating a network system including a server system according to an embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram illustrating a data processing system according to an exemplary embodiment of the present invention.

Referring to FIG. 1 , a data processing system 10 may include a host 100 and a storage system 200 . Also, the storage system 200 may include a controller 210 and a storage device 220 . Also, according to an exemplary embodiment of the present invention, the host 100 may include the index generator 110 , and the controller 210 of the storage system 200 may include the index table 211 . In the example of FIG. 1 , the index table 211 is illustrated as being provided in the controller 210 , but the embodiment of the present invention is not limited thereto. For example, the index table 211 may be stored in a memory disposed outside the controller 210 in the storage system 200 .

The data processing system 10 may include storage media for storing data according to a request from an external system (eg, a computing node). As an example, the storage system 200 may include one or more solid state drives (SSDs). When the storage system 200 includes a solid state drive, the storage system 200 may include a plurality of flash memory chips (eg, NAND memory chips) that nonvolatilely store data. Alternatively, the storage system 200 may correspond to one flash memory device. Alternatively, the storage system 200 may correspond to a memory card including one or more flash memory chips.

When the storage system 200 includes a flash memory, the flash memory may include a 2D NAND memory array or a 3D (or vertical) NAND (VNAND) memory array. The 3D memory array is a monolithic array of memory cells having an active area disposed over a silicon substrate, or at least one physical level of circuitry formed on or within the substrate as circuitry associated with the operation of the memory cells. is formed with The term "monolithic" means that the layers of each level constituting the array are stacked directly on top of the layers of each lower level of the array.

In an embodiment of the inventive concept, the 3D memory array includes vertical NAND strings arranged in a vertical direction such that at least one memory cell is positioned on top of another memory cell. The at least one memory cell may include a charge trap layer.

US Patent Application Publication Nos. 7,679,133, 8,553,466, 8,654,587, 8,559,235, and US 2011/0233648 disclose that a 3D memory array is constructed in multiple levels and contains word lines and/or Those detailing suitable configurations for a 3D memory array in which bit lines are shared between levels are incorporated herein by reference.

As another example, the storage system 200 may include other various types of memories. For example, the storage system 200 may include a nonvolatile memory, which includes a magnetic RAM (MRAM), a spin-transfer torque MRAM (MRAM), a conductive bridging RAM (CBRAM), and a FeRAM (FeRAM). Ferroelectric RAM), PRAM (Phase RAM), Resistive RAM, Nanotube RAM, Polymer RAM (PoRAM), Nano Floating Gate Memory (NFGM), Holographic Memory Various types of memories, such as a holographic memory, a molecular electronic memory, or an insulator resistance change memory, may be applied.

The host 100 may perform a data management operation in the data processing system 10 . As an example, the host 100 may provide a request to write or read data to the storage system 200 . Also, in response to a data erase request from the host 100 , the storage system 200 may perform an erase operation on data in an area indicated by the host 100 .

The host 100 may communicate with the storage system 200 through various interfaces. The host 100 may include various types of devices capable of accessing data to the storage system 200 . For example, the host 100 may be an application processor (AP) that communicates with the flash memory-based storage system 200 . According to an embodiment, the host 100 is a Universal Serial Bus (USB), MultiMediaCard (MMC), PCI-E (PCIExpress), ATA (AT Attachment), SATA (Serial AT Attachment), PATA (Parallel AT Attachment), It may communicate with the storage system 200 through various interfaces, such as a small computer system interface (SCSI), a serial attached SCSI (SAS), an enhanced small disk interface (ESD), and an integrated drive electronics (IDE).

According to one embodiment, data processing system 10 may employ data deduplication techniques. When the deduplication technology is applied, when the data requested to be written is duplicated (or identical to) the data previously stored in the storage system 200, instead of storing the data requested to be written in duplicate, the previously stored data By managing only the link of data, the processing of the write request can be completed. Accordingly, the storage space of the storage system 200 may be efficiently used.

In order to determine whether the write-requested data is duplicate data, an index table may be managed in the storage system 200 . According to an embodiment, the index generator 110 of the host 100 may generate an index corresponding to the write-requested data and provide it to the storage system 200 . The index may have information for identifying the data, and as an example, an index having a unique value for each data may be generated and provided to the storage system 200 . .

The index generator 110 may be implemented in various ways. For example, the index generator 110 may include an arithmetic circuit implemented in hardware. Alternatively, the index generator 110 may be implemented as software that performs an arithmetic function. According to an embodiment, the index generator 110 may correspond to a hash engine that calculates a hash value as an index through an operation using a hash function on data. If the index generator 110 corresponds to a hash engine, the index generator 110 is GOST, HAVAL, MD2, MD4, MD5, PANAMA, RadioGatun, RIPEMD, RIPEMD-128/256, RIPEMD-160, RIPEMD-320, SHA Hash values can be calculated using various hash algorithms such as -0, SHA-1, SHA-256/224, SHA-512/384, SHA-3, and WHIRLPOOL.

When a write request is made, the storage system 200 may receive data, and may also receive an index generated from the data as information for identifying the data. During a data write operation, the controller 210 of the storage system 200 maps an index and a physical address (eg, a physical block address (PBA)), and places data in a position corresponding to the mapped physical address (PBA). (Data) can be saved. Also, mapping information between the index and the physical address PBA may be stored and managed in the index table 211 .

According to an embodiment, the host 100 does not need to execute a file system for managing data in a file unit or for generating a logical address for the storage system 200 , and the host 100 can The corresponding index may be provided to the storage system 200 as information for data recording. Also, when the storage system 200 includes a flash memory, the controller 210 may include a Flash Translation Layer (FTL) to provide an interface between the host 100 and the storage device 200 , The address mapping operation through ? may perform mapping between an index (Index) and a physical address (PBA).

An example of an operation related to data deduplication according to an embodiment of the present invention will be described as follows.

As data recording is requested from the external system, the host 100 may receive data and a corresponding logical address (not shown) from the external system. Also, an index generated by the index generator 110 may be stored in the host 100 . As an example, the host 100 may include a memory (not shown), and an index may be aligned with a received logical address and stored in the memory as a tree structure.

The storage system 200 receives data and an index from the host 100 , determines whether data is duplicated using the index, and performs deduplication processing according to the determination result. can be done As an example, the storage system 200 compares whether an index received from the host 100 is the same as an index corresponding to data previously stored in the storage system 200 , and thus whether data is duplicated. can be judged

In determining whether data is duplicated using the index, when the previously received index is stored in the index table 211 , the received index is compared with the index stored in the index table 211 . Data duplication may be determined through the operation. When the same index (Index) does not exist in the index table 211, the storage system 200 may store the data (Data) at a location indicated by the physical address (PBA) newly mapped to the received index (Index). have. On the other hand, when the same index as the received index Index exists in the index table 211 , the storage system 200 determines that the received data Data is duplicate data, and the data By not storing in the storage device 220, the deduplication process may be performed.

As data recording based on deduplication is performed, data previously stored in the storage system 200 may be referenced (or accessed) by a plurality of logical addresses from an external system. According to an embodiment, the storage system 200 may further store count information (eg, a reference count) in order to manage the referenced number of times of previously stored data (Data). As an example, the reference count may be stored in the index table 211 ) can be stored and managed. According to an embodiment, when the data (Data) requested to be written from the host 100 corresponds to duplicate data, the storage system 200 performs an update operation on the reference count and information indicating that the deduplication process has been performed. together with the updated reference count may be provided to the host 100 .

As a deformable embodiment, the physical address (PBA) and the reference count may be sorted and stored in an index (Index) in the index table 211, and according to an embodiment, actual information of the index (Index) may be stored in the index table 211 ) may not be saved. Determination of the above-described duplicate data may be performed by various methods, and as an example, whether duplicate data is determined by checking information (eg, physical address and/or reference count) stored in alignment with a received index. it might be

According to the above embodiment, the host 100 may directly provide the index generated by processing the data to the storage system 200 as information for writing/reading the data. Therefore, the amount of information managed for data deduplication may be reduced, and a memory space for storing information in the host 100 may be reduced. For example, in a general case, the host 100 needs to separately manage mapping information between an index and a file ID (or a logical block address for the storage system 200 ) through operation of a file system, etc. According to an embodiment of the present invention, data deduplication may be processed by the host 100 without storing and managing information according to the execution of the file system or the execution result.

2 and 3 are block diagrams illustrating specific implementation examples of a data processing system. In the following embodiments, it is assumed that the above-described index generator corresponds to a hash engine that generates a hash value, and that the index is a hash index. In addition, it will be assumed that the data processing system compresses and stores data from the outside, but embodiments of the present invention need not be limited thereto.

Referring to FIG. 2 , the data processing system 300A may include a host 310A and a storage system 320A, and may include data from an external system (eg, an external computing node) and corresponding logical addresses ( LBA) can be received. Assuming that the first to third logical addresses LBA 1 to LBA 3 and corresponding data Data have been previously provided from an external system, the first to third logical addresses LBA 1 to LBA 3 and Mapping information of the first to third hash indexes (Hash Index 1 to Hash Index 3) is stored in the host 310A, and the first to third hash indexes (Hash Index 1 to Hash Index 3) and the first to third Mapping information of the physical addresses PBA 1 to PBA 3 may be stored in the storage system 320A. Thereafter, it is assumed that a fourth logical address LBA 4 and corresponding data Data are provided from an external system, and a fourth hash index 4 is generated from the data Data.

The host 310A may include a hash engine 311A as an index generator, and may also include a memory 312A that stores the generated hash indexes. The hash engine 311A may generate a hash index having a plurality of bits corresponding to data of a predetermined size. The size of the data (Data) and the hash index may be defined in various ways, and as an example, a hash index of 128 bits may be generated from 4 kB of data (Data).

According to an embodiment, the first to third hash indexes (Hash Index 1 to Hash Index 3) may be arranged in the first to third logical addresses LBA 1 to LBA 3 and stored in the memory 312A. When a logical address LBA for writing or reading data is received from an external system, a pre-stored hash index corresponding to the logical address LBA may be read from the memory 312A.

Also, the storage system 320A may include a memory 321A and a compressor 322A for compressing data. As an example, the storage system 320A may generate a physical address PBA corresponding to the received hash index, and the memory 321A may store mapping information between the hash index and the physical address PBA in the form of a table. have. As an example, the first to third hash indexes Hash Index 1 to Hash Index 3 and the first to third physical addresses PBA 1 to PBA 3 may be stored together in the memory 321A. Alternatively, the first to third physical addresses PBA 1 to PBA 3 may be arranged in the first to third hash indexes Hash Index 1 to Hash Index 3 and stored in the memory 321A, at this time, The first to third hash indexes (Hash Index 1 to Hash Index 3) may not be actually stored in the memory 321A.

According to an embodiment, the memory 321A may further store a reference count Ref CNT corresponding to the hash index. For example, the memory 321A may further store reference counts Ref CNT 1 to Ref CNT 3 corresponding to the first to third hash indexes Hash Index 1 to Hash Index 3 . That is, in an embodiment of the present invention, the reference count Ref CNT may be managed in the storage system 320A.

An example of the data deduplication operation will be described as follows.

The host 310A may receive the fourth logical address LBA 4 and data corresponding thereto, and the hash engine 311A may generate a fourth hash index 4 from the data Data. have. Mapping information between the generated fourth hash index 4 and the fourth logical address LBA 4 may be stored in the memory 312A. Also, in providing the data write request to the storage system 320A, the host 310A may provide a fourth hash index 4 and corresponding data Data to the storage system 320A.

The storage system 320A may determine whether there is duplicate data by using a fourth hash index (Hash Index 4). For example, it may be determined whether any one of the first to third hash indexes (Hash Index 1 to Hash Index 3) corresponding to the previously stored data is the same as the fourth hash index (Hash Index 4). If the same hash index as the fourth hash index (Hash Index 4) does not exist in the memory 321A, the storage system 320A maps the fourth hash index (Hash Index 4) to the fourth physical address (PBA 4) and data (User Data) may be stored at a location indicated by the fourth physical address PBA 4 . Also, mapping information between the fourth hash index 4 and the fourth physical address PBA 4 may be stored in the memory 321A.

On the other hand, when it is determined that the fourth hash index (Hash Index 4) is the same as any one hash index (eg, the first hash index (Hash Index 1)), redundant storage of data through deduplication processing This is skipped, and the data Data corresponding to the first hash index 1 may be referred to by the fourth logical address LBA 4 . According to an embodiment, when the deduplication process is performed, the first reference count (Ref CNT 1) value corresponding to the first hash index (Hash Index 1) may be updated, and as an example, the first reference count ( The Ref CNT 1) value may be increased by 1. Also, according to an embodiment, an updated first reference count Ref CNT 1 may be provided from the storage system 320A to the host 310A together with information indicating that the deduplication process has been performed.

Meanwhile, FIG. 3 illustrates a case in which a compressor for compressing data is provided in the host, and as shown in FIG. 3 , the data processing system 300B includes a host 310B and a storage system 320B. The host 310B may include a hash engine 311B, a memory 312B, and a compressor 313B. Also, the storage system 320B may include a memory 321B that stores mapping information between a hash index and a physical address. The data processing system 300B shown in FIG. 3 may also perform data deduplication in the same manner as in the above-described embodiment, and as an example, the storage system 320B may be duplicated using a hash index provided from the host 310B. It may be determined whether there is data, and data deduplication may be performed according to the determination result.

Meanwhile, according to the above-described embodiments, a memory for storing various types of mapping information may be implemented as various types of memory, and as an example, dynamic random access memory (DRAM), static random access memory (SRAM), and T-RAM. (thyristor RAM), Z-RAM (zero capacitor RAM), or TTRAM (Twin Transistor RAM) may be implemented as a volatile memory.

4 is a block diagram illustrating an example of functions performed by a host of the data processing system of the present invention.

Referring to FIG. 4 , the data processing system 400 includes a host 410 and a storage system 420 , and the host 410 may include various modules implemented in hardware and/or software. For example, the host 410 may include a remote procedure calls (RPC) module 411 , a block service module 412 , a deduplication management module 413 , and a compression module 414 .

The RPC module 411 may communicate with another system (or another server), and, for example, may perform a function of calling another server for data transmission/reception. Also, the block service module 412 may perform a function for processing data management based on a block. In addition, the deduplication management module 413 may be provided to perform a part of the function for data deduplication at the host 410 end, and as an example, the deduplication management module 413 uses the data to generate a hash index It may include a hash engine that generates Also, the deduplication management module 413 may include a memory for storing mapping information between a logical address and a hash index from an external system. Also, the compression module 414 may compress data and provide it to the storage system 420 .

According to embodiments of the present invention, a hash index may be directly provided to the storage system 420 as information related to storage and reading of data. Accordingly, a file system for managing data on a file basis or a block layer for managing data whose size is changed through compression according to a size corresponding to a logical block does not need to be executed in the host 410 . That is, memory resources of the host 410 required in connection with data deduplication may be reduced, and system performance may be improved because at least some of the functions of the file system and/or block layer may not be executed. .

5 is a block diagram illustrating an implementation example of a storage system according to an embodiment of the present invention. The storage system may include a controller and a storage device, and the configuration shown in FIG. 5 corresponds to an implementation example of the controller.

Referring to FIG. 5 , a storage system 500 as a processor may include a central processing unit 510 , a host interface 520 , a memory interface 530 , and a working memory 540 . . According to an embodiment, the storage system 500 may further include a hash engine 550 . Also, the index table 541 may be stored in the operation memory 540 , and as a deformable embodiment, the index table 541 may be stored in another memory in the storage system 500 .

The central processing unit 510 may control the overall operation of the storage system 500 by executing various programs stored in the operation memory 540 . Software including various programs related to data deduplication along with functions of the storage system 500 may be loaded into the operation memory 540 . The operative memory 540 may be implemented as random access memory (RAM), read-only memory (ROM), Electronically Erasable Programmable Read Only Memory (EEPROM), flash memory, or other memory technology.

According to the above-described embodiment, the host may generate a hash index for data from an external system and provide it to the storage system 500 . The storage system 500 may further include a hash engine 550 , and according to an embodiment, the hash engine 550 may additionally perform a hash operation on the hash index or data provided from the host. That is, as the hash engine 550 is further provided in the storage system 500 , the amount of information stored in the storage system 500 may be further reduced.

A more specific configuration and operation of the present invention will be described with reference to FIGS. 5 and 6 as follows. 6 is a block diagram illustrating an example of various modules stored in the operation memory of FIG. 5 . When the storage system 500 includes a flash memory, various modules illustrated in FIG. 6 may be defined as components included in the FTL.

In the operation memory 540 , the above-described index table 541 is stored, and modules performing various functions by the execution of the central processing unit 510 may be stored. As an example, the address translation module 542 , the deduplication control module 543 , and the data management module 544 may be further stored in the operation memory 540 .

The address translation module 542 converts the hash index provided from the host into a physical address. As an example, mapping information between a hash index and a physical address may be stored in the index table 541 . As in the above example, the index table 541 may store physical addresses in a form sorted according to the hash index, and the physical address corresponding to the hash index provided from the host may be read from the index table 541 . .

The deduplication control module 543 may perform various functions to prevent duplicate data from being stored. As an example, the deduplication control module 543 may determine whether the write-requested data corresponds to duplicate data by checking the hash index provided from the host and information stored in the index table 541 . In addition, the deduplication control module 543 may perform an operation for storing and managing the reference count information in the index table 541. As an example, when the same hash index as the hash index from the host exists, the same hash The reference count value corresponding to the index may be updated.

Meanwhile, the data management module 544 may perform various data management operations, and as an example, may perform a data management operation in a flash memory. According to an embodiment, the data management module 544 may perform a data management operation using information related to data deduplication. For example, the data management operation may be adjusted according to the value of the reference count stored in the index table 541 , and as an example, various management operations such as data movement, backup, garbage collection, etc. may be performed based on the reference count value. will be able

In the above-described embodiments of FIGS. 5 and 6, an example in which the deduplication processing according to embodiments of the present invention is performed by software is illustrated, but the embodiment of the present invention is not limited thereto. As an example, at least some of the functions for deduplication processing may be implemented by hardware or a combination of hardware and software.

7A and 7B are diagrams illustrating examples of information managed by a host and a storage system according to embodiments of the present invention. 7A illustrates a general case of determining data redundancy at the host side, and FIG. 7B illustrates an example of determining data redundancy at the storage system side according to an embodiment of the present invention.

Referring to FIG. 7A , the host receives logical addresses (LBA 1 to LBA 3) and corresponding data from an external system, and generates an index (eg, a hash index, Hash Index 1 to Hash Index 3) for the data. can Also, mapping information of logical addresses (LBA 1 to LBA 3) and hash indexes (Hash Index 1 to Hash Index 3) may be stored and managed in a memory.

In addition, the host may operate a file system to access the storage system, and after deduplication is performed, hash indexes (Hash Index 1 to Hash Index 3) and corresponding file information (eg, file ID, File ID 1) ~ File ID 3) can be saved in memory. Also, reference counts Ref CNT 1 to Ref CNT 3 may be further stored in correspondence with the hash indexes Hash Index 1 to Hash Index 3 and file information File ID 1 to File ID 3 . In addition, the host provides logical addresses (LBA S1 to LBA S3) to the storage system through the file system, and the storage system provides logical addresses (LBA S1 to LBA S3) and physical addresses (PBA 1 to PBA 3) to the storage system. of mapping information can be stored. That is, the host can perform data deduplication by performing double table management, which increases memory usage and also increases information retrieval time.

On the other hand, as shown in FIG. 7B , according to an embodiment of the present invention, the host maps logical addresses (LBA 1 to LBA 3) from an external system and corresponding hash indexes (Hash Index 1 to Hash Index 3). Only information can be managed. Accordingly, the host does not need to manage the double table, and the information processing burden at the host end can be reduced.

The host provides the hash index (Hash Index 1 ~ Hash Index 3) to the storage system, and the storage system stores the mapping information between the hash index (Hash Index 1 ~ Hash Index 3) and the physical address (PBA 1 ~ PBA 3) and manage. Also, the storage system may further store the hash indexes Hash Index 1 to Hash Index 3 and reference counts Ref CNT 1 to Ref CNT 3 corresponding to the physical addresses PBA 1 to PBA 3 .

8 is a block diagram illustrating an example of data write and read operations of the data processing system according to an embodiment of the present invention. In the embodiment shown in FIG. 8 , the storage system 620 is an SSD including NAND memory, and a key-value SSD is exemplified.

A data processing system according to an embodiment may include a plurality of storage systems, one or more storage systems are configured as key-value storage, and actual data is stored in another storage system. This can be operated. As an example, a key-value storage is configured with a low-spec node and an SSD having low computing power, and external clients may access the key-value storage and request storage and reading of data. At this time, the storage system 620 may receive a key as an index in the above-described embodiment, and may also receive a value as data. Also, similar to the above-described embodiment, a key may be generated through a hash operation on data provided from an external system.

Referring to FIG. 8 , the data processing system 600 includes a host 610 and a storage system 620 , and according to the above-described embodiments, the storage system 620 stores and manages a key as an index. and data deduplication can be performed using the stored key.

The host 610 may receive a data write and read request. As an example of a write operation, a key may be generated through a hash operation on data (User Data), and a value corresponding to compressed data may be generated through compression processing on data (User Data). can In addition, a write request (Put(Key, Value)) and a read request (Get(Key)) may be generated through the key and value interface command processing, and the requests (Put(Key, Value)) may be generated. ), Get(Key)) may be provided to the storage system 620 through the SSD device driver.

The storage system 620 may perform a write/read operation based on deduplication by using the received key and value. For example, the storage system 620 may determine whether data is duplicated by referring to the received key and information stored in the index table. For example, assuming that it is determined whether the received key and pre-stored keys are identical to each other, if the same key does not exist, the storage system 620 may store the received key and Mapping information of the corresponding physical address PBA may be additionally stored in the index table, and a value may be stored in a location indicated by the physical address PBA in the NAND memory. As one storage example, a received key, a value, and meta data corresponding thereto may be stored together in a NAND page of a NAND memory.

According to an embodiment, a reference count may be further stored in the index table, and when the same key exists, the same key and the same key are not repeatedly stored in the NAND memory. The data write operation can be completed by updating the reference count corresponding to (Key). In addition, according to an embodiment, a hash operation processing may be further performed in the storage system 620 for a key and a value, and at this time, the key stored in the storage system 620 . and the size of Value may be further reduced.

On the other hand, taking the read operation as an example, the host 610 generates a key corresponding to data (User Data) through a hash engine, and uses the generated key as information for data readout by the storage system 620 ) can be provided. For example, a read request Get(Key) together with a key may be provided to the storage system 620 through the SSD device driver.

The storage system 620 receives a read request (Get(Key)) of data (User Data) corresponding to a key (Key), and determines a physical address (PBA) mapped to a key (Key) through an index table. and data at a location indicated by the physical address PBA can be read. According to an embodiment, a value corresponding to data among information stored in the NAND memory may be read and provided to the host 610, and the host 610 decompresses the data (Value) User Data) can be restored.

9 is a flowchart illustrating a method of operating a host according to an exemplary embodiment of the present invention.

Referring to FIG. 9 , the host receives a logical address LBA and data corresponding thereto as an address on the external system side ( S11 ). The host may create an index through arithmetic processing on data, and store the created index in the host (S12). As an example, the host may generate a hash index using a hash function, and align the generated hash index to the logical address and store it in a memory.

The host provides data and a corresponding index to the storage system (eg, SSD) (S13). The storage system may perform a write operation to which data deduplication is applied according to a write request from the host, and according to an embodiment, when data deduplication is performed, the host may receive reference count information from the storage system ( S14). The received reference count information may be used for subsequent data management operations.

10 is a flowchart illustrating a method of operating a storage system according to an exemplary embodiment of the present invention.

The storage system may receive data and a corresponding index from the host (S21), and search information previously stored in the index table for data deduplication (S22). In addition, according to the search result, it may be determined whether information stored in alignment with the received index or whether the same index as the received index exists may be determined, and the data received from the host according to the determination result It can be determined whether the overlap of (S23).

When it is determined that the data is not duplicate, the storage system may generate a physical address PBA corresponding to the received index Index and store mapping information between the index Index and the physical address PBA ( S24 ). . Also, since the same index does not exist, it is determined that the data provided from the host is initially stored in the storage system, and accordingly, the data may be stored at a location corresponding to the physical address PBA (S25). ).

On the other hand, if it is determined that the data is duplicate, it is determined that the same data as the data provided from the host exists, and accordingly, the processing of the write request is completed without redundantly storing the data provided from the host. can do. As an example, the reference count corresponding to the same index as the index provided from the host may be updated (S26), and the updated reference count information may be provided to the host (S27). The update of the reference count may be performed by increasing or decreasing the value of the reference count, and as an example, the reference count may be incremented by 1 whenever a write request for the same index is received.

Hereinafter, in relation to data deduplication, various operation examples applicable to an embodiment of the present invention will be described. 11 to 18 are diagrams illustrating examples of communication between a host and a storage system in the data processing system of the present invention. In addition, in the following embodiments, it is assumed that the storage system is a Key-Value SSD (KV SSD), and Value may be referred to as data.

In the example of FIG. 11 , a data deduplication operation without considering data collision is described. As an example, a key generated using a hash function or the like has a smaller size compared to the data value, and accordingly, data collision in which the same key is generated even though the data values are different There is a possibility that it will occur.

Referring to FIG. 11 , upon receiving a data write request, a host generates a key from data Value and provides a write request (PUT (Key, Value)) to the storage system. The storage system may perform a data redundancy check operation using a key, and in case of duplicate data, only update the reference count (Ref CNT) without redundantly storing the data (Value). The storage system may provide information (Info_DD) to the host indicating that deduplication processing has been performed for the corresponding write request (PUT (Key, Value)), and may also provide an updated reference count (Ref CNT) to the host. have. The host may determine that data deduplication has been performed based on the information Info_DD.

Meanwhile, FIGS. 12 and 13 show an example of a data deduplication operation in consideration of data collision. 12 illustrates an example in which data collision determination is performed on the host side, and data collision determination is performed on the storage system side in FIG. 13 .

Referring to FIG. 12 , as in the embodiment of FIG. 11 , the host generates a key from data Value and provides a write request (PUT (Key, Value)) to the storage system. In addition, the storage system performs a duplicate check operation using a key, and in the case of duplicate data, data corresponding to the received key (Key) together with information (Info_D) indicating that data duplicate has occurred Value) can be read and provided to the host.

The host may check whether there is a data conflict through a comparison operation between the data (Value) requested to be written from the external system and the data (Value) provided from the storage system. As an example, the host determines whether the data (Value) is the same through a bit or byte comparison operation between the write-requested data (Value) and the data (Value) provided from the storage system, and the determination result (Res_C) can be provided as a storage system.

According to the determination result Res_C indicating that the write-requested data (Value) and the data (Value) provided from the storage system are the same, the storage system updates only the reference count (Ref CNT) without redundantly storing the data (Value) and information (Info_DD) indicating that duplication has been performed may be provided to the host. In addition, an updated reference count (Ref CNT) may be further provided to the host.

On the other hand, it is determined that a data conflict has occurred because the data (Value) requested to be written is different from the data (Value) provided from the storage system, and the host may perform a management operation for removing the data conflict. The data collision removal may be performed according to various methods, and as an example, the host may generate a key (Key') having a different hash value for the data (Value) in which the collision occurs. According to an exemplary embodiment, in case of data collision, the host may provide a new write request (PUT(Key', Value)) to the storage system, and the storage system responds to the write request (PUT(Key', Value)) for data By storing (Value), data collisions can be avoided.

Meanwhile, referring to FIG. 13 , as in the above-described embodiments of FIGS. 11 and 12 , the host generates a key through a hash function and provides a write request (PUT (Key, Value)) to the storage system. do. Also, the storage system may perform a duplicate check operation using a key.

When it is determined that duplicate data is duplicated according to a duplicate check operation using a key, the storage system may determine whether data collision occurs. As an example, the storage system may read data (Value) corresponding to a key (Key) and determine whether the read data (Value) is identical to data (Value) provided from the host. If the read data (Value) and the data (Value) provided from the host are the same, it is determined that no data collision has occurred, and accordingly, the storage system does not duplicate the data (Value) and does not store the reference count (Ref CNT). ) can only be updated. In addition, information indicating that deduplication has been performed (Info_DD) and an updated reference count (Ref CNT) may be provided to the host.

On the other hand, when it is determined that a data collision has occurred, the storage system may provide information Info_C indicating that a data collision has occurred to the host. In the same or similar manner as in the above embodiment, the host may perform a management operation for data collision removal, and as an example, the host may have a key (Key') having a different hash value for the data (Value) in which the collision has occurred. can be created and provide a new write request (PUT(Key', Value)) to the storage system.

In the above-described embodiments, an example in which a new hash operation is performed for data collision removal has been described, but the embodiment of the present invention is not limited thereto. For example, data conflicts can be eliminated by recording data in which conflicts occur in the storage system and managing table information in the form of a linked-list, counting the number of conflicts and performing data conflict management or other It will be safe even if various management methods are applied.

In the drawings showing the following embodiments, it is assumed that data (Value) corresponds to “ABCD” and a key corresponding to “123” is generated from data Value. 14 shows an example of an operation of a data processing system related to management of a reference count.

Referring to FIG. 14 , a host generates a key corresponding to “123” from data Value and provides a write request (PUT 123, ABCD) for data Value to the storage system. The storage system determines that the received data (Value) does not correspond to duplicate data, records the data (Value) normally according to the write request (PUT (123, ABCD)), and sends a signal indicating the completion of writing to the host. can provide

The host may then provide a write request for the redundant data “ABCD” to the storage system. The storage system may determine that the received write request corresponds to a write request for duplicate data through verification using a key, and may provide information Info_D indicating that data duplication has occurred to the host. The host may provide a read request (GET 123) including a key corresponding to "123" to the storage system in response to the information Info_D, and the storage system may provide the read request (GET 123) ), the data (Value) can be read and provided to the host.

The host may determine whether data collides using the data (Value) read from the storage system in the same manner as in the above-described embodiment. As a result of the determination, if the data (Value) received from the storage system and the data requested to be written (Value) are the same, the host increments the reference count for the key corresponding to “123” as there is no data conflict. It can be requested by the storage system. The storage system may complete the write operation by incrementing (or updating) a reference count for a key corresponding to “123” in response to a request from the host.

According to the above embodiment, while reference counts for keys are managed in the storage system, an operation for adjusting reference counts for keys may be performed by the host. That is, when a write request for redundant data is requested, whether data collides is determined by the host, and a reference count in the storage system may be managed by the host based on the determination result.

15 illustrates an example of an operation using reference count information in a storage system.

Referring to FIG. 15 , as in the above-described embodiment, the host generates a key corresponding to “123” from data (Value) having “ABCD”, and requests a write (PUT (PUT) 123, ABCD)) as a storage system. The storage system may determine whether data (Value) is duplicated, record data (Value) according to the determination result, or update only the reference count without recording data (Value). Also, information (Info_DD) indicating that duplication has been performed may be provided to the host.

The host may perform an overwrite or partial update operation on existing data (Value) according to a request from an external system. As an example, the host provides a request (PUT_OVERWRITE) to overwrite data (Value) corresponding to a key (Key) corresponding to “123” with another value, or data corresponding to a key (Value) ) may provide a request (PUT_PARTIAL_UPDATE) to update the value of some of them.

The storage system may determine whether to perform an overwrite request or a partial update request from the host. As an example, the storage system determines whether to perform by checking a reference count corresponding to a key corresponding to “123”. can do. If, as a result of checking the reference count, data corresponding to a key corresponding to “123” is data referenced by a plurality of logical addresses on the external system side, it indicates that the storage system cannot change the data. Information (Failed) can be provided to the host. The host may determine again whether data is changed based on the information (Failed) from the storage system.

16 illustrates an example in which data deduplication is determined by a host.

Referring to FIG. 16 , as in the above-described embodiment, the host generates a key corresponding to “123” from the data “ABCD”, and requests a record for the data (Value) (PUT 123, ABCD)) as a storage system. The storage system may perform a duplicate check operation using a key and provide the determination result to the host. When the data (Value) is not duplicate data, the data (Value) requested to be recorded is normally recorded, and when the data (Value) is duplicate data, information (Info_D) indicating that data duplication has occurred is provided to the host can be

The host can optionally perform data deduplication. For example, the host may operate according to the data deduplication mode, and when the deduplication mode is applied, the host may provide a data deduplication request (Req_Dedup) to the storage system. The storage system may update a reference count corresponding to a key in response to the data deduplication request Req_Dedup and provide information Info_DD indicating that deduplication has been performed to the host. On the other hand, if the deduplication mode is not applied, the host may provide a data duplication request (Req_Dup) to the storage system, and the storage system duplicates the data (Value) and indicates that the data (Value) is normally stored. The indicated information may be provided to the host.

The application of deduplication as described above may be performed according to various criteria. As an example, the host may determine its importance according to the data (Value), and may request to redundantly store the data (Value) for relatively important data (or data requiring storage stability). On the other hand, data deduplication may be applied to relatively insignificant data (Value).

According to an embodiment, the storage system may provide the reference count stored therein to the host, and the host may determine the value of the reference count in applying data deduplication. As an example, when the value of the reference count corresponding to the specific key is relatively large, this may indicate that a lot of data (Value) corresponding to the specific key are being referenced. At this time, the host determines whether the value of the reference count corresponding to the specific key exceeds the threshold, and when writing data corresponding to the specific key, the value of the reference count and the threshold Data deduplication may or may not be applied depending on the comparison result of

17 shows an example of an operation using a reference count in a data processing system. Among the features shown in FIG. 17 , detailed descriptions of features that are the same as those described in the previous embodiment will be omitted.

Referring to FIG. 17 , a data processing system according to an embodiment of the present invention includes a host and a storage system, and a reference count corresponding to a key may be stored in the storage system. The storage system may also provide a reference count to the host. The reference count may be provided from the storage system to the host in various ways. As an example, whenever data deduplication is applied, a reference count corresponding to a corresponding key may be provided to the host. Alternatively, irrespective of data deduplication, a reference count stored in a memory in the storage system may be provided to the host periodically or aperiodically.

The host may store the reference count provided from the storage system, and may determine the reference count for data management operations. For example, for a key having a relatively large reference count (or exceeding a threshold value), it is determined that the importance of data corresponding to the key is high, and a management operation may be performed accordingly. As an embodiment, the host may provide a data backup request corresponding to the corresponding key to the storage system. Alternatively, the host may request the storage system to move data corresponding to the corresponding key to a high-reliability storage area (eg, a single-level cell (SLC) area in a NAND memory). The storage system may perform an operation according to a management request from the host.

18 shows an example of an operation using a reference count in a data processing system. Among the features shown in FIG. 18 , detailed descriptions of features that are the same as those described in the previous embodiment will be omitted.

18 shows an example in which the reference count is stored in the storage system, while the value of the reference count is provided from the host to the storage system. In addition, although an example in which an operation for determining whether data is duplicated or determining a data collision is performed in the host is illustrated, the embodiment of the present invention need not be limited thereto. For example, the present embodiment may be applied even when data conflict management is not performed or data conflict management is performed at the storage system side.

Referring to FIG. 18 , the host generates a key corresponding to “123” from data (Value) having “ABCD”, and a write request (PUT(123, ABCD)) for the data (Value) is stored in the storage As provided to the system, the storage system will store data (Value). Thereafter, as the same key (eg, “123”) is generated, the host may determine that data duplication has occurred, and the host requests to read data value corresponding to the key corresponding to “123”. can be provided as a storage system. The storage system may provide a reference count (eg, 1) corresponding to the key (eg, 1) to the host together with data (Value) corresponding to the key (Key).

The host determines whether there is a data collision by using the data (Value) received from the storage system. If it is determined that a data collision has occurred, the host may perform the data collision management operation according to the above-described embodiments. On the other hand, if it is determined that no data collision has occurred, the data write request may be provided to the storage system again, and the reference count corresponding to the corresponding key may be changed to a value of 2 and provided to the storage system. The storage system performs a write operation based on data deduplication, and as an example, updates the reference count corresponding to the corresponding key from 1 to 2 according to the information provided from the host without recording the duplicate data (Value). can do.

19 is a block diagram illustrating a network system including a server system according to an embodiment of the present invention. 19 illustrates a plurality of terminals (eg, a computing node) together with a server system, and the server system may be implemented using the data processing system according to the above-described embodiments.

Referring to FIG. 19 , the network system 700 may include a plurality of terminals 731_1 to 731_n that communicate through the network 720 together with the server system 710 . The server system 710 may include a server 711 and an SSD 712 as a storage system. The server 711 may perform the function of a host in the above-described embodiments.

The server 711 may process requests transmitted from a plurality of terminals 731_1 to 731_n connected to the network 720 . As an example, the server 711 may store data provided from the plurality of terminals 731_1 to 731_n in the SSD 712 . In addition, according to the above-described embodiments, the storage space of the SSD 712 can be efficiently used by reducing or preventing redundant storage of the same data by applying the data deduplication function.

The SSD 712 may manage the hash index and the reference count according to the above-described embodiments. According to an embodiment, the SSD 712 may receive data and a hash index corresponding thereto from the host, and determine whether data is duplicated by performing the hash index, and store data and update the reference count according to the determination result. can be performed. In addition, when the value of the reference count corresponding to the specific key is large, the corresponding data may correspond to data used in one or more terminals among the plurality of terminals 731_1 to 731_n. Accordingly, a data management operation using the reference count may be performed.

Exemplary embodiments have been disclosed in the drawings and specification as described above. Although the embodiments have been described using specific terms in the present specification, these are used only for the purpose of explaining the technical spirit of the present disclosure and are not used to limit the meaning or the scope of the present disclosure described in the claims. . Therefore, it will be understood by those skilled in the art that various modifications and equivalent other embodiments are possible therefrom. Accordingly, the true technical protection scope of the present disclosure should be defined by the technical spirit of the appended claims.

Claims (20)

a storage device for storing data; and
A controller including a memory for directly receiving an index generated from the data by a hash engine in the host together with the data from the host, and storing mapping information between the index and a physical address and a reference count corresponding to the index provided,
The controller determines whether data received from the host corresponding to the index corresponds to duplicate data by determining the mapping information or the reference count read from the memory according to the index received from the host, and the received data performing deduplication processing by updating the reference count when
The storage device is a key-value storage device that stores the data received from the host as a value, and stores the index received from the host as a key related to the value. delete According to claim 1,
The index is a hash value generated through an operation using a hash function on the data. According to claim 1, wherein the controller,
When an index having the same value as the index received from the host exists in the memory, it is determined that data received with the index corresponds to duplicate data. 5. The method of claim 4,
The memory stores first to N-th reference counts corresponding to the first to N-th indexes (where N is an integer of 2 or more);
and the controller, when it is determined that the index received from the host is the same as the first index, performs deduplication by increasing a value of a first reference count corresponding to the first index. According to claim 1, wherein the controller,
and providing the updated reference count to the host. According to claim 1, wherein the controller,
providing first information indicating that the data received from the host is redundant data to the host;
and receiving a reference count update request from the host and performing an update on the reference count in response thereto. According to claim 1, wherein the controller,
and a compressor for compressing the data received from the host and providing the compressed data to the storage device. According to claim 1, wherein the controller,
and a hash engine that performs a hash operation on at least one of the index and the data received from the host. According to claim 1, wherein the controller,
processor; and
and an operation memory for storing a deduplication control module that determines whether the data is duplicated and controls an update operation on the reference count as a program executable by the processor. A method of operating a storage system, comprising:
directly receiving from the host a first index generated from the first data by a hash engine in the host together with the first data from the host;
It is determined whether the received first index is the same as an index corresponding to data previously stored in the memory, based on mapping information between an index and a physical address and a read operation for a memory storing a reference count corresponding to the index to do;
updating the reference count pre-stored in the memory without writing the first data according to data deduplication when the same index as the first index exists; and
providing the updated reference count to the host;
The storage system is a key-value storage system that stores the data received from the host as a value, and stores the index received from the host as a key related to the value. 12. The method of claim 11,
The storage system stores second to N-th indexes and corresponding second to N-th reference counts (where N is an integer greater than or equal to 3);
When the first index is the same as the second index according to the determination result, a value of a second reference count corresponding to the second index is increased. 13. The method of claim 12,
The providing of the updated reference count comprises providing a second reference count, the value of which is increased, to the host. 12. The method of claim 11,
When the same index as the first index does not exist,
mapping the first index to a first physical address;
writing the first data to a location indicated by the first physical address; and
and storing the first physical address corresponding to the first index and a first reference count in the memory. 12. The method of claim 11,
When the same index as the first index exists,
providing information indicating that the first data is redundant data to the host; and
Further comprising the step of receiving a deduplication request or a duplicate storage request from the host,
The data deduplication is performed in response to the deduplication request from the host, and the first data is stored in duplicate in response to the duplicate storage request from the host. delete delete delete delete delete

Images