Wie NAND-Flash-Controller einzelne Seiten effizient löschen?

Schauen Sie sich dieses Dokument von Micron an : Verwenden Sie eine Zuordnung von logischen Blöcken zu physischen Blöcken. Bewahren Sie einen Vorrat an leeren Seiten auf und schreiben Sie in die nächste verfügbare (oder eine, die von Ihrem Wear-Leveling-Algorithmus ausgewählt wurde).

Schließlich sind fast alle Ihre Blöcke voll, mit einigen Löchern, in denen Seiten innerhalb des Blocks als "gelöscht" markiert, aber nicht wirklich gelöscht wurden. Dann führen Sie Ihren Algorithmus aus: Finden Sie Blöcke mit den meisten gelöschten Seiten, kopieren Sie sie an einen neuen Ort, löschen Sie den alten Ort, setzen Sie den alten Ort auf die "freie" Liste.

Damit stellt sich dann die Frage, wie die Mapping-Daten selbst gespeichert werden; Ein gängiger Ansatz besteht darin, die Blöcke leicht zu erweitern und die Zuordnungsdaten auf den Block selbst (als "Tag") zu setzen. Beim Hochfahren kann der Controller einige oder alle Zuordnungen im RAM zwischenspeichern. Ein anderer Ansatz besteht darin, den NOR-Flash des Controllers selbst zum Speichern der Mapping-Daten zu verwenden.

Wie von pjc50 angemerkt, besteht das allgemeine Konzept darin, dass man eine feste Beziehung zwischen logischen Adressen und physikalischen Adressen vermeidet. Jedes Mal, wenn eine Anforderung zum Schreiben einer Seite gestellt wird, verwenden Sie einfach eine andere Seite, von der bekannt ist, dass sie leer ist, und notieren Sie sich, dass der Block jetzt an der neuen Position gespeichert ist.

Konzeptionell ist dies schön und einfach. Je nachdem, mit wie vielen unabhängig zugeordneten Seiten Sie es zu tun haben, kann es in der Praxis auch relativ einfach sein (insbesondere, wenn die Anzahl der zugeordneten Seiten klein genug ist, dass Sie es sich leisten können, die gesamte Tabelle der tatsächlichen Seitenpositionen im RAM zu behalten, und sich die Zeit nehmen können, nach allen Live-Seiten zu suchen und ihre Positionen in der Tabelle zu notieren). Wenn die Anzahl der Seiten jedoch groß ist, kann es erforderlich sein, einige Tabellen im Flash zu führen, die so organisiert sind, dass sie schnell den bestimmten physikalischen Block finden, der einer logischen Adresse zugeordnet ist. Der Versuch, die Speicherorte aller 512-Byte-Seiten in einem 32-GB-Flash zu finden, würde beispielsweise etwa 256 MB Speicher erfordern, und selbst wenn man eine Million Seiten pro Sekunde verarbeiten könnte, würde das Laden dieses Speichers über eine Minute dauern.

Theoretisch könnte man Seiten haben, die die Positionen von 128 anderen Seiten enthalten, Seiten haben, die die Position von 128 dieser Seiten enthalten (indirekt die Position von 16.384 Seiten enthalten), Seiten haben, die 128 davon enthalten (2.097.152 Seiten) und haben eine Seite, die ungefähr 32 davon enthält (was 67.108.864 Seiten mit Daten verwalten würde). Um eine Seite Seite N zu finden, verwenden Sie die Bits 21-25 der Seitennummer, um eine von 32 Seitenadressen in dieser zuletzt erwähnten Seite auszuwählen, dann die Bits 14-20, um eine von 128 Seitenadressen in dieser auszuwählen, dann die Bits 7- 14, um eine der 128 Seitenadressen in dieser auszuwählen, und schließlich die Bits 0-6, um eine Seite in dieser auszuwählen. Voila – man hat jetzt die Adresse der Seite, die man braucht.

Leider bedeutet dieser Ansatz, dass das Lesen jeder Speicherseite das Lesen von fünf Seiten aus dem Flash-Chip erfordert, und noch schlimmer – das Schreiben jeder Speicherseite erfordert ein Neuschreiben der Seite, die ihre Adresse enthält, was wiederum ein Neuschreiben der Seite erfordert, die enthält die Adresse dieser Seite, was wiederum ein Umschreiben der Seite erfordert, die die Adresse dieser Seite enthält, usw. Insgesamt fünf Seiten. Ick.

Man kann die Dinge erheblich verbessern, wenn man die Möglichkeit berücksichtigt, dass die Daten in den Seitenkarten nicht absolut aktuell gehalten werden müssen, wenn bei jedem Seitenwechsel die Adresse der neuen Seite an eine zuvor leere Stelle im Tag geschrieben wird Erinnerung an die alte Seite. Eine solche Erlaubnis kann die Leseleistung verschlechtern, da ein Zeiger, der zu einer Seite gehen soll, auf eine alte Version zeigen kann, die auf eine andere alte Version usw. zeigen kann, bevor sie schließlich die richtige Seite erreicht. Andererseits kann eine solche Erlaubnis die Schreibleistung enorm verbessern.

Selbst wenn man beispielsweise nur eine einzige zusätzliche Umleitungsebene zulässt (was bedeutet, dass, wenn eine Seite einmal verschoben wurde, ohne den Elternzeiger zu aktualisieren, der Elternzeiger bei der nächsten Bewegung aktualisiert werden muss), würde dies nur die Hälfte der Schreibvorgänge auf einer Seite tun erfordert das Schreiben einer Seite plus Tag, ein Viertel würde das Schreiben von zwei Seiten plus Tag erfordern, eine Acht würde das Schreiben von drei Seiten plus Tag erfordern usw. Eine ziemlich große Verbesserung im Vergleich zu jedem adressierten Seitenschreiben, bei dem sechs Seiten neu geschrieben werden müssen. Wenn man bis zu drei zusätzliche Indirektionsebenen zulässt (jeder vierte Schreibvorgang auf einer bestimmten Ebene erfordert eine übergeordnete Aktualisierung), dann sind 3/4 der Aktualisierungen ein Schreibvorgang plus ein Tag, 3/16 sind zwei, 3/64 sind es drei, und nur 1/64 erfordert mehr als das.

Beachten Sie, dass das Zulassen mehrerer Umleitungsebenen zwar die Leseleistung verlangsamen kann, dies jedoch mehr als ausgeglichen werden kann, indem die Adressen kürzlich verwendeter Blöcke im RAM zwischengespeichert werden. Wenn der Inhalt eines Cache-Eintrags verloren geht (sei es, weil die Stromversorgung unterbrochen wurde oder weil er "abgelaufen" ist), wird der nächste Zugriff auf seine Seite langsamer als gewöhnlich sein, aber die Verwendung von Tags für die Aktualisierungen würde bedeuten, dass die korrekten Daten immer noch vorhanden wären gefunden.

Das Entwerfen guter Algorithmen zur Verwaltung eines Flash-Geräts ist schwierig. Obwohl Micron vorzuschlagen scheint, dass der gesamte Chip eine einheitliche "Zone" sein soll, halte ich das nicht für sehr praktisch. Es muss zumindest eine Möglichkeit geben, die Hauptindizierungsseite zu finden. Meine Empfehlung wäre, dass die Master-Indizierungsseite zu jedem Zeitpunkt auf einen von einer relativ kleinen Anzahl von Blöcken beschränkt ist. Die Standorte dieser Blöcke sollten in einem der wenigen Super-Master-Blöcke aufbewahrt werden, die diesem Zweck gewidmet sind. Alle paar hundert Mal, wenn die Master-Indizierungsseite ihre zugewiesenen Blöcke durchlaufen hat, sollte ein neuer Satz von Blöcken dafür ausgewählt und die Super-Master-Blöcke aktualisiert werden, um dies widerzuspiegeln. Die Anzahl der Super-Master-Blöcke wäre klein genug, dass das System sie alle beim Start untersuchen könnte, und die Anzahl der im aktiven Super-Master-Block aufgelisteten Master-Blöcke wäre klein genug, dass das System all diese untersuchen könnte. Da es Tausende von Änderungen am Master-Block für jeden Super-Master-Block geben könnte, sollte es kein Problem geben, dass der letztere verschleißt.