Electronic device and computing system including same

A byte-addressable electronic device is provided. The electronic device includes a volatile memory device, a mapping table storing address information of the volatile memory device corresponding to address information of a non-volatile storage device, and information indicating whether a command related to data access is processed in relation to the address information of the volatile memory device, and a controller connected to a host processor, the volatile memory device, and the non-volatile storage device, and configured to process commands related to data access received from the host processor based on the mapping table.

CROSS-REFERENCE TO RELATED APPLICATION

BACKGROUND

The present disclosure relates to an electronic device and a computing system including the electronic device.

Dynamic random access memory (DRAM), which is a representative byte-addressable memory, may be read and written in units of byte but is more expensive in cost per unit than a block storage and has limitations in expansion. The block storage is cheaper and has higher capacity than DRAM but may not be read or written in units of byte and may operate only in 512 bytes or 4 KB block units.

Data of the block storage may be cached in the DRAM and may be read and written by byte addressability and may be shown to a host as if there is DRAM equal to a size of the block storage. Here, a method of describing a relationship between DRAM and block storage is referred to as mapping, and there is a need to design an algorithm such that advantages of respective devices are fully used.

SUMMARY

The present disclosure provides a mapping structure that may use full advantages of a volatile memory device and a non-volatile storage device.

The present disclosure provides a mapping algorithm that operates quickly, includes a mapping table of a small size, and does not increase write and read amplification.

The present disclosure provides an optimized memory mapping algorithm to increase the entire performance of a system and increase efficiency to reduce total cost of ownership (TCO).

The present disclosure may be implemented in a variety of ways including a device, a system, a method, and a computer program stored in a readable storage medium.

According to an aspect of the present disclosure, a byte-addressable electronic device is provided. The electronic device may include a volatile memory device, a mapping table storing address information of the volatile memory device corresponding to address information of a non-volatile storage device, and information indicating whether a command related to data access is processed in relation to the address information of the volatile memory device, and a controller connected to a host processor, the volatile memory device, and the non-volatile storage device, and configured to process commands related to data access received from the host processor based on the mapping table.

In one embodiment, the mapping table may include a plurality of entries respectively corresponding to a plurality of page numbers of the non-volatile storage device, and each of the plurality of entries may include a page number of the volatile memory device corresponding to a predetermined page number of the non-volatile storage device, a read bitmap indicating whether data at a certain offset position of the page number of the volatile memory device is read, and a write bitmap indicating whether the data at the certain offset position of the page number of the volatile memory device is written.

According to another aspect of the present disclosure, a computing system is provided. The computing system may include a host processor, a byte-addressable electronic device, and a non-volatile storage device, wherein the byte-addressable electronic device includes a volatile memory device, a mapping table storing address information of the volatile memory device corresponding to address information of a non-volatile storage device, and information indicating whether a command related to data access is processed in relation to the address information of the volatile memory device, and a controller connected to the host processor, the volatile memory device, and the non-volatile storage device, and configured to process commands related to data access received from the host processor based on the mapping table.

According to various embodiments of the present disclosure, a mapping structure, which may use full advantages of a volatile memory device and a non-volatile storage device, may be provided.

According to various embodiments of the present disclosure, a mapping algorithm, which operates quickly, includes a mapping table of a small size, and does not increase write and read amplification, may be provided.

According to various embodiments of the present disclosure, an optimized memory mapping algorithm, which increases the entire performance of a system and increases efficiency to reduce total cost of ownership (TCO), may be provided.

Effects of the present disclosure are not limited to the effects described above, and other effects not described may be clearly understood by those (hereinafter referred to as “those skilled in the art”) skilled in the art to which the present disclosure belongs from the descriptions of claims.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Various embodiments set forth herein are illustrated for the purpose of clearly describing the technical ideas of the present disclosure, and are not intended to be limited to particular embodiments. The technical ideas of the present disclosure include various modifications, equivalents, and alternatives of each embodiment set forth herein, and embodiments obtained by selectively combining all or part of each embodiment. In addition, the scope of the technical ideas of the present disclosure is not limited to various embodiments or specific descriptions thereof presented below.

Terms used herein, including technical or scientific terms, may have the meaning commonly understood by those of ordinary skill in the art to which the present disclosure pertains unless defined otherwise.

As used herein, expressions such as “include(s),” “may include,” “is/are provided with”, “may be provided with,” “have/has,” “can have,” and the like mean that target features (e.g., functions, operations, components, or the like) exist, and do not preclude the presence of other additional features. That is, such expressions should be understood as open-ended terms that imply the possibility of including other embodiments.

Singular expressions herein include plural expressions unless the context clearly dictates that they are singular. Further, plural expressions include singular expressions unless the context clearly dictates that they are plural. Throughout the specification, when a part is said to include a component, this means that it may further include other components rather than excluding other components unless particularly described to the contrary.

Further, the term ‘module’ or ‘part’ used herein refers to a software or hardware component, and the ‘module’ or ‘part’ performs certain roles. However, the ‘module’ or ‘part’ is not meant to be limited to software or hardware. The ‘module’ or ‘part’ may be configured to reside on an addressable storage medium or may be configured to run one or more processors. Therefore, as one example, the ‘module’ or ‘part’ may include at least one of components such as software components, object-oriented software components, class components, and task components, processes, functions, properties, procedures, subroutines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, or variables. Functions provided within the components and the ‘modules’ or ‘parts’ may be combined into a smaller number of components and ‘modules’ or ‘parts,’ or may be further separated into additional components and ‘modules’ or ‘parts.’

According to one embodiment of the present disclosure, a ‘module’ or ‘part’ may be implemented with a processor and a memory. The ‘processor’ should be interpreted broadly so as to encompass general-purpose processors, central processing units (CPUs), microprocessors, digital signal processors (DSPs), controllers, microcontrollers, state machines, and the like. In some circumstances, the ‘processor’ may also refer to an application-specific integrated circuit (ASIC), a programmable logic device (PLD), a field programmable gate array (FPGA), or the like. The ‘processor’ may also refer to, for example, a combination of processing devices, such as a combination of a DSP and a microprocessor, a combination of a plurality of microprocessors, a combination of one or more microprocessors combined with a DSP core, or a combination of any other such components. In addition, the ‘memory’ should be interpreted broadly so as to encompass any electronic component capable of storing electronic information. The ‘memory’ may also refer to various types of processor-readable media, such as random-access memory (RAM), read-only memory (ROM), non-volatile random-access memory (NVRAM), programmable read-only memory (PROM), erasable-programmable read-only memory (EPROM), electrically erasable PROM (EEPROM), flash memory, magnetic or optical data storage, registers, etc. A memory is said to be in electronic communication with a processor if the processor can read information from and/or write information to the memory. A memory integrated with a processor is in electronic communication with the processor.

As used herein, expressions such as “first” and “second” are used to distinguish one object from another when referring to a plurality of objects of the same kind unless the context indicates otherwise, and do not limit the order or importance among the relevant objects.

As used herein, expressions such as “A, B, and C,” “A, B, or C,” “A, B, and/or C,” or “at least one of A, B, and C,” “at least one of A, B, or C one,” “at least one of A, B, and/or C,” “at least one selected from A, B, and C,” “at least one selected from A, B, or C,” and “at least one selected from A, B, and/or C” may mean all possible combinations of each listed item or listed items. For example, “at least one selected from A and B” may refer to all of (1) A, (2) at least one of A's, (3) B, (4) at least one of B's, (5) at least one of A's and at least one of B's, (6) at least one of A's and B, (7) at least one of B's and A, (8) A and B.

As used herein, the expression “based on” is used to describe one or more factors that affect the action or operation of a decision or determination described in the phrase or sentence including the expression, and this expression does not preclude additional factors that affect the action or operation of that decision or determination.

As used herein, the expression that a component (e.g., a first component) is “connected” or “coupled” to another component (e.g., a second component) may mean that said component is connected or coupled to said another component directly, as well as connected or coupled via yet another component (e.g., a third component).

As used herein, the expression “configured to” may have the meaning of “set to,” “having the ability to,” “modified to,” “made to,” “capable of,” etc., depending on the context. The expression is not limited to the meaning of “designed specifically in hardware,” and for example, a processor configured to perform a particular operation may refer to a generic-purpose processor capable of performing that particular operation by executing software.

Hereinafter, various embodiments of the present disclosure will be described with reference to the accompanying drawings. In the accompanying drawings and description of the drawings, identical or substantially equivalent components may be given the same reference numerals. Further, in the description of various embodiments below, repetitive descriptions of the same or corresponding components may be omitted, which, however, does not mean that such components are not included in that embodiment.

FIG.1is an example diagram conceptually illustrating a computing system100according to an embodiment of the present disclosure.

The computing system100according to the present disclosure may be a storage server or another type of server that may be used in a data center. As illustrated inFIG.1, the computing system100may include a host processor110(for example, an x86 central processing unit (CPU), ARM, or RISC-V), an electronic device130, and a non-volatile storage device140. The host processor110may be connected to a host memory120. The electronic device130may include a volatile memory device132.

The computing system100according to the present disclosure may use the volatile memory device132of the electronic device130as an intermediate storage medium and may have an expandable device structure that may use the non-volatile storage device140as a final storage medium. The host processor110may recognize the total capacity of the non-volatile storage device140connected to the electronic device130.

The host processor110may communicate with the electronic device130through a first interface150. The first interface150may be a serial interface, for example, an interface using PCIe or a compute express link (CXL) protocol. The electronic device130may communicate with the non-volatile storage device140through a second interface160. The second interface160may be a serial interface.

In the computing system100according to the present disclosure, the first interface150may be a byte-addressable protocol (or a byte addressing protocol), and the second interface160may be a block addressable protocol (or a block addressing protocol). The host processor110may read and write data from and to the electronic device130by designating an address in units of byte. In relation to such characteristics, the electronic device130may be referred to as a byte-addressable electronic device. The electronic device130may read and write data by designating an address in units of block to the non-volatile storage device140. The electronic device130may read data in units of block from the non-volatile storage device140based on a byte address and store the data in the volatile memory device132of the electronic device130. The electronic device130may access data corresponding to an address commanded by the host processor110among pieces of data stored in the volatile memory device132.

According to one embodiment, the electronic device130may internally have a cache for data stored in the volatile memory device132to increase performance.

For the sake of convenience of description,FIG.1illustrates that the non-volatile storage device140is configured separately from the electronic device130. However, the present disclosure is not limited thereto. For example, in the present disclosure, the non-volatile storage device140may be integrated with the electronic device130.

FIG.2is a block diagram of a computing system100including an electronic device130, according to an embodiment of the present disclosure.

As illustrated inFIG.2, the computing system100includes a host processor110, an electronic device130, and a non-volatile storage device140. The host processor110may include a communication port210. The electronic device130may include a volatile memory device132and a controller240.

The host processor110may refer to a set of one or more processors. The host processor110may execute software (for example, commands, programs, or so on) to control at least one component of a device or terminal (for example, the electronic device130) connected to the host processor110. Also, the host processor110may perform various operations, such as calculation, processing, and data generation or processing. Also, the host processor110may load data and so on from various memory devices or storage devices, or may store data in a memory device or storage device.

The controller240may have one or more volatile memory channels and may communicate with individual components or the volatile memory device132through the volatile memory channels. The volatile memory device132may be, for example, a dual in-line memory module (DIMM)-type dynamic random access memory (DRAM). The controller240may include a first communication port220. For example, the first communication port220may be a PCIe end point or a computer express link (CXL) end point. According to one embodiment, the controller240may further include a second communication port230. For example, the second communication port230may be a PCIe root complex port.

The controller240may communicate with the host processor110through a first interface150, the first communication port220, and a communication port210. Also, the controller240may communicate with the volatile memory device132through a third interface250. Also, the controller240may communicate with the non-volatile storage device140through a second interface160and a second communication port230. Here, the first interface150and the second interface160may be serial interfaces, and the third interface250may be a parallel interface.

The controller240may communicate with the host processor110by using a first protocol. Also, the controller240may communicate with the volatile memory device132by using a second protocol. Also, the controller240may communicate with the non-volatile storage device140by using a third protocol. Here, the first and second protocols may be byte-addressable protocols that may read and write data by designating addresses in units of byte, and the third protocol may be a block addressable protocol that may read and write data by designating addresses in units of block.

The non-volatile storage device140may include one or more non-volatile storages. According to one embodiment, non-volatile storages that may be allowed by an interface may be directly connected to the second communication port230. Here, the non-volatile storages may include a hard disk drive (HDD), a solid state drive (SSD), and so on.

The controller240according to the present disclosure may receive a command or request related to data access including address information from the host processor110. The command may be a command for reading or writing data, and may be transmitted through the communication port210and the first communication port220. The controller240may communicate with the volatile memory device132and the non-volatile storage device140to process data access commands.

The electronic device130according to the present disclosure may include a mapping table260. The mapping table260may refer to a set of data or pieces of information indicating a relationship between the volatile memory device132and the non-volatile storage device140. For example, when data stored in the non-volatile storage device140is cached or stored in the volatile memory device132, a positional relationship between different devices for corresponding data is stored in the mapping table260in the form of metadata. According to one embodiment, the mapping table260may include address information of the volatile memory device132corresponding to the address information of the non-volatile storage device140, information indicating whether a command related to data access is processed is stored in relation to address information of the memory device132, and so on. AlthoughFIG.2illustrates an example in which the mapping table260is included (stored) in the volatile memory device132, the present disclosure is not limited thereto. For example, the mapping table260may be included in the controller240or may be implemented by a separate memory in the electronic device130.

FIG.3is a diagram illustrating a data structure of the mapping table260according to an embodiment of the present disclosure.

According to the present disclosure, the mapping table260includes a plurality of entries320, each corresponding to a plurality of page numbers BPNs310of the non-volatile storage device140. In the present disclosure, a term page number (BPN) of the non-volatile storage device140may include not only a block page number of the non-volatile storage device140but also information that may indicate an address or an address range of the non-volatile storage device140. Each of the plurality of entries320includes a read bitmap322, a write bitmap324, and a page number (BPN)326of the volatile memory device132. In the present disclosure, the term page number (DPN) of the volatile memory device132may include not only a DRAM page number of the volatile memory device132but also information that may indicate an address or address range of the volatile memory device132.

The volatile memory page number (BPN)326may correspond to the page number (BPN)310of the non-volatile storage device140. The read bitmap322may indicate whether to read data at a specific offset position of the page number (BPN)326of the volatile memory device132. Also, the write bitmap324may indicate whether to read data at a specific offset position of the page number (BPN)326of the volatile memory device132.

According to one embodiment, a size of each of the plurality of entries320may be equal to a unit by which the host processor110accesses the volatile memory device132once. For example, the size of each of the plurality of entries320may be 4 bytes or 8 bytes. A unit size of the mapping table260may be set to be greater than a page unit (for example, 4 KB). Here, the unit size of the mapping table260may indicate a size of the non-volatile storage device140corresponding to each of the plurality of entries320. Alternatively, the unit size of the mapping table260may indicate a size corresponding to an interval between a plurality of page numbers (BPNs)310of the non-volatile storage device140. According to one embodiment, the unit size of the mapping table260may be a value obtained by multiplying a page unit by m, where m is a natural number (m=1, 2, 3, . . . ). According to another embodiment, the unit size of the mapping table260may be a value obtained by multiplying the page unit by 2n, where n is a natural number (n=1, 2, 3, . . . ). For example, the unit size may be 64 KB.

According to one embodiment, the read bitmap322and the write bitmap324may be composed of a predetermined number of bits. For example, when the size of each of the plurality of entries320is 4 bytes and the page number (BPN)326of the volatile memory device132is composed of 28 bits, the read bitmap322and the write bitmap324may each be composed of 2 bits. In another example, when the size of each of the plurality of entries320is 8 bytes and the page number (BPN)326of the volatile memory device132is composed of 4 bytes, the read bitmap322and the write bitmap (324) may each be composed of 2 bytes.

The read bitmap322according to the present disclosure may be composed of m bits, and the write bitmap324may be composed of n bits. Here, m and n may be the same value or may be different values. According to one embodiment, when a data unit for reading data and a data unit for writing data are set to be different from each other, m and n may have different values. For example, when the unit size of the mapping table is 64 K and read and write are set to be performed respectively in units of 16 K and 4 K, the read bitmap322and the write bitmap324may be respectively composed of 4 bits and 16 bits. In this way, by setting the data unit for reading data to be relatively large, a size of the read bitmap322may be reduced. The present disclosure is not limited to reducing a size of the read bitmap322as in the above example and is also possible to reduce a size of the write bitmap324.

In the read bitmap322, setting an x-th bit (0≤x≤m−1) from the least significant bit (LSB) may mean that data at an x-th offset position in the page number (BPN)326of the volatile memory device132is read. Similarly, in the write bitmap324, setting an x-th bit (0≤x≤n−1) from the least significant bit (LSB) may mean that data at an x-th offset position in the page number (BPN)326of the volatile memory device132is written. Here, setting a certain bit may mean that a value of a corresponding bit is “1”, and clearing a certain bit may mean that a value of a corresponding bit is “0”.

Referring toFIG.3, the read bitmap322and the write bitmap324of the mapping table260is each composed of 2 bytes. The first entry330may mean that an address or address range where the page number (BPN)310of the non-volatile storage device140is “0” corresponds to an address or address range where the page number (BPN)310of the volatile storage device132is “3”. Also, in relation to a read bitmap and a write bitmap of the first entry330, the data at a 0-th offset position from an address where the page number (BPN)326of the volatile memory device132is “3” is read, and the data at 0-th and third offset positions are written. A second entry340may mean that an address or address range where the page number (BPN)310of the non-volatile storage device140is “1” corresponds to an address or address range where the page number (BPN)326of the volatile memory device132is “0”. Also, in relation to a read bitmap and a write bitmap of the second entry340, the data at second and fifth offset positions from the address where the page number (BPN)326of the volatile memory device132is ‘0’ is read and the data at second and third offset positions are written.

FIG.4is a flowchart illustrating a process in which the controller240processes commands related to data access by using the mapping table260, according to an embodiment of the present disclosure.

The controller240calculates the page number (BPN) and a bitmap offset of the non-volatile storage device140(S410). According to one embodiment, the controller240calculates the page number (BPN) and a bitmap offset of the non-volatile storage device140based on the address included in the command related to data access received from the host processor110. The page number (BPN) of the non-volatile storage device140may be related to a quotient of dividing an address included in a command related to data access by a unit size of the mapping table260. Also, the bitmap offset may be related to a quotient of dividing an address included in a command related to data access by a unit size of the mapping table260. For example, the bitmap offset may be a value obtained by dividing the remainder of dividing an address included in a command related to data access by a unit size of the mapping table260by a smallest mapping unit size (for example, 4 KB).

Next, the controller240determines whether there is caching (S420). According to one embodiment, the controller240may determine whether predetermined data corresponding to the page number (BPN) and the bitmap offset of the non-volatile storage device140calculated by using the mapping table260is cached in the volatile memory device132. When it is determined in the determination step S420that a corresponding data is not cached in the volatile memory device132, the controller240may read block storage corresponding to the calculated page number (BPN) and bitmap offset of the non-volatile storage device140and cache in the volatile memory device132(S430). Also, the controller240may set a read bitmap corresponding to the bitmap offset (S440). When it is determined in the determination step S420that a corresponding data is cached in the volatile memory device132, the controller240determines whether the bitmap is not set (S450). When the bitmap is set (no in S450), the processing proceeds to a determination step S460on commands related to data access. When the bitmap is not set (yes in S450), a read bitmap corresponding to the bitmap offset is set (S440), and the processing proceeds to the determination step S460.

Next, the controller240determines whether a command related to data access is a read command or a write command (S460). When it is determined that the command is a read command in the determination step S460, the controller240reads the command from the volatile memory device132(S470). According to one embodiment, the controller240may read data cached in the volatile memory device132and transmit the read data to the host processor110. When it is determined that the command is a write command in the determination step S460, the controller240sets a write bitmap corresponding to the bitmap offset (S480). Next, the controller240writes the write bit map to the volatile memory device132(S490). According to one embodiment, the controller240may update the data cached in the volatile memory device132based on a write command.

FIG.5is a diagram conceptually illustrating a process in which the controller240reads the data stored in the non-volatile storage device140, according to an embodiment of the present disclosure. The processing illustrated inFIG.5may be at least partially related to step S410, step S420, step S430, step S440, step S460, and step S470ofFIG.4.

The controller240checks the mapping table260(S510). The controller240may check the mapping table260based on address information included in a read command from the host processor110. As a result of checking the mapping table260, the controller240may determine that a corresponding data is not cached in the volatile memory device132.

The controller240may a read block storage (S520). The controller240may read data corresponding to the page number (BPN) and bitmap offset of the non-volatile storage device140calculated from an address included in a read command, from the non-volatile storage device140. Also, the controller240may cache the data read from the non-volatile storage device140in the volatile memory device132(S530). The controller240may express that data is cached by setting a read bitmap corresponding to the bitmap offset. Next, the controller240may transmit the data cached in the volatile memory device132to the host processor110(S540).

FIG.6is a diagram illustrating changes in the mapping table260and the volatile memory device132according to commands related to data access, according to an embodiment of the present disclosure. InFIG.6, it is assumed that a unit size of the mapping table260is set to 64 KB and a smallest mapping unit size is 4 KB.

The electronic device130sequentially receives a first command610, a second command620, and a third command630from the host processor110. The first command610is a write command, and an address and data are respectively 0 K and “AB”. The controller240of the electronic device130calculates the page number (BPN) and a bitmap offset of the non-volatile storage device140from the address of 0 K. For example, the controller240may determine 0, which is a quotient of dividing 0 K by 64 K that is a unit size of the mapping table260, as the page number (BPN) of the non-volatile storage device140, and may determines 0, which is a remainder of dividing 0 K by 64 K that is a unit size of the mapping table260, as the bitmap offset.

The controller240determines that data corresponding to the page number (BPN) and bitmap offset of the non-volatile storage device140is not cached in the volatile memory device132, by using the mapping table260. According to this determination, the controller240may read data, in which a page number (BPN) and a bitmap offset of the non-volatile storage device140is each 0, from the non-volatile storage device140and cache in a region where the page number (DPN) and the bitmap offset are respectively 3 and 0. The controller240updates the page number (DPN) of the volatile memory device132to 3 in the entry in which the page number (BPN) of the non-volatile storage device140is 0 in the mapping table260. Also, because the bitmap offset is 0, the controller240sets the least significant bit (LSB) of the read bitmap. Also, the controller240updates a corresponding data cached in the volatile memory device132to “AB” and sets the least significant bit (LSB) of the write bitmap.

The second command620is a read command, and an address thereof is 4 K. The controller240of the electronic device130calculates the page number (BPN) and bitmap offset of the non-volatile storage device140from the address of 4 K. For example, the controller240may determine 0, which is a quotient of dividing 4 K by 64 K that is a unit size of the mapping table260, as the page number (BPN) of the non-volatile storage device140. Also, the controller240may determine 1 that is a value obtained by dividing 4 K, which is a remainder of dividing 4 K by 64 K that is a unit size of the mapping table260, by 4 K that is a smallest mapping unit size, as the bitmap offset.

The controller240to determine that data corresponding to the page number (BPN) and bitmap offset of the non-volatile storage device140is not cached in the volatile memory device132, by using the mapping table260. According to this determination, the controller240reads data “XX”, in which the page number (BPN) and bitmap offset of the non-volatile storage device140are respectively 0 and 1, from the non-volatile storage device140and caches in a region where the page number (DPN) and bitmap offset of the volatile memory device132are respectively 3 and 1. Because the bitmap offset is 1, the controller240sets the first bit from the least significant bit (LSB) of the read bitmap.

The third command630is a write command, and an address and data thereof are respectively 68 K and “CD”. The controller240of the electronic device130calculates the page number (BPN) and bitmap offset of the non-volatile storage device140from the address of 68 K. For example, the controller240may determine 1, which is a quotient of dividing 68 K by 64 K that is a unit size of the mapping table260, as the page number (BPN) of the non-volatile storage device140. Also, the controller240may determine 1, which is a value obtained by dividing 4 K that is a remainder of dividing 68 K by 64 K that is a unit size of the mapping table260by 4 K that is a smallest mapping unit size, as the bitmap offset.

The controller240determines that data corresponding to the page number (BPN) and bitmap offset of the non-volatile storage device140is cached in a page number (DPN) 0 of the volatile memory device132, by using the mapping table260. For example, the controller240determines that the bitmap is not set and sets the first bit in the least significant bit (LSB) of the read bitmap. Also, the controller240updates a corresponding data of the volatile memory device132to “CD” and sets the first bit in the least significant bit (LSB) of the write bitmap.

FIG.7is a flowchart illustrating a process in which the controller240processes a flush command, according to an embodiment of the present disclosure.

The controller240selects data to become a victim (S710). According to one embodiment, the host processor110may issue a flush command. According to another embodiment, the controller240may generate a flush command on its own. In response to the flush command, the controller240may select data to become a victim by using the mapping table260. To this end, the controller240may identify data in which a write bitmap is set in the mapping table260. For example, in the mapping table260in which the third command630ofFIG.6is processed, data in which a page number (DPN) of the volatile memory device132is 3 and a bitmap offset is 0, and data in which a page number (DPN) of the volatile memory device132is 0 and bitmap offsets are respectively 0, 1, and 3 may be identified as data that will become a victim.

Next, the controller240writes data with a set write bitmap to the non-volatile storage device140(S720). According to one embodiment, the controller240may write only the data in which a write bitmap is set in the mapping table260to the non-volatile storage device140, and may not write the data in which a write bitmap is cleared to the non-volatile storage device140. For example, the controller240may write the data in which a page number (DPN) of the volatile memory device132is 3 and a bitmap offset of the volatile memory device132is 0 in the mapping table260in which the third command630ofFIG.6is processed, to a block region where a page number (BPN) of the non-volatile storage device140is 0 and a bitmap offset of the non-volatile storage device140is 0. Also, the controller240may write the data in which a page number (DPN) of the volatile memory device132is 0 and bitmap offsets are respectively 0, 1, and 3 in the mapping table260where the third command630ofFIG.6is processed, to a block region where a page number (BPN) of the non-volatile storage device140is 1 and bitmap offsets are respectively 0, 1, and 3.

FIG.8is a diagram conceptually illustrating a process in which the controller240flushes the data stored in the volatile memory device132, according to an embodiment of the present disclosure. The processing ofFIG.8may be related to the steps ofFIG.7.

The controller240checks the mapping table260(S810). The controller240may check the mapping table260according to a flush command received from the host processor110or a flush command generated by the controller240itself. As a result of checking the mapping table260, the controller240may determine data to become a victim. According to one embodiment, the data to become a victim may be the data in which a write bitmap is set in the mapping table260.

The controller240may write only the data in which a write bitmap is set, to the non-volatile storage device140(S820). The controller240may write only the data in which a write bitmap is set in the mapping table260, to the non-volatile storage device140and may not write the data in which a write bitmap is cleared, to the non-volatile storage device140.

The methods according to the present disclosure may be methods that may be implemented by a computer. In the present disclosure, although respective steps of corresponding methods are illustrated and described in a predetermined order, the respective steps may also be performed in any order that may be randomly combined according to the present disclosure in addition to being performed sequentially. In one embodiment, at least some of the respective steps may be performed in parallel, iteratively, or heuristically. The present disclosure does not exclude making changes or modifications to the methods. In one embodiment, at least some steps may be omitted or other steps may be added thereto.

FIG.9is a table900illustrating technical effects of a mapping structure according to an embodiment of the present disclosure.

A difference between the mapping method according to the present disclosure and other mapping methods will be described with reference toFIG.9. Here, other mapping methods may be conventional mapping methods. InFIG.9, it is assumed that a size of the volatile memory device132is 128 GB and ae size of the non-volatile storage device140is 64 TB.

4K mapping is a method using a direct mapping table based on a general page size of 4 KB. In the case of the 4K mapping method, data may be found immediately through one-time access to the volatile memory device132, and accordingly, algorithm complexity is O(1). However, a size of a mapping table may greatly increase, and approximately 1/1,000 of the capacity of the non-volatile storage device140may be consumed as metadata. For example, when mapping a block storage of 64 TB, a mapping table size of 64 GB is required, and accordingly, a cache operation may require a volatile memory device132of at least 64 GB.

When a mapping unit size is increased, for example, when a 64K mapping method is adopted, the mapping table size may be reduced to 1/16 compared to the 4K mapping method. However, in the case of the 64K mapping method, write and read are performed to be smaller than the mapping size, and accordingly, there is a disadvantage that write and read amplification increases by up to 16 times. As a result, a lifespan of the non-volatile storage device140may be reduced.

A tree method may be adopted to maintain mapping as large as the volatile memory device132in which mapping is actually performed, rather than having a mapping table as large as the non-volatile storage device140. In this case, the mapping size may be reduced. However, in the worst case, data has to be found through access to the volatile memory device132as deep as the tree, there is a problem that the delay required to access the actual desired data increases.

In the present disclosure, in order to find a position of data as quickly as possible, a mapping table method rather than the tree method is basically adopted. In order to reduce a size of a mapping table, a mapping unit size has to be increased. However, when the mapping unit size is increased, a problem may occur in which write and read amplification increases, however, the embodiment according to the present disclosure proposes a type of mapping in which mapping information is combined with a minimal context to prevent write and read amplification from increasing.

In one embodiment of the present disclosure, a write bitmap and a read bitmap are added to a free space or an additional space of a page number (DPN) of the volatile memory device132in an entry of a mapping table, and a mapping unit size is increased. When performing write or read, a bitmap is used to operate as a minimum mapping unit, and thus, the write and read amplification cost may be reduced. In the method according to the present disclosure, performance speed is increased and a mapping unit size is increased compared to other methods, and thus, a mapping table size is reduced, and write and read amplification does not increase because write or read to or from the actual non-volatile storage device140is performed in units of minimum mapping. That is, the mapping methods according to various embodiments of the present disclosure may satisfy all requirements for mapping table size, algorithm complexity, and write and read amplification.

FIG.10is a block diagram of the controller240according to an embodiment of the present disclosure.

As illustrated inFIG.10, the controller240may include an address remapper1010and a memory translation controller1020. The controller240may receive a read or write command including address information from the host processor110through the first communication port220. The address remapper1010may determine whether data corresponding to a byte-unit address included in the command is cached in the volatile memory device132based on the mapping table260.

When it is determined that the data is cached in the volatile memory device132, the address remapper1010may translate the byte-unit address into a physical address (or volatile memory address) of the volatile memory device132. The address remapper1010transmit the translated address to the host processor110such that the host processor110may access the data of the volatile memory device132. When it is determined that the data is not stored in the volatile memory device132, the address remapper1010may transmit byte-unit address information received from the host processor110to the memory translation controller1020.

The memory translation controller1020may generate or manage the mapping table260used by the address remapper1010. The mapping table260may be stored in one region of the volatile memory device132. The memory translation controller1020may determine and perform a memory translation operation between the volatile memory device132and the non-volatile storage device140. The memory translation controller1020may update the mapping table260according to the memory translation operation. The updated mapping table260may be used by the address remapper1010.

The memory translation controller1020may determine whether to cache certain data stored in the non-volatile storage device140to the volatile memory device132. According to one embodiment, the memory translation controller1020may determine that data expected to be called by the host processor110among the pieces of data stored in the non-volatile storage device140is brought to the volatile memory device132. For example, the data expected to be called may be associated with a working set with a usage frequency higher than a threshold. The memory translation controller1020may read data from the non-volatile storage device140and store the read data in the volatile memory device132. In this case, the memory translation controller1020may cause a block address of the non-volatile storage device140where data is located with a byte address of the volatile memory device132where the data is stored, and store the associated addresses in the mapping table260.

The memory translation controller1020may determine whether to transmit a predetermined data cached in the volatile memory device132to the non-volatile storage device140or to copy the predetermined data. According to one embodiment, the memory translation controller1020may determine that data that is not expected to be called by the host processor110among pieces of data stored in the volatile memory device132is transmitted to the non-volatile storage device140. For example, the data that is not expected to be called may be associated with a data set with a usage frequency less than a threshold. The memory translation controller1020may remove the data transmitted to the non-volatile storage device140from the volatile memory device132. In this case, the memory translation controller1020may remove the block address of the non-volatile storage device140and the byte address of the volatile memory device132that are stored in association with each other in the mapping table260.

The controller240according to the present disclosure may further include a memory manager1030and a storage controller1040. The memory manager1030may allocate volatile memory necessary for a memory translation operation. The memory manager1030may secure an empty space in the volatile memory device132. According to one embodiment, in response to the memory translation controller1020determining that predetermined data stored in the non-volatile storage device140is transmitted to the volatile memory device132, the memory manager1030may allocate an empty space corresponding to a block size to the volatile memory device132.

The storage controller1040may drive the non-volatile storage device140according to the determination of the memory translation controller1020to perform data read or data write by designating an address in units of block. According to one embodiment, in response to the memory translation controller1020determining that predetermined data stored in the non-volatile storage device140is transmitted to the volatile memory device132and in response to the memory manager1030allocating a free space corresponding to a block size to the volatile memory device132, the storage controller1040may drive the non-volatile storage device140to read block data from the non-volatile storage device140.

The controller240according to the present disclosure may further include a cache memory1060and a memory controller1050. The cache memory1060may store data that previously accessed or is expected to access. According to one embodiment, the cache memory1060may be implemented by static random access memory (SRAM). The controller240may achieve an increase in performance, especially an increase in read and write speeds, by further including the cache memory1060. The memory controller1050may be connected to the volatile memory device132and the cache memory1060.

The address remapper1010, the memory translation controller1020, the memory manager1030, the storage controller1040, and the memory controller1050illustrated inFIG.10may each be implemented by a hardware device or software codes. According to one embodiment, the address remapper1010may be implemented by a hardware device, and the other components may be implemented by software codes. According to another embodiment, the address remapper1010and the memory translation controller1020may be implemented by hardware devices, and the other components may be implemented by software codes. Also,FIG.10illustrates configurations of the controller240by way of example, and the present disclosure is not limited thereto. For example, some of the configurations illustrated inFIG.10may be omitted or a function of a specific configuration may be included in another configuration.

The methods in accordance with the present disclosure may be computer-implemented methods. Although each step of the corresponding methods has been shown and described in a given order in the present disclosure, the respective steps may also be performed in an order that can be combined arbitrarily according to the present disclosure, in addition to being performed in sequence. In one embodiment, at least some of the steps may be performed in parallel, iteratively, or heuristically. The present disclosure does not exclude making changes or modifications to the methods. In one embodiment, at least some of the steps may be omitted or other steps may be added.

Various embodiments of the present disclosure may be implemented as software recorded on a machine-readable recording medium. The software may be software for implementing the various embodiments of the present disclosure described above. Software may be inferred from the various embodiments of the present disclosure by programmers skilled in the art to which the present disclosure pertains. For example, the software may be machine-readable commands (e.g., code or code segments) or programs. A machine is a device capable of operating according to instructions called from a recording medium, and may be, for example, a computer. In one embodiment, the machine may be the multiprocessor system100, a component thereof, or a combination of components thereof in accordance with the embodiments of the present disclosure. In one embodiment, the processor of the machine may execute the called command and cause the components of the machine to perform functions corresponding to the command. The recording medium may refer to any type of recording medium on which data readable by a machine are stored. The recording medium may include, for example, ROM, RAM, CD-ROM, magnetic tapes, floppy disks, optical data storage devices, and the like. In one embodiment, the recording medium may be implemented in a distributed form over networked computer systems or the like. The software may be stored in a distributed manner and executed on a computer system or the like. The recording medium may be a non-transitory recording medium. A non-transitory recording medium refers to a tangible medium regardless of whether data is stored in it semi-permanently or temporarily, and does not include signals propagating in a transitory manner.

Although the technical idea of the present disclosure has been described by various embodiments above, the technical idea of the present disclosure includes various substitutions, modifications, and changes that can be made within the scope that can be understood by those skilled in the art to which the present disclosure pertains. Further, it is to be understood that such substitutions, modifications, and changes may fall within the scope of the appended claims. The embodiments in accordance with the present disclosure may be combined with each other. The respective embodiments may be combined in various ways according to the number of cases, and the combined embodiments also fall within the scope of the present disclosure.