Mercurial > hg > Papers > 2024 > matac-master

changeset 21:dcb4bb1e6bee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Thu, 11 Jan 2024 17:43:43 +0900
parents 91b67726191c
children a3cc406f4706
files Paper/fig/rbtree_gc.drawio Paper/fig/rbtree_gc.png Paper/master_paper.pdf Paper/master_paper.tex mindmaps/gears_fs_db.mm
diffstat 5 files changed, 226 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- /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
Binary file Paper/fig/rbtree_gc.png has changed
Binary file Paper/master_paper.pdf has changed
--- 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: バックアップのフローを図にしたい
 
--- 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">