Comments
Description
Transcript
仮想ストライビング機能を有するRAID
46巻 3号 生 (1994.3) 産 研 究 ￨ I I I I I I I I I I I I l l l l究 l l l速 研 特 集 8 報 UDC 681.527.07 仮想 ス トライ ビング機 能 を有す る RAID-5型 デ ィス クア レイ PerformanceEvaluationof RAID-5 Disk Arrays with Virtual Striping 茂 木 和 彦 * 。 喜連川 ** 優 K a z u h i k o M O G I a n d Masaru KITSUREGAWA l.は じ め に l l Data 螂 Parity 外 部記憶装 置 の高性能化 。高信頼化 を 目的 としたデ イス 1)の クア レイ 研 究 ・開発 が 活発 に行 われ て い る。RAIDの はデ ー タ と冗 長情報 の記録 方式 か ら 5つ の レベ ル に分類 さ れ (冗長情報 を記録せ ず にデ ー タのス トライ ピングのみ を 行 った もの を含 め て 6つ の レベ ル に分類 され る こ と もあ る), ト ラ ンザ クシ ョン処理 や UNIXの フ ァイル システ ム の よ うに,ア クセ ス され るデ ー タの大 きさは小 さいが ,そ の 1/0負 荷 が大 きな用 途 に対 して は レベ ル 5(RAID 5 型)が よい とされて い る。 RAID 5型 の構 成 を図 1に 示 す 。 各 デ イス クに配置 され たデ ー タか らパ リテ ィス トライプ と呼 ばれ るグル ー プ を作 る.デ ー タを格納 す る とともにそれ らか らパ リテ イを計算 し,記 録 す る こ とによ リミラーデ イス クに比 べ て低 記録 コ ス トで高信頼化 が 図 られて い るが ,パ リテ イの導入 に よ り, デ ー タの書 き込 み (更新)時 にはパ リテ イの更新 が必 要 と なる。 従来 の方式 で は,パ リテ ィス トライプは物理 的 に固定 的 に配 置 されて い た。 そ のため,パ リテ イス トライプ中の一 部 のデ ー タを更新 す る時 には以下 の よ うに して新 しいパ リ テ ィを計算 す る必 要 が あ る。 Ncw Parity=01d Data ① New Data ① 01d Parity したが って ,デ ー タの更新 時 には,パ リテ イの更新 に必 要 な古 い デ ー タ とパ リテ ィを読 み出 さねばな らず ,そ れ に伴 う性 能 の低 下が大 きな問題 とな って い る。 図 l RAID 5型 ディスクア レイの構成 で はパ リテ イス トライプ を仮想化 す るこ とに よ り,デ ー タ の含 まれて い るパ リテ イス トライプの動 的組 み替 えを行 う. この組 み替 えに よ り,書 き込 まれ るデ ー タだ けでパ リテ ィ の計算が可能 とな り,デ ー タ書 き込 み時 の性 能が向上す る こ とが期待 され る。仮想 ス トライ ビングで は,仮 想 ス トラ イプテ ー ブル を用 い る こ とに よって物理 ブ ロ ックア ドレス と論理ブ ロ ックア ドレスの変換 を行 う。これによ り, ガ ー ベ ジヨ レクシ ョン時において もデー タの移動は発生せず, テーブルの組み替えのみの操作 に帰着す る. 以 下, 2 章 で 仮想 ス トライ ピングの機構 について説明す る. 3 章 で ソフ トウェアシ ミュレーシ ョンによる性能評価 を示す. 2 . 仮 想 ス トライビング 仮想 ス トライ ビングの概念図を図 2 に 示す。パ リテ ィス トライプは, 従 来 の R A I D 5 型 デ ィス クアレイと異な り, Stripe そ こで,こ のデ ー タ更新時の性能低下 を抑 えるため, 2)∼ 「 仮想 ス トライ ピング」 のと名付 けたパ リティグルー プ の再編成 を基本 とする方式 を現在検討 してい る.こ の方式 *東 京大学生産技術研究所 第 3部 **東 京大学生産技術研究所 付 属機能エ レク トロニ クス 研究 セ ンター 図 2 仮 想 ス トライ ビングの概念図 46巻 3号 研 速 究 生 (1994.3) 研 究 報 各 デ イス クの任 意 のブ ロ ックか ら構成 す ることが 出来 る. 以下 , 仮 想 ス トライ ビングの システム構成 につ い て説 明す る。 ―――― ―-2H一 ニ パ リテ ィス トラ イプの仮想化 一 ― 以下 の 2点 が挙 げ られ る。 1.デ ー タの物理 ア ドレス と論理 ア ドレスの分離 リテ イス トライプの仮想化 1.は デ ー タの物理 的 な位置 の変更 を可能 とす るため に必 要 な機構 で あ る.ま た, 2.に よ リデ ー タの物理 ア ドレス とその属 す るパ リテ イス トライプは動 的 に変更可能 となる. 仮想 ス トライ ピングで は,パ リテ イス トライプの仮想化 のため,そ の組 み合 わせ を管理す るテ ー ブルが必要 になる。 これ を仮想 ス トライプテ ー ブル と呼 び,図 3の よ うな構成 を とる。 この テ ー ブル には,そ れぞれの ス トライプ を区別 す るス トライプ番号 と,そ のス トライプを構成す るデ ー タ の シ リンダ番号 とブ ロ ック番号 が記録 され る.各 ス トライ プのパ リテ イデ イス クは,ス トライプ番号 か ら計算 され る. ガ ーベ ジ ヨ レクシ ョンのため に,各 ス トライプの ダー テ イ ブ ロ ック (デー タは別 の場所 に移動 したが ,パ リテ ィを計 算 す るため に内容 を保存 してお く必要 が あ るブ ロ ック)の 数 も記録 す る. 2.2 パ リテ ィス トライプの動的割付 け デ ー タの更新 時 には書 き換 えるデ ー タのみで新 しいパ リ テ イス トライプ を構成 し,デ イス ク上 の空 きス トライプに 記録 して い くこ と とし, こ れ をパ リテ イス トライプの動 的 割 り付 け と呼 ぶ. ス トライ プの動 的割 り付 け を実行 し nブ ロ ックか らパ リテ イが計算 されて い る場合 ,nヶ のデ ー タの書 き込 み に 必 要 なデ イス クヘ の ア クセ ス数 は総 計 n× D tt Pアクセ ス で 済 む。 (ここで Dは デ ー タデ イス ク,Pは パ リテ イデ イ ー ス ク を指 す 。 )一 方,従 来 の 方 式 で は古 い デ タ とパ リ テ イの読 み 出 しの ため に総 計 n× (2D+2P)ア クセ ス が必 Cylinder# Block# 要 で あ った。 したが って,パ リテ イス ト ライ プの動 的割 り 付 けを行 うこ とに よ リアクセ ス数が大 き く減少 し,デ ー タ 更新 時 の処理負荷 の軽減が図 れ る. ― ―― 一 仮想 ス トライ ピ ングを用 い た場合 の機構 上の特徴 と して , 2.パ 産 書 き込み可能な空 きス トライプが存在 しない場合,通 常 の 4ア クセス を必要 とする書 き込みを行 う。ただ し,書 き 込 むデ ー タは最 もダー テイブ ロ ックの多 いス トライプの ― ダーティブロ ックヘ と書 き込むようにス トライプの変更を 行 う.同 じス トライプヘ の書 き込みが多数あった場合,パ リテ イアクセスの共有化 を行 うことがで きアクセス数 を減 らす ことがで きる. 2.3 ガ ーベ ジ コレクション 書 き込み時に新 たなパ リテイグル ープを作 り続けてい く と,空 ス トライプは最終的には消費 しつ くされて しま う. 一方,更 新前 のデ ータはパ リテイの計算 に使用 されてい る ためダーティブロ ックとなってい る。 したが って,そ のま までは新 たなデ ー タを書 き込む ことは不可能であ り,ダ ー テ ィブロ ックをまとめ,新 しく書 き込み可能な空 きス トラ イプを作 る必要がある。この操作 をガーベ ジヨ レクシヨン と呼ぶ. 新 しく空 きス トライプを作 るには,そ の元 となるス トラ イプ (以下ヴ イクテイムス トライプと呼 ぶ)を 決め,そ の 中のアクティブブ ロ ック (デー タが存在す るブロ ック)を 他 のス トライプのダーテイブロ ックと置 き換 える必要があ る (図 4)。 これに必要な動作 は,置 換 を行 うダーテイブ ロ ックの内容 を, ヴ ィクテイムス トライプ上 のアクティブ ブロ ックの内容 に置 き換えることで ある。 したがって,仮 想 ス トライ ビングを用 い ない場合 のデー タ更新 と同様 に, この実行 にはパ リテイの更新が必要 である.こ の とき,ス Disk o 1 2 3 4 5 6 ′ Victilll Stripe′ Partner Strlpe Virtual Stripe GC I 眠I I : 笥 D i s k O ん ぉk 1 / 。 1 1 6 … . s k n ■ 時 t y B b c k ∞u 耐 1 0 1 1 1 1 1 2 1 1 1 M * * * Disk 0 4 * 1 葺 y 壺葺 ジ Free Stripe 図 3 仮 想 ス トライプテ ー ブル 0 ::::pe ト ree Marity ttACtive 5Dirty.4∵ iテ 図 4 ガ ーベ ジ コ レク シ ョン lIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIlllllllllllllllllllllllllllllllllllllllllllll 41 46巻 3号 生 産 研 (1994.3) 究 ￨￨￨ll llll llll llll lllll l 究 l l l l 速l l l l報 lll l l ll研 陶晰 )isk O Disk l Disk 2 Disk n ACTIVE DIRTY □ FREE 図 5 物 理プロック状態テーブル トライプの仮想化 に よ リパ リテ ィス トライプは論理 的 に組 み替 えが可能であ り,実 際 にデ ー タの移 動 は行 う必要が な い. このとき,ヴ ィクティムス トライプ中のダーテイブロ ッ クの置換 は必要がない。つ まり,ダ ーテ イブロ ックが多 い ス トライプをヴィクティムス トライプとして選択すること によ り,空 きス トライプを作成す るために必要なアクセス 数 を減少 させ ることが可能 となる.し たが って,ガ ーベ ジ ヨ レクシ ョンの負荷 を軽 くするため,ヴ ィクテイムス トラ イプはダーテ ィブロ ックを多 く含 む ものか ら選択する必要 ガ ーベ ジ ヨ レクシ ョンにお ける 1 ブ ロ ックの置換 には 4 アクセ スが必 要 で あ り, そ の処理 は大 きな負荷 となるこ と が予想 され る。そ こで, パ リテ ィス トライプはシ リ ンダに :固定 貰 仮 奄イヒする とセヽ ま:た,1ク ゞりII「 う制 孫 町条件 を付Sk三 「 テ ィの配置 はシ リ ンダ単位 で各 デ ィス クを巡 回 させ る.1 回の ガ ーベ ジ ヨ レクシ ョンで ,対 象 とす る 1シ リ ンダ中で 実行 可能 な処 理 をすべ て実行 す る.こ の方式 に よ り,ガ ー ベ ジ ヨ レクシ ョンの アクセ ス はすべ て 同 じシ リンダヘ の ア クセ ス とな り,ス ケ ジ ュー リングに よ りそ の コス トを下 げ ることが可能 となる. ガ ーベ ジ ヨ レクシ ョン処 理が通常 の負荷 へ 与 える影響 を 減 らす ため,そ の実行 法 につ い て は種 々の変形が可能 で あ るが ,今 回 はガ ーベ ジ ヨ レクシ ョン処理 の アクセス を一括 してすべ てのデ ィス クヘ と発 行 して フ リース トライプを作 成 した。パ リテ ィス トライプの組合せ はシ リ ンダ内で 固定 されて い るため,一 括処 理 に よ リパ リテ イヘ のアクセス に 関 して ス ケジ ュー リ ングの効果が大 き く出 るこ とが期待 で を利用 して行 う. ガーベ ジヨレクシ ョンで置換 を実行す るブロ ックを選択 するため,各 ブロ ックがアクテ ィブ,ダ ーティ,フ リーの きる。 しか し,一 括処 理 のため,ガ ーベ ジ コ レクシ ョンの 実行 はすべ てのデ ィス クに影響 が及 ぶ.通 常負荷 へ の影響 を最小 限 に押 さえ るため,ガ ーベ ジ ヨ レクシ ョンはで きる だ け多 くのデ イス クが アイ ドル状態 の時 に実 行す る必 要が あ る。 そ こで 今 回 は,i台 以下 のデ イス クのみ ビジ ー状 態 の 時 に ガ ー ベ ジ ヨ レク シ ョ ン を実 行 す る こ と と した。 いずれ の状態 にあるか知 る必 要があ る。そのため,各 ブ ロ ックの状態を物理ブロ ック状態テ ーブルに記録 してお き (GC-1と 名付 け る。 ) 3.2 シ ミュ レー シ ョン環境 (図5),必 要な時にこのテ ーブルか らブ ロ ックの状態 を調 べ ,置 換 を実行するダーテ ィブ ロ ックを選択 す る. ガーベ ジ ヨ レクションには,LFSに み られ るごと くコ ピー を主操作 とす るものと,ス レッ ド化す るものが考 えら デイ ス ク の モ デ ル と し て IBM 0661 Mode1 370 用 い る ( 表 1 ) 。 デ イス ク ア レイのデ ー タ (Lightning)を のス トライ ピング は 4 K B を 1 ブ ロ ック と して行 う. デ イ がある。このダーティブロ ックの多 いス トライプの検索は, 仮想 ス トライプテーブルに記録 されたダーテ ィブ ロ ック数 れるが, ここではガーベ ジ ヨ レクシ ョンコス トの低減 を図 るべ く,後 者 の方式 を採用 してい る. 2.4 フ ローティング/アクセススケジ ュー リング 7)共にこ フ ローテ ィ ング5),ァ クセ ススケジュー リング れまでにデ ィス クアクセスの高性能化手法 として考案 され ている ものである.仮 想 ス トライ ピングでは,仮 想化 を行 う際 にフローテ ィングの考 えを利用するとともにアクセス スケジュー リングを組み込んでい る。 3.シ ミュレーションによる評価 ソフ トウェアシ ミュレーションによ り,イ反想 ス トライ ビ ングの効果 とその性能を調べ る. 3.1 シ リンダ固定仮想ス トライビング 仮想 ス トライ ビングの基本機構 については 2章 で述べ た とお りで あるが,種 々の変形が考 えられる。今回は以下に 述べ るような方式 でシミュレーシ ョンを行 った。 ス ク中の空 きエ リアは初期状態 で は各 シ リ ンダにほほ均 等 表 1 capacity 1 318 cyl inders/disk 1 MB 949 tracks/cy1inder | 14 sectors/track | s e c t o rs i z e | 48 512 bytes r e v o l u t i o nt i m e | 13.Bms s e e kt i m e | 2 m s( m i n ) 肥 … 耐 l sttl鷺 v「d track skew 1 2.0 + 0.011:e:[。 ￨:46 。 46巻 3号 生 産 研 (1994.3) Ⅵ 湘:‖ 1:腰 琳革 ‖ 研満 ;‖‖ こ =¨ ￨ 読:る ぢ・ "¨￨ あ葛島毛 l 究 (GC-1,i=0, 1, 2) ￨ i デ ー タ/パ リテ ィフロー ト+ア クセススケジュー リン グを行 った RAID 5型 : Ｉ ＩＩ ‘ ︱︱ 一‘ ︱ ︱︱ ︱＝ Ｉ ︱Ｈ ‐アクセススケジ ュ ー lJング を行 った RAID 5型 。RAID 5原 型 ― 。RAID O原 型 (デー タデ ィス クのみの構成) 結果 を図 6に 示す .図 の横 軸 は単位 時間あ た りにデ ィス ク ア レイ に到着 す る平 均 1/0数 を表 し,縦 軸 は平均 レス ポ ンス タイ ム を表す。 図 6 よ り明らかなように, 仮 想 ス トライビングは通常の R A I D 5 型に比べて優れた性能を達成 していることがわか る。 図 6 8 D t t P 構 成時での性能 に分 散 して い る とす る。 読 み 出 し/書 き込 み (更新)の ア クセスの割合 は双 方 と も50%と し,ア クセス位 置 は一様分布 をなす と仮 定す る。 ア クセ ス のデ ー タサ イ ズ は 4 KB(1ブ ロ ック)の 固定長 4.お わ り に 仮 想 ス トライ ピ ン グ を用 い た デ イス ク ア レイ につ い て そ の構 成 法 な らび に制御 方 式 を明 らか にす る と と もに,シ ュ ミ レー シ ョンに よる性 能 評価 結 果 を示 した。今 後 よ り詳 細 な評価 を進 め て ゆ く予 定 で あ る。 (1993年 12月10日受理) とす る。 デ イス クア レイに到着 す るアクセ ス要 求 の時 間間 隔 は負 の指数分布 と仮 定す る. デ ィス クア レイの コ ン トロ ー ラにつ いて は次 の よ うな仮 定 を置 く。各 デ ィス クの ス ケ ジ ュー リ ングは独 立 に行 う。 ア レイ コ ン トロ ー ラには十分 なメモ リが 存在 す る と仮 定 し, そ こでのス ケ ジ ュールのための オ ーバ ーヘ ッ ド時 間 は無視 で きる と仮定す る。 パ リテ ィメ ンテナ ンスの処理 はバ ックグラウ ン ドで行 わ れて い る とし,デ ー タ更新 時 の レスポ ンス タイ ム は,デ ー タが デ ィス ク上 に書 き込 まれた時点での時 間 を用 い て計算 す る. シ ミュ レー シ ョンは,仮 想 ス トライ ビ ング の 場 合 は, デ ィス クの台 数 が 8D+Pの 構 成 につ いて ,400万 ア クセ ス 終了後 か ら,そ の他 の場合 は (空き領域 のブ ロ ック数) × 2ア クセ スの終了後 か ら測定 を開始 し,そ の値 は測定 開 始後 の10万アクセスの平均値 を取 る。 3.3 静 的負荷 に対 す る性 能 8台 の デ ー タデ ィス クに対 して静 的負荷 を与 えた時 の平 均 レスポ ンス タイ ム を調 べ た。デ イス クの使用 率 は80%と した。性 能 の比 較 のため に以下 に示 す各方式 の性 能 を測定 した. ・仮想 ス トライ ピングを用 い た RAID 5型 参 考 文 献 1)喜 連川優 :最近の二次記憶装置 :デ イス クアレイ,情 報処 理,Vo1 34,No 5,pp 642-651,1993.5. 2)茂 木和彦,喜 連川優, :動 的パ リテ イス トライプの再編成 による RAID 5型 デ ィス クア レイの高性能化手法 (仮想 ス トライ ピング)に 関す る基 本検討,SWopp'93コ ンピュー タシステ ム研究会,pp 31 38,電 子情報通信学会,1993. 8. 3)Masaru Kitsuregawa,KazuhikO MOgi Virtual Stripins A RAID5 Storage WIanagement Scheme with Robustness fOr the Peak Access Traffic,Proc of the lnt Symp on Next Generation Database Systems and Their ApplicatiOns,pp 280-287, 1993 9 4)茂 木和彦,喜 連川優 :仮想 ス トライ ピングによる RAID 5 型デ ィスクアレイの性能評価,電 子情報通信学会 デ ー タ ]二 と う lTttE`ヽ , pp 69-75,1993 9 5)J Menon et al,“ MethOds for lmproved Update PerfOrm_ ance of Disk Arrays",Proc Of 25th Hawali lnt Conf on System Science Vol I,pp 74-83,January 1992 6)D PattersOn et al,“ A Case fOr Redundant Arrays of ln‐ expens市e Disks(RAID)t PrOc of ACM SIGMOD,pp 109-116.」 u ne 1988 7) NI Seltzer et at,``Disk Scheduling Revisited",PrOc Of Winter 1990 USENIX Technical COnf,January 1990 ￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨lllllll‖ ￨￨￨￨￨￨￨￨￨￨￨￨￨‖ ￨￨￨￨￨￨￨￨IⅢ ‖IIIIIIIIIIIIIIIIIIIIIIII‖ ￨￨￨￨￨￨￨￨‖ ￨￨￨IⅢ IIIII‖ ￨￨llllⅢ IIIIlllll‖ ￨￨￨￨￨￨￨￨llllllⅢ III‖ ￨￨￨￨￨￨￨￨￨￨‖ llllIIIIIIIII‖ ￨￨￨￨￨‖ ￨￨ll‖ ￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨￨IⅢ II‖ ￨￨￨￨￨￨￨￨‖ lllⅢ IIIIIIⅢ IIIIIII