# HG changeset patch # User matac42 # Date 1704380045 -32400 # Node ID 67b68982e36e7fd81876d9dd615190874ac82465 # Parent b7abe0e40c222c1337d1b856f68484ba542cf0c1 ... diff -r b7abe0e40c22 -r 67b68982e36e Paper/.vscode/settings.json --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/.vscode/settings.json Thu Jan 04 23:54:05 2024 +0900 @@ -0,0 +1,85 @@ +{ + // ---------- Language ---------- + + "[tex]": { + // スニペット補完中にも補完を使えるようにする + "editor.suggest.snippetsPreventQuickSuggestions": false, + // インデント幅を2にする + "editor.tabSize": 2 + }, + + "[latex]": { + // スニペット補完中にも補完を使えるようにする + "editor.suggest.snippetsPreventQuickSuggestions": false, + // インデント幅を2にする + "editor.tabSize": 2 + }, + + "[bibtex]": { + // インデント幅を2にする + "editor.tabSize": 2 + }, + + + // ---------- LaTeX Workshop ---------- + + // 使用パッケージのコマンドや環境の補完を有効にする + "latex-workshop.intellisense.package.enabled": true, + + // 生成ファイルを削除するときに対象とするファイル + // デフォルト値に "*.synctex.gz" を追加 + "latex-workshop.latex.autoClean.run": "onBuilt", + "latex-workshop.latex.clean.fileTypes": [ + "*.aux", + "*.bbl", + "*.blg", + "*.idx", + "*.ind", + "*.lof", + "*.lot", + "*.out", + "*.toc", + "*.acn", + "*.acr", + "*.alg", + "*.glg", + "*.glo", + "*.gls", + "*.ist", + "*.fls", + "*.log", + "*.fdb_latexmk", + "*.snm", + "*.nav", + "*.dvi", + "*.ilg", + "*.synctex.gz" + ], + + // 生成ファイルを現在のディレクトリに吐き出す + "latex-workshop.latex.outDir": "", + + // ビルドのレシピ + "latex-workshop.latex.recipes": [ + { + "name": "latexmk", + "tools": [ + "latexmk" + ] + }, + ], + + // ビルドのレシピに使われるパーツ + "latex-workshop.latex.tools": [ + { + "name": "latexmk", + "command": "latexmk", + "args": [ + "-silent", + "-outdir=%OUTDIR%", + "%DOC%" + ], + }, + ], + "latex-workshop.view.pdf.viewer": "tab", +} \ No newline at end of file diff -r b7abe0e40c22 -r 67b68982e36e Paper/chapter/abstract.tex --- a/Paper/chapter/abstract.tex Sat Dec 23 16:08:07 2023 +0900 +++ b/Paper/chapter/abstract.tex Thu Jan 04 23:54:05 2024 +0900 @@ -3,8 +3,6 @@ 当研究室では，Continuation based C（CbC）を用い，定理証明やモデル検査などで信頼性を保証することを目的としたGearsOSを開発している． OSにおいてファイルシステムは重要な機能の一つであるため実装する必要がある． 現在，一般的なアプリケーションはファイルシステムとデータベースを併用する形で構成される． -DBはSQLによってデータの挿入や変更が可能だがスキーマを事前に定義し，insert時にそれらのschemaを指定する必要がある． -GearsOSのファイルシステムではSQLの機能に相当するgrepやfindなどのインターフェースを実装し， アプリケーションのデータベースとしてファイルシステムを使用する構成が取れるようにしたい． ファイルシステムとデータベースの違いについて考え，データベースとしても利用可能なファイルシステムを構築したい． 本研究では，ファイルシステムとデータベースの違いについて考察し，Gears OSのファイルシステムの設計について述べる． diff -r b7abe0e40c22 -r 67b68982e36e Paper/master_paper.pdf Binary file Paper/master_paper.pdf has changed diff -r b7abe0e40c22 -r 67b68982e36e Paper/master_paper.tex --- a/Paper/master_paper.tex Sat Dec 23 16:08:07 2023 +0900 +++ b/Paper/master_paper.tex Thu Jan 04 23:54:05 2024 +0900 @@ -99,9 +99,8 @@ \chapter{GearsOSにおけるファイルシステムとDB} -アプリケーションの信頼性を保証することは -情報システムやコンピュータを用いる業務の信頼性の保障につながる重要な課題である． -したがって，アプリケーションの信頼性を保証するために，基盤となるOSの信頼性を高める必要がある． +情報システムにおけるファイルシステムとDBは重要な要素である． +ファイルシステムではOSが動作するための 当研究室では，信頼性の保証を目的としたGearsOSを開発している． GearsOSは，OSの信頼性を定理証明やモデル検査を行うことで保証することを目指している\cite{modelcheck}． @@ -233,85 +232,11 @@ これは，教育用に開発されたx.v6\cite{xv6}をCbCで書き換える形で実装する． 今回，ファイルシステムを実装する対象は3つ目のCbC\_xv6である． -\chapter{RedBlackTreeによるファイルシステムの構成} - -ファイルシステムは全てRedBlackTreeで構成する． -それにより，プログラムの証明がより簡単になるからである． -また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． -よって，それらはまとめてRedBlackTreeで構成する． - -ファイルシステムとDBの違いとして，スキーマが挙げられる． -DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する． -対して，ファイルシステムにはスキーマに当たるものがなく， -データはファイルパスによって管理される． -スキーマを定義することによってデータは構造化され， -構造化されたデータは非構造化データと比較して， -インデックスを作成することが容易であり，データの検索性が向上する利点がある． -しかしながら，スキーマはDBの運用中に変更されることがあり， -スキーマを変更した以前へロールバックができない問題がある． - -ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， -スキーマを定義する必要のないスキーマレスなDBが必要になる． -ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ -DBがスキーマによって実現していた機能を付け加えることを試みる． - -RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． -今回用いるのは，非破壊的な実装のRedBlackTreeである． -図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している． -編集前の木構造の6のノードをAにアップデートすることを考える． -まず，ルートノードからアップデートしたいノード6までをコピーする． -その後，コピーしたもののノード6をAにアップデートする． -これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である． -参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える． -この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える． - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=80mm]{fig/nonDestroyTreeEdit.pdf} - \end{center} - \caption{非破壊的なTree編集} - \label{fig:TreeEdit} -\end{figure} - - -\chapter{ディスク上とメモリ上のデータ構造} - -ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． -一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． -なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， -B-Treeのようなノードを複数持つことができる構造が効果的だからである． -その点ではRedBlackTreeはB-Treeに劣る． -しかしながら，SSDはランダムアクセスによってデータにアクセスするため， -RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． -よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． -そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． - -\chapter{データのロールバックとバックアップ} - -DBの重要な機能の一つにロールバックがある． -RDBのロールバックは， -コミットするまではトランザクションの開始時点に戻ることができる機能を持つ． -コミットが完了するとそれ以前の状態に戻すことはできないが， -データのバックアップをとっておくことで復元を行う． -このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい． - -今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， -データの復元が行える仕組みを構築することを考える． -非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． -つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． -よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． - -ルートノードはデータのアップデート時に増えるため， -データが際限なく増加していく問題がある． -この問題はCopyingGCを行うことによって解決する． -まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． -その後，コピーしたものはバックアップないしログとしてディスクに書き込む． -そうすることで，データの増加によるリソースの枯渇を防ぎ， -かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． - -% TODO: バックアップのフローを図にしたい - -\chapter{RedBlackTreeのトランザクション} +\chapter{GearsFileSystem} +\section{DataGearManagerによる分散ファイルシステム} +\section{i-nodeを用いたファイルシステム} +\section{非破壊RedBlackTreeによる構成} +\section{RedBlackTreeのトランザクション} トランザクションはDBの重要な機能の一つである． データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう @@ -359,8 +284,101 @@ しかし，常に最新の情報を読み込めるとは限らない． 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． +\section{ディスク上とメモリ上のデータ構造} -\chapter{ファイルシステムにおけるスキーマ} + +ファイルシステムは全てRedBlackTreeで構成する． +それにより，プログラムの証明がより簡単になるからである． +また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． +よって，それらはまとめてRedBlackTreeで構成する． + +ファイルシステムとDBの違いとして，スキーマが挙げられる． +DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する． +対して，ファイルシステムにはスキーマに当たるものがなく， +データはファイルパスによって管理される． +スキーマを定義することによってデータは構造化され， +構造化されたデータは非構造化データと比較して， +インデックスを作成することが容易であり，データの検索性が向上する利点がある． +しかしながら，スキーマはDBの運用中に変更されることがあり， +スキーマを変更した以前へロールバックができない問題がある． + +ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， +スキーマを定義する必要のないスキーマレスなDBが必要になる． +ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ +DBがスキーマによって実現していた機能を付け加えることを試みる． + +RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． +今回用いるのは，非破壊的な実装のRedBlackTreeである． +図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している． +編集前の木構造の6のノードをAにアップデートすることを考える． +まず，ルートノードからアップデートしたいノード6までをコピーする． +その後，コピーしたもののノード6をAにアップデートする． +これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である． +参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える． +この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える． + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=80mm]{fig/nonDestroyTreeEdit.pdf} + \end{center} + \caption{非破壊的なTree編集} + \label{fig:TreeEdit} +\end{figure} + + +\chapter{GearsFileSystemにおけるGCとレプリケーションの仕組み} +\section{CopyRedBlackTreeによるGCの仕組み} +\section{CopyRedBlackTreeによるレプリケーションの仕組み} + +ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． +一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． +なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， +B-Treeのようなノードを複数持つことができる構造が効果的だからである． +その点ではRedBlackTreeはB-Treeに劣る． +しかしながら，SSDはランダムアクセスによってデータにアクセスするため， +RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． +よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． +そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． + +\chapter{CopyRedBlackTreeの実装} +\section{コピーのアルゴリズム} +\section{Stackの使用に関して} +\section{証明のしやすさについて} + + +DBの重要な機能の一つにロールバックがある． +RDBのロールバックは， +コミットするまではトランザクションの開始時点に戻ることができる機能を持つ． +コミットが完了するとそれ以前の状態に戻すことはできないが， +データのバックアップをとっておくことで復元を行う． +このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい． + +今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， +データの復元が行える仕組みを構築することを考える． +非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． +つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． +よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． + +ルートノードはデータのアップデート時に増えるため， +データが際限なく増加していく問題がある． +この問題はCopyingGCを行うことによって解決する． +まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． +その後，コピーしたものはバックアップないしログとしてディスクに書き込む． +そうすることで，データの増加によるリソースの枯渇を防ぎ， +かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． + +% TODO: バックアップのフローを図にしたい + + +\chapter{まとめと今後の課題} + +本論文ではGearsOSのファイルシステムとDBの設計について説明した． +今後，実装を行いながら設計と動作の確認，計測を行い， +設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある． + +また，今後の課題や議題として次のようなものが挙げられる． + +\section{ファイルシステムにおけるスキーマ} 従来のRDBのようなスキーマが存在すると， 個別にバックアップなどを取らない限り @@ -390,22 +408,13 @@ DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている． よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． -\chapter{RedBlackTreeによる権限の表現} +\section{RedBlackTreeによる権限の表現} ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある． 今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することが ファイルに対して権限を設定することにあたる． ルートに対してアクセスする権限がなければ， 読み書きができないといった実装になると考える． - -\chapter{まとめと今後の課題} - -本論文ではGearsOSのファイルシステムとDBの設計について説明した． -今後，実装を行いながら設計と動作の確認，計測を行い， -設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある． - -また，今後の課題や議題として次のようなものが挙げられる． - \section{データクエリ言語} ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を diff -r b7abe0e40c22 -r 67b68982e36e Paper/reference.bib --- a/Paper/reference.bib Sat Dec 23 16:08:07 2023 +0900 +++ b/Paper/reference.bib Thu Jan 04 23:54:05 2024 +0900 @@ -105,4 +105,22 @@ journal = {情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)}, month = {May}, year = 2022 +} + +@misc{zengin, + title = {全国銀行データ通信システムの障害について}, + author = {一般社団法人 全国銀行資金決済ネットワーク}, + howpublished = {https://www.zengin-net.jp/announcement/pdf/announcement\_20231201.pdf} +} + +@misc{ana, + title = {4月3日に発生した国内線システム不具合の原因及び再発防止策について}, + author = {全日本空輸株式会社}, + howpublished = {https://www.anahd.co.jp/group/pr/202304/notification-2.html} +} + +@misc{glory, + title = {2月14日から2月19日にかけて発生した電子マネー決済システム（iD決済）の障害に関するお詫びとお知らせ}, + author = {グローリー株式会社}, + howpublished = {https://www.glory.co.jp/news/detail/id=2017} } \ No newline at end of file diff -r b7abe0e40c22 -r 67b68982e36e mindmaps/gears_fs_db.mm --- a/mindmaps/gears_fs_db.mm Sat Dec 23 16:08:07 2023 +0900 +++ b/mindmaps/gears_fs_db.mm Thu Jan 04 23:54:05 2024 +0900 @@ -348,8 +348,37 @@ - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + @@ -379,18 +408,20 @@ + - - + - - - - + + - + + + + +