Managing enhanced write caching

1. Field of the Invention

The present invention relates to managing enhanced write caching.

2. Description of Prior Art

Data storage systems are used within computer networks and systems to store large amounts of data, e.g., data that is used by multiple servers and client computers (“hosts”). Generally, one or more servers are connected to the storage system, e.g., to supply data to and from a computer network. The data may be transferred through the network to various users or clients. The data storage system generally comprises a controller (“storage processor” or “SP”) that interacts with one or more storage devices such as one or more magnetic or solid state disk drives or other forms of data storage. To facilitate uninterrupted operation of the server as it reads and writes data from and to the storage system, as well as executes application programs for use by users, the storage system comprises a write cache that allows data from the server to be temporarily stored in the write cache prior to being written to a storage device. As such, the server can send data to the storage system and quickly be provided an acknowledgement that the storage system has stored the data. The acknowledgement is sent even though the storage system has only stored the data in the write cache and is waiting for an appropriate, convenient time to store the data in a storage device. As is well known in the art, storing data to a write cache is typically much faster than storing data directly to a disk drive. Consequently, the write cache buffers a large amount of data in anticipation of subsequent storing of that data in a storage device.

One conventional data storage system includes two storage processors and an array of disk drives. Each storage processor includes, among other things, a local write cache. The local write caches mirror each other. Mirroring the cache protects data in the event of a storage processor failure.

During operation, the storage processors perform read and write operations on behalf of one or more external hosts. Since the contents of the local write caches are mirrored, the storage processors initially attend to write operations in a write-back manner. That is, the write policy employed by the storage processors involves acknowledging host write operations once the write data is stored in both write caches. By the time the external hosts receive such acknowledgement, the storage processors may not have yet evicted the write data from the write caches to the array of disk drives.

A method and system for use in managing enhanced write caching is disclosed. In at least one embodiment, the method and system comprises performing write-back caching operations using a write cache of a storage processor of a data storage system. A first cache page corresponding to a disk location is provided in the write cache. A host is allowed to write to a second cache page in the write cache corresponding to the same disk location. Both the first and second cache pages are maintained after acknowledging the write to the host.

The foregoing and other objects, features and advantages of the invention will be apparent from the following description of particular embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

FIG. 1 is a block diagram of a data storage system which is configured for enhanced write caching.

FIG. 2 is a block diagram of a storage processor of the data storage system of FIG. 1 .

FIG. 3 is a block diagram of aspects of the storage processors of FIG. 1 .

Described below is a technique for use in managing enhanced write caching. In at least one implementation, the technique may be used to help provide a method to defer page merges, e.g., until they are no longer necessary. In general, for data integrity reasons a write I/O (a “write”) from a host may be written to a respective newly allocated page in the write cache via direct memory access (DMA), and conventionally data movement is required for writes smaller than the page size as writes are committed as described below. By contrast, in at least some implementations in accordance with the technique described herein, such data movement is delayed until a future point in time or until it is no longer necessary, which can save substantial CPU time in at least some cases.

In particular, conventionally when data is being transferred into part of a page in a cache, and the prior version of that page is dirty in the cache as explained below, the new data must not overwrite the old data. When the transfer size is smaller than the cache page, it is necessary to copy the data that changed. By contrast, in accordance with the technique, a new approach for tracking that data avoids a cost of copying the data between pages. The approach avoids the allocation of the new page in simple cases, and in the other cases, delays the copying until some future point in time, possibly eliminating the need for some or all of the copying. In the approach, if in the intervening period another transfer is requested, it is transferred without requiring a page allocation, and in some cases causes the original page to be freed, i.e., de-allocated.

Conventionally, a storage system allocated a new cache page when a write arrived, transferred the data into that new cache page, and then merged the pages into one page by copying data from the old page to the new page or vice versa depending which involved less copying of data. This conventional approach incurs the expense of processor time for copying the data from one page to the other.

By contrast, at least some implementations in accordance with the technique as described herein, copying data between cache pages is reduced or eliminated, avoiding cost in processor time and memory bandwidth.

FIG. 1 is a block diagram of a data storage system 20 which is configured for write caching enhancement for improved performance with a set of external host computers 22 ( 1 ), 22 ( 2 ), . . . (collectively, external hosts 22 ). The external hosts 22 connect to the data storage system 20 via a respective communications medium 24 ( 1 ), 24 ( 2 ), . . . (collectively, communications media 24 ).

The data storage system 20 includes multiple storage processors 26 (A), 26 (B) (collectively, storage processors 26 ), a cache mirror bus 28 and a set of disk drives 30 ( 1 ), . . . 30 (N) (collectively, disk drives 30 ). The storage processors 26 are configured to perform data storage operations (e.g., read operations, write operations, etc.) on behalf of the external hosts 22 . The cache mirror bus 28 is configured to convey data between caches of the storage processors 26 thus enabling cache mirroring between the storage processors 26 . The set of disk drives 30 enables the data storage system 20 to store and retrieve data on behalf of the external hosts 22 in a fault tolerant, non-volatile manner (e.g., using a RAID scheme).

Each storage processor 26 is configured to perform write-back caching in response to write operations 32 from the external hosts 22 while both storage processors 26 are in operation. That is, each storage processor 26 acknowledges completion of a write operation 32 once the write data reaches its local write cache and, if possible, once the write data is mirrored in the local write cache of the other storage processor 26 . Additionally, each storage processor 26 is configured to continue to perform enhanced write-back caching as described herein. Such operation enables the data storage system 20 to provide improved response times.

FIG. 2 is a block diagram of each storage processor 26 of the data storage system 20 . Each storage processor 26 includes a communications interface 40 , a controller 42 and a memory subsystem 44 . The communications interface 40 includes a host interface 46 , a cache mirroring interface 48 , and a disk interface 50 . The memory subsystem 44 includes a control circuit 52 , a local write cache 54 and additional memory 58 . The additional memory 58 includes operating system storage, firmware for storing BIOS and POST code, optional flash memory, etc.

The communications interface 40 is configured to provide connectivity from the storage processor 26 to various other components. In particular, the host interface 46 is configured to connect the storage processor 26 to one or more external hosts 22 through the connection media 24 (also see FIG. 1 ). The cache mirroring interface 48 is configured to connect the storage processor 26 (e.g., the storage processor 26 (A)) to another storage processor 26 (e.g., the storage processor 26 (B)) to enable cache mirroring through the cache mirroring bus 28 . The disk interface 50 is configured to connect the storage processor 26 to the set of disk drives 30 .

The controller 42 is configured to carryout data storage operations on behalf of one or more of the external hosts 22 through the communications interface 40 (e.g., see the write operations 32 in FIG. 1 ). In some arrangements, the controller 42 is implemented as a set of processors running an operating system which is capable of being stored in a designated area on one or more of the disk drives 30 . In other arrangements, the controller 42 is implemented as logic circuitry (e.g., Application Specific Integrated Circuitry, Field Programmable Gate Arrays, etc.), microprocessors or processor chip sets, analog circuitry, various combinations thereof, and so on.

The memory subsystem 44 is configured to provide memory services to the controller 42 . In particular, the control circuitry 54 of the memory subsystem 44 is configured to provide enhanced merging logic for use with the write cache 56 , i.e., to provide a write caching enhancement as described herein. The control circuit 54 is further capable of performing other tasks using the additional memory 58 (e.g., operating a read cache, operating as an instruction cache, optionally vaulting contents of the write cache 56 into non-volatile flash memory or disk drive memory in response to a failure of the controller 42 , etc.).

In general, the write caching enhancement helps avoid or defer page merging in at least many typical cases, so that the system can use arbitrary page sizes without excessive CPU usage. In some cases, e.g., a minority of cases, use of the write caching enhancement can double the memory used, but by deferring page merges, their frequency can be reduced and therefore performance can be improved.

Each cache page has, tracked in a page reference structure:

Sector states that identify whether each sector is valid or dirty

An “owning SP” bit

A nonOwnerHasDirtyData bit (if TRUE, non-owner dirty bits are correct)

A nonOwnerHasValidData bit (if TRUE, non-owner memory contains identical data as owner memory for valid/dirty sectors)

A NonOwnerKnowsItHasValidData bit (if TRUE, non-owner valid bits are correct; if FALSE: valid bits are all off on peer)

Cache pages also have a way to find a “second” page (key to the write caching enhancement) for the same LBA:

The primary page may have a link to the second page.

Both pages may be on the same hash list.

For correctness on any single fault (e.g., owning SP crash):

Write data can be transferred directly to any sub-page that is not dirty, provided the SP receiving the data will not interpret the data as valid if the transfer fails.

If the other SP will interpret the data is valid, it must be marked invalid prior to the transfer.

The valid or dirty bits cannot be set for the same sector in both pages at any single point in time (may apply to more than single fault correctness).

If an SP crashes, the other SP will discard any valid, non-dirty, data. Thus writes on top of valid, non-dirty sectors a permissible.

The cache page can merge the second page at any time, using an existing process (the remaining page is the one which will require the least copying of data). Bit nonOwnerHasValidData/NonOwnerKnowsItHasValidData can be used to optimize cache performance in some cases. NonOwnerKnowsItHasValidData indicates that the system cannot DMA to a valid page on the peer prior to informing the peer that it is invalid.

In a use case 1 with a sequential write of sub-pages, the transfer can occur directly into invalid sectors, and only one cache page is needed per LBA.

In a use case 2 a , with a full page read and then write of sub-pages (e.g., read modify write when predicting some locality):

On read, an entire page is loaded into the cache on the owning SP, nonOwnerHasDirtyData=FALSE, nonOwnerHasValidData=FALSE, NonOwnerKnowsItHasValidData=FALSE, and valid bits are set for the entire page. On write, data is transferred directly into non-dirty sectors on both SPs, nonOwnerHasDirtyData=TRUE, and dirty bits are transferred to peer SP. Upon completion, some sub pages are dirty, and some are valid.

In a use case 2 b : a sub-page is read, and then an overwrite write is executed of the same sub-page (e.g., random read modify write). Read and write have characteristics similar to use case 2 a , and upon completion, there are no sub-pages that are valid and not dirty.

In a use case 3 a , dirty pages are to be overwritten (second page pointer==NULL, nonOwnerHasDirtyData=TRUE). A new “second page” is allocated, data is transferred to that page on both SPs, dirty bits are set in the second page, corresponding valid/dirty bits are cleared in the primary page, dirty bits for both pages are transferred to the peer atomically. The primary page is freed if it has no valid/dirty data.

In a use case 3 b , dirty pages are overwritten (second page pointer !=NULL, nonOwnerHasDirtyData=TRUE). Data is transferred to the invalid sub-pages across the two pages. The dirty bits are set for the corresponding sub-pages, and the other dirty bits are cleared. Dirty bits are transferred for both pages. The primary page is freed if it has no current valid/dirty data.

Analysis of the write caching enhancement reveals the following characteristics in at least some implementations.

If the host writes to a sub-page exactly once, only one buffer/page is needed; examples are random writes, random read/modify write.

If the host does not read the page, and writes to all sub-pages the same number of times, only one buffer/page is needed or there is a transient use of two buffers/pages, and no data copies are needed; an example is typical application behavior with a host read cache.

If the host writes different sub-pages of a page a different number of times, two partially dirty buffers are needed per cache page until a page merge, i.e., two pages are needed. This occurs on a random cache hit test.

If the host reads first, and then writes the full page, the read is irrelevant, and the characteristics above remain.

If the host reads first, and then writes less data than the data storage system read, and writes each sub-page an even number of times, only one buffer is needed. This describes half of the cases not described above.

If the host reads first, and then writes less data than the data storage system read, and writes a sub-page an odd number of times but more than once, two buffers are needed. This describes the remaining half of the cases not described above.

If merging is deferred, the following describes when merging would occur, in at least some implementations:

A NULL merge which occurs when there are two pages and one page becomes completely invalid, and can be freed at no data-copying cost.

When there is a need for free memory for pages.

In at least one implementation, having the second page on a least recently used (LRU) list of second pages allows page merges to free pages. For example, multiple classes of LRUs may be provided, with a timestamp in each entry. The decision as to which class to replace from may be a function of the class and the time since last reference of the least recently used item in that class. In a specific example, a page merge of a 60 second old page may be preferred over writing to memory a dirty page that has not been referenced for 119 seconds.

FIG. 3 illustrates an example of components and data structures that may be used in at least one implementation using the technique. Cache pages 98 A, 98 B, 99 A, 99 B may be used as described below to provide enhanced caching functionality on behalf of data portion 1010 of disk(s) 30 . Each cache page includes respective sub-pages, e.g., page 98 A has sub-pages U 01 A, U 02 A, U 03 A, U 04 A, U 05 A, U 06 A. In FIG. 3 , each sub-page is identified by notation Uxyz, where x=0 indicates location within a primary page such as page 98 A or 98 B, x=1 indicates location within a secondary page such as page 99 A or 99 B, y=0 indicates sub-page number within a respective page, z=A indicates location in cache 56 A of SPA, and z=B indicates location in cache 56 B of SPB which is the peer SP. The status of each sub-page is indicated by respective status indicators, e.g., sub-pages U 01 A, U 02 A, U 03 A, U 04 A, U 05 A, U 06 A have respective status indicators S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A. Each status indicator is identified by notation Sxyz, where x, y, and z have the meaning described above.

Sub-pages of page 99 A correspond to respective sub-pages of page 98 A. For example, sub-page U 11 A corresponds to sub-page U 01 A, and sub-page U 12 A corresponds to sub-page U 02 A.

When host 22 writes data to cache 56 A, system 20 does not acknowledge such write as complete to host 22 until such data is committed, i.e., is also stored sufficiently in cache 56 B via interface 48 .

Each sub-page may correspond to a sector as represented in the cache. Status is encoded by the status indicators into one of four states: Invalid (I), Valid (V), Dirty (D), and Prepared (P):

Invalid—The sector is invalid.

Valid—The sector is valid on this SP.

Prepared—For writes, it indicates that the sector contains data needed for commit.

Dirty—The sector is dirty on both SPs.

In an example, primary page 98 A is allocated with all sub-pages having status I, and the host writes data to sub-pages U 03 A, U 05 A which are marked with status P in S 03 A, S 05 A, respectively. (It should be noted that sub-pages may be accessed consecutively starting at U 01 A instead.) The page 98 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={I, I, P, I, P, I}

After sub-pages U 03 A, U 05 A are mirrored to sub-pages U 03 B, U 05 B respectively, status of sub-pages U 03 A, U 05 A, U 03 B, U 05 B is updated to D in S 03 A, S 05 A, S 03 B, S 05 B, respectively, and the write is acknowledged to the host. The page 98 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={I, I, D, I, D, I}

Next, the host indicates it needs write to sectors corresponding to sub-pages U 02 A, U 05 A. Secondary page 98 B is allocated with all sub-pages having status I, and the host writes data to sub-pages U 12 A, U 15 A which are marked with status P in S 12 A, S 15 A, respectively. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={I, I, D, I, D, I}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, P, I, I, P, I}

After sub-pages U 12 A, U 15 A are mirrored to sub-pages U 12 B, U 15 B respectively, status of sub-pages U 12 A, U 15 A, U 12 B, U 15 B is updated to D in S 12 A, S 15 A, S 12 B, S 15 B, respectively, status of sub-pages U 05 A, U 05 B is updated to I in S 05 A, S 05 B, respectively, and the write is acknowledged to the host. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={I, I, D, I, I, I}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, D, I, I, D, I}

The reason that status of sub-pages U 05 A, U 05 B is updated to I is that sub-pages U 05 A, U 05 B are now out of date, having been superseded by sub-pages U 15 A, U 15 B respectively.

(In the example, no flushing takes place, but if at this point a portion of cache 56 A corresponding to disk portion 1010 were flushed to disk, this would be accomplished by reading from both pages 98 A, 99 A, particular the portions of such pages currently having status D, which are sub-pages U 12 A, U 03 A, U 15 A. After such flushing, sub-pages U 12 A, U 03 A, U 15 A would be updated to status V.)

Next the host indicates it needs to write to sectors corresponding to sub-pages U 01 A, U 02 A, U 03 A, U 04 A, U 05 A, U 06 A. The host writes data to primary page sub-pages U 01 A, U 02 A, U 13 A, U 04 A, U 05 A, U 06 A which are marked with status P in S 01 A, S 02 A, S 13 A, S 04 A, S 05 A, S 06 A, respectively. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={P, P, D, P, P, P}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, D, P, I, D, I}

After sub-pages U 01 A, U 02 A, U 13 A, U 04 A, U 05 A, U 06 A are mirrored to sub-pages U 01 B, U 02 B, U 13 B, U 04 B, U 05 B, U 06 B, respectively, status of sub-pages U 01 A, U 02 A, U 13 A, U 04 A, U 05 A, U 06 A, U 01 B, U 02 B, U 13 B, U 04 B, U 05 B, U 06 B is updated to D in S 01 A, S 02 A, S 13 A, S 04 A, S 05 A, S 06 A, S 01 B, S 02 B, S 13 B, S 04 B, S 05 B, S 06 B, respectively, status of sub-pages U 12 A, U 03 A, U 15 A, U 12 B, U 03 B, U 15 B is updated to I in S 12 A, S 03 A, S 15 A, S 12 B, S 03 B, S 15 B, respectively, and the write is acknowledged to the host. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={D, D, I, D, D, D}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, I, D, I, I, I}

The reason that sub-page U 13 A was written to instead of sub-page U 03 A is that sub-page U 03 A had status D at the time the write was initiated.

Next the host indicates it needs to write to sectors corresponding to sub-page U 03 A. The host writes data to primary page sub-pages U 03 A, which is marked with status P in S 03 A. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={D, D, P, D, D, D}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, I, D, I, I, I}

After sub-page U 03 A is mirrored to sub-pages U 03 B, status of sub-pages U 03 A, U 03 B is updated to D in S 03 A, S 03 B, respectively, status of sub-pages U 13 A, U 13 B is updated to I in S 13 A, S 13 B, respectively, and the write is acknowledged to the host. The page 98 A and 99 A status indicators may now indicate the following:

{S 01 A, S 02 A, S 03 A, S 04 A, S 05 A, S 06 A}={D, D, D, D, D, D}

{S 11 A, S 12 A, S 13 A, S 14 A, S 15 A, S 16 A}={I, I, I, I, I, I}

At this point, since all sub-pages of pages 99 A, 99 B have status I, pages 99 A, 99 B can be de-allocated.

In different examples, if all sub-pages of pages 98 A, 98 B have status I, pages 98 A, 98 B can be de-allocated, in which case pages 99 A, 99 B become the primary pages.

At least one implementation involves objects referred to as logical pages (which may include a compound transactional page) and simple transactional pages. A logical page (e.g., page 1020 A or 1020 B) is the portion of a cache page reference that describes the cache pages the reference is using for its caching. The logical page itself tracks only information about the state of the data on the peer SP, along with some summary bits about the state of the data in the local pages for performance optimization. Each logical page also has a transient free list to ensure that mirrored cache pages cannot be freed and reused prior to a transaction commit. The logical page may be divided up into cache page size units. If the cache page reference describes 32 k of the volume's address space, and the cache page represents 4 k of memory, the compound transactional page has an array of 8 simple transactional pages. The simple transactional page (STP) represents a slot in the volumes virtual address space the same size as the cache page, and tracks whether data exists in the cache on a per-sector basis. For each sector, the state (i.e., status) can be invalid, valid, dirty, prepared, or dirty and prepared. In the latter case, a simple transactional page can hold both the previously committed data, and data that is about to be committed. In the prepared case, it only holds data that has not yet been committed. The commit operation includes setting all D values for which there is a corresponding P value to an I value, and then to change each P value to a D value. This sequence is idempotent, i.e., it can be repeated from the beginning if it is interrupted.

At least some implementations have one or more of the following characteristics. The host sends I/O that has a size that is a multiple of a typical sector size of 512 bytes. The cache has data, header/metadata (which describes what is in the data), and a cache tag. Linked lists are used, and a unit of tracking needs to be of significant size to avoid metadata using significant memory compared to the page itself. A host should not perform a write (e.g., a DMA write) over a sub-page that has dirty data, because such dirty data may be lost if the write fails.

While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.