SSDのIndirection Unit (IU) (3/4)：ページマッピングの課題と対策

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

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

　[2回目](https://qiita.com/ken-yossy/items/ac4e9aa9ec628814462e)の記事では、そのブロックマッピングの課題を明らかにし、その課題を解決できるより細かいIUを用いた設計（ページマッピング）を説明しました。

　しかしこのページマッピングにも課題は存在します。

　そこで3回目となる今回の記事では、ページマッピングの課題とその課題への対策を説明します。ここまでくると、現在のSSDで採用されている間接参照方式に近づきます。

# まとめ

* ページマッピングの課題は論理アドレスと物理アドレスの対応表のサイズ増大
* IUサイズ拡大、対応表SLC配置、対応表キャッシュ導入、など様々な対策が存在
* これら対策の巧拙がデータアクセス性能や寿命を左右する

# 復習1：ブロックマッピングとは
　まずブロックマッピングの例を再掲します。

　ブロックサイズが2 MiBでページサイズが2 KiB（1ブロック1,024ページ）というNANDフラッシュメモリを使用したセクタサイズ512バイトのSSDにおけるブロックマッピングの例が図1です。

![SSDにおけるブロックマッピングの例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/37da9ce2-42f1-91f5-b543-c9a2877257c4.png "SSDにおけるブロックマッピングの例")
_図1：SSDにおけるブロックマッピングの例_

　このブロックマッピングではLBAから物理アドレスへの変換を以下のように行います。

1. LBAの上位N-12ビット（ここでは仮想ブロック番号と呼びます）を抽出する（図1では3）
1. その仮想ブロック番号で「仮想ブロック番号と物理ブロック番号の対応表」を参照してアクセス先物理ブロックを特定する（図1ではブロックK）
1. LBAの下位12ビットのうち上位10ビットからページ番号を取得する（図1では100）
1. 最後にLBAの下位2ビットからページ内オフセットを取得する（図1では1）

　この結果、アクセス先物理アドレスは「物理ブロックK、物理ページ100、オフセット1」と判明します。このように、ブロックマッピングはLBA（範囲）に対する物理ブロックの割り当てについて自由度を持ちます。

# 復習2：ページマッピングとは
　次に、ページマッピングの例としてIUがページの設計を再掲します。

　図1と同じくブロックサイズが2 MiBでページサイズが2 KiBというNANDフラッシュメモリを使用したセクタサイズ512バイトのSSDにおける、IUをNANDフラッシュメモリのページとしたページマッピングの設計例が図2です。

![SSDにおけるページマッピングの例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/730757cd-dbbf-0824-c8d5-d6360bff521d.png "SSDにおけるページマッピングの例")
_図2：SSDにおけるページマッピングの例_

　このページマッピングではLBAから物理アドレスへの変換を以下のように行います。

1. LBAの上位N-2ビット（ここでは仮想ページ番号と呼びます）を抽出する（図2では3）
1. その仮想ページ番号で「仮想ページ番号と物理ブロック番号＋物理ページ番号の対応表」を参照してアクセス先物理ブロックと物理ページを特定する（図2では「ブロックK、ページj」）
1. LBAの下位2ビットからページ内オフセットを取得する（図2では1）

　この結果、アクセス先物理アドレスは「物理ブロックK、物理ページj、オフセット1」と判明します。このように、このページマッピングはLBA（範囲）に対する物理ブロックと物理ページの割り当てについて自由度を持ちます。つまりブロックマッピングと比較して自由度が高いです。

# ページマッピングの課題は対応表のサイズ
　ページマッピングはデータの書き込みに制約を持つNANDフラッシュメモリに適した方式です。ページマッピングの採用によりSSDはより幅広いワークロードに対して高い性能を発揮できるようになりました。

　一方でページマッピングにも課題があります。それは「対応表」のサイズが大きくなることです。例として図2の対応表サイズを概算します。

　図2ではNANDフラッシュメモリのページサイズは2 KiB、セクタサイズは512バイト（2<sup>9</sup>バイト）であり、LBAの下位2ビットはページ内オフセットに使われますので、対応表の総エントリ数は総LBA数の4分の1になります。仮にSSDの容量を1 TiB（2<sup>40</sup>バイト）とし、また簡単のためユーザがアクセス可能な容量も1 TiBとすると、LBAの総数は1 TiB÷512バイト=2<sup>31</sup>個ですので、対応表の総エントリ数は2<sup>31</sup>個÷4=2<sup>29</sup>個となります。ここで対応表の1エントリが4バイトであれば、対応表の総サイズは2<sup>29</sup>個x4バイト=2<sup>31</sup>バイトつまり2 GiBとなります。この計算手順をまとめると図3のようになります。

![ページマッピングの対応表総サイズ計算方法](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/3e575127-be51-9c53-a7ac-f37d57d92f3c.png "ページマッピングの対応表総サイズ計算方法")
_図3：ページマッピングの対応表総サイズ計算方法_

　同じ設計で2 TiBや4 TiBのSSDを作ると対応表の総サイズは4 GiBや8 GiBとなります。

　比較のために、同じ条件でブロックマッピング（図1）の対応表サイズを見積もります。容量は1 TiB（2<sup>40</sup>バイト）、ブロックサイズは2 MiB（2<sup>21</sup>バイト）ですので対応表の総エントリ数は2<sup>40</sup>個÷2<sup>21</sup>=2<sup>19</sup>個となります。対応表の1エントリが4バイトであれば、対応表の総サイズは2<sup>19</sup>個x4バイト=2<sup>21</sup>バイトつまり2 MiBとなります。

　同条件での対応表の総サイズがページマッピングでは2 GiB、ブロックマッピングでは2 MiB、つまりページマッピングではブロックマッピングの1,024倍大きくなります。この具体的な数字はあくまで図1と図2に示した例の場合ですが、おおよそこのレベルでサイズに違いが生じます。この大サイズの対応表をどう扱うかがページマッピングの課題です。

# 対応表のサイズが大きいことによるデメリット
　対応表のサイズが大きいことは、データアクセス性能と寿命に影響を与えます。

　対応表のサイズが大きいと、DRAMを搭載するSSDでも対応表全体をDRAMに乗せることが難しくなります。この結果、ホストからRead要求されたLBAの物理アドレスへの変換に必要な対応表（の一部）がDRAM上に存在しないことが起こり得ます。その場合、NANDフラッシュメモリ上の対応表を読み出します。このため「対応表の読み出し」と「目的のデータの読み出し」の2回NANDフラッシュメモリへのアクセスが必要となり、データアクセス性能が低下します。

　実際には、コントローラは複数コマンドを同時並行で処理する（パイプライン処理する）などしてホストには可能な限り途切れなくデータ転送し、データアクセス性能低下を抑制します。しかし、ひとつひとつのコマンドの処理レイテンシが問われるQueue Depth (QD) = 1の条件ではこのデメリットが表面化します。

　寿命への影響は簡潔で、サイズの大きい対応表を記録する領域がNANDフラッシュメモリ内に必要となることです。SSDの電源が切られるとき、対応表はNANDフラッシュメモリに記録しなければなりません。この対応表を記録するための領域はユーザデータ用に確保する容量とは別に確保しなければなりません。つまりオーバープロビジョニング(OP)領域を削るなどして確保する必要があります。一般的に、OP領域のサイズが減るとWrite Amplification (WAF)が増えてGarbage Collection (GC)の効率が悪化しますので、寿命消費が早まりデータアクセス性能も低下します。

# 課題への対策
　ページマッピングにおいて対応表のサイズが大きくなることへの設計上の対策のひとつは、IUサイズを大きくすることです。図2の例ではIUサイズが2 KiBでしたが、これを4 KiBや16 KiBに変更すると図4 (A)および(B)のように対応表のサイズは小さくなります。

![IUサイズによるページマッピングの対応表総サイズの違い](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/439683/c7cead01-d8da-9c96-af09-ba958917fd7f.png "IUサイズによるページマッピングの対応表総サイズの違い")
_図4：IUサイズによるページマッピングの対応表総サイズの違い_

　ただし、IUサイズを大きくするとIUサイズ未満のランダムライト性能が低下します。

　データアクセス性能低下対策には「対応表をSLCで記録する」という方法があります。SLCで記録することにより、対応表のNANDフラッシュメモリからの読み出しにかかる時間を短くできます。ただし、TLC NANDを搭載したSSDでは（疑似）SLCで対応表を記録すると記憶容量を3倍消費することになるため、OP領域サイズの減少量が増えます。この課題は対応表用の高速不揮発メモリを別途搭載することでも解決できますが、この方法はコスト上なかなか選択されません。

　ほかには、優れた「対応表のキャッシュ」を導入する方法があります。Windowsなどの一般的なOSが動作するPCでは搭載するストレージへのアクセスに偏りが存在します。偏りの存在はキャッシュの効果を高めますので、このような偏りを上手く活用したキャッシュを実装することでデータアクセス性能の低下を軽減しかつ寿命の消費も抑えることができます。ただし、キャッシュにはライトバックがつきものです。つまりキャッシュから追い出された対応表の一部をNANDフラッシュメモリに書き出す処理が発生します。これはデータアクセス性能の低下と寿命消費につながります。

　この偏りをさらに積極的に活用し複数サイズのIUを組み合わせて使う方式もあります。あまりアクセスされないLBA領域は大きいIUで「粗く」管理し、頻繁にアクセスされるLBA領域は小さいIUで「細かく」管理する方式です。ただし、コントローラでの処理が複雑化しデータアクセス性能に影響を及ぼす可能性があります。

　このほかにもメーカー各社が工夫を凝らして課題への対策を講じています。

# おわりに
　今回の記事では、ブロックマッピングの課題を解決したページマッピングが抱える課題とそれに対する対策を説明しました。

　最終回となる次回は、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>の下に提供されています。