Smooth flushing of cached write data
A method of performing write operations that have been received by a data storage apparatus is provided. The method includes (a) storing page descriptors for received write operations within temporary storage, each page descriptor indicating respective data to be written; (b) upon storing each page descriptor, organizing that page descriptor into a shared working-set structure; and (c) operating a plurality of flushers to persist the data indicated by respective page descriptors to long-term persistent storage based on organization of the page descriptors in the shared working-set structure, each flusher accessing page descriptors via the shared working-set structure. An apparatus, system, and computer program product for performing a similar method are also provided.
1. A method of performing write operations that have been received by a data storage apparatus, the method comprising:
storing a plurality of page descriptors for received write operations within temporary storage, each page descriptor of the plurality of page descriptors indicating respective data to be written;
upon storing each page descriptor of the plurality of page descriptors, organizing that page descriptor into a shared working-set structure, the shared working-set structure including a set of leaf structures, each leaf structure referencing a respective set of page descriptors, said organizing including causing a leaf structure to reference a set of related page descriptors; and
operating a plurality of flushers to persist the data indicated by the plurality of page descriptors to long-term persistent storage based on organization of the plurality of page descriptors in the shared working-set structure, each flusher accessing page descriptors of the plurality of page descriptors via the shared working-set structure, said operating the plurality of flushers including operating each of the plurality of flushers to (i) detach a leaf structure from the shared working-set structure and (ii) persist data indicated by the related page descriptors referenced by the detached leaf structure to the long-term persistent storage.
2. The method of claim 1 wherein:
operating each flusher to persist data further includes persisting data to a respective fixed-length storage segment on the long-term persistent storage for that flusher; and
operating the plurality of flushers to persist the data further includes operating each flusher to continue detaching leaf structures and persisting data indicated by related page descriptors referenced by those detached leaf structures to that flusher's fixed-length storage segment until that fixed-length storage segment is full.
3. The method of claim 2 wherein operating each flusher to continue detaching leaf structures and persisting data indicated by related page descriptors referenced by those detached leaf structures to that flusher's fixed-length storage segment until that fixed-length storage segment is full includes, for a last leaf structure detached prior to that fixed-length storage segment becoming full, removing references to page descriptors whose data has been persisted from the last leaf structure and reattaching the last leaf structure to the shared working-set structure.
4. The method of claim 2 wherein operating each flusher to continue detaching leaf structures and persisting data of related page descriptors referenced by those detached leaf structures to that flusher's fixed-length storage segment includes selecting a leaf structure to detach based on a number of page descriptors referenced by that leaf structure and an amount of space left in that fixed-length storage segment.
5. The method of claim 1 wherein:
organizing further includes setting a dependency field of a leaf structure to indicate that it must be processed after another leaf structure; and
operating the plurality of flushers to persist the data further includes operating each flusher to select, for detaching, a leaf structure with an empty dependency field indicating that it need not be processed after any other leaf structure.
6. The method of claim 5 wherein selecting the leaf structure for detaching includes:
preliminarily choosing a test leaf structure to be detached; and
in response to detecting that the test leaf structure includes a set dependency field indicating that it must be processed after another leaf structure, selecting a different leaf structure in place of the test leaf structure that is neither the test leaf structure nor the other leaf structure.
7. The method of claim 5 wherein selecting the leaf structure for detaching includes:
preliminarily choosing a test leaf structure to be detached; and
in response to detecting that the test leaf structure includes a set dependency field indicating that it must be processed after another leaf structure, selecting the other leaf structure in place of the test leaf structure.
8. The method of claim 5 wherein:
organizing further includes setting a reverse dependency field of a leaf structure to indicate that it must be processed before yet another leaf structure; and
operating the plurality of flushers to persist the data further includes operating each flusher to, for a detached leaf structure that includes a set reverse dependency field indicating that it must be processed before a dependent leaf structure, after persisting data indicated by the related page descriptors referenced by the detached leaf structure, unsetting the dependency field of the dependent leaf structure to indicate that it no longer need be processed after the detached leaf structure.
9. The method of claim 1 wherein:
the shared working-set structure includes a hash table; and
organizing that page descriptor into the shared working-set structure further includes hashing a location of that page descriptor and causing a leaf structure in a bucket of the hash table identified by the hashed location to reference that page descriptor.
10. The method of claim 9 wherein:
hashing a location of that page descriptor includes hashing an identifier of a range of logical block addresses, that page descriptor indicating data to be written to a block within the range; and
the leaf structure identified by the hashed location references page descriptors indicating data to be written to blocks within the range of that location.
11. The method of claim 10 wherein organizing further includes, for a page descriptor indicative of a copy operation from a source block at a first logical block address to a destination block at a second logical block address:
creating a new leaf structure, within the shared working-set structure, representing a destination range of logical block addresses that includes the second logical block address; and
setting a dependency field of the new leaf structure to indicate that it must be processed after an existing leaf structure representing a source range of logical block addresses that includes the first logical block address.
12. The method of claim 11 wherein organizing further includes, for the page descriptor indicative of the copy operation from the source block to the destination block:
hashing an identifier of the destination range, yielding a destination hash;
detecting a preexisting leaf structure representing the destination range within a bucket of the hash table identified by the destination hash, the preexisting leaf structure representing writes made to the destination range prior to the copy operation; and
inserting the new leaf structure into the hash table by causing a version pointer of the preexisting leaf structure to point to the new leaf structure.
13. The method of claim 9 wherein:
the shared working-set structure further includes an outer hash table containing entries that represent storage volumes; and
organizing that page descriptor into the shared working-set structure further includes, prior to hashing the location of that page descriptor, hashing a storage volume with which that page descriptor is associated to locate an entry in the outer hash table that represents the storage volume with which that page descriptor is associated.
14. The method of claim 13 wherein:
each entry of the outer table has a respective associated hash table of a plurality of hash tables; and
organizing that page descriptor into the shared working-set structure further includes, prior to hashing the location of that page descriptor:
selecting the hash table from the plurality of hash tables with reference to the located entry in the outer hash table that represents the storage volume with which that page descriptor is associated and
hashing the location of that page descriptor includes hashing an identifier of a range of logical block addresses within the storage volume with which that page descriptor is associated, that page descriptor indicating data to be written to a block within the range.
15. The method of claim 13 wherein organizing further includes, for a page descriptor indicative of a snapshot creation operation for a main storage volume:
creating a new entry in the outer hash table, the new entry representing a snapshot of the main storage volume; and
setting a dependency field of the new entry to indicate that it must be processed after an existing entry in the outer hash table, the existing entry representing writes made to the main storage volume prior to the snapshot operation.
16. The method of claim 15 wherein organizing further includes, for another page descriptor indicative of a write operation to the main storage volume after the snapshot creation operation:
inserting another new entry in the outer hash table by causing a version pointer of the existing entry to point to the other new entry, the other new entry representing writes made to the main storage volume after the snapshot operation;
causing the other new entry to point to the existing entry; and
performing the write operation to the main storage volume with reference to the other new entry.
17. A computer program product comprising a non-transitory computer-readable storage medium storing instructions, which, when performed by a data storage apparatus, cause the data storage apparatus to perform received write operations by:
storing a plurality of page descriptors for the received write operations within temporary storage, each page descriptor of the plurality of page descriptors indicating respective data to be written;
upon storing each page descriptor of the plurality of page descriptors, organizing that page descriptor into a shared working-set structure, the shared working-set structure including a set of leaf structures, each leaf structure referencing a respective set of page descriptors, said organizing including causing a leaf structure to reference a set of related page descriptors; and
operating a plurality of flushers to persist the data indicated by the plurality of page descriptors to long-term persistent storage based on organization of the plurality of page descriptors in the shared working-set structure, each flusher accessing page descriptors of the plurality of page descriptors via the shared working-set structure, said operating the plurality of flushers including operating each of the plurality of flushers to (i) detach a leaf structure from the shared working-set structure and (ii) persist data indicated by the related page descriptors referenced by the detached leaf structure to the long-term persistent storage.
18. A data storage apparatus comprising:
temporary storage;
long-term persistent storage; and
processing circuitry coupled to memory configured to perform received write operations by:
storing a plurality of page descriptors for the received write operations within the temporary storage, each page descriptor of the plurality of page descriptors indicating respective data to be written;
upon storing each page descriptor of the plurality of page descriptors, organizing that page descriptor into a shared working-set structure, the shared working-set structure including a set of leaf structures, each leaf structure referencing a respective set of page descriptors, said organizing including causing a leaf structure to reference a set of related page descriptors; and
operating a plurality of flushers to persist the data indicated by the plurality of page descriptors to the long-term persistent storage based on organization of the page descriptors in the shared working-set structure, each flusher accessing page descriptors of the plurality of page descriptors via the shared working-set structure, said operating the plurality of flushers including operating each of the plurality of flushers to (i) detach a leaf structure from the shared working-set structure and (ii) persist data indicated by the related page descriptors referenced by the detached leaf structure to the long-term persistent storage.