Optimizing read-modify-write operations to a storage device by writing a copy of the write data to a shadow block

A computer-implemented method according to one embodiment includes initiating a read-modify-write (RMW) operation; assigning the RMW operation to a thread; identifying a storage device associated with the RMW operation; assign a log block within the storage device to the thread; determining a free shadow block location within the storage device; creating a copy of data to be written to the storage device during the RMW operation; writing the copy of the data to the free shadow block location within the storage device; updating the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and writing the data to one or more blocks of a home area of the storage device.

BACKGROUND

The present invention relates to data protection, and more specifically, this invention relates to ensuring data consistency via write operation atomicity.

Many storage devices (e.g., non-volatile, block-addressable storage, etc.) implement erasure code-protected data storage. Erasure codes may store both data as well as some form of parity computed from the data. In order to implement erasure code-protected data storage, both the data and the parity information need to be updated in the same atomic transaction (e.g., to prevent data corruption). However, current methods for implementing such erasure code protection are expensive, and complex.

SUMMARY

A computer-implemented method according to one embodiment includes initiating a read-modify-write (RMW) operation; assigning the RMW operation to a thread; identifying a storage device associated with the RMW operation; assigning a log block within the storage device to the thread; determining a free shadow block location within the storage device; creating a copy of data to be written to the storage device during the RMW operation; writing the copy of the data to the free shadow block location within the storage device; updating the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and writing the data to one or more blocks of a home area of the storage device.

According to another embodiment, a computer program product for optimizing atomic writes to a storage device includes a computer readable storage medium having program instructions embodied therewith, where the computer readable storage medium is not a transitory signal per se, and where the program instructions are executable by a processor to cause the processor to perform a method including initiating, by the processor, a read-modify-write (RMW) operation; assigning, by the processor, the RMW operation to a thread; identifying, by the processor, the storage device associated with the RMW operation; assigning, by the processor, a log block within the storage device to the thread; determining, by the processor, a free shadow block location within the storage device; creating, by the processor, a copy of data to be written to the storage device during the RMW operation; writing, by the processor, the copy of the data to the free shadow block location within the storage device; updating, by the processor, the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and writing, by the processor, the data to one or more blocks of a home area of the storage device.

According to another embodiment, a system includes a processor; and logic integrated with the processor, executable by the processor, or integrated with and executable by the processor, where the logic is configured to initiate a read-modify-write (RMW) operation; assign the RMW operation to a thread; assign a log block within the storage device to the thread; identify a storage device associated with the RMW operation; determine a free shadow block location within the storage device; create a copy of data to be written to the storage device during the RMW operation; write the copy of the data to the free shadow block location within the storage device; update the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and write the data to one or more blocks of a home area of the storage device.

DETAILED DESCRIPTION

The following description discloses several preferred embodiments of systems, methods and computer program products for optimizing atomic writes to a storage device.

In one general embodiment, a computer-implemented method includes initiating a read-modify-write (RMW) operation; assigning the RMW operation to a thread; identifying a storage device associated with the RMW operation; assigning a log block within the storage device to the thread; determining a free shadow block location within the storage device; creating a copy of data to be written to the storage device during the RMW operation; writing the copy of the data to the free shadow block location within the storage device; updating the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and writing the data to one or more blocks of a home area of the storage device.

In another general embodiment, a computer program product for optimizing atomic writes to a storage device includes a computer readable storage medium having program instructions embodied therewith, where the computer readable storage medium is not a transitory signal per se, and where the program instructions are executable by a processor to cause the processor to perform a method including initiating, by the processor, a read-modify-write (RMW) operation; assigning, by the processor, the RMW operation to a thread; identifying, by the processor, the storage device associated with the RMW operation; assigning, by the processor, a log block within the storage device to the thread; determining, by the processor, a free shadow block location within the storage device; creating, by the processor, a copy of data to be written to the storage device during the RMW operation; writing, by the processor, the copy of the data to the free shadow block location within the storage device; updating, by the processor, the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and writing, by the processor, the data to one or more blocks of a home area of the storage device.

In another general embodiment, a system includes a processor; and logic integrated with the processor, executable by the processor, or integrated with and executable by the processor, where the logic is configured to initiate a read-modify-write (RMW) operation; assign the RMW operation to a thread; assign a log block within the storage device to the thread; identify a storage device associated with the RMW operation; determine a free shadow block location within the storage device; create a copy of data to be written to the storage device during the RMW operation; write the copy of the data to the free shadow block location within the storage device; update the log block within the storage device to point to the free shadow block location to which the copy of the data is written; and write the data to one or more blocks of a home area of the storage device.

Now referring toFIG. 3, a storage system300is shown according to one embodiment. Note that some of the elements shown inFIG. 3may be implemented as hardware and/or software, according to various embodiments. The storage system300may include a storage system manager312for communicating with a plurality of media on at least one higher storage tier302and at least one lower storage tier306. The higher storage tier(s)302preferably may include one or more random access and/or direct access media304, such as hard disks in hard disk drives (HDDs), nonvolatile memory (NVM), solid state memory in solid state drives (SSDs), flash memory, SSD arrays, flash memory arrays, etc., and/or others noted herein or known in the art. The lower storage tier(s)306may preferably include one or more lower performing storage media308, including sequential access media such as magnetic tape in tape drives and/or optical media, slower accessing HDDs, slower accessing SSDs, etc., and/or others noted herein or known in the art. One or more additional storage tiers316may include any combination of storage memory media as desired by a designer of the system300. Also, any of the higher storage tiers302and/or the lower storage tiers306may include some combination of storage devices and/or storage media.

The storage system manager312may communicate with the storage media304,308on the higher storage tier(s)302and lower storage tier(s)306through a network310, such as a storage area network (SAN), as shown inFIG. 3, or some other suitable network type. The storage system manager312may also communicate with one or more host systems (not shown) through a host interface314, which may or may not be a part of the storage system manager312. The storage system manager312and/or any other component of the storage system300may be implemented in hardware and/or software, and may make use of a processor (not shown) for executing commands of a type known in the art, such as a central processing unit (CPU), a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), etc. Of course, any arrangement of a storage system may be used, as will be apparent to those of skill in the art upon reading the present description.

According to some embodiments, the storage system (such as300) may include logic configured to receive a request to open a data set, logic configured to determine if the requested data set is stored to a lower storage tier306of a tiered data storage system300in multiple associated portions, logic configured to move each associated portion of the requested data set to a higher storage tier302of the tiered data storage system300, and logic configured to assemble the requested data set on the higher storage tier302of the tiered data storage system300from the associated portions.

Now referring toFIG. 4, a flowchart of a method400is shown according to one embodiment. The method400may be performed in accordance with the present invention in any of the environments depicted inFIGS. 1-3, and 6-8, among others, in various embodiments. Of course, greater or fewer operations than those specifically described inFIG. 4may be included in method400, as would be understood by one of skill in the art upon reading the present descriptions.

As shown inFIG. 4, method400may initiate with operation402, where a read-modify-write (RMW) operation is initiated. In one embodiment, the RMW operation may include an operation that writes data to one or more storage devices. In another embodiment, the RMW operation may read old data and corresponding parity information from one or more predetermined locations within one or more storage devices.

Additionally, in one embodiment, the RMW operation may modify the read data, as well as the corresponding parity information. In another embodiment, the RMW operation may modify the read data, as well as the corresponding parity information.

Further, in one embodiment, the one or more storage devices may be included within a distributed storage environment. For example, the distributed storage environment may include a plurality of erasure code-protected storage devices (e.g., an erasure code array that includes an array of storage devices that implement an erasure code, etc.). In another example, the distributed storage environment may include a plurality of replication storage devices (e.g., a replication array that includes an array of storage devices that implement replication, etc.). In yet another example, the distributed storage environment may include data storage, cloud-based storage, local storage, etc. In yet another example, erasure code-protected storage may include a method of storing data that transforms data into a code word, where the data can be recovered using a subset of such code word.

Further still, in one embodiment, the RMW operation may be initiated within intermediary storage. For example, the intermediary storage may include one or more volatile data buffers at one or more host computers that are in communication with the one or more storage devices. In another example, the intermediary storage may include volatile memory such as dynamic random-access memory (DRAM), static random-access memory (SRAM), etc. In yet another example, the RMW operation may be buffered in the intermediary storage before writes are performed at the one or more storage devices.

Also, method400may proceed with operation404, where the RMW operation is assigned to a thread. In one embodiment, the thread may include a predetermined sequence of programmed instructions. In another embodiment, the thread may be managed by a scheduler within an operating system (OS) of a system.

In addition, in one embodiment, the thread may be associated with predetermined home area blocks of each of a plurality of storage devices, as well as predetermined log blocks. For example, the home area blocks may include storage blocks within the storage devices that are reserved for storing data to be written. In another example, the predetermined home area blocks may be reserved for the thread within the system, within the one or more storage devices, etc.

Furthermore, in one embodiment, the thread may be associated with predetermined log shadow blocks of each of the plurality of storage devices. For example, the log shadow blocks may include shadow blocks within the storage devices that are reserved for storing temporary copies of the data written to the home area blocks, as well as for storing log blocks that point to active shadow blocks.

Further still, in one embodiment, the amount of home area blocks and log shadow blocks may be predetermined, may be based on historical or predicted input/output (I/O) workloads to the storage devices, etc. In another embodiment, the home area blocks and log shadow blocks may be divided using partitions, or may be intermixed using logical partitions without physical partitions. IN yet another embodiment, the RMW operation may be assigned a monotonically-increasing transaction sequence number associated with the RMW operation.

Also, method400may proceed with operation406, where a storage device associated with the RMW operation is identified. In one embodiment, the RMW operation may instruct the writing of data to a specific plurality of storage devices within a distributed storage environment. In another embodiment, each of the specific plurality of storage devices may be identified, based on the RMW operation. In yet another embodiment, each of the specific plurality of storage devices may be identified based on a specific erasure code utilized within the distributed storage environment.

Further, method400may proceed with operation408, where a log block within the storage device is assigned to the thread. In one embodiment, a log block within each storage device that is involved in the RMW transaction may be assigned to the thread.

Additionally, method400may proceed with operation410, where a free shadow block location is determined within the storage device. In one embodiment, the storage device may include log shadow blocks reserved for the thread to which the RMW operation is assigned. In another embodiment, the reserved log shadow blocks may include an active shadow block and a free shadow block.

For example, the active shadow block may include the latest temporary copy of data that is written/to be written to home area blocks within the storage device. In another example, the free shadow block may include a temporary copy of other data that older than the data stored in the active shadow block.

Further, in one embodiment, the reserved log shadow blocks may also include a log block. For example, the log block may point to a location of the active shadow block within the storage device. In another embodiment, the free shadow block location may be determined utilizing the log block within the storage device.

For example, locations of a first shadow block and a second shadow block may be identified within the storage device. In another example, the log block may be referenced to identify whether the first or second shadow block is the active shadow block. In yet another example, the free shadow block location may include the shadow block that is not the identified active shadow block.

Further still, in one embodiment, the free shadow block location may be determined utilizing a location cache. For example, the locations of the free shadow block and the active shadow block may be stored in the location cache. In another example, the cache may be referenced to determine the location of the free shadow block.

Also, method400may proceed with operation412, where a copy of data to be written to the storage device during the RMW operation is created. In one embodiment, the copy of the data may be created within the intermediary storage. In another embodiment, the copy of the data may be created by the thread to which the RMW operation is assigned.

In addition, method400may proceed with operation414, where the copy of the data is written to the free shadow block location within the storage device. In one embodiment, the copy of the data may be written from the intermediary storage to the storage device. In another embodiment, the copy of the data may be written by the thread to which the RMW operation is assigned.

Furthermore, method400may proceed with operation416, where the log block within the storage device is updated to point to the free shadow block location to which the copy of the data is written. In one embodiment, the log block may be included within the log shadow blocks that are reserved for the thread within the storage device. In another embodiment, the log block may initially point to the active shadow block.

Further still, in one embodiment, once the copy of the data has been written to the free shadow block, the free shadow block may be updated to become the updated active shadow block. Likewise, the active shadow block may be updated to become the updated free shadow block. As a result, the log block may be updated to point to the updated active shadow block.

Also, in one embodiment, the log block may be updated simultaneously with the writing of the copy of the data to the free shadow block location. This may reduce a number of I/O operations during the RMW operation. In another embodiment, the transaction sequence number associated with the RMW operation may also be stored within the log block.

Additionally, method400may proceed with operation418, where the data is written to one or more blocks of a home area of the storage device. In one embodiment, the one or more blocks may be included within the home area blocks within the storage device that are reserved for the thread during an RMW operation. In another embodiment, the writes to the home area blocks may be performed in parallel with the writes to the log shadow blocks.

In one embodiment, a single write operation may be used to both write the copy of the data to the free shadow block location within the storage device and update the log block within the storage device to point to the free shadow block location to which the copy of the data is written. This may be enabled utilizing reordered shadow blocks, combined log and shadow blocks, etc. In this way, I/O overhead may be reduced from two I/O operations per device to one I/O operation per device when performing the RMW operation.

In this way, the RMW operation may be performed with transaction-level atomicity. For example, the RMW operation may be performed at the storage device in a single step, with no partial write state. This ensures that the data and the parity information (e.g., the copy of the data), or multiple copies of the data (in the case of replication) are written to the storage device in a single atomic transaction, which may avoid data corruption during RMW operations within the storage device.

Additionally, by keeping the home area blocks and the log shadow blocks within a single storage device, a complexity of the RMW operation may be reduced, and resource costs of the RMW operation may also be lowered. This may improve a performance of RMW operations using the storage device, which may in turn improve a performance and operation of a system running intermediary storage in communication with the storage device.

Now referring toFIG. 5, a flowchart of a method500for replaying read-modify-write (RMW) operations within a system is shown according to one embodiment. The method500may be performed in accordance with the present invention in any of the environments depicted inFIGS. 1-3, and 6-8, among others, in various embodiments. Of course, greater or fewer operations than those specifically described inFIG. 5may be included in method500, as would be understood by one of skill in the art upon reading the present descriptions.

As shown inFIG. 5, method500may initiate with operation502, where a system is restarted. In one embodiment, the system may be restarted in response to a system crash, a system reboot, etc. In another embodiment, the system may include one or more storage devices. In yet another embodiment, the system may include intermediary storage in communication with the one or more storage devices.

Additionally, method500may proceed with operation504, where all log blocks are read from the storage devices that require recovery for all threads that were active within the system when the system was last used. In one embodiment, the log blocks may be filtered so that only a predetermined number of pertinent log blocks are read (e.g., log blocks associated with predetermined threads, etc.). In another embodiment, each storage device within the system may include reserved blocks for each of a plurality of threads. In yet another embodiment, for each of the plurality of threads, a log block may be stored within the storage device within the reserved blocks for that thread.

Further, method500may proceed with operation506, where all the log blocks are sorted, utilizing transaction sequence numbers for each of the log blocks. In one embodiment, each of the log blocks includes a pointer to an active shadow block location, as well as a monotonically-increasing transaction sequence number.

For example, transaction sequence numbers are assigned to threads with associated RMW operations. These transaction sequence numbers are increased monotonically as they are assigned. For instance, after a first sequence number is assigned to a first thread, a second sequence number is determined by monotonically increasing the first sequence number, and the second sequence number is assigned to a second thread that is instantiated after the first thread. As a result, a thread with a lower sequence number was instantiated before a thread with a greater sequence number.

Further still, in one embodiment, the log blocks may be sorted from lowest to highest sequence number.

Also, method500may proceed with operation508, where one or more read-modify-write (RMW) operations are replayed, utilizing the sorted log blocks. In one embodiment, starting with the log block with the lowest sequence number, the updated active shadow block location pointed to by the log block may be determined. In another embodiment, the copy of the data stored within the updated active shadow block location may be retrieved and stored within one or more blocks of a home area of the storage device that is reserved for the same thread that stored the copy of the data within the updated active shadow block location.

In this way, data writes may be replayed within a system after a system crash or reboot.

FIG. 6Aillustrates an exemplary representation600of contents of log blocks and shadow blocks602-606within a plurality of storage devices608prior to a read-modify-write (RMW) operation, according to one exemplary embodiment. As shown, the log blocks and shadow blocks602-606include a log block602and shadow blocks604-606that are reserved for a predetermined thread (in this case, thread42).

Additionally, in response to an initiation of the RMW operation and the assigning of the RMW operation to thread42, the RMW operation is analyzed to determine which storage devices608are to be written to during the RMW operation. In this case, the RMW operation instructs the writing of data to storage device1610within a distributed storage environment.

In one embodiment, the thread may include a process for performing a RMW operation (e.g., by attempting to write one or more data blocks atomically to the storage devices608, etc.).

Further, in response to determining that storage device1610is to be written to during the RMW operation, a second shadow block location612is determined to store a free shadow block within storage device1610. In one embodiment, the second shadow block location612may be determined to store the free shadow block by referencing the log block614for storage device1610, which points to the first shadow block616as the active shadow block. In another embodiment, a separate location cache may be referenced to identify the second shadow block location612.

FIG. 6Billustrates an exemplary representation600of contents of log blocks and shadow blocks602-606within a plurality of storage devices608during a read-modify-write (RMW) operation, according to one exemplary embodiment. As shown, once the second shadow block location612is determined to store the free shadow block within storage device1610inFIG. 6A, a copy is made of data to be written to the storage device during the RMW operation, and the copy of the data is written to the second shadow block location612within storage device1610.

At this point, the second shadow block location612now stores the updated active shadow block. The second shadow block location612is marked as “outstanding” since the log block614for storage device1610is not yet updated to point to the second shadow block location612as the updated active shadow block.

FIG. 6Cillustrates an exemplary representation600of contents of log blocks and shadow blocks602-606within a plurality of storage devices608after a completion of a read-modify-write (RMW) operation, according to one exemplary embodiment. As shown, after a copy of data is written to the second shadow block location612within storage device1610inFIG. 6B, the log block614for storage device1610is updated to point to the second shadow block location612as the updated active shadow block.

The second shadow block location612is marked as “active” since the log block614for storage device1610has been updated to point to the second shadow block location612as the updated active shadow block. The first shadow block location616is then marked as “Old” since it contains copy data older than the copy data stored in the second shadow block location612, and is no longer pointed to by the log block614.

In one embodiment, the log block614for storage device1610is updated to point to the second shadow block location612at the same time the copy of the data is written to the second shadow block location612within storage device1610. This may enable a state transition fromFIG. 6Adirectly toFIG. 6C, without the intermediary state shown inFIG. 6B.

In this way, an atomic RMW operation may be performed within the plurality of storage devices608, utilizing the log blocks and shadow blocks602-606of the storage devices608.

FIG. 7illustrates an exemplary representation700of combined log and shadow blocks702-704within a plurality of storage devices706, according to one exemplary embodiment. As shown, the combined log and shadow blocks702-704are reserved for a predetermined thread (in this case, thread N).

Additionally, in response to RMW operations and the assigning of the RMW operations to thread N, thread N ping-pongs between the combined log and shadow blocks702-704using a single I/O operation. During recovery, the system reads both of the combined log and shadow blocks702-704and uses the block with the higher number for recovery operations.

FIG. 8illustrates an exemplary representation800of reordered shadow blocks802-804within a plurality of storage devices808, according to one exemplary embodiment. As shown, the reordered shadow blocks802-804are reserved for a predetermined thread (in this case, thread N). Additionally, a single common log block806is sandwiched between the reordered shadow blocks802-804. In this way, a single write operation may be used to update one of the reordered shadow blocks802-804as well as the single common log block806together in a single I/O operation that writes to contiguous LBA regions on the storage device. During recovery, only the single common log block806is needed for recovery for thread N.

FIG. 9illustrates an exemplary representation900of a single combined log and shadow block902within a plurality of storage devices904, according to one exemplary embodiment. As shown, the single combined log and shadow block702is reserved for a predetermined thread (in this case, thread N).

The lack of ping-pong areas for thread N is possible because thread N will attempt to write to the single combined log and shadow block902only when the previous write it was handling has completed, thus no longer requiring a shadow block region. The single combined log and shadow block902is sized to match a block size of the storage device, which is guaranteed to provide atomic updates at the block level.

As a result, a crash when writing to the single combined log and shadow block902will result in either the old or the new copy on the disk being found during the next recovery. Additionally, thread N may write to M devices at a time (e.g., due to RAID operations) and the log block may be replicated on each of the M devices. Thus, if the single combined log and shadow block902is unreadable due to a media error (e.g., a hardware error), then recovery can still occur using a replica of the single combined log and shadow block902on other devices. When a single combined log and shadow block902of thread N is unreadable during recovery (or runs into a checksum error due to a torn write), then the system may mark the region on that device indicated in the single combined log and shadow block902as stale and may prevent future writes until the area is overwritten or asked to be ignored by an administrator.

Parallel Shadow Copy and Transaction Log Write for Atomic Write

To update erasure code protected storage devices, atomicity of write operation may be required to ensure code is always consistent. In a system where NV (Non-Volatile) memory is available, the write operation is buffered in NV memory, so power outages and software crashes may not interrupt the write operation. As a result, atomicity of writes is guaranteed. However, NV memory is expensive and complex to integrate with regular systems. Systems without NV memory rely on software technique to implement atomic write.

In general, such techniques involve two parts: one is to write the updated content to a temporary location, which is called a shadow copy location, before writing to its intended location (called a home location). The other is to keep track of the outstanding write operations in a log, which is called a transaction log. The transaction log stores the details of the outstanding writes such as the home location and the shadow copy location. In the event of a system crash or a power outage, the transaction log is scanned and then replayed idempotently (e.g., by updating a home location from a shadow copy) to ensure that all the outstanding writes are atomic.

However, transactional logs and shadow copies have a performance impact. It takes at least two extra writes for a single atomic write operation. These extra I/O operations makes a Read-Modify-Write operation slower. As a result, optimization may be performed by directing the log and shadow I/O operations to a separate device. However, by doing this, the cost of the system is increased, as fast and reliable NV storages are expensive. Additionally, the complexity of the system is increased by requiring extra devices. Further, the improvement in I/O operations may not scale with the main storage devices (e.g., in a large system, a dedicated central log device would eventually become a performance bottleneck).

In one solution, each block device in the storage array is partitioned into 3 parts: a metadata area, a log/shadow area, and a home area. The metadata area is for storing permanent or infrequently-updated information about the storage system. The log/shadow area is for storing temporary block updates and keeping track of outstanding I/O operations. The size of this area is proportional to the concurrency of the I/O workload.

The home area stores the final version of the contents of the blocks. This implementation introduces a method of localizing shadow block copies to the associated erasure code block, and replicating the log to a minimum set of blocks within the log/shadow area, thereby reducing the write amplification associated with read-modify-write operations of home area blocks. The implementation also integrates the log with the primary storage, so that an external log is not required, which simplifies the system design and eliminates a performance bottleneck.