インメモリー重複除去における書き込み高速化

全文

(1)コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. インメモリー重複除去における書き込み高速化加藤純1. 大辻弘貴1. 鈴木康介1. 佐藤充1. 吉田英司1. 概要：エンタープライズ向けのスケールアウト型 AFA(All Flash Array) では，重複除去に関する処理をすべてメモリー上で行うことで高速化と Flash デバイスの高寿命化を実現するインメモリー重複除去が注目されている．しかし，従来のインメモリー重複除去では，DRAM キャッシュの容量効率化のためにキャッシュへの書き込みの前に重複除去処理を行うため，アプリケーションによらずユーザーから見た書き込みレイテンシーに常に重複除去処理の時間が計上される課題があった．本稿では，この従来の方式とキャッシュ書き込み完了後に重複除去を非同期で行う方式を実装・比較し，レイテンシーと IOPS の観点から 2 つの方式を最適に組み合わせるハイブリッド方式により，最大 IOPS を維持しつつ最大 34.7%のレイテンシーを削減したので報告する．キーワード：インメモリー重複除去，コンテンツキャッシュ，dedup-through，dedup-back，tail latency. 1. はじめに. 下が少なく，コンテンツキャッシュとの相性が良い．インメモリー重複除去を行うストレージシステムの書き. エンタープライズ向けのスケールアウト型 AFA(All Flash. 込み I/O フローでは，重複除去処理を先に行ってからキャッ. Array) では，複数の同一データを 1 つにまとめる重複除去. シュ処理を行う dedup-through 方式が一般的であるが，本. 技術により容量効率と同時に，ストレージデバイスである. 稿では，従来の dedup-through 方式と，write-through と. フラッシュへの書き込み量を減らすことで高寿命化を図っ. write-back の関係になぞらえてキャッシュ処理を先に行い. ている [1], [2], [3], [4], [5]．ストレージデバイスに書き込. 重複除去処理は非同期に行う dedup-back 方式を組み合わ. む前に重複除去を行う方式はインライン方式と呼ばれ，イ. せたハイブリッド方式を提案する．従来の dedup-through. ンライン方式の中でも重複除去に関する処理をすべてメ. 方式では重複除去処理をユーザー I/O 処理中に同期的に行. モリー上で行う方式をインメモリー方式 [1], [6] と本稿で. うため，非同期で行う処理がない代わりにレイテンシーに. は呼ぶ．インメモリー方式は重複除去処理中にストレージ. 重複除去処理が計上されてしまう．その逆に，dedup-back. デバイスにアクセスすることがなく，メモリー上で処理が. 方式では非同期に重複除去処理を行うためレイテンシーに. すべて完結するため高速かつ Flash の寿命を長くできる重. 重複除去処理が計上されなくなるが，非同期で行う重複除. 複除去方式である．しかし，重複除去の処理に必要なメタ. 去処理により通信回数が増加するため，tail latency の悪化. データ量はストレージ容量に対して 1%程度なため，数百. に伴い IOPS が低下する．. TiB 級のストレージ容量に対して数 TiB ものメモリーが. 本稿では上述の dedup-through 方式と dedup-back 方式. 必要となる．近年，DRAM 容量は飽和傾向にあるが，3D. の性能の違いを明らかにし，レイテンシーと IOPS をモニタ. XPoint[7] に代表されるバイトアドレス可能な大容量の次. リングして動的に dedup-through 方式と dedup-back 方式. 世代不揮発メモリー登場への期待とともに，高速な AFA. を切り替えるハイブリッド方式を提案する．Linux Kernel. の実現に向けてインメモリー方式に注目が集まっている．. モジュールのブロックデバイスの処理として，dedup-. 重複除去はもともとストレージデバイスに書かれるデー. through，dedup-back，ハイブリッドの 3 方式を実装して比. タを削減することを目的としていたが，近年ではキャッ. 較を行ったところ，ハイブリッド方式は dedup-through 方. シュにも重複除去を適用して，キャッシュの容量効率を高. 式を活用することで dedup-back 方式の課題であった IOPS. めたコンテンツキャッシュ [1], [8] も登場している．特に，. の低下を解決し，また低レイテンシーな dedup-back 方式. 重複除去処理がメモリー上ですべて完結するインメモリー. を活用することで最大 34.7%のレイテンシー削減を実現. 重複除去は，キャッシュを重複除去することによる性能低. した．. 1. 株式会社富士通研究所. c 2016 Information Processing Society of Japan ⃝. 51.

(2) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. 䛆ซ౛䛇 ᭩䛝㎸䜏. ^,Ͳϭ್ 䠄䝭䝷䞊䠅. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000000. 㻿㻴㻭㻙㻝䞉䝕䞊䝍䛾䝭䝷䞊ᚋ 䝺䝅䝢䜢᭦᪂. 䝕䞊䝍䠄䝭䝷䞊䠅. ᢸ ᙜ 叙. 向けのスケールアウト型 AFA，特に，[17] に従った重複除. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000. の重複除去で，(2) 時間的・空間的局所性を用いず，(3) 重. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. 䝕䞊䝍. 㻿㻴㻭㻙㻝್䛷 ᢸᙜ䜢Ỵ䜑䜛. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000 0000000 0000000 0000000000000000000000000000000000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000. に示すと，本稿は 3 章で述べるように (1)8KiB 固定長粒度. ㄞ䜏㎸䜏. ィ㻝 ⟬. どに適用されているが，本稿はその中でエンタープライズ去を行うストレージシステムを分類する 6 つの基準で詳細. 䝺䝅䝢䜢ㄞ䜏ྲྀ䜚䝕䞊䝍䜢ྲྀᚓ. 㻿㻴㻭㻙. 向け [9], [10]，フラッシュキャッシュ向け [11], [12], HDD 向け [13], [14] バックアップやアーカイブ向け [15], [16] な. 䝺䝅䝢䠄䝭䝷䞊䠅 ^,Ͳϭ್. 重複除去は複数の同一データをまとめるというシンプルなアイデアであるため適用範囲が広く，ファイルシステム. 䝺䝅䝢. 00 00 00 00 00 00 00. 2. 関連研究. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000. 䝭䝷䞊 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. 0000000000000000000000000000000000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. EŽĚĞϬ. 000000000000000000000000000000000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000000000000000000000000000000000. EŽĚĞϭ. EŽĚĞϮ. EŽĚĞWĂŝƌϬ. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000 0000000 0000000 0000000000000000000000000000000000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000. EŽĚĞϯ EŽĚĞWĂŝƌϭ. 図 1 dedup-through 方式の書き込み I/O フロー. (重複除去ができないユニークデータの場合). 複除去はインラインのタイミングで，(4) 重複除去と同じ. 8KiB の粒度ごとにメタデータを用意してデータを 1 対 1 で管理を行い，(5)SHA-1 160 ビット値の一致で重複を見つけ，(6) クラスターワイドに重複除去を行う，ブロックストレージシステムを対象としている．重複除去の性能向上は重複除去率の向上にならぶ 2 大トピックの 1 つ [18] であり，Bloom Filter[19] を階層的にすることでメタデータの検索を高速に行いレイテンシーを低下させる DBLK[14] や，時間的・空間的局所性を考慮してフラグメンテーションを減らすことで読み書き両方の性能を向上させる iDedup[13]，重複除去とキャッシュを統合して，ARC[20] ベースのアルゴリズムを採用することで重複除去メタデータキャッシュのヒット率を向上させる. CacheDedup[11]，ファイルシステムからのヒント情報をもとにブロックレベルの重複除去を最適化する手法 [21] などが提案されているが，本稿が課題とするのは I/O フローの設計に起因する重複除去のタイミングの違いによる性能差であり，上記の I/O フローを変更しない高速化手法では解決できない課題である．. Dirty ページ数をもとにしたフィードバック制御により dedup-through 方式と dedup-back 方式を組み合わせる方式も提案 [6] されている．その方式では dedup-back 方式のレイテンシーの分布が平均的であると仮定されていたが，. 3.3 節で示すように dedup-back 方式のレイテンシーの分布は平均的ではなく，tail latency を見ると dedup-through 方式の方がレイテンシーが短いことがあり，本稿の提案するハイブリッド方式は dedup-back 方式の tail latency も配慮した方式である．. 3. 書き込み I/O フロー 3.1 dedup-through 方式本稿が対象とするエンタープライズ向けのスケールアウト型 AFA 上での dedup-through 方式による書き込み I/O フローが図 1 である．エンタープライズ向けの HA(High. Availability) 構成のため 2 ノードから構成されるペアがスケールアウトする際の基本単位であり，データはすべ. c 2016 Information Processing Society of Japan ⃝. てペア内の別ノード (ミラーノード) との間で 2 重化を行う．重複除去を行う上で重要なデータ構造は重複を判定・管理するためのハッシュ値と参照カウントから構成されるメタデータと，LUN(Logical Unit Number) 番号と. LBA(Logical Block Address) からデータの場所を特定するレシピの 2 つである．インメモリー重複排除はこのメタデータとレシピがミラー分も含めてすべてメモリー上にあるのが特徴で，重複除去を行う上でストレージデバイスにアクセスすることがない．重複を判定するハッシュ値には十分に衝突困難 [22], [23] な SHA-1 160 ビットを用いて，. 8KiB 固定長単位での重複除去を行う．重複除去率の観点からは 8KiB ではなく 4KiB が望ましい [24] が，メタデータとレシピはそれぞれ 32，8 バイトと小さいサイズながら，シンプロビジョニングや重複除去によるストレージの仮想化に伴い数が膨大となるため，現実的なメモリー使用量を見積もった結果，本稿では 8KiB とした．. dedup-through 方式では，ユーザーからの書き込みが行われるとまず SHA-1 値の計算を行い，その値をもとに処理を担当するノードに SHA-1 値の転送を行う．SHA-1 値をもとに担当するノードを決定するので，ノード間での処理の偏りはない．SHA-1 値を受け取ったノードは，SHA-1 値をもとに重複除去できるかどうか判定を行い，重複除去ができる場合はローカルとミラー両方のメタデータの参照カウントを上げ，重複除去ができない場合は SHA-1 値の他にデータの取得も行い，重複除去のためのメタデータを新規に作成したのちにキャッシュ処理を行う．キャッシュ処理では，Dirty ページの設定や Dirty 管理用 LRU 操作の他に，HA を実現するためにデータとメタデータ両方のミラー処理を行う．ここまでの処理が完了したら，最後にミラーも含めたレシピの更新を行う．レシピは LUN 番号と. LBA アドレスをもとに各ノードに均等に分散されており，データの読み込みの際はまず LUN 番号と LBA アドレスをもとにレシピを読み取り，その値に従ってデータの場所を特定する． 52.

(3) コンピュータシステム・シンポジウム Computer System Symposium. Ğ ŝƚƌ t ŐŚ Ƶ ƌŽ Ś ƚͲ Ɖ Ƶ Ě Ğ Ě ŝ < ϴ. ComSys2016 2016/11/28. ϵϬ. 䛆ซ౛䛇. ϴϬ. 00 00 00 00 00 00 00. ΁Đ ĞƐ ϳϬ ʅ ΀ ϲϬ. 䝺䝅䝢䝺䝅䝢䠄䝭䝷䞊䠅 ^,Ͳϭ್. 䞊䝅䞁䝔ϱϬ 䜲䝺ϰϬ ϯϬ ϭ. 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. ᭩䛝㎸䜏. ^,Ͳϭ್ 䠄䝭䝷䞊䠅䝕䞊䝍. 䝕䞊䝍䛾䝭䝷䞊ᚋ 䝺䝅䝢䜢᭦᪂. 㻸㼁㻺䛸㻸㻮㻭䛷 ᢸᙜ䜢Ỵ䜑䜛. Ͳ , ^ ϮϬ. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000000000000000000000000000000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000000000000000000000000000000000. ᢸ ᙜ叙. 䛾䛷ϭϬ ᗘϬ 㔜 ከϭ ྛ. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. ϭƐƚ. ϱƚŚ. ϭϬƚŚ. ϮϬƚŚ. ϯϬƚŚ. ϰϬƚŚ. ϱϬƚŚ. ϲϬƚŚ. ϳϬƚŚ. ϴϬƚŚ. ϵϬƚŚ. ϵϱƚŚ. ϵϵƚŚ. ϮϮ. Ϯϰ. Ϯϰ. Ϯϱ. Ϯϲ. Ϯϲ. Ϯϳ. Ϯϴ. ϯϬ. ϯϮ. ϯϰ. ϯϱ. ϰϲ. Ϯ. ϵ. ϭϬ. ϭϬ. ϭϰ. ϭϰ. ϭϱ. ϭϲ. ϭϵ. Ϯϰ. Ϯϱ. Ϯϳ. ϯϬ. ϯϳ. ϰ. ϭϬ. ϭϬ. ϭϬ. ϭϭ. ϭϭ. ϭϰ. ϭϰ. ϭϱ. ϭϵ. Ϯϯ. Ϯϲ. Ϯϳ. ϯϱ. ϴ. ϭϭ. ϭϭ. ϭϮ. ϭϮ. ϭϮ. ϭϮ. ϭϰ. ϭϱ. ϭϳ. Ϯϭ. Ϯϱ. Ϯϳ. ϰϬ. ϭϲ. ϭϭ. ϭϭ. ϭϭ. ϭϮ. ϭϮ. ϭϮ. ϭϮ. ϭϮ. ϭϰ. ϭϲ. Ϯϰ. Ϯϴ. ϴϮ. 図 2. 䝭䝷䞊. 䛣䛣䛛䜙ඛ䛿 ᭩䛝㎸䜏᏶஢ᚋ 㠀ྠᮇ䛻⾜䛖. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000000 000000 000000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000000. 㻿㻴㻭㻙. 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. 㻿㻴㻭㻙㻝䞉䝕䞊䝍䛾䝭䝷䞊ᚋ 䝺䝅䝢䜢᭦᪂. ィ㻝 ⟬ ᢸᙜ䜈. 㻿㻴㻭㻙㻝್䛷 ᢸᙜ䜢Ỵ䜑䜛 EŽĚĞϬ. SHA-1 レイテンシー (Turbo Boost 有効). 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00. 䝕䞊䝍䠄䝭䝷䞊䠅. 䝭䝷䞊. EŽĚĞϭ. EŽĚĞϮ. 0000000000000000000000000000000000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 0000000000000000000000000000000000000 0000000000000000000000000000000000000. EŽĚĞWĂŝƌϬ. EŽĚĞϯ EŽĚĞWĂŝƌϭ. 図 4 dedup-back 方式の書き込み I/O フロー ϭϴϬ. (重複除去ができないユニークデータの場合). ϭϲϬ. Ğ ŝƚƌ t ŐŚ Ƶ ƌŽ Ś ƚͲ Ɖ Ƶ Ě Ğ Ě ŝ < ϴ. ΁Đ ĞƐ ϭϰϬ ʅ ΀ ϭϮϬ. 䞊䝅䞁䝔ϭϬϬ 䜲䝺 ϴϬ ϲϬ ϭ. 番号と LBA をもとに決定する．担当が決定したら，担当にデータを転送してキャッシュ処理を行う．キャッシュ処. Ͳ , ^ ϰϬ. 理に関して dedup-through 方式と異なる点は，この時点で. 䛾䛷 ϮϬ ᗘϬ 㔜 ከ ϭ ྛ. はまだ SHA-1 計算をしていないため重複除去のメタデー ϭƐƚ. ϱƚŚ. ϭϬƚŚ. ϮϬƚŚ. ϯϬƚŚ. ϰϬƚŚ. ϱϬƚŚ. ϲϬƚŚ. ϳϬƚŚ. ϴϬƚŚ. ϵϬƚŚ. ϵϱƚŚ. ϵϵƚŚ. Ϯϭ. Ϯϭ. Ϯϭ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. Ϯϯ. Ϯϯ. Ϯϰ. Ϯϲ. Ϯ. Ϯϭ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. Ϯϯ. Ϯϯ. Ϯϰ. Ϯϲ. Ϯϴ. ϯϯ. ϰ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϰ. Ϯϵ. ϯϰ. ϰϰ. ϴ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϰ. ϯϮ. ϰϳ. ϲϴ. ϭϲ. ϮϮ. ϮϮ. ϮϮ. ϮϮ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϯ. Ϯϰ. Ϯϵ. ϭϱϳ. 図 3. SHA-1 レイテンシー (Turbo Boost 無効). タではなく代わりに LUN 番号や LBA などをミラーすることであり，その他の Dirty ページの設定や管理 LRU の操作，データのミラー処理は同じである．キャッシュ処理が完了したら，ミラーも含めたレシピの更新を行い，書き込みは完了である．このように，ユーザーの書き込み処理. 3.2 dedup-back 方式 dedup-through 方式は書き込み I/O があるとまず SHA-1 計算を行うため，ユーザーから見た書き込みレイテンシーが高くなる [6]．評価の詳細については 3.3 節で述べるが，. 中には SHA-1 計算が含まれておらず，SHA-1 計算のオーバーヘッドを回避できることが dedup-back 方式の利点である．. dedup-back 方式では重複除去のタイミングを決めるた. 図 2，3 が実際に 8KiB で dedup-through 方式による処理. めに write-back と同様の Watermark 方式 [26] を用い，重. 中にかかる SHA-1 計算のレイテンシーである．SHA-1 計. 複除去されていない Dirty ページが一定量貯まったら重複. 算は発熱量に余裕がある場合に CPU の動作クロックを定. 除去を行う．重複除去の処理は dedup-through の重複除去. 格クロック以上に上昇させる Turbo Boost[25] の影響を受. と同様に，まず SHA-1 計算を行い，SHA-1 値をもとに担当. けやすく，Turbo Boost 無効時の 1 多重の書き込みレイテ. ノードを決定して SHA-1 値を転送，SHA-1 値を受け取っ. ンシー (図 A·1) の中央値 68 マイクロ秒に対して SHA-1 計. たノードはキャッシュ処理を行う．ユーザーからの書き込. 算の中央値は 22 マイクロ秒，Turbo Boost がうまく機能し. み時点では SHA-1 計算を行っていなかったため LUN 番号. ている 16 多重時の書き込みレイテンシー (図 9) の中央値. や LBA などのミラーを行うが，この段階では重複除去の. 75 マイクロ秒に対して SHA-1 計算の中央値は 12 マイクロ. メタデータが作成できるので，dedup-through 方式と同様. 秒と，Turbo Boost によって SHA-1 計算の割合は 16%か. にメタデータのミラーを行う．最後に，ミラーも含めたレ. ら 32%と 2 倍近く異なる．このように，Turbo Boost の有. シピの更新を行えば重複除去は完了である．. 無によってオーバーヘッドの値は大きく異なるが，Turbo. Boost が有効であっても 15%以上，最悪で 30%近くとレイテンシーを考慮すると無視できない高い値であり，この. 3.3 性能比較と考察 dedup-through 方式と dedup-back 方式の両方式を比較. オーバーヘッドが解消できればレイテンシーの大幅な改善. するため，表 1 に示す環境上に Linux Kernel モジュールと. が見込める．. してブロックデバイスを実装し，そのブロックデバイスの. dedup-back 方式はこの SHA-1 計算のオーバーヘッドを. 書き込み処理方式として dedup-through，dedup-back の各. 解消するため，重複除去を非同期に行う．図 4 は dedup-. 方式を実装した．重複除去のための SHA-1 計算には Linux. back 方式の書き込み I/O フローであるが，dedup-back 方. Kernel の crypto API で提供される AVX2 実装のものを用. 式では，ユーザーからの書き込み I/O が届いても dedup-. いた．サーバーは 2 台でインターコネクトには Infiniband. through 方式のように SHA-1 計算を行わず，処理を行う. を採用し，HA のための SHA-1 値やデータのミラーなど. 担当を決める際も SHA-1 値ではなくレシピと同様に LUN. に RDMA(Remote Direct Memory Access) Write，読み込. c 2016 Information Processing Society of Japan ⃝. 53.

(4) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. 表 1 評価環境サーバー. ϵϵƚŚ. 型版. Supermicro SYS-2028U-TN24R4T+, 2 台. CPU. Intel Xeon E5-2697 v4 2.30GHz 36 コア (Hyper-Threading 有効), 2 ソケット. メモリー. PC4-17000 2133MHz DDR4 64GiB, 8 枚. IB HCA. Mellanox Connect X3, FDR 4X 56Gbps, 2 枚ソフトウェア. OS. CentOS 7.2, Kernel 3.10.0-327.36.1. fio. 2.28 (scramble buffers オプション有効). ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϮϬ ϭƐƚ ϯϭ. ϱƚŚ ϯϯ. ϳϬ. ϳϱ. ϰϬ. ϲϬ. ϴϬ. ϭϬϬ. ϭϮϬ. ϭϰϬ. ϭϲϬ. ϭϴϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϯϲ ϰϰ ϰϵ ϱϮ ϱϱ ϲϬ ϲϳ ϳϮ ϳϳ ϴϭ ϭϬϴ ϳϴ. ϴϮ. ϴϲ. ϵϰ. ϭϬϬ. ϭϬϰ. ϭϬϴ. ϭϭϰ. ϭϮϳ. ϭϰϯ. ϭϲϭ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭ. ϮϬϬ ϭϴϬ. 図 7 1 多重時のレイテンシー (Turbo Boost 有効). ϭϲϬ. ΁^ ϭϰϬ W K / ϭϮϬ < ΀Ğ ƚ ƌŝ ϭϬϬ t ŝ ϴϬ < ϴ. ϵϵƚŚ ϵϱƚŚ. ϲϬ ϰϬ ϮϬ Ϭ. ϭ. Ϯ. ϰ. ϴ. ϭϲ. ĚĞĚƵƉͲďĂĐŬ. ϭϰ͘ϲ. ϯϯ͘ϴ. ϱϴ͘ϵ. ϵϱ. ϭϯϳ͘ϴ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϴ͘ϴ. Ϯϱ. ϱϮ͘ϯ. ϭϬϳ͘ϳ. ϭϴϬ͘ϳ. ከ㔜ᗘ. /ͬK. 図 5. ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ. IOPS (Turbo Boost 有効) ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϱϬ ϭƐƚ Ϯϴ. ϱƚŚ ϯϬ. ϰϬ. ϰϯ. ϭϬϬ. ϭϱϬ. ϮϬϬ. ϮϱϬ. ϯϬϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϯϮ ϯϰ ϯϲ ϰϭ ϰϲ ϰϵ ϱϭ ϱϰ ϲϮ ϳϳ ϮϳϬ ϰϱ. ϱϬ. ϱϳ. ϲϱ. ϳϰ. ϴϬ. ϴϱ. ϵϭ. ϵϴ. ϭϬϲ. ϭϮϲ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭϴϬ. Ϯ. ϭϲϬ ϭϰϬ. 図 8 2 多重時のレイテンシー (Turbo Boost 有効). ΁^ W ϭϮϬ /K ΀< Ğƚ ϭϬϬ ŝƌ t ϴϬ ŝ < ϴ ϲϬ. ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ. ϰϬ. ϲϬƚŚ ϱϬƚŚ. ϮϬ Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϭ. Ϯ. ϰ. ϴ. ϭϲ. ϮϬ. ϯϰ͘ϱ. ϱϴ͘ϳ. ϵϯ͘ϱ. ϭϯϭ. ϭϯ͘ϴ. Ϯϲ͘ϭ. ϰϴ͘ϴ. ϴϵ͘ϵ. ϭϱϳ͘ϱ. ከ㔜ᗘ. /ͬK. 図 6. ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ. IOPS (Turbo Boost 無効) ĚĞĚƵƉͲďĂĐŬ. み処理と書き込み処理で共有するためアトミックな操作が必要なレシピの処理には RDMA Atomic CAS(Compare. And Swap) を用いた．負荷としては fio を用いて 1，2，4，. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϭϬϬ ϭƐƚ ϯϱ. ϱƚŚ ϰϬ. ϰϰ. ϰϴ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. ϲϬϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϰϰ ϱϬ ϱϳ ϲϰ ϳϮ ϴϮ ϵϴ ϭϮϱ ϭϴϵ Ϯϵϰ ϱϵϲ ϱϭ. ϱϲ. ϲϮ. ϲϵ. ϳϱ. ϴϭ. ϴϴ. ϵϴ. ϭϭϱ. ϭϯϳ. ϭϵϱ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭϲ. 図 9 16 多重時のレイテンシー (Turbo Boost 有効). 8，16 スレッドで並列に 8KiB ランダム書き込みを行った．書き込み性能は重複除去できた場合とできなかった場合で. Boost の影響がないことから，以降では Turbo Boost 有効. 大きく異なるため，今回は fio の scramble buffers オプショ. 時のみに着目し，Turbo Boost 無効時については付録 A.1. ンを有効にして重複除去が効かない負荷とした．重複除去. に記載する．. が効く場合も含めた性能比較は今後の課題である．. この IOPS の逆転をレイテンシーの観点から見てみると，. IOPS の観点から見ると，図 5，6 に示すように，dedup-. 図 7，8，9 に示すように，1 多重時は 1 パーセンタイルか. through 方式の IOPS が Turbo Boost による SHA-1 計算. ら 99 パーセンタイルに至るまで dedup-back 方式の方がレ. 速度の差から大きく変化するものの，どちらも 100K IOPS. イテンシーが短いが，2 多重時では 99 パーセンタイル値. あたりを境に dedup-back 方式と dedup-through 方式で. で 270 マイクロ秒と tail latency が悪化する傾向が見え始. IOPS が逆転していることが分かる．IOPS の逆転に Turbo. め，16 多重時では 50 パーセンタイルまでしか dedup-back. c 2016 Information Processing Society of Japan ⃝. 54.

(5) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. ZDƚŽŵŝĐ. ZDƚŽŵŝĐ. ZDtƌŝƚĞ. ZDtƌŝƚĞ. ZDZĞĂĚ. ZDZĞĂĚ. ZĞĐǀ. ZĞĐǀ. ^ĞŶĚ. ^ĞŶĚ. Ϭ. ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. Ϭ. ϲϬϬ. ĚĞĚƵƉͲďĂĐŬ. ^ĞŶĚ ϭϯϳ͘ϯ. ZĞĐǀ ϭϯϳ͘ϯ. ZDZĞĂĚ ϯϰ. ZDtƌŝƚĞ ϯϰϭ͘ϭ. ZDƚŽŵŝĐ ϱϭϳ͘Ϯ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϵϭ͘ϰ. ϵϭ͘ϰ. Ϭ. ϭϴϬ͘ϭ. ϱϬϳ͘ϱ. ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ከ㔜ᗘ䛷䛾䝻䞊䜹䝹䝜䞊䝗䛾䝯䝑䝉䞊䝆䝺䞊䝖 ΀<ŵĞƐƐĂŐĞͬƐĞĐ΁. 16 多重時のメッセージレート (ローカル，Turbo Boost 有効). ZDƚŽŵŝĐ. ZDtƌŝƚĞ. ZDtƌŝƚĞ. ZDZĞĂĚ. ZDZĞĂĚ. ZĞĐǀ. ZĞĐǀ. ^ĞŶĚ. ^ĞŶĚ ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. ϲϬϬ. ĚĞĚƵƉͲďĂĐŬ. ^ĞŶĚ ϭϯϳ͘ϯ. ZĞĐǀ ϭϯϳ͘ϯ. ZDZĞĂĚ ϭϳϭ. ZDtƌŝƚĞ ϯϰϮ͘Ϯ. ZDƚŽŵŝĐ ϱϭϴ͘ϰ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϵϭ͘ϯ. ϵϭ͘ϯ. ϭϴϬ͘ϴ. ϭϴϬ͘ϴ. ϱϬϵ͘Ϯ. ከ㔜ᗘ䛷䛾䝭䝷䞊䝜䞊䝗䛾䝯䝑䝉䞊䝆䝺䞊䝖 ΀<ŵĞƐƐĂŐĞͬƐĞĐ΁. Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϴ<ŝtƌŝƚĞϭϲ. 図 11. 16 多重時のメッセージレート (ミラー，Turbo Boost 有効). ϭϱ. ϲϬϬ. ϴϬϬ. ϭϬϬϬ. ϭϮϬϬ. ZDZĞĂĚ ϮϴϬ. ZDtƌŝƚĞ ϭϭϯϲ. ZDƚŽŵŝĐ ϰ. ϭ. Ϭ. ϳϱϭ. ϰ. ከ㔜ᗘ䛷䛾䝻䞊䜹䝹䝜䞊䝗䛾䝇䝹䞊䝥䝑䝖 ΀DŝͬƐĞĐ΁. 図 12 16 多重時のスループット (ローカル，Turbo Boost 有効). ZDƚŽŵŝĐ. Ϭ. ϰϬϬ ZĞĐǀ ϰ. ϴ<ŝtƌŝƚĞϭϲ. ϴ<ŝtƌŝƚĞϭϲ. 図 10. ϮϬϬ ^ĞŶĚ ϭϱ. ϮϬϬ. ϰϬϬ. ^ĞŶĚ ϰ ϭ. ϲϬϬ. ϴϬϬ. ϭϬϬϬ. ϭϮϬϬ. ZĞĐǀ ϭϱ. ZDZĞĂĚ ϴϰϳ. ZDtƌŝƚĞ ϭϭϯϱ. ZDƚŽŵŝĐ ϰ. ϭϱ. ϳϰϭ. ϳϰϰ. ϰ. ከ㔜ᗘ䛷䛾䝭䝷䞊䝜䞊䝗䛾䝇䝹䞊䝥䝑䝖 ΀DŝͬƐĞĐ΁. ϴ<ŝtƌŝƚĞϭϲ. 図 13. 16 多重時のスループット (ミラー，Turbo Boost 有効). 方式のレイテンシーが短い利点が活きなくなっており，そ. するため 2 回追加の少なくとも 6 回の発行を行っているこ. れ以上に tail latency の悪化が IOPS を低下させるボトル. とがこの高いメッセージレートの要因だと考えられる．ま. ネックとして浮かび上がっていることがわかる．. た，Infiniband の規格 [27] で Atomic オペレーションによ. dedup-back 方式で tail latency が悪化した要因はイン. るアトミック性が保証されるのは同一 HCA(Host Channel. ターコネクトである Infiniband の通信遅延である．図 10，. Adapter) 内のみと規定されており，発行先が自ノードで. 11，12，13 は 16 多重時の dedup-back 方式と dedup-through. あっても HCA を経由した Atomic オペレーションが必要. 方式で負荷をかけたローカルノードとミラー先のミラー. であること [28] も要因の一つである．. ノードそれぞれのメッセージレートとスループットを In-. スループットの観点から見ると，メッセージレートの. finiband の各オペレーションごとに分類した結果である．. 場合とは大きく異なり，RDMA Write と RDMA Read が. まず，dedup-back，dedup-through 方式に共通する特徴と. 突出した形となる．これは Atomic オペレーションでは. して Atomic オペレーションのメッセージレートが高く，. Infiniband の規格により 1 メッセージ当たり 8 バイトでし. ローカル，ミラーを問わずに毎秒 500K メッセージ以上が. か通信できなかったので毎秒 500K メッセージ以上発行し. 発行されている．Atomic オペレーションが使われるのは. ても 4MiB 程度にしかならなかったのが，データのミラー. LBA からデータの場所を特定するレシピを操作する場面. やノード間でのデータの受け渡しを主に行う RDMA Write. である．dedup-through 方式ではミラーも含めたレシピの. や RDMA Read では I/O サイズにあたる 8KiB 単位で通信. 更新に 2 回，加えて Atomic オペレーションは CAS 方式の. することが多く，Atomic オペレーションと比べてメッセー. 更新であるため更新時には更新前のレシピの値が必要であ. ジサイズが比較的大きくなるためである．dedup-through. り，キャッシュ処理中に並列して更新前のレシピをそれぞ. 方式と dedup-back 方式で比較すると，dedup-back 方式の. れ読み取る 2 回と合わせて書き込み 1 回につき少なくとも. 方がスループットが高く，RDMA Write では 1.5 倍近いス. 4 回の Atomic オペレーションを発行する．dedup-back 方. ループットとなっているが，これは dedup-through 方式で. 式ではさらに非同期の重複除去処理中に再びレシピを更新. はキャッシュ処理時にデータのミラーを 1 回行えばよかっ. c 2016 Information Processing Society of Japan ⃝. 55.

(6) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. たものが，dedup-back 方式では非同期の重複除去中にさら. ϮϬϬ ϭϴϬ. にデータのミラーをもう 1 回行わなければならず，ミラーの処理回数が 1 回増えているためである．RDMA Read に関しても同様に非同期の重複除去処理中のデータ受け渡しの際に RDMA Read が使われるため増加している．キャッシュ処理だけの単純な場合でも RDMA Write に. ϭϲϬ. ΁^ W K / ΀< Ğ ƚ ƌŝ t ŝ < ϴ. ϭϰϬ ϭϮϬ ϭϬϬ ϴϬ ϲϬ ϰϬ. よるミラー処理がボトルネックとなって Infiniband の帯域. ϮϬ. を使いきれず，帯域よりもメッセージレートがボトルネックになっていることが知られている [29] が，本稿では，さらに重複除去のための各種 Infiniband のオペレーション，. Ϭ. ᥦ᱌ᡭἲ. ϭ. Ϯ. ϰ. ϴ. ϭϲ. ϭϮ͘ϴ. Ϯϴ͘ϳ. ϱϳ͘Ϯ. ϭϬϲ͘ϱ. ϭϴϬ͘ϰ. ĚĞĚƵƉͲďĂĐŬ. ϭϰ͘ϲ. ϯϯ͘ϴ. ϱϴ͘ϵ. ϵϱ. ϭϯϳ͘ϴ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϴ͘ϴ. Ϯϱ. ϱϮ͘ϯ. ϭϬϳ͘ϳ. ϭϴϬ͘ϳ. ከ㔜ᗘ. /ͬK. 特にレシピのための毎秒 500K メッセージを超える 8 バイトの Atomic オペレーション，が加わったことで，ボトル. 図 14. IOPS (Turbo Boost 有効). ネックに拍車がかかりやすい状態である．dedup-back 方式はその中で非同期の重複除去処理により RDMA Write や RDMA Read の回数を増やしてしまう方式であり，非同期に重複除去が行われてメッセージレートが上がっている最中に運悪くユーザーの書き込み処理が入り込むとメッセージレートが高い分レイテンシーが悪化する．このことが原因となって dedup-back 方式では tail latency が悪化すると考えられる．. ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ. 4. ハイブリッドな書き込み I/O フロー 3.3 節のように方式の違いによって IOPS やレイテンシーに関する特性が異なっており，これらを使い分けることで. dedup-back 方式の低レイテンシー，dedup-through 方式の. ϮϬ. ϰϬ. ϲϬ. ϴϬ. ϭϬϬ. ϭϮϬ. ϭϰϬ. ϭϲϬ. ϭϴϬ. ᥦ᱌ᡭἲ. ϭƐƚ ϰϭ. ϱƚŚ ϰϱ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϰϳ ϱϭ ϱϲ ϲϭ ϲϱ ϲϵ ϳϯ ϳϵ ϴϵ ϵϴ ϭϮϯ. ĚĞĚƵƉͲďĂĐŬ. ϯϭ. ϯϯ. ϯϲ. ϰϰ. ϰϵ. ϱϮ. ϱϱ. ϲϬ. ϲϳ. ϳϮ. ϳϳ. ϴϭ. ϭϬϴ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϳϬ. ϳϱ. ϳϴ. ϴϮ. ϴϲ. ϵϰ. ϭϬϬ. ϭϬϰ. ϭϬϴ. ϭϭϰ. ϭϮϳ. ϭϰϯ. ϭϲϭ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭ. 図 15 1 多重時のレイテンシー (Turbo Boost 有効). 高 IOPS を実現するのが本稿が提案するハイブリッド方式である．従来の dedup-through 方式から比較すると，図 7，. 方式に SHA-1 計算のオーバーヘッドを足しても dedup-. 8 が示すように 100K IOPS 未満の場面では dedup-back 方. through 方式の方が早い場合，3.3 節で示したようにネッ. 式の方がレイテンシーが低くなることが多く，IOPS をな. トワークがボトルネックとなっていると考えられ，dedup-. るべく下げることなくレイテンシーを高速化することがハ. back 方式にしてもレイテンシーを短縮することができな. イブリッド方式の狙いであり，dedup-back 方式から比較. いためである．. すると IOPS の向上に加えて，dedup-through 方式を混ぜることで非同期の重複除去による通信回数の増加を緩和し. 4.1 性能評価. て，tail latency を低く保つことが目的である．. 4.2 ハイブリッド方式. ハイブリッド方式では，定期的に書き込み IOPS をモニ. 3.3 節での評価と同じ表 1 の環境上にハイブリッド方式も. タリングして一定以上の場合はすべて dedup-through 方. 実装して同様の評価を行った．その時の書き込み IOPS が. 式とする．図 9 から一定以上の IOPS がかかっている場合. 図 14 である．1，2，4 多重時では dedup-back 方式を混ぜ. は dedup-back 方式のメリットは数マイクロ秒程度しかな. たことにより従来の dedup-through 方式と比較して IOPS. く，それ以上に tail latency による性能劣化が大きいため. が改善されており，8，16 多重時では dedup-back 方式は. このような閾値を設ける．3.3 節の考察から，表 1 の環境. ネットワークのボトルネックにより IOPS が低下していた. では 100K IOPS が境目とわかるので，本稿では閾値とし. ところ，ハイブリッド方式では従来通り dedup-through 方. て 100K IOPS を採用する．. 式で処理を行うため，IOPS の低下はない．. 100K IOPS の閾値以下の場合，dedup-back 方式，dedup-. ハイブリッド方式では dedup-back 方式を活用すること. through 方式を混ぜて発行することになるが，各方式ごとの. で従来の dedup-through 方式に比べて低レイテンシーとな. レイテンシーとそのノードでの SHA-1 計算のレイテンシー. る．図 15，16，17 はハイブリッド方式も含めた 1，2，16. をモニタリングして，dedup-through 方式と dedup-back 方. 多重時のレイテンシーの分布であるが，dedup-back 方式. 式の差分が SHA-1 計算のレイテンシー以下となる割合を，. が IOPS の観点で活用できない 16 多重時はレイテンシー. dedup-through 方式で処理する割合とする．dedup-back. が同じであるが，2 多重時の 99 パーセンタイル値以外では. c 2016 Information Processing Society of Japan ⃝. 56.

(7) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. た．Linux Kernel モジュールに実装して評価したところ，. ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ. ハイブリッド方式は従来の dedup-through 方式と遜色ない. IOPS を維持しつつ，レイテンシーを最大 34.7%削減した．今後の課題として，重複除去が効く場合も含めた方式の検討が挙げられる．すでに重複したデータがある場合はデータの 2 重化処理が既に行われているため参照カウントを上げるだけでよく，本稿が対象としていた重複除去がで Ϭ. ᥦ᱌ᡭἲ. ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϱϬ. ϭϬϬ. ϭϱϬ. ϮϬϬ. ϮϱϬ. ϯϬϬ. ϭƐƚ ϯϬ. ϱƚŚ ϯϮ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϯϱ ϰϯ ϰϳ ϱϯ ϱϴ ϲϯ ϲϴ ϳϱ ϴϱ ϵϰ ϭϲϱ. Ϯϴ. ϯϬ. ϯϮ. ϯϰ. ϯϲ. ϰϭ. ϰϲ. ϰϵ. ϱϭ. ϱϰ. ϲϮ. ϳϳ. ϮϳϬ. ϰϬ. ϰϯ. ϰϱ. ϱϬ. ϱϳ. ϲϱ. ϳϰ. ϴϬ. ϴϱ. ϵϭ. ϵϴ. ϭϬϲ. ϭϮϲ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. Ϯ. きない場合の書き込みとは異なった性能特性となるため，実用化に向けて重複が除去できた場合の I/O フローの考慮が必至である．また，現状ではフリーページ不足による空き待ちによるキャッシュ処理の遅延やキャッシュの重複除去率などが考慮されていない．これらキャッシュに関する. 図 16 2 多重時のレイテンシー (Turbo Boost 有効). 情報を活用してワークロードに最適な方式を選択することで書き込み性能を向上させることも今後の課題である．. ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ. 参考文献 [1] [2] [3] Ϭ. ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. ϲϬϬ. ϳϬϬ. ᥦ᱌ᡭἲ. ϭƐƚ ϰϰ. ϱƚŚ ϰϴ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϱϭ ϱϲ ϲϮ ϲϴ ϳϰ ϴϭ ϴϵ ϵϵ ϭϭϳ ϭϯϵ ϭϵϱ. ĚĞĚƵƉͲďĂĐŬ. ϯϱ. ϰϬ. ϰϰ. ϱϬ. ϱϳ. ϲϰ. ϳϮ. ϴϮ. ϵϴ. ϭϮϱ. ϭϴϵ. Ϯϵϰ. ϱϵϲ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϰϰ. ϰϴ. ϱϭ. ϱϲ. ϲϮ. ϲϵ. ϳϱ. ϴϭ. ϴϴ. ϵϴ. ϭϭϱ. ϭϯϳ. ϭϵϱ. [4] [5]. ከ㔜䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭϲ. [6] 図 17 16 多重時のレイテンシー (Turbo Boost 有効). dedup-through 方式よりも短く，平均すると，1 多重時で. [7]. 100.6 マイクロ秒から 65.7 マイクロ秒，2 多重時で 72.5 マイクロ秒から 61.8 マイクロ秒とレイテンシーをそれぞれ. 34.7%，14.8%削減した．. [8] [9]. レイテンシーの観点から dedup-back 方式と比較すると，ハイブリッド方式は dedup-through 方式が混ざった分オーバーヘッドが加わるが，tail latency が緩和される．図 16 から 99 パーセンタイル値を比較すると，270 マイクロ秒が. 165 マイクロ秒と tail latency を 39%削減した．. [10]. 5. おわりに [11]. インメモリー重複除去を設計する上で，重複除去を行うタイミングは書き込み性能の特性を左右する重要なファクターの 1 つである．本稿では，従来の同期的に重複除去を. [12]. 行う dedup-through 方式に加えて，非同期に重複除去を行う dedup-back 方式の 2 つを比較して，dedup-through 方式の高い IOPS 性能と同期的な重複除去処理のオーバー. [13]. ヘッドによる高レイテンシー，dedup-back 方式の低レイテンシーと tail latency の増加に伴う IOPS 低下を明らかにして，この 2 つの方式を組み合わせることで高 IOPS と低レイテンシーの両立を目指すハイブリッド方式を提案し. c 2016 Information Processing Society of Japan ⃝. [14]. EMC: XtremIO, https://www.emc.com/en-us/storage/ xtremio/definitions.htm. Hewlett Packard Enterprise: 3PAR StoreServ Storage, https://www.hpe.com/us/en/storage/3par.html. IBM: Flash System, http://www-03.ibm.com/systems/ storage/flash/. NetApp: SolidFire, http://www.netapp.com/us/ products/storage-systems/solidfire/index.aspx. Pure Storage: Flash Array, https:// www.purestorage.com/products/flash-array-m/ m10.html. 大辻弘貴，加藤純，鈴木康介，佐藤充，吉田英司：ブロックストレージシステムにおける Latency-aware InlineDedup Optimization，研究報告ハイパフォーマンスコンピューティング (2016). Intel: 3D XPoint, http://www.intel.com/content/ www/us/en/architecture-and-technology/non-volatilememory.html. Nutanix: Nutanix, http://www.nutanix.com/. Ungureanu, C., Atkin, B., Aranya, A., Gokhale, S., Rago, S., Calkowski, G., Dubnicki, C. and Bohra, A.: HydraFS: A High-Throughput File System for the HYDRAstor Content-Addressable Storage System, 8th USENIX Conference on File and Storage Technologies (FAST 10) (2010). Zhu, B., Li, K. and Patterson, R. H.: Avoiding the Disk Bottleneck in the Data Domain Deduplication File System, 6th USENIX Conference on File and Storage Technologies (FAST 08) (2008). Li, W., Jean-Baptise, G., Riveros, J., Narasimhan, G., Zhang, T. and Zhao, M.: CacheDedup: In-line Deduplication for Flash Caching, 14th USENIX Conference on File and Storage Technologies (FAST 16) (2016). Li, C., Shilane, P., Douglis, F., Shim, H., Smaldone, S. and Wallace, G.: Nitro: A Capacity-Optimized SSD Cache for Primary Storage, 2014 USENIX Annual Technical Conference (USENIX ATC 14) (2014). Srinivasan, K., Bisson, T., Goodson, G. R. and Voruganti, K.: iDedup: Latency-aware, Inline Data Deduplication for Primary Storage, 10th USENIX Conference on File and Storage Technologies (FAST 12) (2012). Tsuchiya, Y. and Watanabe, T.: DBLK: Deduplication for Primary Block Storage, 2011 IEEE 27th Symposium. 57.

(8) コンピュータシステム・シンポジウム Computer System Symposium. [15]. [16]. [17]. [18]. [19]. [20]. [21]. [22]. [23]. [24]. [25]. [26]. [27] [28]. [29]. on Mass Storage Systems and Technologies (MSST), pp. 1–5 (2011). Fu, M., Feng, D., Hua, Y., He, X., Chen, Z., Xia, W., Zhang, Y. and Tan, Y.: Design Tradeoffs for Data Deduplication Performance in Backup Workloads, 13th USENIX Conference on File and Storage Technologies (FAST 15) (2015). Quinlan, S. and Dorward, S.: Venti: A New Approach to Archival Storage, Conference on File and Storage Technologies (FAST 02) (2002). Paulo, J. and Pereira, J.: A Survey and Classification of Storage Deduplication Systems, ACM Computing Surveys (CSUR), Vol. 47, No. 1, p. 11 (2014). Shilane, P., Chitloor, R. and Jonnala, U. K.: 99 Deduplication Problems, 8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 16) (2016). Bloom, B. H.: Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, Vol. 13, No. 7, pp. 422–426 (1970). Megiddo, N. and Modha, D. S.: ARC: A Self-Tuning, Low Overhead Replacement Cache, 2nd USENIX Conference on File and Storage Technologies (FAST 03), Vol. 3 (2003). Mandal, S., Kuenning, G., Ok, D., Shastry, V., Shilane, P., Zhen, S., Tarasov, V. and Zadok, E.: Using Hints to Improve Inline Block-layer Deduplication, 14th USENIX Conference on File and Storage Technologies (FAST 16) (2016). De Canniere, C. and Rechberger, C.: Finding SHA-1 characteristics: General results and applications, International Conference on the Theory and Application of Cryptology and Information Security, Springer, pp. 1– 20 (2006). Wang, X., Yin, Y. L. and Yu, H.: Finding collisions in the full SHA-1, Annual International Cryptology Conference, Springer, pp. 17–36 (2005). Kim, J., Lee, C., Lee, S., Son, I., Choi, J., Yoon, S., Lee, H.-u., Kang, S., Won, Y. and Cha, J.: Deduplication in SSDs: Model and quantitative analysis, 012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST), IEEE, pp. 1–12 (2012). Intel: Turbo Boost Technology, http://www.intel.com/ content/www/us/en/architecture-and-technology/ turbo-boost/turbo-boost-max-technology.html. Varma, A. and Jacobson, Q.: Destage Algorithms for Disk Arrays with Nonvolatile Caches, IEEE Transactions on Computers, Vol. 47, No. 2, pp. 228–235 (1998). Infiniband Trade Association: Infiniband Architecture Specification, Release 1.3, Vol. 1 (2015). 秋元秀行，三浦健一，岡本高幸，安島雄一郎，住本真司：Infiniband Atomic Operation の性能評価，研究報告ハイパフォーマンスコンピューティング (2013). 加藤純，佐藤充：ブロックストレージシステムにおけるキャッシュの高速化，研究報告システムソフトウェアとオペレーティング・システム (2016).. ComSys2016 2016/11/28. ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϭϬ ϭƐƚ ϯϬ. ϱƚŚ ϯϬ. ϱϯ. ϱϰ. ϮϬ. ϯϬ. ϰϬ. ϱϬ. ϲϬ. ϳϬ. ϴϬ. ϵϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϯϭ ϯϮ ϯϱ ϯϳ ϰϱ ϰϳ ϰϵ ϱϬ ϱϭ ϱϯ ϳϱ ϱϰ. ϱϲ. ϱϴ. ϱϵ. ϲϴ. ϳϭ. ϳϮ. ϳϰ. ϳϲ. ϳϳ. ϴϭ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭ. 図 A·1 1 多重時のレイテンシー (Turbo Boost 無効). ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϮϬ ϭƐƚ ϯϬ. ϱƚŚ ϯϮ. ϱϯ. ϱϱ. ϰϬ. ϲϬ. ϴϬ. ϭϬϬ. ϭϮϬ. ϭϰϬ. ϭϲϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϯϰ ϯϲ ϯϴ ϰϭ ϰϴ ϱϬ ϱϮ ϱϰ ϱϴ ϲϴ ϭϰϵ ϱϲ. ϱϴ. ϲϬ. ϲϮ. ϳϬ. ϳϯ. ϳϱ. ϳϳ. ϴϬ. ϴϯ. ϴϴ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. Ϯ. 図 A·2 2 多重時のレイテンシー (Turbo Boost 無効). ϵϵƚŚ ϵϱƚŚ ϵϬƚŚ ϴϬƚŚ ϳϬƚŚ ϲϬƚŚ ϱϬƚŚ ϰϬƚŚ ϯϬƚŚ ϮϬƚŚ ϭϬƚŚ ϱƚŚ ϭƐƚ Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϭϬϬ ϭƐƚ ϯϵ. ϱƚŚ ϰϰ. ϱϳ. ϲϭ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. ϲϬϬ. ϭϬƚŚ ϮϬƚŚ ϯϬƚŚ ϰϬƚŚ ϱϬƚŚ ϲϬƚŚ ϳϬƚŚ ϴϬƚŚ ϵϬƚŚ ϵϱƚŚ ϵϵƚŚ ϰϴ ϱϱ ϲϯ ϳϬ ϳϳ ϴϵ ϭϬϲ ϭϯϱ ϭϵϱ ϮϴϮ ϱϱϲ ϲϰ. ϲϴ. ϳϯ. ϳϵ. ϴϱ. ϵϬ. ϵϳ. ϭϬϲ. ϭϮϲ. ϭϱϳ. Ϯϰϳ. ከ㔜ᗘ䛷䛾ϴ<ŝtƌŝƚĞ䜢Ⓨ⾜䛧䛶䛛䜙᏶஢䛩䜛䜎䛷䛾䝺䜲䝔䞁䝅䞊 ΀ʅƐĞĐ΁. ϭϲ. 図 A·3 16 多重時のレイテンシー (Turbo Boost 無効). かかる時間が変わるため書き込みレイテンシーの値は異なるが，多重度が上がるにつれて tail latency が悪化する. 付. 録. A.1 Turbo Boost 無効時の性能. 点は本文で示した Turbo Boost 有効時と変わらず，Turbo. Boost が tail latency の悪化には影響しないことが分かる．図 A·4，A·5，A·6，A·7 は本文の図 10，11，12，13 と. 図 A·1，A·2，A·3 はそれぞれ 3.3 節に記載しなかった. 同様に Turbo Boost 無効時でのローカルノードとミラー. Turbo Boost 無効時の 1，2，16 多重時のレイテンシーの. ノード，それぞれのメッセージレートとスループットを. 分布である．Turbo Boost の有無によって SHA-1 計算に. Infiniband の各オペレーションごとに分類した結果である． Turbo Boost 機能の有無による性能差があるものの全体的. c 2016 Information Processing Society of Japan ⃝. 58.

(9) コンピュータシステム・シンポジウム Computer System Symposium. ComSys2016 2016/11/28. ZDƚŽŵŝĐ. ZDƚŽŵŝĐ. ZDtƌŝƚĞ. ZDtƌŝƚĞ. ZDZĞĂĚ. ZDZĞĂĚ. ZĞĐǀ. ZĞĐǀ. ^ĞŶĚ. ^ĞŶĚ. Ϭ. ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. Ϭ. ϲϬϬ. ĚĞĚƵƉͲďĂĐŬ. ^ĞŶĚ ϭϯϭ͘ϴ. ZĞĐǀ ϭϯϭ͘ϴ. ZDZĞĂĚ ϯϮ͘ϳ. ZDtƌŝƚĞ ϯϯϬ͘ϯ. ZDƚŽŵŝĐ ϰϵϬ͘ϱ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϳϵ͘ϲ. ϳϵ͘ϲ. Ϭ. ϭϱϳ. ϰϰϮ͘ϲ. ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ከ㔜ᗘ䛷䛾䝻䞊䜹䝹䝜䞊䝗䛾䝯䝑䝉䞊䝆䝺䞊䝖 ΀<ŵĞƐƐĂŐĞͬƐĞĐ΁. ϰϬϬ. ϭϯ. ϲϬϬ. ϴϬϬ. ϭϬϬϬ. ϭϮϬϬ. ZĞĐǀ ϰ. ZDZĞĂĚ ϮϳϬ. ZDtƌŝƚĞ ϭϬϴϳ. ZDƚŽŵŝĐ ϰ. ϭ. Ϭ. ϲϰϳ. ϰ. ከ㔜ᗘ䛷䛾䝻䞊䜹䝹䝜䞊䝗䛾䝇䝹䞊䝥䝑䝖 ΀DŝͬƐĞĐ΁. ϴ<ŝtƌŝƚĞϭϲ. ϴ<ŝtƌŝƚĞϭϲ. 図 A·4 16 多重時のメッセージレート (ローカル，Turbo Boost. ϮϬϬ ^ĞŶĚ ϭϰ. 図 A·6 16 多重時のスループット (ローカル，Turbo Boost 無効). 無効). ZDƚŽŵŝĐ. ZDƚŽŵŝĐ. ZDtƌŝƚĞ. ZDtƌŝƚĞ. ZDZĞĂĚ. ZDZĞĂĚ. ZĞĐǀ. ZĞĐǀ. ^ĞŶĚ. ^ĞŶĚ Ϭ. ϭϬϬ. ϮϬϬ. ϯϬϬ. ϰϬϬ. ϱϬϬ. ϲϬϬ. ĚĞĚƵƉͲďĂĐŬ. ^ĞŶĚ ϭϯϮ. ZĞĐǀ ϭϯϮ. ZDZĞĂĚ ϭϲϰ͘Ϯ. ZDtƌŝƚĞ ϯϮϴ͘ϯ. ZDƚŽŵŝĐ ϰϴϳ͘ϯ. ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϳϵ͘ϲ. ϳϵ͘ϲ. ϭϱϳ͘ϲ. ϭϱϳ͘ϲ. ϰϰϰ͘ϭ. ከ㔜ᗘ䛷䛾䝭䝷䞊䝜䞊䝗䛾䝯䝑䝉䞊䝆䝺䞊䝖 ΀<ŵĞƐƐĂŐĞͬƐĞĐ΁. ϴ<ŝtƌŝƚĞϭϲ. 図 A·5 16 多重時のメッセージレート (ミラー，Turbo Boost 無効). Ϭ ĚĞĚƵƉͲďĂĐŬ ĚĞĚƵƉͲƚŚƌŽƵŐŚ. ϮϬϬ. ϰϬϬ. ^ĞŶĚ ϰ ϭ. ϲϬϬ. ϴϬϬ. ϭϬϬϬ. ϭϮϬϬ. ZĞĐǀ ϭϰ. ZDZĞĂĚ ϴϬϴ. ZDtƌŝƚĞ ϭϬϴϭ. ZDƚŽŵŝĐ ϰ. ϭϯ. ϲϰϰ. ϲϰϳ. ϰ. ከ㔜ᗘ䛷䛾䝭䝷䞊䝜䞊䝗䛾䝇䝹䞊䝥䝑䝖 ΀DŝͬƐĞĐ΁. ϴ<ŝtƌŝƚĞϭϲ. 図 A·7 16 多重時のスループット (ミラー，Turbo Boost 無効). な傾向は一致しているため，3.3 節で述べた考察は Turbo. Boost 無効時にも当てはまり，本稿の提案手法は Turbo Boost 無効時にも有効であると考えられる．. c 2016 Information Processing Society of Japan ⃝. 59.

(10)