# US 12,007,887 B2 · Method and system for garbage collection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,007,887 B2 - Document ID: US12007887B2 - Status: Granted - Kind: B2 - Application number: 17/752,449 - Filed: 2022-05-24 - Published: 2022-12-01 - Granted: 2024-06-11 - Earliest claimed: 2021-05-25 - Assignees: SK hynix Inc. - Applicants: SK hynix Inc. - Inventors: Soon Yeal Yang - Web page: https://patentgrep.com/patent/US12007887B2 ## CPC - G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory} - G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing - G06F 12/0882: Page mode - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A storage device may include a memory device including a plurality of memory dies; and a memory controller configured to control the memory device in units of super blocks each including two or more memory blocks included in the memory device, wherein at least one of the super blocks within the memory device is a super block including a plurality of small multi-die zones each including a portion of each of the memory blocks included in different memory dies among the memory dies, wherein the memory controller is further configured to receive a garbage collection request and information on valid pages included in the small multi-die zone, and to select, among the super blocks within the memory device, a victim super block in response to the garbage collection request and information on valid pages included in the small multi-die zone. ## Claims ### Claim 1 A storage device comprising: a memory device including a plurality of memory dies; and a memory controller configured to control the memory device in units of super blocks each including two or more memory blocks included in the memory device, wherein at least one of the super blocks within the memory device is a super block including a plurality of small multi-die zones each including a portion of each of the memory blocks included in different memory dies among the memory dies, and wherein the memory controller is further configured to receive a garbage collection request and information on valid pages included in the small multi-die zone, and to select, among the super blocks within the memory device, a victim super block in response to the garbage collection request, wherein the victim super block includes the plurality of small multi-die zones including one or more small multi-die zones having a ready-to-reset state in which a reset operation is performed on the victim super block to cause all small multi-die zones in the victim super block to be in an empty state by erasing the all small multi-die zones, and wherein the reset operation is not completed on the victim super block according to a state of another small multi-die zone in the victim super block. ### Claim 2 (depends on 1) The storage device of claim 1, wherein each of the small multi-die zones has one state among a full state in which an empty area does not exist in a corresponding zone, the empty state in which the corresponding zone is empty, an active state in which data is stored only in a partial area in the corresponding zone, and the ready-to-reset state in which the reset operation is performed on a super block including the corresponding zone to cause all small multi-die zones in the super block including the corresponding zone to be in the empty state by erasing the all small multi-die zones in the super block including the corresponding zone, and wherein the reset operation is not completed on the super block including the corresponding zone according to a state of another small multi-die zone in the super block including the corresponding zone. ### Claim 3 (depends on 2) The storage device of claim 2, wherein the memory controller selects, among the super blocks within the memory device, the victim super block from among super blocks formed of only the small multi-die zones that are in the full state and the ready-to-reset state. ### Claim 4 (depends on 3) The storage device of claim 3, wherein the information on the valid pages included in the small multi-die zone includes information on valid pages included in the small multi-die zone in the full state in each of the super blocks within the memory device. ### Claim 5 (depends on 4) The storage device of claim 4, wherein the memory controller selects the victim super block based on the information on the valid pages included in the small multi-die zone. ### Claim 6 (depends on 4) The storage device of claim 4, wherein the information on the valid pages included in the small multi-die zone that is in the full state includes a number of valid pages included in the small multi-die zone that is in the full state and a list of small multi-die zones each including a predetermined number of valid pages or more. ### Claim 7 (depends on 4) The storage device of claim 4, wherein the memory controller selects the victim super block based on a number of the small multi-die zones that are in the ready-to-reset state. ### Claim 8 (depends on 3) The storage device of claim 3, wherein the memory controller is further configured to copy data stored in the small multi-die zones that are in the full state in the victim super block, and store the data in another super block including a plurality of small multi-die zones. ### Claim 9 (depends on 2) The storage device of claim 2, wherein the memory controller is further configured to perform the reset operation on a selected super block including the plurality of small multi-die zones by: switching states of all small multi-die zones in the selected super block to the ready-to-reset state, and erasing all switched small multi-die zones for the states of the all switched small multi-die zones to become the empty state. ### Claim 10 (depends on 1) The storage device of claim 1, wherein at least one of the super blocks within the memory device is a super block including a plurality of small single-die zones each including one or more memory blocks in one memory die. ### Claim 11 A method of operating a storage device comprising a memory device including a plurality of memory dies and a memory controller controlling the memory device in units of super blocks each including two or more memory blocks included in the memory device, the method comprising: receiving a garbage collection request and information on valid pages; and selecting, among the super blocks within the memory device, a victim super block based on the information on the valid pages, wherein at least one of the super blocks within the memory device is a super block including a plurality of small multi-die zones each including a portion of each of the memory blocks included in different memory dies among the memory dies, wherein the valid pages are included in the small multi-die zone, wherein the victim super block includes the plurality of small multi-die zones including one or more small multi-die zones having a ready-to-reset state in which a reset operation is performed on the victim super block to cause all small multi-die zones in the victim super block to be in an empty state by erasing the all small multi-die zones, and wherein the reset operation is not completed on the victim super block according to a state of another small multi-die zone in the victim super block. ### Claim 12 (depends on 11) The method of claim 11, wherein each of the small multi-die zones has one state among a full state in which an empty area does not exist in a corresponding zone, the empty state in which the corresponding zone is empty, an active state in which data is stored only in a partial area in the corresponding zone, and the ready-to-reset state in which the reset operation is performed on a super block including the corresponding zone to cause all small multi-die zones in the super block including the corresponding zone to be in the empty state by erasing the all small multi-die zones in the super block including the corresponding zone, wherein the reset operation is not completed on the super block including the corresponding zone according to a state of another small multi-die zone in the super block including the corresponding zone, and wherein the victim super block is selected from among super blocks formed of only the small multi-die zones that are in the full state and the ready-to-reset state among the super blocks within the memory device. ### Claim 13 (depends on 12) The method of claim 12, wherein the selecting of the victim super block comprises: selecting, among the super blocks within the memory device, candidate super blocks each formed of only the small multi-die zones that are in the full state and the ready-to-reset state; and selecting, among the candidate super blocks, the victim super block based on a number of valid pages included in the small multi-die zone that is in the full state in each of the candidate super blocks. ### Claim 14 (depends on 13) The method of claim 13, wherein the information on the valid pages included in the small multi-die zone includes information related to the number of valid pages included in the small multi-die zone that is in the full state in each of the super blocks within the memory device. ### Claim 15 (depends on 13) The method of claim 13, wherein the selecting of the victim super block among the candidate super blocks comprises: calculating a cost based on a number of the small multi-die zones that are in the ready-to-reset state in each of the candidate super blocks; adjusting the cost based on the number of the valid pages included in the small multi-die zone of the full state in each of the candidate super blocks; and comparing the adjusted costs of the candidate super blocks. ### Claim 16 (depends on 13) The method of claim 13, further comprising: copying data stored in the small multi-die zones of the full state in the victim super block; storing the copied data in another super block; and erasing the victim super block. ### Claim 17 (depends on 16) The method of claim 16, wherein the another super block is a super block including the plurality of small multi-die zones. ### Claim 18 (depends on 11) The method of claim 11, wherein at least one of the super blocks within the memory device is a super block including a plurality of small single-die zones each including one or more memory blocks in one memory die.