Multi-stream journaled replay
A method of indirection replay for a flash storage system includes writing data, in a host stream, to blocksets of the flash storage system. The host blocksets are assigned a major sequence number incremented from the most recently closed host blockset. The method includes writing an indirection journal to each host blockset which are associated with the assigned major sequence number. The method includes writing data, in a garbage collection (GC) stream, to other blocksets of the flash storage system. The GC blocksets are assigned a major sequence number, based on the most recently closed host blockset, and a minor sequence number, incremented from the most recently closed GC blockset. The method includes writing an indirection journal to each GC blockset which are associated with the assigned major and minor sequence numbers. The indirection table is constructed by replaying the journals of the blocksets in order of major sequence and minor sequence numbers.
1. A method comprising:
writing data, in a primary stream, to a first plurality of blocksets of a storage device;
assigning a respective major sequence number to each blockset of the first plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first plurality of blocksets;
writing a respective indirection journal to each of the first plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major sequence number assigned to the respective blockset;
writing data, in a secondary stream operating concurrently with the primary stream, to a second plurality of blocksets of the storage device;
assigning respective major-minor sequence numbers to each blockset of the second plurality of blocksets, wherein the respective major-minor sequence numbers comprise the previous major sequence number assigned to the most recently closed blockset of the first plurality of blocksets and a respective minor sequence number incremented from a most recently closed blockset in the second plurality of blocksets;
writing a respective indirection journal to each of the second plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major-minor sequence numbers assigned to the respective blockset; and
constructing an indirection table in a memory of the storage device by replaying the indirection journals from the first and second pluralities of blocksets ordered first according to respective major sequence numbers and second according to respective minor sequence numbers.
2. The method of claim 1 , wherein constructing the indirection table further comprises:
ordering the first plurality of blocksets according to respective major sequence numbers;
ordering the second plurality of blocksets according to respective major sequence numbers; and
ordering blocksets of the second plurality of blocksets having a same major sequence number according to respective minor sequence numbers.
3. The method of claim 2 , wherein constructing the indirection table further comprises:
replaying the indirection journals from each blockset of the ordered first plurality of blocksets until a major sequence number of a replayed blockset matches an oldest major sequence number in the ordered second plurality of blocksets; and
replaying the indirection journals from each blockset of the ordered second plurality of blocksets until all blocksets having a major sequence number matching the oldest major sequence number have been replayed.
4. The method of claim 1 , wherein constructing the indirection table further comprises:
combining the first plurality of blocksets and the second plurality of blocksets into a third plurality of blocksets;
ordering the third plurality of blocksets according to respective major sequence numbers;
ordering blocksets of the second plurality of blocksets having a same major sequence number according to respective minor sequence numbers; and
replaying the indirection journals from each blockset of the ordered third plurality of blocksets.
5. The method of claim 1 , further comprising:
writing data, in a second primary stream operating concurrently with the primary stream, to a third plurality of blocksets of the storage device;
assigning a respective major sequence number to each blockset of the third plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first or third pluralities of blocksets; and
writing a respective indirection journal to each of the third plurality of blocksets.
6. The method of claim 5 , wherein the major-minor sequence numbers comprise the previous major sequence number assigned to the most recently closed blockset of the first or third pluralities of blocksets.
7. The method of claim 5 , wherein the major-minor sequence numbers comprise the previous major sequence number assigned to an older blockset between the most recently closed blockset of the first plurality of blocksets and the most recently closed blockset of the third plurality of blocksets.
8. The method of claim 5 , wherein the primary stream corresponds to a host stream, the second primary stream corresponds to a second host stream, and the secondary stream corresponds to a garbage collection stream.
9. The method of claim 1 , wherein the primary stream corresponds to a host stream, and the secondary stream corresponds to a garbage collection stream.
10. The method of claim 9 , wherein the garbage collection stream selects blocksets, for the second plurality of blocksets, having respective major sequence numbers less than the major sequence number of the assigned major-minor sequence numbers.
11. The method of claim 1 , wherein constructing the indirection table is performed in response to booting the storage device.
12. A flash storage system, comprising:
a memory;
a plurality of flash memory devices; and
a controller configured to:
write data, in a host stream, to a first plurality of blocksets of the flash storage system;
assign a respective major sequence number to each blockset of the first plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first plurality of blocksets;
write a respective indirection journal to each of the first plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major sequence number assigned to the respective blockset;
write data, in a garbage collection stream operating concurrently with the host stream, to a second plurality of blocksets of the flash storage system;
assign respective major-minor sequence numbers to each blockset of the second plurality of blocksets, wherein the respective major-minor sequence numbers comprise the previous major sequence number assigned to the most recently closed blockset of the first plurality of blocksets and a respective minor sequence number incremented from a most recently closed blockset in the second plurality of blocksets;
write a respective indirection journal to each of the second plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major-minor sequence numbers assigned to the respective blockset; and
construct an indirection table in the memory by replaying the indirection journals from the first and second pluralities of blocksets ordered first according to respective major sequence numbers and second according to respective minor sequence numbers.
13. The flash storage system of claim 12 , wherein the controller is further configured to:
order the first plurality of blocksets according to respective major sequence numbers;
order the second plurality of blocksets according to respective major sequence numbers; and
order blocksets of the second plurality of blocksets having a same major sequence number according to respective minor sequence numbers
replay the indirection journals from each blockset of the ordered first plurality of blocksets until a major sequence number of a replayed blockset matches an oldest major sequence number in the ordered second plurality of blocksets; and
replay the indirection journals from each blockset of the ordered second plurality of blocksets until all blocksets having a major sequence number matching the oldest major sequence number have been replayed.
14. The flash storage system of claim 12 , wherein the controller is further configured to:
combine the first plurality of blocksets and the second plurality of blocksets into a third plurality of blocksets;
order the third plurality of blocksets according to respective major sequence numbers;
order blocksets of the second plurality of blocksets having a same major sequence number according to respective minor sequence numbers; and
replay the indirection journals from each blockset of the ordered third plurality of blocksets.
15. The flash storage system of claim 12 , wherein the controller is further configured to:
write data, in a second host stream operating concurrently with the host stream, to a third plurality of blocksets of the flash storage system;
assign a respective major sequence number to each blockset of the third plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first or third pluralities of blocksets; and
write a respective indirection journal to each of the third plurality of blocksets.
16. The flash storage system of claim 12 , wherein constructing the indirection table is performed in response to booting the storage device.
17. A machine-readable non-transitory media encoded with executable instructions which, when executed by a processor, cause the processor to perform operations comprising:
writing data, in a primary stream, to a first plurality of blocksets of a storage device;
assigning a respective major sequence number to each blockset of the first plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first plurality of blocksets;
writing a respective indirection journal to each of the first plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major sequence number assigned to the respective blockset;
writing data, in a secondary stream operating concurrently with the primary stream, to a second plurality of blocksets of the storage device;
assigning respective major-minor sequence numbers to each blockset of the second plurality of blocksets, wherein the respective major-minor sequence numbers comprise the previous major sequence number assigned to the most recently closed blockset of the first plurality of blocksets and a respective minor sequence number incremented from a most recently closed blockset in the second plurality of blocksets;
writing a respective indirection journal to each of the second plurality of blocksets, wherein the respective indirection journal corresponds to the data written to the respective blockset and is associated with the respective major-minor sequence numbers assigned to the respective blockset; and
constructing an indirection table in a memory of the storage device by replaying the indirection journals from the first and second pluralities of blocksets ordered first according to respective major sequence numbers and second according to respective minor sequence numbers.
18. The machine-readable non-transitory media of claim 17 , wherein the operations further comprise:
writing data, in a second primary stream operating concurrently with the primary stream, to a third plurality of blocksets of the storage device;
assigning a respective major sequence number to each blockset of the third plurality of blocksets, wherein the respective major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first or third pluralities of blocksets; and
writing a respective indirection journal to each of the third plurality of blocksets.
19. The machine-readable non-transitory media of claim 18 , wherein the major-minor sequence numbers comprise the previous major sequence number assigned to an older blockset between the most recently closed blockset of the first plurality of blocksets and the most recently closed blockset of the third plurality of blocksets.
20. The machine-readable non-transitory media of claim 18 , wherein the primary stream corresponds to a host stream, the second primary stream corresponds to a second host stream, and the secondary stream corresponds to a garbage collection stream.