はじめに

最近はSSDが広まってきたため語られることが増えてきたものの、以前はそうでもなかったような、そんなフラッシュメモリにまつわる話をこのへんでプログラマ視点でまとめておこうと思う。

技術的な話というよりポエム感がでているかもしれない。内容がLinuxにかたよっているかもしれない。

FTLとMTD

HDDと比較するとフラッシュメモリは以下のような点が異なる。

read, writeはページ単位で行う
通常はwriteは上書きできない
writeしなおすためには一度eraseをする必要がある
eraseはブロック単位で行う
今時のMLC NANDだと、ページは8KiBでブロックが512KiBとかそんなオーダ、

NORはランダムreadできる(でも最近はSPI接続だよねぇ)、ビットを寝かす方向なら上書きwriteできる(でもECCが高度化する今時のNANDではやらないよねぇ)、とか細かい話はあるかもしれない。

こういう違いがあるので、これをOSからそのまま扱えるようにしたのがLinuxのMTD(Memory Technology Device)で、こんな面倒な処理をすべてデバイス側に押しやりこれまでのHDDと同じように使えるようにしたのがFTL(Flash Translation Layer)となる。FTLは具体的には、SSD/eMMC/USBメモリ/SDカードなど。

kernel/Documentation/mtdに一応ドキュメントがあるが、あまりきちんとはしていない。むしろkernel/Documentation/filesystems/ubifs.txtの出だしのほうがちゃんと書いてあるぞ...やはりkernelの中のドキュメントよりLinuxのMTDのページのほうがよい。

NANDフラッシュメモリのプログラミングモデル

1つのNANDフラッシュメモリは、複数のブロックからなる
1つのブロックは、複数のページからなる
readは1ページ単位で行う
writeは1ページ単位で行う
eraseは1ブロック単位で行う

が基本となる。これらに、Badblockを判定できるようにしたり、ECCでビットエラーの訂正をしたり、冗長領域を読めるようにしたり、といったことを加えて行う。

適当に落ちてたデータシートだと、ページサイズ2KiB、ページごとの冗長領域64バイト、1ブロックあたり64ページ(128KiB)、トータル2048ブロック(256MiB)となっている。SLCの小容量だからこんなもんだけど、MLCの大容量だとこれの2倍とか4倍とかになる。

Badblock

NANDフラッシュメモリは歩留まりを上げるため、正常に使えないブロック(=Badblock)を仕様として許容している。多くても全体の2%程度、たいていは0.5%以下程度の数のブロックがBadblockになっている。

Badblockはreadもwriteもeraseも正常にできない(エラーになるようNANDフラッシュメモリにプログラムしている場合が多い)。Badblockは使い物にならないので、容量やデータの保存位置を使う側のソフトウェアで考慮しなければいけない。つまりプログラマが設計しないといけない。フラッシュメモリメーカの特許にも関わるため、詳細は割愛する。お手軽には、パーティショニングするときに容量多めになるようにし、読むときはBadblockがあるとそこをスキップして次のブロックに続きがあるものとするやり方となる。

ECCエラー訂正

NANDフラッシュメモリは微細化多値化をすすめるため、データがビット単位でちょっと化けるのを仕様として許容している。世代やSLC/MLC/TLCやに依存するものの、1bitなんてのははるか昔の話、今時のMLCだと3桁ビットも当たり前となっている。詳しくは後のWearLevelingで書くが、何度もeraseしたブロックほどビット化けしやすくなる。

ビット化けに対処するため、ECCと呼ばれる冗長なビット列をデータと一緒にwrite/readしている。read時にデータとECCから計算してデータが化けていないことの確認や化けたデータの訂正をしている。冗長なECCビット列を書き込むため、通常NANDフラッシュメモリはページごとに冗長領域(extraとかoobとも呼ばれる)を別途持っている。

1bit程度であればハミング符号でも十分だが、2桁3桁ビットともなればBCH符号(リードソロモンを一般化したやつ)やさらに高度なものが必要となる。また、read/writeのたびに計算が必要になるので、スループット向上のために計算も訂正もコントローラ(NANDフラッシュメモリと接続するインタフェース)側で持つものが当たり前になっている。

ECCの処理はハードで行うのが今時なので、プログラマがここに直接関わることは少ない。が、正しく訂正できたのかどうかや訂正不能なほど化けていた場合の処理、訂正なしにビット化けも含むありのままを読み書きする、といったことの管理が必要になる。

WearLeveling

NANDフラッシュメモリは寿命(ライフサイクル)を向上させるために、ビット化けは進行性であることを仕様としている。つまり、長く使うほどどんどん化けやすくなっていくものだとしている。

寿命問題

特に、eraseした回数によりブロックがビット化けしやすくなる。世代やSLC/MLC/TLCやECCの訂正能力に依存するが、おおむね、SLCだと5桁、MLCだと4桁、TLCだと3桁、が実ユースケースでのeraseしてよい回数のオーダとなる。この回数のことをendurance(エンデュランス)と呼ぶ。

eraseによる劣化はブロックの単位で蓄積するため、理想的にはNANDフラッシュチップの中のブロックを順にまんべんなくeraseするような使い方が望ましい。しかし深く考えずに設計すると大抵の場合は特定のエリアのブロックにeraseが集中することになる。そこで、ユースケースに依存せずにまんべんなくeraseするようなブロックのマッピングを行うアルゴリズムが必要になる。これをWearLeveling(ウェアレベリング)という。

先の通り、eraseしないとwriteできないので、eraseの制限回数はwriteの制限回数におおむね等しい。理想的にWearLevelingできていると仮定しても、全ブロックを制限回数ぎりぎりまでeraseするところまでが限界なので、ここから、writeできる量の上限が決まる。よくSSDで寿命が書き込み量で表されるのはこのような理由からとなる。

プログラマとしてはまずWearLevelingアルゴリズムの実装が求められる。LinuxだととりあえずUBIを使っておけばある程度はなんとかなると思う。その上で、プログラマにはNANDフラッシュメモリの寿命が製品寿命を下回っていないかの確認が求められ、おおむね書き込み量の見積もりを行うことになる。

さらに、enduranceの目安に達していなくてもerase,write直後にすぐに醜いほどビット化けするブロックが出てくることもある。出荷時からのBadblockに対してこういうブロックを後発Badblockとも呼ぶ。初期Badblockだけでなく後発Badblockも考えて、容量に余裕を持たせつつ代替処理も考慮しないといけない。

Retension

NANDフラッシュメモリは一度writeしたものでも長い時間が経過するとビット化けすることを仕様としている。もっと簡単に言うと、USBメモリ/SDカードを1年間ほうっておくと中のデータが消える。

実力はともかく保証のレベルでは1年も持てばいい方のオーダになる。またこの期間も一般的にerase回数に応じて加速度的に悪化する。この「writeしてからどのくらいの期間が過ぎてもデータを正しくreadできるか」のことをRetension(リテンション)と呼ぶ。

このRetensionの対策のため、一般的に「時々関係ないところも含めてNANDフラッシュメモリの全体をreadする」ようソフトを組む。readしたときにECC訂正したビット数から危険度を判断し、場合によっては該当ブロックの書き直し処理をする。Retensionは電源入れずに放置していても進行するため、「時々」をどう担保するのかがプログラマからすると面倒だ。あまりreadしすぎると次の「Disturb」の問題を進行させてしまう。

Retensionは温度によっても変わり、一般的に高温なほど進行が早くなる。「半導体だからHDDに比べて熱に強い」とか言われることもあるが、Retensionを考えるととてもそんなことは言えない。

Disturb

NANDフラッシュメモリはreadを繰り返すだけでもeraseほどではないにしろセルに負荷をかける。先のようにeraseには制限回数があるので注意するが、readはそこまで極端ではないのであまり注意されないこともあり、過度にreadを繰り返してビット化けを起こす危険がある。

readすると該当するページに負荷がかかるのはもちろんのこと、col/rawの電圧を共有している別のページや隣接するブロックにも負荷がかかる。readしているページはそこでECCエラーを確認するので問題あればすぐに書き直しができるが、隣のページやブロックはreadしていないのでどれだけエラーが出ているかもわからない。この点でも、Retensionの箇所に書いたような「時々関係ないところも含めてNANDフラッシュメモリの全体をreadする」処理が必要となる。一度writeしたものをreadの対象ページじゃないものも含めて周辺箇所を何回までreadしてよいかのことをread Disturb(ディスターブ)と呼ぶ。

Disturbによる化けはRetensionと同じく書き直せば解決する。しかし、過度に書き換えるとenduranceの寿命問題を悪化させる。バランスを取った「時々read」をする必要がある。

フラッシュファイルシステム

フラッシュメモリをMTDとして抽象化しても、実ユースではやはりファイルシステムが必要になる。MTD上で動くよう設計されたファイルシステムのことをフラッシュファイルシステムと呼ぶ。

歴史的には、jffs -> jffs2 -> logfs -> ubifs と順により最近の複雑なものとなる。jffs/jffs2時代にはyaffs/yaffs2というのもあったが、もうしわけないあまり詳しくはない。

log-structured

上書きwriteできず、また大きな単位のeraseが必要であるというフラッシュメモリの特性から、フラッシュファイルシステムはlog-structuredと呼ばれる設計に偏重している。単純に言うと、インクリメンタルで追記オンリーな形でwriteしておき、古いものから順にGarbedgeColloectしてeraseしていく。低容量であまり早くなくてもよい2000年半ばまでの組み込み用途で次第に使われるようになった。

log-structuredな構造は、eraseに時間がかかり小容量で組み込みのような電源断のある用途には適していた。が、インデックスがない(全体を読まないとファイルシステムツリーが完成しない)、小さいwriteを繰り返すと断片化して速度低下する、比較的RAMを多く使う、パーティションサイズに対して性能がスケールしない、といった問題を抱えていた。

時代はすすみ、スマホ黎明期(2007年前後)くらいになってくると、次第に大容量で早さも求められるようになっていく。またちょうどこの頃からNANDフラッシュメモリのビット化けや寿命問題も大きくなってきて、log-structuredなだけのファイルシステム(特にJFFS2)では限界になっていく。

Wandering tree

問題を解決するためにLogFS(初期はjffs3とも呼ばれていた)が作られた。LogFSでは目新しいアイディアとしてWandering treeが提唱された。

Wandering treeについてはNOKIAのUBIFSの資料の34ページ目がわかりやすい。rootとなるinodeからのファイルシステムツリーを変更に対して定期的に書き込む。あるファイルに変更があるとそれは追記式に新しい位置に書き込まれ、そのファイルへのpath上にあるディレクトリは新しいディレクトリエントリを指すように葉から根へと逆順にrootまで同様に変更が追記式に書かれ、最後に新しいrootのinodeへのポインタを書き換える、という言葉では伝えにくいことやっている。

Wandering treeの考え方はUBIFSへと引き継がれていくも、LogFSはあまり広く使われることはなく、logfs.orgのドメインも期限が切れて、ついにLinux-4.10でLogFSそのものがツリーから消された。

UBI

LogFSの代わりに広まったのがUBIFS。おそらくドキュメントがしっかりしていてツールも整備され、またNOKIAが取り組んでいる(2008年ごろのNOKIAは端末数で世界シェアNo.1)のもあって広まった。UBIFSは現実的に使えるようにするため泥臭い設計をあえて取り込んだりしている点もあるが、一番大きい点は、これまでのフラッシュファイルシステムをUBIとUBIFSとの2つに分けたところだと思う。

UBIはMTDの上に作られる論的なボリューム。BadblockとWearLevelingの2つを一手に担う層として構築する。1ブロック当たりおおむね64ページあるNANDフラッシュメモリのうちの2ページを用いて、erase回数とブロックのマッピング(物理ブロック位置と論理ブロック位置の変換)を管理する。またBadblockがあるかもしれないという前提でUBI層は必要とするサイズより多めのパーティションサイズとしておく。こうすることで、UBI上に構築されるモジュールがBadblockとWearLevelingを意識しなくても済むようにしている。

UBIはLVMと比較されることもある。LVMはブロックデバイス上に構築する論理的なブロック層で、あとからLVM上のボリュームを追加したり削除したりが柔軟にできるようになっている。UBIはMTD上に構築する論理的なMTDで、あとからUBIのボリュームを追加したり削除したりが柔軟にできるようになっている。

UBIの上にUBIFSを載せることが多いが、既存のMTD上に載せるようなものも含めて一緒に大きなUBIの上に載せることで、効率的なWearLevelingを行えるようになる。ただし、起動時のUBIボリュームのattachやUBI層の容量的なオーバヘッドとのトレードオフになる。

UBIFS

「美しい設計」とは言い難いものの、面倒な処理をUBIに追い出せたおかげで、見通しのよい設計になっている。master node, orphan, LPT, journalなどの役割に応じたブロックを論理的に固定の位置に配置することで役割分担がしっかりしている。LogFSのWandering treeをベースにしつつも、頻繁にindexを書くことはせずに、多くをjournalとして書き込む設計になっている。こうすることで100MiBを超えるようなパーティションのサイズでもうまく動くように作られている。

ただ、UBIを用いたりUBIFSの中でブロックごとに役割分担が分かれていることもあり、小容量のパーティションには向かない。NANDフラッシュメモリのブロックサイズにも寄るが、最低でも10MiBくらいはないとまともに使えない。

そしてeMMC/SD/SSDへ

MLC/TLCと発展するNANDフラッシュメモリ、巨大化する一方のページサイズ・ブロックサイズ、増え続けて複雑化し続けるECCとビット訂正、電源断対策を複雑にするshared pages問題、などにより、もはやNANDフラッシュメモリをRawのまま汎用に扱うことが近年は難しくなった。またSSDのように、単に扱うのではなくread/writeの性能を極限まで引き上げることも求められてきた。その結果、容量増加・性能向上の必要がなくなったような一部用途を除き、たいていのものはFTLへと流れた。

PCの世界ではSSDだが、これまでRawなフラッシュメモリを扱ってきたような製品では今はeMMCが圧巻している。またraspberry piやスマホのように、大容量への要望とコストとの兼ね合いから、付属するストレージは最低限として外付けのMicroSDカードに頼り切っているものも多い。

ただ、FTLとしてデバイス側に追いやったとしても、結局デバイスの中では上記で述べてきたようなことをファームウェアが行っていることに変わりはない。電源入れて定期的にreadをしないとRetension問題が起こる。高温の場所に放置するとあっという間にデータが消える。高負荷にwriteが走るサーバでは、頻繁なwriteがendurance問題を起こしつつも、逆に頻繁にwriteしないとすぐにRetension問題を起こしてデータが読めなくなるという、一見すると矛盾したようなことが起こる。

そういった面倒なことをユーザが考えなくても済むように日々FTLデバイスのメーカはファームウェアの開発に力を入れている。そうに違いない、はず、きっと、たぶん、そうかもしれない。

あとがき

F2FSの詳細をまとめておこうと書き始めて「log-structured」「Wandering tree」なキーワードが出てきて既視感を覚えながらカキコしてたらどんどん横にそれる話になってしまったので、タイトル変更して書き直したのがこ記事です。正確さの点やら物性・電気電子の観点からはツッコミどころが多いかもしれないけど、プログラマ視点からだとそれほど間違ったことは書いてないと信じている。

プログラマのためのフラッシュメモリ入門