[發(fā)明專利]對順序存取存儲介質(zhì)上變長度數(shù)據(jù)的有效存取

有效

• 申請?zhí)枺?/td>: 00128623.4
• 申請日: 2000-08-18
• 公開（公告）號: CN1294387A
• 公開（公告）日: 2001-05-09
• 發(fā)明（設(shè)計）人: L·F·卡布拉;A·S·克哈利得;S·R·斯特納
• 申請（專利權(quán)）人: 微軟公司
• 主分類號: G11B20/12
• 分類號: G11B20/12;G11B27/10
• 代理公司: 上海專利商標(biāo)事務(wù)所
• 代理人: 李湘

一般地，本發(fā)明是關(guān)于順序存取存儲介質(zhì)的，特別是關(guān)于在順序存取存儲介質(zhì)上，存取可變長度數(shù)據(jù)段。

順序存取存儲介質(zhì)，如磁帶和WORM(一次寫入、多次讀取)光盤，典型地用于存儲大量數(shù)據(jù)。相對于其它存儲方法的選擇，如磁盤、磁盤陣列或隨機存取存儲器(RAM)，順序存取存儲介質(zhì)提供了一種低成本存儲的選擇。但是，順序存取存儲介質(zhì)的缺點是，對介質(zhì)上特定位置的定位過程相對慢。對磁帶來說，這種定位一般包括介質(zhì)的機械前繞和／或后繞以便在磁帶上定位于所需數(shù)據(jù)的適當(dāng)位置。這樣，對磁帶上特定數(shù)據(jù)偏移量的定位，會導(dǎo)致順序存取存儲介質(zhì)上，檢索記錄數(shù)據(jù)的整個進程產(chǎn)生大量的操作。

將大量的數(shù)據(jù)流寫到順序存取存儲介質(zhì)時，最好將數(shù)據(jù)流分成較小的數(shù)據(jù)段，因為有幾個原因：第一，數(shù)據(jù)分段分配提高了錯誤恢復(fù)性。一個數(shù)據(jù)段含有一個首部和錯誤恢復(fù)參數(shù)，如校驗和參數(shù)。如果一個很大的數(shù)據(jù)流包含一個數(shù)據(jù)段，在該數(shù)據(jù)段被確認(rèn)前，整個數(shù)據(jù)流必須被讀取。整個一個數(shù)據(jù)段的數(shù)據(jù)流還可能因為一個較小的錯誤而不可恢復(fù)。因此，如果數(shù)據(jù)流被分配成多個較小的數(shù)據(jù)段，單一數(shù)據(jù)段中的錯誤不會使整個數(shù)據(jù)流不可恢復(fù)。

第二，最好使用較小的數(shù)據(jù)段，是因為數(shù)據(jù)段可以作為界線，以適應(yīng)系統(tǒng)緩存的數(shù)據(jù)自動清空。一般地，在數(shù)據(jù)被實際存儲到順序存取存儲介質(zhì)前，應(yīng)用程序?qū)⒁粔K會話數(shù)據(jù)“寫”到系統(tǒng)緩存。一些系統(tǒng)使用數(shù)據(jù)段界線來定義數(shù)據(jù)，使系統(tǒng)自動將緩存的數(shù)據(jù)清空，并記錄到介質(zhì)上。

第三，最好使用較小的數(shù)據(jù)段，因為當(dāng)“寫”操作被初始化時，對應(yīng)用程序來說，整個數(shù)據(jù)流的長度未知，這樣就不能在數(shù)據(jù)段首部中存儲數(shù)據(jù)段長度了?？蛇x地，如果數(shù)據(jù)流被分成多個數(shù)據(jù)段，甚至當(dāng)整個數(shù)據(jù)流的長度還未知時，應(yīng)用程序也可以指定數(shù)據(jù)段的長度。

一項減少在順序存取存儲介質(zhì)上定位的操作耗費的技術(shù)，是使用固定長度數(shù)據(jù)段。即記錄在順序存取存儲介質(zhì)上的數(shù)據(jù)，被分配成存儲在介質(zhì)上的固定長度數(shù)據(jù)段。每個數(shù)據(jù)段典型地含有一個固定長度首部，連接在每個數(shù)據(jù)段的開始部分，例如，數(shù)據(jù)段索引，用來指定數(shù)據(jù)段內(nèi)的數(shù)據(jù)開始部分、段內(nèi)的數(shù)據(jù)長度和填充符的量。如果記錄在段內(nèi)的數(shù)據(jù)比整個固定長度數(shù)據(jù)段短，段內(nèi)剩余部分被填充(也就是，后續(xù)會話數(shù)據(jù)被記錄在下一個數(shù)據(jù)段，而不是當(dāng)前數(shù)據(jù)段的其余部分)。

應(yīng)理解：介質(zhì)偏移量代表沿介質(zhì)方向的順序偏移量，包括首部、數(shù)據(jù)、校驗和、和填充符；而數(shù)據(jù)偏移量只代表數(shù)據(jù)的順序偏移量，不包括首部、數(shù)據(jù)、校驗和、和填充符。為了定位特定的數(shù)據(jù)偏移量O_d，程序(例如，操作系統(tǒng)，應(yīng)用程序，系統(tǒng)驅(qū)動，或嵌入程序)使用簡單的確定算術(shù)方法，計算出對于包含特定數(shù)據(jù)偏移量O_d的數(shù)據(jù)段的介質(zhì)偏移量。固定長度數(shù)據(jù)段的一個缺點是，數(shù)據(jù)段傾向于固定在大的值上(例如64KB(千字節(jié)))，這樣，需要大量填充符，通過在介質(zhì)上引入必要的浪費空間，減小了存儲效率。

為減少固定長度數(shù)據(jù)段引入的浪費空間，現(xiàn)有的一種途徑使用可變長度數(shù)據(jù)段以減少固定長度數(shù)據(jù)段方法中過多的填充符?？勺冮L度數(shù)據(jù)段意味著，數(shù)據(jù)段不必遵從預(yù)設(shè)固定長度，甚至在一些或多數(shù)數(shù)據(jù)段都具有相同長度時也是如此。但是，在固定長度數(shù)據(jù)段的方法中使用的簡單確定位置的方法，在可變長度數(shù)據(jù)段中不起作用。因而，可變長度數(shù)據(jù)段方法包括，使每個讀取頭沿介質(zhì)方向移動，將讀取頭按一個特定數(shù)據(jù)偏移量定位。沿介質(zhì)上的每個首部的數(shù)據(jù)偏移量，和數(shù)據(jù)長度信息被順序估算，直到到達(dá)包含特定數(shù)據(jù)偏移量Od的數(shù)據(jù)段。這一移動機制是費時的，特別是特定數(shù)據(jù)偏移量位于介質(zhì)的尾部時更是如此。

根據(jù)本發(fā)明，上述的和其它問題，通過將可變長度數(shù)據(jù)段結(jié)合到順序存取存儲介質(zhì)上解決，而不需要在順序存取存儲介質(zhì)順序移動讀取頭。

提供在順序存取存儲介質(zhì)上，存取具有可變長度數(shù)據(jù)段數(shù)據(jù)的方法和程序產(chǎn)品。每個可變長度數(shù)據(jù)段包括一個具有預(yù)設(shè)標(biāo)志字段的首部。

在順序存取存儲介質(zhì)上存儲數(shù)據(jù)時，數(shù)據(jù)段按預(yù)設(shè)排列間隔排列。數(shù)據(jù)段被記錄在順序存取存儲介質(zhì)上，使得與預(yù)設(shè)標(biāo)志字段匹配的會話數(shù)據(jù)，不按預(yù)設(shè)排列間隔排列。

從特定數(shù)據(jù)偏移量檢索會話數(shù)據(jù)時，一個或多個估計介質(zhì)偏移量被迭代估計以便在順序存取存儲介質(zhì)上定位特定數(shù)據(jù)偏移量，每次估計從介質(zhì)的上次估計向前或向后移動。定位在估計介質(zhì)偏移量的每個數(shù)據(jù)段被估算以便確定它是否包含特定數(shù)據(jù)偏移量。當(dāng)特定數(shù)據(jù)偏移量被找到，讀寫頭定位在相應(yīng)數(shù)據(jù)段并且記錄在相應(yīng)數(shù)據(jù)段中的所需數(shù)據(jù)被檢索到。