Mercurial > hg > Papers > 2024 > matac-master
changeset 43:6e3720c12b23
gc timing
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 23 Jan 2024 18:35:35 +0900 |
| parents | a6031e4cd85a |
| children | a556d22b4ebd |
| files | Paper/fig/timing.drawio Paper/fig/timing.png Paper/images/rbtree_bkp.drawio Paper/master_paper.lol Paper/master_paper.pdf Paper/master_paper.tex Paper/src/isEmpty.cbc |
| diffstat | 7 files changed, 236 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/fig/timing.drawio Tue Jan 23 18:35:35 2024 +0900 @@ -0,0 +1,59 @@ +<mxfile host="65bd71144e"> + <diagram id="nG00YISbjDC7b9rnUGSf" name="Page-1"> + <mxGraphModel dx="165" dy="692" 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="5" style="edgeStyle=none;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="2" target="3"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="2" value="" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="160" y="320" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="8" style="edgeStyle=none;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="3" target="7"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="15" value="≦ 80" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="8"> + <mxGeometry x="-0.25" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="9" style="edgeStyle=orthogonalEdgeStyle;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="3" target="6"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="17" value="≧ 80" style="edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];" vertex="1" connectable="0" parent="9"> + <mxGeometry x="-0.4" relative="1" as="geometry"> + <mxPoint as="offset"/> + </mxGeometry> + </mxCell> + <mxCell id="3" value="memory usage check" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="320" y="320" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="10" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;" edge="1" parent="1" source="6" target="7"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="6" value="GC" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="390" y="400" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="7" value="<meta charset="utf-8"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: center; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(251, 251, 251); text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial; float: none; display: inline !important;">Memory</span><br style="border-color: var(--border-color); color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: center; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(251, 251, 251); text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: center; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(251, 251, 251); text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial; float: none; display: inline !important;">Allocation</span>" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="520" y="320" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="13" style="edgeStyle=orthogonalEdgeStyle;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;" edge="1" parent="1" source="11" target="12"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="11" value="" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="160" y="240" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="12" value="Memory<br>Allocation" style="rounded=0;whiteSpace=wrap;html=1;" vertex="1" parent="1"> + <mxGeometry x="520" y="240" width="80" height="40" as="geometry"/> + </mxCell> + <mxCell id="18" value="①" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="110" y="245" width="60" height="30" as="geometry"/> + </mxCell> + <mxCell id="19" value="②" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="110" y="325" width="60" height="30" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/images/rbtree_bkp.drawio Tue Jan 23 18:35:35 2024 +0900 @@ -0,0 +1,116 @@ +<mxfile host="65bd71144e"> + <diagram id="z3zCV0kYmXK18lSSGJo1" name="Page-1"> + <mxGraphModel dx="544" dy="461" 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="53" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="42" target="43"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="56" style="edgeStyle=none;html=1;entryX=0.317;entryY=0.496;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="42" target="44"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="42" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="190" y="110" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="54" style="edgeStyle=none;html=1;entryX=0.631;entryY=0.348;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="45"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="55" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="43" target="46"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="43" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="160" y="150" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="57" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="44" target="47"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="44" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="220" y="150" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="45" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="130" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="46" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="190" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="47" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="250" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="58" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="49" target="43"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="59" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="49" target="50"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="49" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="250" y="110" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="60" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="50" target="52"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="50" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="280" y="150" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="52" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="310" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="81" style="edgeStyle=none;html=1;endArrow=classic;endFill=1;" edge="1" parent="1" source="61" target="49"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="61" value="From" style="text;html=1;strokeColor=default;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="240" y="50" width="40" height="30" as="geometry"/> + </mxCell> + <mxCell id="62" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" target="67"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="420" y="120" as="sourcePoint"/> + </mxGeometry> + </mxCell> + <mxCell id="63" style="edgeStyle=none;html=1;entryX=0.317;entryY=0.496;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;startArrow=none;" edge="1" parent="1" source="64" target="69"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="420" y="120" as="sourcePoint"/> + </mxGeometry> + </mxCell> + <mxCell id="65" style="edgeStyle=none;html=1;entryX=0.631;entryY=0.348;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" source="67" target="70"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="66" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="67" target="71"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="67" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="380" y="150" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="68" style="edgeStyle=none;html=1;endArrow=none;endFill=0;" edge="1" parent="1" source="69" target="72"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="69" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="440" y="150" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="70" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="350" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="71" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="410" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="72" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="470" y="190" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="79" value="" style="edgeStyle=none;html=1;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=none;endFill=0;" edge="1" parent="1" target="64"> + <mxGeometry relative="1" as="geometry"> + <mxPoint x="420" y="120" as="sourcePoint"/> + <mxPoint x="450" y="160" as="targetPoint"/> + </mxGeometry> + </mxCell> + <mxCell id="64" value="" style="shape=waypoint;sketch=0;fillStyle=solid;size=6;pointerEvents=1;points=[];fillColor=none;resizable=0;rotatable=0;perimeter=centerPerimeter;snapToPoint=1;" vertex="1" parent="1"> + <mxGeometry x="410" y="110" width="20" height="20" as="geometry"/> + </mxCell> + <mxCell id="82" style="edgeStyle=none;html=1;entryX=0.567;entryY=1.033;entryDx=0;entryDy=0;entryPerimeter=0;endArrow=classic;endFill=1;" edge="1" parent="1" source="80" target="64"> + <mxGeometry relative="1" as="geometry"/> + </mxCell> + <mxCell id="80" value="To" style="text;html=1;strokeColor=default;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;" vertex="1" parent="1"> + <mxGeometry x="400" y="50" width="40" height="30" as="geometry"/> + </mxCell> + </root> + </mxGraphModel> + </diagram> +</mxfile> \ No newline at end of file
--- a/Paper/master_paper.lol Tue Jan 23 14:38:18 2024 +0900 +++ b/Paper/master_paper.lol Tue Jan 23 18:35:35 2024 +0900 @@ -6,5 +6,6 @@ \contentsline {lstlisting}{\numberline {3.5}Treeの仕様}{15}{}% \contentsline {lstlisting}{\numberline {3.6}RedBlackTreeの実装}{16}{}% \contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの実装の型定義}{16}{}% -\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{29}{}% -\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{31}{}% +\contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{29}{}% +\contentsline {lstlisting}{\numberline {6.1}CopyRedBlackTreeの実装}{30}{}% +\contentsline {lstlisting}{\numberline {6.2}CopyRedBlackTreeのアルゴリズム}{32}{}%
--- a/Paper/master_paper.tex Tue Jan 23 14:38:18 2024 +0900 +++ b/Paper/master_paper.tex Tue Jan 23 18:35:35 2024 +0900 @@ -663,8 +663,8 @@ コミットが完了するとそれ以前の状態に戻すことはできないが， データのバックアップをとっておくことで復元を行う． -今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， -データの復元が行える仕組みを構築することを考える． +RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し， +データの復元が行える仕組みを考える． 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす． つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる． よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える． @@ -686,6 +686,7 @@ 災害などによって発生するシステム障害を防止することや， アクセス分散によるネットワーク負荷の低減につながる． そのため，GearsFileSystemにおいてもレプリケーションの機能を実装したい． + GearsFileSystemではディレクトリをRedBlackTreeによって構成しており， RedBlackTreeから全てのデータにアクセス可能である． よって，RedBlackTreeのコピーを行うことによって， @@ -710,9 +711,53 @@ 通信の仕組みが必要である． レプリケーションを実装する際は通信の仕組みについて考える必要がある． -\section{GearsFileSystemのバックアップ} +既存のDBにおけるレプリケーション手法は同期のタイミングやレプリカの作成単位によっていくつか種類がある． + +\section{コピー実行のタイミング} + +GCやレプリケーション，バックアップはそれを実行するタイミングが重要である． +GCはメモリの使用状況に応じて実行される． +例えば，RedBlackTreeに新規ノードを追加する際にメモリが不足した場合などが +GCを実行するタイミングとして挙げられる． +レプリケーションは同期のタイミングがあり，同期型，非同期型，準同期型が挙げられる． +また，バックアップは1日に1回，週に1回など定期的な実行をする． +そのため，RedBlackTreeのコピーにコピー実行のタイミングを制御する機構が必要である． +GearsOSは拡張性の高いCbCによって記述され，本来実行したい処理に追加の処理を挿入することが比較的容易に可能である． +図\ref{fig:GCTiming}にGC実行処理の挿入の仕組みの例を示す． + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=160mm]{fig/timing.png} + \end{center} + \caption{GC実行処理の挿入} + \label{fig:GCTiming} +\end{figure} -レプリケーションを作成した際でも，データのバックアップを別個で取ることは必要である． +矢印は軽量継続であり， +\textcircled{\scriptsize 1}ではメモリアロケーションを必要とする本来行いたい処理を表している． +\textcircled{\scriptsize 2}はメモリ使用率をチェックするCodeGearを挿入し， +使用率が80\%以上の場合にGCを実行する． +メモリ使用率をチェックするCodeGearは条件によって実行するCodeGearを切り替えるものであり， +既存のGearsOSのコードにもこのような処理を行うものは存在し， +例としてSingleLinkedStackのコードの一部をソースコード\ref{src:isEmpty.cbc}に示す． + +\lstinputlisting[label=src:isEmpty.cbc, caption=実行するCodeGearの切り替えのコード]{src/isEmpty.cbc} + +CodeGearは遷移先のCodeGearの参照を持つ必要があるため， +inputDataGearとしてnextとwhenEmptyを渡している． +条件分岐は通常のif文で行われ，条件ごとに次のCodeGearを指定している． + +このようにして，条件分岐をして実行するCodeGearを切り替えることができる． +しかし，GCは本来行いたい処理ではなくメタレベルの処理である． +そのため，GCへの切り替えにおいてソースコード\ref{src:isEmpty.cbc}のようなコードを記述すると， +ノーマルレベルとメタレベルが混在するCodeGearとなってしまう問題がある． + +\section{GCとレプリケーションとバックアップ} + +ここまででRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べた． +そこから，GC，レプリケーション，バックアップをRedBlackTreeのコピーを基礎とする， +統一的な仕組みにより実装することが考えられる． + \chapter{CopyRedBlackTreeの実装} @@ -814,6 +859,8 @@ スタンドアロンなDBの形にするか， その他の方法でポータビリティを向上させる手法を考えたい． +\section{GCタイミングに必要な処理の自動挿入} + % %謝辞
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/src/isEmpty.cbc Tue Jan 23 18:35:35 2024 +0900 @@ -0,0 +1,7 @@ +__code isEmptySingleLinkedStack(struct SingleLinkedStack* stack, __code next(...), __code whenEmpty(...)) { + if (stack->top) { + goto next(...); + } else { + goto whenEmpty(...); + } +} \ No newline at end of file