Binary file Paper/fig/gears_dir.png has changed

--- a/Paper/master_paper.lol	Tue Jan 23 18:35:35 2024 +0900
+++ b/Paper/master_paper.lol	Tue Jan 23 20:13:55 2024 +0900
@@ -6,6 +6,7 @@
 \contentsline {lstlisting}{\numberline {3.5}Treeの仕様}{15}{}%
 \contentsline {lstlisting}{\numberline {3.6}RedBlackTreeの実装}{16}{}%
 \contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの実装の型定義}{16}{}%
-\contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{29}{}%
-\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{30}{}%
-\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{32}{}%
+\contentsline {lstlisting}{\numberline {3.8}Nodeの型定義}{17}{}%
+\contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{30}{}%
+\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{31}{}%
+\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{33}{}%

Binary file Paper/master_paper.pdf has changed

--- a/Paper/master_paper.tex	Tue Jan 23 18:35:35 2024 +0900
+++ b/Paper/master_paper.tex	Tue Jan 23 20:13:55 2024 +0900
@@ -404,6 +404,16 @@
 9行目のfindNodeNextはfindNode CodeGearを実行後，次に実行するCodeGearを保持する．
 10行目のresultはノードを探索する際のノードの比較結果を保持する．
 
+ソースコード\ref{src:RedBlackTree.h}にある通り，
+RedBlackTreeはNode構造体を複数持つ．
+ソースコード\ref{src:Node.h}にNodeの型定義を示す．
+
+\lstinputlisting[label=src:Node.h, caption=Nodeの型定義]{src/Node.h}
+
+1，2行目よりノードのキーがint型であり，valueとしてDataGearのポインタを持つことがわかる．
+また，3〜7行目よりleft，rightで子のNodeのポインタを持つことによって木構造を構築し，
+enum ColorでRedBlackTreeとして必要なノードの色を表現していることがわかる．
+
 \chapter{GearsFileSystem}
 
 ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや
@@ -577,6 +587,10 @@
 
 \chapter{GearsFileSystemにおけるGCとレプリケーション}
 
+本章ではRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べる．
+GC，レプリケーション，バックアップをRedBlackTreeのコピーを基礎とする，
+統一的な仕組みにより実装することが考えられる．
+
 \section{ファイルシステムの信頼性に関する機能}
 
 ファイルシステムはデータを保持することを基本的な機能としている．
@@ -752,11 +766,7 @@
 そのため，GCへの切り替えにおいてソースコード\ref{src:isEmpty.cbc}のようなコードを記述すると，
 ノーマルレベルとメタレベルが混在するCodeGearとなってしまう問題がある．
 
-\section{GCとレプリケーションとバックアップ}
 
-ここまででRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べた．
-そこから，GC，レプリケーション，バックアップをRedBlackTreeのコピーを基礎とする，
-統一的な仕組みにより実装することが考えられる．
 
 
 
@@ -794,9 +804,8 @@
 
 \chapter{まとめと今後の課題}
 
-本論文ではGearsOSのファイルシステムとDBの設計について説明した．
-今後，実装を行いながら設計と動作の確認，計測を行い，
-設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある．
+本研究ではGearsOSのファイルシステムであるGearsFileSystemにおける
+GCとレプリケーションについての考察，CopyRedBlackTreeの実装と考察を行った．
 
 また，今後の課題や議題として次のようなものが挙げられる．
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/Node.h	Tue Jan 23 20:13:55 2024 +0900
@@ -0,0 +1,12 @@
+typedef struct Node <> {
+  int key; // comparable data segment;
+  union Data* value;
+  struct Node* left;
+  struct Node* right;
+          // need to balancing
+  enum Color {
+      Red,
+      Black,
+      // Red eq 0,Black eq 1. enum name convert intager.
+  }color;
+} Node;
\ No newline at end of file

--- a/TODO.md	Tue Jan 23 18:35:35 2024 +0900
+++ b/TODO.md	Tue Jan 23 20:13:55 2024 +0900
@@ -6,8 +6,9 @@
 - [x] GearsOSのRedBlackTreeの説明
 
 - [x] レプリケーションの説明
+- [x] Nodeの説明
 - [ ] DGMによる分散ファイルシステム
-- [ ] Nodeの説明
 - [ ] 実装の説明
+- [ ] 評価
 - [ ] まとめ
 - [ ] 今後の課題
\ No newline at end of file

--- a/mindmaps/gears_fs_db.mm	Tue Jan 23 18:35:35 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Tue Jan 23 20:13:55 2024 +0900
@@ -357,6 +357,9 @@
 <node TEXT="探索，挿入，削除操作のオーダーが最悪の場合でもO(log n)" ID="ID_1352435743" CREATED="1705402694002" MODIFIED="1705402896426"/>
 <node TEXT="データ構造の一つ" ID="ID_1144589445" CREATED="1705402772112" MODIFIED="1705402780832"/>
 </node>
+<node TEXT="rootを保持する構造がほしい" ID="ID_1410049473" CREATED="1705991762051" MODIFIED="1705991775332">
+<node TEXT="バージョンを参照するため" ID="ID_1632488340" CREATED="1705991775778" MODIFIED="1705991782869"/>
+</node>
 </node>
 <node TEXT="Rustの所有権" POSITION="right" ID="ID_612327915" CREATED="1704949737149" MODIFIED="1704949745661">
 <node TEXT="メモリを所有する変数のスコープを抜けるとメモリも解放される" ID="ID_972875880" CREATED="1704949746103" MODIFIED="1704949765401"/>
@@ -546,7 +549,7 @@
 </node>
 <node TEXT="GearsOSのRedBlackTree" ID="ID_594513732" CREATED="1705400358246" MODIFIED="1705400364641"/>
 </node>
-<node TEXT="GearsOSのファイルシステムとDB(現状の話" FOLDED="true" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1705549429213">
+<node TEXT="GearsOSのファイルシステムとDB(現状の話" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1705549429213">
 <node TEXT="GearsOSのファイルシステムとDB" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1705549436675">
 <node TEXT="ファイルシステムはOSの重要な機能である" ID="ID_46805604" CREATED="1704630103040" MODIFIED="1704630119191"/>
 <node TEXT="分散ファイルシステムとi-nodeを用いたファイルシステムが存在する" ID="ID_1509553363" CREATED="1704630119858" MODIFIED="1704630152926"/>
@@ -565,7 +568,7 @@
 <node TEXT="RedBlackTreeのトランザクション" ID="ID_1088328123" CREATED="1701696247760" MODIFIED="1702112463420" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="3.75 pt"/>
 </node>
 </node>
-<node TEXT="GearsFileSystemにおけるGCとレプリケーション" FOLDED="true" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1705569492385" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt">
+<node TEXT="GearsFileSystemにおけるGCとレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1705569492385" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt">
 <node TEXT="ファイルシステムの信頼性" FOLDED="true" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1704630267498">
 <node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/>
 <node TEXT="GCやレプリケーションの機能がない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704632961588"/>
@@ -675,6 +678,10 @@
 <node TEXT="CopyRedBlackTreeによるレプリケーション" ID="ID_1106336919" CREATED="1703490971550" MODIFIED="1704973002324">
 <node TEXT="GCとほとんど同じ仕組みで実装する" ID="ID_1738615864" CREATED="1704973003111" MODIFIED="1704973021762"/>
 <node TEXT="実際にはCopy時に送信を同時に行う" ID="ID_1536582463" CREATED="1704973022427" MODIFIED="1704974557823"/>
+<node TEXT="socket通信が使える" ID="ID_703110643" CREATED="1705985752084" MODIFIED="1705985760495"/>
+<node TEXT="RedBlackTreeで構成されたディレクトリシステム" ID="ID_1425337861" CREATED="1705985761147" MODIFIED="1705985786882">
+<node TEXT="なのでRedBlackTreeのコピーで単純に実装できる" ID="ID_1509690636" CREATED="1705985788492" MODIFIED="1705985812755"/>
+</node>
 </node>
 <node TEXT="メモ" ID="ID_1983774695" CREATED="1705551362475" MODIFIED="1705551366046">
 <node TEXT="i-node treeをbackup, replication, gc可能であることを書きたい" ID="ID_559931709" CREATED="1705551366386" MODIFIED="1705551399134"/>
@@ -709,6 +716,7 @@
 </node>
 </node>
 <node TEXT="コード説明" ID="ID_1352482727" CREATED="1704630501155" MODIFIED="1704630507416"/>
+<node TEXT="Copyのタイミング処理" ID="ID_39116936" CREATED="1706002572872" MODIFIED="1706002587228"/>
 <node TEXT="証明のしやすさについて" ID="ID_2776247" CREATED="1703492904417" MODIFIED="1703492910899">
 <node TEXT="Stackの使用に関して" ID="ID_432827984" CREATED="1703492856041" MODIFIED="1703492863503"/>
 </node>
@@ -731,5 +739,41 @@
 <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_1837705741" CREATED="1704631962837" MODIFIED="1704631974676"/>
 <node TEXT="Christieを用いている" ID="ID_703384422" CREATED="1704631982827" MODIFIED="1704631995001"/>
 </node>
+<node TEXT="バックアップやGCのタイミング" POSITION="left" ID="ID_1968325106" CREATED="1705995867783" MODIFIED="1705995947002">
+<node TEXT="木の操作の度にGCしていては効率が悪い" ID="ID_1270257607" CREATED="1705995886579" MODIFIED="1705995983113">
+<node TEXT="システムの状態によって処理を切り替える" ID="ID_835268540" CREATED="1705995987307" MODIFIED="1705995998232"/>
+<node TEXT="メモリがこれくらい使われている" ID="ID_708465587" CREATED="1705996000486" MODIFIED="1705996008587"/>
+<node TEXT="木の高さがこれくらい" ID="ID_1934598628" CREATED="1705996009257" MODIFIED="1705996031354"/>
+</node>
+<node TEXT="なのでGCのタイミング調整が必要" ID="ID_170776289" CREATED="1705996050869" MODIFIED="1705996064159"/>
+<node TEXT="GCを実行するか否かを切り替える必要がある" ID="ID_1199737568" CREATED="1705996069993" MODIFIED="1705996085988"/>
+<node TEXT="処理を切り替える方法" ID="ID_1407643935" CREATED="1705996106051" MODIFIED="1705996112103">
+<node TEXT="popWhenEmpty" ID="ID_1257912829" CREATED="1705995877759" MODIFIED="1705995885499">
+<node TEXT="Stackの状態によって処理を切り替える" ID="ID_886354624" CREATED="1705995949042" MODIFIED="1705995962045"/>
+</node>
+<node TEXT="つまりContextの状態で切り替えることは可能" ID="ID_329144789" CREATED="1705996126760" MODIFIED="1705996137063"/>
+<node TEXT="足りないのは" ID="ID_1622130118" CREATED="1705996115915" MODIFIED="1705996119770">
+<node TEXT="物理的なシステムの状態を検知する" ID="ID_1564229654" CREATED="1705996138349" MODIFIED="1705996160843">
+<node TEXT="meta的" ID="ID_1276371991" CREATED="1705996165959" MODIFIED="1705996168549"/>
+</node>
+<node TEXT="木の状態を知る" ID="ID_1036632951" CREATED="1705996178150" MODIFIED="1705996183527"/>
+</node>
+</node>
+</node>
+<node TEXT="レプリケーション手法" POSITION="left" ID="ID_1667606869" CREATED="1705990967981" MODIFIED="1705990975745">
+<node TEXT="bin log" ID="ID_1578494368" CREATED="1705990975951" MODIFIED="1705990978180"/>
+<node TEXT="WAL" ID="ID_173341311" CREATED="1705991115261" MODIFIED="1705991117448">
+<node TEXT="Write Ahead Logging" ID="ID_885834048" CREATED="1705991256045" MODIFIED="1705991267446"/>
+<node TEXT="書き込み前にログを作成する" ID="ID_420054269" CREATED="1705991269014" MODIFIED="1705991282168"/>
+</node>
+<node TEXT="postgres" ID="ID_1145631818" CREATED="1705990978764" MODIFIED="1705991044845">
+<node TEXT="ストリーミング" ID="ID_185225230" CREATED="1705991045169" MODIFIED="1705991049261">
+<node TEXT="クラスタ単位のWALを使用" ID="ID_408924701" CREATED="1705991149565" MODIFIED="1705991173466"/>
+</node>
+<node TEXT="ロジカル" ID="ID_1849732950" CREATED="1705991049947" MODIFIED="1705991052987">
+<node TEXT="DBやテーブル単位のWALを使用" ID="ID_978332518" CREATED="1705991174849" MODIFIED="1705991208124"/>
+</node>
+</node>
+</node>
 </node>
 </map>