Memory efficient triggers of read disturb checks in solid state storage

An indication is received that a word line has been read. The word line is part of a plurality of word lines (in solid state storage) which is divided into a plurality of groups. It is determined which group is associated with the read. A count of consecutive, at least potentially uninformative reads is updated based at least in part on the group associated with the read and a group associated with a prior read. It is determining if the count is greater than a threshold and in the event it is determined the count is greater than the threshold, a read disturb check is triggered.

BACKGROUND OF THE INVENTION

Read disturb occurs when a read is performed on a word line in solid state storage. Cells on word lines (other than the one being read) may have a small amount of charge inadvertently added to them during the read; typically, cells storing the lowest voltages in unread word lines are affected the most.

One technique to mitigate read disturb is to have a counter for each word line which counts the number of reads since the last P/E cycle. As such, they are incremented with each read, and reset when the block is erased and re-written. These counters have a number of drawbacks associated with them. A first issue is size. Typically, the size of these counters is relatively large, for example 20 bits per counter. If there are 64,000 blocks and there is a counter per block, then this is over 1 MB of information which must be stored. This amount of overhead information is undesirable. A second issue is the type of storage in which these counters must be stored. The counts have to be preserved even if the system is power cycled, so non-volatile storage must be used. In some cases, this means periodically “flushing” the current counts from volatile storage to non-volatile storage. Even if a power down is indicated beforehand, there may not be enough time to flush the current counts to non-volatile storage (e.g., because the system has a maximum power down time). Finally, as a result of variations in manufacturing processing, some solid state storage devices are more durable than others. P/E counters do not take manufacturing variations into account. New techniques related to read disturb which address some or all of these issues would be desirable.

DETAILED DESCRIPTION

FIG. 1is a diagram showing an embodiment of word lines in solid state storage. In the example shown, there are 4 word lines and 4 bit lines (i.e., there are 16 cells total) and word line2(100) is being read. For clarity, a relatively small number of word lines and bit lines are shown in this and other examples. Naturally, the techniques described herein are applicable to any number of cells, word lines, bit lines, etc.

Word lines which are not being read are set to a pass voltage (Vpass). As such, word lines1and3-4(102a-102c) are set to Vpasssince they are not being read. Vpassmust be greater than the largest possible voltage written to the floating gate of any cell in the array. The word line which is being read (in this example, word line100) is set to an appropriate read threshold, Vref. Some read threshold examples are described in more detail below.

Read disturb occurs when electrons are inadvertently added to the floating gate of a cell during a read. This occurs because electrons “jump” to the floating gate voltage of a cell; the likelihood or ease of a jump tends to increase with the difference between the applied voltage (e.g., Vpass) and the voltage stored by the cell. As such, read disturb tends to victimize cells in word lines which are not being read (e.g., because cells in unread word lines have the highest voltages applied) and which store the lowest voltages because such cells have the largest voltage differences.

In examples described herein, cells are multi-level cells (MLC) which store 2 bits per cell. The following figure shows an example of an MLC histogram of voltage levels.

FIG. 2is a diagram showing an embodiment of an MLC histogram of voltage levels stored by a group of cells. In the example shown, read threshold200a-200bare most significant bit (MSB) read thresholds and read threshold202is a least significant bit (LSB) read threshold because they (respectively) are used to read back the MSB and LSB values. Cells which store a voltage below read threshold200aare interpreted or read back as having an LSB of 1 and an MSB of 1. Cells which store a voltage between read thresholds200aand202are interpreted or read back as having an LSB of 1 and an MSB of 0. Cells which store a voltage between read thresholds202and200bare interpreted or read back as having an LSB of 0 and an MSB of 0. Cells which store a voltage greater than read threshold200bare interpreted or read back as having an LSB of 0 and an MSB of 1. Note that the LSB/MSB assignments shown herein are merely exemplary; any LSB/MSB assignment may be used (e.g., the MSB may have a single read threshold and the LSB may have two read thresholds).

For MLC cells, a read of a word line is either an MSB read or an LSB read. Returning toFIG. 1, if an MSB read is being performed on word line100then two reads are performed: one at Vref=VA(i.e., read threshold200ainFIG. 2) and one at Vref=VC(i.e., read threshold200binFIG. 2) in order to obtain the MSB values of cells in word line100. Note that the two reads may be performed in any order and/or this process of reading twice may be internal to the NAND. If an LSB read is performed on word line100, then a single read at Vref=VB(i.e., read threshold202inFIG. 2) is performed in order to obtain the LSB values of cells in word line100.

Returning toFIG. 2, read disturb tends to affect those cells storing the lowest voltages, which in this case are the cells storing a 11. See read disturb region204which corresponds to cells storing the lowest voltages. As was described above, read disturb tends to affect cells storing the lowest voltages (in this case, a 11) because it is easier for an electron to make the jump to a floating gate of a cell if the difference between the applied voltage (e.g., Vpass) and the stored voltage (e.g., in the range [0, VA] for cells storing a 11) is greater. Cells storing a 11 which are not being read will have the greatest voltage difference and thus will have the most additional voltage added to it because of read disturb.

In some embodiments, information stored in a word line is error correction encoded. The following figure shows an example of error correction decoding performed on information read back from a word line.

FIG. 3is a diagram showing an embodiment of data from an MSB page and an LSB page which are error correction decoded.FIG. 3continues the example ofFIG. 1, so the length of a word line is 4 bits long. A word line refers to a (e.g., physical) group of cells. In MLC, 2 bits of information are written to the cells and those groups of bits are termed the LSB page and MSB page. The word line consists of both bits (i.e., the MSB(s) and LSB(s)) which are written to the (i.e., same) physical cells.

Diagram310shows an MSB example. In that example, an MSB read is performed which returns an MSB page (e.g., word line100inFIG. 1is read twice: once with Vref=VAand again with Vref=VC). Read back bits300a-300ccorrespond to an MSB payload portion and read back bit300dcorresponds to an MSB parity portion. After error correction decoding, a corrected bit sequence is produced comprising bits302a-302d. Corrected bits302a-302band302dmatch their corresponding read back bits (i.e., those bits did not have to be “flipped” during error correction decoding) but bit302cis corrected or flipped (i.e., read back bit300cand corrected bit302care opposite values).

Diagram360shows an LSB example. If an LSB read is performed on word line100inFIG. 1(e.g., a single read with Vref=VB) then an LSB page is returned. As in the MSB example, read back bits350a-350ccorrespond to an LSB payload portion and read back bit350dcorresponds to an LSB parity portion. After error correction decoding, none of the bits had to be corrected or flipped (352a-352c).

One read disturb detection technique “piggybacks” off of normal or operational reads (e.g., initiated by a host or driver). To summarize this read disturb detection technique, if the number of corrected bits (e.g., ncorrected=1 in diagram310and ncorrected=0 in diagram360) exceeds some threshold, then according to that technique, that page or word line probably has too much read disturb and the data in that page or word line is moved to another page or word line.

The problem with the read disturb detection technique described above is that not all types of reads are informative about read disturb. For example, an LSB read is not an informative read with respect to read disturb. Looking atFIG. 2, read disturb204affects cells storing a 11. The cells in read disturb204are nowhere near the voltage level of read threshold202, which is the read threshold used during an LSB read. As such, read disturb will not contribute significantly to LSB errors and using the number of corrected LSB bits is not informative with respect to the amount of read disturb.

Another type of read which is not informative is when the same word line is read over and over, even if an MSB read is being performed. For example, suppose an MSB read is being performed over and over on word line100inFIG. 1. Since the word line being read (word line100in this example) is not affected by read disturb and the word lines which are not being read are the victims (word lines102a-102cin this example), using the number of corrected bits from reading word line100over and over is not informative with respect to read disturb. This is being when word line100is read over and over, additional voltage from read disturb is being added to word lines102a-102c, which are not the word lines which are being evaluated or tested. Word line100, which is the word line being tested, does not have a significant amount of read disturb because word lines102a-102care not being read. Thus, repeatedly reading the same word line over and over (even if MSB reads are being performed) is not informative with respect to read disturb.

To detect when too many of these uninformative reads have been performed in a row (in other words, the system is developing a blind spot with respect to read disturb), a count of consecutive, at least potentially uninformative reads is used. The following figure describes this in more detail.

FIG. 4is a flowchart illustrating an embodiment of a process for performing a read disturb check. In some embodiments, the process is performed by a read processor in a solid state storage controller (e.g., implemented on a semiconductor device, such as an application-specific integrated circuit (ASIC) or field-programmable gate array (FPGA)).

At401, an indication is received that a word line, from a plurality of word lines in solid state storage, has been read, wherein the plurality of word lines is divided into a plurality of groups. For example, even word lines (e.g., those word lines having an address or offset which is an even number) may be assigned to one group and odd word lines are assigned to another group. In some embodiments, a read at401is a host or firmware initiated read. For example, a user or application may desire some data stored in solid state storage and the process ofFIG. 4piggybacks off of the host or firmware initiated read.

At402, it is determined which group is associated with the read. To continue the example where word lines are divided into odd and even word lines, when a read is performed on word line W of block B, the bit pnewis set to pnew=mod(W, 2) where the mod(•) operation is mod(x,2)=

mod⁡(x,2)={0,xeven1,xodd.
In other words, if an even word line is read, then pnew=0 and if an odd word line is read, then pnew=1.

At403, a count of consecutive, at least potentially uninformative reads is updated based at least in part on the group associated with the read and a group associated with a prior read. In some embodiments, the count cBis updated at403, where cBis a count of consecutive, at least potentially uninformative reads for block B. Another way of describing a read which is “at least potentially uninformative” is that it is either (1) a read which is known to be uninformative with respect to read disturb or (2) a read which is potentially uninformative with respect to read disturb. A read which is known to be informative with respect to read disturb is not counted at403.

In one example of step403, pBis used to track the group, for block B, which was read during the last informative read. To continue the example where word lines are divided into odd or even word lines, if pB=1 then the last informative read was an MSB read of an odd word line in block B and if pB=0 then the last informative read was an MSB read of an even word line in block B. In some embodiments, the bit pBis initialized to a random or arbitrary value (e.g., when the process is started and no informative reads have been performed). An example of step403is described in further detail below.

At404, it is determined if the count is greater than a threshold. If the count is greater than the threshold, then a read disturb check is triggered at405. Any read disturb check may be performed and the techniques described herein are not tied to any one particular read disturb check. If the count is not greater than the threshold at404, then another indication is received at401.

FIG. 5is a flowchart illustrating an embodiment of a process for updating a count of consecutive, at least potentially uninformative reads. In some embodiments, the example process is performed at step403inFIG. 4. At500, a bit position associated with the read is determined. For example, in the case of a 2-bit MLC system, either an MSB read or an LSB read is performed.

At502, it is determined if the bit position corresponds to an informative read. In the example ofFIG. 2, an LSB read is an uninformative read (e.g., because LSB read threshold202is not near read disturb region204) and an MSB read is an informative read (e.g., because read disturb region204is near read threshold200a, which is an MSB read threshold).

If at502it is determined that the bit position does not correspond to an informative read, then a count of consecutive, at least potentially uninformative reads is incremented at504. For example, if an LSB read is performed, then cB=cB+1. In other words, it is a necessary but not sufficient condition that an informative read is an MSB read (at least for the bit assignments inFIG. 2).

If at502it is determined that the bit position does correspond to an informative read, it is determined at506if the group associated with the read is the same as a group associated with a last informative read. For example, if pnew=pBthen the decision at step506is yes; if pnew≠pBthen the decision at step506is no. The group associated with the last informative read at step506is one example of a group associated with a prior read from step403inFIG. 4.

If the groups are the same, then the count is incremented at504. If the groups are not the same, then the group associated with the last informative read is updated to be the group associated with the read at508. For example, pB=pnew. At510, the count of consecutive, at least potentially uninformative reads is reset to 0.

FIG. 6is a diagram showing an embodiment of a solid state storage system which uses a count of consecutive, at least potentially uninformative reads to trigger read disturb detection. In the example shown, read disturb trigger660performs the process described inFIG. 4. In this example, read processor650is implemented on or using an ASIC or FPGA.

In the example shown, solid state storage600includes word lines602a-602d. The word lines are divided into odd and even groups so that word lines602aand602care in one group and word lines602band602dare in another group.

The word line read address and MSB/LSB read are passed from solid state storage600to read disturb trigger660. From the word line read address, read disturb trigger660is able to determine the group associated with a read (e.g., even or odd) and from the MSB/LSB read, read disturb trigger660is able to determine a bit position associated with the read. Read disturb trigger660stores bit pB664and bit pnew666(in count updater668) which are used to update count cB662. In this example, count cB662is a 4-bit counter.

Count comparator670compares count cB662against a threshold. When the count exceeds the threshold, an enable signal to read disturb detector680is asserted, which causes read disturb detector680to initiate read disturb detection. In one example, correction based detector682is used. First, an MSB read of the other group is used. For example, if pB=0 (i.e., the last informative read was from the even group), then a word line from the odd group is randomly selected and an MSB read is performed on that randomly selected odd word line. The read back data is then passed to an error correction decoder (not shown) and a number of corrected bits in a payload portion (and/or a parity portion) is determined (see, e.g.,FIG. 3). If the number of corrected bits exceeds some threshold (not shown) then that word line is determined to have too much read disturb and the data is moved to another word line. The read disturb detection process may continue for other word lines if read disturb is detected in the tested word line.

In another example, read based detector684is used. Generally speaking, the idea behind a read based detector is to determine how many cells are storing a non-zero but relatively low voltage by performing two reads at two different (but relatively low) read thresholds. For example, inFIG. 2, an MSB read is performed at read threshold210and then at read threshold212. In this example, the word line which is read twice is randomly selected from the group which is oppose to pB(e.g., if pB=0 then randomly select an odd word line) which is the same as in the above example. Then, the number of cells which flipped between those two MSB reads is determined (e.g., by finding the difference in the number of 1s read back with the different read threshold, or the difference in the number of 0s read back with the different read thresholds). This number indicates how many cells store a voltage between voltage210and voltage212. A perfect distribution without any read disturb would look like a delta function which spikes just below 0 V, so if the number of cells between voltages210and212is greater than some threshold, it is determined that that word line has too much read disturb and the data is moved to another word line. As in the previous example, the read disturb detection process may go on to test other word lines if read disturb is detected in the tested word line.

Although other ways of grouping word lines602a-602dexist, having word lines be assigned to alternating groups (e.g., even/odd groups) is desirable because it catches a sequential read. For example, suppose a song is stored in solid state storage in consecutive word lines. To play back the song, word lines are accessed in ascending or descending order; this is referred to as a sequential read. If (instead) the upper word lines were assigned to one group and the bottom word lines were assigned to another group, then a sequential read would be interpreted by read disturb trigger660as reading from the same group over and over and the count cBwould be incremented with each read. In contrast, with an even group and an odd group, a sequential read would be interpreted by read disturb trigger as switching back and forth between the two groups, and fewer unnecessary read disturb checks would be triggered.

A benefit to using groups to increment the count cBis that less information needs to be stored. Instead of having to store the entire address of a word line for some previous read, only a single bit (pB) needs to be stored. For example, suppose there are M blocks in solid state storage. The number of bits which must be stored by read disturb trigger660is (M×4 bits)+(M×1 bits)+(1 bit) where the first term corresponds to all of the cBcounts, the second term corresponds to all of the pBbits, and the third term corresponds to the pnew(i.e., a single pnewbit is shared amongst all blocks). When compared against other read disturb techniques which use counters (e.g., one counter per block) that count program and erase (P/E) cycles that go into the millions, this is much less storage.

In addition to requiring less storage, because the counter cBis relatively small, it is acceptable if the count is lost, for example, because of a power down. As such, it can be stored in volatile memory and does not need to be moved to non-volatile memory if a power down is signaled. Some solid state storage system manufacturers have power down timing requirements which component manufacturers must comply with. Having a shorter list of things to migrate to non-volatile storage would be desirable in such systems because there are fewer things to be backed up before the power down.

FIG. 7is a diagram showing an embodiment of performance reduction as a function of the number of bits in a counter. In the example shown, the counter cBhas N bits. As the number of bits in the counter increases, the performance reduction which comes from having to perform an extra read (e.g., a read not requested by the host) is shown along the y-axis. When N=4, the performance reduction is less than 1%, so a counter which is 4 bits long may be acceptable in some applications. Having a counter which is 4 bits long is much smaller than a 20 bit counter which counts into the millions.

In some embodiments, a count is merely one path by which a read disturb check may be triggered. The following figure shows an example in which there are two paths by which a read disturb check may be triggered.

FIG. 8is a diagram showing an embodiment of a process for triggering a read disturb check based on a count or on a number of corrected bits. At802, an indication is received that a word line, from a plurality of word lines in solid state storage, has been read, wherein the plurality of word lines is divided into a plurality of groups. For example, even word lines are in one group and odd word lines are in another group. At804, it is determined which group is associated with the read. At806, a count of consecutive, at least potentially uninformative reads is updated based at least in part on the group associated with the read and a group associated with a prior read. At808, it is determined if the count is greater than a first threshold. If so, a read disturb check is triggered at810, for example, on a word line randomly selected from the group other than the group associated with the last informative read. For example, if pB=1, then a word line from the even group is randomly selected.

If the count is not greater than the first threshold, a number of corrected bits is received at812. For example, error correction decoding may be performed and the number of corrected bits from that error correction decoding process is received at812. At814, it is determined if the number of corrected bits is greater than a second threshold. If so, a read disturb check is triggered at816, for example, on a word line randomly selected from any group. If not, a next indication is received at802. In some embodiments, the second threshold used at step814is less than a threshold used to detect read disturb (e.g., used by correction based detector682inFIG. 6).

To illustrate why in some cases it is desirable to have a second path via which a read disturb check is triggered, consider the following example. Suppose that inFIG. 6, word lines602aand602bare MSB read in alternating fashion and word lines602cand602dare never read. Word lines602aand602bbelong to different groups, so the alternating MSB that reads to those word lines causes the counter cBto reset each time. The counter cBwill never trigger a read disturb check in this scenario, even though read disturb is accumulating with each read on word lines602cand602dsince they are never read (and to a lesser degree on word lines602aand602bwith every other MSB read). However, the process shown inFIG. 8will eventually trigger a read disturb check when the number of corrected bits exceeds the second threshold at814. The read of word line602acauses read disturb on word line602band vice versa, so eventually the number of corrected bits will exceed the second threshold and cause a read disturb check to be triggered. This example also illustrates why it may be attractive to randomly select a word line from any class at step816. The bit pBmay have no meaning in the above example, so it may make more sense to select a word line from any group.

FIG. 9is a diagram showing an embodiment of a solid state storage system which uses a count of consecutive, at least potentially uninformative reads to trigger read disturb detection, as well as a number of corrected bits. In the example shown, read disturb trigger960performs the process shown inFIG. 8. In the example shown, the enable signal output by read disturb trigger960may be asserted based either on count cB962or based on the number of corrected bits output by error correction decoder990. Comparator970includes two thresholds: T1and T2. The first threshold (T1) is compared against count cB962and the second threshold (T2) is compared against the number of corrected bits. In this example, the number of corrected bits output by error correction decoder990is also passed to correction based detector982.

In this example, depending upon how the enable signal is triggered, different groups on which to perform read disturb detection are signaled by read disturb trigger960. If a read disturb is triggered based on count cB962, the read disturb trigger signals the group opposite of the group associated with a last informative read. For example, if pB=0 then the group output by read disturb trigger960is the opposite (i.e., perform a read disturb check on the odd group).

If a read disturb is triggered based on the number of corrected bits, then both the even group and odd group are output by read disturb trigger. In one example, the group signal output by read disturb trigger960is a 2-bit signal where one bit is associated with the even group and the other bit is associated with the odd group so that if both bits are asserted, a word line is randomly selected from either group.

Returning toFIG. 1, in some embodiments, the pass voltages (i.e., the voltages applied to word lines which are not being read) are the same. In some other embodiments, different pass voltages are used. The following figures show an example of the latter embodiment and an example of how this may be taken into consideration when selecting a word line for read disturb testing.

FIG. 10is a diagram showing an embodiment of unequal pass voltages. In the example shown, word line1002is being read. In this system configuration, the word lines which are adjacent to the word line being read are set to a highest pass voltage. As such, word lines1000aand1000bare set to pass voltages of Vpass. All other word lines which are not being read are set to some lower pass voltage. As such, word line1004is set to a pass voltage of 0.8 Vpass.

FIG. 11is a diagram showing an embodiment of a process for selecting a word line using weights based on pass voltages. In the example shown, the process is performed in a system where unequal pass voltages are applied to word lines which are not read. One example of this is shown inFIG. 10. In various embodiments, the process ofFIG. 11may be performed during step405inFIG. 4, step810inFIG. 8, and/or step816inFIG. 8.

At1100, pass voltage information associated with word lines which are not read is received. In one example, an array of scaling factors may be received, where a scaling factor of 0 indicates a word line which is read. UsingFIG. 10as an example, the array [1 0 1 0.8] may be received at1100.

At1102, identification of one or more groups from which to select a word line is received. For example, if the process is performed at step810inFIG. 8, then the group identified at1102would be the group other than the group associated with the last informative read. If, on the other hand, the process is performed at step814inFIG. 8, both the even group and odd groups would be identified at1102.

At1104, a plurality of weights is generated based at least in part on the pass voltage information, such that word lines with higher pass voltages are more heavily favored. InFIG. 10, for example, the weight for word line1004would be lower than the weight for word line1000aor1000b. This favors selection of word line1000aor1000b(which probably have more read disturb) over word line1004; it is desirable to check for read disturb on word lines which are likely to have the most read disturb. A word line is selected from the one or more identified groups using the plurality of weights at1106.

In one example, the last word line read is word line k and this last read is taken into consideration by skewing the probability towards reading word lines (k−1) and (k+1), which are likely to have greater read disturb than others if word line k is being read repeatedly. In this example, if there are M word lines to choose from, the probability of testing word lines (k−1) and (k+1) is set to 1/(M−a) and the probabilities of all other word lines being read set to 1/(M+b) so that word lines (k−1) and (k+1) have a higher probability of being selected for testing.

FIG. 12is a diagram showing an embodiment of a solid state storage system which uses a count of consecutive, at least potentially uninformative reads to trigger read disturb detection on a word line selected based on pass voltage information.FIG. 12is similar toFIG. 6and for brevity similar components are not described herein. In the example shown, word line selector1200performs the process described inFIG. 11and selects a word line on which read disturb detection is performed. As such, the word line which is tested is passed from the read disturb trigger1202to read disturb detector1204. Word line selector1200selects a word line to perform read disturb detection on. It makes this selected based on the pass voltage information, generates weights which favor selection of word lines with higher pass voltages, and then makes the selection based on the weights.

FIG. 13is a diagram showing an embodiment of a solid state storage system which uses a count of consecutive, at least potentially uninformative reads to trigger read disturb detection, as well as a number of corrected bits, to trigger read disturb detection on a word line selected based on pass voltage information.FIG. 13is similar toFIG. 9and similar components are not described herein. Word line selector1300performs the process shown inFIG. 11. Read disturb trigger1302passes this selected word line to read disturb detector1304which performs read disturb detection on the indicated word line.