Granted Patent B2

US 12,443,345 · App. 18/453,967 · Granted Oct 14, 2025

Inventors: Kyoungho Koo (Daejeon, KR); Youjip Won (Daejeon, KR)

Assignees: SK hynix Inc.; Korea Advanced Institute of Science and Technology

G06F3/061G06F3/0653G06F3/0673G06F2212/7208

Abstract

Claims (31)

1. A multi-level data storage device comprising:

a first storage device;

a second storage device located at a lower level than the first storage device;

an input/output (I/O) control circuit configured to control a first write operation for the first storage device and a second write operation for the second storage device; and

an imbalance control circuit configured to calculate an imbalance index corresponding to a write set that is generated when a sum of a number of first write operations and a number of second write operations becomes a predetermined number, and configured to control the I/O control circuit to control imbalance of write operations performed in the multi-level data storage device by controlling the first write operation or the second write operation based on the imbalance index,

wherein the imbalance control circuit calculates the imbalance index by dividing an average latency of the second write operations included in the write set by an average latency of the first write operations included in the write set, and

wherein, when the write set is a first write set, the imbalance control circuit controls the I/O control circuit to reduce an imbalance index for a second write set when the imbalance index for the first write set indicates an imbalance state, the second write set being generated to follow the first write set.

2. The multi-level storage device of claim 1 , wherein the imbalance control circuit monitors a minimum value of an imbalance index and generates a threshold value from the minimum value to be compared with the imbalance index.

3. The multi-level storage device of claim 1 , wherein the imbalance control circuit controls the I/O control circuit to insert a predetermined waiting time between first write operations included in the second write set when the imbalance state is determined.

4. The multi-level storage device of claim 1 , wherein the first storage device and the second storage device each store a key-value (KV) set according to levels of a log-structured merge (LSM) tree,

wherein the first storage device stores a plurality of KV sets corresponding to level 0 of the LSM tree, and

wherein when the imbalance state is determined, the imbalance control circuit controls the I/O control circuit to change a KV set corresponding to the level 0 into one or more KV sets corresponding to level 1 to keep the one or more KV sets corresponding to the level 1 in the first storage device.

5. The multi-level storage device of claim 4 , wherein when a used storage space of the first storage device exceeds a space threshold, the imbalance control circuit controls the I/O control circuit to move the one or more KV sets corresponding to the level 1 stored in the first storage device to the second storage device.

6. The multi-level storage device of claim 4 , wherein if the imbalance state is not determined, the imbalance control circuit controls the I/O control circuit to store the one or more KV sets corresponding to the level 1 in the second storage device when the KV set corresponding to the level 0 is changed to the one or more KV sets in the level 1.

7. An operation method of a multi-level data storage device including a first storage device storing data by performing a first write operation and a second storage device storing data by moving the data stored in the first storage device to the second storage device by performing a second write operation, the operation method comprising:

generating a first write set when a sum of a number of first write operations and a number of second write operations becomes a predetermined number;

calculating an imbalance index corresponding to the first write set by using an average latency of the first write operations and an average latency of the second write operations corresponding to the first write set;

determining an imbalance state based on the imbalance index; and

controlling imbalance of write operations performed in the multi-level data storage device by controlling the first write operation or the second write operation so that an imbalance index corresponding to a second write set is reduced when the imbalance state is determined, the second write set being generated to follow the first write set,

wherein calculating the imbalance index includes dividing an average latency of second write operations by an average latency of first write operations, corresponding to the first write set.

8. The operation method of claim 7 , wherein determining the imbalance state includes:

monitoring a minimum value of the imbalance index and determining a threshold value from the minimum value; and

comparing the threshold value with the imbalance index.

9. The operation method of claim 7 , wherein controlling the imbalance includes inserting a predetermined waiting time between first write operations in the second write set.

10. The operation method of claim 7 , wherein the first storage device and the second storage device each store a key-value (KV) set according to levels of a log-structured merge (LSM) tree, and the first storage device stores a plurality of KV sets corresponding to level 0 of the LSM tree,

wherein when the imbalance state is determined, controlling the imbalance includes:

changing a KV set corresponding to the level 0 to one or more KV sets corresponding to level 1; and

storing the one or more KV sets corresponding to the level 1 in the first storage device without performing the second write operation.

11. The operation method of claim 10 , wherein controlling the imbalance further includes:

determining whether a used storage space of the first storage device exceeds a space threshold; and

performing a second write operation to move the one or more KV sets stored in the first storage device to the second storage device when the storage space exceeds the storage threshold.

Assignments (1)

Priority Claims (2)

Continuity (1)

References Cited (46)