Mercurial > hg > Papers > 2024 > matac-master

comparison mindmaps/gears_fs_db.mm @ 17:6b40679f0eef

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 Mon, 08 Jan 2024 20:22:51 +0900
parents 7d7117822000
children 66e1b4c4df1f
comparison
equal deleted inserted replaced
16:110cf95f4106 17:6b40679f0eef
1 <map version="freeplane 1.9.8"> 1 <map version="freeplane 1.9.8">
2 <!--To view this file, download free mind mapping software Freeplane from https://www.freeplane.org --> 2 <!--To view this file, download free mind mapping software Freeplane from https://www.freeplane.org -->
3 <node TEXT="GearsOS上のファイルシステムとDBの信頼性(仮)" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1702111913150" STYLE="oval"> 3 <node TEXT="GearsOS上のファイルシステムとDBの信頼性(仮)" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1702111913150" STYLE="oval">
4 <font SIZE="18"/> 4 <font SIZE="18"/>
5 <hook NAME="MapStyle"> 5 <hook NAME="MapStyle" zoom="0.8">
6 <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"/> 6 <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"/>
7 7
8 <map_styles> 8 <map_styles>
9 <stylenode LOCALIZED_TEXT="styles.root_node" STYLE="oval" UNIFORM_SHAPE="true" VGAP_QUANTITY="24 pt"> 9 <stylenode LOCALIZED_TEXT="styles.root_node" STYLE="oval" UNIFORM_SHAPE="true" VGAP_QUANTITY="24 pt">
10 <font SIZE="24"/> 10 <font SIZE="24"/>
395 </node> 395 </node>
396 <node TEXT="Gearの概念" ID="ID_1818389006" CREATED="1703307708710" MODIFIED="1704622216143"/> 396 <node TEXT="Gearの概念" ID="ID_1818389006" CREATED="1703307708710" MODIFIED="1704622216143"/>
397 <node TEXT="gotoによる軽量継続" ID="ID_726882949" CREATED="1703307895880" MODIFIED="1703307911540"/> 397 <node TEXT="gotoによる軽量継続" ID="ID_726882949" CREATED="1703307895880" MODIFIED="1703307911540"/>
398 <node TEXT="CodeGearの記述例" ID="ID_1731637915" CREATED="1703307784821" MODIFIED="1703307887307"/> 398 <node TEXT="CodeGearの記述例" ID="ID_1731637915" CREATED="1703307784821" MODIFIED="1703307887307"/>
399 </node> 399 </node>
400 <node TEXT="信頼性の保証を目的としたGearsOS" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671"> 400 <node TEXT="信頼性の保証を目的としたGearsOS" FOLDED="true" ID="ID_1315567458" CREATED="1701692210913" MODIFIED="1703311040671">
401 <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"/> 401 <node TEXT="3種類のGearsOS" ID="ID_1326415213" CREATED="1703309744902" MODIFIED="1703309750565"/>
402 <node TEXT="メタ処理を記述するmetaGear" FOLDED="true" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823"> 402 <node TEXT="メタ処理を記述するmetaGear" FOLDED="true" ID="ID_1666892566" CREATED="1703309692742" MODIFIED="1703309713823">
403 <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844"> 403 <node TEXT="ノーマルレベルとメタレベルの切り分け" ID="ID_719507396" CREATED="1703308470210" MODIFIED="1703308478844">
404 <node TEXT="リフレクション" ID="ID_355579006" CREATED="1703308504930" MODIFIED="1703308513027"/> 404 <node TEXT="リフレクション" ID="ID_355579006" CREATED="1703308504930" MODIFIED="1703308513027"/>
405 </node> 405 </node>
411 <node TEXT="Treeを継承している" ID="ID_830044324" CREATED="1704625938387" MODIFIED="1704625986222"/> 411 <node TEXT="Treeを継承している" ID="ID_830044324" CREATED="1704625938387" MODIFIED="1704625986222"/>
412 <node TEXT="Treeはput, get, removeを持つ" ID="ID_325206226" CREATED="1704625785328" MODIFIED="1704625993146"/> 412 <node TEXT="Treeはput, get, removeを持つ" ID="ID_325206226" CREATED="1704625785328" MODIFIED="1704625993146"/>
413 <node TEXT="Copyがない" ID="ID_1861504637" CREATED="1704625774975" MODIFIED="1704625778526"/> 413 <node TEXT="Copyがない" ID="ID_1861504637" CREATED="1704625774975" MODIFIED="1704625778526"/>
414 </node> 414 </node>
415 </node> 415 </node>
416 <node TEXT="GearsOSのファイルシステム(現状の話" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1704630791818"> 416 <node TEXT="GearsOSのファイルシステム(現状の話" FOLDED="true" ID="ID_667012992" CREATED="1701694178540" MODIFIED="1704630791818">
417 <node TEXT="GearsOSのファイルシステム" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1704630099465"> 417 <node TEXT="GearsOSのファイルシステム" ID="ID_188577314" CREATED="1704630094596" MODIFIED="1704630099465">
418 <node TEXT="ファイルシステムはOSの重要な機能である" ID="ID_46805604" CREATED="1704630103040" MODIFIED="1704630119191"/> 418 <node TEXT="ファイルシステムはOSの重要な機能である" ID="ID_46805604" CREATED="1704630103040" MODIFIED="1704630119191"/>
419 <node TEXT="分散ファイルシステムとi-nodeを用いたファイルシステムが存在する" ID="ID_1509553363" CREATED="1704630119858" MODIFIED="1704630152926"/> 419 <node TEXT="分散ファイルシステムとi-nodeを用いたファイルシステムが存在する" ID="ID_1509553363" CREATED="1704630119858" MODIFIED="1704630152926"/>
420 </node> 420 </node>
421 <node TEXT="DataGearManagerによる分散ファイルシステム" ID="ID_540180010" CREATED="1703315001066" MODIFIED="1703315085575"> 421 <node TEXT="DataGearManagerによる分散ファイルシステム" ID="ID_540180010" CREATED="1703315001066" MODIFIED="1703315085575">
433 </node> 433 </node>
434 </node> 434 </node>
435 <node TEXT="GearsFileSystemにおけるGCとレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1704632532265" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt"> 435 <node TEXT="GearsFileSystemにおけるGCとレプリケーション" ID="ID_1092227909" CREATED="1701690558237" MODIFIED="1704632532265" HGAP_QUANTITY="16.25 pt" VSHIFT_QUANTITY="-1.5 pt">
436 <node TEXT="ファイルシステムの信頼性" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1704630267498"> 436 <node TEXT="ファイルシステムの信頼性" ID="ID_200982245" CREATED="1704630258973" MODIFIED="1704630267498">
437 <node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/> 437 <node TEXT="信頼性に関する追加機能" ID="ID_1574949535" CREATED="1704630312069" MODIFIED="1704630320377"/>
438 <node TEXT="これらは実装されていない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704630331968"/> 438 <node TEXT="GCやレプリケーションの機能がない" ID="ID_878946385" CREATED="1704630323433" MODIFIED="1704632961588"/>
439 <node TEXT="実装するためにはデータのCopyが必要" ID="ID_822351907" CREATED="1704630337081" MODIFIED="1704630382753"/> 439 <node TEXT="実装するためにはデータのCopyが必要" ID="ID_822351907" CREATED="1704630337081" MODIFIED="1704630382753"/>
440 <node TEXT="現状はTreeにCopyがない" ID="ID_65833123" CREATED="1704630383271" MODIFIED="1704630397371"/> 440 <node TEXT="現状はTreeにCopyがない" ID="ID_65833123" CREATED="1704630383271" MODIFIED="1704630397371"/>
441 <node TEXT="" ID="ID_1314300132" CREATED="1704632535428" MODIFIED="1704632535428"/> 441 <node TEXT="Copyを実装したい" ID="ID_1314300132" CREATED="1704632535428" MODIFIED="1704632976417"/>
442 </node> 442 </node>
443 <node TEXT="RedBlackTreeは単なる2分木" ID="ID_1037813952" CREATED="1704632767323" MODIFIED="1704632780206"/> 443 <node TEXT="GearsFileSystemのGC" ID="ID_442801060" CREATED="1704692757836" MODIFIED="1704692764197">
444 <node TEXT="GCの種類" ID="ID_1746770811" CREATED="1704695739812" MODIFIED="1704696582051">
445 <node TEXT="CopyingGCとは" ID="ID_344664264" CREATED="1704692777863" MODIFIED="1704692782352">
446 <node TEXT="正確なGC" ID="ID_267216671" CREATED="1704696904268" MODIFIED="1704696908732"/>
447 <node TEXT="ヒープ領域をFrom領域とTo領域に分割" ID="ID_1262852949" CREATED="1704711856815" MODIFIED="1704711932146"/>
448 <node TEXT="ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする" ID="ID_1311182649" CREATED="1704711932613" MODIFIED="1704711957213"/>
449 </node>
450 <node TEXT="Reference counting GC" ID="ID_776539806" CREATED="1704696590166" MODIFIED="1704696594363">
451 <node TEXT="オブジェクトの被参照数を表すカウンタを用いる" ID="ID_166536665" CREATED="1704710714477" MODIFIED="1704710852447"/>
452 <node TEXT="被参照数が0になった時オブジェクトが解放される" ID="ID_1678718232" CREATED="1704711836498" MODIFIED="1704711854290"/>
453 </node>
454 <node TEXT="Mark \&amp; Sweep GC" ID="ID_715438606" CREATED="1704696594768" MODIFIED="1704696598757">
455 <node TEXT="マークフェーズとスイープフェーズからなる" ID="ID_1584128194" CREATED="1704710119330" MODIFIED="1704710167419"/>
456 <node TEXT="マークフェーズ" ID="ID_393316688" CREATED="1704710141321" MODIFIED="1704710158148">
457 <node TEXT="生きているオブジェクト全てにマークをつける" ID="ID_684669159" CREATED="1704710178984" MODIFIED="1704710191749"/>
458 </node>
459 <node TEXT="スイープフェーズ" ID="ID_1823266942" CREATED="1704710168764" MODIFIED="1704710173540">
460 <node TEXT="マークがつけられなかったオブジェクトを回収する" ID="ID_1569463715" CREATED="1704710220250" MODIFIED="1704710369400"/>
461 </node>
462 </node>
463 </node>
464 <node TEXT="GCは併用される" ID="ID_1496671439" CREATED="1704696631667" MODIFIED="1704696640285"/>
465 <node TEXT="Rustのスマートポインタ" ID="ID_881149259" CREATED="1704696608959" MODIFIED="1704696615328"/>
466 <node TEXT="CopyingGCを用いる" ID="ID_1639428535" CREATED="1704692768575" MODIFIED="1704692777490">
467 <node TEXT="なぜCopyingGCなのか" ID="ID_1226680678" CREATED="1704696722580" MODIFIED="1704696736347">
468 <node TEXT="全てのデータはRedBlackTreeに格納される" ID="ID_1096077315" CREATED="1704710451766" MODIFIED="1704710463902">
469 <node TEXT="(使用中のデータ)" ID="ID_55750630" CREATED="1704710470136" MODIFIED="1704710480143"/>
470 </node>
471 <node TEXT="木を辿れば全ての生きているオブジェクトを参照することが可能" ID="ID_1690086792" CREATED="1704710464413" MODIFIED="1704710513053">
472 <node TEXT="正確なGC" ID="ID_1987344082" CREATED="1704710533695" MODIFIED="1704710540754"/>
473 </node>
474 <node TEXT="なのでCopyingGCを簡単に適用できる" ID="ID_1935146464" CREATED="1704710513688" MODIFIED="1704710568354"/>
475 </node>
476 <node TEXT="どのように利用するか" ID="ID_549509034" CREATED="1704696775586" MODIFIED="1704696779463">
477 <node TEXT="通常のCopyingGCではヒープ領がコピーされる" ID="ID_830576894" CREATED="1704692782815" MODIFIED="1704692814222"/>
478 <node TEXT="GearsFileSystemの場合は木をコピーする" ID="ID_1003156855" CREATED="1704692814851" MODIFIED="1704692831840"/>
479 <node TEXT="参照しているオブジェクトは木のルートから辿れる" ID="ID_1653048898" CREATED="1704696789481" MODIFIED="1704696806177"/>
480 <node TEXT="辿れるノードのみコピーするだけでGCになる" ID="ID_355389629" CREATED="1704696807343" MODIFIED="1704696829530"/>
481 </node>
482 <node TEXT="併用はしないのか" ID="ID_939269191" CREATED="1704696736711" MODIFIED="1704696742433"/>
483 <node TEXT="Rustのスマートポインタのような仕組みにしないのか" ID="ID_110730790" CREATED="1704696742911" MODIFIED="1704696758432"/>
484 </node>
485 </node>
444 <node TEXT="RedBlackTreeのコピーを用いる" ID="ID_1495626047" CREATED="1704630409263" MODIFIED="1704632465291"> 486 <node TEXT="RedBlackTreeのコピーを用いる" ID="ID_1495626047" CREATED="1704630409263" MODIFIED="1704632465291">
445 <node TEXT="Copy" ID="ID_1713857745" CREATED="1699848476363" MODIFIED="1699848479936"> 487 <node TEXT="Copy" ID="ID_1713857745" CREATED="1699848476363" MODIFIED="1699848479936">
446 <node TEXT="単なる2分木のコピー" ID="ID_1165724596" CREATED="1699849455588" MODIFIED="1699849469353"/> 488 <node TEXT="単なる2分木のコピー" ID="ID_1165724596" CREATED="1699849455588" MODIFIED="1699849469353"/>
447 <node TEXT="Stack無しで書くとおそらく結構複雑" ID="ID_1214201745" CREATED="1699849470075" MODIFIED="1699857892247"/> 489 <node TEXT="Stack無しで書くとおそらく結構複雑" ID="ID_1214201745" CREATED="1699849470075" MODIFIED="1699857892247"/>
448 <node TEXT="木を辿るためにStackを使う" ID="ID_278711519" CREATED="1699849561986" MODIFIED="1699849582652"> 490 <node TEXT="木を辿るためにStackを使う" ID="ID_278711519" CREATED="1699849561986" MODIFIED="1699849582652">
449 <node TEXT="コピー後に消されるので使って良い" ID="ID_841332618" CREATED="1701690823328" MODIFIED="1701690834394"/> 491 <node TEXT="コピー後に消されるので使って良い" ID="ID_841332618" CREATED="1701690823328" MODIFIED="1701690834394"/>
450 </node> 492 </node>
451 <node TEXT="アルゴリズム" ID="ID_1656007390" CREATED="1699849518269" MODIFIED="1699849522647">
452 <node TEXT="左側を深さ優先で辿る" ID="ID_1668782448" CREATED="1699849525266" MODIFIED="1699849604742">
453 <node TEXT="Stack push" ID="ID_687427551" CREATED="1699849778090" MODIFIED="1699849781012"/>
454 </node>
455 <node TEXT="アロケートしたノードは別のContext上に作る" ID="ID_143303559" CREATED="1699849620905" MODIFIED="1699849638042">
456 <node TEXT="GCのため" ID="ID_938753766" CREATED="1699849638520" MODIFIED="1699849668501"/>
457 <node TEXT="Copy後古いContextを消す" ID="ID_743040439" CREATED="1699849646521" MODIFIED="1699849693755"/>
458 <node TEXT="メモリ管理をモナドで表していることになる" ID="ID_4878265" CREATED="1699849705089" MODIFIED="1699849715878"/>
459 </node>
460 <node TEXT="リーフまで降りたらroot方向に木を戻る" ID="ID_1651314723" CREATED="1699849731393" MODIFIED="1699849765553">
461 <node TEXT="Stack pop" ID="ID_657141661" CREATED="1699849765982" MODIFIED="1699849773214"/>
462 <node TEXT="右側を呼び出す" ID="ID_412841654" CREATED="1699849789218" MODIFIED="1699849803550"/>
463 </node>
464 <node TEXT="Stackを2つ使うならば" ID="ID_179912595" CREATED="1699849785880" MODIFIED="1699850937824">
465 <node TEXT="全体のStack" ID="ID_605104581" CREATED="1699850965212" MODIFIED="1699858010811">
466 <node TEXT="originの木を辿るために使う" ID="ID_742122803" CREATED="1699858046929" MODIFIED="1699858071837"/>
467 </node>
468 <node TEXT="途中のStack" ID="ID_1233298698" CREATED="1699850966215" MODIFIED="1699858024318">
469 <node TEXT="右側を呼び出す際にそれまでの左側部分木を保持" ID="ID_573311498" CREATED="1699851138198" MODIFIED="1699858042178"/>
470 </node>
471 </node>
472 </node>
473 <node TEXT="Copy前後の同一性確認が必要" ID="ID_659073251" CREATED="1699849956727" MODIFIED="1699849974942"/> 493 <node TEXT="Copy前後の同一性確認が必要" ID="ID_659073251" CREATED="1699849956727" MODIFIED="1699849974942"/>
474 <node TEXT="Copy中の変更" ID="ID_58260128" CREATED="1699849982760" MODIFIED="1699849992692"/> 494 <node TEXT="Copy中の変更" ID="ID_58260128" CREATED="1699849982760" MODIFIED="1699849992692"/>
475 <node TEXT="毎回全てをGCするか" ID="ID_1441955822" CREATED="1699858222922" MODIFIED="1699858309153"> 495 <node TEXT="毎回全てをGCするか" ID="ID_1441955822" CREATED="1699858222922" MODIFIED="1699858309153">
476 <node TEXT="アクセス頻度によって世代分けする" ID="ID_1844124057" CREATED="1699858236610" MODIFIED="1699858248665"/> 496 <node TEXT="アクセス頻度によって世代分けする" ID="ID_1844124057" CREATED="1699858236610" MODIFIED="1699858248665"/>
477 <node TEXT="ほとんどアクセスされないデータはGC対象から除く" ID="ID_279065121" CREATED="1699858262921" MODIFIED="1699858318515"/> 497 <node TEXT="ほとんどアクセスされないデータはGC対象から除く" ID="ID_279065121" CREATED="1699858262921" MODIFIED="1699858318515"/>
488 <node TEXT="insert, delete" ID="ID_252146025" CREATED="1699869929471" MODIFIED="1699869933942"/> 508 <node TEXT="insert, delete" ID="ID_252146025" CREATED="1699869929471" MODIFIED="1699869933942"/>
489 </node> 509 </node>
490 </node> 510 </node>
491 </node> 511 </node>
492 </node> 512 </node>
513 <node TEXT="RedBlackTreeは単なる2分木" ID="ID_1037813952" CREATED="1704632767323" MODIFIED="1704632780206"/>
493 </node> 514 </node>
494 <node TEXT="CopyRedBlackTreeによるGCの仕組み" ID="ID_694714867" CREATED="1701696212033" MODIFIED="1703491006779"> 515 <node TEXT="CopyRedBlackTreeによるGCの仕組み" ID="ID_694714867" CREATED="1701696212033" MODIFIED="1703491006779">
495 <node TEXT="CopyingGCを使用する" ID="ID_1956008882" CREATED="1704630535071" MODIFIED="1704630542771"/> 516 <node TEXT="CopyingGCを使用する" ID="ID_1956008882" CREATED="1704630535071" MODIFIED="1704630542771"/>
496 <node TEXT="ディスク上とメモリ上の構造が同じ" ID="ID_1708669942" CREATED="1704630543186" MODIFIED="1704630559778"> 517 <node TEXT="ディスク上とメモリ上の構造が同じ" ID="ID_1708669942" CREATED="1704630543186" MODIFIED="1704630559778">
497 <node TEXT="データの一貫性" ID="ID_1054564074" CREATED="1704630577917" MODIFIED="1704630584566"/> 518 <node TEXT="データの一貫性" ID="ID_1054564074" CREATED="1704630577917" MODIFIED="1704630584566"/>