Mercurial > hg > Papers > 2024 > matac-master

changeset 52:886c8902f16e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
copy context
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Wed, 31 Jan 2024 16:27:14 +0900
parents bc69a109778c
children c7ed59e807a5
files Paper/fig/copy_context.pdf Paper/master_paper.lol Paper/master_paper.pdf Paper/master_paper.tex TODO.md mindmaps/gears_fs_db.mm
diffstat 6 files changed, 115 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/fig/copy_context.pdf has changed
--- a/Paper/master_paper.lol	Tue Jan 30 19:51:40 2024 +0900
+++ b/Paper/master_paper.lol	Wed Jan 31 16:27:14 2024 +0900
@@ -8,6 +8,6 @@
 \contentsline {lstlisting}{\numberline {3.7}RedBlackTreeの実装の型定義}{16}{}%
 \contentsline {lstlisting}{\numberline {3.8}Nodeの型定義}{17}{}%
 \contentsline {lstlisting}{\numberline {3.9}ALLOCATEの定義}{18}{}%
-\contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{28}{}%
+\contentsline {lstlisting}{\numberline {5.1}実行するCodeGearの切り替えのコード}{29}{}%
 \contentsline {lstlisting}{\numberline {6.1}Tree Interfaceの使用定義(Copy追加後)}{32}{}%
 \contentsline {lstlisting}{\numberline {6.2}RedBlackTreeの実装の型定義(Copy追加後)}{32}{}%
Binary file Paper/master_paper.pdf has changed
--- a/Paper/master_paper.tex	Tue Jan 30 19:51:40 2024 +0900
+++ b/Paper/master_paper.tex	Wed Jan 31 16:27:14 2024 +0900
@@ -666,7 +666,7 @@
 Mark \& Sweep GCやReference counting GCの場合は，
 GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある．
 また，同様の構造をコピーするのみで実装することによって，
-データの透過性の確保がしやすい．
+データの持続性の確保がしやすい．
 ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ．
 そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い．
 
@@ -741,20 +741,6 @@
 
 既存のDBにおけるレプリケーション手法は同期のタイミングやレプリカの作成単位によっていくつか種類がある．
 
-\section{}
-
-TODO: Contextを含めたコピーの説
-
-\ref{fig:CopyContext}
-
-\begin{figure}[ht]
-  \begin{center}
-      \includegraphics[width=160mm]{fig/copy_context.png}
-  \end{center}
-  \caption{別Contextへのコピー}
-  \label{fig:CopyContext}
-\end{figure}
-
 \section{コピー実行のタイミング}
 
 GCやレプリケーション，バックアップはそれを実行するタイミングが重要である．
@@ -795,6 +781,48 @@
 ノーマルレベルとメタレベルが混在するCodeGearとなってしまう問題がある．
 これは，GC処理を自動的に
 
+\section{別Contextへのコピー}
+
+\begin{figure}[ht]
+  \begin{center}
+      \includegraphics[width=160mm]{fig/copy_context.pdf}
+  \end{center}
+  \caption{別Contextへのコピー}
+  \label{fig:CopyContext}
+\end{figure}
+
+図\ref{fig:CopyContext}にContextとCode Table，Data Tableの関係と，
+の複数のContextがある状態を示す．
+ContextはそれぞれCode TableとData Tableを持つ．
+DataGearをALLOCATEするとData Tableのヒープ領域にそのDataGear分の領域が確保される．
+これらの複数のContextはContextキューで管理され，
+順次実行される．
+
+RedBlackTreeは別のContextへコピーすると良い．
+同じContextへコピーする場合，GCはFromとToの領域が同じヒープ領域に置かれることになる．
+ヒープ領域を共有してしまうと，FromからToへの切り替えがしづらい．
+また，すでにそのヒープ領域でフラグメンテーションが起きている可能性があり，
+Copying GCの利点であるコンパクションができない．
+レプリケーションの場合，別のノードでは別のContextが動いているため，
+同じContextにコピーできるだけではレプリケーション機能は実現できない．
+別のContextへコピーすると，GCの場合，FromとToの領域が別のヒープ領域に置かれる．
+そのためContextを切り替えることによってFromからToへの切り替えができ，
+まっさらな状態のヒープ領域にコピーを行えるため，
+リニアアロケーションをしていればコンパクションが発生する．
+
+動的にバックアップする際のコピーを考える．
+別Contextへコピーする場合，ディスクをContextのData Tableのヒープ領域と捉え，
+単純にディスク書き込みを行う．
+RedBlackTreeは非破壊であり，複数のルートノードによってバージョン管理されている．
+そのため，あるバージョンのバックアップをリストアしたい場合がある．
+現在のバージョンをディスク上にある特定のバージョンに切り替える場合，
+現在のバージョンへの書き込みの最中にバージョンが切り替わってしまうとデータの一貫性を損なう．
+そのため，データリストア時の一貫性を確保する仕組みが必要となる．
+また，バージョン付きのバックアップは無尽蔵にデータが増加していく問題がある．
+それは，任意のタイミングでデータを区切ることで解決できる．
+仮想的にData Tableを作成し，そのヒープ領域(ディスク)に対してデータをコピーする．
+過去のData Tableのバージョンに戻りたい場合があるため，
+Data Tableは前のData Tableの参照を持つ．
 
 
 \chapter{CopyRedBlackTreeの実装}
--- a/TODO.md	Tue Jan 30 19:51:40 2024 +0900
+++ b/TODO.md	Wed Jan 31 16:27:14 2024 +0900
@@ -14,11 +14,15 @@
 - [x] ALLOCの説明
 - [x] 一度通して見直し(2024/01/30)
 
+- [x] 別Contextへの書き込み
 - [ ] DGMによる分散ファイルシステム
-- [ ] 別Contextへの書き込み
 - [ ] Copy時の一貫性
 - [ ] 実装の説明
 - [ ] 評価
 - [ ] まとめ
 - [ ] 今後の課題
-- [ ] 図の清書
\ No newline at end of file
+- [ ] 図の清書
+
+確認したいこと
+
+- [ ] ある程度木が大きくなると動かなくなる(詳細未調査)
\ No newline at end of file
--- a/mindmaps/gears_fs_db.mm	Tue Jan 30 19:51:40 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Wed Jan 31 16:27:14 2024 +0900
@@ -1,6 +1,6 @@
 <map version="freeplane 1.9.8">
 <!--To view this file, download free mind mapping software Freeplane from https://www.freeplane.org -->
-<node TEXT="GearsOS上のファイルシステムとDBの信頼性(仮)" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1706520588455" STYLE="oval">
+<node TEXT="GearsOS上のファイルシステムとDBの信頼性(仮)" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1706679674396" STYLE="oval">
 <font SIZE="18"/>
 <hook NAME="MapStyle" zoom="0.8">
     <properties edgeColorConfiguration="#808080ff,#ff0000ff,#0000ffff,#00ff00ff,#ff00ffff,#00ffffff,#7c0000ff,#00007cff,#007c00ff,#7c007cff,#007c7cff,#7c7c00ff" associatedTemplateLocation="template:/standard-1.6-noEdgeColor.mm" fit_to_viewport="false"/>
@@ -417,22 +417,6 @@
 </node>
 <node TEXT="評価方法" POSITION="right" ID="ID_1979397312" CREATED="1699850131177" MODIFIED="1699850137060"/>
 <node TEXT="erasure coding" POSITION="right" ID="ID_1412038732" CREATED="1706607173301" MODIFIED="1706607177606"/>
-<node TEXT="別ContextへのCopy" POSITION="right" ID="ID_1256969896" CREATED="1706608691732" MODIFIED="1706610433076">
-<node TEXT="新たにヒープ領域を確保することによりコンパクションされる" ID="ID_1570751579" CREATED="1706610433391" MODIFIED="1706610495922">
-<node TEXT="少なくとも論理的には" ID="ID_1203172749" CREATED="1706610530004" MODIFIED="1706610535897"/>
-</node>
-<node TEXT="別ノードにコピーすることが可能になる" ID="ID_18132759" CREATED="1706610497553" MODIFIED="1706610550820">
-<node TEXT="別ノードは別のContextを持っているため" ID="ID_261769933" CREATED="1706610552438" MODIFIED="1706610561888"/>
-</node>
-<node TEXT="Contextキュー" ID="ID_441803002" CREATED="1706610609324" MODIFIED="1706610615562"/>
-<node TEXT="無尽蔵に大きくなるデータ" ID="ID_371220284" CREATED="1706610724283" MODIFIED="1706610735719">
-<node TEXT="ある地点で分離可能であるように区切る必要がある" ID="ID_31321201" CREATED="1706610736028" MODIFIED="1706610750038"/>
-<node TEXT="仮想的に別ContextのData tableを用意" ID="ID_517308151" CREATED="1706610750494" MODIFIED="1706610780803">
-<node TEXT="Data table同士を接続してデータを持続させる" ID="ID_109885431" CREATED="1706610791990" MODIFIED="1706610969823"/>
-</node>
-</node>
-<node TEXT="ディスクへの書き込み" ID="ID_1313978495" CREATED="1706611103173" MODIFIED="1706611107617"/>
-</node>
 <node TEXT="章立て" POSITION="left" ID="ID_378600647" CREATED="1699848424709" MODIFIED="1706520588455" HGAP_QUANTITY="8 pt" VSHIFT_QUANTITY="-117 pt">
 <node TEXT="要旨" FOLDED="true" ID="ID_1862870052" CREATED="1705571598152" MODIFIED="1705571620770">
 <node TEXT="CbCでGearsOSを開発している" ID="ID_1596447160" CREATED="1705571621398" MODIFIED="1705571639432"/>
@@ -746,11 +730,11 @@
 </node>
 <node TEXT="今後" ID="ID_87524419" CREATED="1702112509364" MODIFIED="1702112512270"/>
 </node>
-<node TEXT="修論で言いたいこと" POSITION="right" ID="ID_1194781583" CREATED="1701690732709" MODIFIED="1701696321975" HGAP_QUANTITY="29 pt" VSHIFT_QUANTITY="134.25 pt">
+<node TEXT="修論で言いたいこと" POSITION="right" ID="ID_1194781583" CREATED="1701690732709" MODIFIED="1706679669392" HGAP_QUANTITY="15.5 pt" VSHIFT_QUANTITY="-0.75 pt">
 <node TEXT="RedBlackTreeのCopyでreplicationによる信頼性の向上とGCの仕組みを実装した" ID="ID_729318951" CREATED="1701690742376" MODIFIED="1701691473760"/>
 <node TEXT="ファイルシステムとDBを同一システムとして実装してしまおうという試みの一部" ID="ID_803529790" CREATED="1701693180112" MODIFIED="1701696299725"/>
 </node>
-<node TEXT="DataGearManagerによる分散ファイルシステム" POSITION="right" ID="ID_1005780153" CREATED="1703315001066" MODIFIED="1703315085575">
+<node TEXT="DataGearManagerによる分散ファイルシステム" POSITION="right" ID="ID_1005780153" CREATED="1703315001066" MODIFIED="1706679671263" HGAP_QUANTITY="10.25 pt" VSHIFT_QUANTITY="-8.25 pt">
 <node TEXT="ikkiさんの研究" ID="ID_557379148" CREATED="1704630869165" MODIFIED="1704630876474"/>
 <node TEXT="DataGearManager" ID="ID_521285238" CREATED="1705646099321" MODIFIED="1705646107853">
 <node TEXT="" ID="ID_1859471968" CREATED="1705646108176" MODIFIED="1705646108176"/>
@@ -758,6 +742,68 @@
 <node TEXT="分散ファイルシステムのトポロジー形成" ID="ID_1837705741" CREATED="1704631962837" MODIFIED="1704631974676"/>
 <node TEXT="Christieを用いている" ID="ID_703384422" CREATED="1704631982827" MODIFIED="1704631995001"/>
 </node>
+<node TEXT="別ContextへのCopy" POSITION="right" ID="ID_1256969896" CREATED="1706608691732" MODIFIED="1706679674395" HGAP_QUANTITY="108.5 pt" VSHIFT_QUANTITY="371.99999 pt">
+<node TEXT="新たにヒープ領域を確保することによりコンパクションされる" ID="ID_1570751579" CREATED="1706610433391" MODIFIED="1706610495922">
+<node TEXT="少なくとも論理的には" ID="ID_1203172749" CREATED="1706610530004" MODIFIED="1706610535897"/>
+</node>
+<node TEXT="別ノードにコピーすることが可能になる" ID="ID_18132759" CREATED="1706610497553" MODIFIED="1706610550820">
+<node TEXT="別ノードは別のContextを持っているため" ID="ID_261769933" CREATED="1706610552438" MODIFIED="1706610561888"/>
+</node>
+<node TEXT="無尽蔵に大きくなるデータ" ID="ID_371220284" CREATED="1706610724283" MODIFIED="1706610735719">
+<node TEXT="ある地点で分離可能であるように区切る必要がある" ID="ID_31321201" CREATED="1706610736028" MODIFIED="1706610750038"/>
+<node TEXT="仮想的に別ContextのData tableを用意" ID="ID_517308151" CREATED="1706610750494" MODIFIED="1706610780803">
+<node TEXT="Data table同士を接続してデータを持続させる" ID="ID_109885431" CREATED="1706610791990" MODIFIED="1706610969823"/>
+</node>
+</node>
+<node TEXT="ディスクへの書き込み" ID="ID_1313978495" CREATED="1706611103173" MODIFIED="1706611107617">
+<node TEXT="リストア方法" ID="ID_1201150664" CREATED="1706611422642" MODIFIED="1706611428892">
+<node TEXT="Contextヒープとディスク上のデータ形式がbit単位で一致していればコピーするだけで済む......" ID="ID_1094786351" CREATED="1706611580254" MODIFIED="1706611621038"/>
+</node>
+<node TEXT="リストアのタイミング" ID="ID_484916387" CREATED="1706611430637" MODIFIED="1706611800129"/>
+</node>
+<node TEXT="Contextキュー" ID="ID_1047057445" CREATED="1706679759621" MODIFIED="1706679771873">
+<node TEXT="Contextが順次参照される" ID="ID_1047250748" CREATED="1706679793618" MODIFIED="1706679812635"/>
+<node TEXT="単純にコピーするだけであればコピー元-&gt;コピー先の実行でよい" ID="ID_1030846182" CREATED="1706679825615" MODIFIED="1706679860026">
+<node TEXT="read replicaは問題ない" ID="ID_759103130" CREATED="1706679997994" MODIFIED="1706680004839"/>
+</node>
+<node TEXT="writeノードを増やす場合は？" ID="ID_398140096" CREATED="1706680011118" MODIFIED="1706680102288">
+<node TEXT="トランザクション管理が必要" ID="ID_934097308" CREATED="1706680102768" MODIFIED="1706680740608"/>
+<node TEXT="ACID" ID="ID_668349518" CREATED="1706680871405" MODIFIED="1706680874016"/>
+</node>
+</node>
+<node TEXT="説明" ID="ID_1566388365" CREATED="1706681655595" MODIFIED="1706681658850">
+<node TEXT="Contextとデータの関係" ID="ID_1454555004" CREATED="1706682841186" MODIFIED="1706682863894">
+<node TEXT="ContextはCode tableとData tableをそれぞれ持つ" ID="ID_1112158379" CREATED="1706682868410" MODIFIED="1706682889001"/>
+<node TEXT="ALLOCATIONするとData tableのヒープ領域に，そのDataGear分の領域が確保される" ID="ID_1845935915" CREATED="1706682889540" MODIFIED="1706682925919"/>
+<node TEXT="Contextが複数ある場合" ID="ID_1202004282" CREATED="1706682969341" MODIFIED="1706682981045">
+<node TEXT="ContextキューでContextが切り替えられる" ID="ID_1938589889" CREATED="1706682982216" MODIFIED="1706683001147"/>
+</node>
+</node>
+<node TEXT="別Contextにコピーするとよい" ID="ID_497217227" CREATED="1706681659200" MODIFIED="1706682209127"/>
+<node TEXT="別Contextでなかった場合" ID="ID_814918893" CREATED="1706681671376" MODIFIED="1706681678666">
+<node TEXT="gcの場合" ID="ID_1798592055" CREATED="1706682243505" MODIFIED="1706682247016">
+<node TEXT="コピーがContextのヒープ領域を共有してしまう" ID="ID_754213404" CREATED="1706681679033" MODIFIED="1706681732770"/>
+<node TEXT="GCにおけるコンパクションがしづらい" ID="ID_638713116" CREATED="1706681733377" MODIFIED="1706681761877"/>
+</node>
+<node TEXT="レプリケーションの場合" ID="ID_1498053901" CREATED="1706682256823" MODIFIED="1706682272029">
+<node TEXT="別ノードでは別のContextが動いている" ID="ID_662166719" CREATED="1706682266069" MODIFIED="1706682286844"/>
+<node TEXT="なのでそもそもレプリケーションできない" ID="ID_381677948" CREATED="1706682287142" MODIFIED="1706682340929"/>
+</node>
+</node>
+<node TEXT="別にすると" ID="ID_652852110" CREATED="1706681763993" MODIFIED="1706681768496">
+<node TEXT="gcの場合" ID="ID_239429338" CREATED="1706681768979" MODIFIED="1706681890584">
+<node TEXT="ヒープ領域が完全に分けられる" ID="ID_1991432215" CREATED="1706681878410" MODIFIED="1706681904308"/>
+<node TEXT="前のContextから切り替えることでFrom To入れ替えができる" ID="ID_1287374124" CREATED="1706681905021" MODIFIED="1706682233872"/>
+</node>
+<node TEXT="レプリケーションの場合" ID="ID_1842008675" CREATED="1706682237947" MODIFIED="1706682320750">
+<node TEXT="レプリケーションできるようになる" ID="ID_1747513810" CREATED="1706682321617" MODIFIED="1706682348973"/>
+</node>
+</node>
+<node TEXT="バックアップの場合" ID="ID_1960787415" CREATED="1706683084193" MODIFIED="1706683089437">
+<node TEXT="ディスクを仮想的な別Contextのヒープ領域として捉える" ID="ID_212019334" CREATED="1706683089813" MODIFIED="1706683124532"/>
+</node>
+</node>
+</node>
 <node TEXT="バックアップやGCのタイミング" FOLDED="true" 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"/>