changeset 66:b036cdccbdcc

matome
author matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date Wed, 07 Feb 2024 17:24:31 +0900 (2024-02-07)
parents 47b4ddf35b1d
children e3833922c93c
files Paper/fig/rbtree_replica.drawio Paper/fig/rbtree_replica.pdf Paper/master_paper.pdf Paper/master_paper.tex TODO.md mindmaps/gears_fs_db.mm
diffstat 6 files changed, 63 insertions(+), 92 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/fig/rbtree_replica.drawio	Wed Feb 07 14:32:11 2024 +0900
+++ b/Paper/fig/rbtree_replica.drawio	Wed Feb 07 17:24:31 2024 +0900
@@ -1,13 +1,13 @@
-<mxfile host="app.diagrams.net" modified="2024-01-30T09:23:58.703Z" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/121.0.0.0 Safari/537.36" version="23.0.2" etag="vfmeqV9Lhd-g7L167kAf" type="device">
+<mxfile host="app.diagrams.net" modified="2024-02-07T08:22:19.243Z" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/121.0.0.0 Safari/537.36" etag="8bya9TPAVz95CvzbKg_k" version="23.0.2" type="device">
   <diagram id="kZjAbhT0E9gDD8kV_gd3" name="Page-1">
-    <mxGraphModel dx="760" dy="507" 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">
+    <mxGraphModel dx="1026" dy="684" 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="63" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;arcSize=30;fontSize=14;" parent="1" vertex="1">
+        <mxCell id="63" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;arcSize=30;fontSize=14;dashed=1;" parent="1" vertex="1">
           <mxGeometry x="450" y="382.5" width="260" height="245" as="geometry" />
         </mxCell>
-        <mxCell id="62" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;arcSize=30;fontSize=14;" parent="1" vertex="1">
+        <mxCell id="62" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=none;arcSize=30;fontSize=14;dashed=1;" parent="1" vertex="1">
           <mxGeometry x="70" y="80" width="640" height="270" as="geometry" />
         </mxCell>
         <mxCell id="2" value="" style="rounded=1;whiteSpace=wrap;html=1;fillColor=none;fontSize=14;" parent="1" vertex="1">
Binary file Paper/fig/rbtree_replica.pdf has changed
Binary file Paper/master_paper.pdf has changed
--- a/Paper/master_paper.tex	Wed Feb 07 14:32:11 2024 +0900
+++ b/Paper/master_paper.tex	Wed Feb 07 17:24:31 2024 +0900
@@ -1013,7 +1013,6 @@
 CopyRedBlackTreeは木を単純にコピーする機能であるため,
 RedBlackTree乃至,データの持続性が確保されている.
 
-
 \section{Stackの使用}
 
 今回の実装ではSingleLinkedStackを2つ使用している.
@@ -1022,11 +1021,6 @@
 しかしながら,今回のStackはCall stackとは違い,プログラムの中で明示的に使用され,
 また,CodeGear自体が状態を持たないため問題がない.
 
-\section{GCやレプリケーションへの適用}
-
-
-
-
 \chapter{まとめと今後の課題}
 
 本研究ではGearsOSのファイルシステムであるGearsFileSystemにおける
@@ -1042,78 +1036,30 @@
 別のContextを指定することができない.
 そのため,ALLOCATIONに別Contextを操作するための機能を導入する必要があると考える.
 
+\section{ヒープオーバーフロー問題}
+
+RedBlackTreeはContext上のData Tableのヒープ領域に確保,コピーされる.
+この際,ヒープ領域の容量が足りず,ヒープオーバーフローする問題がある.
+ヒープ領域はContext生成時に確保され,ALLOCATEマクロによってDataGearが配置される.
+ALLOCATEはDataGearをヒープ領域に配置するのみであるため,
+容量が足りない場合にヒープ領域を拡張する機能を追加する必要がある.
+
 \section{テストケースの生成}
 
-\texttt{tree->copy}のAPIを実装する際は,
-想定した動作をするか確認するために木を生成するコードを書いた.
-C言語で
-
-\section{ヒープオーバーフロー問題}
-
-\section{テストコードでは不完全な部分}
+CopyRedBlackTreeを作成する際,コピーの動作確認のためのテストケースを11パターン用意した.
+その際のテストコードの行数が約1000行となった.
+開発の効率化のため,より簡潔にテストコードを書けるような仕組みを作る必要があると考える.
 
 
-\section{ファイルシステムにおけるスキーマ}
-
-従来のRDBのようなスキーマが存在すると,
-個別にバックアップなどを取らない限り
-スキーマの変更以前にロールバックすることができない.
-しかしながら,実際運用する上でスキーマを変更することは多々ある.
-これは,データの信頼性を低下させると考える.
-また,DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる
-インピーダンスミスマッチが発生し,DBのデータをプログラムが扱う際に
-その差を埋めるような変換を必要とする場合が生まれる.
-一方で,スキーマがあることによってデータに対して高度な操作を行うことができ,
-また,インデックスを容易に作成することができるといったメリットがある.
-よって,スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり,
-状況によって使い分けるのが良いと考える.
-
-今回は,非構造化データ内であれば構造化データを扱うことが可能であることと,
-信頼性を保証したいという点から,
-スキーマレスなDBとしてのファイルシステムを考える.
-しかしながら,トランザクションの仕組みを作る上でRedBlackTreeに対し,
-キーを設定することから完全なスキーマレスとは言えない構成となる.
-
-GearsOSのデータは全てDataGearで表される.
-よって,GearsOSにおけるファイルシステムはDataGearの集合となる.
-スキーマレスとはキーがない状態のことといえるが,
-DataGearはキーが設定されていないため,その集合自体にスキーマは無い.
-そのことから,GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる.
-なお,今回のRedBlackTreeによる構成の場合,キーはRedBlackTreeを指す.
-DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている.
-よって,KernelのContext上にキーを用いたDataGearの参照を書き込む.
+\section{GCとレプリケーションの実装}
 
-\section{RedBlackTreeによる権限の表現}
-
-ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある.
-今回のRedBlackTreeによる構成の場合,木のルートの所持者を設定することが
-ファイルに対して権限を設定することにあたる.
-ルートに対してアクセスする権限がなければ,
-読み書きができないといった実装になると考える.
-\section{データクエリ言語}
-
-ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を
-する必要がある.
-RedBlackTreeのキーを用いたインデックスに対応し,
-従来のSQLと比較してより柔軟なクエリを実行できることを目指したい.
-
-\section{ログなどの時系列データの保存}
-
-時系列データは通常のデータと違った保存の方法を考えることができる.
-時系列に並んでいることを生かしたデータの保存方式や,
-時間経過に伴うデータの重要性の変化を考慮に入れたデータ圧縮の方法をとることで,
-より効率的な保存が可能だと考える.
-
-\section{スタンドアロンなDB}
-
-MySQLやPostgreSQLなどはOSの機能としてではなく,
-それ自体が一つのアプリケーションとして自立的に動作している.
-自立的に動作するのは,データのポータビリティを向上させるためである.
-スタンドアロンなDBの形にするか,
-その他の方法でポータビリティを向上させる手法を考えたい.
-
-\section{GearsOSのプログラミング}
-
+今回はGCやレプリケーションの実装をするために必要な木のコピー機能であるCopyRedBlackTreeの実装を行った.
+Copying GCの動作を想定したswapを作成したものの,
+コンパクションが行われないなどGCとして不十分な点がある.
+今後は十分な機能をもったGCやレプリケーションを実装していきたい.
+GCはContextの廃棄やフリーリスト,GCタイミングの機構が必要である.
+また,GearsOS全体をGCすることも考えられる.
+レプリケーションは別ノードでのコピーの実行やレプリカとの通信プロトコルを定義する必要があるだろう.
 
 % %謝辞
 \input{chapter/thanks.tex}
--- a/TODO.md	Wed Feb 07 14:32:11 2024 +0900
+++ b/TODO.md	Wed Feb 07 17:24:31 2024 +0900
@@ -22,9 +22,9 @@
 - [x] 図の清書
 
 - [x] レプリケーションとDGM通信の話を入れる
+- [x] 評価
+- [x] まとめと今後の課題
 - [ ] 4章......
-- [ ] 評価
-- [ ] まとめと今後の課題
 
 確認したいこと
 
--- a/mindmaps/gears_fs_db.mm	Wed Feb 07 14:32:11 2024 +0900
+++ b/mindmaps/gears_fs_db.mm	Wed Feb 07 17:24:31 2024 +0900
@@ -958,9 +958,9 @@
 </node>
 <node TEXT="tree-&gt;rootを書き換えて,途中のノードからコピーできるみたいなの作りたい" ID="ID_1603927493" CREATED="1706692686178" MODIFIED="1706692704418"/>
 </node>
-<node TEXT="評価" POSITION="right" ID="ID_1699170037" CREATED="1706803749390" MODIFIED="1707213585346" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="121.5 pt">
+<node TEXT="評価" FOLDED="true" POSITION="right" ID="ID_1699170037" CREATED="1706803749390" MODIFIED="1707213585346" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="121.5 pt">
 <node TEXT="説明" ID="ID_1332913546" CREATED="1707024290462" MODIFIED="1707024304655">
-<node TEXT="テストコード" ID="ID_83989606" CREATED="1707024312272" MODIFIED="1707024315913">
+<node TEXT="テストコード" FOLDED="true" ID="ID_83989606" CREATED="1707024312272" MODIFIED="1707024315913">
 <node TEXT="いくつかの考えられる木の形はテストした" ID="ID_401372478" CREATED="1707024501611" MODIFIED="1707024539431">
 <node TEXT="11パターン" ID="ID_1060583266" CREATED="1707036504432" MODIFIED="1707110133774"/>
 <node TEXT="動作した" ID="ID_854834536" CREATED="1707024607282" MODIFIED="1707024611419"/>
@@ -974,7 +974,7 @@
 <node TEXT="上限を拡大する仕組みがいる" ID="ID_37519178" CREATED="1707024740319" MODIFIED="1707024747188"/>
 </node>
 </node>
-<node TEXT="非破壊RedBlackTreeの増大抑制" ID="ID_529836819" CREATED="1707024322382" MODIFIED="1707024336261">
+<node TEXT="非破壊RedBlackTreeの増大抑制" FOLDED="true" ID="ID_529836819" CREATED="1707024322382" MODIFIED="1707024336261">
 <node TEXT="非破壊なので過去の履歴がそのまま残り木が増大する問題があった" ID="ID_1452229252" CREATED="1707219315165" MODIFIED="1707219344850"/>
 <node TEXT="Copyによって参照される木の増大は防がれる" ID="ID_1864064653" CREATED="1707024754607" MODIFIED="1707024920464">
 <node TEXT="履歴部分が削がれるので" ID="ID_1998328102" CREATED="1707219356967" MODIFIED="1707219363161"/>
@@ -984,6 +984,15 @@
 <node TEXT="ゴミをフリーリストなどに接続する必要がある" ID="ID_891844429" CREATED="1707024810210" MODIFIED="1707024822315"/>
 <node TEXT="もしくは,別Contextへのコピーができていれば,Contextごと捨てることが考えられる" ID="ID_1594506897" CREATED="1707024822639" MODIFIED="1707024844218"/>
 </node>
+<node TEXT="RedBlackTreeの持続性" FOLDED="true" ID="ID_661781686" CREATED="1707024357426" MODIFIED="1707024367737">
+<node TEXT="単純なコピーで実装したため,データの持続性が保たれている" ID="ID_1984829925" CREATED="1707025135915" MODIFIED="1707025157178"/>
+</node>
+<node TEXT="Stackの使用" FOLDED="true" ID="ID_1762844508" CREATED="1707024350775" MODIFIED="1707024356847">
+<node TEXT="軽量継続の利点はcall stackなどの状態をもたいないことにある" ID="ID_1185503713" CREATED="1707025000678" MODIFIED="1707025032692"/>
+<node TEXT="しかし,Stackを使用している" ID="ID_206860039" CREATED="1707025033563" MODIFIED="1707025074768"/>
+<node TEXT="明示的に使用しており,CodeGear自体が状態を持っているわけではないので問題ない" ID="ID_1843110566" CREATED="1707025055736" MODIFIED="1707025100382"/>
+<node TEXT="SingleLinkedStackの操作もCodeGearの遷移で行われている" ID="ID_1840403810" CREATED="1707025106566" MODIFIED="1707025121167"/>
+</node>
 <node TEXT="同一ContextへのCopy" ID="ID_1254085673" CREATED="1707024372861" MODIFIED="1707024381556">
 <node TEXT="現状は同一Contextにコピーされている" ID="ID_309717594" CREATED="1707024852535" MODIFIED="1707024863311"/>
 <node TEXT="別Contextにする必要がある" ID="ID_275256559" CREATED="1707024863869" MODIFIED="1707024890077">
@@ -992,17 +1001,9 @@
 </node>
 <node TEXT="ALLOCATEの修正がいる" ID="ID_823404339" CREATED="1707024986029" MODIFIED="1707024994422"/>
 </node>
-<node TEXT="Stackの使用" ID="ID_1762844508" CREATED="1707024350775" MODIFIED="1707024356847">
-<node TEXT="軽量継続の利点はcall stackなどの状態をもたいないことにある" ID="ID_1185503713" CREATED="1707025000678" MODIFIED="1707025032692"/>
-<node TEXT="しかし,Stackを使用している" ID="ID_206860039" CREATED="1707025033563" MODIFIED="1707025074768"/>
-<node TEXT="明示的に使用しており,CodeGear自体が状態を持っているわけではないので問題ない" ID="ID_1843110566" CREATED="1707025055736" MODIFIED="1707025100382"/>
-<node TEXT="SingleLinkedStackの操作もCodeGearの遷移で行われている" ID="ID_1840403810" CREATED="1707025106566" MODIFIED="1707025121167"/>
-</node>
-<node TEXT="RedBlackTreeの持続性" ID="ID_661781686" CREATED="1707024357426" MODIFIED="1707024367737">
-<node TEXT="単純なコピーで実装したため,データの持続性が保たれている" ID="ID_1984829925" CREATED="1707025135915" MODIFIED="1707025157178"/>
-</node>
 <node TEXT="GC, レプリケーション,バックアップへの適用" ID="ID_1095924486" CREATED="1707221209456" MODIFIED="1707221228881">
 <font BOLD="false"/>
+<node TEXT="" ID="ID_281699551" CREATED="1707283824577" MODIFIED="1707283824577"/>
 </node>
 </node>
 <node TEXT="テストは動いた" ID="ID_1202499591" CREATED="1706803764279" MODIFIED="1706803770865">
@@ -1055,7 +1056,7 @@
 <node TEXT="それ以外はまとめと今後の課題に書く" ID="ID_1941288242" CREATED="1706803862696" MODIFIED="1706803878303"/>
 </node>
 </node>
-<node TEXT="まとめと今後の課題" FOLDED="true" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142">
+<node TEXT="まとめと今後の課題" POSITION="right" ID="ID_912711900" CREATED="1706956151544" MODIFIED="1707213611142">
 <node TEXT="非破壊RedBlackTreeの増大を防ぐ仕組みを構築できた" ID="ID_418966492" CREATED="1706956585170" MODIFIED="1706956610719"/>
 <node TEXT="別コンテキストへのコピー" ID="ID_1209930854" CREATED="1706956313462" MODIFIED="1706956324424"/>
 <node TEXT="GearsOS全体をGCすることも考えられる" ID="ID_1250275844" CREATED="1707013490904" MODIFIED="1707013522142"/>
@@ -1068,6 +1069,30 @@
 </node>
 <node TEXT="ファイルシステムのスキーマ" ID="ID_63849619" CREATED="1707214184680" MODIFIED="1707214189832"/>
 <node TEXT="権限表現" ID="ID_598953757" CREATED="1707214211262" MODIFIED="1707214215981"/>
+<node TEXT="Contextをコピーすることでフラグメンテーションは解消する" ID="ID_1667984108" CREATED="1707286730333" MODIFIED="1707286747139">
+<node TEXT="Gears全体では解消してないかも" ID="ID_1073971147" CREATED="1707286747311" MODIFIED="1707286755075"/>
+</node>
+<node TEXT="今後の課題" ID="ID_428993998" CREATED="1707285565828" MODIFIED="1707285588990">
+<node TEXT="別ContextへのALLOCATION" ID="ID_1464367692" CREATED="1707285571840" MODIFIED="1707285601877">
+<node TEXT="現状は同一Contextにコピーしている" ID="ID_864566640" CREATED="1707286044589" MODIFIED="1707286060465"/>
+<node TEXT="別Contextにコピーする必要がある" ID="ID_1623888373" CREATED="1707286061336" MODIFIED="1707286081622">
+<node TEXT="レプリケーションへの適用のため" ID="ID_1340706064" CREATED="1707286082265" MODIFIED="1707286088934"/>
+<node TEXT="Contextの廃棄によってGCのコンパクションを発生させる" ID="ID_747779692" CREATED="1707286089184" MODIFIED="1707286122746"/>
+</node>
+</node>
+<node TEXT="ヒープオーバーフロー問題" ID="ID_1520918245" CREATED="1707285616558" MODIFIED="1707285622872">
+<node TEXT="ALLOCATEに限界がある" ID="ID_145024116" CREATED="1707286144904" MODIFIED="1707286157215"/>
+<node TEXT="ヒープ領域の追加機構がないため必要である" ID="ID_1200324860" CREATED="1707286157588" MODIFIED="1707286202952"/>
+</node>
+<node TEXT="GCとレプリケーションの実装" ID="ID_1710394671" CREATED="1707286605335" MODIFIED="1707286619440"/>
+<node TEXT="GearsOSのプログラミング" ID="ID_1522560459" CREATED="1707285716374" MODIFIED="1707285722515">
+<node TEXT="テストケースの生成" ID="ID_508754044" CREATED="1707285602305" MODIFIED="1707285611890">
+<node TEXT="10パターンあたりで1000行のテストコードになった" ID="ID_310747926" CREATED="1707286211702" MODIFIED="1707286225014"/>
+<node TEXT="動作確認を困難にしている" ID="ID_729064103" CREATED="1707286242799" MODIFIED="1707286251072"/>
+<node TEXT="もっと簡潔に書ける仕組みが必要である" ID="ID_1162968810" CREATED="1707286225521" MODIFIED="1707286238147"/>
+</node>
+</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">