はじめに
これまでNANDフラッシュメモリを不揮発性記憶媒体として使用するSolid State Drive（以降SSDと記載）が備える機能のひとつとして「SLCキャッシュ」を取り上げ、SLCキャッシュを上手く使うためのノウハウをまとめてきました。
最後となる今回は「SLCキャッシュからのデータ追い出しアルゴリズム」の視点でまとめます。
まとめ
- SLCキャッシュから追い出すデータを決めるときはまず追い出すブロックを選択している
- そのブロック選択アルゴリズムにはFIFOやLRUそして有効データ数によるものがあり、それらはデータの空間的および時間的局所性や処理の効率を基準とするもの
- ユーザがデータに空間的および時間的局所性を持たせる書き込みを行うにはシーケンシャルライトするのが一番の近道
【再掲】SLCキャッシュの制御方式
代表的な「SLCキャッシュの制御方式」を再掲します。
SLCキャッシュの挙動を特徴づける項目には大きく4つあります。それは、容量、データ、追い出し処理の契機、そして追い出しアルゴリズム、です。
この記事では代表的なものを示します。ここに示した項目や方式以外にも、各メーカーおよび製品に特有の項目の存在や方式の実装が考えられます。その場合、SLCキャッシュの特性も変化します。
表：SLCキャッシュの動作を特徴づける項目と代表的な制御方式
| 項目 | 代表的な方式 | 概要 |
|---|---|---|
| 容量 | 静的 | 静的に容量を確保して運用 |
| 動的 | データ量に応じて容量を増減 | |
| 記録データ | 何でも | 区別なし |
| 小サイズのみ | 一定サイズ未満 | |
| 特定データのみ | 何らかの法則で決定 | |
| 追い出し契機 | 容量 | （残）容量のみで判断 |
| アイドル時 | アイドル時に積極的に実施 | |
| 追い出しアルゴリズム | Least Recently Used (LRU) | アクセス頻度が少ない順 |
| First-In-First-Out (FIFO) | 記録された時刻が古い順 |
この表に記載した項目のうち今回は「追い出しアルゴリズム」に注目します。
追い出しアルゴリズムとは
SLCキャッシュ用の記録領域を空けることを目的としてSLCキャッシュに記録されているデータを多値記録領域にコピーすることをここでは「追い出し」と呼ぶこととします。
この追い出しのアルゴリズムは主に「どのデータを多値記録領域にコピーするか」の決めかたを指します。これにはデータの時間的局所性や空間的局所性を利用するものがあります。
今回の記事では、このアルゴリズムと、それを上手く利用してSLCキャッシュ適用時の高い性能や寿命消費速度の緩和効果を得る方法を説明します。
なお、このアルゴリズムはSSDの性能と寿命消費に大きな影響を与えるため、実製品ではSSDメーカー各社がひとつではなく複数のアルゴリズムを組み合わる、状況に応じて使い分ける、などの工夫をしているものです。このため、ここで説明した仕組みや動作がそのまま当てはまるものではないことをご了承ください。
その1：ブロック選択アルゴリズムがFIFO
上の表では「追い出しアルゴリズム」としてLRUとFIFOを挙げましたが、「追い出すデータを選択するアルゴリズム」はSSDでは単純なLRUやFIFOとは異なります。
というのは、追い出し処理はNANDフラッシュメモリの消去単位であるブロックの単位で処理する必要があり、まず追い出すブロックを選択する必要があるからです。
この「追い出すブロックの選択アルゴリズム」にもLRUやFIFOが使われます。
そこでまずは比較的簡単なFIFOによる選択方法を説明します。
図1は、NANDフラッシュメモリのブロックレベルで見たSLCキャッシュの典型的な管理方法です。
図1：SLCキャッシュにおけるブロック管理のイメージ
SLCキャッシュを構成するブロックにホストから受領したWriteデータを記録していきブロックが満杯になると、そのブロックを、SLCキャッシュを構成する（書き込み済み）ブロックキューの末尾に追加します。
SLCキャッシュの容量が満杯に達したなどの理由でSLCキャッシュ内のデータを多値記録領域に移動させる際、このキューの先頭ブロックを選択します。そして選択したブロックに記録されている有効データを多値記録領域にコピーします。このコピーによりSLCキャッシュから選択したコピー元ブロックは消去可能となり、SLCキャッシュの容量を空けることができます。
この図1においてブロックキューの中でブロックの並び替えをしなければ、キューの先頭ブロックはキューに追加された時刻が最も古いブロックとなり、この「追い出すブロックの選択アルゴリズム」はFIFOとなります。
ただし、選択されたブロックから多値記録領域に追い出されるデータの選択アルゴリズムは、実はFIFOではなくWriteに関するLRUとなる（自動的にそうなる）ことに注意が必要です。
というのは、上書きにより無効化されたデータはコピーしないからです。無効化されているということは、このブロックがSLCキャッシュのブロックキューに滞留している間に「上書きされた」つまり無効化されたデータと同じLBAに対してWriteされた（アクセスされた）ことを示します。「最近アクセスされたことを理由に選択順位を下げる」仕組みはまさにLRUです。
ブロック選択アルゴリズムに簡潔なFIFOを使用し、多値記録領域にコピーするデータの選択にはLRUを適用することで、管理コストやオーバーヘッドを抑えながらデータの時間的局所性を活用して多値記録領域にコピーするデータを選択する方法と言えます。
その2：ブロック選択アルゴリズムがLRU
前節で追い出すブロック選択アルゴリズムがFIFOの場合を説明しましたが、追い出すブロックの選択アルゴリズムにLRUを使う方法もあります。
LRUの場合、ホストからWriteもしくはReadでアクセスされたデータがSLCキャッシュに記録されていたときに、当該データを含むブロックを、SLCキャッシュを構成するブロックのキューの末尾に繋ぎなおします（図2）。
図2：追い出すブロックの選択アルゴリズムがLRUとなる例
同じブロックに記録されているデータには時間的局所性がありますので、あるブロックに記録されているデータが上書きされたということは同じブロックに記録されているデータは近い将来アクセスされる可能性がある、と言えます。この繋ぎかえはこの性質を利用したものです。
この結果SLCキャッシュを構成するブロックのキューはLRUで整列し、ブロックキューの先頭ブロックに記録されているデータは本当の意味で「最近全くアクセスされていないもしくはアクセスされないであろうデータ」のみとなります。
SLCキャッシュを構成するブロックのキューの中でブロックの繋ぎかえが必要になる分だけ管理コストが増える一方で、時間的局所性を最大限活用してデータを選択する方法と言えます。
その3：ブロック選択アルゴリズムが有効データ数
ここまではSLCキャッシュを構成するブロックやそれらブロックに記録されたデータの特性を活用した選択方法を説明しました。これとは異なる選択方法もあります。そのひとつがブロック内有効データ数による選択です。
図3：ブロックの有効データ数による選択アルゴリズム
図3の例では、ブロックキューの先頭にあるブロックEよりもキューの中程にあるブロックCのほうがブロックに記録されている有効データ数が少ないです。このとき、この選択アルゴリズムでは追い出し対象ブロックにブロックCを選択します。
有効データ数を基準に選択する理由は、コピーするデータ数を減らすことでWAFの改善（低下）が期待でき、ひいては寿命消費の抑制に繋がるからです。
SLCキャッシュからの追い出しによる多値記録領域へのデータコピーは、SSDの寿命の観点ではできるだけ避けたい処理です。加えて、少ないコピーデータ数で空き領域を増やせれば、コピー処理による性能低下度合いも低減できます。 これらの点からこの基準はとても重要です。
確率的には、同じ性質のアクセスが続いている限りSLCキャッシュのブロックキューでは古いブロックのほうが新しいブロックより有効データ数が少なくなります。例えばランダムアクセスならランダムアクセスが続いていればそのようになります。
しかし、何らかの理由でアクセスの性質が途中で変化した場合、それを起点として図3のように有効データ数の分布の規則性が崩れます。
この方法は、そのような事象が起きた場合でも「寿命」への影響をできるだけ抑えるための方法と言えます。
この選択アルゴリズムの実現には、各ブロック内の有効データ数の管理が必要となります。また、検索処理を避けるためには有効データ数を基準にして整列した構造（リストやキュー）を作成する必要もあります（適宜並び替えも必要）。このアルゴリズムのメリットと管理コストのバランスを取ることが、製品設計上の重要なポイントになります。
その4：巻き添え追い出し
ここまで主に追い出すブロックの選択アルゴリズムを説明しましたが、追い出すデータを個別に選択するアルゴリズムも存在します。その例が「巻き添え追い出し」（勝手に命名）です。
このアルゴリズムは、これまで説明したアルゴリズムで追い出し対象のブロックを選択した後に、選択されたブロックに記録されているデータ（実際にコピーするデータ）と空間的局所性を持つデータを追加で選択する、というものです（図4）。
図4：巻き添え追い出しのイメージ（図中の番号はLBAのイメージ）
図4は、追い出し対象ブロックとしてブロックEが選ばれた状況です。このとき、ブロックEに記録されている有効データ1の巻き添えとしてブロックDに記録されている有効データ2、3、4とブロックCに記録されている有効データ5も追い出す、というのが巻き添え追い出しです。
空間的局所性の計算にはLBA空間上の距離を使用することが多いです。例えば、追い出し対象データとLBAが8離れたデータまで巻き添えで追い出す、などです。
このアルゴリズムは空間的局所性を活用するという点でその根拠とメリットはわかりやすいものの、実現にはSLCキャッシュに記録されているデータの検索もしくは検索コストを抑えるデータ構造とその維持が必要になるため性能向上の阻害要因になりやすく、SSDにとても高い性能が求められる最近ではあまり利用されていないと思われます。
上手な利用方法
これまで4つの追い出しデータ（ブロック）選択アルゴリズムを説明しました。全てのアルゴリズムがSLCキャッシュ内に記録されているデータが持つ空間的および時間的局所性をベースにしている点がポイントです。
SSDが空間的および時間的局所性を利用しているならば、ホスト側もこの性質を利用するのがベストです。ホスト側がこの性質を意識することでSLCキャッシュに記録されるデータがこの性質を持つことになり、SSDがこの性質を利用したアルゴリズムを用いればその意図に沿うデータが低コストで選択できるからです。
ホストがこれらの性質を意識した書き込みを行うにはシーケンシャルライトすることが一番の近道です。本当にLBAが連続していなくても、近いLBAのデータが近い時刻に書き込まれることで実現可能です。
一方、ランダムライトは空間的局所性がありませんので避けたほうが良いです。最も避けるべきはドライブ全域ランダムライトです。このアクセスパターンには空間的局所性に加え時間的局所性もありませんので、SLCキャッシュが一番苦手なパターンです。ただ、SLCキャッシュの容量と比べて小さい（狭い）LBA空間内でのランダムライトであれば性能低下は多少緩和されます。
そして、できる限り単一のアクセスパターンで書き込むと良いです。シーケンシャルライトならシーケンシャルライト、ランダムライトならランダムライトを続ける、極論すればアクセスパターン専用のドライブを割り当てることが理想です。例えば、ストリーミングデータやゲームデータを記録するドライブと頻繁に書き換える細かいテキストファイルなどを記録するドライブを分離する、などです。
おわりに
この記事では、SLCキャッシュからデータを追い出す際の「追い出しデータの選択アルゴリズム」の視点で見たSLCキャッシュの活用方法をまとめました。
SSDの場合、追い出しデータの選択は追い出しブロックの選択から始まることを説明し、その追い出しブロックの選択アルゴリズムには空間的および時間的局所性という基本的な性質に基づいたものがあることを説明しました。具体例としてFIFOやLRUそして有効データ数によるアルゴリズムを挙げました。
実際の製品では、性能や寿命消費の観点から各メーカーが選択方法の組み合わせや各選択方法のパラメータ調整などを実施しています。それらは各メーカーのノウハウですのでユーザが詳細な挙動を知ることはまず無理です。
加えて、OSやファイルシステムが存在する環境ではSSDへのアクセスパターン（シーケンシャルなのかそれともランダムなのかなど）をユーザが意識することや操作することは難しいです。
しかし、例として挙げたドライブ分離などできるだけ望ましい状況を作り出す工夫は可能です。それらの工夫はSSDの性能を引き出すことや寿命の有効活用に繋がりますので、システム設計時やPCを組む前の段階で是非検討してみてください。
ライセンス表記
この記事はクリエイティブ・コモンズ 表示 - 継承 4.0 国際 ライセンスの下に提供されています。