Mercurial > hg > Papers > 2023 > matac-sigos
changeset 43:be0dd5bd0e7b
...
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 14 May 2023 17:48:26 +0900 |
| parents | 0a64058c27fc |
| children | 87fb055f5dc8 |
| files | gearsos_db.mm marp-slide/slide.md |
| diffstat | 2 files changed, 86 insertions(+), 139 deletions(-) [+] |
line wrap: on
line diff
--- a/gearsos_db.mm Sun May 14 01:19:34 2023 +0900 +++ b/gearsos_db.mm Sun May 14 17:48:26 2023 +0900 @@ -2,7 +2,7 @@ <!--To view this file, download free mind mapping software Freeplane from https://www.freeplane.org --> <node TEXT="Gears OSの
FS & DB" FOLDED="false" ID="ID_452131666" CREATED="1610381621610" MODIFIED="1680514786893" STYLE="oval"> <font SIZE="18"/> -<hook NAME="MapStyle"> +<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"/> <map_styles>
--- a/marp-slide/slide.md Sun May 14 01:19:34 2023 +0900 +++ b/marp-slide/slide.md Sun May 14 17:48:26 2023 +0900 @@ -49,16 +49,48 @@ - テスト - モデル検査 - システムの構成要素全体にこれらの方法を適用したい +- 既存システムの信頼性における問題点の解決 --- +<!-- 全体的な問題提起 --> + +## OSとFSとDBがバラバラ + +- 全体を組み合わせた時の正しさが怪しい +- DBは実はファイルの上に作られていたり + - ファイルに対する書き込みのatomicityが保証されてない +- それぞれ別々なトランザクションがある + +--- + +<!-- 全体的(検証における)解決方法 --> + ## FSとDBの要素をRBTreeに対応させる -- ファイルシステムとDBをRedBlackTreeで統一する +<!-- システムの構成要素全体にこれらの方法を適用するために --> + +- ファイルシステムとDBをRedBlackTreeで統一 - 信頼性向上のために必要なDBの仕組み - データ持続性に必要なファイルシステムの仕組み - RedBlackTreeはinvariantで証明する - - RedBlackTreeのみのシンプルな実装 +- システム統一によりシステム全体の検証が簡単に +- トランザクションの統一化 + +<!-- FS, DBの統一的な実装により，複雑性が取り払われ正しさの検証が楽になる --> + +--- + +## 実装がブロックベース + +- B-Treeによる実装はディスクのブロックアクセスが前提 +- SSDのようなランダムアクセスが前提となっていない +- ランダムアクセスの場合B-Treeを用いる利点は少ない +- 証明しやすいRedBlackTreeを用いることが考えられる + +--- + +## Gears OSの基礎概念 --- @@ -110,6 +142,8 @@ ## ファイルシステムとDB +<!-- ここから本編 --> + - 両方ともRedBlackTreeで実装する - 本質的な役割は一緒 - 信頼性の向上 @@ -119,8 +153,27 @@ --- +<!-- 問題提起 --> + +## データの持続性 + +- メモリとディスクみたいな分け方が時代遅れに + - ほとんどのデータはメモリ上にある + - 分散ノード上に多重のコピーが存在する + - 分散台帳などの多様なconsistensyがある +- 多様なストレージ階層に対応できていない + - 大量のメモリ + - NVMe + - SSD + - RAID + - テープ + +--- + ## 非破壊的なRedBlackTree +<!-- これで統一することでトランザクションの統一が可能という話を入れたい --> +  --- @@ -137,14 +190,38 @@ ## データの持続性 +<!-- ディスク上とメモリ上のデータ構造が一緒という話を入れる --> +<!-- 解決方法 --> + - オンメモリーなRedBlackTree - SSD上のコピー - ログ的にコピーしていく - - - Copying GC --- +<!-- 問題提起 --> + +スキーマ + テーブルに入るレコードの決まった形 + 実は頻繁に変更される + なので動的な属性名を設定されたりする + DB理論が役に立たない + 過去のDBとの互換性がない + 扱うデータはjsonなどで，もはや第一正規形でない + ファイルシステムには型が存在しない + ファイルシステムが提供してるトランザクションが明快でない +第一正規形 + 表がネストしてないこと + 実際にプログラムに出てくるのはstack, list, queue + これらは第一正規形ではない + なのでFSになってる +<!-- 第一正規形を満たさないデータを扱う場合はFSが必要 --> + +--- + +<!-- 解決方法 --> + ## スキーマ - DBの各テーブルのレコードの型定義 @@ -153,6 +230,8 @@ --- +<!-- 解決方法 --> + ## インピーダンスミスマッチ - プログラムで使用するデータ構造 @@ -165,6 +244,8 @@ --- +<!-- 解決方法 --> + ## RedBlackTreeベースのファイルシステム - i-node番号をkeyにする @@ -224,138 +305,4 @@ - スタンドアロンなDB - ポータビリティ -<!-- - CodeGearがDataGearを受け取り，処理後にDataGearを次のCodeGearに渡すという動作をしているように見える -- 実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，それらの計算はMetaCodeGearで行われる --> - -<!-- ## RedBlackTreeを用いたFSの構築 - -- Gears OSへファイルシステムを実装するにあたり，RedBlackTreeを用いる -- DBはファイルシステムと本質的に同じ役割を持っているため，同じRedBlackTreeでDBも表現することが可能であると考える - -### Gears OSにおけるDBの機能を持ち合わせたファイルシステムの設計を</br>信頼性の向上と， RedBlackTreeのみのシンプルな構造を基軸として考える - - ---- - -## 非破壊的なRedBlackTree - -- Gears OSにおける永続データは非破壊的な編集を行うRedBlackTreeを用いて保存する -- ディレクトリシステム自体にバックアップの機能を搭載することが可能と考える - ---- - -## 非破壊的なRedBlackTree - - - ---- - -## ディスク上とメモリ上のデータ構造 - -- ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する -- ブロックアクセス数の観点ではRedBlackTreeはB-Treeに劣る -- しかしながら，SSDはランダムアクセスによってデータにアクセスするため，RedBlackTreeでなくB-Treeを用いる利点は少ないと考える -- データ構造を統一することで，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる - ---- - -## データのロールバックとバックアップ - -- RDBのロールバックは，コミットするまではトランザクションの開始時点に戻ることができる機能を持つ -- ロールバックはコミットが完了するとそれ以前の状態に戻すことはできないが，データのバックアップをとっておくことで復元を行う -- このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい - ---- - -## データのロールバックとバックアップ - -- RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用する -- 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす -- つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる -- よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える - ---- - -## データのロールバックとバックアップ - -- ルートノードはデータのアップデート時に増えるため，データが際限なく増加していく問題がある -- この問題はCopyingGCを行うことによって解決する -- まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する -- その後，コピーしたものはバックアップないしログとしてディスクに書き込む -- データの増加によるリソースの枯渇を防ぎ，かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる - ---- - -## トランザクション - -- トランザクションはDBの重要な機能の一つである -- データの競合を防ぎ信頼性を向上させるために，トランザクションの仕組みを考える必要がある -- ファイルシステムは全てRedBlackTreeで実装するため，RedBlackTreeのノードに対するトランザクションを考える -- トランザクションをwriteとreadに分けて考える - ---- - -## トランザクション - -### writeする場合 - -- トランザクションはRedBlackTreeのルートの置き換えと対応する -- writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える -- ルートの置き換えは競合的なので，複数プロセスから同時に書き込みを行っても1つしか成功しない -- 単一のRedBlackTreeに複数の書き込みポイントを作り，並行実行可能にする必要がある - ---- - -## トランザクション - -### 複数の書き込みポイント - -- RedBlackTreeに複数の書き込みポイントを作るために，キーごとのルートを作成する -- ノードはそれぞれがキーとRedBlackTreeを持つ状態になる -- writeする際は，そのキーのルートを置き換える - - ---- - -## トランザクション - -- Aの木はファイルシステム全体を表すRedBlackTreeである -- ノードNのデータに対して書き込みすることを考える -- キーがaであるBの木のルートからロックしCの木を作成して，Bの木からCの木のルートに入れ替えることで書き込みを行う - - - ---- - -## トランザクション - -### readする場合 - -- readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である -- しかし，常に最新の情報を読み込めるとは限らない -- 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる - ---- - -## ファイルシステムにおけるスキーマ - -- Gears OSのデータは全てDataGearで表されるため，Gears OSにおけるファイルシステムはDataGearの集合となる -- Gears OSにおけるスキーマとはDataGear上のキーの構成であることがわかる -- 今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す -- KernelのContext上にキーを用いたDataGearの参照を書き込む - ---- - -## 権限の表現 - -- ファイルの権限はファイルシステムの重要な機能の一つである -- 今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することがファイルに対して権限を設定することにあたる -- ルートに対してアクセスする権限がなければ，読み書きができないといった実装になると考える - ---- - -## 今後の課題・展望 - -- データクエリ言語 -- 時系列データ -- スタンドアロンDB --> \ No newline at end of file +<!-- 今後やりたいことで締めるとなんか締まりがない... --> \ No newline at end of file