System and method for cache management

A method, computer program product, and computing system for processing, on a host, a read request for a portion of a data file stored on a backend storage system. The portion of the data file is obtained from the backend storage system. The portion of the data file is divided into a plurality of file chunks based, at least in part, upon a file type. Each of the plurality of file chunks is compared to other file chunks stored within a frontend cache system associated with the host to identify unique file chunks within the plurality of file chunks. The unique file chunks are stored within the frontend cache system.

TECHNICAL FIELD

This disclosure relates to cache systems and, more particularly, to systems and methods for cache deduplication.

BACKGROUND

Storing and safeguarding electronic content is of paramount importance in modern business. Accordingly, various systems may be employed to protect such electronic content.

The use of solid-state storage devices is increasing in popularity. A solid state storage device is a content storage device that uses solid-state memory to store persistent content. A solid-state storage device may emulate (and therefore replace) a conventional hard disk drive. Additionally/alternatively, a solid state storage device may be used within a cache memory system. With no moving parts, a solid-state storage device largely eliminates (or greatly reduces) seek time, latency and other electromechanical delays and failures associated with a conventional hard disk drive.

SUMMARY OF DISCLOSURE

In a first implementation, a computer-implemented method includes processing, on a host, a read request for a portion of a data file stored on a backend storage system. The portion of the data file is obtained from the backend storage system. The portion of the data file is divided into a plurality of file chunks based, at least in part, upon a file type. Each of the plurality of file chunks is compared to other file chunks stored within a frontend cache system associated with the host to identify unique file chunks within the plurality of file chunks. The unique file chunks are stored within the frontend cache system.

One or more of the following features may be included. Comparing each of the plurality of file chunks to other file chunks stored within the frontend cache system may include identifying non-unique file chunks within the plurality of file chunks. The non-unique file chunks may not be stored within the frontend cache system. The portion of the data file may be a complete data file. The plurality of file chunks may have a common length and may be aligned. The plurality of file chunks may have differing lengths. The backend storage system may include a data array.

Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a sticky bit algorithm. Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a file structure.

In another implementation, a computer program product resides on a computer readable medium that has a plurality of instructions stored on it. When executed by a processor, the instructions cause the processor to perform operations including processing, on a host, a read request for a portion of a data file stored on a backend storage system. The portion of the data file is obtained from the backend storage system. The portion of the data file is divided into a plurality of file chunks based, at least in part, upon a file type. Each of the plurality of file chunks is compared to other file chunks stored within a frontend cache system associated with the host to identify unique file chunks within the plurality of file chunks. The unique file chunks are stored within the frontend cache system.

One or more of the following features may be included. Comparing each of the plurality of file chunks to other file chunks stored within the frontend cache system may include identifying non-unique file chunks within the plurality of file chunks. The non-unique file chunks may not be stored within the frontend cache system. The portion of the data file may be a complete data file. The plurality of file chunks may have a common length and may be aligned. The plurality of file chunks may have differing lengths. The backend storage system may include a data array.

Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a sticky bit algorithm. Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a file structure.

In another implementation, a computing system includes at least one processor and at least one memory architecture coupled with the at least one processor, wherein the computing system is configured to perform operations including processing, on a host, a read request for a portion of a data file stored on a backend storage system. The portion of the data file is obtained from the backend storage system. The portion of the data file is divided into a plurality of file chunks based, at least in part, upon a file type. Each of the plurality of file chunks is compared to other file chunks stored within a frontend cache system associated with the host to identify unique file chunks within the plurality of file chunks. The unique file chunks are stored within the frontend cache system.

One or more of the following features may be included. Comparing each of the plurality of file chunks to other file chunks stored within the frontend cache system may include identifying non-unique file chunks within the plurality of file chunks. The non-unique file chunks may not be stored within the frontend cache system. The portion of the data file may be a complete data file. The plurality of file chunks may have a common length and may be aligned. The plurality of file chunks may have differing lengths. The backend storage system may include a data array.

Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a sticky bit algorithm. Dividing the portion of the data file into a plurality of file chunks may include dividing the portion of the data file into a plurality of file chunks based, at least in part, upon a file structure.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring toFIG. 1, there is shown cache management process10that may reside on and may be executed by storage system12, which may be connected to network14(e.g., the Internet or a local area network). Examples of storage system12may include, but are not limited to: a Network Attached Storage (NAS) system, a Storage Area Network (SAN), a personal computer with a memory system, a server computer with a memory system, and a cloud-based device with a memory system.

As is known in the art, a SAN may include one or more of a personal computer, a server computer, a series of server computers, a mini computer, a mainframe computer, a RAID device and a NAS system. The various components of storage system12may execute one or more operating systems, examples of which may include but are not limited to: Microsoft Windows XP Server™; Novell Netware™; Redhat Linux™, Unix, or a custom operating system, for example.

The instruction sets and subroutines of cache management process10, which may be stored on storage device16included within storage system12, may be executed by one or more processors (not shown) and one or more memory architectures (not shown) included within storage system12. Storage device16may include but is not limited to: a hard disk drive; a tape drive; an optical drive; a RAID device; a random access memory (RAM); a read-only memory (ROM); and all forms of flash memory storage devices.

Various IO requests (e.g. IO request20) may be sent from client applications22,24,26,28to storage system12. Examples of IO request20may include but are not limited to data write requests (i.e. a request that content be written to storage system12) and data read requests (i.e. a request that content be read from storage system12).

The instruction sets and subroutines of client applications22,24,26,28, which may be stored on storage devices30,32,34,36(respectively) coupled to client electronic devices38,40,42,44(respectively), may be executed by one or more processors (not shown) and one or more memory architectures (not shown) incorporated into client electronic devices38,40,42,44(respectively). Storage devices30,32,34,36may include but are not limited to: hard disk drives; tape drives; optical drives; RAID devices; random access memories (RAM); read-only memories (ROM), and all forms of flash memory storage devices. Examples of client electronic devices38,40,42,44may include, but are not limited to, personal computer38, laptop computer40, personal digital assistant42, notebook computer44, a server (not shown), a data-enabled, cellular telephone (not shown), and a dedicated network device (not shown).

Users46,48,50,52may access storage system12directly through network14or through secondary network18. Further, storage system12may be connected to network14through secondary network18, as illustrated with link line54.

Client electronic devices38,40,42,44may each execute an operating system, examples of which may include but are not limited to Microsoft Windows™, Microsoft Windows CE™, Redhat Linux™, or a custom operating system.

For illustrative purposes, storage system12will be described as being a network-based storage system that includes a plurality of electro-mechanical backend storage devices. However, this is for illustrative purposes only and is not intended to be a limitation of this disclosure, as other configurations are possible and are considered to be within the scope of this disclosure. For example and as discussed above, storage system12may be a personal computer that includes a single electro-mechanical storage device.

Referring also toFIG. 2, storage system12may include a server computer/controller (e.g. server computer/controller100) and a plurality of storage targets T1-n(e.g. storage targets102,104,106,108). Storage targets102,104,106,108may be configured to provide various levels of performance and/or high availability. For example, one or more of storage targets102,104,106,108may be configured as a RAID 0 array, in which data is striped across storage targets. By striping data across a plurality of storage targets, improved performance may be realized. However, RAID 0 arrays do not provide a level of high availability. Accordingly, one or more of storage targets102,104,106,108may be configured as a RAID 1 array, in which data is mirrored between storage targets. By minoring data between storage targets, a level of high availability is achieved as multiple copies of the data are stored within storage system12.

While storage targets102,104,106,108are discussed above as being configured in a RAID 0 or RAID 1 array, this is for illustrative purposes only and is not intended to be a limitation of this disclosure, as other configurations are possible. For example, storage targets102,104,106,108may be configured as a RAID 3, RAID 4, RAID 5 or RAID 6 array.

While in this particular example, storage system12is shown to include four storage targets (e.g. storage targets102,104,106,108), this is for illustrative purposes only and is not intended to be a limitation of this disclosure. Specifically, the actual number of storage targets may be increased or decreased depending upon e.g. the level of redundancy/performance/capacity required.

Storage system12may also include one or more coded targets110. As is known in the art, a coded target may be used to store coded data that may allow for the regeneration of data lost/corrupted on one or more of storage targets102,104,106,108. An example of such a coded target may include but is not limited to a hard disk drive that is used to store parity data within a RAID array.

While in this particular example, storage system12is shown to include one coded target (e.g., coded target110), this is for illustrative purposes only and is not intended to be a limitation of this disclosure. Specifically, the actual number of coded targets may be increased or decreased depending upon e.g. the level of redundancy/performance/capacity required.

Examples of storage targets102,104,106,108and coded target110may include one or more electro-mechanical hard disk drives, wherein a combination of storage targets102,104,106,108and coded target110may form non-volatile, electro-mechanical memory system112.

The manner in which storage system12is implemented may vary depending upon e.g. the level of redundancy/performance/capacity required. For example, storage system12may be a RAID device in which server computer/controller100is a RAID controller card and storage targets102,104,106,108and/or coded target110are individual “hot-swappable” hard disk drives. An example of such a RAID device may include but is not limited to an NAS device. Alternatively, storage system12may be configured as a SAN, in which server computer/controller100may be e.g., a server computer and each of storage targets102,104,106,108and/or coded target110may be a RAID device and/or computer-based hard disk drive. Further still, one or more of storage targets102,104,106,108and/or coded target110may be a SAN.

In the event that storage system12is configured as a SAN, the various components of storage system12(e.g. server computer/controller100, storage targets102,104,106,108, and coded target110) may be coupled using network infrastructure114, examples of which may include but are not limited to an Ethernet (e.g., Layer2or Layer3) network, a fiber channel network, an InfiniBand network, or any other circuit switched/packet switched network.

Storage system12may execute all or a portion of cache management process10. The instruction sets and subroutines of cache management process10, which may be stored on a storage device (e.g., storage device16) coupled to server computer/controller100, may be executed by one or more processors (not shown) and one or more memory architectures (not shown) included within server computer/controller100. Storage device16may include but is not limited to: a hard disk drive; a tape drive; an optical drive; a RAID device; a random access memory (RAM); a read-only memory (ROM); and all forms of flash memory storage devices.

As discussed above, various IO requests (e.g. IO request20) may be generated. For example, these IO requests may be sent from client applications22,24,26,28to storage system12. Additionally/alternatively and when server computer/controller100is configured as an application server, these IO requests may be internally generated within server computer/controller100. Examples of IO request20may include but are not limited to data write request116(i.e. a request that content118be written to storage system12) and data read request120(i.e. a request that content118be read from storage system12).

Server computer/controller100may include input-output logic122(e.g., a network interface card or a Host Bus Adaptor (HBA)), processing logic124, and first cache system126. Examples of first cache system126may include but are not limited to a volatile, solid-state, cache memory system (e.g., a dynamic RAM cache memory system) and/or a non-volatile, solid-state, cache memory system (e.g., a flash-based, cache memory system).

During operation of server computer/controller100, content118to be written to storage system12may be received by input-output logic122(e.g. from network14and/or network18) and processed by processing logic124. Additionally/alternatively and when server computer/controller100is configured as an application server, content118to be written to storage system12may be internally generated by server computer/controller100. As will be discussed below in greater detail, processing logic124may initially store content118within first cache system126.

Depending on the manner in which first cache system126is configured, processing logic124may immediately write content118to second cache system128/non-volatile, electro-mechanical memory system112(if first cache system126is configured as a write-through cache) or may subsequently write content118to second cache system128/non-volatile, electro-mechanical memory system112(if first cache system126is configured as a write-back cache). Additionally and in certain configurations, processing logic124may calculate and store coded data on coded target110(included within non-volatile, electromechanical memory system112) that may allow for the regeneration of data lost/corrupted on one or more of storage targets102,104,106,108. For example, if processing logic124was included within a RAID controller card or an NAS/SAN controller, processing logic124may calculate and store coded data on coded target110. However, if processing logic124was included within e.g., an applications server, data array130may calculate and store coded data on coded target110.

Examples of second cache system128may include but are not limited to a volatile, solid-state, cache memory system (e.g., a dynamic RAM cache memory system) and/or a non-volatile, solid-state, cache memory system (e.g., a flash-based, cache memory system).

The combination of second cache system128and non-volatile, electromechanical memory system112may form data array130, wherein first cache system126may be sized so that the number of times that data array130is accessed may be reduced. Accordingly, by sizing first cache system126so that first cache system126retains a quantity of data sufficient to satisfy a significant quantity of IO requests (e.g., IO request20), the overall performance of storage system12may be enhanced.

Further, second cache system128within data array130may be sized so that the number of times that non-volatile, electromechanical memory system112is accessed may be reduced. Accordingly, by sizing second cache system128so that second cache system128retains a quantity of data sufficient to satisfy a significant quantity of IO requests (e.g., IO request20), the overall performance of storage system12may be enhanced.

As discussed above, the instruction sets and subroutines of cache management process10, which may be stored on storage device16included within storage system12, may be executed by one or more processors (not shown) and one or more memory architectures (not shown) included within storage system12. Accordingly, in addition to being executed on server computer/controller100, some or all of the instruction sets and subroutines of cache management process10may be executed by one or more processors (not shown) and one or more memory architectures (not shown) included within data array130.

The Cache Management Process:

As discussed above, various IO requests may be processed by server computer/controller100, examples of which may include but are not limited to data write request116(i.e. a request that content118be written to storage system12) and data read request120(i.e. a request that content118be read from storage system12). Assume for illustrative proposes that content118is a considerably large file that resides within data array130. Examples of such a large file may include but are not limited to a shared database file. Accordingly, when a read request is received concerning content118(which, as discussed, is resident on data array130), only a small portion of content118may be retrieved and cached in response to such a read request (as it would be impractical/undesirable/unneeded to retrieve and cache content118in its entirety.

Assume for illustrative purposes that server computer/controller100receives such a read request120concerning only a portion of content118(e.g., portion132of content118) currently stored on a backend storage system (e.g., data array130). Cache management process10may process200(on the host e.g., server computer/controller100) read request120.

While content118is described above as a larger file and, therefore, read request120concerns only a portion of content118, this is for illustrative purposes only and is not intended to be a limitation of this disclosure, as other configurations are possible and are considered to be within the scope of this disclosure and the claims. For example, in the event that content118is a smaller file, the portion requested in read request120may be the entire file (e.g., all of content118), as opposed to a smaller amount).

Upon processing read request120, cache management process10may obtain202portion132of the data file (e.g., content118) from the backend storage system (e.g., data array130) and may divide204portion132of content118into plurality of file chunks134. For example, if portion132was a 128 kb portion of content118, portion132may be divided204into thirty-two 4 kb chunks.

When dividing204portion132of content118into plurality of chunks134, logic may be applied to increase the probability of commonality amongst chunks. Therefore, portion132may be divided204in accordance with the format/type of content118. For example, text files may be divided204in accordance with a sticky bit algorithm.

A sticky bit algorithm is an algorithm that calculates a hash value for short sequences of data. For instance, if there is a data chunk of 100 KB, the sticky bit algorithm may calculate the hash value for every ten consecutive bytes of the data chunk and may identify a cut point (if the hash value modulo some constant is zero). For instance, if the hash value modulo 4,096 is 0, this assures that the file will be cut to portions that are roughly 4,096 bytes in length. If there is a large chunk with no cut point (e.g., a 40 KB chunk with no cut point), a cut point may be added artificially. This may happen e.g., if all the data is constant. The sticky bit algorithm may assure that if only a few bytes of data are added in the middle of a file, most chunks of the file will remain the same.

Additionally, video files may be divided204into video frames. Further, document files may be divided204based upon components (e.g., still images and text-based components). Accordingly, plurality of file chunks134may all have a common length or may have differing lengths (depending upon the manner in which they are divided).

Cache management process10may compare206each of plurality of file chunks132to other file chunks stored within a frontend cache system (e.g., first cache system126) associated with the host (e.g., server computer/controller100) to identify the unique file chunks within plurality of file chunks132. A unique file chunk may be classified as a file chunk that is included within plurality of file chunks132that is not identical to any other file chunk already stored within first cache system126. Once comparison206is performed and one or more unique file chunks are identified, cache management process10may store208the unique file chunks within first cache system126.

When comparing206each of plurality of file chunks132to other file chunks already stored within first cache system126, cache management process10may identify210non-unique file chunks within plurality of file chunks132. A non-unique file chunk may be classified as a file chunk that is included within plurality of file chunks132that is identical to another file chunk already stored within first cache system126. Once the non-unique file chunks are identified210, cache management process10may not store212the non-unique file chunks within first cache system126(and/or delete the non-unique file chunks from their temporary storage location).

Accordingly, through the use of cache management process10, only a single copy of a file chunk will be stored within first cache system126. Accordingly, assume for illustrative purposes that four different files (or file portions) are currently stored within first cache system126due to the processing of four different read requests. Further, assume that read request120is received by e.g., server computer/controller100requesting portion132of content118. Accordingly, cache management process10may process200read request120; may obtain202portion132of content118from data array130; and may divide204portion132of content118into plurality of file chunks134, where the division algorithm is dependent on the file type.

As discussed above, cache management process10may compare206each of plurality of file chunks132to other file chunks already stored within first cache system126(namely the file chunks of the above-described four different files/file portions) to identify the unique file chunks included within plurality of file chunks132. Assume for illustrative purposes that cache management process10divides204portion132into ten file chunks, namely file chunks136,138,140,142,144,146,148,150,152,154. Further assume for illustrative purposes that when comparing206each of plurality of file chunks132to other file chunks already stored within first cache system126, cache management process10determines that only six file chunks (namely file chunks136,138,140,146,150,152) are unique (and may be stored208within first cache system126) and that four file chunks (namely file chunks142,144,148,154) are not unique (and may not be stored212within first cache system126). For the file chunks that are not unique (namely file chunks142,144,148,154) and, therefore, are not stored212within first cache system126, the cache directory (not shown) associated with first cache system126may simply map the cache directory entry that is associated with each of the four non-stored file chunks to the file chunk included within first cache system126that is identical to each of the four non-stored file chunks.