# HG changeset patch # User matac42 # Date 1681650089 -32400 # Node ID 0cf15f862f020c4be30ce7d32430276bfbe11fb9 # Parent 091510a8cd0acd2cf68ab8c2988a2ab39529690c transaction diff -r 091510a8cd0a -r 0cf15f862f02 Paper/paper.aux --- a/Paper/paper.aux Sun Apr 16 20:58:40 2023 +0900 +++ b/Paper/paper.aux Sun Apr 16 22:01:29 2023 +0900 @@ -39,7 +39,7 @@ \bibcite{xv6}{11} \bibcite{christie}{12} \bibcite{directory}{13} -\@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{トランザクション}}{4}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{RedBlackTreeのトランザクション}}{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 091510a8cd0a -r 0cf15f862f02 Paper/paper.log --- a/Paper/paper.log Sun Apr 16 20:58:40 2023 +0900 +++ b/Paper/paper.log Sun Apr 16 22:01:29 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) 16 APR 2023 20:51 +This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 16 APR 2023 22:01 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -3239,4 +3239,4 @@ 929 hyphenation exceptions out of 8191 55i,10n,63p,294b,1365s stack positions out of 10000i,1000n,20000p,200000b,200000s -Output written on paper.dvi (4 pages, 35628 bytes). +Output written on paper.dvi (4 pages, 36476 bytes). diff -r 091510a8cd0a -r 0cf15f862f02 Paper/paper.pdf Binary file Paper/paper.pdf has changed diff -r 091510a8cd0a -r 0cf15f862f02 Paper/paper.synctex.gz Binary file Paper/paper.synctex.gz has changed diff -r 091510a8cd0a -r 0cf15f862f02 Paper/paper.tex --- a/Paper/paper.tex Sun Apr 16 20:58:40 2023 +0900 +++ b/Paper/paper.tex Sun Apr 16 22:01:29 2023 +0900 @@ -291,21 +291,34 @@ かつデータのバックアップを作成することで信頼性の向上が期待できる． -\section{トランザクション} +\section{RedBlackTreeのトランザクション} + +トランザクションはDBの重要な機能の一つである． +データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう +トランザクションの仕組みを考える必要がある． +今回，ファイルシステムは全てRedBlackTreeで実装するため， +RedBlackTreeのノードに対するトランザクションを考える． -ルートノードはデータをリード，ライトする時に増やす． -それにより，ルートノードは一つのスレッドを表現する． -スレッドがデータのアップデートを行う際は，他のスレッドとの競合を防ぐ必要がある． -スレッドはルートノードからアップデート対象のノードまで辿るようにロックを獲得していく． -その際，子ノードのロックを獲得した後は親ノードのロックを手放して良いことにする． -データのアップデートが完了し，ロックを解除後，ルートノードの切り替えを行う． -このような操作によって，トランザクションを実現する． -しかし，このままだとアップデートによってデータの一貫性を損なう場合がある． -常に最新のデータを持ったルートノードを選択する仕組みが必要になる． +トランザクションをwriteとreadに分けて考える． +writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する． +writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える． +そのため，書き込みの並列度はルートの数と一致する． +しかしながら，ルートの置き換えは競合的なので， +複数書き込みを行っても1つしか成功しない． +よって，単一のRedBlackTreeに複数の書き込みポイントを作り， +並行実行可能にする必要がある． -なお，リードする際はその時点で最新のルートノードを元にリード用のルートノードを作成する． -リードは木を変更することがないので， -作成したリード用ルートノードの数だけ同時にリード可能となる． +RedBlackTreeに複数の書き込みポイントを作るために， +キーごとのルートを作成する． +ノードはそれぞれがキーとRedBlackTreeを持つ状態になる． +writeする際は，そのキーのルートを置き換える． +それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， +writeを並行実行することが可能となる． + +readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である． +しかし，常に最新の情報を読み込めるとは限らない． +最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． + \section{スキーマレスな実装}