# HG changeset patch # User matac42 # Date 1681511977 -32400 # Node ID 991d2e95a7a6f9b37c1591711274f2b4d8fb7f21 # Parent ff938946c7f893431ebe93e50ee3d638c175502f ... diff -r ff938946c7f8 -r 991d2e95a7a6 Paper/paper.aux --- a/Paper/paper.aux Sat Apr 15 04:00:32 2023 +0900 +++ b/Paper/paper.aux Sat Apr 15 07:39:37 2023 +0900 @@ -22,8 +22,7 @@ \@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces 非破壊的なTree編集\relax }}{3}{}\protected@file@percent } \newlabel{fig:TreeEdit}{{4}{3}} \@writefile{toc}{\contentsline {section}{\numberline {5}\hskip 1zw{ディスク上とメモリ上のデータ構造}}{3}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {6}\hskip 1zw{データのロールバック}}{3}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{並行アップデート時の問題}}{3}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {6}\hskip 1zw{データのロールバックとバックアップ}}{3}{}\protected@file@percent } \citation{*} \bibstyle{ipsjunsrt} \bibdata{matac-bib} @@ -39,6 +38,7 @@ \bibcite{xv6component}{10} \bibcite{xv6}{11} \bibcite{christie}{12} +\@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{並行アップデート時の問題}}{4}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {8}\hskip 1zw{スキーマ}}{4}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {9}\hskip 1zw{インデックス}}{4}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {10}\hskip 1zw{今後の課題}}{4}{}\protected@file@percent } diff -r ff938946c7f8 -r 991d2e95a7a6 Paper/paper.log --- a/Paper/paper.log Sat Apr 15 04:00:32 2023 +0900 +++ b/Paper/paper.log Sat Apr 15 07:39:37 2023 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 15 APR 2023 04:00 +This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 15 APR 2023 07:35 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -3226,9 +3226,7 @@ \OT1/cmr/m/n/8.8711 https://pdos.csail.mit.edu/6.828/2018/xv6/book- [] -) [4 - -] (./paper.aux) +) [4] (./paper.aux) LaTeX Font Warning: Some font shapes were not available, defaults substituted. @@ -3240,6 +3238,6 @@ 23498 multiletter control sequences out of 15000+600000 499135 words of font info for 160 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 55i,11n,63p,294b,1696s stack positions out of 10000i,1000n,20000p,200000b,200000s - -Output written on paper.dvi (4 pages, 30072 bytes). + 55i,10n,63p,294b,1696s stack positions out of 10000i,1000n,20000p,200000b,200000s + +Output written on paper.dvi (4 pages, 32464 bytes). diff -r ff938946c7f8 -r 991d2e95a7a6 Paper/paper.pdf Binary file Paper/paper.pdf has changed diff -r ff938946c7f8 -r 991d2e95a7a6 Paper/paper.synctex.gz Binary file Paper/paper.synctex.gz has changed diff -r ff938946c7f8 -r 991d2e95a7a6 Paper/paper.tex --- a/Paper/paper.tex Sat Apr 15 04:00:32 2023 +0900 +++ b/Paper/paper.tex Sat Apr 15 07:39:37 2023 +0900 @@ -267,10 +267,51 @@ よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． -メモリからディスクに書き戻すタイミングの話をしたい +% メモリからディスクに書き戻すタイミングの話をしたい + +\section{データのロールバックとバックアップ} + +DBの重要な機能の一つにロールバックがある． +RDBのロールバックは， +コミットするまではトランザクションの開始時点に戻ることができる機能である． +コミットが完了するとそれ以前の状態に戻すことはできないが， +データのバックアップをとっておくことで復元を行う． +このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい． + +今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， +データの復元が行える仕組みを構築することを考える． +非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． +つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． +よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． -\section{データのロールバック} +ルートノードはデータのアップデート時に増えるため， +データが際限なく増加していく問題がある． +この問題はCopyingGCを行うことによって解決する． +まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． +その後，コピーしたものはバックアップとしてディスクに書き込む． +そうすることで，データの増加によるリソースの枯渇を防ぎ， +かつデータのバックアップを作成することで信頼性の向上が期待できる． + + + +% CopyingGCを用いたデータのバックアップを考える． +% 木をコピーして，最新のルートだけを残す． +% コピーしたものはそのままディスクに書き込み，バックアップとして活用する． + + + +% また，トランザクションは複数のプロセスがデータにアクセスする際に， +% データの整合性を保つための機能だが，それについては後の章で述べる． + + +% RedBlackTreeのルートをバージョンとしてとっておいて戻る機能と， +% 過去のツリーをバックアップしておく機能を持たせたい． + + \section{並行アップデート時の問題} + + + \section{スキーマ} \section{インデックス} \section{今後の課題}