書換え耐性が低いNAND flashメモリはどう使えばいいのか　LRU-kを応用した、Frozen Dataを区別するアルゴリズム

自己紹介と発表の動機

Shinpei Matsuda氏：「書換え耐性が低いNAND flashメモリ向けのキャッシュアルゴリズム」と題してMatsudaから発表します。

最初に簡単な自己紹介と、個人的な動機について話します。専門は半導体のデバイス、特にトランジスタの物理で、ITエンジニアではありません。研究したいことがあったので退職D進（※退職後、大学院に進学すること）しましたが、その研究所から「あなたの研究計画書は現実的ではありません」と言われました。渋々NAND flashメモリのコントローラーの研究を行いましたが話が合わなすぎて退学しました。

その時に思い付いたアイデアをどこかに出したいと思って学会に投稿もしましたが、いろいろあって話すことができず、そのアイデアの供養として話したいと思いました。

書き換え回数が低いメモリを液体窒素なしでどう使えばいいのか

人類が生み出すデータが指数関数的に増加していることが問題になっていて、ハードディスクを置き換えるかたちで、NAND flashメモリの普及が進んでいます。NAND flashメモリは今後も重要なメインストレージデバイスであり続けると思われ、高密度化においては多値化という技術が非常に重要です。

NAND flashメモリも当初は0か1の1ビットしか保存できませんでしたが、1、2、3、4の4つのレベルを書き込む「マルチレベルセル」という技術が生まれました。この高密度化がどんどん進み、今は4bit/cellまで保存できます。

この多値化によって高密度化が達成されましたが、同時にメモリセルの書き換え可能な回数がどんどん減っているという問題があります。今の市場に出ている4bit/cellでは、1,000回しか書き換えることができず、これが6bit/cellまでいくと100回以下になってしまうだろうと言われています。

液体窒素で1,000回まで増やそうという提案もされていますが、この書き換え回数が少ないメモリを液体窒素なしでどうやって使いこなせばいいかというのは技術的な課題なわけです。

大半のデータはほとんどアクセスされないFrozen Data

そこでまず、メモリアクセスの統計的な性質に注目しました。（スライドを示して）こちらに示したのはストレージへのトレースファイルです。アクセス履歴をまとめたファイルを解析して、左からアクセスの多い順に並べて、縦軸にそのアクセス回数をプロットしたものです。

見てわかるとおり、アクセスが集中しているのはごく一部のページです。この例では、46パーセントのデータは週に一度しかアクセスされないFrozen Dataです。少し脱線しますが、この分布はZipfian分布やZipfの法則と言われている統計的な分布に従うことが知られています。

Zipfain分布は、メモリアクセス以外にも自然言語の単語の出現回数など、いろいろなところで出てきます。

先ほど述べたとおり、大半のデータはほとんどアクセスされないので、書き換え耐性が低いメモリであったとしても、ほとんどアクセスされないFrozen Dataの保存専用のメモリとして使えばいいということになります。

ただ、すべてを書き換え耐性が低いメモリだけで構成すると、一部の書き換えが多いところで何度も書き換えられてメモリが使えなくなってしまうので、複数の種類のNAND flashメモリを組み合わせてストレージとして使えないかと考えました。構成としては、ごく一部のアクセスが集中しているところをSLCのキャッシュで吸収して、Frozen Dataは書き換え耐性が低いメモリに入れます。それ以外はTLCなど、ある程度書き換え耐性のあるメモリに入れるということを考えました。

Level2のキャッシュ構成にした時の懸念

（スライドを示して）素直にLevel2のキャッシュを組んだ場合がこちらです。この構成にすることで、書き換え耐性の低いメモリの書き換え回数が抑えられると思われますが、同時に1つの問題が考えられます。このストレージにFrozen Dataが入ってきた場合、最初はL1キャッシュに書き込まれ、そのあとL2キャッシュになって下位のメモリ（書き換え耐性の低いメモリ）に落ちるわけです。

L2キャッシュは通り過ぎるだけなので、余計なことをしています。さらにL1、L2キャッシュにおいてFrozen Dataを書き込んでしまうと、NAND flashメモリ特有のガーベッジコレクションが頻発することが懸念されます。NAND flashメモリは上書きできないメモリなので、容量が足りなくなったら全体から空き容量を探してきますが、これが起きるとストレージの性能が大きく低下することも懸念されます。

データのアクセス頻度をどうやって区別するのか

そのためFrozen Dataに関しては、L1キャッシュから落とす際にL2キャッシュをスキップして、直接もう1つ下位のメモリに落とし込みたいわけです。では、どうやってL2キャッシュをスキップすればいいのか。L1キャッシュから落とすデータのアクセス頻度を区別できれば、実現可能であることがわかります。

つまり、L1キャッシュから落ちるデータがFrozen Dataであると判断した場合は、L2キャッシュをスキップして下位のメモリに直接落とす。Frozen Dataではないと判断した場合は、今までどおりL2キャッシュに落とせばよいということになります。そのため、問題設定は「L1キャッシュからデータを追い出す際に、そのアクセス頻度を区別できるようなキャッシュ置換アルゴリズムは可能だろうか」になります。

LRUは追い出すデータがFrozen Dataかどうかを見分けられない

最初に、一番広く使われているキャッシュ置換アルゴリズムであるLRU（Least Recently Used）について考えました。LRUはご存じのとおり、（スライドを示して）このようなリストでキャッシュを管理していて、基本的にアクセスのあった順から上に詰めていきますが、途中でキャッシュに入っているデータにアクセスがあった場合は、もう一度上に詰め直します。

こうすることで、末尾はキャッシュに入っているデータの中で、一番アクセスが古いデータになるので、アクセスの古い順から落としていくことになります。しかし、このLRUには落とすデータが本当にFrozen Dataなのかを見分ける術はありません。キャッシュに残すべきかどうかを区別しているだけで、追い出すデータがFrozen Dataかどうかを見分ける情報は持っていません。

LRU-kはFrozen Dataかどうかを見分けることができる

そのため、LRU以外のキャッシュ置換アルゴリズムが必要になります。そこで、LRU-kアルゴリズムというアルゴリズムに注目しました。LRU-kでは、アドレスと過去のアクセスのタイムスタンプが保存されているテーブルを作り、そのテーブルに従って追い出すデータを決めます。

（スライドを示して）例えば、上の矢印のような順番にアクセスがあったとして、LRUの場合は新しく3のページが入ってきた時に、どこかのページを追い出さなくてはならなくなり、一番アクセスの古い2を追い出そうとします。

しかし、2は頻繁にアクセスされているページです。アドレス0は、もう1つ前を見ると随分昔にアクセスされているので、コールドだと期待できます。そこで、0を落とすにはどうするか。2番目の過去のタイムスタンプを2nd Lastと呼びますが、2nd Lastのタイムスタンプを見て古い順番に追い出すことによって、入った順番ではなくコールドのデータを選択的にキャッシュから追い出すことができるようになります。LRU-kは、既存のLRUの弱点を克服するために考案された最初のアルゴリズムだと言われています。

LRU-kで管理されているキャッシュにFrozen Dataが書き込まれた場合（このスライドの場合はアドレス3がFrozen Data）、どうなるか。

3はFrozen Dataなので優先的に追い出されますが、その際、2nd Lastのタイムスタンプに何も値が入っていない状態で追い出されることになります。なぜなら、Frozen Dataは過去に一度もアクセスされていないからです。なので、この追い出すデータに2nd Lastのタイムスタンプや値が入っているかによって、そのデータがFrozen Dataかどうかを見分けることができます。

実験と考察

考察です。以上のアイデアを確認するためにLRU-kで管理されたキャッシュと、キャッシュから追い出されるデータの数をカウントするプログラムを作りました。全体で1,200万ページくらい書き込まれていますが、そのうち47万ページがL2をスキップして下位のメモリに落ちてきます。L2キャッシュに落ちるのは100万ページくらいです。

下位のメモリに落ちてくるのは、先ほど言ったように過去に一度しかアクセスされていないFrozenのページです。L2キャッシュに落ちるページも、最初はL1キャッシュから下位のメモリに落ちますが、それ以降はL2キャッシュに落ちます。したがって、提案した手法によってL2キャッシュをスキップしてFrozen Dataを下位のメモリ（低書き換え耐性のメモリ）に追い出すことができることを確認できました。

まとめと今後やりたいこと

まとめです。書き換え耐性が極めて低いNAND flashメモリを使いこなすために、LRU-kキャッシュアルゴリズム（LRU-kキャッシュ置換アルゴリズムを使ったアルゴリズム）を応用して、L2キャッシュをスキップしてL1キャッシュから追い出すようなアルゴリズムを提案しました。

このアルゴリズムは、初めてアクセスされるデータにしか適用しませんが、例えば1週間以上経過したタイムスタンプのアクセス履歴は消去する、忘れてしまうなど何か工夫を加えると、実装できるかなと考えています。Q2など、LRU-k以外のアルゴリズムも同じようなことができないかなとちょっと考えています。

また、Future Workとしてなんらかのかたちで実装して、どこかに投稿したいと考えています。NAND flashメモリのメモリコントローラーは素人には扱えないので、OSレイヤーでやるならDevice mapperかなと考えています。以上です。