(57)【要約】【課題】同じデータ量で誤り訂正可能なビット数を増加させることができ、データ格納効率を向上させる。【解決手段】入力されたデータを、修正可能なビット数ｄに応じて求められた代数曲線Ｘに基づくビット数ずつ分割するデータ分割部２１と、データ分割部２１にて分割されたデータをそれぞれ、ビット数ｄに応じて求められた因子Ｇ及び代数曲線Ｘを用いて符号化する符号化部２２と、符号化部２２にて符号化されたデータを、ビット数ｄずつ別々のディスク１０ａ〜１０ｄに格納するデータ格納部２３と、複数のディスク１０ａ〜１０ｄからデータを抽出するデータ抽出部２４と、データ抽出部２４にて前記複数のディスク１０ａ〜１０ｄから抽出されたデータを復号化する復号化部２５と、復号化部２５にて復号化されたデータを結合するデータ結合部２６とを有する。【選択図】図１
2007257458.tif 000002
【特許請求の範囲】
【請求項１】
複数のディスクにデータを分割して格納するデータ格納装置であって、
入力されたデータを、修正可能なビット数に応じて求められた代数曲線に基づくビット数ずつ分割するデータ分割手段と、
前記データ分割手段にて分割されたデータをそれぞれ、前記修正可能なビット数に応じて求められた因子及び前記代数曲線を用いて符号化する符号化手段と、
前記符号化手段にて符号化されたデータを、前記修正可能なビット数ずつ別々のディスクに格納するデータ格納手段と、
前記複数のディスクからデータを抽出するデータ抽出手段と、
前記データ抽出手段にて前記複数のディスクから抽出されたデータを復号化する復号化手段と、
前記復号化手段にて復号化されたデータを結合するデータ結合手段とを有するデータ格納装置。
【請求項２】
請求項１に記載のデータ格納装置において、
前記複数のディスクにて障害が発生した場合、該ディスクに格納されたビットに全て０を代入するビット仮変換手段と、
前記障害が発生したディスクについて、前記代数曲線の生成多項式を用いて誤りのあるビット位置を検出する誤り検出手段と、
前記誤り検出手段にて検出されたビット位置に１を代入する誤り訂正手段とを有することを特徴とするデータ格納装置。
【請求項３】
複数のディスクにデータを分割して格納し、該データを前記複数のディスクから抽出するデータ格納／抽出方法であって、
入力されたデータを、修正可能なビット数に応じて求められた代数曲線に基づくビット数ずつ分割する処理と、
前記分割されたデータをそれぞれ、前記修正可能なビット数に応じて求められた因子及び前記代数曲線を用いて符号化する処理と、
前記符号化されたデータを、前記修正可能なビット数ずつ別々のディスクに格納する処理と、
前記複数のディスクからデータを抽出する処理と、
前記複数のディスクから抽出されたデータを復号化する処理と、
前記復号化されたデータを結合する処理とを有するデータ格納／抽出方法。
【請求項４】
請求項３に記載のデータ格納／抽出方法において、
前記複数のディスクにて障害が発生した場合、該ディスクに格納されたビットに全て０を代入する処理と、
前記障害が発生したディスクについて、前記代数曲線の生成多項式を用いて誤りのあるビット位置を検出する処理と、
前記検出されたビット位置に１を代入する処理とを有することを特徴とするデータ格納／抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ格納装置及びデータ格納／抽出方法に関する。
【背景技術】
【０００２】
現在、データベースのデータの障害からの復元には、パリティビットを配置し、それを使用した方法で行なうのが通常であり、そのために余分なディスク容量を必要とする。
【０００３】
図５は、従来のデータ格納方法の一例を説明するためのシステム図である。
【０００４】
従来は、図５に示すようにサーバ１３０からのデータは、複数に分割され、パリティビットが付加された状態で複数ディスク１１０ａ〜１１０ｄに格納されている。
【０００５】
図６は、図５に示したシステムにてディスク１１０ｃに障害が発生した場合を示す図であり、図７は、図６に示した障害発生時の処理を説明するためのフローチャートである。
【０００６】
図６に示すようにディスク１１０ｃにて障害が発生すると（ステップＳ１）、残りのディスク１１０ａ，１１０ｂ，１１０ｄの該当ビットの和を計算し（ステップＳ２）、パリティの理論によりその和をディスク１１０ｃの該当ビットにすれば修正することができる（ステップＳ３）。そして、このような処理が繰り返し行われる（ステップＳ４）。
【０００７】
このように、データが複数に分割し、パリティビットを付加された状態で複数ディスクに格納しておくことにより、障害復旧を行う技術が利用されている（例えば、特許文献１参照。）。
【特許文献１】特開２００５−２９３１４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述したようにパリティビット等の誤り訂正符号を用いた場合、その分のデータ量が増加し、データ格納効率が低下してしまうという問題点がある。
【０００９】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、同じデータ量で誤り訂正可能なビット数を増加させることができ、データ格納効率を向上させることができるデータ格納装置及びデータ格納／抽出方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために本発明は、
複数のディスクにデータを分割して格納するデータ格納装置であって、
入力されたデータを、修正可能なビット数に応じて求められた代数曲線に基づくビット数ずつ分割するデータ分割手段と、
前記データ分割手段にて分割されたデータをそれぞれ、前記修正可能なビット数に応じて求められた因子及び前記代数曲線を用いて符号化する符号化手段と、
前記符号化手段にて符号化されたデータを、前記修正可能なビット数ずつ別々のディスクに格納するデータ格納手段と、
前記複数のディスクからデータを抽出するデータ抽出手段と、
前記データ抽出手段にて前記複数のディスクから抽出されたデータを復号化する復号化手段と、
前記復号化手段にて復号化されたデータを結合するデータ結合手段とを有する。
【００１１】
また、複数のディスクにデータを分割して格納し、該データを前記複数のディスクから抽出するデータ格納／抽出方法であって、
入力されたデータを、修正可能なビット数に応じて求められた代数曲線に基づくビット数ずつ分割する処理と、
前記分割されたデータをそれぞれ、前記修正可能なビット数に応じて求められた因子及び前記代数曲線を用いて符号化する処理と、
前記符号化されたデータを、前記修正可能なビット数ずつ別々のディスクに格納する処理と、
前記複数のディスクからデータを抽出する処理と、
前記複数のディスクから抽出されたデータを復号化する処理と、
前記復号化されたデータを結合する処理とを有する。
【発明の効果】
【００１２】
本発明は、同じデータ量で従来よりも誤り訂正可能なビット数を増加させることができ、データ格納効率を向上させることができる。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１４】
代数幾何符号とは、有限体上の非特異射影代数曲線から構成される符号である。
【００１５】
射影代数曲線とは、射影平面Ｐｎ上で定義された関数である。
【００１６】
体Ｃ上定義された射影平面とは、Ｃ＼｛（０，０，・・・，０）｝の座標の比を成分とした集合に、（α１，α２，・・・，αｃ）と、（χα１，χα２，・・・，χαｃ）（但しχ∈Ｃ、χ≠０）とは、同じとみなすという同値関係をいれたものである。特に、座標の比を意識して（α１：α２：・・・：αｃ）のように表記される。
【００１７】
まず、代数幾何符号の構成法について簡単に説明する。
【００１８】
代数曲線には種数ｇと呼ばれるパラメータが定義される。種数とは、３次元空間上の閉じた曲面の穴の数を一般化したもので、数学的にはコホモロジー空間の次元として定義される。
【００１９】
種数ｇは双有理不変な値として知られている（双有理同値な代数曲線の種数は同じ）。
【００２０】
有限体Ｆ上の非特異射影代数曲線Ｘ上の点Ｐ１，Ｐ２，・・・，Ｐλをとり、その整数係数形式和
Ｄ＝ｍ１・Ｐ１＋ｍ２・Ｐ２＋ｍ３・Ｐ３・・・＋ｍλ・Ｐλ
を考える。Dを因子という。
ｄｅｇＤ＝ｍ１＋ｍ２＋ｍ３＋・・・＋ｍλ
とおき、これをＤの次数という。
【００２１】
標数ｑの有限体ＧＦ（ｑ）を考え、その代数閉包をＦｑとおく。
【００２２】
Ｆｑ上の射影平面の点で、全ての要素がＧＦ（ｑ）に含まれるものをＧＦ（ｑ）有理点という(以下、有理点と称する）。
【００２３】
ＸをＦｑ上の非特異射影代数曲線とし、Ｐ１，Ｐ２，Ｐ３，・・・，ＰｎをＸの有理点とする。
【００２４】
Ｄ＝Ｐ１＋Ｐ２＋Ｐ３＋Ｐｎとし、ＧをＤと共通の点がない因子とする。
【００２５】
また、Ｇの各点の係数は０以上とする。
【００２６】
Ｘ上のＧＦ（ｑ）に係数を持つ有理関数で高々Ｇに極をもつもの全体のなす空間をＬ（Ｇ）とおく。
【００２７】
Ｌ（Ｇ）からＧＦ（ｑ）ｎへの線形写像ΦをΦ：ｆ→ｆ（Ｐ１），ｆ（Ｐ２），ｆ（Ｐ３），・・・，ｆ（Ｐｎ）として定義し、ＩｍΦを弱い意味の代数幾何符号という。
【００２８】
次に、代数幾何符号のビット数、誤り訂正可能数を求める理論を説明する。
【００２９】
上記の定義より、弱い意味の代数幾何符号の符号長は、ｄｉｍ ＩｍΦとなる。次元定理により、
ｄｉｍ ＩｍΦ＝ｄｉｍＬ（Ｇ）−ｄｉｍ ｋｅｒΦ
であるが、ｄｅｇＧ＜ｎであれば、ｄｉｍ ｋｅｒΦ＝０
であることがわかるので、
ｄｉｍ ＩｍΦ＝ｄｉｍＬ（Ｇ）
がわかる。このとき、ＩｍΦを代数幾何符号という。
【００３０】
ｄｉｍＬ（Ｇ）は、代数幾何の基本的な定理であるリーマン・ロッホの定理の特別な場合からわかる。以下に、リーマン・ロッホの定理を示す。
【００３１】
ｄｅｇＧ＞２ｇ−２のとき、
ｄｉｍＬ（Ｇ）＝ｄｅｇＧ−ｇ＋１
よって、この場合の符号化できるビット数は、ｄｅｇＧ−ｇ＋１であることがわかる。
【００３２】
このとき、訂正可能ビット数ｄは、
ｄ≧ｎ−ｄｅｇＧとなる。
【００３３】
以下に、上述した代数幾何符号を用いたデータ格納装置について説明する。
【００３４】
図１は、本発明のデータ格納装置の実施の一形態を示す図であり、図２は、その詳細な構成を示す図である。
【００３５】
本形態のデータ格納装置２０は図１に示すように、サーバ３０からのデータを複数のディスク１０ａ〜１０ｄに格納するものであって、図２に示すように、データ分割部２１と、符号化部２２と、データ格納部２３と、データ抽出部２４と、復号化部２５と、データ結合部２６と、障害復旧部２７とから構成されている。
【００３６】
上記のように構成されたデータ格納装置２０においては、まず、修正可能ビット数をｄを決めておき、例えばデータを４つのディスク１０ａ〜１０ｄに分割する場合、４ｄ＝ｄｉｍＬ（Ｇ）となるような代数曲線Ｘ及び因子Ｇをとる。
【００３７】
この状態でサーバ３０からデータが入力されると、データ分割部２１において、入力されたデータがｎビット（ｎは代数曲線Ｘの有理点の個数）ずつ分割される。
【００３８】
次に、符号部２２において、データ分割部２１にて分割されたデータ毎に、代数曲線Ｘと因子Ｇを用いた符号化が行われる。
【００３９】
代数曲線の取り方により、符号化されたデータのデータ長は３ｄビットとなるので、続いてデータ格納部２３において、ｄビットずつ別々のディスク１０ａ〜１０ｄへの格納が行われる。
【００４０】
データ出力時には、まず、データ抽出部２４において、ディスク１０ａ〜１０ｄから符号化されたデータが抽出され、次に、復号化部２５において、ディスク１０ａ〜１０ｄから抽出されたデータの復号化が行われる。
【００４１】
その後、データ結合部２６において、復号化部２５にて復号化されたデータが結合され、入力時と同じデータが出力される。
【００４２】
次に、ディスク障害時の復旧方法について説明する。
【００４３】
図３は、図１に示したシステム構成にてディスク１０ｃに障害が発生した場合を示す図であり、図４は、図２に示した障害復旧部２７の構成を示す図である。
【００４４】
図３に示すように、ディスク１０ｃに障害が発生した場合、まず、障害復旧部２７のビット仮変換機構４１において、ディスク１０ｃのビットに全て０が代入される。
【００４５】
次に、障害復旧部２７の誤り検出機構４２において、代数曲線Ｘの生成多項式を用いた誤りのあるビット位置の検出が行われる。この誤り検出は、３ｄビットの格納データ毎に行うため、全ての誤りが訂正可能誤りとして検出されることが保障されている。
【００４６】
次に、障害復旧部２７の誤り訂正機構４３において、検出された誤り位置に１が代入され、障害前の状態に復元される。
【００４７】
上述した実施の形態において、元データ長をｋとおく。上記理論中のｎが符号化されたデータ長であり、ｄが訂正可能な誤り数である。
【００４８】
上記理論により、ｋ＝ｄｅｇＧ−ｇ＋１，ｄ≧ｎ−ｄｅｇＧであり、ｎはＸの有理点の個数であった。
【００４９】
ｄｅｇＧは、代数曲線がフェルマー曲線などの場合は体Ｆｑの標数ｑから定まることがわかる。
【００５０】
よって、標数ｑがある程度大きく、有理点の数が多い代数曲線を選ぶことにより、単純な割り算にてｎｋが定まる従来の方法よりも、同じｎでｋが大きなものを構成することができる。
【図面の簡単な説明】
【００５１】
【図１】本発明のデータ格納装置の実施の一形態を示す図である。
【図２】図１に示したデータ格納装置の詳細な構成を示す図である。
【図３】図１に示したシステム構成にてディスクに障害が発生した場合を示す図である。
【図４】図２に示した障害復旧部の構成を示す図である。
【図５】従来のデータ格納方法の一例を説明するためのシステム図である。
【図６】図５に示したシステムにてディスクに障害が発生した場合を示す図である。
【図７】図６に示した障害発生時の処理を説明するためのフローチャートである。
【符号の説明】
【００５２】
１０ａ〜１０ｄ    ディスク
２０    データ格納装置
２１    データ分割部
２２    符号化部
２３    データ格納お部
２４    データ抽出部
２５    復号化部
２６    データ結合部
２７    障害復旧部
３０    サーバ
４１    ビット仮変換機構
４２    誤り検出機構
４３    誤り訂正機構
【図１】
2007257458.tif 000003
【図２】
2007257458.tif 000004
【図３】
2007257458.tif 000005
【図４】
2007257458.tif 000006
【図５】
2007257458.tif 000007
【図６】
2007257458.tif 000008
【図７】
2007257458.tif 000009