KR102706442B1 - Ssd device and operating method of the same using ftl based on lsm-tree and approximate indexing - Google Patents

Abstract

An embodiment of the present disclosure provides an SSD (Solid State Drive) device including interface logic connected to a host, nonvolatile memory storing data, and a controller controlling the nonvolatile memory, wherein the controller converts a logical address provided by the host into a physical address for the nonvolatile memory and accesses the nonvolatile memory based on the physical address, the controller converts the logical address into a physical address based on indexing information stored in a plurality of layers configured as a log-structured merge tree (LSM-tree) having a hierarchical structure, and at least two layers of the plurality of layers of the LSM-tree store indexing information based on mapping of logical addresses and physical addresses corresponding to the logical addresses in different ways.

Description

SSD device and operating method using FTL based on LSM-tree and approximate indexing {SSD DEVICE AND OPERATING METHOD OF THE SAME USING FTL BASED ON LSM-TREE AND APPROXIMATE INDEXING}

The present disclosure relates to an SSD (Solid State Drive) device and an operating method thereof, and more particularly, to an SSD device applying an FTL (Flash Translation Layer) based on approximate indexing for converting a logical address of a host and a physical address of an SSD, and an operating method thereof.

With the development of storage device technology, storage capacity has increased rapidly, and recently, SSDs (Solid State Drives) of more than 100 TB are available on the market. Despite the rapid increase in SSD storage capacity, the current indexing design for storage management has not developed to suit the increase in storage capacity. That is, SSDs use the same host interface as HDDs (Hard Disk Drives), but the current LBA (Logical Block Address) array is not optimized for SSDs, as it is suitable for HDDs that can be overwritten. Therefore, an FTL is required to hide the internal characteristics of SSDs and expose the LBA array to the host for address translation. However, conventional SSDs still have the problem of using a huge index table to translate logical addresses and physical addresses.

There have been attempts to reduce the size of conventional index tables, and the most representative one is demand-based translation (DFTL, Prior Art 1). DFTL caches only frequently referenced index entries in DRAM based on the translation lookaside buffer (TLB) and stores the rest in non-volatile storage. However, an inherent drawback of DFTL is that read latency varies greatly depending on the task, which is a performance issue. For example, when the workload has weak locality, frequent cache misses increase the delay in reading data. Because of this, some variations of DFTL (e.g., SFTL of Prior Art 2 and TPFTL of Prior Art 3) have been proposed, but they still have the same problem.

These problems are becoming even more serious in the current situation where consistent response performance is very important, as cloud environments are increasing. Therefore, SSD address translation technology that shows consistent response performance for data reading, etc. and SSD technology using it are needed.

Prior art 1: “DFTL: A ash translation layer employing demand- based selective caching of page-level address mappings.", Aayush Gupta et al., In Proceedings of the Conference on Architectural Support for Programming Languages and Operating Systems, pages 229-240, 2009. Prior Art 2: “S-FTL: An efficient address translation for ash memory by exploiting spatial locality.”, Song Jiang et al., In Proceedings of the IEEE Symposium on Mass Storage Systems and Technologies, pages 1-12, 2011. Prior Art 3: “An efficient page-level FTL to optimize address translation in ash memory.”, You Zhou et al., In Proceedings of the European Conference on Computer Systems, 2015.

One embodiment of the present disclosure provides an SSD device and an operating method thereof that enable address translation as a small index table.

Another embodiment of the present disclosure provides an SSD device and an operating method thereof that enable address translation based on approximate indexing.

Another embodiment of the present disclosure provides an SSD device and an operating method thereof that enable address translation based on an LSM-tree applying multiple indexing methods to different layers.

Another embodiment of the present disclosure provides an SSD device and a method of operating the same that enable address translation that exhibits consistent response performance regardless of the locality of a data storage location.

An embodiment of the present disclosure provides an SSD (Solid State Drive) device including interface logic connected to a host, nonvolatile memory storing data, and a controller controlling the nonvolatile memory, wherein the controller converts a logical address provided by the host into a physical address for the nonvolatile memory and accesses the nonvolatile memory based on the physical address, the controller converts the logical address into a physical address based on indexing information stored in a plurality of layers configured as a log-structured merge tree (LSM-tree) having a hierarchical structure, and at least two layers of the plurality of layers of the LSM-tree store indexing information based on mapping of logical addresses and physical addresses corresponding to the logical addresses in different ways.

Another embodiment of the present disclosure provides a method of operating an SSD device including interface logic connected to a host, non-volatile memory storing data, and a controller controlling the non-volatile memory, the method including a step of the controller receiving a logical address transmitted by the host, a step of converting the logical address provided by the controller into a physical address for the non-volatile memory based on indexing information stored in a plurality of layers configured as a log-structured merge tree (LSM-tree) having a hierarchical structure, and a step of the controller accessing the non-volatile memory based on the physical address, wherein at least two layers of the plurality of layers of the LSM-tree store indexing information based on a mapping of a logical address and a physical address corresponding to the logical address in different ways.

An SSD device and its operating method according to an embodiment of the present disclosure can exhibit consistent response performance regardless of the locality of a data storage location.

An SSD device and its operating method according to an embodiment of the present disclosure can demonstrate consistent response performance of a storage device in a cloud environment.

An SSD device and its operating method according to an embodiment of the present disclosure can provide an address translation technology with high response performance even in a small volatile memory space by using an index table of a small size compared to the size of a conventional index table.

FIG. 1 is a block diagram showing the configuration of an SSD device according to an embodiment of the present disclosure.
FIG. 2 is a diagram illustrating the configuration of each layer of an LSM-tree of an SSD device according to an embodiment of the present disclosure.
FIG. 3 is a drawing explaining the LSM-tree each layer configuration and address conversion method of an SSD device according to one embodiment of the present disclosure.
FIGS. 4 and 5 are diagrams illustrating address translation based on a bloom filter in the middle layer of an LSM-tree of an SSD device according to an embodiment of the present disclosure.
FIG. 6 is a diagram illustrating address translation based on a piece-wise linear regression (PLR) model of a lower layer of an LSM-tree of an SSD device according to an embodiment of the present disclosure.
FIGS. 7 to 10 are drawings illustrating performance test results according to one embodiment of the present disclosure.
FIG. 11 and FIG. 12 are flowcharts illustrating a method of operating an SSD device according to an embodiment of the present disclosure.

Hereinafter, embodiments disclosed in this specification will be described in detail with reference to the attached drawings. Regardless of the drawing symbols, identical or similar components will be given the same reference numerals and redundant descriptions thereof will be omitted. The suffixes "module" and "part" used for components in the following description are assigned or used interchangeably only for the convenience of writing the specification, and do not have distinct meanings or roles in themselves. In addition, when describing embodiments disclosed in this specification, if it is determined that a specific description of a related known technology may obscure the gist of the embodiments disclosed in this specification, the detailed description thereof will be omitted. In addition, the attached drawings are only intended to facilitate easy understanding of the embodiments disclosed in this specification, and the technical ideas disclosed in this specification are not limited by the attached drawings, and should be understood to include all modifications, equivalents, and substitutes included in the spirit and technical scope of the present invention.

Terms that include ordinal numbers, such as first, second, etc., may be used to describe various components, but the components are not limited by the terms. The terms are used only to distinguish one component from another.

When it is said that a component is "connected" or "connected" to another component, it should be understood that it may be directly connected or connected to that other component, but that there may be other components in between. On the other hand, when it is said that a component is "directly connected" or "directly connected" to another component, it should be understood that there are no other components in between.

The embodiments below are described as embodiments implemented in a controller of an SSD, but can be implemented as a logical address translation component of a host to which an SSD device, such as a server device or a computer, is connected. For convenience, embodiments implemented in an SSD device are described.

Referring to FIG. 1, the configuration and operating environment of a Solid State Drive (SSD) device according to one embodiment of the present disclosure are described.

An SSD device (100) according to an embodiment of the present disclosure receives a logical address from a host (200) through a host interface circuit (120), and an SSD controller (110) converts the logical address into a physical address to access a nonvolatile memory (130).

The host (200) includes a server device that provides a cloud environment for storage space and data processing, or a computing device that can utilize an SSD device as a storage device, such as a notebook computer, personal computer, or tablet computer that connects an SSD device to an interface such as SATA.

The SSD controller (110) performs logical block mapping (address translation) that converts a logical address (LBA, Logical Block Address) of a host (200) area into a physical address (PBA, Physical Sector Address: PSA) of a flash memory. For address translation, one embodiment of the present invention is based on indexing information stored in multiple layers of a log-structured merge tree (LSM-tree), which is a hierarchical structure. In some descriptions of this specification, a symbol for a logical address may be referred to as x _i , and a symbol for a physical address may be referred to as y _i . The subscript may be exemplarily changed and explained to distinguish entries.

In this specification, a physical address may be a specific physical address of a sector or block of an SSD device, or an address indirectly indicating a specific physical address of a sector or block of an SSD device. The indirectly indicating address may mean, for example, a specific physical address and an offset from the specific physical address. In addition, in this specification, a physical address is described as including not only an actual physical address where desired data is actually stored by the host (200), but also an estimated physical address that is probabilistically estimated based on approximate indexing according to an embodiment of the present invention by the SSD controller (110). In addition, in this specification, the conversion relationship between a logical address and a physical address is described using the terms mapping, indexing, and indexing interchangeably.

The SSD controller (110) converts a logical address into a physical address through a component, FTL (Flash Translation Layer). The FTL converts a logical address into a physical address based on index information. In this specification, an FTL using a unique address conversion method according to an embodiment of the present invention may be referred to as APX-FTL (Approximate FTL).

In one embodiment, the index information may be loaded and used in a RAM buffer (140) configured as a DRAM of an SSD for fast access, and may be stored in whole or in part in a nonvolatile memory (130). Accordingly, when power is supplied to the SSD, the index information stored in the nonvolatile memory (130) may be read and loaded into the RAM buffer (140). The nonvolatile memory (130) may be configured as a flash RAM of a NAND or NOR type, and its type is not particularly limited.

One embodiment of the present invention is a novel approximate address translation method that indexes a non-volatile memory (130) using a modified LSM-tree that uses a Bloom Filter (BF) and Piece-wise linear regression (PLR) model, which are probabilistic but space-efficient data structures, unlike the prior art that has accurate but large-capacity Logical to Physical (L2P) mapping entries (each 48 bits).

As explained above, in one embodiment, for memory efficiency, a part of the index information, the Bloom filter and the PLR model, may always be maintained in a RAM buffer (140) implemented in DRAM.

When the SSD controller (110) receives a data write request from the host (200), it adds the data to the nonvolatile memory (130) and changes the index information to point to the location of the written data. The changed index information may be index information based on approximate indexing.

When the SSD controller (110) receives a data read request from the host (200), it searches for a physical address based on index information stored in one layer of the LSM-tree. In one embodiment, the SSD controller (110) can infer the physical address of data to be read by searching for index information based on approximate indexing and read data from the predicted location. Due to the characteristic (false positive) of the guessing method of index information based on approximate indexing according to one embodiment of the present invention, the physical address searched from the index information may not be the actual physical address where the data desired by the host (200) is actually stored. In this case, the SSD controller (110) repeatedly attempts to convert the physical address from the index information until it finds the physical address where the desired data is actually stored.

Referring to FIG. 2, the configuration of each layer of the LSM-tree (141 to 143) of an SSD device (100) according to one embodiment of the present disclosure is described. And address conversion according to index information of each layer is described.

Unlike conventional LSM-trees, an LSM-tree (141 to 143) according to an embodiment of the present invention stores index information, which is a mapping relationship between a logical address and a physical address, in a plurality of layers, and at least two layers among the plurality of layers store index information based on the mapping of the logical address and the physical address in different ways.

According to an embodiment of the present invention, an LSM-tree (141 to 143) may be composed of a top layer (141) (L0) that stores index information of a logical address and a physical address exactly mapped to the logical address, unlike other layers, an intermediate layer (142) and a lower layer (143) that are other layers (L ₁ to L _h-1 ) that store index information that estimates a physical address mapped to the logical address in a guessing manner. h may be the height of the LSM-tree (141 to 143). Adjacent layers L _i and L _i+1 may be such that L _i+1 is T times larger than L _i , and T may be a preset multiple.

Each layer of the LSM tree (141 to 143) stores a unique key-value pair (KV pair) sorted by key, and in an embodiment of the present invention, the LSM tree can be used to map a logical block to a physical sector by processing the logical address of the logical block as a key and the corresponding data as a value.

The index information storage based on the LSM-tree (141 to 143) according to an embodiment of the present invention can provide higher write throughput than the conventional table-based indexing. The append-only update policy can avoid the expensive READ-MODIFY-WRITE (RMW) while processing a request by making it impossible to change a KV pair and its associated index once written to the disk. The disadvantage of the LSM-tree used in the conventional database data indexing is that it requires a long waiting time for reading, but the LSM-tree (141 to 143) according to an embodiment of the present invention does not require a long waiting time for reading by applying the bloom filter and PLW model according to the embodiments of the present invention to layers other than the top layer.

At least some layers of an LSM-tree (141 to 143) according to an embodiment of the present invention may include a plurality of runs, and in each run, a plurality of index information, which is a mapping relationship between a plurality of logical addresses and physical addresses, may be stored as KV pairs. In an embodiment, a run may be composed of a plurality of run chunks, and a run chunk may have the same size as a memory block of a non-volatile memory.

Multiple layers of LSM-tree (141~143) can be composed of a top layer, at least one middle layer, and at least one lower layer in the order of layers, and the runs of each layer can store multiple index information by sorting KV pairs in the logical address order of the index information.

When all runs of one layer among the layers of the LSM-tree (141 to 143) are saturated, the SSD controller (110) can move (flushing out) at least one index information of the saturated layer to a layer located below in the order of the top layer, the middle layer, and the lower layer.

Referring to FIG. 3, address conversion according to index information of each layer of the LSM-tree (141 to 143) of an SSD device (100) according to one embodiment of the present disclosure is described.

According to an embodiment of the present disclosure, the LSM-tree (141 to 143) is hierarchical, and the index information of each layer can index a 4KB logical block. Accordingly, a 48-bit integer (i.e., LBA, which is a logical address) in a KV pair can be used as a key, and a 4KB data block can be used as a value. Each run can include a unique 4KB logical block sorted by logical address, and the logical addresses of each layer and run can be partially overlapped.

The top layer (L0, 141) of the LSM-tree (141 to 143) according to one embodiment of the present disclosure is based on exact indexing that stores a logical address and a physical address mapped to the logical address as index information, and therefore, a logical block flushed from a memory table (memTable) to the top layer (L0, 141) does not necessarily need to be sorted.

Among the layers other than the top layer of the LSM-tree (141-143), at least one intermediate layer (142) may be included that stores index information based on approximate indexing that probabilistically estimates a physical address based on a Bloom filter.

In one embodiment, each bloom filter index whose logical addresses are sparsely sorted can occupy a smaller memory space and provide a faster index building time than index information based on exact indexing by maintaining a very small approximate logical address without pointers to physical sectors of the SSD. This is described in detail with reference to FIGS. 4 and 5 below.

Among the layers other than the top layer of the LSM-tree (141-143), at least one lower layer (143) may be included that stores index information based on approximate indexing that probabilistically estimates a physical address based on a piece-wise linear regression (PLR) model.

In one embodiment, a lower layer (143) in which a large number of logical addresses are densely arranged may use approximate indexing based on the PLR model, and convert the mapping relationship between logical addresses and physical addresses, <x _i , y _i >, into several linear equations y = ax + b and store them as index information. This will be described in detail with reference to FIGS. 6 to 8 below.

Accordingly, the SSD controller (110) can obtain a physical address (y _i ) mapped to a logical address with one lookup in the highest layer, and can obtain an accurate actual physical address mapped to a logical address by looking up the physical address (y' _j , y' _k ) one or more times in an intermediate layer or lower layer other than the highest layer.

In one embodiment, the SSD controller (110) can obtain a physical address by querying a shortcut table (144) in which information of a run in which index information corresponding to a logical address exists for logical address conversion is stored, and by querying index information corresponding to a logical address in a run searched in the shortcut table. For example, for all logical addresses, the shortcut table can store information about a run with the most recent data. The size of the shortcut table can vary depending on the number of runs included in the LSM-tree (141 to 143), and for example, if there are 32 runs in the tree, 5-bit entries are sufficient to find all possible runs. When a target run is selected, the SSD controller (110) can query index information in the corresponding run.

In one embodiment, the SSD controller (110) can read data stored in the actual nonvolatile memory (130) by looking up the physical addresses (y _i , y' _j , y' _k ) looked up in each layer in a sorted table that stores mapping information between the run chunk and the memory block. As described above, the run may be composed of a plurality of run chunks, and the run chunk may have the same size as the memory block of the nonvolatile memory (130).

Each run of the LSM-tree (141-143) is assumed to be built for physically consecutive sectors of the non-volatile memory (130), but it may be difficult to allocate many physically consecutive sectors due to the run size (at least several GB). The SSD controller (110) according to the embodiment of the present disclosure divides a run into several run chunks, sets each run chunk to have the same size as a memory (e.g., NAND) block of the non-volatile memory (130), and maps each run chunk to a memory block of the non-volatile memory (130) using a sort table, thereby allowing the physically scattered memory blocks to operate as consecutive sectors. The sort table can be indexed by a chunk index, and the size of each entry of each chunk index can be expressed by 4 bytes, so that the overall sort table size can be very small (2 MB for a 1 TB SSD device). The SSD controller (110) according to the embodiment of the present disclosure can easily find data to be read within a memory block of a nonvolatile memory (130) by configuring the offset to be the same as the offset within a run chunk (black circle number 4).

Referring to FIGS. 4 and 5, a method of converting a logical address into a physical address in a data read mode or a data write mode based on a bloom filter in an intermediate layer of an LSM-tree (141 to 143) according to an embodiment of the present disclosure is described.

While the index information of a conventional DFTL stores two 48-bit integer <x _i , y _i > pairs including an exact mapping, the middle layer of the LSM-tree (141 to 143) according to an embodiment of the present invention may store a bloom filter of a configuration such as FIG. 4, which is not an exact mapping relationship, as index information for a 4KB physical sector of a non-volatile memory (130), for example.

For example, the middle layer of the LSM-tree (141-143) can maintain, for a run of n physical sectors y ₀ ,..., y _n-1 , a table of bloom filters BF ₀ ,..., BF _n-1 , the same number as the physical sectors.

The SSD controller (110) can initially set each BF _i to 0. It is assumed and explained that data 200 for a logical address x _i is written to y ₂₀ in compaction. The SSD controller (110) can set BF ₂₀ to store hash (200), which is a hash value of x _i (black circle number 1 in FIG. 4). The SSD controller (110) can write the exact logical address 200 to the OOB area (Out-of-band area) corresponding to y ₂₀ while writing data to the physical address y ₂₀ of the nonvolatile memory (130) (black circle number 2 in FIG. 4). In one embodiment, each bloom filter in the middle layer of the LSM-tree (141-143) may represent an approximate x _i and may not include y _i , and instead, the location of each bloom filter in the table may represent a physical address y _i of the non-volatile memory (130).

When the SSD controller (110) receives a read request for x _j = 100 in the data read mode, it can perform a membership test on each bloom filter in the specified run (white circle number 1 in FIG. 4). Starting from the first bloom filter, the value of each bloom filter is compared with hash(x _j ), and if a match is found, for example, if the value identical to the initial hash(x _j ) in the index information of the middle layer is BF ₉ (BF ₉ = hash(100)), y ₉ can be read. As a result of reading y9, the SSD controller (110) finds that the logical address 37 stored in y9 is different from the requested logical address 100 (white circle number 2 in FIG. 4), so the SSD controller (110) ignores y9 and continues the test on the remaining bloom filters (white circle number 3 in FIG. 4), and can find the correct index information in y ₁₀ (white circle number 4 in FIG. 4).

That is, the middle layer may go through multiple lookup processes to obtain accurate index information by storing index information based on approximate indexing, but it can show better performance overall compared to the cache miss of the conventional DFTL.

Minimizing the number of bits of each bloom filter for the target FPR, FPTT, can help with memory capacity. In the worst case, the queried logical address may be stored in the last physical sector of the run, and other intermediate layers in the embodiment of the present disclosure may have to perform membership tests from BF ₀ to BF _n-1 . Therefore, FPR _T can be estimated as follows.

If FPR _T is 0.1, n is 512, and FPR _BF (FPR for each bloom filter) can be 2.06 x 10 ^-4 . When the number of hash functions k is set to 5, the length m of the bloom filter is minimized. Each bloom filter requires 25 bits for mapping, which is smaller than the 48-bit entries of a typical mapping table. FPR _T 0.1 means 10% overhead, which is acceptable. When FPR _T is 0.1, the read amplification factor (RAF=data read from flash/data read by host) becomes 1.1.

Referring to FIG. 5, a guard can be inserted between each bloom filter within a run in order to form a small candidate set. In one embodiment, the guard can be a 48-bit integer and can be the logical address of the first bloom filter in the candidate set. That is, when there are a large number of LBAs in each run of the tree, as the number of runs n increases, the Relaxed FPR (False Positive Rate) also increases accordingly. In order to maintain the same Relaxed FPR, a large bloom filter must be used to reduce the FPR _BF , which requires a larger DRAM, and furthermore, since many bloom filters must be tested to find a desired logical address, the problem that the time for looking up the entire bloom filter also increases can be solved by inserting a guard.

Referring to FIG. 5, finding a candidate set in each run through binary search may require O(log k) complexity time, where k is the number of candidate sets in the run (see black circle number 1 in FIG. 4). Since n is constant, a membership test for the set requires O(1) complexity time (see black circle number 1 in FIG. 4). Therefore, the logarithmic time complexity for the tree lookup according to the embodiment of the present disclosure is O(log k). However, since most of the actual lookup time is spent on the membership test, the lookup latency can be minimized by arranging the bloom filters in the memory according to the cache line boundary. In one embodiment, the size of each bloom filter can be adjusted to 8 bits for sorting, and the number of bloom filters can be adjusted to n = 26. The candidate sets, each of which is 256 bits (= 32 bytes), can be compressed by including a 48-bit guard inside a 64-byte cache line. Despite the slight memory waste (8.7 bits vs. 9.8 bits), this memory layout has the effect of allowing us to prefetch the candidate set while performing a binary search without additional memory references. In addition, since all bloom filters are packed into 64-byte integers, we can compare all the bloom filters we look up with the input logical address in a single operation with a few bitwise operations.

Referring to FIG. 6, a method for an SSD controller (110) according to an embodiment of the present disclosure to convert a logical address into a physical address in a data read mode or a data write mode based on a PLR model in a lower layer of an LSM-tree (141 to 143) is described.

The SSD controller (110) can construct a line segment modeled as a linear function y'= ax + b based on the PLR model for mapping relationships between a plurality of logical addresses and physical addresses, <x _i , y _i >. The PLR model can calculate a boundary error delta ( ) can return y', which is the location of the predicted physical address existing in [y - delta, y + delta]. For example, Fig. 5 shows that in the lower layer of the LSM-tree (141-143), four mapping entries m ₁ = (x ₁ =2, y ₁ =1), m ₂ =(4, 2), m ₃ =(6, 3), and m ₄ =(7, 4) are modeled based on a linear function with y'=0.6(x-2)+1 and delta 1. The lower layer can return y'=2.2 as the physical address for the query x=4. Similar to the bloom filter in the middle layer described above, the lower layer is also based on approximate indexing that probabilistically guesses the physical address, and thus may experience trial and error, but the size of the trial and error is determined by the boundary error delta, not the local characteristics where the data exists. Therefore, inconsistent response characteristics due to increased read delay speed according to regional characteristics of conventional FTL technology can be excluded.

The PLR model configuration of the SSD controller (110) is described with reference to FIG. 5.

Let M = {m ₁ , m ₂ , ..., m _n } be the set of mapping relationships (items) (m _i = (x _i , y _i )) of multiple logical addresses and physical addresses existing in a particular run, then m _{(i, j)} = {m _i , m _i+1 , ..., m _j } Assuming a preset target boundary error delta for a set M, the SSD controller (110) can divide M into multiple pieces, and a linear function for m _h = (x _h , y _h ) belonging to each piece m _{(i, j)} go can be set to be expressed as a line segment satisfying m _{(i, j). Accordingly, the SSD controller (110) can express the set M as a plurality of line segment pieces, and the linear function for m (i, j)} can be expressed as <Mathematical Formula 2> below.

Here, x _i , y _i can serve as the base point from which the line segment m _{(i, j)} starts based on the first pair m _i . a _{(i, j)} is the slope of the line segment for m _{(i, j)} and b _{(i, j)} is the relative intercept of the line segment from y _i .

When there are seven pairs such as in Fig. 6, two families of line segments can exist, and m ₁ = (2, 1) and m ₅ = (43, 5) can be the base points of each line segment. Therefore, for m _{(1, 4)} , the slope a _{(1, 4)} is 0.6 and the relative intercept b _{(1, 4)} is 0. Also, for m _{(5, 7),} the slope a _{(5, 7)} is 0.33 and the relative intercept b _{(5, 7)} is 0.5.

In one embodiment, the lower layer of the LSM-tree (141 to 143) may store four parameters (a _{(i, j)} , b _{(i, j)} , x _i , y _i ) in the RAM buffer (140). The SSD controller (110) may configure the PLR model so that the number of multiple line segments expressing multiple mapping relationships is minimized in order to reduce the storage space occupied in the RAM buffer (140).

In one embodiment, the SSD controller (110) may use delta encoding to reduce the space for storing the model of <Equation 2>. For example, for two consecutive line segments m _{(i, j)} , m _{(k, l)} (i<j<k<l), the SSD controller (110) may store only the differences x _k -x _j and y _k -y _j in the case of m _{(k, l)} . In this case, the SSD controller (110) may scan the line segments while performing delta decoding to find a line segment suitable for the logical address. To reduce overhead, the SSD controller (110) may store the uncompressed pairs as pivot pairs. The SSD controller (110) may perform a binary search on the pivot table including the pivot pairs to be sorted first, select candidate line segments, and then perform the remaining search on the candidate line segments.

Referring to FIG. 7, an SSD controller (110) according to an embodiment of the present disclosure describes a method for optimizing the tree configuration of the middle and lower layers of an LSM-tree (141 to 143) to minimize memory capacity occupancy. In addition, the influence of the tree configuration on the write amplification factor (WAF = data written to flash/data written by host) is also described.

According to one embodiment of the present disclosure, four major components that determine the memory usage of the RAM buffer (140) of the SSD controller (110) may be (i) the exact index of the top layer L0 stored in the RAM buffer (140), (ii) a shortcut table pointing to a desired run, (iii) a bloom filter index, and (iv) a PLR model. The memory usage varies depending on the tree configuration controlled by two parameters, |L ₀ | and T, where |L ₀ | is the size of the top layer and T is a multiple of the size between adjacent layers L _i and L _i+1 . Considering the change in the tree configuration according to |L ₀ | and T, the size of the metric |L _i | of the LSM-tree (141-143) increases by T times from the top layer |L ₀ |, and therefore, (0<i<h) can be (i is the level number and h is the tree height). Therefore, the height h can be defined as in <Mathematical Formula 3> below.

Here, C is a fixed number as the capacity of the SSD device, and |L0| and T determine h. Therefore, the height of the LSM-tree (141~143) has a great influence on the WAF. In the hierarchical LSM-tree (141~143), T can also express the number of runs in each layer. The size of each run (|R _i |) in each layer is the same, and therefore, the size of the run can be defined as in <Mathematical Formula 4>.

<Mathematical expression 4> means that R _i increases by a multiple of T, so the run size can be larger as the level is lower. As the run becomes larger (because the run belongs to a relatively lower layer), the mapping pairs are likely to be arranged more densely in the run. Therefore, it may be more advantageous to use PLR. Since the size of the index information stored in the bloom filter is determined by the target FPR and the guard density within the run, not the run size, the index information based on the bloom filter requires the same number of bits for each mapping entry regardless of the run size.

Referring to Fig. 7(a), we can see the change in the number of bits per mapping item according to the change in the run size (when the run unit size is 10 GB and the total capacity of the SSD device is 1 TB). For small runs, the indexing based on the bloom filter is better, but as the run size increases, we can see that the indexing based on the PLR model (denoted as OURS) shows better memory efficiency. In addition, when compared with the conventional PLR (denoted as PLR (ORIG)), we can see that the indexing based on the bloom filter or the indexing based on the PLR model according to the embodiment of the present disclosure is better in memory optimization.

Based on <Mathematical Formula 4> and Fig. 7(a), when the same number of LBAs to be mapped is determined (determined by the SSD capacity), it is more likely to manage more runs in the memory-efficient PLR model, so it may be better to increase the average run size, R _avg . R _avg can be obtained by dividing the capacity C of the SSD by the number of runs N run of the tree. Since N _run = h T, Ravg can be defined according to <Mathematical Formula 5>.

<Equation 5> shows that the average size of a run can be increased by decreasing T or increasing |L ₀ |.

FIG. 7(b) shows the memory usage ratio according to the change of |L ₀ | and T at the sector level for the LSM-tree (141 to 143) of the SSD controller (110) according to the embodiment of the present disclosure. Indexing based on the Bloom filter or the PLR model is used for each layer. Two facts can be confirmed from FIG. 7(b): first, the memory requirement is mainly determined by T, and second, the size of L ₀ has a negligible effect on the memory occupancy. Therefore, by increasing |L ₀ |, N run can be reduced, and consequently R _avg can be increased. However, since N _run and R _avg change logarithmically with |L ₀ |, the effect may not be significant unless |L ₀ | is very large.

According to <Mathematical Formula 3>, as T and L0 decrease, LSM-tree(141~143) can increase, and therefore WAF can increase. Fig. 7(c) shows the change in WAF of LSM-tree(141~143) for the combination of T and L0 of Fig. 7(b), and it can be confirmed that there is a trade-off between memory and WAF. Therefore, in the read-only mode, write efficiency is not that important, so small T and _L0 can be better. On the contrary, in the large-capacity write mode, memory should be sacrificed for a lower WAF. For most cases, the balance of LSM-tree(141~143) should be achieved, and the memory occupancy of LSM-tree(141~143) was 20.3% at T=14 and | _L0 |=5.4GB, and the WAF was also an acceptable level of 3. In this case, the LSM-tree (141-143) can have three layers, the top layer is based on exact indexing, the middle layer is based on a bloom filter, and the third lower layer can be based on a PLR model.

Once the tree configuration is determined, the WAF can be fine-tuned by changing the FPR. Figure 7(d) shows the change in memory usage according to the change in FPR.

Referring to FIG. 8, the results of comparing the performance of an SSD controller (110) according to one embodiment of the present disclosure with that of a conventional technology are described.

SECTOR of FIG. 8 is a sector-level FTL that performs all mapping relationships in DRAM based on accurate indexing, and the performance of APX-FTL (APX) according to an embodiment of the present invention can be verified compared to conventional DFTL, SFTL, and TPFTL. FIG. 8 shows the results of a performance experiment for operations of random writes (RW), sequential reads (SR), random reads (RR), and sequential writes (SW). Referring to FIG. 8(a), SECTOR shows the best performance for all workloads, but SECTOR inherently has a problem of requiring a huge table capacity. It can be verified that APX-FTL according to an embodiment of the present disclosure has similar performance to other conventional methods for SR operations, and similar to SECTOR in RR, i.e., random read mode, and superior performance than other conventional methods. Therefore, it can be verified that APX-FTL according to an embodiment of the present disclosure shows consistent response performance in data read regardless of locality.

Fig. 8(b) shows the CDF(Cumulative Distribution Function) performance comparison results of read delay. As with Fig. 8(a), it can be confirmed that in RR, i.e., random read mode, it is similar to SECTOR and has superior performance compared to other conventional methods. Compared to demand-based conventional methods, the average delay was 35% shorter and the 99th read delay was 30% shorter.

Fig. 9 shows the results of performance comparison in a real working environment accommodating filebench workloads of OLTP, Varmali and Webproxy. The CDF performance of read delay in Fig. 9(a) confirms that APX-FTL according to the embodiment of the present disclosure is superior to other demand-based FTL methods and shows similar results to SECTOR based on accurate indexing. The results in Fig. 9(b) also confirm the high performance results, and the miss ratio in Fig. 10 also confirms the high performance of APX-FTL according to the embodiment of the present disclosure.

An operation method of an SSD device according to an embodiment of the present disclosure will be described with reference to FIGS. 11 and 12. Parts that overlap with those described above will be omitted for detailed description.

According to an embodiment of the present disclosure, a method for operating an SSD device includes an interface logic connected to a host, a non-volatile memory storing data, and a controller controlling the non-volatile memory, the method including a step (S110) in which the controller receives a logical address transmitted by the host, a step (S120) in which the controller converts the received logical address into a physical address for the non-volatile memory based on index information stored in a plurality of layers configured as an LSM-tree having a hierarchical structure, and a step (S130) in which the controller accesses the non-volatile memory based on the physical address. At least two layers among the plurality of layers of the LSM-tree store index information based on a mapping of a logical address and a physical address corresponding to the logical address in different ways.

The multiple layers of the LSM-tree can be composed of the top layer (L0) that stores index information of a logical address and the physical address that is exactly mapped to the logical address, and the middle and lower layers (L1 to Lh-1) that store index information that guesses the physical address mapped to the logical address.

In one embodiment, the step (S120) of converting a logical address into a physical address may include a step (S122) of the controller querying a top layer among multiple layers of an LSM-tree that stores a logical address and a physical address mapped to the logical address as index information in the form of a pair, or a step (S123, S124) of the controller querying layers other than the top layer that store index information that estimates a physical address mapped to the logical address in a guessing manner.

In one embodiment, when the controller queries other layers storing index information that guesses a physical address mapped to a logical address in a speculative manner, the method may include a step (S123) of querying at least one middle layer storing index information based on approximate indexing that probabilistically guesses a physical address based on a bloom filter, or a step (S124) of querying at least one lower layer storing index information based on approximate indexing that probabilistically guesses a physical address based on a PLR model.

In one embodiment, the controller may optionally include a step (S121) of searching a shortcut table storing information on a run in which index information corresponding to a logical address exists to specify a run in which index information is stored before searching for index information of each layer, and may search for index information corresponding to a logical address for the run searched in the shortcut table.

In one embodiment, the controller may further include a step (S125) of searching for a physical address corresponding to index information searched in the run based on a sort table storing mapping information between a run chunk and a memory block of a non-volatile memory. The run chunk may have the same size as a memory block of the non-volatile memory, and thus may operate as a continuous sector for physically scattered memory blocks.

Although the embodiments of the present disclosure described above have been described as being implemented in a controller of an SSD, it does not exclude that they may be implemented as a conversion component of a logical address in a host.

The above-described present disclosure can be implemented as a computer-readable code on a medium in which a program is recorded. The computer-readable medium includes all kinds of recording devices that store data that can be read by a computer system. Examples of the computer-readable medium include a hard disk drive (HDD), a solid state disk (SSD), a silicon disk drive (SDD), a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, an optical data storage device, and the like. In addition, the computer may include a processor of each device.

Meanwhile, the above program may be specially designed and configured for the present disclosure or may be known and available to those skilled in the art of computer software. Examples of the program may include not only machine language codes such as those produced by a compiler, but also high-level language codes that can be executed by a computer using an interpreter or the like.

The use of the term "above" and similar referential terms in the specification of this disclosure (especially in the claims) may refer to both the singular and the plural. In addition, when a range is described in this disclosure, it is intended that the invention be applied to individual values falling within the range (unless otherwise stated), and it is the same as describing each individual value constituting the range in the detailed description of the invention.

Unless there is an explicit description of the order or the contrary for the steps constituting the method according to the present disclosure, the steps can be performed in any suitable order. The present disclosure is not necessarily limited by the description order of the steps. The use of all examples or exemplary terms (e.g., etc.) in this disclosure is merely for the purpose of describing the present disclosure in detail and the scope of the present disclosure is not limited by the examples or exemplary terms unless limited by the claims. In addition, those skilled in the art will appreciate that various modifications, combinations, and changes can be configured according to design conditions and factors within the scope of the appended claims or their equivalents.

Therefore, the spirit of the present disclosure should not be limited to the embodiments described above, and not only the scope of the patent claims described below but also all scopes equivalent to or equivalently modified from the scope of the patent claims are included in the scope of the spirit of the present disclosure.

100: SSD device
200: Host
141: Top layer
142: Middle class
143: Lower class
144: Shortcut Table
145: Sorting Table

Claims (20)

Interface logic that connects to the host;
Non-volatile memory where data is stored; and
A controller comprising: a controller controlling the non-volatile memory;
The controller converts a logical address provided by the host into a physical address for the non-volatile memory, and accesses the non-volatile memory based on the physical address.
The above controller converts the logical address into the physical address based on indexing information stored in multiple layers consisting of a hierarchical structure, LSM-tree (log-structured merge tree), and
At least two of the above layers among the plurality of said layers of the LSM-tree store the index information based on the mapping of the logical address and the physical address corresponding to the logical address in different ways.
Solid state drive (SSD) device.
In the first paragraph,
Among the multiple layers of the LSM-tree, the top layer stores the logical address and the physical address mapped to the logical address as the index information, and layers other than the top layer store the index information that estimates the physical address mapped to the logical address in a guessing manner.
Solid state drive (SSD) device.
In the second paragraph,
Layers other than the top layer above,
At least one intermediate layer storing the index information based on approximate indexing that probabilistically guesses the physical address based on a bloom filter; and
Consisting of at least one lower layer storing the index information based on approximate indexing that probabilistically estimates the physical address based on a piece-wise linear regression (PLR) model,
Solid state drive (SSD) device.
In the second paragraph,
The above controller,
Obtaining the physical address mapped to the logical address as a single lookup in the uppermost layer,
The physical address mapped to the logical address can be obtained by at least one lookup in the layer other than the uppermost layer.
Solid state drive (SSD) device.
In the third paragraph,
The above intermediate layer stores the hash value of the above logical address,
When the controller searches for a first physical address corresponding to a first logical address in the intermediate layer, the controller obtains a first estimated physical address corresponding to a bloom filter having a hash value identical to a hash value of the first logical address based on the index information of the intermediate layer.
Solid state drive (SSD) device.
In the third paragraph,
When the controller stores the index information based on the mapping of the first logical address and the first physical address corresponding to the first logical address in the intermediate layer in the write mode,
Store the hash value of the first logical address in a bloom filter corresponding to the first physical address to be mapped to the first logical address, store the first logical address in an out-of-band area (OOB area) corresponding to the first physical address, and store data in the first physical address.
Solid state drive (SSD) device.
In the third paragraph,
When the controller searches for a second physical address corresponding to a second logical address in the lower layer, the controller obtains a second estimated physical address that exists within a preset error range based on the second physical address corresponding to the second logical address based on the index information of the lower layer.
Solid state drive (SSD) device.
In the third paragraph,
If the above lower layer stores the index information of the second logical address and the second physical address corresponding to the second logical address,
Storing the PLR model capable of calculating a second estimated physical address within a preset error range based on the second physical address based on the second logical address;
Solid state drive (SSD) device.
In Article 8,
The above lower layer stores a plurality of PLR models having different slopes and intercepts, each of which is capable of producing an estimated physical address for a set of different logical addresses.
Solid state drive (SSD) device.
In the first paragraph,
Each of the plurality of said layers includes at least one run that maintains said index information,
The controller searches a shortcut table storing information of the run in which the index information corresponding to the first logical address exists for the first logical address conversion, and searches for the index information corresponding to the first logical address from a plurality of index information of the run searched in the shortcut table.
Solid state drive (SSD) device.
In Article 10,
The above run is composed of a plurality of run chunks, and the run chunks are the same size as the memory blocks of the non-volatile memory,
The controller searches for the physical address corresponding to the index information based on a sorted table that stores mapping information between the run chunk and the memory block.
Solid state drive (SSD) device.
In the first paragraph,
The plurality of said layers are composed of a top layer, at least one middle layer, and at least one lower layer in the order of the layers, and the lower layer among the two adjacent layers is larger than the upper layer by a preset multiple, and each of the said layers includes at least one run that stores the said index information, and the run stores the plurality of said index information by arranging them in the order of the logical addresses of the said index information,
The controller moves at least one index information of the saturated layer to the layer located below in the order of the top layer, the middle layer, and the lower layer, when all runs of any one of the layers are saturated.
Solid state drive (SSD) device.
Interface logic that connects to the host;
Non-volatile memory where data is stored; and
A method of operating an SSD (Solid State Drive) device including a controller controlling the above non-volatile memory,
A step in which the controller receives a logical address transmitted by the host;
A step of converting the logical address provided by the controller into a physical address for the non-volatile memory based on indexing information stored in multiple layers consisting of a hierarchical structure, LSM-tree (log-structured merge tree); and
The above controller comprises a step of accessing the non-volatile memory based on the physical address,
At least two of the above layers among the plurality of said layers of the LSM-tree store the index information based on the mapping of the logical address and the physical address corresponding to the logical address in different ways.
How a Solid State Drive (SSD) device works.
In Article 13,
The steps for converting to the above physical address are:
The step of the controller searching for the uppermost layer among the plurality of layers of the LSM-tree, which stores the logical address and the physical address mapped to the logical address as the index information in the form of a pair, or the step of the controller searching for layers other than the uppermost layer, which stores the index information that estimates the physical address mapped to the logical address in a guessing manner.
How a Solid State Drive (SSD) device works.
In Article 14,
The step in which the above controller searches layers other than the top layer is:
A step in which the controller searches at least one intermediate layer storing the index information based on approximate indexing that probabilistically guesses the physical address based on a Bloom filter, or a step in which the controller searches at least one lower layer storing the index information based on approximate indexing that probabilistically guesses the physical address based on a Piece-wise linear regression (PLR) model.
How a Solid State Drive (SSD) device works.
In Article 15,
The above intermediate layer stores the hash value of the above logical address,
The step in which the above controller queries the intermediate layer is:
The step of the controller obtaining a first estimated physical address corresponding to a bloom filter having a hash value identical to a hash value of the first logical address based on the index information of the intermediate layer,
How a Solid State Drive (SSD) device works.
In Article 15,
When the controller stores the index information based on the mapping of the first logical address and the first physical address corresponding to the first logical address in the intermediate layer in the write mode,
The step of the controller storing a hash value of the first logical address in a bloom filter corresponding to the first physical address to be mapped to the first logical address; and
The controller comprises a step of storing the first logical address in an out-of-band area (OOB area) corresponding to the first physical address and storing data in the first physical address.
How a Solid State Drive (SSD) device works.
In Article 15,
When the above controller looks up the second physical address corresponding to the second logical address in the lower layer,
The step in which the above controller searches the lower layer is:
The controller comprises a step of obtaining a second estimated physical address that exists within a preset error range based on a second physical address corresponding to a second logical address based on the index information of the lower layer.
How a Solid State Drive (SSD) device works.
In Article 15,
When the above controller stores the index information of the second logical address and the second physical address corresponding to the second logical address in the lower layer,
The step of storing or modifying the PLR model capable of calculating a second estimated physical address within a preset error range based on the second physical address based on the second logical address, wherein the controller
How a Solid State Drive (SSD) device works.
In Article 13,
Each of the plurality of said layers includes at least one run that maintains said index information,
The steps for converting to the above physical address are:
A step in which the controller searches a shortcut table storing information of the run in which the index information corresponding to the first logical address exists for the first logical address conversion; and
The above controller comprises a step of searching for the index information corresponding to the first logical address from the plurality of index information of the runs searched in the shortcut table.
How a Solid State Drive (SSD) device works.

Images