TW409215B - Parallel file system and method for multiple node file access - Google Patents

Description

A7 B7 五、發明説明。） ~~ ~~~ ~~ .發明頜碰： 本發明係有關電腦及電腦系統，尤係有關—種在多個電 腦上執行的檔案系統，其中每一電腦有其本身的作業系統 實例，且爲了資料共用而與連接共用磁碟的網路耦合，亦 即本發明係有關一種共用磁碟檔案系統。 口 術語詞彙袅： 雖然字典也提及本文所用的某些術語的意義，但下文所 7JT與本發明有關的某些術語之詞彙表將是相當有用的。 .資料/權案系統資料（Data/File System Data):只有在 一特定應用程式的環境下具有意義的任意位元串。 •檔案（File): —電腦應用程式可存取的一命名位元串。 檔案具有某些標準的屬性，例如長度 '修改時間、及 最近存取的時間。 _中介資料（河“以以3):檔案系統軟體所產生的一種 控制結構，用以描述—檔案的結構、及包含檔案系統 的磁碟之使用情形。應用於此類檔案系統的特定中介 資料類型有： -目錄（Directory):使一名稱與一組資料相關聯且以 一檔案索引表示之控制結構。 -檔案索引（inode):包含檔案屬性 '及包含構成該 樓案的資料的磁碟區之一系列指標。如果構案較 大’則間接區段可補充檔案索引，其中間接區段 係以額外的指標補充檔案索引。 " 分配對映表（A1丨ocation maps): 指示磁碟的特定區 -4 - 本紙狀度適用中_家轉（CNS) Λ4^ (21QX 297公费） ------—. i , . I I .~J I II .*1:: 1--1 I^---I- - I 1·: m II 丁 »-1-='" ί請先閱讀背面之注意事項再填释本頁} 經濟部中央標隼局員工消合作社印製 409215 A7 B7 五、發明説明（2 域（或諸如檔案索引等其他控制結構）是否在使用 中或可使用之控制結構。分配對映表可讓軟體將 可用的區段及檔案索引有效地指定給新的檔案。 -登錄（L〇gs):在系統故障時用來使其他類型的中介 資料保持同步的一组記錄。登綠包含用來描述對 多個結構進行相關更新的單—記綠。 樓案系統（File system):—種軟體元件，利用與檔案資 料相關的乂〇]^11及？031乂這組標準所指示之方式，而管 理可存取資料的一组指定磁碟。亦利用該術語描述— 特定组磁碟内包含的資料及中介資料組。 共用磁碟檔案系統（Shared disk file system) · 一種檔案 系統，其中多個電腦分享檔案系統的管理，而不將所 有的管理指定給單—實體。所有的電腦都注意是否有 任何電腦可能執行管理資料所需的任何任務a可在需 要時將特定的任務指定給特定的電腦。 共用磁碟連接（Shared disk attachmem): 一種利用通訊 協足而將磁碟連接到多個電腦之方法，使磁碟如同在 當地連接到每一檔案系統。到每一電腦的正確連接通 Λ b疋對此工作並不重要；但包含以網路連接的磁 碟、交換式磁碟連接、或存轉連接等這種形式。關鍵 項目是共用磁碟連接如同在檔案系統當地，且對所有 的標案系統實例如同是同一個共用磁碟。 配額（Quota):—檔案系統限制—特定使用者或一群命 名使用者在該檔案系統的使用率之功能。例如，管二 -5- ' —I ! -n f — [ ^ I ___

'1T 經濟部中决標準局肩工消贤合作社印裝 t紙張尺度適用中國國家標準（CNS ) Λ4規輅 (210X297^^ 經濟部个央標來局貝工消f合作社印製 409215 A7 ._ B7 _ 五、發明説明（3 ) 員可將使用者"John"限制爲檔案系統内的100百萬位元 組。配額是UniX(S.C.O公司的商標）環境中所使用的功 能名稱。 -存取控制表（Access Control List): —使用者可限制在 —特定表中出現名稱的使用者對資料的存取之一種檔 案系統技術。 發明背景： 目前需要將檔案服務提供給各電腦，例如一 MPP電腦及 其他的電腦叢集，這些電腦叢集形成連接電腦的—網路之 一部分，而作爲一共用電腦資源。 現在已有與共用磁碟檔案系統的檔案資料相關之某些"開 放性（例如X〇per^ P0SIX)標準，其中將在各電腦上執行 的計算工作需要存取相同的檔案資料，就如同該資料係存 在於執行工作的電腦當地（以便執行IBM爲不同系統所開 發的系統，請參閲諸如美國專利4,274,139、5,202,971、及 5,226,159)。當多個電腦是-1網路的·一部分，且多個磁碟 是該網路的一部分時，需要產生一種共用磁碟檔案系統， 此種共用磁碟檔案系統與各標準相容，且無須改變在各 MMP或叢集等電腦上執行的多種作業系統實例。 共用檔案系統（Shared F"ile System ;簡稱SFS)(請參閲美 國專利5,〇43，S76)適用於IBM的S/390系统之術語，S/390系 統係在IBM的VM下作業，使各虛擬機器得以共用資料。 共用檔案系統也是一種諸如IBM的IMS及GRS等資料共用 媒介’其中係爲了單一系統的環境開發IMS及GRS，且在 -6 - 本纸張尺度適用中國國家標準（CNS ) Λ4规輅（2⑴X 297公苁） (諳先閱讀背而之注意事項再4艿本頁) *π 409215 Λ7 ___B7 五 '發明説明（4 ) ^ ~~ MVS下GRS係用於共用磁碟儲存裝置的一系統叢集，而且 在此種系統中GRS可在共用磁碟上分配小的鎖定標案，以 便循序進行對資料集的存取。MVS必須循序進行對磁碟上 内容表或目綠的存取，因而作業系統需要執行任何類型的 保留作業。此種方式造成了相當大的系統資源虛耗。 已可修改IBM的DB 2而適用於一多重虛擬儲存裝置 (Multiple Virtual Storage ;簡稱 MVS)/ 企業系統架構 (Enterprise System Architectures ;簡稱ESA)環境中之資料 共用，其方式爲使用IBM的耦合設施，以產生多系統的資 料共用，此種資料共用需要—System/39〇 ParaUd Sysplex 環境，這是因爲需要該耦合設施以傳送高效率且可擴展的 資料共用功能，其中該耦合設施利用美國專利5,463,736所 述的訊息路徑機制管理各處理器間之連接，因而該_合設 施在本質上變成了共用資料的超級單—伺服器。 經濟部中央標準局員工消费合作.社印災 (对先閱讀背而之注意事項#填窍本頁)

,1T 如可能是最佳種類的音訊/視訊檔案系統（IBM用於ΑΙχ作 業系統的VideoCharger伺服器）所提出，以往符合標準的對 •a胳系統之解決方案有賴於將檔案系統層級的要求傳送到 一個可取得資料並傳送回資料的一單一伺服器，或有賴於 將一用户端電腦的中介資料要求傳送到一個可讓原來的電 腦直接提取資料之單一伺服器。IBM也提供了—種被稱爲 虛擬共用磁碟（Virtual Shared Disk ;簡稱VSD)的程式產 品’可讓SP2使用者設定各節點的組態，而作爲主要及輔 助IBM VSD伺服器節點。VSD軟體可讓執行作業系統的各 獨又影像之多個節點存取一個在實體上只連接到其中一個 409215 A7

經濟部十央標準局負工消费合作社印製 —_ 409215 五、發明説明（6 ) — 處理器 ' —交換式網路、一將支援Tcp/ip的高速企業内 網路轉合、一非均一記憶體存取匯流排耦合、或其他類似 的連接方式，即可達到上逑目的。根據本發明，該共用磁 碟構案系統係利用相關聯的管理呼叫支援磁碟讀取及窝入 呼叫。作業系統實例是常見的或標準的，因而無須改變作 業系統即可使用本發明之共用磁碟檔案系統。我們提供了 所需的新服務程式’使本發明的共用磁碟檔案系統可以在 實用的方式下進行。 本發明的共用磁碟檔案系統係在一共用磁碟環境下以— 平行檔案系統之方式作業。本發明將一可擴展檔案服務提 供給具有—穩定游標的系統。本發明也提供一分段分配對 映表。在本發明的可擴展平行檔案系統中，本發明實現了 動態預取。藉由提高緩衝儲存區效能及空間利用率：而提 南本發明的可擴展平行檔案系統中之速度。此外，延伸檔 案屬性支援Unix環境中之存取控制表(Access。_丨 簡稱)，机首次可在—個在—共用磁料境中可擴展 的平行檔案系統中作業。 本發明所作的各種改良可在—共用磁碟環境中對共用磁 碟及檀案環境的多個電腦作有效率的基本檔案控制。本發 明的目錄服務可以有效率之方式將檔案插入資料結構中： 並自資料結構中刪除檔案’而不會使資料結構造成太太的 混亂。此種方式在必須對所要修改的區域取得獨有控 的平行系統中是相當重要的。本發明所開發的分配對映表 能夠在以平行方式配置的同一群磁碟中分配儲存空 本纸狀度s s以!^Tcns （2m — (請先閱讀背面之注意事項再填$本頁)

409215 A7 B7 五、發明説明（7 維持中介資料的完全-致性。這點是相#重要的，因爲可 存取檔案系統的每-電腦都將希望在不必顧及其他電腦中 進行的情形下產錢外的資料^發明的預取轉法計算 可用I/O頻寬及應用程式對資料的需求，以便決定所要預 取的資料量。這點在對1/0的需求可能超過可用頻寬的平' 行系統中是相當重要的。本發明在緩衝儲存區效能上的發 展平衡了多個存取的緩衝儲存區’且緩衝儲存區效能的發 展雖然與平行處理並不相關，但仍是檔案系統的一般性改 反。利用植案屬性作爲-支援機制也適用於非平行樓案系 統；但是在本發明的整體平行權案系统機制中，此種利用 檔案屬性作爲一支援機制是相當重要的，因爲此種方式可 在一平行檔案系統中有效地實施存取控制表。 訂 本發明提供了可在一共用磁碟環境中對同一檔案或目錄 進行平行更新。本發明提供了 —中介資料節點，用以管理 在平行讀取及寫入動作中使用的檔案中介資料3在本發明 的系統中，將符記（token)用於中介資料節點的選擇及識 別，且本發明具有增強符記模式，用以控制檔案大小，並 以智慧型方式緩衝儲存使用檔案存取型樣的位元組範圍符 經濟部中央標準局負工消费合作社印" 記、及使用一位元組範圍符記介面的位元組範固鎖定演算 法。 、 平行樓案更新需要有一些創新之處，這些創新處仔細考 慮到下列問題：在更新來自多個電腦的同—檔案時，如何 有效率地產生及更新中介資料。本發明的—種解決方案是 建立一中介資料節點，該中介資料節點處理—慣地來自多 _________ -10 - 本纸悵尺度適用中國國家標準（CNS ) Λ；5現格（2丨〇'x 297公龙） 409215 A7 B7 五 、發明説明（8 個發端電腦應用程式的某些可改變中介資料之合併。第二 種解決方案是提供一種鎖定架冑，用以有&地對所有需要 (請先閱讀背而之注意事項再填寫本頁) 其服務者識別該電腦。此種方式無須建立—個可能造:瓶 頸的固定管理點。 現在，檔案大小是—種中介資料，用以經常改變平行更 新的狀況。本發明提供了一種在執行的應用程式需要正確 的檔案大小時”及時"取得正確的檔案大小之方法。此 外，本發明重新界定了鎖定技術，用以減少此環境中符記 管理器之虚耗作業。 本發明提供了在無法使用參與共用磁碟管理的電腦時之 檔案系统回復，可能有多種原因使該電腦無法使用，其中 包括系統的故障。本發明提供了一種平行檔案系統回復模 型，並以同步及非同步之方式接管一中介資料節點。 本發明的平行共用磁碟檔案系統可將某些資源的控制權 暫時指定給一特定的電腦，以供修改。在此種情形中，其 他電腦可得知的磁碟上的結構可能處於一不一致狀態，而 且必須在發生故障時修正該結構。爲了處理此種情形，本 發明提供了一種延伸標準登錄及鎖定回復的方法，使其他 經濟部中央標準局員工消费合作社印掣 電腦持續在存取檔案系統上大部分的時得以進行此種回 復。 現在’在UNIX環境中，配額的觀念以其名稱而廣爲人 知。配額是一種可用來管理一空間的起始範圍之一般性觀 念’且可配合諸如S/390所用的作業系統等其他的作業系 統而使用此種觀念。一般而言，當我們考慮到配額時，必 11 - 表纸張尺度適用中國國家標準（CNS ) Λ4規枱（2!〇x 297公兑） 409215 經濟部中央標率局貝工消贽合作枉印" A7 B?五、發明説明（9 ) ' 肩積極地管理配額，使鎖定不會經常被需要用來代表一使 2者分配新的區段。本發明針對配額管理提供了可回復的 當地分配額（local share)，其中情形將於下文中説明之。 見由於配額是一種對—使用者或一群使用者可使用的磁碟 里1限制，所以爲了將該配額觀念用於本發明的平行檔案 系統中，本發明創造了一種由一（存取單一配額檔案的）配 額管理器分配當地分配額以供平行分配之方式。此種方式 對一使用者有多個應用程式實例在共用一檔案系統的若干 不同電腦上執行的情形是相當重要的。本發明開發之方法 在發生故障時有足夠的配額存在時的許多情形中提供了立 即的回復。在某些情形中，需要執行一個諸如υΝΙχ標準 公用程式"qUOtacheck"等的公用程式以完成該回復。本發 明亦開發了一種技術，可在應用程式使用配額的同一時間 執行一 quotacheck公用程式，且只有最小的干擾。 上述這些及其他的改良係述於下文的詳細説明中3爲了 更易於兩解本發明及其優點與特徵，請參閲下文之説明及 圖示。 f付圖簡述 圖1示出一個根據本發明的共用磁碟檔案系統，該系統 包含一個用於各電腦系統節點之符記管理器。 本發明之詳細説明： 設有若干相關元件的本發明共用磁碟檔案系統之一較佳 實施例係示於圖1。如圖I所示，本發明之系統包含一符 記管理器（Π)，用以將鎖定能力提供給參與一檔案系統管 -12^ 本紙伕尺度適用中國國家標準（CNS ) Λ4規2】〇χ 297公筇） (讀先閱讀背而之注意事項再填艿本頁) -丨"

*1T 409215 AT B7 五、發明説明（ΊΟ 理的電腦節點U)、（2) '及（3) ^ (請注意，在本發明的符記 管理器中，必須修改美國專利5,454,108之鎖定管理器） 本發明之檔案系统碼管理應用程式所要求的讀取及寫 入。此種管理使用應用程式要求及共同管理的中介資料， 而在標案系統内產生及存取資料ώ該功能是大部分的處 理’且在所有的電腦中都相同。由於設有適當的符記，所 以琢處理利用磁碟讀取、寫入、及控制功能而直接存取磁 碟0 如圖1所示且於前文中概述的共用磁碟實施例有勝過先 则平行及叢集檔案系統的數個主要優點。該共用磁碟實施 例提供了將資料移動進出所用應用程式之可能最短路徑。 資料或中介資料在此路徑中都没有擋案系統伺服器。可使 用任何可用的路徑，以避免使一伺服器成爲瓶頸或單一故 障點。因爲鎖定管理器中所需的各中央功能並未連接到一 特疋的電腦，所以該等中央功能可自茱一電腦移到另一電 腦，以滿足效能及可用性之需求。 輕濟.邙中央榡毕局員工消费合作.社印^ (诗先閱讀背而之注意事項再琪寫本頁) 訂 爲了作出本發明所述的系統，如前文所述的美國專利 5,454;108示出一種鎖定管理器，而本發明已修改該鎖定管 理器，使其夠處理共用磁碟檔案系統所需的不同回復典 範’本發明也增加了中介資料節點處理所需的一些額外鎖 定狀態，而得以對同-檔案進行平行更新。將在下文的詳 細説明之各節中詳述這些特徵及其他特徵。 (extend.ble hashin.)^ ^ 展的目錄服務 13- 本紙張尺度適用中國國家標準（CNS )八4規枯 (210X 297公犮） 經濟部中央標準局只工消费合作社印t 409215 A7 —-- 五、發明説明（u ) 一 在本發明的共用磁碟檔案系統實施例中，本發明開發了 種以支援極快速插入、刪除、及查詢作業之方式而爲— 且資料a綠進彳了儲存及建立索狀方法，該方法並在可 =任何作業系統實例(甚至是單一作業系統)中實施的—環 兄中以不會和現有的介面程式設計標準（例如X/Opei^〇

Slnglel|nix規格）衝突之方式，而循序擷取（"掃描"）所有 、；料己錄因此，開始時將先説明本發明的循序掃描、 及儲存與查詢資料記錄的基本方法。與先前的建立索引方 法不同’本^'明縱使在循序掃描進行中插人或刪除記錄， 本發明之循序掃描只利用少而有限量的與上下文相關之資 訊(:’游標即可產生可預測的結果。本發明所採用的方 疋在種被稱爲可延伸赫許法的技術領域中。一個實施 勺可L伸赫許法可使用稀疏檔案（sparse ，而不儲存一 個明確的赫許表°因此’由於使用了可延伸赫許法，所以 本發明可在一個符合Unix標準的檔案系統（雖然並未作如 此的限制）中實施目錄。一般而言，可在一 Unix作業系統 3承境中實施本發明之較佳實施例，並將該環境視爲一背 景’然而我們也考慮到使用同一功能的其他作業系統。事 實上’現代的基本系統可配合在實際用於驅動電腦的作業 系統層以上的許多作業系統層而工作。 資料課系統及一般用途的檔案系統係以指定一個可識別 一資料記錄或—檔案的”關鍵字"（"key")之方式，而得以 儲存及擷取資料。在一個_般用途檔案系統中，檔案名稱 是作爲擬取樓案中儲存的資料之關键字；通常將一個儲存 -—— _____-14 - 本紙張尺度適财賴紐: (請先閱讀背面之>i意事項再¾¾本頁} ---A1-----訂------ 40^2n 經濟部妒央橾準局員工消费合作社印製 五、發明説明（1: •且福案名稱及相關於沾桃& > , 關知的檔案存取資訊的結構稱爲目錄。 f引的輔助：錄或檔案名稱較大時，經常使用-種被稱爲 ==料結構來加速查詢…索?丨可在—資料庫表 : = 案名稱—而無須掃描整 *31有數種基於赫許表及諸如ML樹與B樹的平衡式搜 方。爲了達到&好的查詢效能，這些方法 或刪除某—數目的資料記錄之後必須重組至少部分 掛二引例如，將—圮錄插入一 B樹時，可能需要將一B P ’么刀割成兩個新的節點，以便讓出空間給該新的記 ，彔因此，可能需要將—些現有^& _㈣—$ 體位置。 此種方式對f要循序掃描—資料庫表或m统目錄 的應用&式（例如列出_目綠的内容）造成問題。此類應用 程式重複呼叫資料庫或檔案系統，而在每一呼叫中擷取一 « ie錄’直到6 M取了所有的記錄或目錄資料項 時爲止。在各次呼叫之間，必須維護某—數量的與上下文 ，關乏訊（通常稱爲"游標"），以便追蹤該掃描已進行了 多遠。此種方式是必要的，使次一呼叫可繼續擷取其餘的 °己錄保案系統目錄的實施例通常使用—目錄内的一資料 項之實體位置或偏移量作爲一循序掃描的游標。因爲—個 如一 B樹分割的索引更新可能將現有的資料項移到目錄内 的一個不同位置，所以在—循序掃描中插入或刪除登錄的 資料項時，將對掃描的結果有不利的影響；亦即，如果移 -15 本紙張尺度適用中國國家標準（CNS ) Λ4現輅（210x 297公总 (請先閒讀背面之注意事項再填{ί5本頁) 丁 ，-° 4092η A1 一 Β7 躂濟部中央榡準局員工消贵合作社印裝 五、發明説明（13 ) 動一個現有的資料項，則循序掃描可能漏掉該資科項， 者可能送回兩次相同的資料項。 s 爲了解決先前晋知索幻方法所發生的此種問題，我們可 使索引獨丘於資料記錄，或者可在一掃描中错存更多的與 上下文相關^資訊。前—種方式使查詢、插入'及删除作 業的成本更高也更爲複雜，這是因爲比本發明之較佳方 需要有額外的間接層級。當系統需要與現有的程式設計二 面標準相料，U儲存肖上下文相關的資訊之方法二 無法適用了。例如，在X/〇Pen Smgle驗規格中規定的目 綠；I 面（readdir、telldir、及 seekdir 函式）可以一個單一 32 位元値作爲一猶序目錄掃描之游標。 由於本發明所開發的採用可延伸赫許法之較佳方式，本 發明可證明如何以一種支援極快速插入、删除 '及查詞作 業以及循序掃描之方式而爲—组極多的資料記錄料儲存 及索引建^。此外，我們當可了解本發明所開發的較佳方 式之下列情形：-個小而有界限的游標值（通常爲”位元） 足以保證-循序掃描將不會送回任何重複的記錄並可糊取 所有現有的記錄（亦即除了在掃描進行中所插 的記錄以外之所有記綠）。 啟]除 、現在；^豕都知道赫許法是—種以關鍵字㈣)儲存及查詢 資料記綠的技術，如果預先知道記綠數的—適當範圍，則 2許法技術將可工作良好。赫許法工作時，係將可用的错 子空間分成固定數目的"赫許儲存區，，("hash bucket")。爲 了儲存-個記綠’應用一種稱爲，，赫許函數"(Μ

I — J I f許先閱讀背而之：15-意亊項再填圬本頁) i" 丁 -=° 本祕尺度適财 -16 (2Ι0Χ 297公势） 409215 A? B7 五、發明説明（14 function")之對映方式，將關鍵字値對映到一赫許儲 數；將新的記錄错存在由赫許植所指示的赫許錯存區 了以關鍵字尋找-個記錄，計算該記綠的赫許値然後: 搜尋該赫許値指示的儲存區中所儲存的記錄，即 ^ 要求的死錄。 -般而Τ’無法事先知道所要儲存的赫許値數，且該 許植數可能成長到任意大的數。此種情形對標準的赫許技 術造成-㈣題，因爲標準㈣許技術需要在—開始時 知，赫許儲存區的最大數目…種稱爲"可延伸赫許法,， 的先進形式的赫許演算法解力了此_問@，其解決。 ::許函數的値中採用可變數目的位元當一赫許儲存二 =即二裂"該赫許儲存區，亦即加入一個新的赫許 儲^，將—些記錄自現有的赫許儲存區移到新的赫許 =乙Γ新評估赫許函數並多使用一個位元來決定赫 之方式而決定要移動哪些記綠，亦即，額外的 位凡馬零的鱗留在現有的儲存區，而 的記錄則被移到新的儲存區。 凡 ®濟部中央標準局員工消費合作社印31 使用本發明採用可延伸赫許法的較佳實施例時，一索引 ^錄開始時係存放在-單一赫許儲存區，亦即第零個儲 要儲存區能夠容納，不論記綠的赫許値爲何，都 被用來決ί綠放入起始儲存區中，亦即赫許函數的零位元 入-個二赫坪儲存區編號。當起始儲存區填滿時，即加 ‘勺赫許儲存區（亦即第—個儲 始儲存區。現在赫許函數的-位元被用㈣二St -17 本紙張尺度適用中國國家標车 (CNS ) Λ4現格（2l0_x 297公并 409215 A7 B? 铉濟郢中夹滹準局負工消费合作社印絮 五、發明説明（15 赫許値的最低有效位元爲 區，而最低有& ρ ά 〈那些記錄留在第零個儲存 區。要將新的記綠加入第己綠則被移到第一個儲存 許値的最低有效位元之値：=7:儲存；二係取決於赫 區又被填滿且需要分裂。 5在^卜赫許儲存 元來決定是否將要移開第—儲广用赫許函數的最後兩個位 的那些記錄留在第—赫許广?己錄。位元値爲01 記錄則進入一個儲存£_ ’而位元値爲11的那些 的1㈣… 爲3(二進位的"等於十進位 許儲存E巾、°儲存區。适次的分裂不會影f到在第零赫 亦即最後兩個位元爲。。或1。的記錄 二存區’直到第零錯存區已被填滿且亦需要分 彳能在第零儲存區分裂之前’第-儲存區被 填滿且再度需要分裂。 表1中實例所示的—66 - A _L+1 . — Ί 的一進位树（"赫許樹11 )可代表經過 數次赫許错存區分裂之後的目錄結構。利用赫許値位元決 f在每τ内部節點上時要依循哪-分支，⑥以自根到一葉 即點（万式通過該赫許樹，即可找到—記錄。取決於各赫 許値分佈的情形，赫許樹的某—分支可能比其他的分支更 長對於個經過適當選擇的赫許函數（亦即一個產生均 习刀佈的赫沣値之函數）而言，我們預期所有的樹分支都 有近似相同的深度。以深度優先之方式通過赫許樹，即可 元成循序目綠掃描，此時係以自左到右的順序檢查各葉節 點（赫許儲存區）。 _____—__-18- 本紙张纽制巾關家料（CNS〉(別幻97公处） (讀先聞讀背而之注意事項再填寫本頁)

409215 A7 B7 五、發明説明（π 表1

X

X

X 00=0

X 01=1 11=3 經濟部中央標势历負工消费合作社印^ .910;2 110=6 一個赫許樹在經過4次分裂之後的例子： 第〇儲存區分裂成第〇儲存區及第1儲存區， 第〇儲存區再度分裂成第〇儲存區及第2儲存區， 第2儲存區分裂成第2儲存區及第6儲存區， 第1儲存區分琴成第1儲存區及第3儲存區。 以二進位及十進位的赫許數標示赫許樹的各葉節點。 根據本較佳實施例，係將一赫許樹表示爲磁碟上的稀疏 檔案’且於一赫許儲存區分裂時重新安置各記錄，而且循 序目錄掃描係以只回到所有現有資料項一次之方式通過赫 許樹。每一個這類發展的領域都提供了適用於本發明系統 之改良。 在本發明的系統中，稀疏檔案係用於實施可延伸赫許 法。在一檔案系統中，係將寫入一正規檔案的資料儲存在 磁碟的一個或多個磁碟區段中。Unix及類似Unix的檔案系 統介面可在各寫入呼叫之間發出"搜尋"呼叫，而將新的 表1 (請先閱讀背而之注意事項再填寫本瓦) -19 - 本紙張尺度適用中囷國家標隼（CNS ) Λ4規柏（210X 297公势） 409215 經濟部中央標準局貞工消开合作社印裝 A7. B7 五、發明説明（17 資料寫入超過一檔案的目前結尾之處。此種方式將產生具 有間隙或"空洞"（亦即一檔案内並未被寫入任何資料之區 域）的檔案。將此種檔案稱爲"稀疏擋案,，。對稀疏檔案的 讀取作業將送回一些零値，此時讀取的偏移量及長度交叉 到一空洞。支援稀疏檔案的檔案系統實施例只有效率地分 配磁碟儲存容量給寫入資料的檔案區域，而不分配給空 洞，或者至少不分配给大於區段容量或該檔案系統所用的 磁碟分配單位之空洞。 在本較佳實施例中，係利用一稀疏檔案實施基於可延伸 赫彳法的索引或目錄。每一赫許儲存區係以一偏移量 而儲存在檔案中，其中i是赫許儲存區编號（自零開 始），S是赫許儲存區大小（所有的赫許儲存區都有相同的 大小）。目綠開始時是一個空的檔案。當插入第一記錄 時，係知該C錄儲存在第零赫許儲存區，且循序將記錄寫 入標案中，而將權案大小自零增加到s 3當第零赫許儲存 區需要分裂時，寫入第！儲存區，而將檔案大小自s增加 到2*s。次一赫許儲存區分裂將取決於前兩個儲存區中哪 -儲存區需要作次-分裂，&寫人第2或3赫許儲存區。 如果第1儲存區作次一分裂，則將寫入第3赫許儲存區， 而將檔案大小自2*s增加到4*s，而在偏移量2*s處在檔案留 下一個空洞，其中第2赫許儲存區將自偏料&處開始2 入。表2示出如何將表丨所示實例中之赫許樹儲存在一 疏檔案中。 _一_-20- 本纸浪尺度適用中國國家標準（CNS ) A4規栝（2!〇χ297^犮） (請先閱讀背面之注意事項再填寫本頁)

409215 A7 B7 五、發明説明（18 ) 表2 第0儲存區第1儲存區第2儲存區第3儲存區空洞空洞第6儲存區 表2 :將表1所示的赫許樹對映到一稀疏檔案。 經濟部中央標苹局貝工消費合作社印製 (請先閱讀背16之注意事項#填ϊίτ本頁) 訂 如前文所述，自根（第〇儲存區）開始由上向下通過赫許 樹，即可找到一個具有一特定關鍵字之記錄a然而，因爲 我們預期所有的樹分支都有近似相同的深度，所以更有效 率的方式是由下向上通過該樹。執行的方式如下文所述。 若知道檔案大小，則我們可計算最長赫許樹分支的深度， 因爲在-個最大深度爲d的赫許樹中，所以所有的赫許儲 存區編號都是d個位元或更少的位元，且至少一個儲存區 必須有-個第d位元是-的儲存區編號。目此，可將最大 深度d計算爲最大赫許儲存區編號中之位元數，亦即仏 -1，其中f是㈣大小。爲了以-特定關鍵字查詢-記 :效我們：須先計算以該特定關鍵字的赫許値的」個最低 !上:赫許儲存區編號b。如果赫許樹的所有分 冰度’則即可保證可在以該關鍵字表示的赫 :#中找m己錄1爲儲存該特定關鍵字的分支之 木度可能小於d，户斤以儲存區b可 中。如果發生此種情形，則該標案將在:二:= 許値的-個較小位元計算則我們利用赫 固新的赫許儲存區編號b'，此 本紙張尺度適用中國國家標準（CNS ) A4規棺 -21 - 409215 A7 B7 五、發明説明（19 時如果該赫許樹分支的深詹良d 木度爲心1，則將可得到該記錄的 位置。只要在檔案中碰到-個空㈣，即重複上述的程 I (請先閱讀背面之注意事項再填寫本頁) 序。-旦找到-個非空洞之後，如果具有該特定關键字的 記錄存在’則必定在該赫許儲存區中找到該記綠。查詢及 插入作業的處理情形如下： 查詢作業： 1.計算所查詢的關鍵字之赫許値11。 2·以檔案大小除以赫許儲存區大小，在求基爲2的對數 値，然後捨入到次-整數，而計算出赫許樹深心。 3. 將赫許儲存區編號b計算爲個最低有效位元： b=h mod(2，d) 4. 自樓案的偏移量b*s上擷取赫許儲存區，其中s是赫許 儲存區大小。 -二1Γ 5. 如果赫許儲存區未存在（樓案在偏移量上有一空 洞），則將d遞減一，並回到步驟3。 6. 在赫許儲存區b中尋找具有指定關鍵字的記錄；如果 " 找到琢兒綠，則送回該記錄；否則送回"並未找 的錯誤訊息。. 插入作業： 1. 利用所要插入的記錄之關鍵字，以如查詢作 =到5所述之方式，計算赫許深度仏赫許儲存區編 就b。 2. :果具有該特定關鍵字的一記綠業已存在於赫許儲 存區b，則送回"業已存在"的錯誤訊息。 22- 本紙张人度適CNS ) Λ4規格（210>< 297公® A7 409215 五、發明説明（20 ) ~ ~ 3.如果赫許儲存^中有足夠的空間保留给新的記錄， 則儲相記綠並傳送回H必須分裂赫許儲存 --I -n i I l~ 1 - - - 1*I- i n I - I— (請先閲讀背面之注意事項再填寫本頁) 區b，以便讓出空間給新的記錄，其中情形將於下列 步驟中説明之。 4-計算b，=2-!d+b。 5 .對於赫許儲存區b中所有的記錄而言，重複下列步 化計算v=h mod(2 id+l))，其中h是該記錄的關鍵 芋之赫許値。請注意，v必須等於b或b ,，因爲 對赫許儲存區b中所有的記綠而言h m〇d 2 _^等 於b 〇 5b.如果v _ b ，則將該記錄移到赫許儲存區b，；否 則，將該記錄留在b中。 6.將d遞増一，並重新計算1>爲11 m〇d(2 ，其中卜是 所要插入的記錄之關鍵字。 回到步驟3。 鲮螭部中决樣羋局Μ工消贽合作乜印製 雖然本發明所述的可延伸赫許法實施例可配合任何赫許 儲存區大小而工作，但是如果儲存區大小與檔案系統的區 ^大小相同或爲區段大小的倍數，則該實施例將更有效率 地工作。這是因爲在空洞對準檔案系統的區段邊界時，一 甸有效率的稀疏檔案實施例並不需要任何磁媒I/O來讀取 —空洞。因此，如果現在並未在緩衝儲存區中儲存保有該 6己綠的赫許儲存區，則所有的查詢作業只多只需要—個磁 碟I / 0來讀取該赫許儲存區。請注意，此時假設在緩儲 ___ -23- 本紙张尺度適州中國囚家榡牟（cf>is ) Λ4说格（2ί0Χ297公釐〉 經濟部中*標卑局負工消费合作社印製 A7 ________________B7 五、發明説明（21 ) -— 存區中儲存了包含檔案的磁碟區段位置之檀案中介資料。對於均勻分佈的赫許僅而言，我們預期平均在每一查詢 =業中將碰到0.5個空洞。如果可延伸赫許法實施例^接 的中介資料（例如，如果利用可延伸赫許法 實施例實施檔案系統中之目錄），則直接查詢檔案中介資 科，即可識別2洞。否則，查詢作業必須對其計算的每一 赫許儲存區編號至少讀取某些資料，並以該讀取作業送回 的都是零而識別-空洞。儲存具有一個包含—非零値的短 起始碼之赫許儲存區，即可以最簡易之方式執行上述程 序。 現在本發明提供了赫許儲存區的分裂及合併。記綠係儲 存f每一赫許儲存區内，且當一赫許儲存區分裂時，即移 動這二。己綠。在刪除圮綠之後合併若干赫許儲存區，即可 收回磁碟空間。 母—赫許儲存區包含一個具有一"赫許樹層級，'欄位之起 始碼。該襴位的値只是赫許儲存區在赫許樹内的層級，亦 即該儲存區離開赫許樹的根有多遠。開始時赫許樹只有— 個儲存區，亦即在赫許樹層級零上的第零儲存區。當第零 儲存區分裂時，其赫許樹層級自零改變成一：新的儲存區 編號一是第零儲存區在分裂之後的兄弟儲存區，亦即該新 的儲存區之赫許樹層級將也是一。每當一赫許儲存區分裂 時，其層級即増加―，且將與進行分裂的儲存區相同的赫 彳樹層級指定給所增加的新儲存區。 每S知個新的έ己錄加入一赫許儲存區時，即在該時間 -----24- 本紙张尺度^2l0x297ii7 .In —ί I— (請先閲讀背面之注意事項再填跨本頁)

Hi I ..---夂

'1T A7 B7 五 22 --"部中央掠丰局η消贽合作社印來 409215 、發明説明（ 將孩圮綠連同赫許儲存區的赫 許儲存區分裂時，即遞増儲 =、·及—起儲存。當該赫 級，但連同每-記錄错存的料^碼中儲存的赫許樹層 新赫許儲存區的記錄也保持其層、.及足保持不變。移到 此，將和—特定印錄細紐，、原九的赫許樹層級値。因 φ 〇 聯的赫許樹層級値與該赫許儲存 上的赫許樹層級比較，即可決定在該儲存區 種能I 插入了該記錄。循序目綠掃描需要此 種旎力，將於下文中詳述其中情形。 描的另—項要求是：—旦插入記錄之後，一赫許 ==綠之偏移量即保持穩定。因此，當我們在 在或刪除-記綠時，現有的記錄被保留 ……的k置’亦即並沒有自由空間的壓縮。此外，當 因分裂而將—記錄移到—個新的赫許儲存區時，即將該纪 T儲存在該新的儲存區中與原始赫賴存區相同的相對偏 移量處。此時，連同赫許樹層級，即可重建—赫許儲存區 在分裂之前的内容。 f某一次數的删除作業之後，最好是收回不再需要的磁 碟空間。如果兩個同胞葉節點中之記錄少到可以放入單一 赫許儲存區’則合併這兩個節點，即可完成上述程序。然 而，循序掃描在合併及分裂中需要保存各記錄偏移量。此 即意指：爲了決定是否可合併兩個赫許儲存區，只在兩個 儲存區中加入自由空間是不夠的；反而需要驗證：當將兩 個赫許儲存區合併成單一赫許儲存區時，任何兩個記錄都 不曰重叠。達到此目的之最簡單方法是將這兩個赫許儲 —____ ___ - 25 - 本紙張尺度^i—捸 (請先閱讀背面之注^|0^項再填寫本頁)

五、發明説明（23 409215 at :并的時機延遲到這兩個赫許儲存區中之一赫許儲存區 元全空出時。 田口併兩個赫許儲存區時，儲存區編號較高的一儲存區 較低己綠被移到儲存區編號較低的另一儲存區，且將編號 儲低的儲存區的起始碼中之赫許樹層級遞減一。清除赫許 :存區値較高的赫許儲存區之内容，*自檔案中去除該赫 艮^存區。在類似Unix的檔案系統中，呼叫fc〖ear函式， ^可執行上逑程序；如果該檔案系統有效率地實施稀疏檔 ’則該程序將因收回該赫許儲存區先前所佔用的磁碟儲 存空間，而產生—空洞。 在本發明的較佳實施例中，爲了支援循序掃描一目錄或 索引中之所有記綠，提供了一種可重複呼叫的掃描作業， 用以送回赫許樹的内容，此種掃描作業被稱爲循序目錄掃 描。每一呼叫送回一個或多個記錄及一"游標"値，且必 須將該游標値傳送到次一呼叫，以便擷取次—组記綠。現 在將首先説明在掃描進行中並未插入或删除任何記錄時目 錄掃描的工作方式’然後將考慮如何處理因對掃描常式的 各呼叫間之插入或刪除而產生的赫許樹變化。 目錄掃描開始時係自赫許樹中最左邊的赫許儲存區（必 然是第零赫許儲存區）擷取記錄。一旦送回第零儲存區的 所有記錄之後’繼續對赫許樹中第零赫許儲存區的兄弟赫 許儲存區掃描。由於建構赫許樹的方式，赫許樹中深度爲 d的兩個兄弟赫許儲存區之赫許儲存區編號間之差異只在 第d個位元，亦即，在赫許儲存區編號的第d個位元上， -26- 本紙張尺度適用中國S家標準（CNS ) Λ4規格（2丨0 X 297公釐） ----.--„---------訂------广 (請先閲讀背面之注意事項再填窍本頁} 經濟部中央榡準局只'.T.消贽合作社印54 409215 37

結：¾—部中夹榡準局员τ_消费合作.社印V 記 於 進 五、發明説明（24 左邊的兄弟赫許儲存區有—個零，而右邊的兄弟赫許儲存 區有-個…因此，第零赫許儲存區的同胞赫許错存區是 bl=2n(d·”(在第d個位置上的單一位元）。在自第μ個赫 許儲存區㈣所有的記錄之後，在赫許樹中在第—赫許樹 通過階深度上繼續對次—赫許儲存區掃描。在第Η個儲 存區之後的次-赫㈣存區並不是—個兄弟赫許儲存區， 而是在赫許樹的一個cM深度上與第bl個赫許儲存區共有 -個共同的來源赫許儲存區。因&，該次—赫許错存區將 在位元位置d-Ι上有一個丨位元並在位置d上有—個零位 元，而得到一個赫許儲存區編號b2= 2 ”（d_2)。一般而 巨，若一第b赫許儲存區是在赫許樹的深度d，則可在第 一赫許樹通過階深度中長到次一葉節點，其尋找的方式 爲：取得b的d個最低有效位元，然後顚倒這些位元，再 將一個模2^d加到所得到的値，最後再度顚倒所得到的結 果。 因此，可利用一個包含一赫許儲存區編號15及一個在— 赫許儲存區内的相對偏移量Γ之游標c=(b，r)，而實施—赫 許樹掃描。以一游標値（b，r)呼叫的一掃描作業首先檢查第 b赫許儲存區中在大於或等於1的偏移量處是否還有;何 記綠。如果確係如此，則該掃描作業送回—個在^之後 次一記綠、及一個新的游標値（b，〇，其中r，是在送回哕 錄後的次一偏移量》如果第b赫許儲存區中在大於或^ r的偏移量處沒有任何記錄，則以—(b，，〇)的游標値繼續切 行掃描，其中13_是次一赫許儲存區編號，且係利用上述以 27- 本紙張尺度適用中國园家標苹（CNS ) Λ4規格（210X297公漦） /--J----------訂------4ΛI (請先閱讀背面之注意事項再填寫本頁) 409215 A7 B7 25 五、發明説明（ (請先閱讀背面之注意事項再填ί本頁) 位元顚倒/遞增程序，而以儲存在第^^儲存區的起始碼中之 赫許樹層級所提供之一 d値來計算該次—赫許儲存區編 號。如果對v的該計算得到一個0的値，則我們已達到赫 許樹的終端，且不再送回任何記錄。 *11 在對掃描常式的各呼叫之間處理因插入或刪⑨而發生的 赫許樹改變。因爲我們並未移動一區段内的各現有的記 錄，而插入一個新的記錄或刪除—個舊的記錄，所以只要 插入及删除不會造成赫許儲存區的分裂或合併，插入及刪 除就不會影響到循序掃描°因爲在此種情形中現有的記錄 並不會移動’所崎描最多只將發現每-記錄-次，並保 战送回m掃描進行巾被删除者以外的所有現有的記 錄。一個新插人或删除的記錄可不可以找到係取決於記綠 的位置（赫許儲存區及偏移量）、及插入/刪除相對於循序 掃描通過赫許樹的時機。如果分裂/合併在循序掃描到達 刀n /合併所影響的赫許儲存區之前發生，或者如果分裂/ 合併在掃描已前進離開受影響的儲存區之後發生 許儲存區的分裂或合併並不會影響到循序掃描。 只有在循序掃描已送回分裂或合併影響的赫許儲存區中 經7¾-部中决橾準局妇工消资合作社印 =但2部的記錄時’即進行對該赫許儲存區的分裂 = 才而要作特殊的考慮。當-區段分裂時，可將先 回到掃描常式的某些記錄移入新的赫許儲存 :綠”相碰到新的區段時，將再度送回相同的 二丄::=:赫許儲存區合併可能使掃描遺漏-些記 。二自—個該掃描所不曾碰到的區段移入現有 本紙狀度適财關幻料. 28 (210X297公釐） 409215 b77 26 五'發明説明（ {請先閎讀背面之注意事項再填湾本頁}

、1T 的赫許儲存區中-個小於現有掃描游標値所指示的偏移量 <偏移量位置。本發明以下述方式解決這些問題：偵測將 影響循序掃描的一赫許儲存區之分裂或合併；以及在必要 時重建分裂或合併之前的赫許儲存區狀態，以便在不回遺 漏或重複記綠的情形下繼績進行掃描。以下文所述之方式 =~赫許樹層級包含在掃描常式所送回的游標値内，即可 完成對一分裂或合併的偵測。當掃描常式自一第b赫許儲 存區送回第一記綠時，該掃描常式送回—游標値 c=(h，b，r)，孩游標値包含前文所述的赫許儲存區编號匕與 相對偏移量、《及於讀取該[記錄時在赫㈣存區的赫 冲法中發現的赫許樹層級値h。當將此游標値傳送到對掃 描常式的-後續呼叫時，將該游標値提供的赫許樹層級h 與在該赫許儲存區的起始碼中發現的現有赫許樹層級h ,比 較如果h外，則在對掃描常式的兩次呼叫之間必定發生 第b赫許儲存區的分裂；如果h，<h，或者如果第1?赫許儲存 區不再存在，則（檔案的偏移量b*s處包含一個空洞），則 该赫6午儲存區必定已被合併。 將赫許儲存區重建成游標產生時該赫許儲存區的狀態， 而處理赫許儲存區的分裂。利用一個暫時性的緩衝區來保 存重建後的赫許儲存區 以一次一個的方式讀取原始赫許 儲存區的各衍生赫許儲存區。並將原始第b赫許儲存區中 存在的任何記綠拷貝到該暫時性緩.衝區中。檢查前文所述 連同每一記錄儲存的赫許樹層級，而識別所要拷貝的記 錄，亦即，因而拷貝赫許樹層級小於或等於h且在第匕赫 409215 A7 B7 27 五、發明説明（ 許儲存區分裂之前即已存在的所有記錄 =分裂時保存了被移到-個新赫許儲存區的記錄== 請 f 先1 閱 I 讀 背L 面 | I之1 I ' 事I 項 I 再 填I 寫 ^ 頁 同一㈣^ 己錄拷貝回該暫時性緩衝區中的 之狀態(但不包括爾後被刪除： 詩利用該暫時性緩衝區中重建的區段， 當掃描常式當達該暫時性緩衝區的終點時， 讀“式利用上料位元遞増程序， 游標的赫許樹層級h所提供之—d値來計算所要碰到3 —赫許儲存區。 訂 3最後’係在—循序掃描中處理赫許儲存區的合併。如果 知描游標e=(h，b，r)提供的赫許樹層級u於在赫㈣存區b 的起始碼中發現的赫許樹層μ，，或者如果第㈣許儲存 區不再存在(亦即反而發現—個空洞），貝“貞測到一合併。 類似於分裂的情形，將赫許儲存區重建成產生游標時該赫 ㈣存區的狀態（亦即在合併之前的狀態），而執行赫許儲 Τ區合併的處理。然而’在此種情形中，並不需要在一獨 =的緩衝區中重建先前的赫許儲存區。而是掃描係對被合 併7赫許儲存區作業，對該儲存區進行多次掃描。在每一 ’人掃痴中’只运回其中—個原始儲存區的記錄；而不理會 其他的，錄。重新計算每一記綠的赫許値，並將該赫許値 的h個最低有效位凡與現有掃描游標提供的赫許儲存區编 號b比較，而執行上述步膝。如果以上所比較的兩者相 同，則在第b赫許儲存區被合併之前該記錄即已被放入該 -30-

本紙張尺度適财關緖4M 409215 A7 B7 五、發明説明（28 赫才儲存區中，因而掃描作業將送回該記錄。否則，將不 理會該記錄。請注音，1$L u ^ 〜、如果弟b赫許儲存區不再存在（亦 即反而發現—個空洞），則在赫許樹中往上—個或多個層 級，直到發現-個黑空洞區爲止（類似於查詢作業），而以 ==現包含赫許儲存區合併結果的儲存區。當掃描 對所合併赫許儲存區的一掃描之終點時，該掃描 二3二述的位元顚倒/遞增程序’而以自掃描游標的 赫^樹層級h所提供之—d値來計算次一赫許儲存區卜 如果新的儲存W是所合併赫許 =:=^，，。)對所合併= 掃描二:4:=,:==次 赫許儲存區進行作業，其中h"是在第^儲吊對第b 中發現的赫許樹層級。 5子區的起始碼 程式設計師可以可實施掃描作業演 言幹：施本發明所述的方法，該掃插作式語 輸入：游標値c=(h,b，r) 耷如下： 輸出 用於送回一個或多個記錄之緩衝區 在所提供緩衝區中送回的記綠 新的游標値 請〉主意 在對掃描常式的第一次呼叫 (0,0,0)的游標値；在後續的呼·〜'傳送—的 , 死則呼叫咕… 標値應被傳送到次一掃描呼叫。 迗回的游 1 設定 h^h, b'=b -31 -

2 五、發明説明（29 ) 自樓案的偏移量4 # 赫許儲存區大小。赫許儲存區，其中S是 案在偏移量b'處包上:)許儲/區並不存在(制 ^^ ^ ° 二洞），則將h ’遞減一，重朝 计异 b '爲！V=m〇(J 2 -th,，# n 2：i t ，並回到步驟2的開始處。 占又疋h’爲在第b’赫許儲在泛沾』 .,π ^ φ f锗存區的起始碼中發現的赫許掏 層'.及’如果h、b、及θ ^ λ 及1都疋零（掃描的開始），則設定ίι 馬與h 1相同的値。 比較。根據該比較的結果，而繼續進行下文所 不的步驟5、6、或7。 如果h'= h : 清注意’在此種情形中b必須等於b ,。 5.1在第b赫許儲存區中，於大於或等的—偏移 量處搜尋次-記錄。根據是否仍有此種記錄，而 繼續進行下文所示的步驟5.2或5 3。 5.2如果此種記錄存在： 檢查在所提供的緩衝區中是否仍有空間而得以送 回記錄。如果仍有空間，則將該記錄拷貝到所提 供的緩衝區，並在拷貝了該記錄之後將掃描游標 中之偏移量r更新爲次一偏移量’然後回到步驟 4 〇 ' 如果在所提供的緩衝區中已無空間，則自掃描常 式跳出，並送回現有的游標値。 5.3 如果此種記錄不存在： 計算b "等於在第一階深度之次一赫許儲存區。 -32- 本紙张尺度適用中國國家標毕（CNS ) Λ4規格（210X297公釐） (請先閱讀背面之注意事項再填寫本頁} 丨^衣.

*1T 赶系部中吹^次局·，只工ί'/ίφ;合作.打印*'14 409215 A7 B7___ 五、發明説明（30 ) "~^ b"=reverse(reverse(b, h) + 1, h) 其中reverse(x，n)意指取x的η個最低有效位元，然 後將其顚倒之。 如果b "等於零，則我們已到達掃描的終點。在此 種情形中’將自掃描常式跳出，並送回現有的游 標値。 否則，以如下所示方式更新游標c=(h，b，r):設定b 及b 1等於b "。將Γ設定爲零。讀取b的新値所指示 的赫許儲存區，並將h及h，設定爲在該赫許儲存 區的起始碼中所發現的赫許樹層級。 然後回到步驟4。 6 .如果 h' > h : 此種情形意指第b赫許儲存區被分裂了。 61如果尚未執行，則將第b赫許儲存區的内容重建 爲其在分裂前的狀態。其方式爲將赫許樹中第b 赫許儲存區的所有衍生赫許儲存區合併到一暫時 性緩衝區。可能在前一反覆中已爲第b儲存區執 行過此步驟；在此種情形中，可跳過此步驟。 6.2在該暫時性緩衝區中大於或等於r的偏移量處找 到次-記綠。根據是否仍有此一記綠，而繼續進 行上文所示的步驟5.2或5.3。 7 .如果 h1 < h : 此種情形意指第b赫許儲存區被合併了。 7」在第b，赫許儲存區中大於或等於㈣偏移量處找到 __________ -33- 本紙狀度_帽辭鮮（CNsTA4^fe G1{)x 297jJ^ p'·〜 -----：——..---^ ! Γ靖先閑靖背面之ii意事項再填寫本頁) 訂 經1¾-部中夾標沭而負1消贽合作社印製 409215 a7 ____ B7 ______ 五、發明说明（31 ) 次一記錄。根據是否仍有此—記錄，而繼續進行 下文所示的步驟7.2或7.3。 7.2 如果此一記錄存在： 計算該記錄中關鍵字的赫許値，並設定V·爲該赫 許値的h個最低有效位元。如果b，，不等於b，則跳 過該記錄，亦即，更新掃描游標中之偏移量r爲 該記錄之後的次一偏移量，並回到步驟7 . 1。 檢查所提供的缓衝區中是否仍有空間以送回該記 錄；如果並非如此，則送回現有的游標値。 如果有足夠的空間，則將該記錄拷貝到所提供的 緩衝區’並將掃描游標中之偏移量r更新爲剛才 被拷貝的記錄之後的次一偏移量。 回到步驟4。 7.3 如果此一記錄不存在： 計算b "等於在第—階深度之次—赫許儲存區。 b"=reverse(reverse(b, h) + 1, h) 如果b ”等於零，則我們已到達掃描的終點。在此 種情形中’將自掃描常式跳出，並送回現有的游 標値》 否則，檢查（b mod 2 ih，）是否等於（b_ mod 2 -nh)。 如果確係如此，則意指所要掃描的次一儲存區仍 然是其中一個被合併到第b |儲存區之儲存區。在 此種情形中，將r設定爲零，並回到步驟7之開始 處’此時將對所合併的第b ’儲存區開始進行次— ____ -34- 本紙張歧劍巾關轉彳.1 CNS ) Λ4規格~( 210X 2974^ ----1--·---^-- (請先閱讀背面之注意事項再填寫本頁) 丁 -•ο 經M部中次標卑局只T,消许合作社印製 409215 at 五、發明説明（32 ) 掃描。 否則’已完成了對所合併儲存區的最後一次掃 描。在此種情形中，繼續進行步驟53,亦即，將 b及b_設定爲b" ’將1設定爲零，並將h&h，設定 爲在第b赫許儲存區的起始碼中發現的赫許樹層 級，然後回到步驟4。 在説明了本發明的循序掃描程序的實施例之後，現在將 回到用來將游標值編碼的方法。 爲了儘量減少存放一游標値所需的位元値，可將赫許樹 層級及赫許儲存區编號結合成單—値，此時只需要比存放 最大可能儲存區编號所需數g的位元多一個位元。這是有 可能的，因爲儲存區的數目必然小於或等於2^L，其中l 是層級。編碼方式如下。此種編碼所用的一個參數是最大 赫許樹層級，亦即赫許樹的任何分支所能到達的最大深 度。 對赫許樹層級L及赫許儲存區編號B的游標編碼如下： 使Μ =最大赫許樹層級

計算Η = Μ - L 计算R =將Β的每個位元顚倒 將儲存區編號及層級編碼爲2，h+R*2，（Η+1) 在解碼時，計算較低階的零位元數，並以Μ減掉該數而 得到層級（L )。爲了得到儲存區編號，將编碼後的値向右 移動L+ 1個位元，並將所得結果的每一位元顚倒。 當然’熟悉本門技術者在閲讀本發明的説明之後，當可 __*___— __ - 35 - 本紙张尺度適用帽( CNS ) A4ii^TTi〇X 297/>f } ----1--.---k— (請先閱讀背面之注項再填寫本頁) 訂 五 、發明説明（33 409215 at B7 暗批:p。些選項的特徵°例如，本系統可實施鎖定及同 二作業，而得以在不同的赫許儲存區中進行同時的更 眚本發明亦實施上溢的區段。雖然在一循序掃描過程中 、際上並不需要—個暫時性緩衝區來處理分裂，但是可使 :呼」耘式所提供的緩衝區。尤其是我們知道應用程式係 欠/、送回—個結果的循序掃描介面，所以只爲了送 回一個記錄而重建一整個儲存區是不合理的。 基…^案系統中分配儲存交蚤 …T刀配是本發明較佳實施例的一個特徵。此即意指： 本發明提供了對—分配對映表（例如一位元對映表）之編 黾本發月對分配對映表的編碼與傳統编碼的分配對映表 比較時，減少了同時分配多個磁碟上的磁碟區段（包含一 共用磁碟檔案結構）的多個節點間之干擾，本發明之^統 亦可讓多個節則時收回干擾減少的磁碟區段。 雖然在杈案系統中實施了分配的觀念，且雖然檔案系統 使用傳統的方法分配儲存容量，但是用於共用磁碟檔案系 統的傳統方法產纟了 —些問豸，因&需要一種可分配及收 回儲存谷量的發明，且此種發明在一共用磁碟檔案系統及 —平行檔案系統中都執行良好。 一般而I，檔案系統是—種可讓其他的應用程式儲存及 擷取磁碟機等媒體上的資料之電腦程式。爲了簡潔起見， 下文的説明中將使用磁碟的術語，但是此種觀念適用於任 何以區&组成的類似儲存媒體。檔案是一個有名稱的任意 大小之資料物件。檔案系統可讓應用程式產生檔案並爲檔 -36 - 纸張尺度適圯中國园家標孪（CNS ) Λ4規格（2〗〇><297公瘦） (請先閱讀背面之注意事項再填寫本Ϊ ) •1 訂 ϋ9|15 五、發明説明（ A7 B7 34 經滴部中央標挲局只工消费合作社印焚 案命名，以便將資料儲存在 除權案，以及對檔案執行其他的作業自‘案4取資料，冊 案㈣結構是磁碟機上的資料之组織。除了權 (夕’檔案結構包含中介資料，亦即—種將声 案名稱對映到對應的檔案之盘: 中尤其重要的有：磁碟上檔案資 料的位置（亦即哪些磁碟區段存放有樓案資料）、—個記錄 哪些磁碟區段目前被用來儲存巾介資料及棺案資料之分配 對映表、以及一個包含與檔案結構有關的整體資訊(例如 目錄、分配對映表、及其他中介資料結構的位 區段。 «另—万面，我們當了解，共用磁碟檔案系統是在各別電 腦上執行的多個檔案系統存取在—個或多個磁碟上常駐的 一檔案結構之一種檔案系統。爲了便於説明本發明之較佳 貫施例，我們爲該檔案結構假設：這些電腦（或節點）沒有 共用圮憶體（縱然這些電腦可以有而且在許多可能的實施 例中將有區域記憶體、及至少某些共用記憶體（如許多 SMP的實施例）’我們也作此種假設），且這些電腦係連接 到若干磁碟，而檔案結構係利用諸如一匯流排或一交換網 路的某一裝置而常駐於這些磁碟上，其中該匯流排或交換 網路都被視爲有這些用途的通訊網路。此外，我們假設： 某一類似的裝置使這些節點相互通訊。共用磁碟檔案系統 可讓一個使用該檔案結構的一計算工作被分成多個部分， 且可在多個節點上平行執行該等多個部分。此種方式可集 37- 本紙滚尺度適用中國囤家標準（CNS ) Λ4現格（2!〇X297公潑） (請先閲讀背面之注意事項再填寫本頁) ίν TJ -=° 409215 A7 B7 五、發明説明（35 ) 合這多個節點的計算能力而完成該計算工作。 (請先閱讀背面之注意事項再填寫本頁) 一分配對映表是本發明的檔案結構之一部分。考慮一個 儲存在N個磁碟DO、D1、...、DN-1上的檔案結構。一對數 子（i，j)識別該檔案結構中的每一磁碟區段，例如，（5 254) 識別磁碟D5上的弟254個區段。分配對映表通常係儲存在 陣列A中，其中元素A(1，j)値表示磁碟區段（i，j)的分配狀 態（被分配/自由）。 分配對映表通常係儲存在磁碟上，作爲檔案結構的一部 分，因而分配對映表係常駐在一個或多個磁碟區段中。傳 統上’ A(i，j)是對映表中的第k個連續元素，其中k=iM+j， 且Μ是某一大於任何磁碟上的最大區段數目之常數。 爲了尋找磁碟空間的一自由區段，檔案系統將Α的一區 段讀進一記憶體緩衝區中，並搜尋該緩衝區，以便尋找— 個其値指示對應的區段（i，j)爲自由的元素A(i，j)。在使用區 段（i，j)之前’檔案系統更新該缓衝區中A(i，j)的値，以便指 示區段（i，j)的狀態爲被分配，並將該缓衝區的内容寫回磁 碟。爲了使一個不再被需要的區段（iJ)成爲自由狀態，檔 案系統將包含A(iJ)的區段讀取到一缓衝區，然後更新 經淖部中央標準而豆工消贽合作社印4.'1木 的値以便指示該區段（i，j)是自由的，並將該區段的内 容自該缓衝區寫回到磁碟。 對以共用方式存取一分配對映表的處理已成爲一特定的 需求。如果包含一共用磁碟檔案系統的各節點並未使其對 共用磁碟的存取有正確的同步，則這些節點可能破壞該檔 案結構。此種情形尤其適用於分配對映表。爲了説明此種 -38 - 本紙張尺度適用中國國家標卒（CNS ) A4規格（210X297公疫） 409215 A7 B7 五、發明説明（ 36 .¾¾‘部中央標5?-局兵工消费合作.社印製 情形，現在將考慮前文所述的分配一自由區段之程序。假 設兩個節點同時嘗試分配一區段。在執行此工作的過程 中，這兩個節點可能同時讀取同一分配對映表區段，同時 找到描述自由區段（i，j)的同一元素A(i，j)，同時更新A(i,j) 以便示出區段（i，j)是被分配的，同時將該區段的内容寫回 磁碟，以及同時爲了不同的用途而繼續使用區段（i，j)，因 而破壞了檔案結構的完整性。如果A(X)及A(Y)係同時包含 在相同的對映表區段中，則縱使各節點同時分配不同的區 段X及Y ’也將發生更微妙也更嚴重的問題。在此種情形 中’第一節點將A(X)設定爲已分配，第二節點將Α(γ)設定 爲已分配’且這兩個節點同時將放在緩衝區的對映表區段 内容寫回磁碟。根據哪一個寫回先被執行，區段X或γ將 在磁碟上的對映表中呈現自由狀態。例如，如果執行第二 節點的窝回是在執行第一節點的寫回之後，則區段X將在 磁碟上的對映表中呈現自由狀態。第一節點將繼續使用區 段χ(例如儲存一檔案的一資料區段），但是在某一稍後的 時間，另一節點可能將區段x分配給其他的用途，此時的 結果又破壞了襠案結構的完整性。 爲了避免檔案結構的破壞，一節點在將每一位元對映表 區段讀取到記憶體之前，必須爲該位元對映表區段取得— 符記，而且如果該節點修改該區段（亦即分配或釋出—區 段）則涊即點必須在釋出該符記之前先將該區段的内容 =磁碟。通常自諸如美國專利5,454，刚所述的鎖定管理 器等的分散式符記管理器,,取得符記，並將符記釋出 (請先閱讀背面之注意事項再填寫本頁) -'ll

St.. 39 - 409215 A7 _________B7_ 五、發明説明（37 ) 到該分散式符記管理器。在釋出區段上存放的符記之前， 自符記管理器取得符記的虛耗作業，以及將對映表區段寫 回磁碟的虛耗作業，都可能大幅降低一共用磁碟檔案系統 的效能。 本發明可如同在一 RAID環境而將拆開在多個磁碟上的 資料。拆開（striping)是一種在不同的磁碟上儲存連續資料 區段（例如—檔案）之技術D拆開之優點包括高效能、及負 載平衡。在拆開中，檔案系統係根據磁碟編號〇、…、N-1 的某一循環組合’而將一檔案的連續區段寫入不同的磁 碟。對於以傳統方式组織的分配對映表而言，寫入一檔案 的N個區段或更多的區段時，需要鎖定、搜尋、更新、及 寫入N個對映表區段（或者在小於n個區段時，需要整個分 配對晚表）。執行上述步騍的虚耗作業遠高於在單一磁碟 上分配N個相接的區段。此外，在一共用磁碟檔案系統 中，寫入檔案的節點可能使其他節點耗用相當長的延遲時 間以等候對所需分配對映表區段的釋出。 爲了解決此一背後的問題，本發明使用—分段分配對映 表而提供了一種磁碟分配器，用以儲存及管理一個支援分 佈在多個磁碟上的分配對映表’並同時可儘量減少與區段 的分配相關聯的鎖定、I/C)、及搜尋虛耗作業。與前文所 述的傳統分配對映表比較時’本發明的磁碟分配器大幅減 少了於分配一拆開檔案時所存取的分配對映表區段數。此 外’在一共用磁碟檔案系統中’該檔案系統大幅減少了於 多個節點同時分配拆開檔案時鎖定之競用、及分配對映表 -40- 本纸依尺度適用中國S家標準（CNS ) Λ4規格（210X 297公楚 (請先閲讀背面之注意事項再填寫本頁) i %

，1T 409215 經消部中央標準局另Κ消赀合作.社印裝 五、發明説明（38 ) 區段之讀取與寫入。 本發明所述磁碟分配器所根據的基本觀念是再將分配對 映表細分爲若干區域。若將對映表分成&個區域，則每一 區域控制N個磁碟中每一磁碟上的1/κ個區段，檔案並非 鎖定分配對映表區段，而是鎖定這些區域，以便同步對映 表之存取。由於使用了不同的區域，所以多個節點可同時 分配拆開檔案’而不會相互干擾。 對於具有Μ個區段的磁碟而言，每—區域包含分配對映 表的ΜΝ/Κ個元素。這ΜΝ/Κ個元素理想上是正好放入—單 一分配對映表區段，但是如果磁碟數（或每一磁碟的容量） 相當大，或者如果區域數相當小，則這些區域可能大於分 配對映表區段。爲了讓分配對映表使用與正规檔案相同的 區段大小，各區域係由一個或多個段落所構成，其中每一 段落的大小最多爲一分配區段，並且控制1^個磁碟的一部 分磁碟上區段的分配。如果區域小於對映表區段大小的一 半’則將多個區域放入每一對映表區段。 決定分段分配對映表组織的參數有區域數κ、磁碟數 Ν、及以每一磁碟的區段數μ表示的磁碟容量。應選擇巴 域數至少等於檔案系統節點數，因而每一節點可自—不同 的區域分配。 如果Β個分配對映表元素正好放入一區段，則係以下式 表示最小區段數、及儲存每一區域所需的最小段落數· ceii((MN/K)/B)， 這是因爲每一區域儲存每一磁碟的第1/κ個元素，亦即每 -41 - 本紙張尺度適/fl中國國家標辛（CN’S ) Λ4規格（210X297公t ) ---------袈— (請先閱讀背面之注意事項存填湾本頁) *1Τ 經斌部中次標iv-局s;工消资合作.社印來 409215 A7 ________ B7 五、發明説明（39 ) ~~ 一區域有NM/K個元素。然而’爲了在—特定磁碟上分配 一區段’最好是使對照到同一磁碟的所有分配對映表元素 都放在同一段落内，亦即放在分配對映表的同一區段内。 在此種限制下，每一段落可存放d個不同磁碟的分配元 素，其中係由下式表示6: d=floor(B/(/K) = fl〇or (BK/M)。 请注意，必須選擇κ至少等於，否則，d將爲零，亦 即，對照到同一磁碟的分配對映表元素將無法正好放入單 一區段内。因此，係以下式表示每—區域的段落數· L=ceil(M/d) = ceil (N/floor(BK/M))。 我們將使用記法S(p，q)表示第p個分配對映表區域的第只 個段落’其中p的範園爲自〇到K_1，q的範圍爲自C到L_ 1 °然後以下文所述之方式將分配對映表的各元素指定給 段落°表示第i個磁碟上的第j個區段的分配狀態之元素 A(i，j)係儲存在段落A(p，q)，其中 p j mod K，以及 q = floor(i/d)。 係按照下列順序將各段落配置在各連續的分配對映表區 段中： s(0,0)、S(1，0)、s(2,0)、S(K十0)， S(0，1)、S(1，1)、s(2，l)、··、s(K-l，l)， S(0，L-1)、S(1，L-1) 、S(2，L-1)、...、s(K-l，L-l)。 換言之，每一區域的第一段落係儲存在分配對映表的開 -42- 本紙疚尺度適用中®园家標準（CNS ) Λ4規格（210 X297公超） 象------II-------〆. (請先閱讀背面之注意事項再填寫本頁} 409215 A7 --_ B7 五、發明説明（40 ) ~ ~ ~ ~ 負後1爲每區域的第二段落，其他依此類推。此種配 置方式使擴展檔案系統成爲可能’其方式爲在不需要重新 组織分配對映表的情形下加入更多的磁碟，亦即，將更多 的磁碟加人樓案系統時，需要將更多的分配對映表元素儲 存在每一區域，此時可能需要將一個或多個段落加入每— 區域(―以利用一個新的N値重新計算L之方心决定需要多少 的段落）。只須將頦外的元素添加到現有分配對映表的結 尾即可。 钱滴部中央楛準局矣二消费合作社印" 爲了分配一拆開檔案的各連續區段，—節點利用區域中 的各自由區段（亦即其分配映表元素指示其狀態爲自由的 區段），並根據拆開組合而取得一區域的符記，並分配各 連續區段。在釋出該符記之前，該節點需要將該區域的内 容寫回磁碟。如果在嘗試於一特定磁碟上分配一區段時發 現玆區域在該磁碟上並未包含任何自由區段，則該節點切 换區域，此時該節點將該區域的内容窝回磁碟並釋出符 記，然後爲另一區域取得一符記，並嘗試自該區域分配。 如果該節點嘗試了所有的區域但無法成功找到一特定磁碟 上的自由區^又，則该節點可（根據檔案系統的拆開策略） 而在另一磁碟上分配一區段，或者將—，，空間不夠，，的狀 況傳送回應用程式。在前一種情形中，當已嘗試過所有的 磁碟但不成功時，檔案系統將送回"空間不夠”的訊卓。 在效能強化的實施例中，檔案系統通常允許其他節點在各 檔案區段寫入之間爲其區域而"借用"符記。却 从即點回應 一符記借用要求，而將該區域的内容寫入磁碟，级 -43- 本紙張尺度適用令囤囚家標4M CNS ) Λ4规格（2I0X297公釐） A7 B7 409215 五'發明説明（Μ =記。區段取回係與第21節所述者相同；爲了取回一區 段，檔案系統在包含描述區段的分配對映表之區域讀取資 訊，將其狀態更新爲自由狀態，並在釋出符記之前將該區 域的内容寫回磁碟。 雖然前文所述的分配對映表組織及演算法大幅減少同時 寫入檔案的各節點間之干擾’但還是可能有一些干擾。這 是由於在切換區域時，一節點並無選擇要切換的區域所依 據 < 資訊。該節點理想上應切換到一個其他節點目前並未 使用的區域，且該區域有足夠的自由區段而容許持續的寫 入’無須再度切換到另—區域。 爲了提供一種使一節點得以作出―個有足夠資訊的區域 選擇’本發明導入了—種分配管理程式，這是一種追蹤哪 —節點（如果有此種情形）正在使用每一分配區域並追蹤每 區域中大約還剩下多少自由空間之程式。於擋案系統啓 動時，居为配卞理程式檢查每一區域，而計算出每—區域 中之自由區段數，並將此資訊存放在一表中。在切換區域 之前’一檔案系統節點將一訊息傳送到該分配管理程式， 知該卽點切換前的區域（包括該區域現有的自由空間容量） 通知該分配管理程式，並取得一個建議的切換區域。該分 配管理程式更新其表，以便指示切換前的區域之自由空 間’並釋出已無節點使用該區域。該分配管理程式然後檢 查其表，以便決定目前並未被使用且自由空間容量最大的 另一區域’然後將該區域的編號回覆該檔案系統節點，並 更新其表，以便指示該區域目前被使用。如果所有其他的 44 - 本纸乐尺度適用中國S家標準（CNS ) Λ4規格（210Χ297公釐） (請先閲讀背面之注意事項再填寫本頁) i %

、1T ¾¾部中央榡卑局W工消先合作杜印^ A7 —_ 409215 五、發明説明（42 ) 區域都處於使用狀態，則該分配管理程式隨機選擇—個區 域。該協定優先切換到未使用的區域，而減少區域切換的 次數。 雖然上述演算法將分配對映表存取局限於檔案產生，但 是檔案删除仍然有可能造成頻繁的區域切換，因而干擾到 正在同時寫入檔案的各節點。縱使個別檔案中之區段局限 於單一區域’仍然經常有—節點將刪除若干由不同的節點 在不同的時間所產生的檔案（例如—目錄的内容）且因而自 不同的區域分配之情形。此種情形將產生收回分配，且因 而頻繁地執行區域切換。 爲了減少這些區域切換，分配管理程式及檔案系統提供 了種指不收回對目前正在使用該區域的節點（如果有此 種情形）的區段分配之裝置，用以控制收回對區段之分 配。其實施方式如下：刪除—區段時，檔案系統首先將一 訊息傳送到分配管理程式，以便取得目前使用該區域的節 點之身份。分配管理程式以該節點之身份或該區域目前並 未被使用的指示作爲回應。在後一種情形中，節點以前文 中在3.2郎所述之方式收回對區段之分配。在前—種情形 中，該節點將一訊息傳送到分配管理程式所指定的節點， 告知收回對區段的分配。如果第二節點確實正在使用該區 域’則該第二節點收回龍段的分配，並回應第一節點而 指示該第二節點已如此執行。如果第二節點目前並未使用 該區域，則將此種情形回應第一節點，此時第―節點收回 對區段的分配。 -45·

(CNS ) 2]〇x 297^-f T

-- I- I - I - I - — /衣 t--- !: I -1 . I (請先閲讀背面之注意事項再填寫本頁；I 經濟部中-^標準局h.T.消先含作社印¾ A7 B7 409215 五、發明説明（43 ) 爲了減少訊息的傳送’可成批處理收回分配的訊息。例 如，在刪除-標案時，分配區域可將屬於該擋案的ς區段 分類，然後可將包含屬於同一區域的各區段之單一收回分 配訊息傳送到目前正在使用該區域的節點。 共用磁碟樓案系統干擾之虚珣 本發明之，系統可讓包含-共用磁碟檔案系統的多個節點 避免相互間不必要的干擾。爲達到此一目的，本發明已作 了各種改良。 _可擴展的平行檔案系統之動態預取 預取是一種檔案系統中用來減少1/0延遲時間的一種技 術’其方式爲在應用程式要求資料之前，即讀取若干區段 的循序存取檔案。本發明之系統處理動態排程及調整預取 專用的樓案系統資源之問體’以便盡量增加一平行樓案系 統（亦即同一檔案的資料係分佈在多個磁碟裝置之樓案系 統）的資料傳輸率，並儘量減少I/O延遲時間。 本系統内設有一個稱爲”緩衝管理程式"之系統服務程 式，該緩衝管理程式在競用記憶體的各種不同系統组件之 間仲裁έ己憶體資源之使用權。每一組件必須將缓衝管理程 式決定將多少記憶體分配給每一组件所需的資訊提供給緩 衝管理程式。該資訊包含下列兩個數字： 1 ·所需的記憶體容量。 該數芋指示在可供應的情形下一組件可有效地利用多 少的記憶體。 2 .現行洽動水準。 46 - k纸ft尺度璉州中國國家標卒（cNS ) Α4规格（210Χ297公1 ) -------.----氣------訂--------- * / (諳先閲讀背面之注意事項再填寫本頁) 經"·部中决榡準局：^工消贽合作社印製 409215 ^ —-----—_______ B7 五、發明説明（44 ) 该數字^ 4提供—組件對記憶體使用頻度的—量測 値’通*係<^—段時間中對記憶體存取的次數表示。 该緩衝管理心式隨即將其指定給每一组件使用的記憶體 容量通知該组件。 競用資源的其中—個组件是檔案系統的缓衝區組，該緩 衝區组係用來緩衝儲存最近所擷取的檔案資料 '及爲循序 讀取而預取的資料。本發明將適當的資訊提供給缓衝管理 私式，以便考慮到預取所需的資源，並安排緩衝管理程式 所指疋資源I使用時間，以便儘量提高檔案系統的資料傳 輸率’並儘量減少I/O延遲時間a 下文中將概述如何達到上述目的。表3及4中示出額外 的細即，且在下文的概述之後將另行説明這些細節。 ~檔案系統的緩衝區组在邏輯上被分成兩個部分，其中 一個部分係用於預取（”預取緩衝區组"，另—部分係用 於緩衝儲存最近擷取的樓案區段（II —般性緩衝區組"）。 "在邏輯上被分成"意指並不需要將個別的緩衝區特別 •is疋給某一緩衝區组或另一緩衝區组；而是維護單一 數字’該數字指示總緩衝區空間中有多少空間係用於 預取’而以此種方式表示這兩種緩衝區组的區分。 好滴部中央枒準局貞-τ消资合作社印判木 -將這兩個緩衝區組提供給缓衝管理程式，作爲兩個獨 土的组件，亦即，檔案系統分別爲一般性緩衝區組及 預取緩衝區组計算各自所需的記憶體容量及活動水 準。 -利用可量測資料存取率的諸如基準計數等傳統的技 _______ -47- $纸浓尺度適用中囡ΐ家標準（CNS ) A4現格（2IOX297公釐） 409215 a7 ----- _ B7 五、發明説明（45 ) ' 術，而計算兩個緩衝區組的活動水準。因爲這兩個緩 衝區組只是在邏輯上隔離，所以保存每一緩衝區組的 各別計數，即可執行上述步騍；在每一次的緩衝區存 取中，根據係由循序或随機1/〇存取緩衝區，而更新適 當的計數。 -利用基準位元及計數器決定在某一段時間中存取不同 檔案資料的總數，量測工作组’而計算一般性緩衝區 组的所需大小。 -然而’係以不同的方式計算預取緩衝區組的所需大 小。該计算考慮到：屬於檔案系統的磁碟裝置數目及 此力、循序存取的檔案數 '及讀取資料的速率。將在 下文中詳述此種計算，且此種計算係示於表3。 -將前—步驟中計算出的數字提供給缓衝管理程式，緩 衝管理程式利用這些數字決定將多少記憶體指定給代 表權案系統的一般性緩衝區组及預取緩衝區組的兩個 組件。植案系統將其緩衝區組的總容量設定爲指定给 這兩個組件的記憶體容量之總和。指定給代表預取緩 衝區组的组件之記憶體容量係用來決定可預取多少資 料。圖2中將詳述預取的時機及預取的資料形式。 開始時最好是以一簡單實例説明表3及4中所示的演算 法，該簡單實例爲自一個儲存在一非平行（單一磁碟）檔案 系統讀取之單一應用程式；然後將考慮如何處理多個應用 程式及具有多個磁碟之檔案系统。 在此簡單實例中，雙重緩衝（兩個預取緩衝區）足以提供 -48- W張尺度適用中國园家標隼（CNS ) Λ4規格（21〇ί_297公釐） (請先閲讀背面之注意事項再填寫本頁) 、1Τ A7 409215 五、發明説明（46 ) 最佳的資料傳輸率及效能。當應用程式開始讀取檔案時， 檔案系統將檔案的第一區段讀取到其中一個預取緩衝區。 當第一I/O結束時，檔案系統將檔案的第二區段讀取到另 一預取緩衝區。在進行第二1/0時，自第一緩衝區擷取檔 案資料，而滿足應用程式的讀取要求。如果到達第一緩衝 區的末端，則當第二I/O結束時，可自第二緩衝區滿足後 續的讀取要求。一旦第二:[/0結束且應用程式已自第一區 段頊取了最後一個位元組之後，即重新使用第一預取緩衝 區預取樓案的第三區段，其他依此類推。 如果應用程式的讀取速率慢於磁碟，則在應用程式完成 讀取前一區段的資料之前，即已結束了各預取I/C)。在此 種情形中，當應用程式已讀取前—緩衝區的最後一個位元 組時，將開始次一預取I/C^在此種情形中，資料的供應 速率將等於應用程式讀取資料的速率，且應用程式將不再 需要等候磁碟I/O。這是最佳的狀況。如果應用程式讀取 责料的速率快於可自磁碟擷取資料的速率，則每當應用程 式到達一個區段的結尾時，即需要等候目前作用的I/C)結 束，且於前一預取I/O結東時，即開始一個新的預取1/()。 在此種情形中，讀取資料的速率將等於自磁碟擷取資料的 速率，再度是一最佳狀況。 表3所示之演算法將多個應用程式及每一檔案系統有多 個磁碟的特性一般化；該演算法計算所需的預取緩衝區 數，因而：（1)如果應用程式嘗試讀取資料的合併資料速 率小於可用總磁碟頻寬，則將以讀取資料的速率將資料供 -49- 本紙张尺度適用中囷囤家標準（C、NS ) Λ4規格（21〇'χ297公楚） ^訂------广 1 (请先閱讀背而之注意事項再填寫本頁) 經滅部中央標卑灼只^消贽合作社印^ 五、發明説明（47 409215 a? _ B7 ¾¾部中央樣卑局；^ T;消於合作71印^ 應給每-應用程式’且不會有1/〇等候β (2)如果應用程式 的合併資料速率太於可用總磁碟頻寬，則將以可自磁碟擷 取資料的速率讀取資料。 〃 '以上兩種情形都需要決定每一應用程式嘗試讀取資料的 速率。量測應用程式的Η思考時間，_(亦即應用程式耗用在 處理檔案系統所供應的資料之時間），即可完成上述程 序。思考時間包括讀取系統要求揭取權案系統緩衝區” 的資料並將該資料拷貝到應用程式的緩衝區之作業時間， 但並不包括檔案系統耗用在等候自磁碟讀取資料的時間。 我們將應用程式在一時間間隔中的"資料耗用率”定義爲 應用程式在該時間間隔中讀取的資料量除以該時間間隔中 之總思考時間。 我們首先考慮總消耗率小於總磁碟頻寬的情形。在此種 情形中’適當的預取作業應可供應所需的資料，而無須任 何應用程式等候1/〇作業。如果總消耗率大於單—磁碟的 頻寬，則將需要以平行方式對多個磁碟執行預取17◦作 業，以便維持所需的資料速率。將總消耗率除以單一磁碟 的頻寬，再將所得結果捨入到次一整數，即可計算出所需 的最小平行I/O數。將該數字稱爲"平行處理因數，， ("parallellsm factor"。爲了供應所需的資料，而無須任何 應用程式等候Z/0作業，必須可使用足狗的額外緩衝區， 使每一應用程式可在進行預取1/0作業時，自另一緩衝區 讀取先前提取的資料。因此，將爲循序1/〇而開啓的檔案 實例數加上平行處理因數，即可得到最佳的預取緩^ = -50- '、紙張尺度適用中國囡家榡孪（CNS ) Λ4規格（210X297公茇） (請先閱讀背面之注意事項再填寫本頁) •I %

-1T 409215 A7 B7 五、發明説明（48 數。當一應用程式自一先前提取的區段讀取最後—個資料 時，即可利用該缓衝區執行次一預取1/〇作業。如表4中之 演算法所示，然後將利用該緩衝區爲最接近目前正在讀取 的緩衝區終端之應用程式預取次—資料區段。”最接近— 緩衝區終端的應用程式”意指根據其現行的消耗速率將最 快要求次一區段的資料之應用程式。 利用最佳預取緩衝區數時，若任何應用程式都不曾在依 據所量測消耗速率而預設的時間之前讀取資料，則該應用 程式將不需要等候I/O作業。如果實際的消耗速率不是固 定的，則可增加預取緩衝區社，以便將消耗速率的變化列 入考慮。除了量測每一應用程式的思考時間之平均値以 外，亦量測思考時間之變異數，即可執行上述步驟。然後 利用該値計算一個"以變易數調整的消耗速率,，，亦即幾 乎所有的讀取要求（例如9〇%或95%的所有讀取要求）之到 達時間不會早於依據以變易數調整的消耗速率預測的時間 之速率。然後利用以變易數調整的消耗速率取代平均消耗 速率’而計算平行處理因數。 見在知考慮所有應用程式的總消耗速率超過標案系統的 總磁碟頻寬之情形。在此種情形中，以前文所述方式計算 的平行處理因數將是一個大於檔案系統可用磁碟數之數 芋。因爲無法起動比現有磁碟數更多的同時I/c>作業數， 所以指定比磁碟數更多的緩衝區給預取1/〇作業時毫無意 義Θ因此，所需的預取缓衝區數係計算爲：爲循序I/。 而開啓的檔案實例數加上磁碟數或平行處理因數（取較小 -51 卜紙浪尺度通用中酬家標辛（CNS ) Λ4規格（2iOX297公楚 ---------裝------訂 (請先閱讀背面之注意事項再填寫本頁) 經濟部中央標準局兵Ti消fr合作社印狀 409215 ΑΊ _________Β7___五、發明説明（49 ) 者）。如果消耗速率超過總磁碟頻寬，則該預取緩衝區數 將足以使所有的磁碟保持忙碌（亦即，當一磁碟上的前一 I/O作業結束時，即開始一個新的預取I/O作業）。因此，供 應資料的速率將等於可自磁碟擷取資料的速率。 最後，將説明對上述計算的兩種改良，這兩種改良考慮 到檔案系統所連接的I/O子系統之特性。第一種改良適用 於在將一 I/O要求提供給裝置驅動程式的時間與開始實際 I/O作業的時間之間有顯著延遲之系統。例如，此種延遲 發生在以網路連接的磁碟（例如VSD)，其中一 I/O要求在到 達磁碟之前必須先經過網路的繞送。爲了獲得最大的磁碟 資料傳輸率，在前一 I/O作業結束之前，必須將次一 1/〇要 求發出到裝置驅動程式。爲了執行此一步驟，必須可在比 原來更早的時間使用一預取緩衝區，以啓動次一 1/〇作 業。因此’預取I/O作業專用的緩衝區必須大於磁碟數（1 + ε)倍’其中係以平均I/O要求的延遲時間與平均磁碟I/O時 間的比率表示£。 緩衝區計算的第二種改良考慮到諸如磁碟控制器及 匯流排等I/O子系統组件之限制。如過檔案系統的磁碟數 較大，則增加磁碟頻寬時，可能得到—個大於總磁碟1/0 資料傳輸率且系統無法支援的數目β如果發生此種情形， 則預取I/O作業專用的預取緩衝區數無須等於磁碟數。等 於總I/O資料傳輸率除以單一磁碟頻寬的緩衝區數將足以 平行啓動系統可有效支援的數目之磁碟I/C)作業。決定總 磁碟I/O資料傳輸率時，可利用硬體規格在安裝檔案系統 ----1——I---合! (請先聞讀背面之注意事項再填寫本頁) 訂 __ -52- 本紙浪尺度適用中關家^1 ( CNS ) M规格ί1()χ297公楚） 409215 A7 B7 五、發明説明（5〇 ) 時直接量測資料傳輸率，亦可於執行檔案系統時記錄所觀 測到的最大資料傳輸率。 (請先閱讀背面之注意事項再填寫本頁} 計算一"有效磁碟數”，即可表示上述這兩種改良，然後 如表3所不，以该有效磁碟數取代實際磁碟數，而用於預 取緩衝區的計算。 ---------表3 :計算預取緩衝區組的所需大小........ 1 .計算有效磁碟數如下： n_eff = MIN(ceil((l + L_start/L」o)*n_diska)，ceil(T- sts/T_disk)) 其中 n_disks=檔案系統可使用的磁碟數 L_io=讀取磁碟上的區段之平均i/o延遲時間 L_start=平均I/O啓動延遲時間 T一sys=磁碟子系統的最大總υο資料傳輸率 T—disk=單一磁碟的平均1/0資料傳輸率 好"·部中夾標枣局Μ工消赀合作社印" 2 對於被循序存取的每一開啓之檔案實例丨而言，計算一 個經過調整的消耗速率c_i，使對次一資料區段的所有 要求的一部分（例如90%)之到達時間不早於該經過調整 的消耗速率所預測之時間（亦即以檔案系統區段大小除 以c_i所表示的一段長度之時間中）。量刿該檔案實例 的平均消耗速率及變異數，即可以统計方式計算出該 經過調整的消耗速率。 〃 將經過調整的總消耗速率計算爲所有循序開啓的樓案 _______ -53- 本紙狀i適财ϋ隊辟（CNs"m视格（2丨GX 297公楚f 40921^7 I--—____B7 五、發明説明~ ~' ~--- 實例的經過調整的消耗速率之總和： c_total=sum c_i, for i =l...nJnst 其中 n_inst=循序存取的開啓檔案實例數 計算所需的預取平行處理因數如下： n_para=c_total/T_disk J ·然後使用步驟1及2中計算出的數値而計算所需的預取 緩衝區數如下： n_bufs_desired = MIN(n_para, n eff) + n jngt ................表4 :安排預取I/O作業的時程…....... 此程序的輸入是實際預取緩衝區數n—bufs—assigfted，由 緩衝管理程式根據以表3所示方式計算出的所需緩衝區數 n_bufs_desired，而指定該實際預取緩衝區數。 咸算法維護兩個整體性計數器：n_io_t〇tal，是目前進 行中的（或已提供給裝置驅動程式的）預取I/O作業數；以 及n_prefetched ’是存放作爲預取區段使用者的應用程式 尚未讀取的預取區段數。這兩個數目的總和即是目前用於 預取的緩衝區數。 ίί1/Γ-ΐ-部中吹枒準局妇工消费合竹社印¾ ---------參------訂 (請先閱讀背面之注意事項再填寫本頁) 此外，對於每一循序存取的開啓檔案實例i而言，本演 算法追蹤應用程式將存取預取I/O作業尚未開始提取的次 一區段之預測時間。將此數字表示爲t_next[i]。 1.設定 n_io_total&n_prefetched的起始値爲零。 對於每一循序存取的開啓檔案實例i而言，設定n_io[i] -54 - _________ 本紙張中國國家標準（CNS } Λ4規格（210X 297公t } 4093½ __________B7 五、發明説明（52 ) ^ 的起始値爲零’並設定t_next[i]的起始値爲應用程式根 據經過調整的消耗速率c—i而將要求次—資料區段的時 間。 以t—next[i]分類所有循序存取的開啓檔案實例，而建構 一個排序的檔案實例表’其中係將最小値放在最前 面。 2.如果n_io_total + prefetched大於或等於n_bufs-assigned， i % 則進入步驟 4 ;否則，繼續進行次一步驟a 3 ‘將次一預取I/O要求提交給排序樓案實例表中之第— 樓案實例in(將是具有最小t_next[i]的標案實例）。 丁 . -so 將t_next[i]更新爲應用程式將要求的在已開始進行預取 I/O作業的資料區段的次一資料區段之預測時間。根據 此新的t_next[i]値，而爲排序檔案索引表中之所有檔案 實例重新排序。 遞增 n_i〇_total。 回到步骤2。 4 .等候下列事件中的一個事件發生： a) 完成一預取I/O作業： 遞減 n_io_total，並遞增 n—prefectched。 經漓部中次核準局另工消贽合作社印策 回到步驟4的開始（等候次一事件發生）。 b) —讀取作業到達已預取的一區段之末尾。 因爲璜取作業將把資料自預取緩衝區拷貝到應用程 式的位址空間，所以另一預取作業無法使用該緩衝 區。 ______ -55- 本紙汰尺度適用中國國家標糸（CNS ) Λ4規格（2ΐ〇χ 297公釐） 五、發明説明（53 ) 遞減N—prefetched，並回到步骤2。 c )緩衝S理程式改變指定給預取緩衝區組的缓衝區數 (n_biifs—assigned) 〇 回到步驟2。 d)關閉一個開啓的檔案實例i。 自該排序檔案實例表去掉該檔案實例。 將η—prefetched遞減一個爲該檔案實例而預取的缓衝 區數之數字。 回到步驟2。 盖良緩衝儲存區效能4緩衝區瞢琿 本發明之平行標案系統是爲了效能是—個極重要因素的 職電腦系統而開f。可能影響到效能的—個面向是標案 系統的緩衝儲存區使用率。該問題在於：係’以無法預測之 方式向系統要求可變容量的緩衝儲存區空間。本發明實施 了-種緩衝儲存區管理架構，其中先識別系統中現有的使 用模式，然後對應地調整緩衝儲存區的行爲，因而提高了 效能及空間使用率。本發明大致經由使用模式分析，而改 善緩衝儲存區效能、空間使用率、及分佈。 因爲本發明之系統識別目前正在操作的丄作負荷類型， 所以可提高本發明的緩衝儲存區使用及内容替換之有效 性’本發明並因而調整缓衝儲存區的行爲。本發明建議架 構所偵測及回應的這兩種工作負荷是循序及隨機工作負 ^此種區分的理論基礎㈣於兩種Η Μ狀工作组 谷ϊ定義义差異。分析目前的狀態，即可預測未來的行 -56- 本紙張X度迠用中國园家標皁（CNS ) Α4規格（2!〇χ297公釐 ----；--.---知-- (请先閱讀背面之注項存填寫本育) 訂 409215 A7 B7 五、發明説明（54 ) 爲。一旦建立了系統中之現行使用模式，且假設該使用模 式爲相對穩定時，則可使緩衝儲存區作出對應的回應。 (請先閱讀背fi之注意事項再填寫本頁) 完整的缓衝儲存區被分成若干不同的工作單元，每一工 作單元都控制該完整缓衝儲存區空間的一部分，並負貴不 同容量的若干緩衝區。每一工作單元係由兩個子單元所組 成，這兩個子單元分別監視系統所操作的兩類工作負荷。 不同的工作單元數目及這些工作單元所負責的缓衝區容量 係動態地改變。緩衝儲存區管理程式在某一時點識別機率 較高的有大量需求之緩衝區容量，並因應地建立各工作單 元。固定設有一個額外的工作單元，用以照顧送進來的對 與所有其他工作單元固定容量不同的緩衝區容量之要求。 此種方式將送進來的要求直接指向主導所需容量的緩衝區 之緩衝儲存區部分，而縮短了緩衝儲存區的回應時間。該 處理面向將緩衝儲存區分段的問題限制於—個工作單元， 且只在該工作單元中採取合併及重新對映等額外措施，而 有助於減輕該問題。針對每一工作單元的每一子單元不斷 地更新使用統計數字。 定期檢查所搜集的使用統計數字。因此，將緩衝儲存區 空間重新分配給不同的工作單元。因爲本發明之系統藉由 分析現有的使用模式，而預測未來的使用模式，所以並非 立即進行新的空間重新分配，而是在有需要時才起作用β 每一工作單元有兩類空間限制，亦即一内部的及—外部 的。内部的空間限制區分兩個子單元外部的空間限制又再 細分爲兩類限制，亦即實體限制及虚擬限制。實體限制代 _________-57- 本纸帳尺度適用中囷國家標準（CNS )六4規格（21〇χ 297公釐） 經淡部中Λ標準局贤^消费合作社印繁 409215 A7 ΒΊ____ 五、發明説明（55 ) 表在使用模式架構的控制下屬於個別工作單元的實際空間 量。虛擬限制是被使用模式分析及預測程序投射爲該工作 單元應嘗試遵守的實體限制之限制。虚擬限制被用來推論 是否容許一特定工作單元的實體限制擴大，或者收到在一 個不容許擴大的工作單元之要求時在其控制下迫使該特定 工作單元放棄一部分的空間，因而在本質上容許該特定工 作單元的縮小。 設定新虛擬限制的程序係以下文所述之方式工作。各子 工作單元的統計數字被分析JL被用來推論使用模式及活動 水準，用以決定最適合該子工作單元需求的的空間。每一 子工作單元嘗試取得所決定最適合其需求的空間量（亦即 其工作組的容量）^該子工作單元的相對活動水準代表最 適合其需求的空間之上限。 係由一架構管制新空間的取得，在此架構中，每一工作 單疋内的實體限制及虚擬限制係以下文所示之方式互動。 當對一新緩衝區的要求到達時，由控制所要求容量的工作 單兄服務該要求。如果在該工作單元中有一個自由的緩衝 區，或者可極簡便且迅速地取得緩衝區，則可用該緩衝區 來滿足進來的要求。該工作單元繼續比較其實體限制及虛 擬限制。如果實體限制並不小於虚擬限制，則該工作單元 繼續尋找在其控制下最易於取得的空間。否則，現有的工 作單元將找到一個可縮至最小的工作單元，並將一空間取 得要求傳送到該工作單元。接收要求的該工作單元^到在 .其控制下最易於取得的空間’並放棄對該空間的控制權。 ------------—--- - 58 - 本紙張歧^(加x 297^ 了 (請先閲讀背面之注意事項再填寫本筲) ^.

-1T 經7¾部中央榡準局M.T-消贤合作社印犁 409215 A7 ____________B7 五、發明説明（56 ) — 原來的工作單元取得該新空間的控制權，並利用該空間來 滿則進來的要求。 執行使用模式偵測程序的頻率可能對整個架構的有效性 有相當大的影響。如果過於頻繁地執行該程序，則可能對 某一子工作單元中極短期的活動尖峰有太嚴厲的反應。另 —万面，如果每隔一段較長的時間間隔才執行一次該程 序，則架構的有效性及準確性將隨著時間而降低Λ因此， 每當執行該程序時，即決定下次應在何時執行該程序。該 计算係基於所有的工作單元存取在其控制下的所有空間之 預期時間。該時間間隔係受限於預定的上限及下限。該時 間間隔可讓使用模式程序推論工作負荷的分佈，而不受單 一限制事件的影響。對隨機工作負荷用户端程式的工作组 疋推論容易度相當於對循序預讀工作負荷用户端程式所需 空間之推論。 本架構之優點包含在一多用途環境中的可用緩衝儲存區 空間的效能及使用率之提高。 習用的處理方式只將緩衝儲存區視爲單一工作單元，並 以取近最少使用（least recent〖y uSed)之方式釋出缓衝儲 存區2間，以滿足進來的空間要求，而熟悉以習用方式管 理一標案系統缓衝儲存區的人士在認知使用模式是—種對 習用處理方式的改良之後，將可了解本發明之方法如何將 缓衝儲存區的使用最佳化。 當我們預知進來的要求之本質，並已爲該要求做好準備 時，則將每一個進來的要求傳送到一個有最高的機率被用 _ . __ - 59 - (CNS ) Λ4規格（2I0X 297公釐） 其衣ΐτ------r (請先鬩讀背面之注項再填寫本頁) 409215 A7 _________ B7 五、發明説明（57 ) — 來滿足該要求的緩衝儲存區區域。此外，我們知道每—工 作單元中可爲每一工作負荷所專用的空間容量，因而可相 應地調整其他的系統動作（例如預取速率）。 A援存取控制表之延伸檔棄屬她 如如文所述，我們知道最好是將存取控制表提供給本發 明的共用磁碟檔案系統，以利於該環境中不同的電腦之平 行執行。爲了達到上述目的，本發明提供了延伸檔案屬 性，以便有效率地支援Unix環境中習知的這類存取控制 表。 經濟部中央標準局吳工消论合作社印絮 ---------^------ΐτ (請先閲讀背面之注意事項再填寫本頁) 延伸屬性可使可變長度的資訊與一檔案相關聯，而可利 用檔案本身中所儲存的資料各別地存取該檔案。延伸屬性 的一種用途即是用來儲存各存取控制表（ACL)，而這些 ACL是用來控制可容許哪些用户或用户群以何種方式（讀 取' 寫入等）存取一檔案。ACL對一延伸屬性實施例所作 的要求與延伸屬性的許多其他用途不同β因爲檢查存取許 可的所有檔案系統作業都需要使用到該檔案的ACl，所以 迅速且有效率地存取ACL的資料對檔案系統的效能是相當 重要的。另一方面，ACL通常是較短的，並不非常頻繁地 改變ACL的内容，而且縱使每一檔案都有一 ACL，但是許 多這類ACL將是相同的，亦即，與檔案中的値比較時，通 常只有相當少的不同ACL値。現在將説明如何利用各acl 所提供的使用特徵，並説明如何提供有效率地利用空間之 屬性儲存區，因而得以迅速地存取屬性資料，而以此種方 式實施延伸屬性。此外，該實施例極有效率地支援屬性繼 ______-60- 本紙張尺度it财關家標準（.0ί7$) Λ4規格（210X297公楚） — 409215 _ 五、發明説明（58 ) , 承。此種方式特別適用於POSIX ACL的實施。 基本上，本發明之延伸屬性實施例採用下列組成部分： (請先閲讀背面之注意事項再填寫本頁) ' 屬性檔案（Attribute File ;簡稱 AttrFile) ° 這是一種儲存所有屬性資料的特殊檔案。該檔案包含 一序列的登錄；每一登錄屬於下列兩種類型的其中之 一：屬性登錄，該屬性登錄包含一特定屬性之値；自 由空間登錄，該自由空間登綠標示屬性檔案内的自由 空間（亦即下一次需要將新的屬性登錄加入AttrFile時 可重新使用的空間）°這兩種登錄都是可變長度，但係 對準適當的邊界（例如，8或1 6位元組的倍數），以便 減少分段。一特定對準長度的選擇取決於屬性登綠的 最小及平均長度。 -屬性參考値（Attribute References ;簡稱 AttrRefs)。 這是儲存在每一檔案的檔案索引中之短値，可在 AttrFile中找出該檔案的屬性資料所在位置。係以對準 長度爲單位，而以AttrFile内屬性登錄的偏移量表示該 位置，亦即，將AttrRef計算爲位元組偏移量除以對準 長度。 -屬性索引（"Attribute Index ;簡稱 Attrlndex)。 經潢部中次枒準而只-τ消资合作社印$ 這是一種可在一 AttrFile中找到一特定屬性値之資料結 構。將在下一節的"屬性値查詢”中詳述Attrlndex的結 構及使用。 - 廢棄屬性收集器。 這是一種在適當的時間啓動而自AttrFile中清除不再被 -61- 本紙張尺度適用中國园家標率（CNS ) Λ4規格（2丨οχ”7公釐） 409215 A7 B7 五、發明説明（59 ) 任何現有檔案查詢的屬性登錄之程序。 屬性値共用 在本發明的共用磁碟權案系統較佳實施例中，提供了屬 性値的共用作爲—種延伸屬性實施方式。此種方式可讓屬 性値相同的所有檔案共用實體屬性儲存區a將所有的屬性 #料儲存在一共同位置，即可達到上述目的，該位置即是 AttrFile。儲存在一檔案"f_，的檔案索引之AmRef包含在 AttrFile存放τ的屬性資料的登錄之位置，且係以仏的以 中該登錄之偏移量表示該位置。屬性値相同的各檔案將在 其檔案索引中包含相同的AttrRef値。係以下列兩種方式完 成該屬性値共用： 1 .屬性繼承： 屬性繼承意指：當產生一個新檔案時，將該新檔案之 延伸屬性設定爲與其根源的一現有檔案之相同延伸屬 性値。例如，當拷貝一檔案時，可將該拷貝檔案的屬 性値設定爲與原始檔案相同的値^ POSIX ACL則是一 種不同的屬性繼承實例，提議的POSIX ACL標準規 定：當產生一個新檔案或目錄時，將該檔案或目錄的 ACL設定爲一個與產生樓案的目錄相關聯之系統預設 ACL値。換言之，在p〇SIX之下，一個新的檔案自其根 源目錄繼承其ACL。 根據本發明，只要自作爲屬性繼承根源的檔案或目綠 之檔案索引拷貝AttrRef，即可完成此種屬性繼承。在 此種方式下，被繼承的屬性將共用與所繼承的屬性相 -62- 本紙張尺度適州十國國家標隼（CNS ) Λ4規格（2I0X 297公釐） (請先閲讀背面之注意事項再填寫本頁) -丨裝_

11T 經濟部中次掠準扃.'只-T-消贽合作社印繁 A7 __________B7 五、發明説明（6〇 ) 同的實體儲存區。 2 .屬性値查詢： I. 來-- (請先閱讀背面之注意事項再填寫本頁3 爲了將一屬性設定成或改變成—個並非自另一檔案繼 承的値’採用了屬性索引，用以決定具有相同値的一 登錄是否已經存在於該AttrFile。—種諸如赫許法等的 索引査詢方法可用於此一目的：爲了設定或改變一屬 性値，將一赫許函數應用於屬性資料。利用所得到的 赫許値作爲一赫許表的一索引，其中將找到>AurRefs 表，這些屬性參考値對照到具有散列對映到同一赫許 値的屬性資料的AttrFile中之各登錄。將待儲存的新屬 性資料與所有這些登錄中之資料比較。如果找到相符 者’則將對照到現有登錄的一 AttrRef儲存在該檔案之 檔案索引。如果沒有找到相符者，則將包含新屬性値 的一個新的登錄加入AttrFile，並將該新登錄之AUrRef 儲存在該檔案的檔案索引及赫許表中，因而使用同一 屬性値的未來屬性更新將找到該新的登錄。 爲了增加屬性値共用的可能性，在許可的情形下，先 將新的屬性値轉換成一正規形成，然後才儲存或查詢 這些新的屬性値。例如，可以用户或用户群識別碼儲 存一存取控制表中之各登錄；此時如果兩個ACL的功 能相當’則縱然在設動這兩個ACL時，可能並未以完 全相同的格式呈現這兩個ACL，上述方式也可使這兩 個ACL共用AttrFile中之相同儲存區。 於實施本發明系統的儲存功能時，延伸屬性特別適用於 -63- 本纸張尺度適用中國國家標準（CNS ) A4規格（2丨0>< 297公釐） 409215 經泊部屮次標卑^0^消资合作社印^ A7 B7 _五、發明説明（61 ) 儲存ACL及其他類似的用途。雖然一使用者可能用有大量 的檔案，但是該使用者相當不可能將一不同的ACL與每一 該使用者的檔案相關聯。而是通常有若干群相關的檔案， 這些相關的檔案具有與這些檔案相關聯的相同存取權。例 如，屬於一特定專案的各檔案通常具有相同的ACL，該 ACL將檔案使用權授與和該專案相關聯的各使用者。再舉 另一個例子，在目錄階層的同一目錄或子樹内之各檔案通 常將共用同一 ACL。事實上，在提議的POSIX ACL標準 中’ ACL繼承的目的在於讓一使用者易於爲同一目錄中之 各檔案維護一個共同的ACL。因此，我們預期一標案系統 中不同ACL値的總數將遠小於檔案的總數；事實上，我們 預期將小於一個很小的分數。亦即，與個別儲存每一 acl 比較時，使具有相同ACL的各檔案共用ACL儲存區之方式 將使用於儲存ACL的虛耗空間至少減少到相同的分數。 此外，各ACL通常並不包含一份較長的個別使用者表， 這疋因爲很難官理此種表。大多數的系統反而容許定義用 户群；然後可在一ACL中使用一用户群，以對照到屬於該 用户群的各用户。因此，極長的ACL是很少見的，因而通 常可將一 ACL儲存在一個小容量的空間中。此一事實加上 ACL的共用意指：有可能將大量檔案的ACL資料緩衝儲存 在記憶趙中。此種方是可以極有效率之方式擷取—檔案之 ACL，這是因爲ACL很可能緩衝儲存在記憶體中，因而無 須額外的磁碟I/O作業即可取得ACl資料。 當改變大量檔案的ACL時，許多這類八匚匕有可能被改變 I- ϊ I -:- - n 1 ^1. >z, ^^^1 1.^1 ^^1— r^i *--D (讀先閱讀背面之注意事項再填寫本頁) ___ -64- • 本躲尺度適财關石料（CNS) (2丨Q χ 297公疫） *00215 A7 B7 五、發明説明（62 ) 成同一新値。例如，此種改變將發生於容許一個新用户使 用與一特定專案相關聯的各檔案。由於ACL的共用，一組 相關的ACL改變作業中，只有第一個ACL改變作業需要更 新AttrFile，使用相同ACL値的後續ACL改變作業只需要杏 詢Attrlndex中之ACU直即可。此即意指··縱使在—個具有 大量同時ACL更新的工作負荷下，對AttrFile的存取大部分 將是唯讀作業。因此，此種將所有的屬性儲存在_個共同 的位置之方式將不會產生瓶頸的問題。此種方式對—個最 好是將屬性資料缓衝儲存在當地的分散式處理環境特別重 要，因爲原先的在當地緩衝儲存之方式將因需要使緩衝儲 存在其他節點上的屬性資料無效，而使AUrFile的更新成 本印貴許多。 _ 廢棄屬性收集是一種需要提供的持續性需求。當不再需 要一屬性登錄時，屬性値的共用使收回八咐打16中的空: 增加了一些困難。問題在於偵測何時删除該登錄才安:: 亦即查詢孩登錄的最後一個檔案何時被刪除或該檔案的屬 性何時被改變。此—問題的的—個共用解決方式是爲每— 登錄维護一個參考計數；當查詢該登錄的一 AurRef被儲存 在一檔案的檔案索引時，即遞增該參考計數，且當— AUrRef被刪除時，即遞減該參考計數。然後在該參考:數 回到零時，即可刪除該AttrFile登錄。然而，縱然新的屬 性値業已存在於AttrFlle ’每當繼承、儲存 '或更新—屬 性時，此種解決方式即需更新—參考計數。因此，對哕 AU㈣e的存取不再大部分是唯讀#業，這將造成潛在: 65- n I n I---1 κ — I - n I ____ T 、-° (請先閱讀背面之注意事項再填寫本頁} 木紙狀度制巾賴 $^ ( CNS ) ( 210-^297¾- 409^15 A7 __________ B7_ 五、發明説明（63 ) 瓶頸。 本發明並不使用參考計數，而是利用廢棄屬性收集之方 式收回屬性空間。廢棄屬性收集以下文所述之方式找到並 刪除不再使用的屬性登錄。每一屬性登錄的—部分是一參 考旗標（Reference Flag ;簡稱Refnag)，當將—個新的登錄 加入AttrFile時’必然設定該RefFlag。廢棄屬性收集係在 下列三個階段中進行： 階段i : 掃描整個AttrFile ’並關閉該檔案中每—屬性登錄之 RefFlag。 階段2 : 掃描所有的檔案索引。對於在一檔案索引中找到的每一 AttrRef而言，將AttrFile中對應的屬性登綠之參考値開 啓。 階段3 : 再度掃描AttrFile，並刪除RefFlag仍然關閉的所有屬性 登錄。 爲了確保廢棄屬性收集將不會删除在該廢棄屬性收集程 序進行中所產生新參考値之各登錄，廢棄屬性收集必須與 查均作業作業同步，其中該查詢作業是參照前文"屬性値 共用”這節中”屬性値查詢"這一項目所述的設定或改變— 檔案屬性作業之一部分。因爲廢棄屬性收集可能耗用較長 的時間（尤其是在第2階段），所以在執行廢棄屬性收集作 業時，只停止所有的設定屬性/改變屬性之作業並不是一 -66 - 本紙诙尺度適州巾國國家標準（CNS ) Λ4規格（210X297公釐〉 ---------私-- (讀先閱讀背面之；;i意事項再填寫本頁) 訂 A7 B7 M部中次樣準而一只工消贽合作社印製 五、發明説明（64 ) 種良好的方式。反而在設定屬性/改變屬性作業發現 AttrFiie中一個現有的登綠具有—個符合所設定新値的値 時’在其將該AttrRef儲存在檔案的樓案索引之前，也先檢 查該登錄中的RefFlag是否是開啓的。在此種方式下，只 有在廢棄屬性收集的最後一個階段中，且只有在屬性値查 詢作業找到一個RefFlag關閉的屬性登.錄時，廢棄屬性收 集與屬性値查詢作業間之明確同步是必要的。 啓動廢棄屬性收集程序的程序是重要的。若沒有磨棄屬 性收集，則縱然現用屬性資料（即仍然有查詢的屬性値）之 總數並未成長’ AttrFile也將毫無限制地成長^ AttrFile成 長的速率取決於設定屬性/改變屬性作業之速率。對於諸 如ACL等屬性使用而言，此種作業的速率在本質上是無法 預測的。因此，每隔—個固定的時間間隔（例如每天一次） 〇動'人廢棄屬性收集的策略是不適用的。我們反而要監 視屬性資料的總容量，亦即AUrFile的容量減掉仏⑽以中 之總自由空間。每當屬性資料的量成長到某一因數（例如 1<5或2)時，即啓動廢棄屬性收集。此種策略在現用屬性 資料量保持不便時可有效地使AurFUe不會 j介資料節點作f ： 本節中將說明中介資料節點之㈣，該作業將提升在多 個電腦需要更新或擴大同一資料物件的情形時之效能。我 們首先將説明爲這些功能而產生—中介資料節點，然後將 况明識別中介資料節點及回復中介資料節點之方法。 _中介資料節點之依用 -67- 表錄尺度賴中關？拆（CNS )罐格（別心了公您 n l^i i ϋ— I I Ij--R, In I- I -- - 1-* 11 U3 ，-·* (請先閱讀背面之注意事項再填寫本頁} A7 409215 五、發明説明（65 ) — 與本發月的中介資料$·點有關之本第—節將大致説明本 發明的中介資料節點是什麼、以及該中介資料節點將解決 哪些問題。在本發明的系統中利用中介資料節點來管理共 用磁碟環境中平行讀取及窝入之檔案中介資料。平行檔案 系統使多個處理器可以獨立存取構成檔案系統的部分或全 邵磁碟。爲了利用此一能力，多個處理器在讀取及寫入時 應共用一個檔案。 ‘ 有幾個問題可能大幅降低此種存取的效能。雖然各節點 在適當鎖定其所讀取或寫入的各區域之情形下，這些節點 可讀取及窝入檔案的各不同區域，但是這些節點都需要存 取相同的中介資料.中介資料包括檔案大小、檔案存取與 修改時間、以及檔案的資料區段之位址。例如，讀取及窝 入檔案的所有作業都需要知道該等作業是否超過了檔案大 小，並在該等作業擴展該檔案時更新該檔案大小^ ^果需 要以70全共用方式平行寫入一檔案，則上述這種單點發生 的事件可能造成一個嚴重的瓶頸。 本發明實施了 一種可讓每一節點於讀取及窝入同—檔安 時儘量獨IL運作之系统，並設計出一種使這些作業同步之 機制’因而只要本發明用來管理中介資料資訊之方法，則 所有的節點都將可得知一致性的檔案狀態ε本發明用於在 一共用磁碟檔案系統中管理一檔案的中介資料資訊之方法 爲：爲每一檔案選擇—單一節點作爲該檔案之中介資科節 點。該中介資料節點負責處理中介資料進出存放中介資^ 的一個或多個磁碟時之所有U0活動。 _________ - 68 - _本紙浪尺度過用中國囚家榡準（CNS ) Λ4規格Γ2_!〇><2们公 (讀先閏讀背面之+注意事項再填穷本頁> 訂 五 :¾¾-部中次榡準局負工消兜合作.iL印 hi B7 、發明説明（66 ) 更:節點都與該中介資科節點通訊，以便提取或 之中介資料資訊。 不直接存取磁碟中 ::存取檔案的第一個節點爲中介資料節點。因此，如 個節點需要存取檔案’則因該節點可直接取得中 4:資=會產生額外的虚耗作業。其他的節點將經由 及千介鸢料節點而取得中介資料。 而2料節點的導入將可避免相當數量的磁碟活動，因 相當的提升。 〕十彳4案系統I效能有 磁節點保存—份緩衝儲存的中介資料，用以反映 :中介資料。其他節點亦保存—份過去 枓即點孩取的緩衝儲存之中介資料，五於需要 改變存取時間時）增添該中介資料。 .r 每-中介資料元素(存取時間、修改時 區段之磁碟位址)有其本身的使用模式及7徵:例 :二本發明之系統不需要—個非常精確的存取時間，炉是 要個準確度在五分鐘内的存取時間 地對中介資料銘 7需要頻繁 ^ U進行更新，因而可節省大量的通訊。 “上’：要系統的行爲具有—致性，所有節點上的樓案 點上的枰央士，咕/ 種複雜的万式來控制所有節 面本'、，將知到—種多個節點可同時擴展檔案 的平行窝入架構。 m心案 利用一種遞延同步演算法，即可“大量的磁碟

--------- - RQ 本紙张纽剌帽 (請先閱讀背面之注意事項再填寫本頁)

、發明説明（67 4092¾ B7 執行之：二？—種作爲。每—節點的作業系統的-部分而 過修改的^料同步服務程式嘗試每_秒即清除磁媒中經 檔案，則咅中介資料°如果M個節點以平行方式寫入 j4母隔N秒對中介資料只有M次磁碟存取。在 傳送二下’所有的節點將其經過更新的中介資料 步服務程i取：7號Γ介資料節點每隔N秒當其自同 〜\取侍一仏唬時，即清除檔案。 —每—節點將存取磁碟，以便讀取或寫人中介資料。 ^ ^ $的平彳T寫人這節的第二部分係有關將鎖定模式用 捧:找七1資料管理節點。在多個處理11可獨立存取構成 :'先的所有磁碟之本發明平行標案系統中，使用鎖定 杈=以哥找中介資料管理節點的符記係用於中介資料節點 勺選擇及識別。爲了利用此種能力，多個處理器於讀取及 寫入時應共用一檔案。 在本系統中，將一節點指派給每一檔案，該節點負貴存 取及更新肩檔案的中介資料。該中介資料節點（或中介節 點）於接收到要求時與其他節點共用此資訊。 孩中介資料節點保存與檔案的中介資料有關的資訊，並 作爲磁碟與存取檔案的所有節點間之一智慧型緩衝儲存裝 置。也會發生中介資料節點（或中介節點）停止服務該功能 的之情況。爲了能得到平順的作業及回復，必須處理這些 情況。此時係以直接的方式從以往都存取該中介資料節點 的各節點中選出一個新的中介節點。 -70 本紙乐尺度適用中國國家標车（CNS > Λ4現格^ΐΤ^χ297公楚] (請先閱讀背面之注意事項再填寫本頁) 裝. 訂 經漭部中央標準扃只τ,ί-f1;赀合作社印«'14 409215^7 ________ _ B7 1 - _ 五、發明説明（68 ) 此時選出一個中介節點，並使所有的節點都知道該資 訊β選擇程序要考慮到樓案的存取模式。每-標案應該有 *個唯一的中介節點。此外，本架構應確實讓中介節點接 管及回復。在本發明的系統中，選出若干中介節點，並使 其他節點都知道這些中介節點的資訊β 本發明使用一符1己管理器子系統。符記管理器是一種將 符記授與各節點的分散式子系統。每一節點可要求一個具 有特疋模式之有名稱符記。如果該模式並未與具有同一 名稱且已授與其他節點的各符記衝突，則符記管理器將該 符圮杈與該節點。爲每—符記設有—份包含可能模式及衝 突表的清單。如果所要求的符記與已授與另—節點的符記 衝犬，則執行一取消作業，且發生衝突的節點將其符記模 式降等爲一個不與被要求的模式發生衝突的模式。 選擇存取檔案的第一節點作爲中介資料節點。因此，如 果只有一個節點需要存取檔案，則因該節點可直接取得中 介資料，而不會產生額外的虛耗作業。其他的節點將經由 該中介節點而取得中介資料β 經滅部中吹標準局κ π消費合作社印欠 II - ---- ---衣！ - II - —订 (請先閲讀背面之注意事項再填寫本K ) 對於每一槽案而言，我們界定了”中介節點符記"。該中 介節點符記共有三種模式："ro〃（唯讀）、，,ww"(弱勢寫 入）、及"XW"(互斥窝入）。規則如下：_，xw"符記與所有的 模式衝突；"WW"與"XW"及本身衝突；"ro"只與”xw，，衝突。 因此，有兩種可能性：〇個或更多個節點保有„Γ〇"中之符 記，然後最多一個節點可保有"ww"中之符記，或單一節 點保有"XW”中之符記。符記管理器（Token Manager ;簡稱 -71 - 本紙张尺度適用中國國家標準（CNS ) A4規格（210X29?公釐） 五、發明説明（69 ) TM)子系統負責管理一節點之符記，益確保符記模式與此 定義一致。可將不同模式間之衝突概述於下表5 : -表 5—------

Γ0 WW XW Γ0 丰* WW * * 伞* χ·\ν 氺本 伞氺 氺* 對於中介節點而言，本發明設計出下列演算法：當一節 點首次開啓一檔案時，該節點嘗試取得模式"ww"中之中 介節點符記=符記管理器tm在有可能時（亦即其他節點並 未保有"WW"或"XW"中之符記時）授與"ww"中之符記°如果 此種情形發生時，該節點變成符記管理器。然而，如果另 一節點保有"WW"中之符記，則TM授與”ro"中之符記。然 後該節點知道另一節點是中介節點。該節點可查詢TM以 便得知該檔案的中介節點是哪一節點。 當一節點變成一中介節點時將發生一些情況。在此種情 形中’要求一"ww"將不會有所助益，因爲舊的中介節點 將不會把其符記降等^此時想要變成中介節點的節點要求 一 "XW"符記。此時將把—個收回訊息傳送到現有的中介節 點°舊的中介節點然後將其符記降等到"r〇"，JL TM將一 "ww”符記送回到該新的中介節點。如果一節點要求一 ’，xw__ 符記’且其他節點都未保有該符記，則TM將授與該模式 中之符記。 -72- 本纸張尺度適财國财標準（CNS ) A4規格（2]Dx 297公楚） (讀先閱讀背面之注意事項再填寫本頁) -丨裝

,1T 如果一卽點保百 409215 Α7 __________ Β7 五、發明説明（7〇 ) 疋 itc 1¾ 來 I Ψ 介節點，但是此外’其他節點都沒有使該檔案開啓。在此 種情形中，如果一節點嘗試取得”ww"中之符記，則將一 取消訊息傳送到中介節點。因此’該節點將其"xw"符記 等爲W'，然後TM可將一"ro”符記授與新的節點。W 將增強符記模式用於控制檔棄士 相關的檔案系統標準要求可在需要時取得正確的檔案大 小；然而，在有多個應用程式將資料增添到檔案時，以平 行方式維護所有節點上的檔案大小就效能而言是既複雜且 异貴的。該系列特徵的次一部分説明本發明的下列方式： 維護檔案大小，而在需要時可取得該檔案大小，且不會有 固定的虛耗作業。在此種情形下，若多個處理器於讀取及 寫入時共用一檔案且不會產生固定的虛耗作業，則該檔案 可利用多個處理器可獨立存取構成檔案系統的所有磁碟之 一平行檔案系統。 檔案的讀取及寫入共用涉及檔案大小的存取。每一讀取 及寫入作業需要檢查該作業的偏移量是否超過現有的檔案 大小，並且在發生此種情形時，送回—個檔案終止（EM— Of-File·，簡稱EOF)訊息。每―寫人需要檢查該作業的偏移 量是否超過現有的E0F，如果確係如此，則應擴展檔案。 當有數個讀取節點及寫入節點時，所有的檔案大小必須— 致。因此，如果某—節點在偏移量丨〇〇〇上寫入，則任何節 點在邊位置上讀取時，不應送回一 E〇F訊息。 保持一致狀態的—種方式是以串列方式進行對檔案大小 -73 f請先聞讀背面之注意事項再填寫本頁) i % 1 1 f 1 本纸依人度即丨H 標準（CNS ) Λ4規格（2!Οχ297公瘦 五、發明説明（71 4092 5 3； 的存取。然而’此種方式將會對平行“造成—大瓶頸， ^每-窝人（及讀取）在進行作業之前必須取得現有的樓 案大小。 在本發明的較佳實施例中，於每—節點當地内保存 標案大小資訊。此外’相每—份檔案大小資訊亦保持— 鎖定模式…鎖定管理器保證相衝突的就模式不會同時 存在。每-讀取及寫人作業的—適當鎖定模式保證在當地 緩衝儲存㈣案太,1、係精確到足以得到該作業的—正確社 果。不同的模式有： 用於在當地緩衝儲存的檔案大小内的讀取及寫入 -rw 作業 -”rf” -”wf_ -"wa -"xw (請先閱讀背莳之注意事項再填寫本頁) 用於在當地缓衝儲存的檔案大小外的讀取作業。 用於在當地缓衝儲存的樓案大小外的寫入作業。 用於添加到檔案之後的寫入作業。 用於減少檔案大小（類似截除作業）之作業，因 需要一互斥窝入鎖定 標案大小的鎖定模式之衝突表如下： 好滅部中央#^^兵-"消赀合作社印$1 --- ----表 6 - rw rf wf wa xw rw * * rf 承ΐ * * 丰本 wf * + ♦伞 氺+ wa * * * * xw 氺本 本氺 氺宰 氺伞 1—— 米衣------,η--------^ 當—節點將其鎖定模式升等時，即自一個追蹤檔案大小 :-_74 _本紙 4〇92i5 A7 B7 五、發明説明（72 赶境.邙-Ί·央樣卒局；3^消贽合作_社印製 的特殊節點(一中介資料節點(簡稱中介節點”讀取新的檔案 ^小。當-節點將其鎖定模式降等時，即將其檔案大小傳 送〗:a節點。中介節點本身保存其所收到所有檔案大小 中的最大値之—檔案大小（例外情形爲一節點將檔案大小 鎖疋在"XW"模式，此時可減少檔案大小）。 某二節點，、可崤取檔案大小〇w，rf)。某些節點（wf，Wa) :5加，术大小。—模式（xw)可減少檔案大小。實際的檔 大J疋各斤點在當地保存的所有標案大小中之最大値。 在田地緩衝儲存的檔案大小内的讀取或寫入作業需要對 案大小的-VW"鎖定4當地緩衝料的檔案大小外的 Μ取作業需要確保自其上次讀取檔案大小之後該檀案大小 並沒有増加。因此，這些作業需要取得鎖定（與增加 檔案大小的模式衝突）β 増：檔案大小的作業需要取得—"wf,或、a，，鎖定。如果 寫U知道新的絕對插案大小，則需要一"w鎖定。增 添作業需要-"仰"鎖定…增添作業係在現有的E0F處^ 因此個增添作業將在另一增添作業的終止處寫 =。因此’ "wa"與其本身衝突’這是因爲—個增添作業應 等候其他的增添作業0 可減少構案大小的唯一模式爲"xw"。這是一種互斥模 式：將使所有其他節點放棄其鎖定，因而失去了在 衡儲存的㈣大小。gut，在取得„xw”的節點完成其 時^例如完成-棺案截斷時），所有節點將必須自中介 取得新的檔案大小》 ' -75 (請先閲婧背Ϊ&之注意事項再填寫本頁) 裝 訂 4092 五、發明説明（π A7 B7 經¾-部中次標準局負工消费合作社印製 -76 我們無法得知一個在不同的節點上緩衝儲存不同的檔案 大J、足系統内部情形’因而須儘量增加檔案的平行寫入共 用’但疋孩系統仍然將檔案的—致性狀態提供給所有的使 用者。 此種解決方式可讓在不同節點上的使用者擴展檔案，並 因而獲致極高程度的寫入共用。縱然使用者擴展檔案大 小，也不需要以串列方式執行寫入作業。 衝儲存位元組範圍符記 、開發的平行窝人實施例的次—部分將説明用於 有存取（平行及非平行存取）的鎖定。只鎖定立即需要的 ^部分是成本高“ ’且需要利用每__應用程式呼叫而 :Η鎖疋&理器。本演算法嘗試預測應用程式的需求，其 2爲=慮系统中還有其他什麼事情正在進行，並儘量減 ^付记官理器呼叫的次數。 取對讀取及寫入同-構案而言，爲了 "列方式存 若要二此：H:區域’使用一分散式鎖定機制。然而， m :鎖* ’需要先取得—符記，這顯然是一種代 二1卜r業°因此’最好是預測檔案的存取模式，而在 衝儲存各符記。另一方面，取得-個不需要的 本㈣=降低效能’這是因爲另—節點將需要該符記。 式：而Ϊ 項説明了下列演算法··預測標案的存取模 =:即點取得-符記，因而得到最大的效能。

备不同郎點上的程A 元組範圍符艾銷， 丁巧~檔案時，以分散式位 圍付尤鎖疋執行對該檔案中不同區域的串列式存 本纸紅㈣财_家^τ^τ^(210χϋ 丨裝------訂 (請先閲讀背面之注意事項再填Κ本頁) 409215 A7 B7 經"-部中火標嗥历只工消"合作社印製 五、發明説明（74 ) 取。當-程序需要鎖定-位元組範圍時，該程序 取得-個適當的位元組範圍符記。該位元組範園： 該節點對i案的-部分之存取權。因此，= 有-個在讀取模式下用於檔案乂的範圍（⑽，2()·^待 時，則意指#節點可安*地讀取該㉟案的該部*。然3 5己 爲了避免該符記的借用，該節點在實際讀取之前必須二 孩符記’這是因爲如果另一節點需要寫入同—部分，可： 會借用該符記。鎖定該符記即可以借用。在完 ; 業之後，即解除對該符記的鎖定。 我們可將符記視爲"緩衝儲存"鎖定的一種方式。當 點需要鎖定一檔案的—部分時，該節點需要鎖定符：。： 先孩節點需要取得-符記並鎖定該符記…互完成作業且 解除該符記的鎖定之後，該符記仍然存放在該節點。因 此’在同-區域的各後續作業將不f要接觸符記管理器 只有在該符記被借用時’才需要一個新的對符記之要丄。 因此，要I一個比所冑更大的符言己而鎖定之可能是較有 利的。例如，如果-程序循序讀取一檔案，且該程序讀取 麵到2_的範圍，則戟次—鎖定將是刪到胸的範 圍，但該程序可要求—個諸如自1〇〇〇到1〇〇〇〇等的較大符 z然而’此種方式可能在其他節點上產生過量的符記流 通。如果另一節點正在進行自5〇〇〇到6〇〇〇的寫入作業，則 上述的符記取得可能延遲了該寫入作業。 、 本發明的觀念是在要求一位元组範園符記時提供兩個範 園：必要範固（這是作業所f的最小範園）、及希望範圍 -77 本纸ίΑ尺㈣财咖家系準（CNS ) Λ4規^ 參-- (請先閲讀背面之注意事項再填寫本頁)

*1T 40d2 A7 B7 五、發明説明（75 (這是預期將使用到的最大範圍）。符記管理 個涵蓋必要範圍但不大於希望範 〇J1 演算法:⑴如何爲每—作業計了:二…須指定兩個 法T 希望範圍及必要範圍， 孩/貝算法疋在要求端上執行々 .當贫法B .过女々1 ()如何計舁授與範圍，該 决异法疋在保有各相衝突的符記的節點上執行。 對於上述演算、m本發明區分兩種㈣存取模式： 隨機存取及循序存取。在隨婦取t，無法制起始偏移 量^欠:作業。假設循序作業係開始於前—作業結束處。 在母^一印點上每一檀案可客；t > 罹莱了多，人開啓，卫每一此種檔案實例 可展現一種不同的存取模式。 、本發明提供下列較佳的演算法。主要目標是儘量減少符 記的流通。 當嘗試鎖s-位元組範„ ,我們首A查詢符記管理 器，以確認節點上是否存在一個相容的符記。所試探的範 圍是作業必要的最小範圍。如果可在當地取得該符記，則 鎖定該符記’且不會發生其他的符記活動。 然而，如果無法取得該符記，則要求—符記。係根據檔 案作業的偏移量及長度而計算必要範園。係根據該檔案的 存取模式而計算希望範園。如果係隨機存取該檔案，則希 望範圍將等於必要範圍，這是因爲自其他節點借用符記 (可能是不需要的）可能得不到任何好處。然而，如果係循 序存取該標案，則希望範圍開始於必要範圍的起點，但終 止於無限大（將有一個特殊値代表無限大）^此種方式是嘗 試儘量減少未來的符記要求’因爲我們可預測到將需要未 -78- 本紙悵尺度適川中國囡家標準（CNS ) Λ4規格（210X 297公瘦） —----------良_______丁 ,vs (諳先閱讀背面之注意事項再填寫本頁) 五 發明説明（ 76 A7 B7 經系‘部中次標準局货Η消贽合作社印製 來的鎖定。 , 節站保有一個與另一節點上的一符記要求衝突的符 =時’該節點得到—取消要求。該取消要求包含要求節點 裳必要範圍及希望範圍。此時，时符記的節點必須決定 也:放棄的範圍。如果該必要範園等於希望範圍，則易於 足，且授與範園是必要範圍（也是希望範圍）。，然而，如 希望範圍與必要範園不同，則意指要求節點正循序存取 ^案，且菘節點希望有—個開始於必要範圍的起點但終止 ^播限大的符記°保有符記的節點隨即掃描要求節點存取 ^案的所有現行程序，檢查這些程序係循序存取或隨機存 % ^檔案。如果所有程序都是隨機存取該檔案，則該節點 ^與希望範固 '然而’如果—個或多個程序循序存取該權 ，則放棄希望圍將是—種浪費，因爲我們有極高的機 率可以得知隨即將被要求的符記。在此種情形巾，檢查所 2循序作業的檔案指標（亦即次一作業的預期位置），且計 算出最小偏移量。我們預期這些作業將不會存取在該最小 偏移量之下的檔案區域，這是因爲這些作業是循序作業。 因此’授與|a園伸展到所計算出的最小偏移量或必要範圍 (取較高値）。 我們然法得知一個基於檔案的存取模式而要求位元组範 圍符記之系統内部情形。 此種解決方式可依據檔案存取模式而緩衝儲存各符記。 因而節約了代價很大的符記取得作業，並因而提高了系統 的整體效能。 ' (請先閱讀背面之：ΐ意事項再填寫本頁)

，1T Γ -79- 409215 A7 B7 五、發明説明（77 ) 此種解決方式適用於需要容許檔案的平行寫入共用且需 要循序存取擋案中各相同區域的任何平行構案手统 位元組範圍符記介面 本發明之平行窝人改良使用—種具有—位元組範圍符記 介面之位元组範圍鎖定演算法，而得以管理描述符記的資 訊。利用多個處理器可獨立存取構成構案系統的所有磁碟 (本發明平行檔案,系統時，要求多個處理器於讀取及寫入 :應共用一個標案。爲了起動平行窝入作業，並同時確保 植案的-致性，需要有一個用於各構案區域的鎖定機制。 在-分散式處理環境中’有時要用到符記。該符 節點對：物㈣存取權。然而，-節點可能執行數個程 序且&些私序嘗試存取—檀案的相同g -個對符記之當地鎖定機制D此外，另—節點可能需：存 取相同區域’因而可能嘗試取消該節點之符記；因此，口 ，一當地程序較符記’則不應提出—取消要求。因此: 應將某些種類的鎖定演算法用於這些符記，本發 管理器(TM)即管理這些種類的演算法，而符記管理器： ==國際商業機器股份有限公司的美心 =0¾部中央標準局·_Μ T;消费合作社印裝 爲了存取一檔案中之—區域，— , 的符記，然後鎖定哕符纪ik Γ、八取得適當 哕符允之銷> 古作業，最後則解除對 鎖疋。有幾個與鎖定符記相關聯的問題；在第一 中，無須再度取得兮符# 得付^己。在此種情形 取件…己。在弟二個問題令，必須 L-_______ 一 -80- 409215 A7 B7 i!r:;"'部中^樣泽^κ-τ·消费 At 作社印" 五、發明説明（78 同—節點内的各鎖定不會衝突；在第二個 問题中，必須處 理其他郎點因需要一個與現用節點目前持有的—符記衝突 之符記而發出的取消要求。本發明所提出的鎖定演算法有 效率地解決了這些問題。 ' 本發明之鎖定演算法係以一組API之方式呈現。其中兩 種API係用於對一位元组範圍的鎖定及解除鎖定。第三種 API是一個由符記管理器呼叫的召回函式。符記管理^當 然也提供三種API。第一種API是用來取得—位元組範圍符 記（"Acquire”）。第二種八？1是用來測試是否已在節點上緩 衝儲存一位元組範圍符記（"Test")。第三種Αρϊ係用於回應 一取消要求而放棄一符記（"Relinguish")。爲了識別檔案中 之各存取區域，每一符記包含其可存取的檔案區域之一範 園（起點、終點）。 現在將詳細説明所採用的各符記管理器ΑΡΙ。一取得函 式的形式如下：

Acquire(byte_range) 呼叫該函式而取得一範圍符記。 一取消函式之形式如下： R>evoke(by te一range) 當另一節點需要該符記時，TM即呼叫該函式。 因此，該節點應呼叫：

Relinquish(byte_jange) 本發明所實施的演算法亦基於必須由TM提供的第四種 介面： -81 - 冬紙乐尺度適用中國國家標毕（CNS ) Λ4規格（210X297公t ) I I.^* ' 1 I~~ 訂 {請先聞讀背面之注意事項再填寫本頁) 經漳部中央樣準局后J-消费合作社印¾ A7 B7五、發明説明（79 ) T est(byte_range) 該介面向TM查詢節點上的符記是否存在。 爲了簡化實施方式，各節點並不追蹤所保有的各符記； 而將此項工作留給符記管理器，且各節點將利用測試介面 查詢是否需要取得一符記。於取得一符記時，通常要執行 一些動作。因此，最好是知道是否已保有一符記而可省掉 這些動作。 該演算法係基於一鎖定表（範圍鎖定表（Range Lock Table ;簡稱RLT))，該RLT存有所有現有的鎖定a — mutex 偵測該表，以起動鎖定的自動插入及刪除。三個主要的函 式爲：LOCK，用以鎖定一位元組範圍；UNLOCK，用以解 除一先前被鎖定的範園；以及REVOKE，用以處理一取消 要求。 本發明提供這些介面的虛擬碼如下： LOCK(rang) { retry '· old_revokes=nrev〇kes ； if(not Test(byte_range)){ //the token does not exist of this node acquiTe_mutex ； i_am_fetching=true ： fetch_is_pending=true ； release一mutex ; ___-82-__ 本紙張尺度適用中國®家榡( CNS ) Λ4規格（2[OX 297公釐） (請先E讀背面之注意事項再填寫本f} 訂 K、 4092 A7 B7 五、發明説明（so )

Acquire(byte_range)； get_data_associated_with byte range ； goto retry ； } else{ stolen are 經消部中夾標羋局只工消φ；合作社印1i to revokes //we have the token locally-check that it was not acquire_mutex ； if(old_revokes !=nrevokes) release_mutex ； goto retry ；} // make sure there are nc pending acquires ； if there // make sure they are finished first if (not i_am_fetching) { if (fetch—is_pending) { sleep(); goto retry} }· II if we acquired the token before the Test, we need // release other threads, we hold the mutex, so no 83 - 本纸張尺度適用中國國家標準（CNS ) Λ4規格（210X 297公釐） (請先M讀背面之注意事項再填寫本頁) ^ 117 409:^5 A7 好濟部中吹樘準局β,τ.消许合作社印說 B7 五、發明説明（81 ) // can interfere here if (i_am_fetching) { i_am_fetching=false ; fetch_is_pending=false ； wakeup()；}} err=insert_range_into_lock_table ； if (err==E_CONELICT) { sleep( ) ； //wait for someone to release the lock goto retry ;} exit if (i_am_fetching) { fetch_is_pending=fa!se ' i_am_fetching=false ；} release—mutex ;} UNLOCK(range){ acquire_mutex ; delete_range_from_lock_table i wakeup ; -84- ---------^------IT------ (讀先閱讀背面之注意事^再填寫本頁) 本紙張尺度適用中國园家標準（CNS ) Λ4说格（21〇Χ 297公釐） 409215 A7 B7 五、發明説明（82 release mutex ： REVOKE(range){ retry acquire mutex ； err=insert_range_into_lock_table if (err==E_CONELICT) { sleep()； goto retry ：} nrevokes++ ； release_mutex ； put_data_associated_with_byte—range Relinquish (range); acquire_mutex ； delete_range_from」〇ck一table ; wakeup ; release mutex ; 至此已説明了 一種位元組範圍鎖定。雖然我們無法得知 位元组範圍鎖定的任何演算法，但是我們注意到先前對非 位元组範圍鎖定的解決方式會在符記管理器之外保存—份 -85- 本纸狀度4用巾§1财轉（CNS ) M娜（21()>< 297公楚 (請先閲讀背面之注意事項再填艿本頁) ^ 訂 ^ A7 五、發明説明（83 ) 符記狀態》 此處’請注意本發明的分散式符記管理器將若干介面 (Acquire、Revoke、Relinguish、及 Test)提供給範圍（亦即一 檔案的位元組範圍）之鎖定。可在共用讀取模式或互斥寫 入模式中要求—特定範圍。 本發明的一項特徵在於：符記管理器檢查對一指定位元 組範圍的符記要求，並將該要求與整個多節點系統中現有 的各衝突範圍比較，並授與一個無須另—電腦的符記取消 之珉大可能位元組範圍。此種方式將減少在要求節點上的 ^入作業心出另一符記要求的機率。利用計數器及非阻隔 鎖定呼叫以取得符記，並同時保有其他的鎖定。此種技術 可在單一節點内更有效率地循序進行多個要求，而得以進 行所需的多個節點循序存取a 根據本發明，符記管理器的Acquire介面以一個模式以及 兩個範圍（一"必要"範圍及一"希望"範圍作爲輸入。希望 範圍必須是必要範圍的一超集合。對一個呼叫Acqnre介面 的應用％式保證：至少將必要範圍授與該應用程式。符記 管理器知決定是否已將任何衝突範圍（亦即在—衝突模式 中與必要範圍衝突的各範圍）授與其他節點。如果找到任 何衝突範圍’則符記管理器將要求具有—衝突範圍的每— 節點將重疊的範圍降等到一非衝突模式。 又根據本發明，在解決了與必要範圍的任何衝突之後， Acquire介面將決定完全涵蓋必要範圍的—個最大相接範 圍’該範圍也是希望範圍的一個予集；該範圍也是 -86- 本紙張尺度適用中國國家標準（CNS ) Λ4規格ΠΙΟΧ297公釐） (锖先閲讀背而之注意事項再填寫本頁)

-1T 經湞部中央樣準局只工消费合作社印？水 409215 A7 --- --B7 五、發明説明（84 )

Acquire介面將送回給呼叫應用程式的範圍。事實上，符 °己ί理赛將授與無須執行額外的取消處理之最大可能範園 (但受希望範圍參數之限制）。 付記管理器之Revoke介面係用來將與另—節點的一衝突 範園要求相關之資訊傳送到一應用程式。當一八叫以代要 求偵測到已授與其他節點的衝突範圍時，將要求在每—衝 突節點上執行的應用程式將已授與的範園降等。經由 Revoke介面而傳送的資訊包含模式、及在Acquire呼叫中指 定的必要範圍/希望範圍。 一應用程式接收到一取消要求時，將呼叫尺化吨“比介 面’將已授與該應用程式的任何衝突範圍降等到一非衝突 模式。可要求該應用程式將與"必要"範固衝突的任何範 圍降等到一個最小的非衝突模式，但是亦可降等到該應用 程式想要的一個較大範圍。 付冗管理器亦提供一 Test介面，該介面將決定是否已將 —特定範圍授與當地的節點。一應用程式可利用該丁est介 面以決定對一特定範固的—Acquire要求是否將向符記词 服器節點提出一通訊要求。 利用一特定位元組範園的一些循序數字而處理時，將可 正確地在相同的位元组範園上處理取得及取消。符記管理 器的Acquire介面將一循序數字作爲一引數。對於每一符 έ己而g ’符|己管理器爲已被授與一範圍的每—節點維護— 循序數字。於一 Acquire作業結束時，符記管理器利用 Acquire介面中指定的値更新包含一節點循序數字之糊 _______________-87- 本紙张尺度適Λ]中國囤家標準（CNS ) Λ4規格（2I0X 297公漦） (請先聞讀背面之注意事項再填寫本頁) T -* 五、發明説明（ 85 A7 B7 經浸部中决標卑局負工消资合作社印製 位。當一後續的Acquire作業必須取消各衝突節點的範圍 時，符記管理器將自該節點經由符記管理器Rev〇ke介面傳 送上次成功取得之循序數字β 考慮到分散式符記管理器的各介面（Acquire、Rev〇ke、 Relmguish、及Test)，本發明提供了 一種在所用的程式碼 中實施當地位元組範圍鎖定之改良式方法。這些程式方法 或演算法簡潔地解決了數種潛在的複雜性，並提供了—些 將於下文中説明的精緻特徵。 ，，本發明利用將於下文中配合原創揭露事項中之虛擬碼而 說明（鎖定技術，以平行方式處理多個符記取得及取消作 業。本發明容許以平行方式處理數個符記取得作業。例 如，如果數個檔案系統作業嘗試以平行方式存取一檔案的 不同區域時，即可發生上述的情形。 本發明也容許對一樓案的—部分之符記取消作業 得作業同時發生，只要這兩個作業不會衝突即可。 我們當了解，本發明並不f要在位元组範園鎖定 内保存一份當地符記狀態。 … 若在取得一符記之後但在鎖定該符記之前，另 消了該符記，貝.】此種情形被稱爲㈣⑽，本發明消除 此種livelock的情形。另一節點取得 -、 兮& h、义 付"己’但在鎖定 Π ’該符記又被借用。此種交替效應停止進行。 -份當地符記狀態，所以將減少本發明存 求，因爲該資訊業已儲存在㈣中。如果業已 請 先 閱 讀 背 之 注 意 事 項 再 ▲ 寫 本 頁 訂 -88 - 本紙烺纽適财關 ^$4*- ( CNsTa^# ( 210Χ 297^Ϊ Α7 Β7 五、發明説日S ( 86 ) 記’則一 API將查詢TM以尋找符記。在鎖定位元組範圍之 後，提供一特殊機制，以便確定在測試過符記的存在但在 鎖定該符記之前不會發生取消作業。但是有可能在取得與 鎖定之前取消該符記，在此種情形中，將再度取得該符記 並嘗試鎖定。 取消召回函式也使用檔案系統作業所使用的同一位元组 fe圍鎖足程式碼。然而’將有—個特殊的旗標指示這是一 個用於取消的鎖定》此種方式使該程式碼的長度更爲缩 短’而得以使用相同的鎖定表。 鎖疋一位元组範圍的API支援可增強其作業的各選項： 非阻隔、當地鎖定、測試、及循序。非阻隔選項可容許一 非阻隔作業；如果各節點並沒有符記，或一衝突鎖定已被 持有，則鎖定程式碼立即送回—個適當的送回碼β 當地鎖定選項可容許一個非分散式作業；如果我們不需 要整體性的鎖定，只需要在節點内的鎖定，則可使用該選 項。 測試選項可檢查是否可鎖定位元組範圍但不實際鎖定。 循序選頁可提示我們鎖定了 —位元組範圍，以供讀取 (或寫入）一個循序存取的檔案。如果需要一符記，則使用 該提示。在此種情”，希望（但不是必須）有-個大於時 序需要的符記之符記。 本發明作了特殊的準備，以便追縱各執行緒（thread)所持 有的各種鎖定。—除錯公用程式傾出現有的位元組範圍鎖 足、及持有這些鎖定的執行緒编號。此外，也保存統計數 ---—~一 __ ' 89 - 本紙狀舰 1 t ‘ .17------ir. I (請先閲讀背面之注意事項再填荇本頁) 409215 A7 B7 五v發明説明（87 ) 經肩部中夹標枣局^:工消玢合作社印絮 字，以便了解檔案存取模式、及鎖定行爲。 藉由送回每—成功鎖定作業的一檔案代碼伽 解除歧《快速進行，且並不需要_搜#或查詢作業使 由於保存了各現有鎖定模式的計數器，所以檢查 鎖定是否存在的作業是快速的。例如，如果我們保存現= 共用讀取鎖定及現用互斥寫入鎖定數目的—計數器 經常了解範圍的重4情形n如果並無互斥窝入 定’且我們需要—共用讀取歧，則我們知道此時並無衝 突’且我們只需要在鎖定表中找到叫固空的儲存區即可。 鎖定程式碼支援τ、限㈣目的a a組範圍鎖定要求 鎖定表已滿的情形中’或在要求—衝突鎖定的情形中1 要求該鎖定的執行緒$於睡眠狀態’並在解除_鎖定 該執行緒唤醒。 本發明之解決方式並不複製符記資訊，因而使用較小 儲存2間且具有效率。 在二符記管理器瑗嫱中夕向痏 由於多個處理器隨時讀取及寫入檔案系統的各部分， 以平行檔案系統是相當複雜的。我們可能想知道當此環現 中的某一部分故障時將會發生何事。本發明提供了此環境 中t回復機制。第一種回復機制係有關於當一節點故障時 正在更新中介資料之處理情形。現在將説明一種與回復符 記狀態、重新執行中介資料登綠及固定作業順序有關的 術0 平行標案系統之回復模型 在 將 所 境 技 {請先閱讀背面之注意事項再填寫本頁} .1-.. -90- 本紙张尺度適用中國國家標4M CNS ) Λ4規格（210X297公釐） B7 五、發明说明（88 本發明之回復模型適用於本發明之共用磁案 各磁碟係經由多個磁碟境線（例如㈣或 ^平 式的網路連㈣存裝“連接。每—處理M = = = Γ散式鎖定管理器而維持資料7中介資料 的-致性。每-處理器獨立登錄各中介資料 : 在故障時不需要用到檔案系统掃描。 因而 困難的問題在於各處理器（不論是硬體或軟體）。這 障的形式可爲嚴㈣實際燒燦處理器、或失掉參*_技 理協定的通訊能力。發生這些故障時，故障的處理器可： 持有可讓其修改共用磁磲的某些區域之鎖定β依照鎖定= 理的拓撲情形，甚至可能要取得額外的鎖定 ： 理器最後將知道其狀況，但是外部無法得知執行的時間處 因爲這將取決於故障處理器中出現的狀況。 本發明之目的在於讓所有並未故障的處理器利用共用磁 碟文全地執行作業，且也讓故障的處理器於可回到—已知 狀態時即提供使用應用程式的支援。 本發明之回復模式實施下列觀念： 赶滅部中*樣準局；〇<工消费合作社印 _ 組監視服務程式（類似於Phoenix group的服務程 式），用以監視所有處理器上的程序，並偵測處理器 及通訊的故障。由參與"程序群"提供該服務程式， 當一成員程序故障或一新的程序想要參與—程序群 時即和此訊息通知該程式群的所有成員程序。於 啓動時，各處理器必須參與各〃程序群"。 -分散式鎖定。經由分散式鎖定而協調各群成員程 本躲尺度適用中_轉準（CNS) Λ4%格（21GX 297讀） 經滅部中夾標準灼货工消资含作社印絮 ^ ^00215 4092^5 —]「_ —. 厂_ — . . ——— - _ 五、發明説明（89 ) 間之所有磁碟存取： -一成員程序在讀取或改變一共用磁碟中的—特定 部分之資料/中介資料之前，必須取得鎖定。 -一程序群的成員程序是一鎖定協調者；該鎖定協 調者知道可將哪些鎖定保存在哪一節點上。 -法定成員程序數（quorum)。於啓動時，且於發生通訊 故障時，可能形成一個以上的程序群。此時可能導 致不同程序群中之鎖定協調者作出衝突的鎖定決 定。爲避免此一情形’如果可存取磁碟的處理器中 之半數以下是，，程序群"中之成員程序，則將不容許 任何檔案系統作業。 -登錄（logging)。登綠一故障後可能造成資訊不—致的 所有資料/中介資料更新。每一處理器有其本身的登 錄’但是並不將這些登錄儲存在共用磁碟中，因而 在發生故障時所有的節點都可擷取這些登錄。 -隔離（fencing)。必須擁有不使一特定處理器存取一特 定磁碟之能力。 -關卡（barriers)。因爲各回復步驟原本即是循序進行， 且需要在所有節點上執行某些回復步驟，所以利用 關卡以確保在任何節點執行次一步驟之前必須先在 所有節點上完成前一步驟。 本發明的回復模型可在不利用硬體鎖定機制的情形下處 理節點的故障。檔案系統的每—檔案實例只有在其可成爲 —程序群"的一現有成員程序時，才可作業。當偵測到 _________-92- 本紙張尺度適用中國ϋ標準（CNS ) Λ4規格 (諳先閲讀背面之注意事項再填寫本頁) ο%- 丁 、-& r 好湞部中央楛窣局；^工消赀合作ii印*0表 A7 —--——------ B7 五、發明説明（9〇 ) '-— 處理器的故障，且該故障的表現形式爲—實際的處理器 故障或無法順利通訊時，程序群的監視服務程式將通知所 有其餘的％序群成員程序。利用未故障的程序群成員程序 門之關卡同步協定執行將於下文所述的各回復步驟，即 :執行故障處理器的回復。因爲是在一個處理器上執行某 —回復步驟，所以選出一個檔案系統協調處理器 列這些步驟。 术執行下 -所有未故障處理器停止與該故障處理器間之通訊。 檔案系統協調處理器隔離故障的處理器。此時將使 磁碟子系統停止接受該故障處理器的磁碟存取要 求。縱然尚未偵測到該故障處理器有通訊上的故 障’也將禁止該故障處理器存取共用磁碟。 -次―。關卡是在必要時回復鎖定狀態。㈣系統協調 處理器通知該鎖定協調者。該鎖定協調者暫停該故 障處理器於發生故障時所持有的授與鎖定。此種方 式使其他節點不會存取該故障節點可能留在一個不 一致狀態之資料。如果故障處理器原來是鎖定協調 者則替代的鎖定協賙者自未故障的處理器收集 緩衝儲存的鎖定狀態資訊，而計算新的鎖定狀態。 如果此一階段不是必要的，則可在未故障的節點上 重新開始暫停鎖定未涵蓋的資料之正常檔案系統 業。 -第三個關卡是檔案系統協調處理器重新進行該故障 節點的登綠。在知道故障處理器與各磁碟隔離，且 -93- 本紙浪尺ϋδ射關家標準（〇VS ) Λ视格（210X 297^*^7 其衣 訂r (請先閲讀背面之注意事項再填寫本頁) 409· B7 五、發明説明（91 未故障的處理器將不會授與被阻隔的鎖定時，才執 重新進行=> 在完成此步驟時，磁碟上的資料將 疋一致的，且可釋出各鎖定。解除該關卡意指完成 了成功的回復，且可方袖女+ A . 所有未故障的處理器上重新 進行正常的作業。 處理於回復過程中偵測到的處理器故障時，係自第 步驟重新開始。以不超出原先故障程度的方式執 行個別回復步驟，因而在完成回復協定之前，如果 執行多次的個別回復步驟，也不會有壞處，不會有 額外的故障。 、上述這些回復步職明了—個擒案系统的时，但如果 —:了自以上的檔案系統，則對所有的檔案系統造行每 —步驟中所有的回復動作。 二於處理〜點回復而s，故障處理器在許可時將儘速嘗 ^重新加人程序群。如果故障回復仍在進行中，則無法加 二序群直到完成故障回復協定爲丨。有兩種可能 丄t故障節點可加入一個現有的程序群，亦可加入 —個等待凑齊法定成員程序數的程序群。如果該故障節點 口入-個寺待凑齊法定成員程序數的程序群，則杏—法定 數凑齊時(此時知道不會有衝突的鎖定)：將重新 撤：：過該故障節點加入-個現有的程序群，則將 撤销對Μ點的隔離，且容許正常㈣案系統作業。 第：：回復特徵處理回復的交叉及中介資科節點的需 〆。中介資料節點維護需要在-故障中保留的各狀態。 ______ - 94- 本紙張尺料; I , ^ I— (請先閲讀背面之注意事項再填寫本頁) 訂 "丨 -"』部中"榡"局兵丁：消贽合作杜印" A7 A7 -碎部中失樣芈局荬工消费合作社印^ B7 五、發明説明（92 ) 也介資料節點的同步及非同步拉管 本發明之平行檔案系統工作時，構成檔案系統的所有磁 碟係分佈在一個諸如tcp/ip網路的網路上，或分佈在可讓 多個處理器以如同大量平行系統或叢集之方式互動的一交 換機上，因而多個處理器需要存取且可獨立存取—檔案。 爲了利用此種能力，多個處理器應在讀取及窝入時共用— 樓案。 在一分散式檔案中各檔案的窝入共用造成幾個問題。其 中一個問題是本發明所提供中介資料之存取及更新。本發 明之中介資料節點是一種用來控制—分散式檔案系統中的 中介資料之機構。存取-構案的每—節點需要讀取或寫入 中介資料資訊到中介資料節點（或中介節點）。 中介資料節點保存與標案的中介資料㈣的資訊，並作 ^磁碟與存取樓案的所有節點間之—智慧型緩衝儲存裝 二。也會發生中介資料節點(或中介節點)停止服務該功能 $之情況。爲了能得到平順的作業及回復，必須處理這此 :::二時係以直接的方式從以往都存取該中介節點的各 即點中返出一個新的中介節點。 我們特.此説明可能處理—中介節點接f 起動一接管而選擇之方法。 及為了 =種：：下會發生—中介節點停止執行中介 =二=兩種㈣是非同步的，亦即其他節點無法立 P侍知此種h形。第三種情形是 得知有接管的情形。 π即所有郎點都 i__ 05 ^^適用中 {請先閱讀背面之注意事項再填寫本頁)

起"·部中夾標準局工消处合作社印製 -96 40921^7 —B7 五、發明説明（93 ) ~ 1 ·中介節點故障（損毁）； 2.中介節點關閉稽案，< 自其緩衝错存區中清除該樓 案； 3-另一節點希望成爲中介節點。 在所有這些情料，我Μ需要保證發生一丨可靠的接 管。在非同步作業中，嘗試存取舊中介節點的第一節點傾 測到-個錯誤；該中介節點可能故障，在此種情形中將得 到—個通訊錯誤；或者舊中介節點決定不再作中介節點， 在此種情形中該節點自舊中介節點得到—個適當的錯誤訊 息。在兩種情形中，該節點向丁“要求適當的符記，而嘗 試成爲一中介節點。如果没有其他的中介節點（若該節點 是=一個存取舊中介節點的節點即爲此種情形），則該節 =將成爲新的中介節，點。隨後嘗試存取舊中介節點的其他 節點亦將經過相同的過程，但是將無法取得適當的符記。 向符°己s理益查詢時，將透露新的中介節點。因此，每— 即點最後將發現其已變成新的中介節點，或中介節點已鲈 改變了。不論在哪—種情形，都將採取適當的動作。如果 ^即點變成一中介節點，則該節點自磁碟讀取最新的中介 資料。如果一節點的中介節點已改變，則該節點將其自2 的申介資料更新重新傳送到新的中介節點，這是因爲舊， 中介節點有可能在將這些更新清除到磁碟之前即已故障的 由於利用每一個此類更新的一版本编號，所以 道哪些更新是在磁碟中以及必須將哪些更新重新傳、： 的中介節點。 运到新 本紙狀度@削，:縣（eNs )以規格 (210X297公釐 1丨 "裝--------訂--I----f (請先閱讀背面之注意事項再填寫本頁) 經"部中次標卑局吳工消贽合作社印製 A7 B7五、發明説明（94 ) 因爲一個節點在嘗試成爲一中介節點時可能會失敗，所 以涉及存取中介節點的每一作業具有下列的大綱： --表 7- retry : if (I am metanode) then DO this and theat else { errl=send_message_to_the_metanode ； //so the metanode will do // "this_and_that" if (ot1=METAN0DE_IS_DEAD | |end=METANODE_NOT_ANY_MORE){ err2=try_to_becom_metanode ； if (err2==0K) then//we became the metanode read_metadata_from_disk(and other stuff to do when becoming a metanode) else // someone else became the metanode // find_out_the_new_metanode, and_send_it_information_theat_is not yet on disk // metanode has changed ； in both cases, retry the origina // operation } goto retry * } ----END TABLE- 上述用於動態接管中介節點的系統是獨有的，且本發明 ______-97-_ 本紙張尺度適用中阖因家榡準（CNS ) A4規格（2丨0.X297公f ) (請先閲讀背面之注意事項再填寫本頁) -?τ ·"t - 經-欢部中次標if-局貨工消费合作社印製 409^15 a7 ------------B7五、發明説明（95 ) ~ ~ 的特定解決方式之優點在於：此種方式將-個有其他用途 (符記管理器）的子系統用於依據檔案活動性而選擇—個新 的中介節點。因爲所有的作業都涉及一個故有的，，重新嘗 試”機制，且因爲每—節點都可作爲一中介節點，所以^ 咒將選出一個中介節點，因而可保證終究將動態地發生— 次接管》 保存在每—節點的資訊保證：縱使一中介節點故障，回 復程序將重建所有的資訊，而能得到檔案内容的一致性。 配額的分< 然後將説明本發明在該共用磁碟檔案系統中對配額分配 万面的改良。基本的困難點在於必須嚴格維護一组節點的 配額。大家可能想到在一中央伺服器中維護這些配額，但 是我們發現這不是一種可行的解決方式，因爲當每—新的 資料寫入在寫入資料之前需要先向該單一伺服器要求許可 時点中央伺服器將變成一個瓶頸。此處將説明本發明將 配額分配給代表一配額持有的使用者而正在窝入一檔案系 統的各電腦之方法。隨後將論及在發生故障時回復此種配 額之方式。 在一平行檔案系統中，其中多個處理器可獨立存取構成 檔案系統的所有磁碟，以便讀取及窝入各磁碟上的檔案， 此時必須將一磁碟的若干磁區指定給產生檔案的每—處理 器之標案°分配給一特定使用者擁有的棺案之磁區受限於 配额’為配額指定容許該使用者或一群使用者使用的磁 碟2間谷量。其問題在於‘各使用者可能正在多個處理器 (靖先閲讀背面之注意事項再填焉本頁) -------- % -訂 S.--—. -98- 本纸依尺度通用中國國家標窣（CNS ) Λ4現格（2!〇><297公 經，¾部屮決榡準扃妇工消贽合作社印褽 4〇92i5A7 _____ Β7 五、發明説明（96 ) 上同時執行，且索取同一配額。若在中央分配新的磁碟區 段時’將使本發明的大量平行處理系統之使用慢下來。 本發明實施了 一種系統，該系統將配額分配給每一節 點’並根據需要而重新分配配額，且於發生故障時回復該 配額。本發明之解決方式是在—大量平行電腦運算環境或 本文所述的多個電腦之其他環境中，提供一種管理每一樓 案系統的檀案索引及磁碟區段配額之方法。將此工作分給 每一檔案系統的一配額伺服器、及每一檔案系統中正操作 該檔案系統内資料的每一節點之一配額用户端電腦。 配額限度是一臨界値’在此臨界値之下可將檔案索引及 樓案系統空間分配給一使用者。在本文中，將一使用者可 以擁有的的檔案索引數及空間容量稱爲配額。當地分配額 是一配額用户端電腦無須與配額伺服器互動即可代表使用 者分配的空間容量。 該伺服器維護一常駐磁確的標案，該樓案包含整個MPP 系統中所有使用者的配額限度及累積使用量。只有該飼服 器可存取該檔案，該伺服器爲所有的處理器執行該檔案的 所有讀取及更新。因此’只有該伺服器可完全知道各配額 的使用量及仍然可使用的分配量。 在配額伺服器上執行與整體配額管理有關的所有行動。 限度改變、分配當地分配額' 及顯示現行狀態等情形都需 要與配額伺服器互動。配額用户端電腦在其當地分配額容 許的範圍内改變構案系統的分配量，並根據其分配額的使 用量而定期更新伺服器。該伺服器可取消一用户的分配 _______- 99 - 本纸張尺度適用中國國家^準（CNS ) Α4規格（210X297公茇） Α^- * .ITn Ϊ ' — (請先閲讀背面之注意事項再填寫本頁) A7 _B7____ 五、發明説明（97 ) 額，以滿足另一用户的分配額要求。 配额用户端電腦開始時具有零的當地分配額。只有在處 理器上的一應用程式嘗試產生新的檔案系統資料時，才爲 該使用者要求一當地分配額。只有在該用户端程式接收到 一個適當的當地分配額時，才能滿足該應用程式的要求； 否則將無法接受該應用程式的要求。該配額用户端電腦维 護一個包含當地分配額及使用掉多少的該分配額之記錄a 釋出磁碟空間的各應用程式將增加該使用者的當地分配 額。該配額用户端電腦將就其使用量而定期更新配額词服 器，並將根據應用程式的使用模式而釋出過量的配額。 只要配額伺服器仍有可用的配額，該配額伺服器將送出 當地分配額，亦即不會超過系統的整體配額限度。如果已 提供所有的配額限度作爲當地分配額，配額伺服器將取消 一些當地分配額，以滿足新的要求。取消部分的當地分配 額’讓用户端程式繼續使用剩餘的分配額，即可執行上述 程序。這些要求愈來愈強烈地取消較大部分的當地分配 額，直到不再有可用的配額可滿足這些要求爲止，此時將 拒絕應用程式的要求。 該方法的困難處在於必須設想到用户端電腦及伺服器的 故障。用户端電腦故障時可能有部分使用的當地分配額， 而伺服器可能與一用户端電腦同時發生故障。使用者永遠 不得超過所分配的配額，且亦預期能取得空間容量。此時 需要使用配額分配的"不確定"方法。每當配額伺服器分 配一當地分配額時，即將一個形式爲”不確定値”的當地 -100- 本紙張尺度通用中家標孪（CNS )八4規格（2!0^ 297公釐） (請先聞讀背面之i£意事項再填寫本頁}

11T 409215 A7 B7 .¾¾.部屮次摞準历只工消拎合作社印？木 五、發明説明（98 ) 分配額總和記錄存放在可回復的磁碟上。該記綠代表伺服 器沒有正確資訊的配額空間容量。不得重新分配不確定的 空間’因而不會有一使用者超過其限度的危險。用户端電 腦的當地分配額使用量之定期訊息更新這些不確定値。該 $間自不確定狀態移到被使用狀態。也自不確定値中扣除 一用户端電腦所放棄的空間。一使用者可使用的總分配量 等於該使用者的分配量減.掉已知用掉的分配量再減掉不確 定的分配量。不確定値的所有修改都被強制立即傳送到磁 碟，以處理回復作業。 如果一用户端電腦故障，則一使用者無法使用不確定的 儲存容量，直到執行一個確認該使用者的實際儲存使用量 之"配額檢查"公用程式爲止。某些部分的不確定値代表 使用者的實際使用量；但某些部分則代表暫時喪失的潛在 使用量。分配分配額的演算法對用户端電腦上新磁碟儲存 裝置的使用量相當敏感，並爲了效能的表現而嘗試提供用 户端電腦其即將用到的使用量，但爲了回復作業而限制過 度的當地分配額。該方法可就使用者配額中並非不確定的 部分繼續使用者的作業’直到執行配額檢查公用程式爲 止。遠方法亦可爲了效能的表現而容許平行分配磁碟區 段。 當配額词服器故障時，將選擇一個新的配額伺服器。將 不會有尚未寫入磁碟的任何資訊。新的配額伺服器將取消 所有的當地分配額，並根據回覆而更新不確定値，因而產 生該資訊。請注意，用户端電腦故障及伺服器故障同時發 -101 - 本、紙张尺度適用中國因家標準（CNS ) Λ4規格（公釐〉 (锖先閱讀背面之注意事項再填寫本頁)

•IT 409215 at 五、發明説明（99 ) ' 生時，將造成在執行配額檢查公用程式之前的磁碟區段内 容喪失。本演算法可在一故障之後迅速針對非不確定分配 量正確地執行配額強化。 我們不知道有任何對一平行系統的所有節點獨立分配磁 碟區段的平行檔案系統。亦即，使用者在嘗試網路連接式 儲存系統之前’將不會碰到此種問題。 本發明爲了效能的表現而以平行方式分配儲存容量。任 何分配伺服器的解決方式都會碰到瓶頸及回復的問題。本 發明必須設立配額，因爲使用者想要在整個平行處理系統 上控制磁碟儲存裝置的使用量。本發明之解決方式容許平 行分配，並不強制繼續鎖定一個將是緩慢的整體性配額， 並可以即時方式回復處理上的故障β 任何使用磁碟連接的共用磁碟模型之平行處理系統都可 利用本發明所開發的方法。 芎復當地分配額以供平行處理中之配額管理 本節中將説明在此環境中本發明的配額檢查公用程式之 作業。配額檢查的功能類似於在—Unix作業環境中發生故 障後用於修復配額檔案的一標準公用程式Qu〇taehk，但是 Quotachk無法如本發明所述在共用配額的多個節點中執 行。本發明開發之方式可執行一 "Qu〇tachk"，而無須關閉 存取資料的所有電腦。 本希中將説明一種公用程式/方法，用以在一故障之後 回復這些不知已被使用/已被分配或仍可使用的分配額。 該公用程式工作時不會讓使用者在分配或收回檔案系統中 -102-

本紙張反度適W中國®家標隼（CNS—) Λ4規格（2!0X (請先閱讀背面之：ix意事項再填寫本頁) A衣 經".部中"標苹局ρ、-τ·-'-ίϊ!资合作社印欠 A7 ---____B7 五、發明説明（1〇〇 ) 之磁碟空間時產生混亂。 爲了管理一大量平行電腦運算環境中每一檔案系統的擋 案索引及磁碟區段配額，將此工作分給每一檔案系統的— 配額伺服器、及每一檔案系統中正在操作每一檔案系統的 每一節點之一配額用户端電腦。 配額限度是一臨界値，在此臨界値之下可將檔案索引及 檔案系統空間分配給一使用者。在本文中，將—使用者可 以擁有的的檔案索引數及空間容量稱爲配額。當地分配額 是一配額用户端電腦無須與配額伺服器互動即可代表使用 者分配的空問容量。 該飼服器維護一常駐磁碟的檔案，該檔案包含整個MPP 系統中所有使用者的配額限度、累積使用量 '及"不確定 値"。”不確定値"代表伺服器並無正確相關資訊的配額空 間量。重新分配不確定的空間時，可能造成—使用者超過 其限度的危險。某些部分的不確定値代表使用者的實際使 用量；但某些部分則代表暫時喪失的潛在使用量。 本發明所述之解決方式是一種自"不確定値"中回復當地 分配額的方法，因而能夠再度使用這些未使用的或暫時喪 失的配額。此種機制（後文中稱爲配額檢查）對一現用檔案 系統工作，而不會混亂磁碟空間及檔案索引的分配及收回 分配。 配額檢查在配額伺服器中產生所有配額記錄的一份對映 拷貝，並累積在檔案索引資訊中找到的配額使用量。雖然 配額檢查係掃描各檔案索引，但是分配及收回分配的所有 -103- 本紙張尺度適川中国园家標準（CiNS ) Λ4規格（210X297公t ) (請先閏讀背面之注意事項再填寫本頁)

A

,1T 409215 A7 ------------- --------B7_____ 五、發明説明（101) 改變係記綠在原始的配額記錄及配額伺服器的對映記錄 中。必須分別處理在現行配額檢查位置（亦即現行讀取樓 案索引）之前及之後的配額使用量更新。在原始配額記錄 及對映記錄中更新在現行配額檢查位置之後（已檢查的樓 案索引）的分配改變；只在原始配額記錄中更新在現行配 額檢查位置之前（尚未檢查的檔案索引）的分配改變。同樣 更新兩個記錄中之"不確定値"，因而在配额檢查結束後 配額用户端電腦上的當地分配額總和是正確的。 將現行配額檢查位置通知各配額用户端電腦，因而這些 配頦用户端電腦可在對映登錄中收集在各別現行配額檢查 位置之後的所有已分配或收回分配的這些配額。當配額檢 查結束對各樓案索引的掃描且開始合併原始及對映的配額 登錄時，各配額用户端電腦將其所收集的對映配額記錄之 改變傳送到配額伺服器。 在產生所有對映記錄且自各用户端電腦取消所有的當地 分配額之後，但在配額檢查開始掃描檔案索引以取得配額 使用量資訊之前（亦即’對映"不確定値”開始時爲零，且 正规的”不確定値"顯示喪失的配額），同時更新對映記錄 的"不確定"値及伺服器上原始配额記綠的，'不確定'，値。 當在配額檢查結束時合併對映及正規配額記錄時，將對映 記錄的"不確定"値拷貝到正規的配額記錄中。 我們不知道有任何對一平行系統的所有節點獨立分配磁 碟區段的平行摇案系統。亦即，使用者在嘗試網路連接式 儲存系統之前，將不會碰到此種問題。 ___- 104- { CNS } AWT2iOX：97^t ) (諳先閱讀背面之注意事項再填寫本頁) 丁 '-° A7 B7 五 '發明説明（1〇2) 本發明爲了效能的表現而以平行方式分配儲存容量，並 避免了單一伺服器的解決方式會碰到瓶頸及回復的問題。 本發明必須設立配額，因爲使用者想要在整個平行處理系 統上控制磁碟儲存裝置_的使用量。本發明之解決方式容許 平行为配，並不強制繼續鎖定一個將是緩慢的整體性配 額，並可以即時方式回復處理上的故障。 雖然至此已説明了本發明之較佳實施例，但是熟悉本門 技術者當可了肖’不論在目前或在未來，在下文申請專利 範圍的範圍内仍可作出各種改良及強化。這些申請專利範 圍應對首度揭示的本發明提供適當的保護。一 (請先閱讀背面之注意事項再填寫本頁) 裝 r anir·:部t次標準扃資工消fr合作社印^ -105- 本紙狀賴财酬家縣（

Claims (1)

1. 40921δ8 Βδ CB D8 經濟部中央榡準局貝工消费合作社印製 申請專利範圍 r :種料-系統之方法，㈣統採Κ目料 之檔案系統，並具有一個包含中介資_ ' .Λ. 丨貧科·^檔案結構，該 系說設有存取該檔案系統的若干分 .,χ 丁刀散式通訊電腦節點， 孩万法包含下列步驟： .將一常駐在一個或多個磁碟的檔案結構提供給一檔案系 統’在各別電腦節點上執行的多個檔案系統可存取該等 磁碟，該檔案系統可讓一個使用檔案結構的—計算2作 分成多個部分，且可在各別的該等電腦節點上以平行方 式執行這些部分；以及 將一機制提供給該檔案結構的每—檔案之—中介資料節 點，以便控制一分散式檔案系統中之中介資料’其中可 服務存取一檔案且需要將中介資料資訊讀取或寫入到中 介資料節點的每一節點。 2. 如申請專利範圍第i項之方法，其中一系統係採用—個如 申請專利範圍第1項之檔案系統，其中該中介資料節點保 存與檔案的中介資料有關之資訊，且係作爲磁碟與存取 檔案的所有節點間之一智慧型缓衝儲存區^ 3. 如申請專利範園第2項之方法，其中—系統係採用—個如 申請專利範圍第2項之檔案系統，其中在該中介資料節點 停止作爲一中介資料節點的服務之情形中，於轉變而能 夠得到平順的作業及回復之過程中，必須處理這些情 形’且進行其中包括動態接管的回復作業。 4. 如申請專利範圍第3項之方法，其中一系統係採用—個如 申請專利範圍第3項之檔案系統，其中在三種情形下會發 106 本紙張尺度適用中园國家榡準（CNS ) Λ4現格（210 X 297公釐） (請先閲讀背面之注意事項再填寫本瓦) 裝. -II 8 8 8 8 ABCD 經濟部中央標準局—工消費合作杜印製 六、申請專利範圍 生-中介節點停止執行中介節點應有的作業；有兩種情 形是非同步的’且於一中介節點故障，或於一中介節點 關閉檔案或將該檔案自其緩衝儲存區清除時，其他節點 無法立即得知這些情形，而第三種情形是❹的，且於 另-節點需要變成該檔案的中介節點時，所有節點都得 知有接管的情形。 5·如申請專利範圍第4項之方法，其中_系統係採用—個如 申請專利範園第4項之檔案系統，其中在非同步作業中， 當-舊中介節點故障時，嘗試存取該舊中介節點的第一 節·點偵測到一個錯誤，在此種情形中將得到—個通訊錯 誤’或者舊中介節點決定不再作中介節點，在此種情形 中該節點自舊中介節點得到一個適當的錯誤訊息，然後 在這兩種非同步作業中停止使該節點成爲一中介節點， 並向一符记f理器要求一個用於存取檔案的適當符記。 6, 如申請專利範圍第5項之方法’其中一系統係採用—個如 申請專利範圍第5項之樓案系統’其中當該符記管理器自 —個想要變成一中介節點的節點接收到一個對一適當符 I己t要求時，如果沒有其他的中介節點，則提出要求的 該節點將成爲新的中介節點，且隨後嘗試存取舊中介節 點的其他節點亦將經過相同的過程，但是將無法取得— 適當的符記，且向符記管理器查詢時，將透露該新的中 介節點。 7. 如申請專利範園第6項之方法，其中—系統係採用—個如 申請專利範圍第6項之檔案系統，其中當一中介節點改辯 -107 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） ---------裝------,玎------# (請先閲讀背面之注意事項再填寫本頁) 409215 申請專利範圍 時’該樓案系統的每-電腦節點終將知道該節黏已變成 新的中介節點，或中介節點己經改變了。 8. ^請專利範圍第6項之方法，其中—系統係採用一個如 申凊士利範圍第6項之檔案系統，其中如果_節點變成一 中介即點，則孩節點自磁碟讀取最新的中介資料，同時 如果-節點知道其中介節點已改變，則該節點利用每一 此種更新的-版本編號，而將其自己的中介資料重新傳 送到新的中介節點。 m . I I I 裝 I I (請先閱讀背面之注意事項再填寫本頁) 經濟部中央標隼局員工消f合作社印裝 -108- 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐）