A method is provided to operate a storage device including a storage controller and a plurality of nonvolatile memory devices. A plurality of original data blocks are received at the storage controller from a host. An original parity block is generated based on the original data blocks. The original data blocks and the original parity block are stored in respective ones of the nonvolatile memory devices, wherein a first original data block of the original data blocks is stored in a first one of the nonvolatile memory devices, and wherein the original parity block is stored in a second one of the nonvolatile memory devices. A new data block corresponding to the first original data block is received at the storage controller from the host after storing the original data blocks and the original parity block. The new data block is stored in the first nonvolatile memory device. A new parity block is generated at the second nonvolatile memory device based on the original parity block and based on differences between the first original data block and the new data block.