Source: https://patents.google.com/patent/US9665287B2/en
Timestamp: 2018-12-16 16:32:00
Document Index: 678967065

Matched Legal Cases: ['arts 400', 'art 400', 'art 400', 'art 400', 'art 400', 'art 400', 'art 600', 'art 700']

US9665287B2 - Data deduplication using a solid state drive controller - Google Patents
Data deduplication using a solid state drive controller Download PDF
US9665287B2
US9665287B2 US14858257 US201514858257A US9665287B2 US 9665287 B2 US9665287 B2 US 9665287B2 US 14858257 US14858257 US 14858257 US 201514858257 A US201514858257 A US 201514858257A US 9665287 B2 US9665287 B2 US 9665287B2
US14858257
US20170083245A1 (en )
Gongbiao NIU
A data deduplication method is executed by a controller for a solid state drive (SSD). The controller receives a signature for a block of data. The controller performs a comparison of the signature and information in a signature library and determines whether or not the signature matches the information. The controller sends a signal that indicates a result of the comparison. If the signature and the information match then the signal has a first value indicating that the block of data is already stored on the SSD; if the signature and the information do not match then the signal has a second value that is different than the first value.
Contemporary businesses accumulate tremendous amounts (e.g., petabytes) of data in databases that are stored on all kinds of media such as tapes, hard disk drives, solid state drives (SSDs), etc. Legal requirements, government rules and regulations, and business rules and best practices require that the databases are archived and backed up frequently. Consequently, thousands of petabytes (PBs) of data are already being stored, and the amount of stored data continues to skyrocket.
Data deduplication methods and systems are used to reduce the amount of data to increase efficiency and reduce costs. In general, a deduplication system finds identical parts in different data files and stores those identical parts only once. The deduplication system also maintains metadata so that the data files can be organized and rebuilt at a later time when they are accessed. However, the tremendous amounts of data being stored test the limits of existing deduplication methods and systems. Current deduplication methods and systems work well for several petabytes of data but are not designed for amounts of data on the scale of thousands of petabytes.
The use of SSDs (instead of other storage media such as random access memory (RAM)) to store large amounts of data presents some challenges. SSDs have longer read and write latencies relative to, for example, double data rate type three synchronous dynamic RAM (DDR3 DRAM). Also, SSDs are erased before being written to and can only be erased a limited number of times before wearing out.
On the other hand, SSDs have a number of advantages that make them a good choice for storing large amounts of data. For deduplication, files are split into blocks or fragments commonly referred to as “chunks” (e.g., four kilobyte (KB), 16 KB, or 256 KB chunks) with associated metadata. Each unique chunk is stored with its metadata. The metadata may be, for example, 16 bytes (B), 32 B, 128 B, or 256 B in size. For 512 PB of data, assuming each chunk is 16 KB in size and also assuming 32 B of metadata per chunk, the storage space for just the metadata is one PB. Storing this amount of data is not practical using RAM, but is practical using SSDs.
Also, to satisfy the aforementioned regulations and requirements, the metadata needs to be hard-written into storage. When power to RAM is lost or interrupted, the data held by the RAM is lost. SSDs use NAND-based flash memory, for example, which retains data without power.
Thus, the advantages of SSDs include their capacity and non-volatility. To mitigate their longer access time (read and write latencies), data is written in parallel. The basic unit of each SSD read/write operation is referred to as a page. For a page size of 16 KB, assuming 128 B of metadata per chunk, the metadata for 128 chunks can be read or written in parallel within a page.
The metadata for each chunk includes a hash value, or signature, that uniquely identifies the chunk. Hence, to determine whether it is necessary to store a new chunk (to determine whether an identical chunk has been previously stored), the signature for the new chunk can be compared to signatures for chunks that have already been stored. If the signature for the new chunk matches an existing signature, then the new chunk does not need to be stored.
As noted above, the basic unit of an SSD read/write operation is a page. To get the signature of a chunk for comparison to other signatures, an entire page (e.g., 16 KB) is read and transferred from the SSD to the central processing unit (CPU). This transfer can consume a significant amount of resources on the CPU as well as memory bandwidth and bus bandwidth.
More specifically, a client with data to be stored on a storage server will split the data into chunks and calculate a signature for each chunk. In an implementation, the client sends each signature to a signature server that holds a library of signatures for chunks already stored on the storage server. The signature server's role is to determine whether the signatures from the client match any of the signatures in the signature library. To accomplish this, an entire page (e.g., 16 KB) is transferred to memory for each signature, and the CPU will locate and extract the signature within the page and compare the extracted signature to the signatures from the client. However, a signature may be only 32 B in size. Thus, to get a signature for comparison to other signatures, up to 500 times more data than is needed is read and transferred (e.g., 16 KB of data is read to get a 32 B signature).
Furthermore, based on the number of clients that are requesting signature comparisons and the number of signature servers, the number of comparisons per signature server can be estimated. Each comparison requires at least two input/output (I/O) accesses, so the number of I/O operations per second (IOPS) per signature server can also be estimated. Considering CPU and SSD capabilities, the IOPS requirements turn out to be so large that a large number of signature servers are needed, and it is also necessary to use more expensive, higher bandwidth Peripheral Component Interconnect Express (PCIe) SSDs to provide the necessary capacity.
In summary, conventional deduplication methods are inefficient, expensive, and occupy significant amounts of CPU, memory, and bus resources.
Embodiments according to the present invention address the problems described above by accomplishing signature comparisons in the SSD. As a result, the CPU's workload is reduced and the amount of data being transferred between the SSD and the CPU is reduced, thereby also reducing the impact on memory and on bus bandwidth.
In embodiments according to the present invention, a data deduplication method is executed by a controller for an SSD. The controller receives a first signature for a block or fragment (a “chunk”) of data from the CPU. The controller performs a comparison of the first signature and information in a signature library and determines whether or not the first signature matches the information. The controller sends a signal to the CPU that indicates a result of the comparison. If the first signature matches information in the signature library, then the signal has a first value indicating that the chunk of data is already stored on the SSD; if the first signature does not match information in the signature library, then the signal has a second value that is different than the first value. If the first signature does not match information in the signature library (e.g., if the signal has the second value), then the chunk of data is received from its source (e.g., a client) and written to the SSD.
In an embodiment, the controller also receives an address associated with the first signature from the CPU. In such an embodiment, the controller uses the address to locate an entry in the signature library. The controller then compares the signature to the information at that entry. That information may be a second signature, or it may be a null value (e.g., the entry may not hold any information). The controller then sends a signal to the CPU to indicate the result of the comparison as described above.
In an embodiment, the signal from the SSD controller to the CPU consists of a single binary bit that has the first value if the first signature matches information in the signature library and that has the second value if the first signature does not match information in the signature library.
In an embodiment, if the first signature matches information in the signature library, then a counter associated with the chunk of data is incremented. If the first signature does not match information in the signature library, then the first signature is added to the signature library and a counter associated with the chunk of data is initialized and incremented.
In an embodiment, the controller includes, in addition to conventional components, a deduplication processor that compares the first signature and information from the signature library. In one such embodiment, the deduplication processor includes a number of gates that perform a bit-by-bit comparison of the first signature and information from the signature library.
In an embodiment, the SSD is a Serial Advanced Technology Attachment (SATA) SSD.
Embodiments according to the invention can be used for efficient deduplication in large-scale data applications where the amounts of stored data are measured in terms of exabytes (EBs). Fewer IOPS are required, and so embodiments according to the invention can be implemented using less expensive SATA SSDs.
FIG. 1 is a block diagram illustrating an example of a system upon which a deduplication system can be implemented in an embodiment according to the invention.
FIG. 2 is a block diagram illustrating elements of a computer system in an embodiment according to the present invention.
FIG. 3 is a block diagram showing a connection between SATA SSDs and a central processing unit in an embodiment according to the present invention.
FIG. 4 is a flowchart of a deduplication method in an embodiment according to the present invention.
FIG. 5 illustrates a circuit that can be used to implement a deduplication processor in an embodiment according to the present invention.
FIG. 6 is a flowchart of a data deduplication method executed by a controller for an SSD in an embodiment according to the present invention.
FIG. 7 is a flowchart of a data deduplication method executed by a signature server that includes a CPU and an SSD in an embodiment according to the present invention.
FIG. 8 is a block diagram illustrating an example of an implementation of a deduplication system in an embodiment according to the present invention.
It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present disclosure, discussions utilizing terms such as “receiving,” “storing,” “reading,” “writing,” “indexing,” “performing,” “sending,” “comparing,” “adding,” “accessing,” “locating,” “using,” “determining,” “generating,” “incrementing,” “signaling,” or the like, refer to actions and processes (e.g., flowcharts 400, 600, and 700 of FIGS. 4, 6, and 7, respectively) of an apparatus or computer system or similar electronic computing device or processor (e.g., the computer system 200 of FIG. 2). A computer system or similar electronic computing device manipulates and transforms data represented as physical (electronic) quantities within memories, registers or other such information storage, transmission or display devices.
Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, random access memory (RAM), read only memory (ROM), electrically erasable programmable ROM (EEPROM), flash memory (e.g., an SSD) or other memory technology, compact disk ROM (CD-ROM), digital versatile disks (DVDs) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information and that can accessed to retrieve that information.
FIG. 1 is a block diagram illustrating an example of a network or system 100 upon which a deduplication system can be implemented in an embodiment according to the invention. In the example of FIG. 1, the system 100 includes: a number of clients 101 a, 101 b, 101 c, . . . , 101 m, which may be singularly referred to as a client 101 m or collectively referred to as the clients 101; one or more configuration servers 102; and a number of signature servers 103 a, 103 b, 103 c, . . . , 103 n, which may be singularly referred to as the signature server 103 n and collectively referred to as the signature servers 103. The clients 101, signature servers 103, and configuration server 102 are communicatively coupled (wired or wirelessly) via a network 104 (e.g., the Internet, but not so limited).
The clients 101 may themselves be servers. In general, the clients 101 have data files that they have generated or that they have received from other devices or systems (not shown). A client 101 m splits the data files that it has into smaller pieces (e.g., blocks or fragments, commonly referred to as chunks). For each such chunk, the client 101 m calculates a signature Scp that uniquely identifies the chunk and sends the signature to the signature servers 103. In an embodiment, the signatures from the client 101 m are sent in batch mode; thus, multiple signatures (e.g., hundreds of signatures) can be grouped into a single data package and sent to the signature servers 103 for comparison.
In an embodiment, a signature for a chunk is calculated by applying a hash function to the contents of the chunk. In an embodiment, metadata is associated with each chunk, and the signature for a chunk is included in the metadata for that chunk. The metadata for a chunk may include information in addition to the signature for the chunk. For example, the metadata can include information that can be used to combine the chunk with other chunks associated with a data file in order to reconstruct the data file. For example, in addition to the signature, the metadata may include an address that points to where the data for the chunk is stored, and an appendix that identifies how (e.g., in what order) the chunk is to be combined with other chunks to reconstruct the data file.
The configuration server 102 schedules and controls traffic between the clients 101 and the signature servers 103. The configuration server 102 directs the signatures from the clients 101 to the proper signature server.
A signature server 103 n receives signatures from the clients 101 as directed by the configuration server 102, looks up entries (content or information, e.g., signatures) in its signature library, compares the signatures from the clients and the information from the signature library and, for each signature Scp that it receives, notifies the clients with regard to whether or not the signature Scp matches information in its signature library.
As previously described herein, deduplication involves determining whether or not it is necessary to store a new chunk by comparing signatures for chunks that have already been stored to the signature for the new chunk to determine whether a chunk identical to the new chunk has been previously stored. If the signature for the new chunk matches an existing signature, then the new chunk does not need to be stored.
FIG. 2 is a block diagram illustrating elements of a computer system 200 in an embodiment according to the present invention. In an embodiment, the computer system 200 represents a platform for implementing the signature servers 103 (FIG. 1). In the example of FIG. 2, the computer system 200 includes a central processing unit (CPU) 201, a memory 203, and a solid state device (SSD) 205. The memory 203 may be, for example, dynamic random access memory (DRAM). In an embodiment, the SSD 205 is a Serial Advanced Technology Attachment (SATA) SSD and is coupled to the CPU 201 via a SATA bus 207. The computer system 200 may include elements other than those shown.
FIG. 3 is a block diagram showing a connection between SATA SSDs 301, 302, and 303 and the CPU 201 in an embodiment according to the present invention. The SSDs 301-303 are coupled to a host bus adaptor (HBA) 320 via SATA buses 311, 312, and 313, respectively. In an embodiment, the HBA adaptor 320 includes a SATA interface 321, an Advanced Host Controller Interface (AHCI) engine 322 (e.g., a hardware mechanism that allows software to communicate with a SATA device; a bus master to system memory), a Peripheral Component Interconnect Express (PCIe)-to-AHCI bridge 323 (e.g., to translate data between the SATA and PCIe formats), and a PCIe interface 324. The HBA 320 is coupled to the CPU 201 via a PCIe bus 330.
With reference again to FIG. 2, the SSD 205 includes a controller 210 and a number of storage elements, specifically a number of dies or chips 240 a-240 k that are used to store data. The dies 240 a-240 k may be singularly referred to as the die 240 k and collectively referred to as the dies 240. In an embodiment, the dies 240 are NAND dies, and as such the SSD 205 may be referred to as a NAND flash device.
The controller 210 can be implemented as an application-specific integrated circuit (ASIC) or field-programmable gate array (FPGA) that is embedded in the SSD 205. In the embodiment of FIG. 2, the controller 210 includes a flash translation layer (FTL), which may be implemented in firmware or as software. The controller 210 also includes a write path and a read path. The write path starts at the interface 211, which includes, for example, a physical layer (PHY) interface and a serializer/deserializer that converts data between the analog and digital domains (from analog to digital, and from digital to analog). The write path may include a data compression block 212, an encryption block 213, and an error correction code (ECC) encoding block 214. The SSD controller is coupled to the dies 240 via an interface 220 (e.g., an Open NAND Interface, ONFI). Data is moved to the dies 240 using a synchronous and asynchronous trigger mode (toggle).
Data is moved to the read path from the dies 240 via the same toggle mechanism and interface 220. The read path may include an ECC decoding block 216, a decryption block 217, and a decompression block 218.
Significantly, and in contrast to conventional SSD controllers, the controller 210 includes a deduplication processor 230 in the read path. As will be described more fully below, the deduplication processor 230 performs at least two main functions: it extracts information (e.g., signatures) from the dies 240, and it compares those signatures with a signature received from a client 101 m to determine whether the signature from the client matches the extracted information (e.g., whether the signature matches any of the extracted signatures).
FIG. 4 is a flowchart 400 of a deduplication method in an embodiment according to the present invention. All or some of the operations represented by the blocks in the flowchart 400 can be implemented as computer-executable instructions residing on some form of non-transitory computer-readable storage medium, and performed by a signature server or computer system such as the signature server 103 n or the computer system 200 of FIGS. 1 and 2, respectively.
In block 402 of FIG. 4, a signature Scp for a block (e.g., a chunk) of data is received from a client (e.g., the client 101 m of FIG. 1).
In block 404 of FIG. 4, in an embodiment, a read address (Raddr) is calculated based on the signature Scp.
In block 406, the signature Scp is sent to the SSD controller 210 (FIG. 2). In an embodiment, the read address Raddr is also sent to the SSD controller 210. In such an embodiment, the controller uses the read address Raddr to locate an entry in a signature library stored on the dies 240 (FIG. 2). More specifically, the controller 210 can use the read address Raddr as an index to a particular entry in a signature library that is stored on one of the dies 240 (e.g., the die 240 k). The entry may be a signature, or it may be a null value (e.g., the entry may be vacant). Generally speaking, there is content or information Rssd at the entry indexed by the read address Raddr; that content may or may not be a signature, and even the lack of content (e.g., a null or vacant entry) conveys information.
In block 408 of FIG. 4, the SSD controller 210 compares the signature Scp with the information Rssd. In an embodiment, the comparison is performed using the deduplication processor 230 (FIG. 2). Additional information is provided in connection with FIG. 5 below.
If the signature Scp matches the information Rssd, then the flowchart 400 proceeds to block 410; otherwise, the flowchart proceeds to block 414.
In block 410 of FIG. 4, the signature Scp matches the information Rssd. In that case, the information Rssd constitutes a second signature identical to the first signature Scp, which indicates that the chunk of data that is associated with the signature Scp has already been stored on the SSD 205 and it is not necessary to rewrite that chunk of data to the SSD. Accordingly, the controller 210 sends a signal to the CPU 201. In an embodiment, the signal consists of a single binary bit. The bit value has a first value (e.g., binary one, or high) to indicate that the signature Scp matches the information Rssd.
Continuing with reference to FIG. 4, in block 412, metadata associated with the signature Scp is updated and a mapping count is incremented. The metadata is used to recover or help recover the data file that includes the chunk that is associated with the signature Scp. The mapping count identifies how many times that chunk is used (e.g., how many data files contain that chunk).
In block 414, the signature Scp does not match the information Rssd, which indicates that the chunk of data that is associated with the signature Scp is not currently stored on the SSD 205 and so that chunk of data can be written to the SSD. As in block 410, the controller 210 sends a signal to the CPU 201. In an embodiment, the signal again consists of a single binary bit. However, the bit value has a second value (e.g., binary zero, or low) to indicate that the signature Scp does not match the information Rssd.
In block 416, the controller 210 adds the signature Scp into the signature library. In an embodiment, the controller 210 adds the signature Scp into the entry in the signature library identified by the read address Raddr.
In block 418, the chunk of data is written to the SSD 205. In an embodiment, the chunk of data is written to the die 240 k that stores the signature library indexed by the read address Raddr. Also, metadata associated with the signature Scp is updated and a mapping count for the chunk is started (incremented) by the controller 210. The controller 210 can also confirm that the signature library has been updated and that the chunk is saved.
In block 420, if there is another signature for another chunk of data, then the flowchart 400 returns to block 402.
Embodiments according to the invention are not limited to the use of a read address Raddr to find an entry for comparison to the signature Scp in order to determine whether the chunk of data has already been stored on the SSD 205. Other techniques can be used to compare the signature Scp with information in the signature library. One such technique is known as the Cuckoo search algorithm. Other techniques known as particle swarm optimization, differential evolution, and artificial bee colony algorithm may also be used.
As mentioned above, signatures from the clients 101 can be sent in batch mode; thus, multiple signatures (e.g., hundreds of signatures) can be grouped into a single data package and sent to the signature servers 103, in which case the operations of the flowchart 400 can be performed in parallel for each signature. In an embodiment, this can be implemented using a multi-bit bus between the SSD and the CPU, where each bit in the bus denotes whether or not an individual signature has been matched by information in the signature library as described above. This functionality can instead be implemented with a multi-bit register that is polled regularly to get its status.
Also as mentioned above, with reference back to FIG. 2, the controller 210 includes a deduplication processor 230 in the read path. FIG. 5 illustrates a circuit that can be used to implement the deduplication processor 230 in an embodiment according to the present invention. In FIG. 5, “A” is used in reference to the signature Scp, and “B” is used in reference to the information that the signature Scp is being compared against (e.g., the information at the entry indexed by the read address Raddr, or the information in the signature library that is searched using an algorithm such as those mentioned above). The bits in A are identified as A[0], . . . , A[n−1], and the bits in B are identified as B[0], . . . , B[n−1].
During the operations described by block 406 of FIG. 4, the signature Scp (A) can be held in a buffer (not shown) in the write path of the controller 210 for a certain amount of time until the information (B) is read. Then, after the information (B) is read, the signature Scp (A) and the information (B) can be compared bit-by-bit using the deduplication processor 230 of FIG. 5.
In the embodiment of FIG. 5, the deduplication processor 230 includes a number of exclusive-OR (XOR) gates exemplified by the XOR gates 501 and 502. The XOR gate 501 compares the first bit (A[0]) of the signature Scp (A) with the first bit (B[0]) of the information (B), another XOR gate (not shown) compares the second bit of the signature Scp (A) with the second bit of the information (B), and so on, with the XOR gate 502 comparing the last bit (A[n−1]) of the signature Scp (A) with the last bit (B[n−1]) of the information (B). If all of the bits match, then the OR gate 511 will output a binary zero; otherwise, the output of the OR gate will be a binary one. This can be expressed as: Out=(A==B)?1′b0:1′b1.
Thus, the deduplication processor 230 can be implemented using basic circuit elements (e.g., gates). Therefore, the deduplication processor 230 can be readily and inexpensively added to a conventional SSD controller design. Furthermore, it may be possible for the deduplication processor 230 to share some circuit elements with other modules in the SSD controller, such as the ECC decoding block 216, the decryption block 217, and/or the decompression block 218, thereby further helping to control costs.
To summarize, in embodiments according to the present invention, the internal processing circuitry of an SSD is designed so that the signature comparison can be performed by the SSD (specifically, by the SSD controller) instead of on the CPU. Consequently, the CPU's workload is reduced and the amount of data transferred between the SSD and the CPU is significantly reduced.
The CPU sends a signature Scp to the SSD. In an embodiment, the CPU also sends a read address Raddr based on the signature Scp to the SSD. The SSD sends a signal to the CPU that indicates whether or not the signature Scp matches information in the signature library. Multiple signatures, read addresses, and signals can be sent in batch mode and processed in parallel as previously described herein.
Embodiments according to the invention effectively utilize the block write and block read characteristics of an SSD (e.g., NAND flash device). Also, bandwidth is no longer consumed by transferring non-used data from the SSD to the CPU as opposed to conventional approaches. As a result, the number of input/output operations per second (IOPS) on the SSD is dramatically reduced, from about 500,000 to about 9,000. Required performance is sustained but at a reduced cost in terms of CPU, memory, and bandwidth consumption.
Also, by improving the efficiency at which the data is processed, SATA SSDs can be used in the signature servers, which are less expensive than PCIe SSDs. Furthermore, more SATA SSDs than PCIe SSDs can be configured and connected with each CPU core. Thus, hardware costs are also reduced.
FIG. 6 is a flowchart 600 of a data deduplication method executed by a controller (e.g., the controller 210 of FIG. 2) for an SSD in an embodiment according to the present invention.
In block 602 of FIG. 6, a signature Scp for a block (fragment, piece, chunk) of data is received by the controller from a CPU. In an embodiment, an address Raddr associated with the signature is also received by the controller from the CPU.
In block 604, information in a signature library is accessed by the controller. In an embodiment, the address Raddr is used by the controller to index an entry in the signature library.
In block 606, a determination is made by the controller with regard to whether the signature Scp matches information in the signature library. That is, the controller determines whether the signature Scp matches any other signature in the signature library. In an embodiment, the controller determines whether the signature Scp matches the information at the entry addressed by the address Raddr.
In block 608, a signal that indicates the result from block 606 is sent from the controller to the CPU. If the signature Scp matches information in the signature library, then the signal has a first value indicating that the block of data is already stored on the SSD. If the signature Scp does not match information in the signature library, then the signal has a second value that is different from the first value.
If the signature Scp does not match information in the signature library, then the block of data is written to the SSD. If the signature Scp does not match information in the signature library, then the signature is added to the signature library and a counter associated with the block of data is initialized and incremented. If the signature Scp matches information in the signature library, then a counter associated with the block of data is incremented.
FIG. 7 is a flowchart 700 of a data deduplication method executed by a signature server 103 n (FIG. 1) that includes a CPU and an SSD, with an SSD controller, in an embodiment according to the present invention.
In block 702 of FIG. 7, a signature Scp for a block (piece, fragment, chunk) of data is received from a client 101 m. The CPU sends the signature to the SSD controller.
In block 704, in an embodiment, an address Raddr based on the signature is determined (e.g., by the CPU). In such an embodiment, the CPU sends the address Raddr to the SSD controller.
In block 706, information in a signature library is accessed by the SSD controller. In an embodiment, an entry in the signature library is located by the SSD controller using the address Raddr.
In block 708, the SSD controller compares the signature Scp and information from the signature library. In an embodiment, the SSD controller compares the signature and information at the entry in the signature library addressed by the address Raddr.
In block 710, the controller generates a signal that indicates whether or not the signature Scp matches information in the signature library and sends the signal to the CPU. If the signature Scp matches information in the signature library, then the block of data is already stored on the SSD. If the signature Scp does not match information in the signature library, then the signal is sent from the signature server to the client, the block of data is received at the signature server from the client in response to the signal, and the block of data is written to the SSD.
FIG. 8 is a block diagram illustrating an example of an implementation of a deduplication system 800 in an embodiment according to the invention. The deduplication system 800 can be deployed on storage clusters, and can work directly on the backup copies 804, 805, 806, and 807 to be stored by the applications 802. Analyzing the data's redundancy at the global level, the deduplication system 800 removes deduplicated blocks and keeps only unique blocks while also updating the associated metadata. Later, when certain data is accessed or updated, the metadata and unique blocks are modified. By this mechanism, the amount of storage consumed by the backups 804-807 is significantly reduced, by an order of magnitude, for example.
SATA SSDs instead of PCIe SSDs can be used as mentioned above. Each signature server is able to drive more SSDs, for example, 12 SATA SSDs versus four PCIe cards. As a result of the present invention, each SATA SSD performs equally as well as PCIe SSDs in terms of satisfying deduplication needs. Thus, each signature server's capability is improved by three times; in other words, for the same performance, the number of signature servers can be reduced by one-third. Thus, costs are reduced because SATA SSDs cost less than PCIe SSDs and fewer signature servers are needed. Furthermore, computer resources are saved by eliminating the need to retrieve large amounts of unnecessary data.
1. A data deduplication method executed by a controller for a solid state drive (SSD), the method comprising:
receiving, by the controller and from a central processing unit (CPU), a signature for a block of data;
determining, by the controller, whether the signature matches information in a signature library; and
sending a signal from the controller to the CPU that indicates a result of said determining, wherein if the signature matches information in the signature library then the signal has a first value indicating that the block of data is already stored on the SSD and wherein further if the signature does not match information in the signature library then the signal has a second value that is different than the first value.
receiving, by the controller from the CPU, an address associated with the signature;
the controller using the address to index an entry in the signature library; and
determining, by the controller, whether the signature matches the information at the entry in the signature library.
3. The method of claim 1, wherein the signal comprises a single binary bit, wherein the bit is the first value if the signature matches information in the signature library and the second value if the signature does not match information in the signature library.
4. The method of claim 1, wherein if the signature matches information in the signature library then the method further comprises incrementing a counter associated with the block of data.
5. The method of claim 1, wherein if the signature does not match information in the signature library then the method further comprises:
receiving the block of data and writing the block of data to the SSD; and
adding the signature to the signature library and incrementing a counter associated with the block of data.
6. The method of claim 1, wherein the controller comprises a deduplication processor that compares the signature and information in the signature library.
7. The method of claim 6, wherein the deduplication processor comprises a plurality of gates that perform a bit-by-bit comparison of the signature and information in the signature library.
8. The method of claim 1, wherein the SSD is a SATA (Serial Advanced Technology Attachment) SSD.
9. A data deduplication method executed by a server comprising a central processing unit (CPU) and a solid state drive (SSD), the SSD comprising a controller, the method comprising:
receiving, from a client, a signature for a block of data;
determining an address based on the signature;
locating, with the controller and using the address, an entry in a signature library;
comparing, with the controller, the signature and information at the entry in the signature library;
generating, with the controller, a signal that indicates whether or not the signature matches the information, wherein if the signature and the information match then the block of data is already stored on the SSD, and wherein if the signature and the information do not match then the method further comprises:
signaling the client;
receiving the block of data from the client in response to said signaling; and
writing the block of data to the SSD.
10. The method of claim 9, wherein the signal comprises a single binary bit, wherein the bit is a first value if the signature and the information match and a second value if the signature and the information do not match.
11. The method of claim 9, wherein if the signature and the information match then the method further comprises incrementing a counter associated with the block of data.
12. The method of claim 9, wherein if the signature and the information do not match then the method further comprises adding the signature to the signature library and incrementing a counter associated with the block of data.
13. The method of claim 9, wherein the controller comprises a plurality of exclusive-OR (XOR) gates, each gate of the plurality of gates comparing a bit value from the signature and a respective bit value from the information in the signature library.
14. The method of claim 9, wherein the SSD is a SATA (Serial Advanced Technology Attachment) SSD.
15. A solid state drive (SSD), comprising:
a controller coupled to the storage elements;
the controller operable to receive, from a central processing unit (CPU), a signature for a block of data and an address based on the signature, wherein the signature is received by the CPU from a source of the block of data;
the controller operable to locate an entry in a signature library using the address, for comparing the signature and information at the entry in the signature library, and for generating a signal that indicates whether or not the signature matches the information and for sending the signal to the CPU;
the controller further operable to write the block of data to a storage element of the plurality of storage elements when the block of data is received in response to a signal indicating that the signature does not match the information in the signature library.
16. The SSD of claim 15, wherein the signal comprises a single binary bit, wherein the bit is a first value if the signature and the information match and a second value if the signature and the information do not match.
17. The SSD of claim 15, wherein if the signature and the information match then a counter associated with the block of data is incremented.
18. The SSD of claim 15, wherein if the signature and the information do not match then the signature is added to the signature library and a counter associated with the block of data is incremented.
19. The SSD of claim 15, wherein the controller comprises a deduplication processor that compares the signature and the information, wherein the deduplication processor comprises a plurality of exclusive-OR (XOR) gates, each gate of the plurality of gates comparing a bit value from the signature and a respective bit value from the information from the signature library.
20. The SSD of claim 15, wherein the SSD is a SATA (Serial Advanced Technology Attachment) SSD and the storage elements comprise NAND dies.
US14858257 2015-09-18 2015-09-18 Data deduplication using a solid state drive controller Active 2035-11-26 US9665287B2 (en)
US14858257 US9665287B2 (en) 2015-09-18 2015-09-18 Data deduplication using a solid state drive controller
CN 201680054387 CN108027713A (en) 2015-09-18 2016-09-16 Data deduplication using a solid state drive controller
JP2018514841A JP2018527681A (en) 2015-09-18 2016-09-16 Data deduplication to use a solid-state drive controller
PCT/US2016/052222 WO2017049142A1 (en) 2015-09-18 2016-09-16 Data deduplication using a solid state drive controller
EP20160847431 EP3350683A1 (en) 2015-09-18 2016-09-16 Data deduplication using a solid state drive controller
KR20187010549A KR20180052739A (en) 2015-09-18 2016-09-16 Data de-duplication using the solid state drive controller
US15589256 US9864542B2 (en) 2015-09-18 2017-05-08 Data deduplication using a solid state drive controller
US15589256 Continuation US9864542B2 (en) 2015-09-18 2017-05-08 Data deduplication using a solid state drive controller
US20170083245A1 true US20170083245A1 (en) 2017-03-23
US9665287B2 true US9665287B2 (en) 2017-05-30
ID=58282696
US14858257 Active 2035-11-26 US9665287B2 (en) 2015-09-18 2015-09-18 Data deduplication using a solid state drive controller
US15589256 Active US9864542B2 (en) 2015-09-18 2017-05-08 Data deduplication using a solid state drive controller
US (2) US9665287B2 (en)
EP (1) EP3350683A1 (en)
JP (1) JP2018527681A (en)
KR (1) KR20180052739A (en)
CN (1) CN108027713A (en)
WO (1) WO2017049142A1 (en)
US20090307416A1 (en) 2008-06-04 2009-12-10 Intitio Corporation Ssd with a controller accelerator
US20110093439A1 (en) 2009-10-16 2011-04-21 Fanglu Guo De-duplication Storage System with Multiple Indices for Efficient File Storage
US8321384B2 (en) 2010-03-12 2012-11-27 Fujitsu Limited Storage device, and program and method for controlling storage device
US8407186B1 (en) 2009-03-31 2013-03-26 Symantec Corporation Systems and methods for data-selection-specific data deduplication
US8442954B2 (en) 2009-07-21 2013-05-14 Stephen Philip SPACKMAN Creating and managing links to deduplication information
US8478933B2 (en) 2009-11-24 2013-07-02 International Business Machines Corporation Systems and methods for performing deduplicated data processing on tape
US8572312B2 (en) 2011-12-07 2013-10-29 Jeffrey Tofano Data de-duplication and solid state memory device
US20130290277A1 (en) 2012-04-30 2013-10-31 International Business Machines Corporation Deduplicating storage with enhanced frequent-block detection
US20140304464A1 (en) 2013-04-03 2014-10-09 Lsi Corporation Methods and systems for performing deduplication in a data storage system
US8898119B2 (en) 2010-12-15 2014-11-25 Netapp, Inc. Fingerprints datastore and stale fingerprint removal in de-duplication environments
US8930648B1 (en) 2012-05-23 2015-01-06 Netapp, Inc. Distributed deduplication using global chunk data structure and epochs
CN104407982A (en) 2014-11-19 2015-03-11 湖南国科微电子有限公司 SSD (solid state drive) disk garbage recycling method
US9047301B2 (en) 2010-04-19 2015-06-02 Greenbytes, Inc. Method for optimizing the memory usage and performance of data deduplication storage systems
US9092151B1 (en) 2010-09-17 2015-07-28 Permabit Technology Corporation Managing deduplication of stored data
"Smart In-Network Deduplication for storage-aware SDN" Hua, et al. Copyright SIGCOMM'13 Aug. 12-16, 2013 Hong Kong, China pp. 509-510.
WO2017049142A1 (en) 2017-03-23 application
US20170242616A1 (en) 2017-08-24 application
US9864542B2 (en) 2018-01-09 grant
EP3350683A1 (en) 2018-07-25 application
JP2018527681A (en) 2018-09-20 application
US20170083245A1 (en) 2017-03-23 application
CN108027713A (en) 2018-05-11 application
KR20180052739A (en) 2018-05-18 application
US8156241B1 (en) 2012-04-10 System and method for compressing data transferred over a network for storage purposes
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:LI, SHU;LI, YONG;NIU, GONGBIAO;SIGNING DATES FROM 20150813 TO 20150814;REEL/FRAME:036600/0474