Stripe reconstituting method performed in storage system, method of performing garbage collection by using the stripe reconstituting method, and storage system performing the stripe reconstituting method

Patent metadata

Field	Value
Publication number	US-9817717-B2
Application number	US-201514968472-A
Country	US
Kind code	B2
Filing date	Dec 14, 2015
Priority date	Dec 29, 2014
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

A stripe reconstituting method in a storage system, a garbage collection method employing the stripe reconstituting method, and the storage system performing the stripe reconstituting method are provided. The stripe reconstituting method includes the operations of selecting a target stripe in which an imbalance between valid page ratios of memory blocks included in the target stripe exceeds an initially-set threshold value, from among stripes produced in a log-structured storage system; and reconstituting a stripe by regrouping the memory blocks included in the target stripe such that the imbalance between the valid page ratios of the memory blocks included in the target stripe is reduced.

First claim

What is claimed is:

1. A stripe reconstituting method in a log-structured storage system, the stripe reconstituting method comprising:
identifying, based on an analysis for an imbalance between valid page ratios of memory blocks included in a target stripe that exceeds an initially-set threshold value;
selecting, by a memory controller, the target stripe in which the imbalance between valid page ratios of memory blocks included in the target stripe exceeds the initially-set threshold value, from among stripes produced in the log-structured storage system; and
reconstituting, by the memory controller, a stripe by regrouping the memory blocks included in the target stripe such that the imbalance between the valid page ratios of the memory blocks included in the target stripe is reduced.

2. The stripe reconstituting method of claim 1 , wherein, in the selecting of the target stripe, a stripe in which valid page ratios of at least one memory block in the stripe are less than an initially-set first threshold value and valid page ratios of remaining memory blocks in the stripe are greater than an initially-set second threshold value is selected as the target stripe, and the initially-set second threshold value is greater than the initially-set first threshold value.

3. The stripe reconstituting method of claim 2 , wherein, in the selecting of the target stripe, when there exists a plurality of stripes in each of which valid page ratios of at least N (where N is an integer equal to or greater than 1) memory blocks are less than the initially-set first threshold value and valid page ratios of remaining memory blocks are greater than the initially-set second threshold value, a single target stripe is selected from the plurality of stripes, based on at least one selected from a descending order of values of N, an ascending order of valid page ratios that are less than the first threshold value, and a descending order of valid page ratios that are greater than the second threshold value.

4. The stripe reconstituting method of claim 1 , wherein, in the reconstituting of the stripe, the memory blocks of the target stripe are regrouped such that at least one target memory block having a low valid page ratio from among the memory blocks included in the target stripe is replaced by a memory block having a higher valid page ratio than the at least one target memory block from among memory blocks included in another stripe.

5. The stripe reconstituting method of claim 4 , wherein the reconstituting of the stripe comprises:
selecting at least one memory block having a high valid page ratio from among the memory blocks included in the other stripe in order to replace the at least one target memory block having a low valid page ratio in the target stripe;
producing a new stripe by replacing the at least one target memory block having a low valid page ratio in the target stripe with the at least one memory block having a high valid page ratio in the other stripe; and
writing parity information about the new stripe to a memory block included in the new stripe.

6. The stripe reconstituting method of claim 5 , wherein the selecting of the at least one memory block comprises selecting a replacement memory block from a storage device in which the memory block to be replaced in the target stripe exists.

7. The stripe reconstituting method of claim 5 , wherein the parity information about the new stripe is calculated by performing an XOR calculation on the parity information about the target stripe, data stored in the memory block that is replaced, and data stored in a replacement memory block.

8. The stripe reconstituting method of claim 5 , further comprising:
adding information about the new stripe to a stripe mapping table and deleting information about the target stripe from the stripe mapping table.

9. The stripe reconstituting method of claim 5 , wherein the reconstituting of the stripe comprises:
copying valid pages included in the at least one target memory block replaced in the target stripe into a non-volatile cache memory; and
erasing a memory block in which the parity information about the target stripe has been stored.

10. The stripe reconstituting method of claim 5 , wherein the reconstituting of the stripe comprises:
copying valid pages included in the at least one target memory block replaced in the target stripe into memory blocks constituting an orphan stripe and a non-volatile cache memory; and
erasing the at least one target memory block replaced in the target stripe and a memory block in which the parity information about the target stripe has been stored,
wherein, the orphan stripe is a stripe designated as a stripe into which valid pages are copied during garbage collection.

11. The stripe reconstituting method of claim 5 , further comprising:
updating information about a number of stripes formed by each of the memory blocks included in the target stripe and information about a number of stripes formed by each of the memory blocks included in the new stripe.

12. The stripe reconstituting method of claim 1 , wherein, in the reconstituting of the stripe, the memory blocks of the target stripe are regrouped such that at least one target memory block having a low valid page ratio from among the memory blocks included in the target stripe is excluded from the target stripe.

13. The stripe reconstituting method of claim 12 , wherein the reconstituting of the stripe comprises:
producing a new stripe by excluding the at least one target memory block from the target stripe;
calculating parity information about the new stripe and writing the calculated parity information to a memory block included in the new stripe; and
adding information about the new stripe to a stripe mapping table and deleting information about the target stripe from the stripe mapping table.

14. The stripe reconstituting method of claim 13 , wherein the reconstituting of the stripe comprises:
copying valid pages included in the at least one target memory block excluded from the target stripe into memory blocks constituting an orphan stripe and a non-volatile cache memory; and
erasing the at least one target memory block excluded from the target stripe and a memory block in which the parity information about the target stripe has been stored,
wherein, the orphan stripe is a stripe designated as a stripe into which valid pages are copied during garbage collection.

15. The stripe reconstituting method of claim 1 , wherein the reconstituting of the stripe comprises searching for another target stripe in which a memory block having a relatively low valid page ratio does not overlap a memory block having a relatively low valid page ratio from among the memory blocks included in the target stripe, and exchanging memory blocks between the target stripe and the other target stripe to produce a new stripe comprised of memory blocks having high valid page ratios and another new stripe comprised of memory blocks having low valid page ratios.

16. The stripe reconstituting method of claim 15 , wherein the reconstituting of the stripe comprises:
producing the new stripe comprised of memory blocks having high valid page ratios and the other new stripe comprised of memory blocks having low valid page ratios by exchanging memory blocks between the target stripe and the other target stripe;
calculating parity information about each of the new stripe and the other new stripe and writing each of the calculated parity information to respective memory blocks included in the new stripe and the other new stripe;
erasing the memory blocks in wh

Assignees

• Lee Ju-Pyung
• Samsung Electronics Co Ltd

Inventors

• Lee Ju-Pyung

Classifications

• G06F3/0629 Primary

  Configuration or reconfiguration of storage systems · CPC title

• G06F11/1088 Primary

  Reconstruction on already foreseen single or plurality of spare disks · CPC title

• G06F11/1044

  with specific ECC/EDC distribution · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F12/02 Primary

  Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00) · CPC title