SSDのIndirection Unit (IU) (2/4)：性能と信頼性を鑑みた改良

# はじめに
　前回からNANDフラッシュメモリを不揮発メディアとするSolid State Drive（以降単にSSDと記載）の設計における重要なパラメータのひとつであるIndirection Unit (IU)の説明をしています。

　初回である[前回](https://qiita.com/ken-yossy/items/d57c12377bd50958dc67)は、SSDにおいて間接参照の導入目的が「NANDフラッシュメモリの不良ブロック回避」であることを説明し、基本的な間接参照の設計としてIUをNANDフラッシュメモリのブロックにした設計を説明しました。

　しかしこの設計はSSDの性能および信頼性の観点で大きな課題を抱えています。
 
　今回の記事では、前半でこの課題を説明し、後半でこの課題を解決した設計を説明します。

# まとめ
* ブロックマッピングはアクセスパターンにより深刻な性能低下や寿命浪費を引き起こす
* それを解決する間接参照の方法がページまで間接参照の対象とするページマッピング
* ページマッピングの導入によりSSDのランダムライト性能は改善されSSDの普及が進んだ

# 再掲：IUがブロックの設計
　前回説明したIUがブロックの設計（ブロックマッピング）を再掲します。

　例えば、ブロックサイズが2 MiBでページサイズが2 KiB（1ブロック1,024ページ）というNANDフラッシュメモリを使用したSSDにおいて、セクタサイズ512バイトで512 GiBのLBA空間に対してIUをNANDフラッシュメモリのブロックとした場合のブロックマッピングが図1です。

　図1の設計におけるIUサイズは、NANDフラッシュメモリのブロックサイズである2 MiBです。
 
![SSDにおけるブロックマッピングの具体例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/e82b012f-7e43-e066-35ee-f31dfe863b4a.png "SSDにおけるブロックマッピングの具体例")
_図1：SSDにおけるブロックマッピングの具体例_

　このブロックマッピングではLBAから物理アドレスへの変換を以下のように行います。
 
 1. LBAの上位18ビット（ここではこれを仮想ブロック番号と呼びます）を抽出し、仮想ブロック番号と物理ブロック番号の対応表を参照してアクセス先物理ブロックを特定する（図1ではブロックK）
 1. LBAの下位12ビットのうち上位10ビットからページ番号を取得する（図1では100）
 1. 最後にLBAの下位2ビットからページ内オフセットを取得する（図1では1）

　とてもシンプルな設計です。この設計は、導入目的である「不良ブロックの回避」を達成できます。

# どんなケースで何が困るのか
　そのうちに、図1のシンプルな設計がSSDの性能低下や寿命浪費を引き起こすことがわかりました。その原因は、LBAがブロック内でリニアマッピングされていることです。

　具体例を用いて説明します。簡略化のために、NANDフラッシュメモリの諸元をページサイズ2 KiB、ページ数8、つまりブロックサイズ16 KiBとし、セクタサイズは512バイトとします。ここで図1のようなブロックマッピングを導入するとブロック内オフセットはLBAの下位5ビットとなります（ブロック内にセクタが32個あるから）。LBAの残り（上位）が仮想ブロック番号です。

　仮想ブロック3に対応する物理ブロックがブロックAでまだ未書き込みのときに、ホストがLBA 0x60から8セクタ（LBA 0x67まで）のWriteを行うと図2のようになります。

![ブロックマッピングにおけるWriteの様子(1)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/c8741cb2-9946-ef02-33ea-cec3f558bd86.png "ブロックマッピングにおけるWriteの様子(1)")
_図2：ブロックマッピングにおけるWriteの様子(1)_
 
　0x60を仮想ブロック番号とブロック内オフセットに分解するとそれぞれ3と0になります。ブロック内オフセットが0ですので、図2のようにLBA 0x60に対応する記憶領域はブロックの先頭（ページ番号0のページ内オフセット0）になります。

　NANDフラッシュメモリはブロックの先頭ページからページ番号順に書き込む規則ですので、このWriteは「ページ番号0のオフセット0」というキリの良い場所からのWriteとなり、問題なく処理できます。
 
　一方Writeで指定されたLBAに対応する記憶領域がブロックの先頭ではない場合に問題が起こります。その例を示したものが図3です。

![ブロックマッピングにおけるWriteの様子(2)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/4fedea5f-4f8c-9cdc-3d20-9930af4ac143.png "ブロックマッピングにおけるWriteの様子(2)")
_図3：ブロックマッピングにおけるWriteの様子(2)_

　この図3は、図2と同様に仮想ブロック3に対応する物理ブロックがブロックAでまだ未書き込みのときに、ホストがLBA 0x64から4セクタ（LBA 0x67まで）のWriteを実施したときの様子です。

　LBA 0x64に対応する記憶領域を計算すると、ページの先頭ではありますがブロックの先頭ページではないことがわかります。このため、NANDフラッシュメモリの制約を守りながらこのWriteデータを記録するにはLBA 0x60から0x63が割り当てられたページ番号0にダミーデータを書き込まなければなりません。

　この結果、ホストからの要求は4セクタのWriteなのにNANDフラッシュメモリには8セクタのデータを書き込むことになります。わかりやすく言えばWrite Amplification Factor (WAF)が2の状態です。

　さらにマズいのは、同じブロックに記憶領域を割り当てられたLBAのデータが既に書き込まれている状態で一部のLBAだけ書きかえられたときです。

![ブロックマッピングにおけるWriteの様子(3)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/89319f47-07b5-c9da-f377-3062738e6294.png "ブロックマッピングにおけるWriteの様子(3)")
_図4：ブロックマッピングにおけるWriteの様子(3)_

　図4は、仮想ブロック番号3に割り当てられたすべてのLBAにデータが書き込まれている状態でホストからLBA 0x7BだけWriteされたときの挙動です。

　NANDフラッシュメモリの制約から、LBA 0x7Bに割り当てられた記憶領域だけを上書きすることはできず、同じブロックに記録されている書き換え対象ではないLBAのデータを別のブロックにコピーしながらLBA 0x7Bのデータのみ新しいデータを記録する、というRead-Modify-Writeをしなければなりません。

　この結果、1セクタのデータを書き込むために残りの31セクタのデータを無駄にコピーすることになります。つまりこの例でのWAFは32になります。

　これらの例はブロックマッピングに内在する課題を端的に示すものです。

# なぜこの課題が注目されたか
　前節で説明したとおり、ブロックマッピングの課題は苦手とするアクセスパターンにおいてオーバーヘッドが大きくストレージの重要な価値である性能と寿命に悪影響を与えることです。

　これらの課題が注目され始めた理由は2点です。それはNANDフラッシュメモリの技術進化とSSDが幅広く利用され始めたことです。

　NANDフラッシュメモリの技術進化としては、まずページサイズとブロックサイズの増大が挙げられます。ページサイズとブロックサイズが大きくなりひとつのブロックに記録できるデータが増えた結果、図3や図4のようなケースでのダミーデータ書き込みや無駄なコピーというオーバーヘッドが無視できなくなりました。

　そしてTLC NANDの登場も重要です。TLC NANDの登場は上記ページサイズとブロックサイズの増大にも影響を与えています。加えてTLC NANDはSLC NANDやMLC NANDと比較して書き換え回数が少ないため、その書き換え回数を有効に活用して長い寿命を実現するには図3や図4のような無駄な書き込みをできるだけ減らす必要があります。

　一方SSDが幅広く利用され始めたこととは、ノートPCなどの起動ドライブとして使用され始めたことを指します。それまでNANDフラッシュメモリベースのストレージの主な用途は画像データなどを記録するデータドライブでした。しかしPCの起動ドライブにはシステムデータが記録され一時データやユーザが作成した細かいファイルも記録されます。SSDをPCの起動ドライブに使用することで図3や図4で示したような書き込みが頻繁に発生しました。

# より細かいIUの導入
　このブロックマッピングが抱える欠点の解決には、間接参照の単位つまりIUにブロックよりも粒度の細かいものを使う、という方法が採られました。具体的には、NANDフラッシュメモリのページや、ホストがデータを指定するときに使用するセクタなどがIUの候補になりました。

　ここではIUにページを使う例を説明します。ページもしくはページサイズ未満の単位をIUに使用する設計は「ページマッピング」と呼ばれることがあります。この記事ではそれらをまとめて「ページマッピング」と呼びます。

　NANDフラッシュメモリのページサイズを2 KiB、セクタサイズを512バイトとした場合、IUをNANDフラッシュメモリのページとしたページマッピングの設計例は図5のようになります。

![間接参照の単位(IU)をページとしたページマッピングの例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/a6585563-7c0a-3f15-9d73-145c92810dd6.png "間接参照の単位(IU)をページとしたページマッピングの例")
_図5：間接参照の単位(IU)をページとしたページマッピングの例_

　図1と図5を比較すると、図1（ブロックマッピング）ではLBAの一部をそのままアクセス先ページ番号とページ内オフセットに使用するのに対し、図5（ページマッピング）ではページ内オフセットにのみ使用します。

　ページマッピングでは、LBAのうちページ内オフセットを除いた部分（ここでは「仮想ページ番号」と呼びます）を使用してテーブルを参照し、物理ブロック番号と物理ページ番号を取得します。

　図5の例では、LBAから仮想ページ番号を抽出し、その番号で「仮想ページ番号と物理ブロック番号＋物理ページ番号の対応表」を参照します。その結果として得られた「ブロックK、ページj」の、LBAから取得したオフセット1がアクセス先となります。

　SSDに間接参照を導入した目的は不良ブロックを避けるためでした。このページマッピングでも、LBAからアクセス先の物理ブロック番号を特定する際にテーブルを参照していますので、このテーブルの物理ブロックに不良ブロックを登録しないようにすることで前記目的が達成できます。

　ページマッピングではブロックだけでなくページまで間接参照の対象にすることで、ブロックマッピングよりも柔軟にLBAに対して記憶領域を割り当てることができます。

# ページマッピングでの書き込み処理
　最後に、このページマッピングがブロックマッピングの課題を解決していることを示します。

　図6は、図2から図4と同じくページサイズ2 KiB、ブロック内ページ数8、セクタサイズ512バイトというSSDにおいて、ページマッピングを導入した例です。
 
![ページマッピングにおけるWrite処理の例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/dd32daa4-3602-5a95-41fd-fdb5d13f281e.png "ページマッピングにおけるWrite処理の例")
_図6：ページマッピングにおけるWrite処理の例_

　まだ何も書き込まれていないブロックAが書き込み先ブロックとして選択されている状態でホストがLBA 0x64から0x67までの4セクタのWriteを要求したとします。すると、SSDはWriteされたデータをブロックAのページ0に書き込んでテーブルを更新します。

　テーブルの更新とは、具体的にはLBA 0x64からページ内オフセットである下位2ビットを取り除いて（LBAを2ビット右シフトして）得られた19番のエントリに「ブロックA、ページ0」と記入することを指します。

　図3では同じWriteで1ページ分の余計な書き込みが発生していましたので、この時点でブロックマッピングと比べて効率改善が見られます。

　その後ホストがLBA 0x7BのWriteを要求したとします。このとき、LBA 0x7Bと同じページに書き込まなければならないデータが既に書き込まれていればそれをコピーし、ホストから受領したLBA 0x7BのデータとまとめてブロックAのページ1に書き込みます。いわゆるRead-Modify-Writeになります。

　そして再びテーブルを更新します。LBA 0x7Bから仮想ページ番号を求めると30（16進数で0x1E）になりますので、今度はテーブルの30番のエントリに「ブロックA、ページ1」と記入します。これで書き込み処理完了です。

　図4では同じケースでWAFが32になりましたが、この図6ではWAFは4であり寿命消費の度合いが大きく抑制されています。

# おわりに
　この記事では、SSDにおける間接参照の仕組みのひとつであるブロックマッピングの課題と、その課題を解決可能なページマッピングとその仕組みを説明しました。

　このページマッピングが導入されるようになり、SSDのランダムライト性能が改善され、SSDの利用がより進みました。

　ただページマッピングも良いことばかりではなく課題を抱えています。次回はページマッピングの課題や解決する工夫、そしてブロックマッピングとの比較などを説明します。

# ライセンス表記
<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/88x31.png" /></a><br />この記事は<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">クリエイティブ・コモンズ 表示 - 継承 4.0 国際 ライセンス</a>の下に提供されています。