TWI338219B - Raid 3+3 - Google Patents

Description

1338219 九、發明說明： 相關申請之交互參照 本申請案係有關於專利申請號（代理人案號; ARC9-2003-0014-US1) ’ 標題為「變形碼（Anamorphic

Codes )」、專利申請號（代理人案號 ARC9-2003-0015-US1 )，標題為「自主同位交^ (Autonomic Parity Exchange)」、以及專利申請號（代理 人案號ARC9-2003-0016-US1) ’標題為「由冗餘陣列之 多路徑資料檢索（Multi-path Data Retrieval From

Redundant Array)」，以上皆於此同時共同審查、共同讓 渡和申請’且每一於此被納入作為參考。本申請亦關於共 同審查與共同讓渡的專利申請號（代理人案^ YOR9-2003-0069-US1) ’亦於此被納入作為參考。 【發明所屬之技術領域】 本發明係關於儲存系統。特別是’本發明係關於為儲 存單元之陣列（array of storage units)提供更佳的性能、 保護和有效率的系統和方法。 【先前技術】 以下疋義於文中使用，並為了例示而非限制的目的被 提供： 「元（element)」係一儲存單元上的—資料區塊（b|〇ck of data) ° …γ基本陣列（base array)」係一組「元」，係為一陣 歹J單元包占錯6吳或抹除更正碼（Error or Erasure 理慈 4BM/04077TW，ARC9-2003-0〇40(JL) 6 1338219

Correcting Code)。 陣列（array)」係一組儲存單元，具有一或更多基 本陣列。 「儲存條（stripe)」係一陣列中的一基本陣列。 η為基本陣列中資料單元之數目。 r為基本陣列中冗餘單元之數目。 m為陣列中儲存單元之數目。 d為陣列之最小漢明（Hamming)距離。 D為儲存系統之最小漢明距離。 丨〇w為執行更新寫入(update write)之 （丨〇 的數目。 陣列中儲存單元之總數為 m=n+r ° 儲存系統一般倚賴獨立磁碟冗餘陣列（RAID)技術 ，- 來保護，以避免儲存單元故障（failures)導致的資料遺失。 ^基於儲存單元的容量增加，目前的獨立磁碟冗餘陣列 十之達2它們實用性的極限。文中使用符號(χ+γ)來表 j ΐ料單元和丫冗餘單元。現今大部分的系統使用獨立 π 4、几餘陣列 5(η+1)或單一鏡射（s_e mirrorin9 } φ lr+，來作為基本卩車列設計。這兩種儲存系統配置都具有 · 农小漢明賴D=2，因祕護單—儲料元轉。如种 : 所用’「距離（distance)」意指最小漢明距離。然而 個磁碟故障（drive failure)和硬體錯誤（ha「d e|T〇「）會 增加，立磁碟冗餘陣列5系統配置中，資料遺失事件之^ 生。實務上已觀察到多個儲存單元遺失導致資料遺失。" 許多陣列配置被提出，供處理這樣的高故障率。例 W.^4IBM/04077TW · ARC9-2003-0040(JL) 1338219 如，具有距離D=3的獨立磁碟冗餘陣列6(n+2)、具有距 離D=3的雙鏡射(1+2)、以及具有距離D=4的獨立磁碟冗 餘陣列51 (n+(n+2))都被提出作為處理高故障率之解決辦 法。不過，所有這些陣列配置都有會如同表一和圖二說明 之缺點。 因此仍需要提供相較傳統方法具有較佳性能、保護和 效率的陣列配置。

【發明内容】 提供較傳統方法為佳的性 本發明提供一陣列配置， 能、保護和效率。 發明之優點她合至三個:祕儲存單元和三個核 疋的一陣列控制器提供:(3+3)配置在本文中係指 ，立3+3 _。資訊以對稱最大距離分隔碼 (symmetric Maximum distance Separation code) ‘貝料儲存子系統上，對稱最大距離分隔碼之 碼、EVEN0DD碼或EVEN〇DD碼之衍生碼、 ί i e ;omon碼。陣列控制器決定核對儲存單元之内 列㈣H二個㈣料和核對儲存單元之抹除，可由陣 障儲存單元（資料和檢查）之故 维错㈣絲/。：科儲存子系統上的資料遺失前發生。在 輸二” 二夺二陣列控制器只使用六個輸入 梅元之抹除，可由陣列控制器來 更&個輸入輪出作業中，二個為讀取作業，四個為 埋慈 4旧M/04077TW • ARC9-20〇3-〇〇4〇(JL) 8 1338219 寫入作業。t明確地，讀取作業由尚未更新的 取資料’而四個寫入作業將資料寫入已更新之ί:儲 存早兀、以及二個核對儲存單元。 、 【實施方式】 本發明提供新的儲存系統配置，其較先前 ，己置具有顯著優點。在此而言，本發明之儲 提供性能、保護和效率之最佳結合。本發明存♦έ 亦使得用於處理錯誤的全新技術變得可能， 專級。舉例來說，見專利申請號（代理;^ RC9-2^)3-G()14七S1) ’ 標題為「失真碼（Anam〇^ ^odes )」、專利申請號（代理 ARC9-2003-0015-us”，標題為「自主同位交J (^ut〇nomic Par丨ty Exchange)」、以及專利申請 Λ案號ARC9-2003_0016_US1),標題為「由冗餘 (路徑貧料檢索（Multi-path Data Retrjeval Fr〇m Redundant Array)」，以上皆於此被納入作為參考。 圖-顯示根據本發明之獨立磁碟冗餘陣列3+ 子系統勘。子系統勘包含陣列控制器1〇1 ; ^ 的二個貢料儲存單元A、B和c;以及包含冗餘的二 個核對儲存單元P、Q和R。資料儲存單元A、B、和c [ =對儲存單it P、Q和R，典型係驗碟機（_⑽ D_，HDDs) ’然文中稱為儲存單元，因為本發明可應 憶^:二如隨機存取記憶體儲存裝置： ϋΪί A R Γί裝置）之陣列形成的儲存系 統。贿早兀A、Β、C、p、Q和R透過介面1〇2 邱 S 4IBM/04077TW，ARC9-2003-0040(JL> 9 1338219 列控制器101溝通。p車卩彳^^丨$彳 他杵制Μ Λ 透過介面103和其 他控心以及主錄（未顯示）溝 列控制器1〇1和多個儲存陣列溝通。U㈣配置〜午陣 ，存子系、，4 100之配置被稱為對稱碼（sy_et「jc code)，其中資料儲存單蚊數目和冗餘儲存單元之數目 相^ ’且為MDS。陣列控制器101從資料單元之内容來 計算冗餘資訊’使得所有資料可從六個儲存單 個恢復。

有幾個方法計异冗餘資料。較佳方法為使用 Winograd碼。Winograd碼為高度有效率的編碼，只利用 互斥或（exclusive-OR ’ XOR)作業來計算冗餘資料。有 高度有效率的Winograd碼供計算3+3碼，如專利申請號 (代理人案號YOR9-2003-0069-US1 )，於此被納入 參考。也有延伸至EVENODD碼，只利用互斥或作業， 然而它較Winograd碼不有效率。舉例來說，見M B丨aum 等人的「EVENODD :供容忍獨立磁碟冗餘陣列架構中雙

磁碟故障之有效方案（EVENODD : An Efficient Scheme For Tolerating Double Disk Failures In A RAID

Architecture)」，旧EE Trans, on Computers，Vol· 44, No. 2，pp. 192-202，Feb. 1995 以及 M· Blaum 等人的 「EVENODD 碼及其概述（The EVENODD Code and its

Generalization)」，高性能大量儲存與平行輸入/輸出：科 技與應用（High Performance Mass Storage and Parallel I/O : Technologies and Applications)，H. Jin 等人編輯， lEEE&Wiley Press, New York, Chapter 14, pp. 187-208, 冲怒 4旧M/04077TW * ARC9-2003-0040(儿) 10 2001 〇 獨立磁碟冗餘陣列3+3儲存子系 (data efficjency)為 1/2。想 死 100 之貝枓效率 ㈣瓜达土 乂；為/2獨立磁碟冗餘陣列3+3陣列之 Ϊί产:ί:ί大儲存系統之—部分的儲存子系統，在關 子糸統提健鑛點。 糾·存 何一 立磁碟冗餘陣列3+3子系統100可以容忍任 二:存早7"之故障，而不遺失資料組。這是最大距離 ^ 質.:rj^nce Se陶tion ’MDS)抹除碼之 例如，磁碟冗餘陣列3+3儲存子系統10 用的=_d碼、EVENQDD、或EVEV〇DD碼之衍^ 二之恢復力容許以較傳統 二不緊急的方式，對獨立磁碟冗 3 ϋ存糸統1⑻做修護。亦即，藉由提供更多 〔故障子系統的機會增加’藉此容許在肇因於 ΙίΐΓίΐϊ之資，失之前有較長間隔。此外，藉由保 :土：克中的，存單凡數目低，相較於使用大數目儲存單 凡之子糸統’每-子系統中單元轉機會減少。 : 〇=2呀（即有剩餘冗餘），在修護階段中有一額外 j疋，谷許在修護過程令]桃任何使用中的單元之進 一v、或許小的資料遺失事件。此外，當一或更少儲存單 獨碟緣料1 3+3子系統湖耕列控制器 ,,可1 攸回傳不正確資料之任何儲存單元來的資 料0 、 ®.€4IBM/〇4〇77TW . ARC9-2003-0040(JL) 11 -—-__ 表一 獨立磁碟冗餘陣列配置 ---------- 距離 '—---- 儲存效率 寫入損失 獨立磁碟冗餘陣列5 2 ----- 93.8% 4 鏡射 2 50% 2 獨立磁碟冗餘陣列6 3 87.5% 6 獨立磁碟冗餘陣列2+2 3 50% 4 2x鏡射 3 33.3% 3 獨立磁碟冗餘陣列n+3 4 81.3% 8 獨立磁碟冗餘陣列3+3 4 50% 6 獨立磁碟冗餘陣列51 4 43.8% 6 3x鏡射 4 — 25% 4 表 比較不同傳統糸統配置與根據本發明之獨立磁 碟冗餘陣列3+3 魏置之資料儲存效率和寫入性能損 ^penalty)。第—（最左）欄列出_些傳統系統配置， 表-的第-攔中所列出的不同系統配置，第二_示复^ 小漢明距離，第三攔顯示資料儲存效率，而第四攔 入性能損失。每一個別系統配置之資料儲存效率值'，、勿、寫 備分（spares)，係假設m=i6個儲存單元之陣大％、略 計|。寫人性能損失値代表小區塊寫人之輸入輸出作g 數目0 邱慈 4旧M/04077TW . ARC9-2003-0040(儿) 12 1338219 圖二為比較表一所列系統配置經過一段時間的相對 保護（relat丨ve protection)的圖。橫座標列出系統配置， 包含根據本發明之獨立磁碟冗餘陣列3+3系統配置。長條 指出每一個別系統配置所提供的相對保護水平，如縱座標 所定量的。在圖二之範例中，假設m=16的陣列大小、平 均故障時間間隔（MTBF)為1百萬小時之250GB儲存 ，元、以及每1014傳輸位元中有彳的硬體錯誤機率。在保 護水平1之水平線201指明所選的保護目標：每5年每百 萬儲存單元有1 f料遺失事件。從圖二左邊開始，獨立磁 碟冗餘陣列5系統配置和鏡射系統配置（皆為距離d=2 的解決方法）提供的保護水平未達所選的保護目標（線 2〇1) ’顯露需要比這兩個系統配置提供的更強的解決方 法。距離D=3的獨立磁碟冗餘陣列6(n+2)系統配置有高 ，率’但於可靠度目標落後甚遠。對稱2+2⑽配置和 2x鏡射系統配置都是距離D=3的解決方法，而徘徊在所 ^護目標（線201)附近α這兩個系統配置有類似保護 &鏡射配置設計係用效率來換取性能。獨立磁 ，^陣列η+3系統配置為距離D=4的解決方法，且有 ’但具有極差寫入性能以及實質上和距離d=3的解 ίί面護水平。因此要達軸率，需要在可靠 較其 明之獨立磁碟冗餘陣列置 =、!，根據本發 的系統晴最= 統配置有相同寫入行為。3X鏡射系統設 liii4IBM/〇4〇77TW ARC9-20〇3-〇〇4〇(JL) 13 1338219 換得較佳寫入性能。圖二所示所有距離D=4的系統配置， 係具有對未來世代（>4錄量級）儲射、統足夠的保護 空間（headroom)。 根據本發明之一獨立磁碟冗餘陣列3+3系統配置達 到距離D=4，而只需要六個輸入輸出來做小區塊寫入。 &線性MDS碼使用傳統更新技術，來基於資料中的改 變而更新同位（_ies)。傳統技術需要從資料磁碟（咖 φ drive)讀取舊資料’從同位磁碟讀取對應的舊同位，寫入 新資料’計算新同位’並將新同位寫入同位磁碟。基於資 料，變而更新同位之傳統技術於文中將被稱為更新同位 之正向方法（forward method)」。因此，正向方法中執 行更新寫入要用的輪入輸出數目為： I0wf^d = + (l + r) , 醜酸料和同位寫入Siii同位 =2D (1) 在MDS碼中可用來更新同位的第二個方法 ^新同位之「互補方法（c〇mp丨ementary⑺她。。 ίίϊΐίΓ，現存資料先由尚更新的資料磁碟中讀取， 接者新貝料與随被寫人。互補更新方法巾執行 入要用的輸入輸出數目為： ，寫 IOw comp 0 — 1) v-V-, 讀取互補資料 (1 + r) ^-v-· 寫入新資料和同位 + m (2) 理慈 4旧M/04077TW，ARC9姻3 〇〇4〇(⑴ 因此， 則 互補方法巾有比傳統正向方法有效率的情況。當： (3) I〇W_py㈤細 n+r^2(r+1) (4) n^r+2 * ㈣4顯示有高度冗餘的陣列配置藉使用互補方法 i^u/νΓ1位係有較佳的輪入輸出效率。互補方法也更平 散輸人輸出負載㈣統之儲存單元，因為每一裝置 t = 3出—不是讀取就是寫人。相反地，正向方法 式。例如當附近的資料被快取 互補方法也有較佳實施特性。 ^肢財絲麟寫人時，㈣之

° ^ D=r+1 ； J ^MDS的情形中’執行—更新的輸人輸出的數目 為丨〇Wfwd=2D。對使用互補方法的對稱碼更新⑽，’ μ IOwsym=m ° =n+r =2r (5) -2D-2 因此，純使紅向更财法的—般Mds 形，省下兩個輸入輸出。此意謂著再相同寫入性能^ = 稱碼可達到比一般MDS碼多1的最小距離。 T子 理慈 4IBM/04077TW ‘ ARC9-2003-0040(JL) 15 1338219 方法參新寫A入至單元B的情形。使用互補 寫入單元B :而寫It讀，：，新資料被 統正向方法需要從單元Β、Ρ &和R Ϊ:相 二，以及將新丄 要八個輪入輸Ϊ 個輸入輸出，而傳統正向方法需 輸出來做更新要四個輸入 系統設計及其衍生可用ίί 冗餘陣列51 以六個輸入輸出達到距離D=4，但效^〈(^)的結合， 分散同位（distributed parity)μ 士。 餘陣列3+3系統配置—起使用， spot)。熱點會在資料存取ϋ (hot 冗餘陣列5使用分散同位（亦稱^磁碟 parity)來避免因有專屬同位儲存單^==「的 冗餘陣列4)而導致的熱點。使用 碟冗餘陣列系統會因讀取_修改_寫入作蜀立磁 有熱點。而使用互補更新方法的獨立磁碟冗上 衡分佈之一方法。此牽涉至 =y，她）平 元組的資料’使得每，存單元有所有^= 遍佈儲f單 Q和R)類型的元（elements)。參照圖三 ^ 到6顯示為行（她嶋），们到6顯示為列（「〇=)。1 理慈 4旧M/04077TW，ARC9-2003-〇〇4〇(儿) 16 1338219 右轉-單元。清楚地，梅其 ?，ΐ發：二存以列， 置、光學儲存裝置、和磁帶儲存裝:) 糸統。此外’它適合於虛擬』 network-attached storage ) 士丨。匕更可應用於任何冗餘系統，其中有將一冗 ίΐ irC,〇mP〇nent) (subset) ^

JiSlir^~"^*(donationo^> 雖然以上發明已為了解清楚之目的 — 是，某些改變與修改可被實施而在所&以 之乾：内。因此’目前實施例要被當成例示性而非 限^性，且本發明不欲被限制在文中所給細節，而可 附申凊專利範圍之範疇及均等物内修改。

【圖式簡單說明】 明，ίϊΓ係以範例而非關㈣式，於所關式來說 月/、中類似參照編號表示類似元件，且其中： /圖一顯示根據本發明之獨立磁碟冗餘陣列3+3儲存 子系統； 圖二為比較圖，比較不同傳統系統配置與根據本發明 之獨立磁碟冗餘陣列3+3系統配置的相對保護；以及 圖二顯不根據本發明之獨立磁碟冗餘陣列3+3儲存 叶驻 4旧M/04077TW，ARC9-20〇3-〇〇4〇(儿) 17 1338219 中子系統被配置為複數個儲存條，每-儲存你 【主要元件符號說明】 100獨立磁碟冗餘陣列3+3儲 101陣列控制器 糸、，先 102介面 201水平線 103介面 ;'!!#： 4IBM/04077TW · ARC9-2003-0040(JL) 18

Claims (1)

1. 喲年丫月7^^£本 十、申請專利範圍： 1· 一種資料儲存子系統，包含： 三個資料儲存單元； 三個核對儲存單元；以及 -陣列控制n ’耗合至該三個轉儲存單元和該三個 2對儲存單元’該_控㈣決定該核對儲存單元二内 容，使得該資料儲存單元和該核對儲存單元之任何三個抹 除（erasures)可由該陣列控制器更正； 其中該陣列控制器在決定該核對儲存單元之内容時， 只使^六個輸人輸出⑻）作#來諸包含在任—該資料 儲ϊΐ元和該核對儲存單元内之一資料區塊，使得該資料 儲$單元和該核對儲存單元之任何三個抹除可由該陣列控 制is更正。 如7求項1所述之;貝料儲存子系統，其中該資料儲存子 系統係以一對稱的最大距離分隔碼（symmetric Maximum Distance Separation code)而儲存資料。 儲存子系統，其中該最大距離分 ，其中該最大距離分 5·如請求項2所述之資料儲存子系統 隔碼係為一 EVENODD碼。 ’ 統，其中該最大距離分 6·如請求項2所述之資料儲存子系 邵慈 4旧M/04077TW . ARC9-20〇3-〇〇4〇(儿） 19 隔碼係為-EVENODD媽之-衍生碼。 7業，其中該輪入輸出作 入你L為#取作業而該輸人輸出作業之中四個A官 四個為寫 尚ί更儲f子系統，其令該讀取作業由 =寫入已更新之該資料儲存單元、以及該三個核^ί 子系統，其巾任何三個資料 料儲存子纽上的===轉，可麵存於該資 存询，其"料可自一部 料儲存單元1 /其所有三個資 系統上的任何資料。 卫J益可恢復儲存在該資料子 l ㈣存在—㈣儲存子线上㈣料之朴4 貝枓儲存子系統包含三個資料儲存單元、的三貝1之方^^玄 疋以及-陣列控制器，該 私對储存単 存單元和該三個核對儲存^控制益搞合至遠三個資料儲 儲存單元之内容列控制器決定該核對 之任何三㈣柯由子單元 1-1!4IBM/04077TW - ARC9-2〇〇3-〇〇4〇(jL) 20 及 從尚未更新的該兩個資料儲存單元讀 取互補資料；以 寫入資料至已更新的該資料锉;„ 核對儲存單元。 貝卄儲存早兀，以及至該三個 13.如請求項12所述之方法，发中兮咨 ^ 一對稱的最大距離分隔碼而儲存資料二貝科儲存子糸統係以 一 Wir^gtH3。所述之方法’其中該最大距離分隔碼係為 1—娜，其靖卿蝴包含 ====觸之找，料歸妓料隔碼包含 其中該最大距離分隔竭包含 18_如請求項12所述之方法，其中任 J故障和核對儲存單元的故障，可在儲存㈣資元 系統上的資料遺失前發生。 、貝枓儲存子 19·如請求項12所述之方法，更包含自 單元恢復資料之步驟。 刀了 °只取儲存 卯慈 4旧_4077TW，ARC9-2〇〇3_〇〇4〇(jl) 21