2005/11/07

最適なストライピングユニットサイズの選択
最適なストライピングユニットサイズの選択• RAIDの性能を上げる…相反する２つの目標

データ工学特論（３）– 各ディスクにできるだけ多くのデータを転送させる– できるだけ多くのディスクを入出力に参加させる• ストライピングユニット
あるストライプの一部として各ディスクに保存される連続したデータ領域⇒このサイズが RAID の性能を大きく左右する– トレードオフの問題• 小⇒少量のデータでも多くのディスクに分散する• 大⇒少量のデータなら少ないディスクにまとまる• 最適なストライピングユニットサイズの選択は解析が困難– 限定された単純なモデルでの推定– シミュレーション・実験による推定

情報基盤センター
天野 浩文
この講義に関するwebサイト：
http://isabelle.cc.kyushu-u.ac.jp/~amano/data-engineering/

データ工学特論（３）1

データ工学特論（３）2

RAID
RAID の解析的評価を行う上での問題点の解析的評価を行う上での問題点

Chen
Chen とと Patterson
Patterson による経験則(1990)
による経験則(1990) －(1)－(1)• ブロック系 RAID にアクセスする場合には– 個々のディスクに対するリクエストに forkfork(それぞれキューにつながれる)– 処理が終了したら join
join
(同期の処理が入る)• 待ち行列理論による解析– 厳密解は２サーバでのfork-join問題までしか得られていない• アプリケーションの入出力要求のモデル化も難しい– 待ち行列理論では，負荷が一時的に高くなった場合の過渡的な挙動をモデル化しにくい– 定常的な状態（リクエストがたまり続けることなく処理できる状態）での挙動を調べるのがせいぜい• 16台のディスクが同期して回転する場合の最適ストライピングユ
ニットサイズ– 平均リクエストサイズと，同時に発生するリクエストの多重度とを変化させてシミュレーション– 最適なスループットを与えるストライピングユニットサイズ• 結果– 最も大きな影響を与えるパラメータは多重度である• 多重度があらかじめわかっているとき，任意のリクエスト分散に対して最大スループットの 95%を与える式
11セクタ + × 平均位置決め時間 × データ転送速度 × (多重度 − 1)
4

（平均位置決め時間＝平均シーク時間＋平均回転遅延）
データ工学特論（３）

データ工学特論（３）3

データ工学特論（３）412005/11/07

Chen
Chen とと Patterson
Patterson による経験則(1990)
による経験則(1990) －(2)－(2)

LeeとKatzの解析(1991)
LeeとKatzの解析(1991)• 直観的な解釈• 冗長ディスクのないRAIDの解析的モデルを設定し，最適ストライピングユニットサイズを与える式を導出

1
1セクタ + × 平均位置決め時間 × データ転送速度 × (多重度 − 1)
4最適ストライピングユ ニットサイズ =– 多重度が増えれば，サイズは大きくしたほうがよい– 多重度が下がれば，サイズは小さくしたほうがよい– 平均位置決め時間とデータ転送速度の積はストライピングのコストと利益のバランスを表している• コスト：ストライピングしたことによる位置決め時間の増加• 利益：ストライピングによる転送速度の増大• 多重度がわからないときの近似式

P: 平均位置決め時間
X: データ転送速度
L: 多重度Z: リクエストサイズ
N: ディスク数• この式でも，平均位置決め時間とデータ転送速度の積PXが出てきている

2× 平均位置決め時間 × データ転送速度3
データ工学特論（３）PX ( L − 1) ZN

データ工学特論（３）56ChenとLeeの研究(1993)
ChenとLeeの研究(1993)

RAIDの例（１）－ScaleRAIDの例（１）－Scale ArrayArray• RAID-5 の最適ストライピングユニットサイズ– 読み出しが多い場合は RAID-0 と同じ– 書き込みが多い場合は，read-modify-write を行うよりもフルストライプアクセスのほうが速い⇒ストライピングユニットサイズは小さくするとよい• ディスク数と最適ストライピングユニットサイズ– 読み出し：ディスク数が増えるほど小さく– 書き込み：ディスク数が増えるほど大きく• 読み書きが混在するときは• Thinking Machines社 Scale Array （1992）
同社の並列計算機 CM-5 用 RAID-3，大規模数値計算用
CPUCPUCPUCPUCPUCPUCPU
CPU
CPU
CPU
CPU
CPU
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
メモリ
プロセッサ間ネットワーク

20MB/s
バッファ

バッファ

バッファ

Scale Array

1× 平均位置決め時間 × データ転送速度2

データ工学特論（３）

データ工学特論（３）7

データ工学特論（３）822005/11/07

Scale
Scale Array（続き）
Array（続き）

RAIDの例（２）－NCR6298（1992年発表）
RAIDの例（２）－NCR6298（1992年発表）• 最小構成…
– （（SCSI ディスク×２）×４）×３＝２４ディスク
２２データディスク，１パリティ，１スペア• プロセッサ間ネットワークにディスクアレイを直付け– 接続できるディスクアレイの数にほとんど制限なし– 最大１２０ディスク（＝５セット）までテスト済み• ピーク性能（１２０台のとき）– 読み出し：185MB/sec– 書き込み：135MB/sec• NCR社 6298 ディスクアレイサブシステム…RAID-0, 1, 3, 5– 電源・冷却系も多重化
商用システムなので，耐故障性・保守性を重視– 専用コントローラで構成
NCR53C916
NCR53C916

MUX XOR
NCR53C920

データ工学特論（３）read-modify-write 用SRAMバッファ

すべての部品が運用中でも交換可．
自己診断・自動再構
築機能あり

データ工学特論（３）910

NCR6298
NCR6298 （続き）
（続き）

RAIDの例（３）－TickerTAIP/DataMesh
RAIDの例（３）－TickerTAIP/DataMesh• RAID-5の書き込み以外の操作
コントローラの各チャネルがロックステップ（lock-step）動作をするので，バッファは不要• RAID-5の書き込み操作– 旧データ・旧パリティを読み込んでexclusive-OR を取り，SRAM バッファに格納する– ホストから新データが届くと，ただちに SRAMバッファのデータと exclusive-OR される• Hewlett-Packard 研究所の プロトタイプ(1993年発表)– CPU付き「インテリジェントディスク」のアレイ– CPU間に内部接続ネットワーク• 最大転送性能– 10MB/sec (RAID-0, 1, 5)– 14MB/sec (RAID-3)

データ工学特論（３）

データ工学特論（３）– 複数の外部接続インタフェース

CPU
ローカルメモリ

11

CPUCPU
ローカルメモリ

ローカルメモリ

データ工学特論（３）CPU
ローカルメモリ123

2005/11/07

RAIDの例（４）－UCBRAIDの例（４）－UCB RAID-II
RAID-IIUCBUCB RAID-II（続き）
RAID-II（続き）
イーサネット• UCBの ストレージサーバプロトタイプ（1993年発表）– SCSIディスクによるアレイを HIPPIインタフェース（100MB/sec）に接続– XBUSカードと呼ばれる専用ボードで実装

XBUS
card
HIPPIS– ファイルサーバは通常のワークステーションであるが，実際のデータ転送はサーバの遅いメモリを経由しない• サーバはVMEバスによりディスクをコントロールする• データの転送は XBUS - HIPPI インタフェース経由で直接行う

データ工学特論（３）HIPPIDHIPPISHIPPID

ファイル
サーバ
LINK
LINK
LINK
LINK
LINK

4ポート・インターリーブメモリ
4×8クロスバー
スイッチ

XOR

VME

VME

VME
LINK

VME

VME

LINK
LINK
LINK
LINK
VME disk VME disk VME disk VME disk
controller
controller
controller
controller
VME
disk VME
disk VME
disk VME
disk
controller controller controller controller

VME
ケーブル
（制御用）

データ工学特論（３）1314

RAIDの例（５）－Auspex
RAIDの例（５）－Auspex Netserver
Netserver

Auspex
Auspex Netserver（続き）
Netserver（続き）• Auspex社NetServerファミリ– RAIDのデータを，NFS (Network File System) により複数の計算機で共有するためのファイルサーバ専用機– RAIDコントローラ，NFSサーバ，バックアップサーバをそれぞれ専用プロセッサで実装 (Functional Multiprocessing)• Data Guard– ホストプロセッサのUNIXがクラッシュしても，NFSサービスは継続可能になるようなオプションソフトウェア

ネットワークプロセッサ

FMP I/Oバックプレーン（拡張VMEバス）
ネットワークプロセッサ
I/Oキャッシュ
プロトコル
CPU

ストレージプロセッサ
CPU

WRITE
キャッシュ

ファイル
CPU

データ工学特論（３）

データ工学特論（３）ストレージプロセッサ

ホストプロセッサ
UNIX+ユーティリティ

ホストプロセッサ

磁気テープ／
光ディスクライブラリ
装置

UNIX+ユーティリティ
磁気テープ／
光ディスクライブラリ装置

10Base-T/100Base-TX/
FDDI/ATM ネットワーク

FMP I/Oバックプレーン（拡張VMEバス）

NFSサービスは継続！

15

データ工学特論（３）1642005/11/07

Auspex
Auspex Netserver（続き）
Netserver（続き）

RAIDの例（６）－NetApp
RAIDの例（６）－NetApp Multiprotocol
Multiprotocol FilerFiler• Drive Guard– RAID 5のサポート（パリティのみハードウェアで演算）– Normal/Degraded/Rebuildモード– １つのストレージプロセッサ内で複数のレベルのRAIDを混在させることができる• NeTservices– UNIX, Windows のファイルを一元管理• NFS，CIFS (Common Internet File System) プロトコル＊の両方をサポート• Network Appliance 社 Multiprotocol Filer– NetServerと同様の専用機
ただし，単一プロセッサで，UNIXも搭載せず– NFS, CIFS, HTTP (Hypertext Transfer Protocol) の３種類のプロトコルをサポート– RAIDには珍しく，レベル４のみサポート…運用中でもディスク追加による拡張が可能• WAFL (Write Anywhere File Layout)– UNIXファイルシステムと同様のファイルシステム＊CIFS…Windows で用いられるファイルシェアリングプロトコル• 同一ディレクトリ内でUNIX/Windowsファイルの混在も可能
データ工学特論（３）– ただし，メタデータ（データブロックの所在を記録するデータ）をファイルに格納し，これ自体もディスク上の任意の場所に格納できるようにしている。
– NVRAMにNFSリクエストをログとして記録
データ工学特論（３）1718NetApp
NetApp Multiprotocol
Multiprotocol Filer（続き）
Filer（続き）

RAIDの例（７）－SiliconGraphics
RAIDの例（７）－SiliconGraphics Challenge
Challenge RAID
RAID

• WAFLとRAID-4– RAID-5が考案された理由は，RAID-4ではRead-ModifyWrite操作が多数あるとパリティディスクがボトルネックになるためだった。
– WAFLでは，Read-Modify-Writeを行わない• 数百のリクエストを，近接するいくつかのフルストライプにまとめて書きこみ，ディスクアクセス回数を減らす。

• Orthogonal RAID の一例

D2

D3w

Pww

w

D0w
w

www
データ工学特論（３）

データ工学特論（３）D2D3PWAFLww

D1ww

w
w

w
w

19RAID-5

RAID-5RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5Storage-control
Processor

CPUメモリ

18GB disk
SCSI SCSI SCSI SCSI SCSIRAID-4

D1

RAID-5SCSI-2

D0

ホスト

RAID-5

RAID-5

データ工学特論（３）2052005/11/07

SiliconGraphics
SiliconGraphics Challenge
Challenge RAID（続き）
RAID（続き）

RAIDの例（８）－Sun
RAIDの例（８）－Sun Microsystems
Microsystems StorEDGE
StorEDGE• 九州大学情報基盤センターでの構成例

ホスト

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

RAID-5

磁気テープ
ライブラリ
装置

RAID-5…１つ約72GB

実効容量の総和：2.1TB
データ工学特論（３）

データ工学特論（３）21

ディスクアレイのまとめ（１）ディスクアレイのまとめ（１）ディスクアレイのまとめ（２）ディスクアレイのまとめ（２）• RAIDの重要性• RAIDの比較– RAID-0 と RAID-1– RAID-2 と RAID-3– RAID-3 と RAID-5• ハードディスクの基礎知識• RAIDのパターン– Level 0 (Non-Redundant)– Level 1 (Mirrored)– Level 2 (Memory-Style ECC)
– Level 3 (Bit-Interleaved parity)– Level 4 (Block-Interleaved Parity)– Level 5 (Block-Interleaved Distributed Parity)• 大きな読み出し，小さな読み出し• 大きな書き込み，小さな書き込み• RAIDの信頼性を左右する要因– ２台のディスクの故障– システムクラッシュ– 訂正不能なビットエラー• MTTDL (Mean Time to Data Loss)

Level 0+1, Level 6 といったカテゴリもある

データ工学特論（３）

データ工学特論（３）2223

データ工学特論（３）2462005/11/07

ディスクアレイのまとめ（３）ディスクアレイのまとめ（３）ディスクアレイのまとめ（４）ディスクアレイのまとめ（４）• RAIDの信頼性を上げるための方策• 最適なストライピングユニットサイズの選択– 大きくするか，小さくするか，トレードオフの問題– 解析的に求めるのが難しく，今後の課題となっている• RAIDの例– Thinking Machines 社 Scale Array– NCR社 6298
– Hewlett-Packard研究所 TickerTAIP/DataMesh– UCB RAID-II– Auspex NetServer– NetApp Multiprotocol Filer– SiliconGraphics Challenge RAID
– Sun Microsystems StorEDGE– スペアディスク– 状態情報– Orthogonal RAID
• RAIDの性能を上げるための方策– バッファリングとキャッシング
– フローティングパリティ– パリティロギング
– パリティデクラスタリング，– 分散スペアリング，パリティスペアリング– 仮想ストライピング
データ工学特論（３）

データ工学特論（３）25

26

さて，ディスクアレイの次のお題は…
さて，ディスクアレイの次のお題は…

次のお題は
次のお題は

• ディスクアレイ，RAID⇒ディスクを複数台並べて，これを並列に駆動する仕組み
非並列のアプリケーションからの要求を処理するための仕組み• 並列ファイルシステム– 並列アプリケーションプログラムに大容量のデータを読み書きさせるためのファイルシステム• 並列入出力機構– 並列アプリケーションプログラムの各プロセスが同時に読み書きを行うための入出力機構（インタフェース，ライブラリ）• それでは…
– 並列計算機が複数のディスクを持っているときにはどうしたらよいのか？
– 並列プログラムに大量のデータを高速に供給するためにはどうしたらよいのか？

並列ファイルシステム
並列入出力機構
データ工学特論（３）

データ工学特論（３）27• しかし，その前に，並列計算機とはどんなものか，簡単に見ておくことにしよう– Flynn の分類– 共有メモリ型，分散メモリ型– 超並列計算機– SMPとSMPクラスタ
データ工学特論（３）2872005/11/07

並列計算機のアーキテクチャ（１）
並列計算機のアーキテクチャ（１）

並列計算機のアーキテクチャ（２）並列計算機のアーキテクチャ（２）• Flynnによる分類(1966)– データと命令の流れによる有名な４つの分類– 簡潔ではあるが，すべての計算機がこれで分類できるかどうかは，意見が分かれるところでもある• SISD (Single instruction stream, single data stream)– 通常の 1CPUの計算機– 命令パイプラインを持つスカラープロセッサ（RISCチップ）をこれに含める考え方もある• SIMD (Single instruction stream, multiple data stream)
制御ユニット– 単一の制御ユニットから全プロ命令のセッサに命令をブロードキャスト
ブロード– 各プロセッサは１命令（または１キャストクロック）ごとに同期をとりながら プロセッサ実行– ベクトルプロセッサをこの分類に含める考え方もある

data stream
instructionstream

singlesingle
SISD

multiple
SIMD

multipleMISD

MIMD

データ
データ工学特論（３）

データ工学特論（３）29

並列計算機のアーキテクチャ（３）並列計算機のアーキテクチャ（３）並列計算機のアーキテクチャ（４）並列計算機のアーキテクチャ（４）• MISD (Multiple instruction stream, sigle data stream)• 共有メモリ型並列計算機
multiprocessor と呼ばれることもある– 多重命令流・単一データ流– 用語としては存在するが実在しない，という考え方と，ベクトルプロセッサをこれに含める考え方とがある• MIMD (Multiple instruction stream, multiple data stream)– 各プロセッサに制御ユニットが付属– 各プロセッサは独立 制御ユニットに動作（別の命令をプロセッサ実行できる）

データ

データ工学特論（３）

データ工学特論（３）

CPU

CPU

CPU

30

CPU

CPU

メモリ

メモリ

相互結合網

メモリ

メモリ

メモリ

– 相互結合網にはいろいろな機構がありうる• バス• クロスバースイッチ

命令31

データ工学特論（３）3282005/11/07

クロスバースイッチ
クロスバースイッチ

並列計算機のアーキテクチャ（５）並列計算機のアーキテクチャ（５）• プロセッサどうし，プロセッサとメモリを接続する
メモリ

メモリ

メモリ

• 分散メモリ型並列計算機
multicomputer と呼ばれることもある

メモリ

CPU

CPU

メモリ

CPU

CPU

CPU

メモリ

メモリ

相互結合網

CPU

– 相互結合網にはいろいろなトポロジがありうる• オメガ網• ハイパーキューブ• メッシュ
• トーラスCPU

データ工学特論（３）

データ工学特論（３）33

超並列計算機
超並列計算機SMPとSMPクラスタ
SMPとSMPクラスタ• 「超」がつくほど多数のプロセッサを搭載した計算機– 「超」の厳密な定義はないが，最近では1024台くらいのプロセッサを搭載したものも珍しくない– そうなると，CPU（central processing unit）という呼称はあまりなじまないので，１つ１つのプロセッサをPE（processingelement）と呼ぶこともある• スケーラビリティ（scalability，規模適応性）• SMP (symmetric multiprocessor)– プロセッサの数やメモリの容量を増やすのが容易なこと– 予算の制約を除き，搭載できるプロセッサ数に制限が（あまり）ないこと– 共有メモリ型並列計算機の一種– すべてのPEが対等– メモリのどこも同等にアクセス可

34

PE

PE

PE

相互結合網
メモリ メモリ

メモリ• SMPクラスタ– SMPを分散メモリ型並列計算機のようにつないだもの
SMP

メモリ

SMP

メモリ

SMP

メモリ

相互結合網

データ工学特論（３）

データ工学特論（３）35データ工学特論（３）3692005/11/07

並列計算機におけるディスク入出力の問題点
並列計算機におけるディスク入出力の問題点

並列入出力の必要性
並列入出力の必要性• 分散メモリ型の並列計算機におけるディスク入出力– 共有メモリではないので，それぞれのメモリにデータを読み込む必要がある• 分散メモリ型並列計算機– 多数のPE（processing element）と大容量の主記憶によって大量のデータを用いた大規模な計算を行うことができる– 複数のディスクを搭載し，それを並列に駆動できる• 高度な科学技術計算では，計算の精度をあげようとす
ると必要なデータの量が急激に増大することが多い– そのようなプログラムは，計算時間を短縮するため，並列化されることが多い– 並列プログラムにディスク入出力を行わせる必要が出てくる

相互結合網

それぞれのプロセッサのメモリにデータが読み込まれなければならない

データはメモリのどこにあっても，すべてのプロセッサから使える

データ工学特論（３）並列プログラムのデータ入出力
並列プログラムのデータ入出力• 単一のPEが代表で入出力を行う⇒大容量のデータの入出力には時間がかかる• 複数のPEが同時に入出力を行う⇒プログラマが制御するのは面倒

データ工学特論（３）38

並列入出力のイメージ
並列入出力のイメージ• 複数のPE上で動作している各プロセスが，自分の必要とするデータを並列に入出力• あたかも，それぞれがローカルディスクにアクセスしているかのように（物理的にはそうでなくてもよい）

前処理部分（単一PEモード）

計算部分（並列モード）プロセス

PE

データの流れ
後処理部分（単一PEモード）

データ工学特論（３）

データ工学特論（３）

37

ディスク
39

データ工学特論（３）40102005/11/07

並列入出力のためのさまざまな手法
並列入出力のためのさまざまな手法• 並列ファイルシステム– どちらかというと，複数のディスクをまとめて１つのファイルシステムのイメージを提供• 並列入出力ライブラリ– どちらかというと，ディスクはバラバラで，それを並列に使うイメージを提供• 並列プログラミングライブラリの入出力インタフェース– MPI (message passing interface) のようなライブラリのなかの並列入出力インタフェース

データ工学特論（３）

データ工学特論（３）4111