NAND Flash
In fast jedem Multimedia-gerät, vom Mobiltelefon bis zum Bilderrahmen, steckt mittlerweile ein Speicher der Anwenderdaten dauerhaft behält. So hat sich der NAND-Flash als preiswerte Technologie herausgestellt und soll daher im nachfolgenden Artikel genauer beleuchtet werden.

Aufbau
Ein NAND-Flash besteht intern aus einer großen Anzahl an Pages (Seiten). Diese haben üblicherweise Größen von 512 Bytes oder auch 2048 Bytes bei größeren Bausteinen. Der Zugriffe auf den Speicher erfolgen 'immer' Seiten-weise, d.h es werden Übertragungstakte für die Addresse und weitere Takte für die Datenübertragung benötigt. Daher werden Adress und Datenleitung im Multiplex-Verfahren verwendet.



Zu jeder Page gehört neben dem genannten Datenbereich noch der Sparebereich, der Verwaltungsinformationen wie beispielweie eine ECC-Prüfsumme beinhaltet. So ist es üblich für 2048 Datenbytes 64 Sparebytes zu verwenden. Mehrere Pages (beispielsweise 64) werden zu einem Block zusammengefasst.

Operationen
Lese- und Schreib-zugriffe können auf jede beliebige Addresse sogar inerhalb einer Page ausgefürt werden, obwohl es aus später genannten Gründen sinnvoller ist immer eine komplette Page zu lesen bzw. schreiben. Der Begriff 'Schreiben' ist jedoch ein wenig irreführend, da tatsächlich nur die Nullen geschrieben werden. Das bedeutet, dass man eine geschriebene Null nicht mit einer Eins überschreiben kann. Vorher muß man den gesamten Block (!), in dem sich die gewünschte Zelle befindet löschen. Dieser Erase-Vorgang setzt alle Zellen auf Eins (jedes Byte ist 0xFF), auch die Spare-Bytes.

Error Correction Code
Aufgrund der eingesetzten Technologie altern die Speicherzellen mit jedem Schreibvorgang. Irgendwann lassen sich einzelne Bits innerhalb einer Page nicht mehr verändern, sie sind defekt. Daher ist es notwendig diesen Defekt zu erkennen und zweitens die Daten möglichst zu retten. Dazu wird im Sparebereich einer jeden Page ein ECC abgelegt, mit dem Fehler erkannt und eventuell sogar korrigiert werden können.
Der Hamming-Code kann zwei Bit-Fehler erkennen und einen Bitfehler korrigieren. Er ist wegen seiner Einfachheit beliebt. Für 2n=512 Bytes an Daten werden 2 * n = 18 Bit an ECC-Daten benötigt. Neben dem Hamming existiert noch der BCH und weiterere ECC-Algorithmen, die bei gleicher Anzahl an verwendeten Spare-Bytes mehr Fehler erkennen und reparieren können, diese aber mehr Rechenleistung benötigen.
Tritt in einer Hamming-geschützten Page ein Bitfehler auf ist dies noch lange kein Problem. Die fehlerhafte Page wird vom Treiber eingelesen und im Speicher korrigiert. Die höheren Schichten des Softwarestacks merken somit nichts von diesem Bitfehler.



Caching
Soll innerhalb einer Page auch nur ein einzelnes Byte verändert werden, so muss die gesamte Page zuerst in den Speicher eingelesen werden. Dann erst kann die gesamte Page mit geändertem Byte und neu berechnetem ECC zurückgeschrieben werden. Dies bedeutet gleichzeitig ein Altern der Page. Würde man eine Bereich im NAND Byte für Byte auf diese Weise verändert, was viele Erase/Write Zyklen bedeutet, so wäre der Baustein ziemlich schnell am Ende. Daher ist es ratsam eine Page so lange wie möglich im Speicher (Cache) zu halten und nur selten zurückzuschreiben. Der Cache kann ein im Controller integrierter SRAM oder auch ein externer SDRAM-Chip sein.


Viel Cache ist aber nicht immer von Vorteil. Denn wenn die Spannungsversorgung abbricht, sind eventuell einzelne Pages aus dem Cache noch nicht in den NAND-Baustein weggeschrieben. Hier helfen Puffer-Akkus, die Controller, Cache und die NAND-Chips solange mit Energie versorgen, bis alle Pages weggeschrieben wurden.

Block Management
Soll eine einzelne Page in den NAND geschrieben werden, dann kann diese nicht an die gleiche Pageadresse geschrieben werden. Denn dort befindet sich noch die Page mit den vorherigen Daten. Zuvor müßte die Page gelöscht werden. Der Erase-Befehl löscht wiederrum nur ganze Blöcke. Eine ineffiziente Methode wäre es, den gesamten Block mit allen (!) darin befindlichen Pages in den Cache zu laden, den gesamten Block zu löschen und danach alle Pages wieder zurück zuschreiben. Dieser Vorgang wäre sehr Zeitaufwändig und würde ein unnötiges Altern der anderen Pages innerhalb des Blockes bedeuten.
Der bessere Weg ist es, eine Page aus einem noch freiem (gelöschtem) Block zu nehmen. Zugriffe auf die Daten erfolgen dann über eine 'virtuelle' Page-Adresse. Eine Mapping-Tabelle übersetzt die virtuelle Adresse auf die aktuelle physikalische Adresse. Die Page mit den alten ungültigen Daten verbleibt dort wo sie ist, unverändert.


Letztendlich bedeutet das aber, dass von einer (virtuellen) Page mehrere Versionen von verschiedenen Zeitpunkten exisitieren. Die Mapping-Tabelle sorgt dafür dass zu jeder virtuellen Page nur eine einzige gültige physikalische Page exisitiert. Die Tabelle muss selbst in regelmäßigen Abständen in den NAND gepeichert werden (Metadaten). Es wird nun auch klar, dass mehr physikalische Pages bzw. Blöcke benötigt werden als virtuell zur Verfügung stehen. Die Differenz nennt man Spare-Blöcke.
In der nachfolgenden Abbildung sollen Daten in Page 8 (virt.) geändert werden. Laut Mapping muss die physikalische Page 8 in den Cache geladen werden. Dort werden die gewünschten Daten verändert. Die virtuelle Page 8 wird dann jedoch auf die noch freie Page 21 (phys.) zurückgeschrieben. In der Mapping-Tabelle zeigt kein Eintrag mehr auf die physikalische Page 8. Damit ist diese ungültig.



Garbage Collection
Irgendwann gehen dem NAND-Baustein die freien Blöcke/Pages aus. Der gesamte NAND Baustein ist gefüllt mit ungültigen (phys.) Pages, zu denen es bereits eine neuere Version gibt. Hier bieten sich nun an, Blöcke zu suchen die keine gültigen Pages (oder nur noch wenige gültige Pages) enthalten und diese Blöcke zu löschen. Obwohl der Speicher im nachfolgenden Bild so gut wie leer ist (5 Pages in Benutzung), exisitieren jedoch keine freien Pages mehr.


Die verbleibenden gültigen Pages aus mehreren Blöcken können auch in einen einzigen freien Block zusammenkopiert werden. Die virtuellen Addressen bleiben unverändert, das Mapping auf die physikalischen Page-Addressen muss nun jedoch nachgezogen werden.
Das Erzeugen von freien, frisch gelöschten Blöcken kann zu jeder Zeit erfolgen. Sei es nun das der NAND gerade nicht benötigt wird, oder dass die freien Blöcke ausgegangen sind. Der NAND kann komplett aufgeräumt werden oder auch nur soviel wie gerade benötigt. Es ist jedoch anzumerken dass häufiges verschieben von Pages ebenfalls zum schnelleren Altern beiträgt. Daher sollte das Zusammenkopieren so selten wie möglich und auf den Blöcken mit den wenigsten gültigen Pages erfolgen.

Bad Block Management
Natürlich kommt es auch vor, dass die Fehlerkorrektur eine Page nicht mehr korrigieren kann, sodaß die ganze Page als defekt zu deklarieren ist. Problematisch ist nun, dass nach einem Erase auf dem Block, der die defekte Page enthält nicht mehr alle Pages zu Verfügung hat. Eine einfache Lösung ist es, den gesamten 'alten' Block (mit der defekten Page) durch einen 'jungen' Reserveblock zu ersetzen. In einer Bad-Block-Liste braucht nur vermerkt werden, welcher Block nicht mehr benutzt werden darf. Dafür wird der Reserveblock von der Liste der Reserveblöcke genommen.


Die Listen, welche Blöcke defekt sind, welche in Benutzung sind und welche noch als Reserve zur Verfügung stehen müssen ebnfalls mit auf den NAND gespeichert werden.