In a parity-based redundancy scheme, allocation information indicative of free and allocated portions of storage is accessed. In response to a request for a write operation, when the write request shares its parity with a non-free portion of the storage, a record of writes to the storage is updated to include the requested write and associated parity. The parity is updated with the requested write, and the write request is executed. When the write request shares its parity with a free portion of the storage or the write request spans all portions of storage that shares the parity, the write request is allowed to be executed in the free portion of the storage without updating the record.