Mercurial > hg > Papers > 2024 > matac-master
view mindmaps/gears_fs_db.mm @ 11:67b68982e36e
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 04 Jan 2024 23:54:05 +0900 |
| parents | b7abe0e40c22 |
| children | 7d7117822000 |
line wrap: on
line source
<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="1702111913150" STYLE="oval"> <font SIZE="18"/> <hook NAME="MapStyle"> <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"/> <map_styles> <stylenode LOCALIZED_TEXT="styles.root_node" STYLE="oval" UNIFORM_SHAPE="true" VGAP_QUANTITY="24 pt"> <font SIZE="24"/> <stylenode LOCALIZED_TEXT="styles.predefined" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="default" ID="ID_207122690" COLOR="#000000" STYLE="fork"> <arrowlink SHAPE="CUBIC_CURVE" COLOR="#000000" WIDTH="2" TRANSPARENCY="200" DASH="" FONT_SIZE="9" FONT_FAMILY="SansSerif" DESTINATION="ID_207122690" STARTARROW="DEFAULT" ENDARROW="NONE"/> <font NAME="SansSerif" SIZE="10" BOLD="false" ITALIC="false"/> <richcontent CONTENT-TYPE="plain/auto" TYPE="DETAILS"/> <richcontent TYPE="NOTE" CONTENT-TYPE="plain/auto"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.details"/> <stylenode LOCALIZED_TEXT="defaultstyle.attributes"> <font SIZE="9"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.note" COLOR="#000000" BACKGROUND_COLOR="#ffffff" TEXT_ALIGN="LEFT"/> <stylenode LOCALIZED_TEXT="defaultstyle.floating"> <edge STYLE="hide_edge"/> <cloud COLOR="#f0f0f0" SHAPE="ROUND_RECT"/> </stylenode> <stylenode LOCALIZED_TEXT="defaultstyle.selection" BACKGROUND_COLOR="#4e85f8" BORDER_COLOR_LIKE_EDGE="false" BORDER_COLOR="#4e85f8"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.user-defined" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="styles.topic" COLOR="#18898b" STYLE="fork"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.subtopic" COLOR="#cc3300" STYLE="fork"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.subsubtopic" COLOR="#669900"> <font NAME="Liberation Sans" SIZE="10" BOLD="true"/> </stylenode> <stylenode LOCALIZED_TEXT="styles.important" ID="ID_3752836"> <icon BUILTIN="yes"/> <arrowlink COLOR="#003399" TRANSPARENCY="255" DESTINATION="ID_3752836"/> </stylenode> </stylenode> <stylenode LOCALIZED_TEXT="styles.AutomaticLayout" POSITION="right" STYLE="bubble"> <stylenode LOCALIZED_TEXT="AutomaticLayout.level.root" COLOR="#000000" STYLE="oval" SHAPE_HORIZONTAL_MARGIN="10 pt" SHAPE_VERTICAL_MARGIN="10 pt"> <font SIZE="18"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,1" COLOR="#0033ff"> <font SIZE="16"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,2" COLOR="#00b439"> <font SIZE="14"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,3" COLOR="#990000"> <font SIZE="12"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,4" COLOR="#111111"> <font SIZE="10"/> </stylenode> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,5"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,6"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,7"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,8"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,9"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,10"/> <stylenode LOCALIZED_TEXT="AutomaticLayout.level,11"/> </stylenode> </stylenode> </map_styles> </hook> <node TEXT="Gears OS" POSITION="right" ID="ID_1060626979" CREATED="1699848393025" MODIFIED="1702111913149" HGAP_QUANTITY="-5.5 pt" VSHIFT_QUANTITY="-72.75 pt"> <node TEXT="特徴" ID="ID_943482341" CREATED="1702111230723" MODIFIED="1702111233987"> <node TEXT="metaGear" ID="ID_160728835" CREATED="1702111234234" MODIFIED="1702111815711"> <node TEXT="データの整合性" ID="ID_1532293232" CREATED="1702111816103" MODIFIED="1702111830986"/> <node TEXT="資源管理" ID="ID_820593070" CREATED="1702111831179" MODIFIED="1702111834866"/> </node> <node TEXT="Context" ID="ID_447263401" CREATED="1702111711616" MODIFIED="1702111713867"> <node TEXT="プロセスに相当" ID="ID_119342897" CREATED="1702111732662" MODIFIED="1702111736239"/> <node TEXT="実行するCG, 使用するDG全てを持つ" ID="ID_1243433858" CREATED="1702111736575" MODIFIED="1702111762536"/> </node> <node TEXT="3種類のGearsOS" ID="ID_1110454361" CREATED="1702111776755" MODIFIED="1702111782168"> <node TEXT="GearsOS" ID="ID_1417588174" CREATED="1702111873653" MODIFIED="1702111876220"> <node TEXT="ユーザーレベルタスクマネジメントの実装を目的とする" ID="ID_916197337" CREATED="1702112069451" MODIFIED="1702112079145"/> <node TEXT="CbC実装" ID="ID_939823586" CREATED="1702112086168" MODIFIED="1702112090340"/> <node TEXT="本研究のメイン対象" ID="ID_179232110" CREATED="1702112096195" MODIFIED="1702112110097"/> </node> <node TEXT="GearsAgda" ID="ID_1260602460" CREATED="1702111876582" MODIFIED="1702111879424"> <node TEXT="Agda実装" ID="ID_1598980937" CREATED="1702112014204" MODIFIED="1702112017570"/> <node TEXT="形式手法による証明を目的とする" ID="ID_1299519318" CREATED="1702112017959" MODIFIED="1702112029698"/> </node> <node TEXT="CbC_x.v6" ID="ID_473963560" CREATED="1702111879786" MODIFIED="1702112199760"> <node TEXT="スタンドアロンOSの開発を目的とする" ID="ID_1891291526" CREATED="1702112042696" MODIFIED="1702112054326"/> </node> </node> <node TEXT="信頼性の保証を目的としている" ID="ID_489283513" CREATED="1702111964176" MODIFIED="1702111972169"/> </node> <node TEXT="ファイルシステムとDB" ID="ID_1884932719" CREATED="1699849849835" MODIFIED="1699849855383"> <node TEXT="RedBlackTreeを基本構造とする" ID="ID_224748942" CREATED="1699849885632" MODIFIED="1699849902671"/> <node TEXT="user interface" ID="ID_1064201171" CREATED="1702117030490" MODIFIED="1702117056047"> <node TEXT="学部の時のやつ" ID="ID_1607825727" CREATED="1702117042878" MODIFIED="1702117046968"/> </node> <node TEXT="複数のreplicationを持てていない" ID="ID_787621439" CREATED="1699849855878" MODIFIED="1699849873297"/> <node TEXT="GCがない" ID="ID_1300729095" CREATED="1699849873756" MODIFIED="1699849878570"> <node TEXT="RustのようなGCを持たないシステムも存在する" ID="ID_417147063" CREATED="1701692764078" MODIFIED="1701692773562"> <node TEXT="GCなくても良いのでは？という疑問が生まれる" ID="ID_660130313" CREATED="1701692778839" MODIFIED="1701692788086"/> <node TEXT="CbR?" ID="ID_1404954258" CREATED="1701692790720" MODIFIED="1701692795814"/> </node> </node> <node TEXT="RedBlackTreeのコピーによって" ID="ID_116893075" CREATED="1699849908039" MODIFIED="1699849924661"> <node TEXT="replication作成" ID="ID_1170481289" CREATED="1699849924973" MODIFIED="1699849930140"/> <node TEXT="GC" ID="ID_1741645302" CREATED="1699849930484" MODIFIED="1699849933881"> <node TEXT="Copying GC" ID="ID_937412490" CREATED="1699850770149" MODIFIED="1699850779042"/> </node> <node TEXT="replicationとGCを同一システムで実現する利点は？" ID="ID_184373863" CREATED="1701692556651" MODIFIED="1701692583435"> <node TEXT="今の所GCするとそれをreplicationとしても扱えるという感じ" ID="ID_214758450" CREATED="1701692591670" MODIFIED="1701692621085"/> <node TEXT="逆に、分ける意味がないのか" ID="ID_587144816" CREATED="1701692621555" MODIFIED="1701692633777"/> <node TEXT="同時にできるのであればその方が効率良い" ID="ID_298223735" CREATED="1701692637636" MODIFIED="1701692696469"/> </node> </node> </node> <node TEXT="現状" ID="ID_932050028" CREATED="1703310897416" MODIFIED="1703310899956"> <node TEXT="" ID="ID_166710427" CREATED="1703310900268" MODIFIED="1703310900268"/> </node> <node TEXT="CbC" ID="ID_740206957" CREATED="1701695838712" MODIFIED="1701695841654"> <node TEXT="Cの下位言語" ID="ID_1949462311" CREATED="1702109769687" MODIFIED="1702109804650"> <node TEXT="CのLLVMに変更を加えている" ID="ID_591487528" CREATED="1702110861488" MODIFIED="1702110890767"/> </node> <node TEXT="処理の単位 CodeGear" ID="ID_1551166772" CREATED="1702109805037" MODIFIED="1702109818187"> <node TEXT="DataGearが入力される" ID="ID_1020316470" CREATED="1702110084628" MODIFIED="1702110125371"> <node TEXT="inputDataGear" ID="ID_1437736688" CREATED="1702110190302" MODIFIED="1702110196899"/> </node> <node TEXT="DataGearを出力する" ID="ID_1796772165" CREATED="1702110099792" MODIFIED="1702110112391"> <node TEXT="outputDataGear" ID="ID_1734410453" CREATED="1702110197415" MODIFIED="1702110202862"/> </node> <node TEXT="CodeGearをDataGearの一種と捉えることも可能" ID="ID_1871025096" CREATED="1702110136840" MODIFIED="1702110151771"/> </node> <node TEXT="データの単位 DataGear" ID="ID_771276269" CREATED="1702109818490" MODIFIED="1702109832058"> <node TEXT="構造体で表現される" ID="ID_870047835" CREATED="1702110827132" MODIFIED="1702110833094"/> <node TEXT="" ID="ID_1157018642" CREATED="1702110833322" MODIFIED="1702110833322"/> </node> <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_1583866878" CREATED="1702109839193" MODIFIED="1702109847067"/> <node TEXT="__code" ID="ID_1535719892" CREATED="1702109980407" MODIFIED="1702109984940"/> <node TEXT="gotoによる軽量継続" ID="ID_1041460941" CREATED="1702109847380" MODIFIED="1702109854199"> <node TEXT="call stackを持たない" ID="ID_1868821185" CREATED="1702109894715" MODIFIED="1702109901816"/> <node TEXT="LLVMのsetjmpとlongjmp" ID="ID_1689168618" CREATED="1702109904182" MODIFIED="1702110048454"/> <node TEXT="tail callっぽい" ID="ID_1025227356" CREATED="1702110686327" MODIFIED="1702110691940"> <node TEXT="tailcall忘れた時はここをみる" ID="ID_1334629625" CREATED="1702110692360" MODIFIED="1702110703733"> <node TEXT="http://www.nct9.ne.jp/m_hiroi/func/abcerl02.html" ID="ID_1874667604" CREATED="1702110709856" MODIFIED="1702110709856" LINK="http://www.nct9.ne.jp/m_hiroi/func/abcerl02.html"/> </node> <node TEXT="再帰呼び出しして、返り値をそのまま返す" ID="ID_801162080" CREATED="1702110795575" MODIFIED="1702110816945"/> </node> </node> <node TEXT="現状" ID="ID_1373082100" CREATED="1702110955427" MODIFIED="1702110958434"> <node TEXT="http://www.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm/" ID="ID_797243399" CREATED="1702111010437" MODIFIED="1702111010437" LINK="http://www.cr.ie.u-ryukyu.ac.jp/hg/CbC/CbC_llvm/"/> <node TEXT="clang llvm 18.0.0" ID="ID_762978767" CREATED="1702111146287" MODIFIED="1702111160675"/> </node> <node TEXT="関連" ID="ID_416590732" CREATED="1703308253194" MODIFIED="1703308255811"> <node TEXT="AspectJ" ID="ID_1370782910" CREATED="1703308256121" MODIFIED="1703308259210"> <node TEXT="リフレクション" ID="ID_96315745" CREATED="1703308259675" MODIFIED="1703308340272"/> <node TEXT="CbCはリフレクションしやすい" ID="ID_1614355873" CREATED="1703308341219" MODIFIED="1703308355429"/> <node TEXT="metaを書ける部分がリフレクション" ID="ID_195416108" CREATED="1703308357434" MODIFIED="1703308372053"/> <node TEXT="AOP" ID="ID_770917898" CREATED="1703308974828" MODIFIED="1703308978370"> <node TEXT="アスペクト志向プログラミング" ID="ID_1702082447" CREATED="1703308978573" MODIFIED="1703308988562"/> </node> <node TEXT="記法" ID="ID_582319031" CREATED="1703308588273" MODIFIED="1703308590240"> <node TEXT="@Aspect" ID="ID_201521343" CREATED="1703308932008" MODIFIED="1703308939119"/> <node TEXT="Advice" ID="ID_1105819991" CREATED="1703308939534" MODIFIED="1703308947617"/> <node TEXT="PointCut" ID="ID_1656105549" CREATED="1703308947870" MODIFIED="1703308951334"/> <node TEXT="JoinPoint" ID="ID_1355814265" CREATED="1703308951712" MODIFIED="1703308972859"/> </node> </node> </node> </node> </node> <node TEXT="ファイルシステム" POSITION="right" ID="ID_1877138212" CREATED="1699848400796" MODIFIED="1699848405514"> <node TEXT="可変長文字列を格納するファイル" ID="ID_1080516331" CREATED="1699849063058" MODIFIED="1699849081419"> <node TEXT="構造化されていないデータ" ID="ID_989502084" CREATED="1699854164275" MODIFIED="1699854171408"/> </node> <node TEXT="ファイルにアクセスするための名前管理" ID="ID_1768633329" CREATED="1699849081914" MODIFIED="1699849094907"> <node TEXT="linux" ID="ID_1049908119" CREATED="1699857284972" MODIFIED="1699857288270"> <node ID="ID_1495135529" CREATED="1699857288486" MODIFIED="1699857326105"><richcontent TYPE="NODE"> <html> <head> </head> <body> <p> /<font color="#000000">home/matac/ws/</font> </p> </body> </html> </richcontent> </node> </node> </node> <node TEXT="同時アクセス時の名前管理の一貫性保証" ID="ID_1592817213" CREATED="1699849095540" MODIFIED="1699849111381"/> <node TEXT="ファイルに同時に書き込まれた時の一貫性の保証は無い" ID="ID_760250864" CREATED="1699849111930" MODIFIED="1699849133659"> <node TEXT="書き込み制御のロック機構がある" ID="ID_1546654520" CREATED="1699849148263" MODIFIED="1699849162973"/> </node> </node> <node TEXT="DB" POSITION="right" ID="ID_149657016" CREATED="1699848406699" MODIFIED="1699848407993"> <node TEXT="レコード" ID="ID_1205240345" CREATED="1699849182564" MODIFIED="1699849185575"> <node TEXT="入力の属性名と型の組" ID="ID_249604408" CREATED="1699849185821" MODIFIED="1699849209586"/> </node> <node TEXT="テーブル" ID="ID_156913568" CREATED="1699849219044" MODIFIED="1699849228825"> <node TEXT="特定の属性をキーとする" ID="ID_415589337" CREATED="1699849229049" MODIFIED="1699849235367"/> </node> <node TEXT="直列化可能性" ID="ID_1355828962" CREATED="1699849247355" MODIFIED="1699849253883"> <node TEXT="Serializability" ID="ID_429588711" CREATED="1699849254710" MODIFIED="1699849318311"/> <node TEXT="複数のトランザクションが並行実行される際の処理結果の正しさを保証する基準" ID="ID_749156965" CREATED="1699849319073" MODIFIED="1699849354090"/> </node> <node TEXT="正規形" ID="ID_1482959686" CREATED="1699854183342" MODIFIED="1699854192704"/> </node> <node TEXT="ファイルシステムとDBの違い" POSITION="right" ID="ID_1607395441" CREATED="1699851419940" MODIFIED="1699851427585"> <node TEXT="データの格納形式" ID="ID_2838179" CREATED="1699851427818" MODIFIED="1699851444191"> <node TEXT="文字列かレコードか" ID="ID_6405282" CREATED="1699851446861" MODIFIED="1699851462681"/> </node> <node TEXT="データアクセス方法" ID="ID_1258040613" CREATED="1699851466951" MODIFIED="1699851472419"> <node TEXT="read, write" ID="ID_823556495" CREATED="1699851468816" MODIFIED="1699851490085"/> <node TEXT="SQL" ID="ID_1745553035" CREATED="1699851490559" MODIFIED="1699851500567"/> </node> <node TEXT="直列化可能性保証方法" ID="ID_1245227752" CREATED="1699851504126" MODIFIED="1699851516763"> <node TEXT="record, table lock" ID="ID_1269582911" CREATED="1699852009313" MODIFIED="1699852028994"/> <node TEXT="ファイルロック" ID="ID_765600991" CREATED="1699852050399" MODIFIED="1699852055041"/> </node> </node> <node TEXT="ファイルシステムとDBの追加機能" POSITION="right" ID="ID_1823247462" CREATED="1699851812550" MODIFIED="1699851823299"> <node TEXT="電源を切った時にデータが残る" ID="ID_1444181613" CREATED="1699851823510" MODIFIED="1699851836412"> <node TEXT="persistency" ID="ID_603526007" CREATED="1699851837510" MODIFIED="1699851840636"/> </node> <node TEXT="書き込めたかどうかを判定する" ID="ID_1468638907" CREATED="1699851851054" MODIFIED="1699851859966"> <node TEXT="atomic write" ID="ID_514160473" CREATED="1699851860291" MODIFIED="1699851864956"/> </node> <node TEXT="一つのノードが失われた時にデータを保護する" ID="ID_369826358" CREATED="1699851869445" MODIFIED="1699851882668"> <node TEXT="多重性" ID="ID_1986614934" CREATED="1699851883681" MODIFIED="1699851887639"/> </node> <node TEXT="複数のコピーを調停するコミット機構" ID="ID_422231006" CREATED="1699851890504" MODIFIED="1699851906965"/> </node> <node TEXT="信頼性" POSITION="right" ID="ID_696728353" CREATED="1699848408447" MODIFIED="1699848413804"> <node TEXT="向上手法" ID="ID_1020078491" CREATED="1699848491366" MODIFIED="1699848496923"> <node TEXT="証明" ID="ID_1018661667" CREATED="1699848497270" MODIFIED="1699848503341"> <node TEXT="Gears Agda" ID="ID_1165126463" CREATED="1699848504251" MODIFIED="1699848509993"/> <node TEXT="invariantを使う" ID="ID_92873298" CREATED="1699848511299" MODIFIED="1699848516818"/> </node> <node TEXT="テスト" ID="ID_853686057" CREATED="1699848525221" MODIFIED="1699848530154"/> <node TEXT="モデル検査" ID="ID_465552896" CREATED="1699848530425" MODIFIED="1699848536874"/> </node> <node TEXT="システム全体で向上させる必要がある" ID="ID_1629969942" CREATED="1699848909002" MODIFIED="1699848931988"> <node TEXT="システムの構成要素" ID="ID_677210990" CREATED="1699848935984" MODIFIED="1699848942782"> <node TEXT="アプリケーション" ID="ID_1491167091" CREATED="1699848943269" MODIFIED="1699848949144"/> <node TEXT="OS" ID="ID_419231398" CREATED="1699848949689" MODIFIED="1699848952218"/> <node TEXT="ファイルシステム" ID="ID_1950317269" CREATED="1699848952489" MODIFIED="1699849002048"/> <node TEXT="DB" ID="ID_92392900" CREATED="1699849003252" MODIFIED="1699849004419"/> <node TEXT="メモリ" ID="ID_1964952999" CREATED="1699849004786" MODIFIED="1699849010256"/> <node TEXT="SSD" ID="ID_1413092539" CREATED="1699849010790" MODIFIED="1699849015545"/> <node TEXT="分散ノード" ID="ID_1536068993" CREATED="1699849016080" MODIFIED="1699849022165"/> <node TEXT="ネットワーク" ID="ID_1088702523" CREATED="1699849022619" MODIFIED="1699849027379"/> </node> </node> <node TEXT="向上手法をシステム全体に適用したい" ID="ID_829551002" CREATED="1699850006058" MODIFIED="1699850017727"/> </node> <node TEXT="RedBlackTree" POSITION="right" ID="ID_858040690" CREATED="1699848437129" MODIFIED="1699848446060"> <node TEXT="Copy" ID="ID_76598812" CREATED="1699848476363" MODIFIED="1699848479936"> <node TEXT="単なる2分木のコピー" ID="ID_1535596989" CREATED="1699849455588" MODIFIED="1699849469353"/> <node TEXT="Stack無しで書くとおそらく結構複雑" ID="ID_527329681" CREATED="1699849470075" MODIFIED="1699857892247"/> <node TEXT="木を辿るためにStackを使う" ID="ID_788381426" CREATED="1699849561986" MODIFIED="1699849582652"> <node TEXT="コピー後に消されるので使って良い" ID="ID_1063130872" CREATED="1701690823328" MODIFIED="1701690834394"/> </node> <node TEXT="アルゴリズム" ID="ID_529312839" CREATED="1699849518269" MODIFIED="1699849522647"> <node TEXT="左側を深さ優先で辿る" ID="ID_468694757" CREATED="1699849525266" MODIFIED="1699849604742"> <node TEXT="Stack push" ID="ID_1123969398" CREATED="1699849778090" MODIFIED="1699849781012"/> </node> <node TEXT="アロケートしたノードは別のContext上に作る" ID="ID_320048499" CREATED="1699849620905" MODIFIED="1699849638042"> <node TEXT="GCのため" ID="ID_1239006804" CREATED="1699849638520" MODIFIED="1699849668501"/> <node TEXT="Copy後古いContextを消す" ID="ID_1485480555" CREATED="1699849646521" MODIFIED="1699849693755"/> <node TEXT="メモリ管理をモナドで表していることになる" ID="ID_1271994335" CREATED="1699849705089" MODIFIED="1699849715878"/> </node> <node TEXT="リーフまで降りたらroot方向に木を戻る" ID="ID_976293319" CREATED="1699849731393" MODIFIED="1699849765553"> <node TEXT="Stack pop" ID="ID_1123748609" CREATED="1699849765982" MODIFIED="1699849773214"/> <node TEXT="右側を呼び出す" ID="ID_831164108" CREATED="1699849789218" MODIFIED="1699849803550"/> </node> <node TEXT="Stackを2つ使うならば" ID="ID_472848117" CREATED="1699849785880" MODIFIED="1699850937824"> <node TEXT="全体のStack" ID="ID_315508287" CREATED="1699850965212" MODIFIED="1699858010811"> <node TEXT="originの木を辿るために使う" ID="ID_824722897" CREATED="1699858046929" MODIFIED="1699858071837"/> </node> <node TEXT="途中のStack" ID="ID_1421142933" CREATED="1699850966215" MODIFIED="1699858024318"> <node TEXT="右側を呼び出す際にそれまでの左側部分木を保持" ID="ID_929949795" CREATED="1699851138198" MODIFIED="1699858042178"/> </node> </node> </node> <node TEXT="Copy前後の同一性確認が必要" ID="ID_1150089347" CREATED="1699849956727" MODIFIED="1699849974942"/> <node TEXT="Copy中の変更" ID="ID_492731672" CREATED="1699849982760" MODIFIED="1699849992692"/> <node TEXT="毎回全てをGCするか" ID="ID_1696799143" CREATED="1699858222922" MODIFIED="1699858309153"> <node TEXT="アクセス頻度によって世代分けする" ID="ID_158787872" CREATED="1699858236610" MODIFIED="1699858248665"/> <node TEXT="ほとんどアクセスされないデータはGC対象から除く" ID="ID_285170374" CREATED="1699858262921" MODIFIED="1699858318515"/> </node> <node TEXT="Copyによってreplicationの作成が可能になる" ID="ID_572465203" CREATED="1701690510698" MODIFIED="1701690536500"/> </node> <node TEXT="incrementalなTreeのcopy" ID="ID_1492567121" CREATED="1699869669939" MODIFIED="1699869692257"> <node TEXT="後からcommitできるかも" ID="ID_1849438115" CREATED="1699869742980" MODIFIED="1699869754391"/> <node TEXT="commitのシーケンスをとっておく" ID="ID_921049246" CREATED="1699869765723" MODIFIED="1699869778036"> <node TEXT="Treeとは別にオペレーションのリストがある" ID="ID_1770284118" CREATED="1699869879779" MODIFIED="1699869889686"> <node TEXT="これもcopyが必要" ID="ID_230010982" CREATED="1699869957930" MODIFIED="1699869963814"/> </node> <node TEXT="RedBlackTree with commtted operation" ID="ID_888988533" CREATED="1699869899048" MODIFIED="1699869915123"> <node TEXT="番号" ID="ID_1935233472" CREATED="1699869923512" MODIFIED="1699869928338"/> <node TEXT="insert, delete" ID="ID_1668599725" CREATED="1699869929471" MODIFIED="1699869933942"/> </node> </node> </node> <node TEXT="証明しやすい" ID="ID_1313077784" CREATED="1699849438956" MODIFIED="1699849443715"/> <node TEXT="全ての操作が最悪でもO(log n)" ID="ID_1382477887" CREATED="1699855369743" MODIFIED="1699855390827"/> </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"> <node TEXT="ただし、木の操作にStackを用いる" ID="ID_1170936451" CREATED="1699857056714" MODIFIED="1699857067513"/> </node> <node TEXT="木自体がオブジェクトルートになる" ID="ID_1404066066" CREATED="1699857074069" MODIFIED="1699857087072"> <node TEXT="正確なGC" ID="ID_462996564" CREATED="1699857087449" MODIFIED="1699857104930"/> </node> </node> <node TEXT="コピーのベンチマーカー" POSITION="right" ID="ID_1415317998" CREATED="1699856883382" MODIFIED="1699856891252"> <node TEXT="ある程度大きな木を用意" ID="ID_1884791368" CREATED="1699857682191" MODIFIED="1699857700584"> <node TEXT="ある程度とは" ID="ID_1182141688" CREATED="1699857704166" MODIFIED="1699857711215"/> </node> <node TEXT="単純にコピーにかかる時間を測定" ID="ID_846596778" CREATED="1699857700957" MODIFIED="1699857730588"/> <node TEXT="比較対象は？" ID="ID_963832906" CREATED="1699857731316" MODIFIED="1699857739036"/> </node> <node TEXT="ディスク上とメモリ上のデータ構造" POSITION="right" ID="ID_1874111745" CREATED="1699850217484" MODIFIED="1699850230859"> <node TEXT="同一のRedBlackTree" ID="ID_1633724271" CREATED="1699850231118" MODIFIED="1699850243142"/> <node TEXT="persistent memoryを想定" ID="ID_719479083" CREATED="1699850243592" MODIFIED="1699850261924"/> </node> <node TEXT="先行研究" POSITION="right" ID="ID_1807805275" CREATED="1699850150666" MODIFIED="1699850155227"> <node TEXT="GearsOS の分散ファイルシステム設計" ID="ID_1737093216" CREATED="1701692836825" MODIFIED="1701692838439"> <node TEXT="一木 貴裕" ID="ID_976656831" CREATED="1701692838974" MODIFIED="1701692861473"/> <node TEXT="修論" ID="ID_1407964942" CREATED="1701692861994" MODIFIED="1701692868384"/> </node> <node TEXT="Gearsos における i-node を用いた file system の設計" ID="ID_152975250" CREATED="1701692905310" MODIFIED="1701692912376"> <node TEXT="又吉 雄斗" ID="ID_537151466" CREATED="1701692914641" MODIFIED="1701692923391"/> <node TEXT="卒論" ID="ID_1486800431" CREATED="1701692926762" MODIFIED="1701692930073"/> </node> <node TEXT="参考文献" ID="ID_1704420848" CREATED="1702289534980" MODIFIED="1702289539226"> <node TEXT="AspectJ" ID="ID_682948653" CREATED="1702289539526" MODIFIED="1702289543447"/> </node> </node> <node TEXT="評価方法" POSITION="right" ID="ID_1979397312" CREATED="1699850131177" MODIFIED="1699850137060"/> <node TEXT="章立て" POSITION="left" ID="ID_378600647" CREATED="1699848424709" MODIFIED="1702112473403"> <node TEXT="Gears OSのファイルシステムとDB" ID="ID_446325287" CREATED="1701690660393" MODIFIED="1701690902283"> <node TEXT="重要なシステムの障害" ID="ID_780032066" CREATED="1704365424619" MODIFIED="1704365554685"> <node TEXT="例" ID="ID_561763413" CREATED="1704365743851" MODIFIED="1704365747240"> <node TEXT="全銀システム" ID="ID_380458549" CREATED="1704365488518" MODIFIED="1704365500548"> <node TEXT="https://www.zengin-net.jp/announcement/pdf/announcement_20231201.pdf" ID="ID_622498163" CREATED="1704365947486" MODIFIED="1704365947486" LINK="https://www.zengin-net.jp/announcement/pdf/announcement_20231201.pdf"/> </node> <node TEXT="ANAの国内線システム" ID="ID_227546985" CREATED="1704365556083" MODIFIED="1704366884696"> <node TEXT="https://www.anahd.co.jp/group/pr/202304/notification-2.html?_gl=1*1h2jfg0*_ga*MTkwMjE0OTIwNC4xNjgwOTIwMTUx*_ga_32F297W9WL*MTY4MDkyMDI2My4xLjEuMTY4MDkyMDMwNy4wLjAuMA.." ID="ID_918028332" CREATED="1704366735088" MODIFIED="1704366735088" LINK="https://www.anahd.co.jp/group/pr/202304/notification-2.html?_gl=1*1h2jfg0*_ga*MTkwMjE0OTIwNC4xNjgwOTIwMTUx*_ga_32F297W9WL*MTY4MDkyMDI2My4xLjEuMTY4MDkyMDMwNy4wLjAuMA.."/> </node> <node TEXT="電子決済システム" ID="ID_271892958" CREATED="1704365579825" MODIFIED="1704366979311"> <node TEXT="https://www.glory.co.jp/news/detail/id=2017" ID="ID_650733639" CREATED="1704367245326" MODIFIED="1704367245326" LINK="https://www.glory.co.jp/news/detail/id=2017"/> </node> </node> <node TEXT="これらは社会に多大な影響を与える" ID="ID_1496226551" CREATED="1704365759256" MODIFIED="1704365779957"/> <node TEXT="よってシステムの高い信頼性が求められる" ID="ID_1365357344" CREATED="1704365780499" MODIFIED="1704365831219"/> </node> <node TEXT="システム全体の信頼性を上げたい" ID="ID_1572843196" CREATED="1703313460915" MODIFIED="1703313713692"> <node TEXT="システムにあるさまざまな要素" ID="ID_1198542652" CREATED="1704365155193" MODIFIED="1704365166358"> <node TEXT="アプリケーション" ID="ID_727581223" CREATED="1704365166793" MODIFIED="1704365223650"/> <node TEXT="OS" ID="ID_1417760159" CREATED="1704365224002" MODIFIED="1704365225602"/> <node TEXT="ファイルシステム" ID="ID_153728143" CREATED="1704365226160" MODIFIED="1704365231311"/> <node TEXT="DB" ID="ID_323366858" CREATED="1704365231782" MODIFIED="1704365232994"/> <node TEXT="メモリ" ID="ID_402756754" CREATED="1704365233331" MODIFIED="1704365236964"/> <node TEXT="SSD" ID="ID_404429414" CREATED="1704365237202" MODIFIED="1704365243718"/> <node TEXT="分散ノード" ID="ID_1628174426" CREATED="1704365244457" MODIFIED="1704365249457"/> <node TEXT="ネットワーク" ID="ID_1337491308" CREATED="1704365250196" MODIFIED="1704365253472"/> </node> <node TEXT="全体の信頼性を上げる必要がある" ID="ID_355799274" CREATED="1704365894036" MODIFIED="1704365915131"/> </node> <node TEXT="ファイルシステムとDBの信頼性を考える" ID="ID_1355454563" CREATED="1703313715002" MODIFIED="1703313723643"> <node TEXT="システムにおいて重要なFSとDBの信頼性を保証したい" ID="ID_1811829647" CREATED="1704365294814" MODIFIED="1704365332688"/> </node> <node TEXT="ファイルシステムとは" ID="ID_1898416034" CREATED="1703313727821" MODIFIED="1703313734372"/> <node TEXT="DBとは" ID="ID_101598045" CREATED="1703313734729" MODIFIED="1703313737449"/> <node TEXT="ファイルシステムとDBの違い" ID="ID_1786247161" CREATED="1703313740484" MODIFIED="1703313748867"/> <node TEXT="ファイルシステムとDBが持つ追加機能" ID="ID_1094923931" CREATED="1703313749849" MODIFIED="1703313784209"/> <node TEXT="GearsOSを使って実現する" ID="ID_646654551" CREATED="1703313787540" MODIFIED="1703313833292"/> <node TEXT="信頼性を向上する手法" ID="ID_578834327" CREATED="1703313866689" MODIFIED="1703313878304"/> <node TEXT="GearsOSのファイルシステムとDBの現状" ID="ID_90571671" CREATED="1703313901390" MODIFIED="1703313918619"/> <node TEXT="RedBlackTreeのコピーの実装" ID="ID_227598094" CREATED="1703313929273" MODIFIED="1703313941132"/> </node> <node TEXT="軽量継続を基本とする言語CbC" ID="ID_1037072660" CREATED="1701690246173" MODIFIED="1703311032386"> <node TEXT="処理の単位CodeGear" ID="ID_1818389006" CREATED="1703307708710" MODIFIED="1703307746215"/> <node TEXT="データの単位DataGear" ID="ID_1930250223" CREATED="1703307746950" MODIFIED="1703307753688"/> <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844"> <node TEXT="リフレクション" ID="ID_355579006" CREATED="1703308504930" MODIFIED="1703308513027"/> </node> <node TEXT="gotoによる軽量継続" ID="ID_726882949" CREATED="1703307895880" MODIFIED="1703307911540"/> <node TEXT="CodeGearの記述例" ID="ID_1731637915" CREATED="1703307784821" MODIFIED="1703307887307"/> <node TEXT="CbCの現状" ID="ID_950222443" CREATED="1703307926203" MODIFIED="1703307929709"/> </node> <node TEXT="信頼性の保証を目的としたGearsOS" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671"> <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"/> <node TEXT="メタ処理を記述するmetaGear" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823"/> <node TEXT="CodeGearの遷移" ID="ID_1403713795" CREATED="1703310522532" MODIFIED="1703310534184"/> <node TEXT="全てのGearを参照するContext" ID="ID_91888278" CREATED="1703309731224" MODIFIED="1703310166027"/> <node TEXT="GearsOSの記述例" ID="ID_227287316" CREATED="1703310975416" MODIFIED="1703310983579"/> <node TEXT="GearsOSの現状" ID="ID_468728002" CREATED="1703310866177" MODIFIED="1703310871670"/> </node> <node TEXT="GearsFileSystem" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1701694184160"> <node TEXT="DataGearManagerによる分散ファイルシステム" ID="ID_540180010" CREATED="1703315001066" MODIFIED="1703315085575"/> <node TEXT="i-nodeを用いたファイルシステム" ID="ID_1851664363" CREATED="1703314946289" MODIFIED="1703492949059"/> <node TEXT="非破壊RedBlackTreeによる構成" ID="ID_262332331" CREATED="1701696133124" MODIFIED="1701696237170"/> <node TEXT="RedBlackTreeのトランザクション" ID="ID_1088328123" CREATED="1701696247760" MODIFIED="1702112463420" HGAP_QUANTITY="14.75 pt" VSHIFT_QUANTITY="3.75 pt"/> <node TEXT="ディスク上とメモリ上のデータ構造" ID="ID_683338430" CREATED="1701696165502" MODIFIED="1701696179372"/> </node> <node TEXT="GearsFileSystemにおけるGCとレプリケーションの仕組み" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1702112470212" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> <node TEXT="CopyRedBlackTreeによるGCの仕組み" ID="ID_694714867" CREATED="1701696212033" MODIFIED="1703491006779"/> <node TEXT="CopyRedBlackTreeによるレプリケーションの仕組み" ID="ID_1106336919" CREATED="1703490971550" MODIFIED="1703491035629"/> </node> <node TEXT="CopyRedBlackTreeの実装" ID="ID_1619882257" CREATED="1701697553803" MODIFIED="1703491075408" VSHIFT_QUANTITY="-4.5 pt"> <node TEXT="コピーのアルゴリズム" ID="ID_64994373" CREATED="1703491215841" MODIFIED="1703491223454"/> <node TEXT="Stackの使用に関して" ID="ID_432827984" CREATED="1703492856041" MODIFIED="1703492863503"/> <node TEXT="証明のしやすさについて" ID="ID_2776247" CREATED="1703492904417" MODIFIED="1703492910899"/> </node> <node TEXT="信頼性" ID="ID_1221084016" CREATED="1702289777950" MODIFIED="1702289781581"> <node TEXT="モデル検査とAgdaによる実装" ID="ID_1438858883" CREATED="1702289781790" MODIFIED="1702289794818"/> </node> <node TEXT="評価" ID="ID_1053436711" CREATED="1702112499515" MODIFIED="1702112509004"/> <node TEXT="今後" ID="ID_87524419" CREATED="1702112509364" MODIFIED="1702112512270"/> </node> <node TEXT="修論で言いたいこと" POSITION="left" ID="ID_1194781583" CREATED="1701690732709" MODIFIED="1701696321975" HGAP_QUANTITY="29 pt" VSHIFT_QUANTITY="134.25 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="GearsFileSystem" POSITION="left" ID="ID_1481163553" CREATED="1701697697176" MODIFIED="1701697708604"/> </node> </map>