Detekce a korekce chyb u NAND flash pamětí

Detekce a korekce chyb v pamětech NAND Flash

V současné době, kdy informace hrají klíčovou roli, je důležitá nejen rychlost, ale i přesnost při ukládání, načítání, přenosu a analýze dat. Vzhledem k množství kritických informací generovaných každou minutu může i ta nejmenší chyba způsobit katastrofu. S tím, jak se flash paměti vyrábějí s menší geometrií, narůstá také počet chybových bitů, což vyžaduje výkonnější algoritmy pro korekci chyb k zajištění spolehlivosti flash úložných zařízení.

Vadné bloky na flash pamětech

Vadné bloky jsou bloky obsahující jeden nebo více neplatných bitů. Mohou být nepoužitelné nebo nestabilní a náchylné k chybám. Mohou se vyskytovat i v nových zařízeních a mohou se vyvinout během životnosti zařízení.

V NAND flash úložištích existují dva typy vadných bloků:

• Počáteční vadné bloky: NAND flash zařízení mohou být dodávána s určitým počtem vadných bloků. Před expedicí zařízení je zmapována poloha vadných bloků a obvykle je implementován algoritmus pro správu vadných bloků, kde je vytvořena tabulka vadných bloků čtením všech náhradních oblastí v flash úložišti. Neplatné bloky jsou identifikovány během testování a validace ve výrobě. Tabulka vadných bloků je uložena v dobrém bloku, aby mohla být načtena zařízením při restartu.
• Nashromážděné nebo přírůstkové vadné bloky: Během používání zařízení může dojít ke ztrátě nebo poškození dat v dobrých blocích v důsledku opotřebení během životnosti, což vede k chybám při čtení/zápisu, chybám v retenci dat a dalším problémům. Následkem toho poškozené bloky způsobují nedostupnost uložených dat a aplikace nebo operační systémy nemusí být schopné je otevřít. S rostoucím počtem vadných bloků se snižuje kapacita disku a zhoršuje se výkon, což nakonec vede k selhání zařízení.

Degradace NAND flash paměti a bitové chyby

K detekci a opravě bitových chyb se používají kódy pro opravu chyb. U prvních modelů flash pamětí se používaly jednociferné chybové kódy, ale s postupným zmenšováním velikosti buněk a zvyšováním počtu bitů na buňku byly potřeba složitější mechanismy. Následující faktory ovlivňují degradaci flash pamětí a nárůst bitových chyb.

• Cykly programování/mazání (P/E): Neustálé cykly programování (zápisu) a mazání vyžadují aplikaci vysokého napětí na NAND buňku, což způsobuje namáhání a oslabování tunelového oxidu. Operace programování (zápisu) a mazání v NAND flash buňce vyžadují aplikaci vysokého napětí, které namáhá tunelový oxid. S rostoucím počtem P/E cyklů se tunelový oxid oslabuje, což způsobuje únik elektronů z plovoucího hradla a degradaci NAND flash buňky.
• Více bitů na buňku (Obrázek 2) : Ve snaze zvýšit hustotu umožnily nové flash technologie ukládání více bitů do jedné buňky, což zužuje mezeru mezi prahovými napěťovými (VT) distribucemi. To vede k napěťovým posunům a způsobuje bitové chyby v důsledku interference mezi buňkami. Více bitů uložených v jedné buňce přináší zvýšenou hustotu/kapacitu, ale také zvyšuje interferenci mezi buňkami, protože jsou buňky umístěny blíže k sobě. Čtení nebo zápis do jedné buňky může ovlivnit sousední buňky a způsobit bitové chyby.

Detekce a korekce chyb v NAND flash úložných zařízeních

Kódy pro opravu chyb (ECC) jsou techniky používané k opravě chyb v NAND flash, které umožňují obnovení dat, jež mohou být poškozena v důsledku bitových chyb. Interní ECC mechanismy mohou detekovat/opravit až určitý počet chyb.

Příkladem ECC používaného v některých flash úložných zařízeních je tzv. Hammingův kód. Byl vynalezen v roce 1950 a pojmenován po svém tvůrci Richardu Hammingovi. Tento algoritmus dokáže detekovat a opravit 1bitové chyby, ale u 2bitových chyb je schopen pouze detekce, nikoliv opravy. Je snadný na implementaci díky svým omezeným schopnostem opravy chyb a je široce používán v jednoúrovňových buňkách (SLC), které mají jednodušší architekturu a vyžadují pouze jednobitovou ECC. Populární Hammingův kód je veverzi 7,4, kde v 7bitovém bloku tvoří pouze 4 bity data a zbývající 3 bity jsou kódy pro opravu chyb.

Níže je ukázka implementace Hammingova kódu na 2KB stránce s 2048 bajty uživatelských dat. (U flash úložných zařízení, kde je velikost stránky větší než 512 bajtů, se data rozdělí do sekcí po 512 bajtech, přičemž pro každou 512bajtovou sekci se použije Hammingův kód.)

Ukázková implementace Hammingova kódu pro 2KB stránku. Hammingův kód pro každou 512KB sekci je uložen v náhradní oblasti.
Zatímco některé levnější produkty dostupné na trhu používají pouze jednoduché Hammingovy kódy, produkty výrobců jako Samsung nebo Sandisk využívají pokročilé ECC, které dokáží opravit více bitových chyb.

Následující část představuje mechanismy detekce a korekce chyb používané v NAND flash úložných zařízeních:

Reed-Solomonův algoritmus

Byl vynalezen v roce 1960 inženýry Irvingem Reedem a Gustavem Solomonem, kteří pracovali v MIT Lincoln Labs. Reed-Solomonův algoritmus zahrnuje přidání dodatečných/redundantních dat k bloku digitálních dat. Běžně se používá v pevných discích a kompaktních discích, stejně jako v NAND flash úložištích, kde se často používá ke zvládání překlápění bitů. K překlopení bitu dochází, když operace na jedné buňce způsobí rušení v jiné buňce kvůli blízkosti paměťových buněk postavených příliš blízko u sebe. Když dojde k překlopení bitu, plovoucí hradlo buňky může získat (být naprogramováno) nebo ztratit (být vymazáno) elektrony kvůli rušení v jiné buňce.

Reed-Solomonovy kódy opravují symboly a jsou proto považovány za vynikající pro aplikace, kde se chyby obvykle vyskytují ve shlucích. Reed-Solomonův algoritmus se široce používá k opravě vícenásobných bitových chyb na jedné stránce, ale může podávat horší výkon u velkých bloků zpráv, výrazně prodlužující čas potřebný k zakódování nebo dekódování dat při zdvojnásobení velikosti bloku.

Populární Reed-Solomonův kód je RS (255, 247) s 8bitovými symboly. Každé kódové slovo obsahuje 255 bajtů, z nichž 247 bajtů jsou data a 8 bajtů je parita. Dekodér může opravit jakékoliv 4 chyby symbolů v kódovém slově.

V současnosti některé flash produkty implementují Reed-Solomonovo kódování pomocí kódování 4 bajtů na 512 bajtů. To znamená, že ECC mechanismus na těchto produktech může opravit nejméně 4 bitové chyby na každých 512B. V nejlepším případě však může opravit až 32 bitových chyb na 512B, pokud se těchto 32 bitových chyb nachází ve stejných 4 symbolech.

BCH (Bose, Chaudhuri, Hocquenghem) algoritmus

BCH kódy byly vynalezeny v roce 1959 Alexisem Hocquenghemem a nezávisle v roce 1960 Rajem Bosem a D.K. Ray-Chaudhurim. BCH kódy dokáží opravit vícenásobné bitové chyby a zvládají jak náhodné, tak shlukové chyby. Hlavní výhodou BCH kódů je, že lze být snadno dekódovány pomocí metody zvané "syndromové dekódování". BCH kódy vyžadují nízkou míru redundance a jsou široce používány v satelitních komunikacích, mechanikách kompaktních disků a čárových kódech.

Na rozdíl od Reed-Solomonova algoritmu, který poskytuje robustnější schopnost opravy chyb, ale vyžaduje velké množství systémových zdrojů pro implementaci, BCH algoritmus získává na popularitě díky své vyšší efektivitě a schopnosti detekovat jak vysoce koncentrované, tak široce rozptýlené chyby. Další výhodou je, že techniky kódování a dekódování jsou relativně jednoduché a BCH kódy vyžadují nízkou míru redundance.

LDPC (Low Density Parity Check)

LDPC kódy, známé také jako Gallagherovy kódy na počest jejich vývojáře Roberta G. Gallaghera, jsou výkonné algoritmy pro opravu chyb, které byly poprvé navrženy v jeho doktorské práci na MIT v roce 1962, ale širšího uplatnění se dočkaly až před přibližně 10 lety. V podnikovém prostředí jsou stále častěji využívány pro svou schopnost dekódovat jak soft-bitová, tak hard-bitová data. V Gallagherově práci je kód s nízkou hustotou parity definován jako "lineární binární blok, pro který má kontrolní matice parity nízkou hustotu jedniček", což znamená, že obsahuje méně jedniček ve srovnání s nulami.

Výhody LDPC oproti jiným algoritmům:

• Nízká složitost dekódování
• Využívá při dekódování jak hard-bitové, tak soft-bitové informace z NAND flash
• Vykazuje dobré výsledky s krátkými bloky
• Dosahuje výkonu "blízkého kapacitě" s dlouhými bloky. (Blízko kapacity se vztahuje k Shannonovu limitu, což je maximální
• rychlost, kterou lze data posílat přes kanál s téměř nulovými nebo blížícími se nule chybami.)

Obrázek 4 - popis: Tannerův graf ukazuje grafickou reprezentaci LDPC kódu pro danou kontrolní matici parity v Tabulce 1 a pomáhá popsat dekódovací algoritmus. "Kontrolní uzly" představují počet paritních bitů a "Proměnné uzly" představují počet bitů v kódovém slově. Hrana spojuje bitový uzel s kontrolním uzlem pouze tehdy, pokud je bit zahrnut v kontrole parity.

Následující tabulka poskytuje srovnání ECC algoritmů probíraných v tomto článku.

S tím, jak se zmenšuje litografie NAND flash pamětí, buňky se zmenšují a ukládají více bitů na buňku, zvyšuje se hustota, ale také počet chybových bitů. Pro zajištění spolehlivosti průmyslových flash úložných produktů proto používají výrobci NAND pamětí pokročilé technologie detekce a opravy chyb.

Specifika LDPC u paměťových karet a jejich vliv na záchranu dat

Moderní paměťové karty využívající LDPC algoritmus pro opravu chyb představují významný pokrok v zabezpečení dat. Tato pokročilá technologie však současně přináší značné komplikace při snaze o záchranu dat z elektronicky poškozených flash médií.

Základním problémem při obnově dat je samotná komplexnost dekódování LDPC. Tento algoritmus pracuje se složitými matematickými operacemi, které jsou běžně zpracovávány řadičem karty. Pokud dojde k poškození řadiče, ztrácíme přístup k originálnímu dekódovacímu algoritmu. Situaci dále komplikuje fakt, že každý výrobce může implementovat vlastní variantu LDPC, což prakticky znemožňuje použití univerzálního přístupu k obnově dat.

Další významnou překážkou je závislost LDPC na specifických metadatech uložených na kartě. Tato metadata obsahují klíčové informace o struktuře kódování a parametrech použitých při zápisu dat. Při poškození oblasti, kde jsou tato metadata uložena, se šance na úspěšnou obnovu dat výrazně snižuje.

Moderní paměťové karty navíc často využívají vícevrstvé zabezpečení, kde je LDPC pouze jednou z několika úrovní. Při pokusu o obnovu dat je nutné postupně dekódovat všechny tyto vrstvy zabezpečení, a to přesně v určeném pořadí. Jakákoliv chyba v tomto procesu může celou obnovu dat zkomplikovat nebo zcela znemožnit.

Významnou roli hraje také typ dekódování, které je při obnově dat možné použít. LDPC běžně využívá takzvané soft-decision dekódování, které poskytuje lepší výsledky při opravě chyb. Pokud je však řadič karty poškozen, často máme k dispozici pouze méně efektivní hard-decision dekódování, což může vést k situaci, kdy část dat již není možné obnovit.

Vzhledem k těmto rizikům je absolutně klíčová prevence ztráty dat. Uživatelům flash pamětí jako jsou SSD, paměťové karty nebo USB flash disky se důrazně doporučuje pravidelně zálohovat svá kritická data. Při prvních příznacích nestability paměti je nutné okamžitě přestat s jejím používáním a svěřit obnovu dat specializovanému pracovišti s odpovídajícím vybavením. Vyčíst a zachránit data i ze silně nestabilní flash paměti je v profesionálních podmínkách je mnohem efektivnější, než řešit záchranu z paměti, která je již zcela netečná. Pro zvýšení šance na úspěšnou obnovu je také důležité poskytnout technikům co nejpřesnější informace o typu karty a okolnostech jejího poškození.

LDPC tak představuje dvojsečnou zbraň - na jedné straně poskytuje vynikající ochranu dat během běžného provozu, na straně druhé však významně komplikuje jejich záchranu v případě poškození karty. Tato skutečnost jen podtrhuje význam pravidelného zálohování jako nejbezpečnější strategie ochrany dat.

LDPC v praxi: Typy pamětí a nástroje pro práci s nimi

LDPC se v současnosti používá především v těchto typech paměťových zařízení:

• Enterprise SSD disky od výrobců jako Samsung (PM883, PM893), Intel (D7-P5510), Micron (7400 PRO)
• Spotřebitelské NVMe SSD zejména vyšších řad (Samsung 990 PRO, WD Black SN850X)
• Pokročilé SD karty a microSD karty UHS-II a vyšší specifikace
• Profesionální paměťové karty formátu XQD a CFexpress
• USB flash disky postavené na moderních řadičích Phison a Silicon Motion

Pro profesionální práci s těmito paměťmi existuje několik vysoce specializovaných nástrojů, bez jejichž dokonalého zvládnutí jsou snahy o záchranu dat při hardwarovém poškození NAND flash bezpředmětné:

Hardwarové nástroje pro práci s poškozenými flash pamětmi:

• Acelab PC-3000 Flash NAND Reader
• Rusolut NAND Programmers

Softwarové nástroje pro analýzu NAND flash při záchraně dat:

• ACE Laboratory SSD Tool Suite
• FlashcatUSB software suite

Je třeba poznamenat, že vzhledem k uzavřené povaze implementací LDPC u jednotlivých výrobců flash pamětí, tyto nástroje často vyžadují pravidelné aktualizace pro podporu nových zařízení a jejich specifických implementací LDPC. Většina profesionálních nástrojů také vyžaduje nejen specializované školení a certifikaci pro jejich efektivní využití, ale také průběžné vzdělávání a sledování nejnovějších trendů v oblasti NAND flash technologií.

Pracovní postupy se liší podle typu zařízení a poškození:

1. Pro poškozené SSD disky:

• Analýza firmware a mapovacích tabulek
• Obnovení nebo emulace řadiče pro přístup k datům

2. Pro nefunkční paměťové karty:

• Monolitické čtení pomocí specializovaných nástrojů
• Přímý přístup k NAND čipům pomocí specializovaných adaptérů / socketů
• Rekonstrukce metadat pro správnou interpretaci LDPC
• Využití kombinace více přístupů pro maximalizaci šance na úspěšnou obnovu

3. Pro vadné USB flash disky:

• Bypass poškozených řadičů
• Přímé čtení NAND čipů
• Rekonstrukce systému souborů