US9946489B2 - Multi-stream journaled replay - Google Patents

Abstract

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.

Description

BACKGROUND

The present disclosure concerns flash storage devices and, more particularly, restoring an indirection system for flash storage devices.

An indirection system for flash storage devices keeps track of the physical location on the flash memory device for each host accessible logical block address (LBA). After the flash storage device loses power and boots again when power is restored, the indirection system is restored to the state the indirection system had before the power loss, a process known as indirection replay or replay. Indirection replay often utilizes a combination of snapshots of the indirection system as a whole, with a journal of new writes or write deltas logged alongside user data. However, snapshot-based replay may increase firmware complexity, as synchronization between snapshots and journaling must be managed. Run-time performance may suffer due to the resources required for snapshots. Boot-time performance may also suffer when replaying using a snapshot.

SUMMARY

The subject technology avoids using a snapshot for replay. The entire flash storage device is replayed from write deltas. The subject technology further allows snapshot-less replay in a multiple-stream system.

According to aspects of the subject technology, a method for replaying a flash storage device is provided. The method includes writing data, in a primary stream, to a first plurality of blocksets of a storage device. The method includes 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. The method further includes writing a respective indirection journal to each of the first plurality of blocksets, wherein the respective indirection journal corresponds to the data written (e.g. write deltas) to the respective blockset and is associated with the respective major sequence number assigned to the respective blockset. The method also includes writing data, in a secondary stream operating concurrently with the primary stream, to a second plurality of blocksets of the storage device. The method includes 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. The method further includes 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. The method also includes 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.

According to aspects of the subject technology, a flash storage device is provided. The flash storage device includes a memory, a plurality of flash memory devices, and a controller. The flash memory devices each contain memory cells divided into blocks, and the plurality of flash memory devices are organized into blocksets by combining blocks from each flash memory device. The controller is configured to write data, in a host stream, to a first plurality of blocksets of the flash storage system. The controller is configured to 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. The controller is further configured to 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. The controller is also configured to write data, in a garbage collection stream operating concurrently with the primary stream, to a second plurality of blocksets of the flash storage system. The controller is configured to 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. The controller is further configured to 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. The controller is also configured to 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.

According to aspects of the subject technology, a machine-readable media encoded with executable instructions is provided. The instructions, when executed by a processor, cause the processor to perform operations. The operations include writing data, in a primary stream, to a first plurality of blocksets of a storage device. The operations include 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. The operations also include 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. The operations further include writing data, in a secondary stream operating concurrently with the primary stream, to a second plurality of blocksets of the storage device. The operations include 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. The operations also include 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. The operations include 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.

It is understood that other configurations of the subject technology will become readily apparent to those skilled in the art from the following detailed description, wherein various configurations of the subject technology are shown and described by way of illustration. As will be realized, the subject technology is capable of other and different configurations and its several details are capable of modification in various other respects, all without departing from the scope of the subject technology. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram illustrating components of a flash storage device according to aspects of the subject technology.

FIG. 2A is a diagram of blockset identifiers (ID) for a primary stream and a secondary stream according to aspects of the subject technology.

FIG. 2B shows blockset IDs with corresponding major/minor sequence numbers for the blocksets ofFIG. 2A.

FIG. 3 is a diagram of a journal according to aspects of the subject technology.

FIG. 4 is a flowchart illustrating a method for replay for a flash storage system according to aspects of the subject technology.

DETAILED DESCRIPTION

The detailed description set forth below is intended as a description of various configurations of the subject technology and is not intended to represent the only configurations in which the subject technology may be practiced. The appended drawings are incorporated herein and constitute a part of the detailed description. The detailed description includes specific details for the purpose of providing a thorough understanding of the subject technology. However, it will be apparent to those skilled in the art that the subject technology may be practiced without these specific details. In some instances, well-known structures and components are shown in block diagram form in order to avoid obscuring the concepts of the subject technology.

FIG. 1 is a block diagram illustrating components of aflash storage system110 according to aspects of the subject technology. As depicted inFIG. 1, theflash storage system110 includesinterface115,controller120,memory125, andflash memory devices130A-130N. Theinterface115 facilitates communication of data, commands, and/or control signals betweenflash storage system110 andhost150. Thecontroller120 controls the operation of theflash storage system110 to store and retrieve data in one of the flash memory devices130 in accordance with commands received from thehost150. Thememory125, which may be a random access memory (RAM), provides temporary storage space for thecontroller120 to process commands and transfer data between thehost150 and theflash memory devices130A-130N. The operation of each of these components is described in more detail below.

Theinterface115 provides a physical and electrical connection between thehost150 and theflash storage system110. Theinterface115 is configured to facilitate communication of data, commands, and/or control signals between thehost150 and theflash storage system110 via the physical and electrical connection. The connection and the communications with theinterface115 may be based on a standard interface such as Universal Serial Bus (USB), Small Computer System Interface (SCSI), Serial Advanced Technology Attachment (SATA), etc. Alternatively, the connection and/or communications may be based on a proprietary interface. The subject technology is not limited to any particular type of interface.

Thecontroller120 manages the flow of data between thehost150 and theflash memory devices130A-130N. Thecontroller120 is coupled to theinterface115 and is configured to receive commands and data from thehost150 via theinterface115. For example, thecontroller120 may receive data and a write command from thehost150 to write the data in one or more flash memory devices130. Thecontroller120 is further configured to send data to the host system via theinterface115. For example, thecontroller120 may read data from a flash memory device130 and send the data to thehost150 in response to a read command. Thecontroller120 is further configured to manage data stored in theflash memory devices130A-130N and thememory125 based on internal control algorithms or other types of commands that may be received from thehost150. Other maintenance operations may be performed by thecontroller120 in theflash storage system110.

Thecontroller120 may be implemented with a general purpose processor, micro-controller, digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic device, discrete hardware components, or any combination thereof designed and configured to perform the operations and functions described herein. Thecontroller120 may perform the operations and functions described herein by executing one or more sequences of instructions stored on a machine/computer readable medium. The machine/computer readable medium may be a flash memory device130, thememory125, or other types of readable media from which thecontroller120 can read instructions or code. For example, theflash storage system110 may include a read only memory (ROM), such as an EPROM or EEPROM, encoded with firmware/software comprising one or more sequences of instructions read and executed by thecontroller120 during the operation of theflash storage system110.

Theflash memory devices130A-130N may all be located on a single flash chip or arranged on multiple flash chips. The flash memory devices may be split among multiple channels through which data is read from and written to the flash memory devices by thecontroller120, or coupled to a single channel. The flash memory devices130 may be implemented using NAND flash.

A flash memory device130 comprises multiple memory cells divided into storage blocks, such as flash memory blocks140. These storage blocks may be referred to as data blocks or memory blocks and are addressable by thecontroller120 using a physical block address. Each of the storage blocks is further divided into multiple data segments or pages addressable by thecontroller120 using a physical page address or offset from a physical block address of the storage block containing the referenced page. The storage blocks represent the units of data that are erased within a flash memory device130 in a single erase operation. The physical pages represent the units of data that are read from or written to a flash memory device130 in a single read or write operation. The flash memory blocks140 similarly located across the flash memory devices130, such as the flash memory blocks140A-1 to140N-1, may be grouped together as ablockset145. Each flash memory device130 also comprises a register135, which may be used to store, for instance, counters and other data related to the corresponding flash memory device130.

The subject technology is not limited to any particular capacity of flash memory. For example, storage blocks in flash memory25 may each comprise 32, 64, or 128 pages. Additionally, pages in flash memory25 may each comprise 512 bytes, 2 kilobytes, or 4 kilobytes.

Thememory125 represents a volatile memory coupled to and used by thecontroller120 during operation of theflash storage system110. Thecontroller120 may buffer commands and/or data in thememory125. Thecontroller120 also may use thememory125 to store an indirection system, such as address translation tables used to convert logical data addresses used by thehost150 into virtual and/or physical addresses corresponding to portions of theflash memory devices130A-130N. Other types of tables, data, status indicators, etc. conventionally used to manage flash storage systems also may be stored in thememory125 by thecontroller120. Thememory125 may be implemented using dynamic random access memory (DRAM), static random access memory (SRAM), or other types of volatile random access memory known to those skilled in the art without departing from the scope of the subject technology.

When theflash storage system110 loses power, for example because of a power failure or shutting down theflash storage system110, the state of the indirection system may be lost. Once power is restored to the flash storage system, the indirection system must be restored to the state of the indirection system before the power loss. The use of snapshots may be avoided in journal-based replay. For each write operation, a journal is logged describing changes to the mapping of virtual to physical addresses. Replaying the journal in sequential order from the first journal will rebuild the indirection system. In a single stream system, wherein only one blockset is opened and written to at a time, sequential numbering of blocksets ensures that the journals will be replayed in the correct order.

The blocksets store corresponding journals. This in-line journaling bounds the number of journals written to the storage device. In-line journal also naturally expires journals that are no longer needed, because the journals are erased when the blockset is erased. Replaying in the correct order would require replaying the journals in the order of blocksets written. However, in multiple stream systems, wherein more than one stream operate concurrently such that more than one blockset can be open at a time, a simple sequential numbering may introduce coherency errors.

For example, a host stream may open a first blockset while a garbage collection (GC) stream opens a second blockset. GC refers to the process of freeing up a block by moving valid data from the block to another block and erasing the block. It is possible that a newer version of mapping is written to a blockset in the GC stream. The correct replay sequence would depend on which blockset is closed first, so that an older mapping (based on an older journal) is not replayed after a newer mapping (based on a newer journal). However, because the sequential number is assigned as a blockset is opened, and the order of blockset closing is not predictable, the simple sequential numbering may produce errors during replay. An older mapping may end up replacing a newer mapping during replay.

FIG. 2A shows sequences of blocksets being opened and closed for two streams, aprimary stream210 and asecondary stream220. Theprimary stream210 includesblocksets201,204,206, and203. Thesecondary stream220 includesblocksets207,202, and205. The lengths of the blocksets correspond to opening and closing times. For example, theblockset207 is opened after theblockset201 is closed and whileblockset204 is open. In other words, two blocksets are open for writing data at the same time. The blocksets may be closed when the blockset is no longer able to be written to, such as if there is no free space, or after a predetermined period of time, such that the blockset is not open indefinitely. Theprimary stream210 may correspond to a host stream, such thatblocksets201,204,206, and203 are opened and closed for host operations. Thesecondary stream220 may correspond to a garbage collection (GC) stream, such thatblocksets207,202, and205 are opened and closed for GC operations.

According to aspects, each blockset is assigned a sequence number when the blockset is opened. The sequence number for a host blockset includes a major sequence number. The sequence number for a GC blockset includes a major-minor sequence number, which includes a major sequence number component and a minor sequence number component. The major sequence number is used to order the host blocksets. The minor sequence number is used to order the GC blocksets. When assigning sequence numbers to host blocksets, the last closed host blockset major sequence number is incremented and assigned to the current host blockset. Minor sequence numbers are not needed for the host blocksets and therefore may be 0 or NULL.

For the GC stream, the major sequence number for the GC blocksets are set to the last closed host blockset major sequence number. The minor sequence number, which may start at 1, is used to number the GC blocksets having the same major sequence number. In other words, until the last closed host blockset changes, the GC blocksets will have the same major sequence number, with different minor sequence numbers. Moreover, when selecting blocksets for the GC stream, blocksets having a major sequence number higher than the major sequence number in the current GC blockset are excluded.

FIG. 2B shows ordered blockset ID blocks for the blocksets inFIG. 2A. As seen inFIG. 2A, theprimary stream210 first opens theblockset201. Theblockset201 is assigned a major number of 1000, and a stream type of host. The minor sequence number is NULL. Theblockset201 is then closed and theblockset204 is opened. Since the last closed blockset—theblockset201—had the major sequence number of 1000, theblockset204 is assigned the next major sequence number, 1001. The minor sequence number is NULL, and the stream type is host.

After theblockset204 is opened, theblockset207 is opened in thesecondary stream220. The last closed host blockset is theblockset201, because theblockset204 is still open. Theblockset201 has a major sequence number of 1000, which is also used for the major sequence number of theblockset207. Theblockset207 is assigned a minor sequence number of 1, being the first GC blockset with the major sequence number of 1000. The stream type is set to GC.

Thesecondary stream220 closes theblockset207 and opens theblockset202 while theblockset204 is still open. The last closed host blockset is still theblockset201, therefore theblockset202 is assigned themajor sequence number 1000. The minor sequence number for theblockset202 is incremented from the previous minor sequence number and therefore set to 2. The stream type is GC.

While theblockset202 is still open, theprimary stream210 closes theblockset204 and opens theblockset206. The last closed host blockset is now theblockset204, thus the major sequence number for theblockset206 is1002 (e.g. incremented from the major sequence number of the blockset204). The minor sequence number is NULL, and the stream type is host.

While theblockset206 is still open, thesecondary stream220 closes theblockset202 and opens theblockset205. The last closed host blockset is theblockset204, thus the major sequence number for theblockset205 is 1001 (e.g. the same major sequence number of the blockset204). The minor sequence number is set to 1, and the stream type is GC.

Theprimary stream210 closes theblockset206 and opens theblockset203. Theblockset203 is assigned a major sequence number of1003 (e.g. incremented from the major sequence number of the blockset206). The minor sequence number is NULL, and the stream type is host.

FIG. 3 shows a diagram of a journal which may be saved to a blockset. The journal includes aheader301, afooter302, and a series of logical block numbers (LBN)307 pairings with virtual-to-physical (V2P)entries308. The LBN corresponds to the logical block address and the V2P corresponds to the physical address. TheLBN307 andV2P308 pairings describe the changes to the indirection system as a result of the corresponding write operation. Theheader301 includes ablockset sequence number303,journal entry number304,open timestamp305, andstream number306. Thefooter302 includes theblockset sequence number303 and thejournal entry number304. Theblockset sequence number303 includes the major sequence number and the minor sequence number. The journal entry number corresponds to an indexing for journal entries. Theopen timestamp305 corresponds to when the blockset was opened. Thestream number306 identifies the stream which opened the blockset.

FIG. 4 is a flowchart illustrating a method for managingflash storage system110 according to aspects of the subject technology. The method may be performed bycontroller120 reading and executing one or more sequences of instructions from a medium encoded with the instructions. The method begins oncecontroller120 has completed any start-up tasks and housekeeping procedures required onceflash storage device110 has been powered up or operation interrupted for maintenance purposes and a write request has been received. The write request may be based on a command received fromhost150 viainterface115. Alternatively, the write request may be generated by an internal process, such as a maintenance process, executed bycontroller120. Upon receiving a write request,controller120 initiates the write request. Initiating the write request may include determining which blocksets to write to. Once the write request has been initiated, the process starts atblock410.

Atblock410, data, in a primary stream, is written to a first plurality of blocksets of a storage device. The primary stream may be a host stream, for example, for writing host data to one or more blocksets145. The one or more blocksets145 may be selected by thecontroller120 based on blocksets needed for the write operation and factors for storage device management. Theblocksets145 may be selected and queued, or may be selected when anext blockset145 is needed, such as after ablockset145 is closed. The primary stream may have oneblockset145 open at a time.

Atblock420, a major sequence number is assigned to each blockset of the first plurality of blocksets. The major sequence number is incremented from a previous major sequence number assigned to a most recently closed blockset of the first plurality of blocksets. When ablockset145 is opened for the primary stream, thecontroller120 determines the major sequence number of the most recentlyclosed blockset145. The major sequence number of the most recently closed blockset is then incremented by one to determine the current major sequence number. The current major sequence number is assigned to the currentlyopen blockset145. In certain implementations, the major sequence number may be tracked with a counter, which increments as a blockset is opened. In such implementations, there may be more than one primary stream opening and closing blocksets. The counter prevents a secondopen blockset145 having the same major number as the firstopen blockset145.

The major sequence number is assigned to a blockset when the blockset is opened in order to correctly steer write operations while the stream is open. For example, if twoblocksets145 were open but did not have major sequence numbers already assigned, the order of replay for theseblocksets145 would be undefined. In addition, certain runtime data steering decisions rely on knowing the major sequence number for each open blockset. However, in certain implementations, the major sequence number may be assigned when the blockset is closed.

Atblock430, an indirection journal is written to each of the first plurality of blocksets. The indirection journal corresponds to the data written to the blockset and is associated with the major sequence number assigned to the respective blockset. The indirection journal is written to each blockset145 as theblockset145 is updated. One or more indirection journals may be written to a block140 of theblockset145. A directory may be written to, for example, the last block140 of theblockset145, which keeps track of the indirection journals. Thus, the indirection journals may be scattered across theblockset145. In addition, the indirection journals may be written to specific locations, such as a page after the last page of the logical stripe.

Atblock440, data, in a secondary stream operating concurrently with the primary stream, is written to a second plurality of blocksets. The secondary stream may be a garbage collection stream or other maintenance stream. The blocksets may be selected and queued, or may be selected as the previous blockset is closed. For example, the GC stream may select ablockset145 for a GC operation. However, the GC stream will exclude blocksets having major sequence numbers greater than the current GC major sequence number.

Atblock450, major-minor sequence numbers are assigned to each blockset of the second plurality of blocksets. The 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 minor sequence number incremented from a most recently closed blockset in the second plurality of blocksets. In certain implementations, such as systems with multiple host streams, the oldest host major sequence number across all host streams is used for the GC major sequence number.

Atblock460, an indirection journal is written to each of the second plurality of blocksets. The 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. The journal is written to thecorresponding blockset145 as theblockset145 is updated, similar to block430 described above.

Atblock470, an indirection table is constructed 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.Block470 may occur during a boot sequence for theflash storage system110. For example, theflash storage system110 may have lost power or may have been shut down and subsequently powered on again.

Theblocksets145 of theflash storage system110 having journals are identified. Thecontroller120 may identify which of theblocksets145 have valid data, and determine the major or major-minor sequence numbers of theblocksets145 having valid data. In certain implementations, thecontroller120 may maintain a persistent list ofblocksets145 and the corresponding major or major-minor sequence numbers. In certain other implementations, eachblockset145 may maintain an identifier or link to thenext blockset145 in the associated stream, for example by storing, when a blockset is closed, an identifier to the next blockset being opened in the stream.

Theblocksets145 having journals are ordered according to respective major sequence numbers first.Blocksets145 having the same major sequence number are then ordered by minor sequence number, with 0 or NULL being first. Replay occurs by replaying the journals from theblocksets145 in this order of blocksets.

Alternatively, theblocksets145 having journals may be separated into two lists, a host list and a GC list. The host list includesblocksets145 designated as host type, and the GC list includesblocksets145 designated as GC type. The blocksets of the host list are sorted by major sequence number. The blocksets of the GC list are sorted first by major sequence number, and then by minor sequence number.

Replay starts with the oldest sequence number, which may be from either the host list or the GC list. When replaying host blocksets, the journals of the blocksets are replayed until a host blockset is replayed having a major sequence number matching a major sequence number of a GC blockset at the head of the GC list (e.g. the oldest GC blockset that has not been replayed). After this host blockset is replayed, the GC blocksets are replayed, starting with the head of the GC list.

The current GC major sequence number corresponds to the head of the GC list. The GC blocksets are replayed until all GC blocksets having the same major sequence number as the current GC major sequence number are replayed. Then, the next host blocklist is replayed. Replay switches between the host list and the GC list until all blocksets have been replayed.

Those of skill in the art would appreciate that the various illustrative blocks, modules, elements, components, methods, and algorithms described herein may be implemented as electronic hardware, computer software, or combinations of both. To illustrate this interchangeability of hardware and software, various illustrative blocks, modules, elements, components, methods, and algorithms have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application. Various components and blocks may be arranged differently (e.g., arranged in a different order, or partitioned in a different way) all without departing from the scope of the subject technology.

It is understood that the specific order or hierarchy of steps in the processes disclosed is an illustration of exemplary approaches. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the processes may be rearranged. Some of the steps may be performed simultaneously. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented.

The previous description is provided to enable any person skilled in the art to practice the various aspects described herein. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects. Thus, the claims are not intended to be limited to the aspects shown herein, but is to be accorded the full scope consistent with the language claims, wherein reference to an element in the singular is not intended to mean “one and only one” unless specifically so stated, but rather “one or more.” Unless specifically stated otherwise, the term “some” refers to one or more. Pronouns in the masculine (e.g., his) include the feminine and neuter gender (e.g., her and its) and vice versa. Headings and subheadings, if any, are used for convenience only and do not limit the invention.

A phrase such as an “aspect” does not imply that such aspect is essential to the subject technology or that such aspect applies to all configurations of the subject technology. A disclosure relating to an aspect may apply to all configurations, or one or more configurations. A phrase such as an aspect may refer to one or more aspects and vice versa. A phrase such as a “configuration” does not imply that such configuration is essential to the subject technology or that such configuration applies to all configurations of the subject technology. A disclosure relating to a configuration may apply to all configurations, or one or more configurations. A phrase such a configuration may refer to one or more configurations and vice versa.

The word “exemplary” is used herein to mean “serving as an example or illustration.” Any aspect or design described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects or designs.

All structural and functional equivalents to the elements of the various aspects described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the claims. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the claims. No claim element is to be construed under the provisions of 35 U.S.C. §112, sixth paragraph, unless the element is expressly recited using the phrase “means for” or, in the case of a method claim, the element is recited using the phrase “step for.” Furthermore, to the extent that the term “include,” “have,” or the like is used in the description or the claims, such term is intended to be inclusive in a manner similar to the term “comprise” as “comprise” is interpreted when employed as a transitional word in a claim.

Claims (20)

What is claimed is:

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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 1, wherein the primary stream corresponds to a host stream, and the secondary stream corresponds to a garbage collection stream.

10. The method ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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.

Images