Flash memory device including deduplication, and related methods

Patent metadata

Field	Value
Publication number	US-9841918-B2
Application number	US-201514956715-A
Country	US
Kind code	B2
Filing date	Dec 2, 2015
Priority date	Dec 2, 2015
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

A flash memory device includes physical pages that store data sectors therein. The method of operating the flash memory device includes receiving write data sectors to be stored in the flash memory device, pairing the write data sectors with write data sectors and with written data sectors previously stored in physical pages of the flash memory device based upon a matching and deduplication operation to define data sector pairs and a difference therebetween, and rewriting to the physical pages of the flash memory device, in a partial-page writing mode, to store the difference between the write data sector and its respective paired data sector. The partial-page writing mode is performed on a respective physical page after a previous programming and before erasing. The written data sectors included in the data sector pairs only partially occupy the corresponding physical page of the flash memory device. The difference between the write data sector and its respective paired data sector is stored in an unoccupied portion of the corresponding physical page of the flash memory device.

First claim

What is claimed is:

1. A method, executed by a memory controller, of storing data within a flash memory device having physical pages, each of the physical pages constituting a maximum portion of the flash memory device that is capable of being simultaneously programmed with data and each of the physical pages being capable of storing multiple data sectors, the method comprising:
receiving, from a host device, new data sectors to be stored in the flash memory device;
matching the new data sectors with stored data sectors being previously stored in a physical page of the flash memory device, based upon a maximal weighted bipartite matching, such that sum of weights between the new data sectors and the stored data sectors is maximized, each of the weights between the new data sectors and the stored data sectors is a similarity between corresponding two sectors;
deduplicating the new data sectors and the stored data sectors to define a difference therebetween according to a result of the matching; and
writing the difference to an unoccupied portion of the physical page, without overwriting the stored data sectors.

2. The method of claim 1 , wherein the similarity is determined by a sub-set of data chunks whose hash function is in a predetermined region.

3. The method of claim 1 , wherein the writing is performed on the physical page after a previous programming and before erasing.

4. The method of claim 1 , wherein the stored data sectors only partially occupy the physical page.

5. The method of claim 1 , wherein the matching maximizes a number of data sector pairs that can be deduplicated.

6. The method of claim 1 , wherein the deduplicating is applied to fewer than all of the data sectors, excluding difference data previously acquired through deduplication, within the physical page storing previously-written data.

7. The method of claim 1 , wherein:
the physical page comprises an array of memory cells, including multi-level cells (MLC) or triple-level cells (TLC), coupled between word lines and bit lines that address the physical page; and
the stored data sectors are addressed by one of the word lines addressing the physical page and the difference is addressed by another of the word lines addressing the physical page.

8. A data storage system comprising:
a flash memory device comprising a physical page for storing multiple data sectors, the physical page constituting a maximum portion of the flash memory device that is capable of being simultaneously programmed with data; and
a memory controller that:
receives, from a host device, new data sectors to be stored in the flash memory device;
matches the new data sectors with stored data sectors being previously stored in a physical page of the flash memory device, based upon a maximal weighted bipartite matching, such that sum of weights between the new data sectors and the stored data sectors is maximized, each of the weights between the new data sectors and the stored data sectors is a similarity between corresponding two sectors;
deduplicates the new data sectors and the stored data sectors to define a difference therebetween according to a result of the matching; and
writes the difference to an unoccupied portion of the physical page, without overwriting the stored data sectors.

9. The data storage system of claim 8 , wherein:
the physical page comprises an array of memory cells, including multi-level cells (MLC) or triple-level cells (TLC), coupled between word lines and bit lines that address the physical page; and
the stored data sectors are addressed by one of the word lines addressing the physical page and the difference is addressed by another of the word lines addressing the physical page.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Erez Elona
• Dor Avner
• Kong Jun Jin

Classifications

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F12/00

  Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06) · CPC title

• G11C16/10 Primary

  Programming or data input circuits · CPC title