Mercurial > hg > Papers > 2023 > matac-sigos

changeset 44:87fb055f5dc8

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, 15 May 2023 16:30:47 +0900
parents be0dd5bd0e7b
children e7cc3c4cc73d
files gearsos_db.mm marp-slide/slide.md
diffstat 2 files changed, 110 insertions(+), 55 deletions(-) [+]
line wrap: on
line diff
--- a/gearsos_db.mm	Sun May 14 17:48:26 2023 +0900
+++ b/gearsos_db.mm	Mon May 15 16:30:47 2023 +0900
@@ -381,7 +381,6 @@
 </node>
 <node TEXT="実装がブロックベース" ID="ID_1622511458" CREATED="1683965098335" MODIFIED="1683965103540">
 <node TEXT="Diskの実装に引きづられている" ID="ID_1120519843" CREATED="1683965105823" MODIFIED="1683965115731"/>
-<node TEXT="" ID="ID_1220596137" CREATED="1683965122928" MODIFIED="1683965122928"/>
 </node>
 <node TEXT="第一正規形" ID="ID_759170373" CREATED="1683965127529" MODIFIED="1683965145748">
 <node TEXT="表がネストしてないこと" ID="ID_489015288" CREATED="1683965149516" MODIFIED="1683965158309"/>
--- a/marp-slide/slide.md	Sun May 14 17:48:26 2023 +0900
+++ b/marp-slide/slide.md	Mon May 15 16:30:47 2023 +0900
@@ -4,6 +4,12 @@
 paginate: true
 ---
 
+<!-- 全体の流れ
+- 目的
+- 基礎概念
+- 問題提起 -> 解決 の繰り返し
+- 評価 -->
+
 # Gears OSのファイルシステムとDB
 
 <!--
@@ -55,38 +61,39 @@
 
 <!-- 全体的な問題提起 -->
 
-## OSとFSとDBがバラバラ
+<!-- ## OSとFSとDBがバラバラ
 
 - 全体を組み合わせた時の正しさが怪しい
 - DBは実はファイルの上に作られていたり
   - ファイルに対する書き込みのatomicityが保証されてない
 - それぞれ別々なトランザクションがある
+- ファイルシステムとDBをRedBlackTreeで統一 -->
 
----
+<!-- --- -->
 
 <!-- 全体的(検証における)解決方法 -->
 
-## FSとDBの要素をRBTreeに対応させる
+<!-- ## FSとDBの要素をRBTreeに対応させる -->
 
 <!-- システムの構成要素全体にこれらの方法を適用するために -->
 
-- ファイルシステムとDBをRedBlackTreeで統一
+<!-- - ファイルシステムとDBをRedBlackTreeで統一
   - 信頼性向上のために必要なDBの仕組み
   - データ持続性に必要なファイルシステムの仕組み
 - RedBlackTreeはinvariantで証明する
 - システム統一によりシステム全体の検証が簡単に
-- トランザクションの統一化
+- トランザクションの統一化 -->
 
 <!-- FS, DBの統一的な実装により，複雑性が取り払われ正しさの検証が楽になる -->
 
----
+<!-- ---
 
 ## 実装がブロックベース
 
 - B-Treeによる実装はディスクのブロックアクセスが前提
 - SSDのようなランダムアクセスが前提となっていない
 - ランダムアクセスの場合B-Treeを用いる利点は少ない
-- 証明しやすいRedBlackTreeを用いることが考えられる
+- 証明しやすいRedBlackTreeを用いることが考えられる -->
 
 ---
 
@@ -140,20 +147,33 @@
 
 ---
 
-## ファイルシステムとDB
+## OSとFSとDBがバラバラ
 
-<!-- ここから本編 -->
+<!-- 問題提起1 統一化 -->
 
-- 両方ともRedBlackTreeで実装する
-  - 本質的な役割は一緒
-  - 信頼性の向上
-  - 証明のしやすさ
-- 非破壊Tree
-  - データの持続性
+- 全体を組み合わせた時の正しさが怪しい
+- DBは実はファイルの上に作られていたり
+  - ファイルに対する書き込みのatomicityが保証されてない
+- それぞれ別々なトランザクションがある
+- ファイルシステムが提供してるトランザクションが明快でない
+- ファイルシステムとDBをRedBlackTreeで統一
 
 ---
 
-<!-- 問題提起 -->
+## ファイルシステムとDB
+
+<!--
+解決1
+-->
+
+- 両方ともRedBlackTreeで実装する
+  - 信頼性向上
+  - 証明のしやすさ
+  - 本質的な役割は一緒
+
+---
+
+<!-- 問題提起2 持続性 -->
 
 ## データの持続性
 
@@ -172,12 +192,40 @@
 
 ## 非破壊的なRedBlackTree
 
-<!-- これで統一することでトランザクションの統一が可能という話を入れたい -->
+<!-- 解決2 -->
 
 ![w:1100](figs/nondestructive_tree_modification.png)
 
 ---
 
+## データの持続性
+
+<!--
+解決2
+ディスク上とメモリ上のデータ構造が一緒という話を入れる
+-->
+
+- オンメモリーなRedBlackTree
+- SSD上のコピー
+  - ログ的にコピーしていく
+  - Copying GC
+
+---
+
+<!-- 補足 B-treeがよく用いられるがそうでなくて良いの？という感じ -->
+
+## 実装がブロックベース
+
+- B-Treeによる実装
+  - ディスクのブロックアクセスが前提
+  - SSDのようなランダムアクセスが前提となっていない
+- ランダムアクセスの場合B-Treeを用いる利点は少ない
+- 証明しやすいRedBlackTreeを用いることが考えられる
+
+---
+
+<!-- 本システムでテーブルはこのように表現される->問題提起へ -->
+
 ## RedBlackTreeはDBのテーブル
 
 - テーブルのキーがRedBlackTreeのkey
@@ -186,41 +234,25 @@
 
 ![bg right:45% 65%](figs/transaction.svg)
 
----
-
-## データの持続性
-
-<!-- ディスク上とメモリ上のデータ構造が一緒という話を入れる -->
-<!-- 解決方法 -->
-
-- オンメモリーなRedBlackTree
-- SSD上のコピー
-  - ログ的にコピーしていく
-  - Copying GC
+<!-- テーブルといえばスキーマ，という感じで次の問題へ -->
 
 ---
 
-<!-- 問題提起 -->
+<!-- 問題提起3 スキーマ 
+最終的にFSのような柔軟性を持ち合わせることで解決 -->
+
+## スキーマ
 
-スキーマ
-    テーブルに入るレコードの決まった形
-    実は頻繁に変更される
-    なので動的な属性名を設定されたりする
-    DB理論が役に立たない
-    過去のDBとの互換性がない
-    扱うデータはjsonなどで，もはや第一正規形でない
-    ファイルシステムには型が存在しない
-    ファイルシステムが提供してるトランザクションが明快でない
-第一正規形
-    表がネストしてないこと
-    実際にプログラムに出てくるのはstack, list, queue
-        これらは第一正規形ではない
-        なのでFSになってる
-<!-- 第一正規形を満たさないデータを扱う場合はFSが必要 -->
+- 実は頻繁に変更される
+  - なので動的な属性名を設定されたりする
+- DB理論が役に立たない
+- 過去のDBとの互換性がない
+- 扱うデータはjsonなどで，もはや第一正規形でない
+- ファイルシステムには型が存在しない
 
 ---
 
-<!-- 解決方法 -->
+<!-- 解決3 解決したいが...とone step置く -->
 
 ## スキーマ
 
@@ -230,7 +262,7 @@
 
 ---
 
-<!-- 解決方法 -->
+<!-- 解決3 解決したいが...とone step置く -->
 
 ## インピーダンスミスマッチ
 
@@ -244,7 +276,7 @@
 
 ---
 
-<!-- 解決方法 -->
+<!-- 本解決3 -->
 
 ## RedBlackTreeベースのファイルシステム
 
@@ -254,6 +286,8 @@
   - オンメモリーなRedBlackTree
   - SSD上のコピー
     - ログ的にコピーしていく
+- 正しくスキーマに対応しているかどうか
+  - 違反しても良い
 
 ---
 
@@ -268,14 +302,23 @@
 
 ---
 
+## RedBlackTreeによる権限の表現
+
+- metaDGで行う
+- ContextからアクセスできるRedBlackTreeがある
+
+---
+
+<!-- 一旦解決したことをまとめて，その後評価 -->
+
 ## 構成要素
 
 - すべてRedBlackTreeで構成されている
   - 検証はRedBlackTreeだけで良い
   - invariantで証明する
-- RedBlackTreeによる権限の表現
-  - metaDGで行う
-  - ContextからアクセスできるRedBlackTreeがある
+  - トランザクション統一化
+  - 持続性
+  - 柔軟なスキーマ
 
 ---
 
@@ -285,15 +328,22 @@
 - トランザクションの正しさ
 - アクセス権限の正しさ
 - SSDへのコピーの正しさ
-- ポータビリティ
-  - 異なる計算機アーキテクチャ
-  - 異なるエンコード
-  - 異なる分散ノード
 - 正しくスキーマに対応しているかどうか
   - 違反しても良い
 
 ---
 
+## 色々問題はある
+
+- 非破壊ツリーのコピーはメモリ量的にダメではないか
+- トランザクションが正しく表現されているか
+  - RBTreeのルート入れ替えのみ
+- 証明できるか
+- 後方互換性
+- メモリプロテクションなどの既存のシステムを使わなくて良いか
+
+---
+
 ## 今後の課題
 
 - データクエリ言語
@@ -305,4 +355,10 @@
 - スタンドアロンなDB
   - ポータビリティ
 
+<!--
+  - 異なる計算機アーキテクチャ
+  - 異なるエンコード
+  - 異なる分散ノード 
+-->
+
 <!-- 今後やりたいことで締めるとなんか締まりがない... -->
\ No newline at end of file