# HG changeset patch
# User matac42 <matac@cr.ie.u-ryukyu.ac.jp>
# Date 1704962623 -32400
# Node ID dcb4bb1e6bee5de7c425315c2e11cb3b79403f46
# Parent  91b67726191cc1e916d03bc01752f77ce3c347aa
...

diff -r 91b67726191c -r dcb4bb1e6bee Paper/fig/rbtree_gc.drawio
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/fig/rbtree_gc.drawio	Thu Jan 11 17:43:43 2024 +0900
@@ -0,0 +1,151 @@
+<mxfile host="65bd71144e">
+    <diagram id="rADU1YbqsmjT1hZ3yXGo" name="Page-1">
+        <mxGraphModel dx="920" dy="728" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0">
+            <root>
+                <mxCell id="0"/>
+                <mxCell id="1" parent="0"/>
+                <mxCell id="52" value="" style="rounded=1;whiteSpace=wrap;html=1;fillColor=none;" vertex="1" parent="1">
+                    <mxGeometry x="480" y="110" width="220" height="210" as="geometry"/>
+                </mxCell>
+                <mxCell id="51" value="" style="rounded=1;whiteSpace=wrap;html=1;fillColor=none;" vertex="1" parent="1">
+                    <mxGeometry x="80" y="110" width="300" height="210" as="geometry"/>
+                </mxCell>
+                <mxCell id="9" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;entryX=0.675;entryY=0.025;entryDx=0;entryDy=0;endArrow=none;endFill=0;entryPerimeter=0;" edge="1" parent="1" source="2" target="4">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="10" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.325;entryY=0.05;entryDx=0;entryDy=0;endArrow=none;endFill=0;entryPerimeter=0;" edge="1" parent="1" source="2" target="3">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="2" value="A" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="170" y="150" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="20" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;endArrow=none;endFill=0;entryX=0.292;entryY=0.043;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="3" target="19">
+                    <mxGeometry relative="1" as="geometry">
+                        <mxPoint x="261" y="271" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="3" value="E" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;strokeColor=#FF8000;fontColor=#FF9933;" vertex="1" parent="1">
+                    <mxGeometry x="210" y="210" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="11" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;endArrow=none;endFill=0;entryX=0.722;entryY=0.042;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="4" target="5">
+                    <mxGeometry relative="1" as="geometry">
+                        <mxPoint x="120" y="270" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="12" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.27;entryY=0.042;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="4" target="6">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="4" value="B" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="130" y="210" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="5" value="C" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="90" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="6" value="D" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="170" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="13" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;entryX=1;entryY=0;entryDx=0;entryDy=0;endArrow=none;endFill=0;" edge="1" parent="1" source="7" target="4">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="22" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.325;entryY=0.025;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="7" target="14">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="7" value="A" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="250" y="150" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="18" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;endArrow=none;endFill=0;entryX=0.303;entryY=0.036;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="14" target="15">
+                    <mxGeometry relative="1" as="geometry">
+                        <mxPoint x="342" y="271" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="14" value="E" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="290" y="210" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="15" value="G" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="330" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="19" value="F" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;strokeColor=#FF8000;fontColor=#FF9933;" vertex="1" parent="1">
+                    <mxGeometry x="250" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="23" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;entryX=0.675;entryY=0.025;entryDx=0;entryDy=0;endArrow=none;endFill=0;entryPerimeter=0;" edge="1" parent="1" source="25" target="30">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="24" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.325;entryY=0.05;entryDx=0;entryDy=0;endArrow=none;endFill=0;entryPerimeter=0;" edge="1" parent="1" source="25" target="27">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="25" value="A" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="570" y="150" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="26" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.275;entryY=0.042;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="27" target="39">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="27" value="E" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="610" y="210" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="28" style="edgeStyle=none;html=1;exitX=0;exitY=1;exitDx=0;exitDy=0;endArrow=none;endFill=0;entryX=0.724;entryY=0.056;entryDx=0;entryDy=0;entryPerimeter=0;" edge="1" parent="1" source="30" target="31">
+                    <mxGeometry relative="1" as="geometry">
+                        <mxPoint x="520" y="269.9999999999998" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="29" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.28;entryY=0.051;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="30" target="32">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="30" value="B" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="530" y="210" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="31" value="C" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="490" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="32" value="D" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="570" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="34" style="edgeStyle=none;html=1;exitX=1;exitY=1;exitDx=0;exitDy=0;entryX=0.325;entryY=0.025;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" target="37">
+                    <mxGeometry relative="1" as="geometry">
+                        <mxPoint x="714.1421356237308" y="154.14213562373084" as="sourcePoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="39" value="G" style="ellipse;whiteSpace=wrap;html=1;aspect=fixed;" vertex="1" parent="1">
+                    <mxGeometry x="650" y="270" width="40" height="40" as="geometry"/>
+                </mxCell>
+                <mxCell id="40" value="Old" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="160" y="110" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="41" value="Latest" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="240" y="110" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="43" value="From" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="90" y="80" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="44" value="To" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="490" y="80" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="45" value="Latest" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1">
+                    <mxGeometry x="560" y="110" width="60" height="30" as="geometry"/>
+                </mxCell>
+                <mxCell id="49" value="" style="shape=flexArrow;endArrow=classic;html=1;width=8.75;endSize=5.124999999999999;" edge="1" parent="1">
+                    <mxGeometry width="50" height="50" relative="1" as="geometry">
+                        <mxPoint x="390" y="220" as="sourcePoint"/>
+                        <mxPoint x="470" y="220" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="53" value="Copy" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="49">
+                    <mxGeometry x="-0.0625" y="4" relative="1" as="geometry">
+                        <mxPoint as="offset"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="54" value="" style="endArrow=none;html=1;fontColor=#FF9933;strokeColor=#FF8000;" edge="1" parent="1">
+                    <mxGeometry width="50" height="50" relative="1" as="geometry">
+                        <mxPoint x="140" y="334.58" as="sourcePoint"/>
+                        <mxPoint x="185" y="334.58" as="targetPoint"/>
+                    </mxGeometry>
+                </mxCell>
+                <mxCell id="57" value="" style="edgeStyle=none;html=1;strokeColor=#FF8000;fontSize=9;fontColor=#FF9933;endArrow=none;endFill=0;" edge="1" parent="1" source="56" target="51">
+                    <mxGeometry relative="1" as="geometry"/>
+                </mxCell>
+                <mxCell id="56" value="Garbage" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FF9933;fontSize=9;" vertex="1" parent="1">
+                    <mxGeometry x="90" y="320" width="60" height="30" as="geometry"/>
+                </mxCell>
+            </root>
+        </mxGraphModel>
+    </diagram>
+</mxfile>
\ No newline at end of file
diff -r 91b67726191c -r dcb4bb1e6bee Paper/fig/rbtree_gc.png
Binary file Paper/fig/rbtree_gc.png has changed
diff -r 91b67726191c -r dcb4bb1e6bee Paper/master_paper.pdf
Binary file Paper/master_paper.pdf has changed
diff -r 91b67726191c -r dcb4bb1e6bee Paper/master_paper.tex
--- a/Paper/master_paper.tex	Thu Jan 11 15:29:29 2024 +0900
+++ b/Paper/master_paper.tex	Thu Jan 11 17:43:43 2024 +0900
@@ -393,6 +393,7 @@
 
 
 \chapter{GearsFileSystemにおけるGCとレプリケーション}
+
 \section{ファイルシステムの信頼性に関する機能}
 
 ファイルシステムはデータを保持することを基本的な機能としている．
@@ -448,15 +449,56 @@
 \section{GearsFileSystemのGC}
 
 GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする．
+他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため，
+実装が簡単で，より高いスループットが期待できる．
+Mark \& Sweep GCやReference counting GCの場合は，
+GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある．
+また，同様の構造をコピーするのみで実装することによって，
+データの透過性の確保がしやすい．
+ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ．
+そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い．
 
-GearsFileSystemにおけるデータは全てRedBlackTreeに格納する．
-また，ディスク上とメモリ上のデータ構造は同一である．
-よって，RedBlackTreeの単なるコピーによってGCを行うことによって，
-データの透過性が確保され，単純なプログラムで実装することが可能と考える．
+一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される．
+一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする．
+ファイルやディレクトリの操作を行うFromのRedBlackTreeから，
+ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする．
+それにより，辿れなかったノード，つまり参照されていないノードはコピーされず，
+不要なオブジェクトが回収された状態となる．
+
+\begin{figure}[ht]
+  \begin{center}
+      \includegraphics[width=160mm]{fig/rbtree_gc.png}
+  \end{center}
+  \caption{RedBlackTReeのCopyによるGC}
+  \label{fig:TreeCopyGC}
+\end{figure}
+
+DBの重要な機能の一つにロールバックがある．
+RDBのロールバックは，
+コミットするまではトランザクションの開始時点に戻ることができる機能を持つ．
+コミットが完了するとそれ以前の状態に戻すことはできないが，
+データのバックアップをとっておくことで復元を行う．
+このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい．
+
+今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し，
+データの復元が行える仕組みを構築することを考える．
+非破壊的なTree編集はアップデートのたびに，ルートノードを増やす．
+つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる．
+よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える．
+
+ルートノードはデータのアップデート時に増えるため，
+データが際限なく増加していく問題がある．
+この問題はCopyingGCを行うことによって解決する．
+まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する．
+その後，コピーしたものはバックアップないしログとしてディスクに書き込む．
+そうすることで，データの増加によるリソースの枯渇を防ぎ，
+かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる．
 
 
 \section{GearsFileSystemのレプリケーション}
 
+
+
 \chapter{CopyRedBlackTreeの実装}
 
 データのバックアップやレプリケーション，GCの機能を実装するためには，
@@ -483,26 +525,6 @@
 \section{証明のしやすさについて}
 
 
-DBの重要な機能の一つにロールバックがある．
-RDBのロールバックは，
-コミットするまではトランザクションの開始時点に戻ることができる機能を持つ．
-コミットが完了するとそれ以前の状態に戻すことはできないが，
-データのバックアップをとっておくことで復元を行う．
-このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい．
-
-今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し，
-データの復元が行える仕組みを構築することを考える．
-非破壊的なTree編集はアップデートのたびに，ルートノードを増やす．
-つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる．
-よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える．
-
-ルートノードはデータのアップデート時に増えるため，
-データが際限なく増加していく問題がある．
-この問題はCopyingGCを行うことによって解決する．
-まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する．
-その後，コピーしたものはバックアップないしログとしてディスクに書き込む．
-そうすることで，データの増加によるリソースの枯渇を防ぎ，
-かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる．
 
 % TODO: バックアップのフローを図にしたい
 
diff -r 91b67726191c -r dcb4bb1e6bee mindmaps/gears_fs_db.mm
--- a/mindmaps/gears_fs_db.mm	Thu Jan 11 15:29:29 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Thu Jan 11 17:43:43 2024 +0900
@@ -312,6 +312,10 @@
 <node TEXT="証明しやすい" ID="ID_1313077784" CREATED="1699849438956" MODIFIED="1699849443715"/>
 <node TEXT="全ての操作が最悪でもO(log n)" ID="ID_1382477887" CREATED="1699855369743" MODIFIED="1699855390827"/>
 </node>
+<node TEXT="Rustの所有権" POSITION="right" ID="ID_612327915" CREATED="1704949737149" MODIFIED="1704949745661">
+<node TEXT="メモリを所有する変数のスコープを抜けるとメモリも解放される" ID="ID_972875880" CREATED="1704949746103" MODIFIED="1704949765401"/>
+<node TEXT="スマートポインタ" ID="ID_403762806" CREATED="1704949766082" MODIFIED="1704949771866"/>
+</node>
 <node TEXT="RBTreeを用いたCopying GC" POSITION="right" ID="ID_704559305" CREATED="1699854075442" MODIFIED="1699857013558">
 <node TEXT="RBTreeのコピーをする" ID="ID_541742554" CREATED="1699857015273" MODIFIED="1699857026447"/>
 <node TEXT="データは全てRedBlackTreeで表現される" ID="ID_1145318684" CREATED="1699857027634" MODIFIED="1699857056196">
@@ -480,28 +484,46 @@
 </node>
 <node TEXT="Rustのスマートポインタ" ID="ID_881149259" CREATED="1704696608959" MODIFIED="1704696615328"/>
 <node TEXT="CopyingGCを用いる" ID="ID_1639428535" CREATED="1704692768575" MODIFIED="1704692777490">
+<node TEXT="どのように利用するか" ID="ID_549509034" CREATED="1704696775586" MODIFIED="1704696779463">
+<node TEXT="通常のCopyingGCではヒープ領がコピーされる" ID="ID_830576894" CREATED="1704692782815" MODIFIED="1704692814222"/>
+<node TEXT="GearsFileSystemの場合は木をコピーする" ID="ID_1003156855" CREATED="1704692814851" MODIFIED="1704692831840"/>
+<node TEXT="参照しているオブジェクトは木のルートから辿れる" ID="ID_1653048898" CREATED="1704696789481" MODIFIED="1704696806177"/>
+<node TEXT="辿れるノードのみコピーするだけでGCになる" ID="ID_355389629" CREATED="1704696807343" MODIFIED="1704696829530"/>
+</node>
 <node TEXT="なぜCopyingGCなのか" ID="ID_1226680678" CREATED="1704696722580" MODIFIED="1704696736347">
 <node TEXT="全てのデータはRedBlackTreeに格納される" ID="ID_1096077315" CREATED="1704710451766" MODIFIED="1704710463902">
 <node TEXT="(使用中のデータ)" ID="ID_55750630" CREATED="1704710470136" MODIFIED="1704710480143"/>
 </node>
 <node TEXT="木を辿れば全ての生きているオブジェクトを参照することが可能" ID="ID_1690086792" CREATED="1704710464413" MODIFIED="1704710513053">
 <node TEXT="正確なGC" ID="ID_1987344082" CREATED="1704710533695" MODIFIED="1704710540754"/>
-</node>
 <node TEXT="なのでCopyingGCを簡単に適用できる" ID="ID_1935146464" CREATED="1704710513688" MODIFIED="1704710568354"/>
 </node>
-<node TEXT="どのように利用するか" ID="ID_549509034" CREATED="1704696775586" MODIFIED="1704696779463">
-<node TEXT="通常のCopyingGCではヒープ領がコピーされる" ID="ID_830576894" CREATED="1704692782815" MODIFIED="1704692814222"/>
-<node TEXT="GearsFileSystemの場合は木をコピーする" ID="ID_1003156855" CREATED="1704692814851" MODIFIED="1704692831840"/>
-<node TEXT="参照しているオブジェクトは木のルートから辿れる" ID="ID_1653048898" CREATED="1704696789481" MODIFIED="1704696806177"/>
-<node TEXT="辿れるノードのみコピーするだけでGCになる" ID="ID_355389629" CREATED="1704696807343" MODIFIED="1704696829530"/>
+<node TEXT="Mark &amp; Sweep GCよりもスループットが出ると考える" ID="ID_613272796" CREATED="1704956892675" MODIFIED="1704956939092">
+<node TEXT="RedBlackTreeは全てのファイルを持つため大きい" ID="ID_908438870" CREATED="1704956939482" MODIFIED="1704956974993"/>
+<node TEXT="参照されているノードのみをコピーするだけのCopying GCの方が相性が良い" ID="ID_502796047" CREATED="1704956975764" MODIFIED="1704957000536"/>
+</node>
 </node>
 <node TEXT="GC併用はしないのか" ID="ID_939269191" CREATED="1704696736711" MODIFIED="1704776977043">
 <node TEXT="今回は単純な実装をしたい" ID="ID_91131104" CREATED="1704776780918" MODIFIED="1704776789505">
 <node TEXT="単なる木のコピー" ID="ID_532595291" CREATED="1704776790471" MODIFIED="1704776797065"/>
 <node TEXT="証明のしやすさにつながる" ID="ID_297159546" CREATED="1704776798186" MODIFIED="1704776845819"/>
 </node>
+<node TEXT="併用するとバックアップやレプリケーションは別の仕組みにする必要がある" ID="ID_896411663" CREATED="1704957031261" MODIFIED="1704957059039"/>
 </node>
-<node TEXT="Rustのスマートポインタのような仕組みにしないのか" ID="ID_110730790" CREATED="1704696742911" MODIFIED="1704696758432"/>
+<node TEXT="Rustの所有権のような仕組みにしないのか" ID="ID_110730790" CREATED="1704696742911" MODIFIED="1704954332719">
+<node TEXT="単純な実装にしたい" ID="ID_1639528076" CREATED="1704955568322" MODIFIED="1704955577331"/>
+<node TEXT="コピーでやる方がデータの透過性を維持しやすい" ID="ID_104562515" CREATED="1704955577814" MODIFIED="1704955770934"/>
+<node TEXT="コピーの方がバックアップやレプリケーションも同様の仕組みで実装できる" ID="ID_1846713241" CREATED="1704955771362" MODIFIED="1704955798240"/>
+</node>
+<node TEXT="バックアップとして扱うことも可能" ID="ID_1170979330" CREATED="1704954394351" MODIFIED="1704954402539">
+<node TEXT="メモリ上とディスク上のデータ構造が同一" ID="ID_1687864170" CREATED="1704955435232" MODIFIED="1704955460360"/>
+<node TEXT="GCで木をコピーするようにバックアップ用のコピーを作成可能" ID="ID_1027992110" CREATED="1704955460903" MODIFIED="1704955483078"/>
+<node TEXT="From領域をバックアップとして扱うことも考えられる" ID="ID_834146670" CREATED="1704955483744" MODIFIED="1704955507082"/>
+<node TEXT="RedBlackTree自体が非破壊" ID="ID_1343358619" CREATED="1704955507787" MODIFIED="1704955517941">
+<node TEXT="データの履歴を持っている" ID="ID_996919473" CREATED="1704955518379" MODIFIED="1704955535054"/>
+<node TEXT="バージョンを持ったバックアップになる" ID="ID_813768933" CREATED="1704955535459" MODIFIED="1704955560610"/>
+</node>
+</node>
 </node>
 <node TEXT="RedBlackTreeのコピーを用いる" ID="ID_1495626047" CREATED="1704630409263" MODIFIED="1704632465291">
 <node TEXT="Copy" ID="ID_1713857745" CREATED="1699848476363" MODIFIED="1699848479936">