- A. In the read-before write step (e.g., step64 ofFIG. 4 or step114 ofFIG. 6), verify whether the existing content of the data block is equal to the “Test” value of the application ATS. If a mismatch is found, fail the application ATS request and return “ERROR_ATS_TEST.”
- B. The fully collaborative writer optimization does not apply to application ATS. Thus, steps76 and84 ofFIG. 4 (or steps134 and142 ofFIG. 6) should be kept separate and not merged. In an embodiment,agent40 sends to the storage device, because the ATS issued for updating the redundancy of the stripe ensures application-ATS serialization. In one rare scenario, all redundancy elements of the stripe are missing (e.g., because the storage devices on which they are stored have all failed). In this scenario, the write of the data itself should be performed using ATS.

Full-Stripe Write Optimization

In the case of full-stripe write (in which all data blocks and redundancy blocks are updated), there is no need to read-before-write the existing data blocks since the new redundancy is calculated entirely based on the new data. For fully-collaborative writers, there is no need to perform ATS in a full-stripe write since the entire stripe is being overwritten. The flow in this case is simpler:

- A. Assignnew timestamps102 to all data blocks.
- B. Calculate new redundancy blocks based only on the new data elements, regardless of the old data and the old redundancy.
- C.Set timestamp arrays106 in the redundancy blocks to equal thenew timestamps102 assigned at step A.
- D. Copy all I/O commands to the staging RAM.
- E. Issue all I/O commands (data and redundancy) concurrently to the storage devices (all using regular write commands, no need for ATS).

Write Hole (Server Failure) Problem

If a server fails in the middle of a RAID transaction, some of the I/O commands may have been completed, and others may have not. For example, in one scenario the ATS command has completed successfully, but the data write commands have not. Various other failure scenarios are possible. In such cases, the information in the strip is irrecoverable since the redundancy information is inconsistent with the data.

As explained above, in some embodiments these scenarios are mitigated using stagingRAMs48, which hold the various I/O requests being performed, and should allow a storage controller or another server the ability to retry these I/O requests.

In an embodiment,storage controller36 regularly monitorsservers24 for liveliness. Upon detecting a server failure (e.g., disappearance or crash), the storage controller may handle orphan I/O requests belonging to the failed server, and perform the retries that the server was supposed to perform. Before attempting this action, the storage controller will typically ping the server for liveliness. If the server is indeed unresponsive, the storage controller will typically black-list it as failed (e.g., prevent the server from issuing new I/O requests).

Staging RAM Concurrent Access

As explained above, in some embodiments eachserver24 is assigned arespective staging RAM48. This assignment is typically performed upon setup of the server insystem20 bystorage controller36.Staging RAM48 for a givenserver24 is typically reserved for that server alone, and there is therefore no need to lock it as it is not being written to concurrently by any other server.

In case of server failure,storage controller36 will typically perform clean-up of the staging RAM assigned to that server, and eventually release this staging RAM for other purposes.

Staging RAM Failure

In some cases a writing server may detect that its assigned staging RAM48 (or the entire staging-RAM unit44) has failed or is otherwise unavailable. In some embodiments, the server may re-attempt the entire write request (for the entire RAID transaction) via another path tostorage devices28. Many storage device configurations enable this sort of solution. A group of storage devices configured as “Just a Bunch Of Disks” (JBOD), for example, has two front-end I/O elements for redundancy. Thus, it is possible that each of these front-end elements will have its own RAM and that the two front-end elements belong to separate failure domains.

Staging RAM and Writing Server Failure

In some cases the writing server may fail concurrently with its staging RAM48 (or with the entire staging-RAM unit44). In case of such a double failure, the RAID stripe may become corrupted, e.g., when some of the write I/O commands are committed by the storage devices and some are not. Moreover, in such a scenario there is usually no record that this I/O request took place, so there is no hint for a storage controller or another server to perform stripe recovery.

In such a scenario, the data blocks that the failed server was trying to write to become inconsistent, which is permissible according to the SCSI standard. One problematic issue is that the redundancy blocks do not necessarily reflect the correct data.System20 may provide various solutions to this problem.

In one embodiment, the above problem is avoided using staging RAM redundancy. For example, the writing server may write each I/O request to twoseparate staging RAMs48. Additionally or alternatively,system20 may run a background scrubbing process that detects inconsistencies betweentimestamps102 andtimestamp arrays106, and perform stripe recovery as needed (including re-calculation of redundancy blocks).

Scrubbing Process

As noted above,system20 may run a scrubbing process that periodically reads data blocks from the storage devices and verify that the corresponding redundancy blocks are correct. The verification may consider the data and redundancy information itself, or it may be based on comparingtimestamps102 andtimestamp arrays106. As noted above, such inconsistency may be indicative of a potential server failure and/or staging-RAM failure. Upon detecting inconsistency, the redundancy information should typically be re-calculated, e.g., by a storage controller or by a functional server.

The rate at which the scrubbing process is performed may vary depending on implementation. Typically, the scrubbing process updates the redundancy blocks using ATS commands or other form of locking, as explained above.

Degraded Read

When one of the data blocks in a RAID stripe is missing, e.g., due to storage device failure, a reading server may reconstruct the data in the missing data block using the redundancy block(s) and the remaining data blocks of the stripe. This reconstruction is sometimes referred to as “degraded read.”

Since, in some embodiments, the redundancy blocks contain a respective timestamp for each data block in the stripe, the reading server can verify that the redundancy blocks are correct (i.e., consistent with the data blocks) by checking the timestamps intimestamp array106 againsttimestamps102 of the corresponding data blocks.

In case of timestamp mismatch, the missing data block cannot be reconstructed. This may be a transient effect due to a race condition with a stripe update, and therefore the reading server should typically re-attempt the entire operation before declaring failure. If the timestamp mismatch is persistent after several attempts, the reading server may attempt to lock the LUN in question, or parts thereof, via SCSI reservation, and re-attempt the degraded read again. If this attempt also fails, the stripe may be irrecoverable (e.g., the reading server may receive MEDIUM_ERROR).

In an example embodiment, a degraded read process may involve the following steps:

- A. If all the missing blocks are redundancy blocks, no further action is needed during degraded read since the data is intact. Thus, a regular read flow is executed.
- B. Read all the available data blocks in the stripe, and the available redundancy blocks.
- C. Verify that the timestamps inarray106 in the redundancy blocks matchtimestamps102 of the available data blocks. In case of a mismatch, re-attempt step B several times until the timestamps match, to rule out a possible transient effect due to a concurrent write.
- D. If even after several attempts the timestamps do not match, attempt to lock the LUN or parts thereof and then re-attempt step B one final time.
- E. If the timestamps match, the missing data block can now be reconstructed. For RAID-5, for example, in case the storage device containing d1 has failed, the d1 data can be reconstructed as d1=p-sum(d2 . . . d8).
- F. If the timestamps do not match, the missing data block cannot be reconstructed, and if the re-attempts described above have not resolved the situation, return a MEDIUM_ERROR to the host.

Degraded Write

When a RAID stripe has missing blocks, e.g., due to storage device failure or other storage device unavailability,system20 can still receive and perform write requests in the strip. This process is sometimes referred to as “degraded write.”

If the missing block is a data block that is not being modified, this block can be ignored and a regular write performed. If, on the other hand, the missing block is a data block that is being modified, it should first be reconstructed from the RAID stripe using a degraded read in order to enable calculating the new redundancy information based on the old redundancy information. Thus, in an embodiment, the degraded write process is similar to the write process ofFIG. 4, with the exception that some of the read-before-write operations are in effect degraded read operations.

If the stripe has one or more missing redundancy blocks, the server may perform the ATS command on the first available redundancy block. Unavailable redundancy blocks do not need to be reconstructed. If all redundancy blocks in the stripe are missing, the server may perform a regular write instead of an ATS command.

Extension to RAID Schemes Having Multiple Redundancy Blocks Per Stripe (e.g., RAID-6 and Beyond)

In some embodiments,system20 may carry out the disclosed techniques with a RAID scheme that defines two or more redundancy blocks per RAID stripe. Typically, each redundancy block will contain atimestamp array106 as explained above. In an embodiment, when performing a RAID transaction, only the first redundancy block is written using an ATS command, whereas the other redundancy block(s) are written using regular write commands.

When performing a degraded write, the writing server should perform locking (e.g., using an ATS command) based on the first available redundancy block (e.g., in RAID-6 having redundancy blocks p and q, if a storage device failure rendered p missing, the ATS command will be performed in writing q). When degraded write is performed without any redundancy block, the entire degraded write process may be performed using regular write commands, without ATS or other lock. Such a scenario may occur, for example, in RAID-6 with a double storage device failure that rendered both p and q missing.

Rebuild Process

After a storage device has failed and was replaced, the missing data blocks on that storage device can be rebuilt (or rebuilt even before the actual device is replaced into some spare capacity of the system). The rebuild process recreates missing data and/or redundancy blocks in the stripe via degraded reads for missing data blocks, and redundancy re-calculations for missing redundancy blocks. The rebuild process should write under a suitable lock (e.g., using ATS commands) similarly to the regular write operations described above.

In case the LUN or parts thereof are locked (e.g. under SCSI reservation), or in case of fully collaborative writers, the rebuild process should write the data blocks (and not only the redundancy blocks) using ATS, in order not to interfere with concurrent writes from the user (since the user is not aware that there is a potential for a write conflict).

Single Writer Optimization

Some of the complexity and latency of the ATS mechanism can be avoided if it is explicitly known that there is only a single writer for the LUN in question. A single-writer scenario may occur, for example, if there is only one server mapped to write to the LUN, or if there is a SCSI reservation that locks the LUN or parts thereof for exclusive writing. In case of a single writer, there is no need to perform ATS commands since there are no concurrent writers. This optimization reduces latency.

Moreover, in a single-writer scenario there is no need to read-before-write only for the purpose of ATS. For example, for a full-stripe write there is no need to read the first parity block (p). This optimization also reduces latency.

If additional writers are later mapped to the LUN, the single writer should be made aware of this fact and switch back to ATS-based operation. Before the mapping of the new writers can be completed, in-flight I/O requests should be allowed to complete. Typically, the rebuild process in this use case should write both data blocks and redundancy blocks under suitable locking (e.g., using ATS commands).

Full-Stripe Write Opportunistic Locking Optimization

When there are many full-stripe writes occurring from a given server to a given LUN, this scenario may be indicative of an intensive write pattern (e.g., sequential or large block). In such a case, locking the LUN (or parts thereof) for exclusive writes may be beneficial as the intensive write will be completed faster. Such a lock may even be beneficial for the other (locked-out) concurrent writers.

In some embodiments, server-local monitoring of I/O patterns may trigger upon a sufficiently-high quantity of sufficiently-large blocks during a certain period of time. Then, the server may attempt a SCSI reservation for exclusive writing to the LUN or parts thereof. This locking request is opportunistic, and if it fails the above-described ATS mechanism can be employed. The server should take care not to overuse the SCSI reservations, and the extent of use can be monitored via SCSI reservation failures that indicate high activity on the LUN.

Block Ordering in Stripe

In various embodiments, the servers may order the data and parity blocks in a stripe in various suitable orders. Different block orders enable different trade-offs between increasing the likelihood of full-stripe write operations and reducing the number of read operations.

Consider, for example a RAID scheme having n data block and m parity blocks, stored in a stripe over (n+m) disks. The size of a full-stripe write is (n)*(number_of_rows)*(disk_atomic_block_size). In an embodiment, the data blocks are written to a given stripe in column order, as follows:


D 1	D 2	. . .	D n	P	Q

Row = 1	#1	# r + 1	. . .	. . .	P of row 1	Q of row 1
Row = 2	#2	# r + 2	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .
Row = r	#r	# 2r	. . .	# n · r	P of row n	Q of row n

Each column in the above table corresponds to a different physical disk. Each row in the table is a logical grouping of blocks that have one or more respective parity blocks calculated upon them (P and Q in the present example). A full-stripe write requires (r rows)*(n disks) writes. The blocks within the full stripe are written column-by-column (i.e., filling each column before proceeding to next).

The effect of this organization is that a trade-off can be struck between writing full stripes vs. performing as few disk read operations as possible. Consider, for example, the case of n=8, and disk_atomic_block_size=4 KB. If number_of_rows is 8, a full-stripe write is 256 KB in size, and thus less likely, but a 32 KB read will incur a single disk I/O. On the other hand, if number_of_rows is 1, a full-stripe write is 32 KB (and thus very likely), but a 32 KB read will incur 8 disk read I/Os.

The parameter number_of_rows is typically determined upon initialization (formatting) of the storage array, but allows flexibility to improve read performance or write performance based on the application being used.

Alternating Data/Parity Roles of Disks

In some redundancy calculation schemes, the parity information is accessed (and in particular written) much more frequently than the data. Thus, in some embodiments the system alternates the roles ofdisks28 between stripes, so that each disk holds data in some stripes, and parity in other stripes. As a result, performance is balanced among the disks. In an example embodiment, the role is alternated every X stripes, as follows:


D 1	D 2	. . .	D n	D n + 1	D n + 1

Stripes 1 . . . X	d1	d2	. . .	dn	P	Q
Stripes (X + 1) . . . 2X	d2	d3	. . .	P	Q	d1
. . .
Stripes	Q	d1	. . .		dn	P
((n + 1)X) +
1 . . . (n + 2) X

In the above table, physical disks are denoted “D1” . . . “D n+1” while data blocks are denoted d1 . . . dn. The parameter X may be determined and fixed, for example, upon initialization (formatting) of the storage array.

It will be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art. Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.