Mercurial > hg > Papers > 2023 > matac-sigos
changeset 45:e7cc3c4cc73d
...
author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 15 May 2023 17:13:12 +0900 |
parents | 87fb055f5dc8 |
children | 8c04d935c7d1 |
files | marp-slide/slide.md |
diffstat | 1 files changed, 69 insertions(+), 76 deletions(-) [+] |
line wrap: on
line diff
--- a/marp-slide/slide.md Mon May 15 16:30:47 2023 +0900 +++ b/marp-slide/slide.md Mon May 15 17:13:12 2023 +0900 @@ -23,6 +23,8 @@ --- +<!-- 目的 --> + ## システム全体の信頼性を上げたい - システムの構成要素全体の信頼性を上げる必要がある @@ -59,47 +61,7 @@ --- -<!-- 全体的な問題提起 --> - -<!-- ## OSとFSとDBがバラバラ - -- 全体を組み合わせた時の正しさが怪しい -- DBは実はファイルの上に作られていたり - - ファイルに対する書き込みのatomicityが保証されてない -- それぞれ別々なトランザクションがある -- ファイルシステムとDBをRedBlackTreeで統一 --> - -<!-- --- --> - -<!-- 全体的(検証における)解決方法 --> - -<!-- ## FSとDBの要素をRBTreeに対応させる --> - -<!-- システムの構成要素全体にこれらの方法を適用するために --> - -<!-- - ファイルシステムとDBをRedBlackTreeで統一 - - 信頼性向上のために必要なDBの仕組み - - データ持続性に必要なファイルシステムの仕組み -- RedBlackTreeはinvariantで証明する -- システム統一によりシステム全体の検証が簡単に -- トランザクションの統一化 --> - -<!-- FS, DBの統一的な実装により,複雑性が取り払われ正しさの検証が楽になる --> - -<!-- --- - -## 実装がブロックベース - -- B-Treeによる実装はディスクのブロックアクセスが前提 -- SSDのようなランダムアクセスが前提となっていない -- ランダムアクセスの場合B-Treeを用いる利点は少ない -- 証明しやすいRedBlackTreeを用いることが考えられる --> - ---- - -## Gears OSの基礎概念 - ---- +<!-- ここからGears OSの基礎概念だと明示する --> ## Continuation based C @@ -141,6 +103,8 @@ --- +<!-- ここまでがGears OSの基礎概念だと明示する --> + ## CodeGear遷移の流れ ![w:1100](figs/context.svg) @@ -156,11 +120,10 @@ - ファイルに対する書き込みのatomicityが保証されてない - それぞれ別々なトランザクションがある - ファイルシステムが提供してるトランザクションが明快でない -- ファイルシステムとDBをRedBlackTreeで統一 --- -## ファイルシステムとDB +## FSとDBをRedBlackTreeで統一 <!-- 解決1 @@ -171,30 +134,50 @@ - 証明のしやすさ - 本質的な役割は一緒 +<!-- +これでFSとDBのシステムは統一化されるが +まだバラバラになっている部分はある +--> + --- -<!-- 問題提起2 持続性 --> +<!-- 問題提起2 +持続性 メモリやディスク,SSDは別々の仕組みをとっている +最終的に全てRBTreeで表現してしまおうという話に持っていく +--> ## データの持続性 +- メモリやディスク,SSDは別々の仕組みをとっている + - 持続されていない - メモリとディスクみたいな分け方が時代遅れに - ほとんどのデータはメモリ上にある - 分散ノード上に多重のコピーが存在する - 分散台帳などの多様なconsistensyがある -- 多様なストレージ階層に対応できていない - - 大量のメモリ - - NVMe - - SSD - - RAID - - テープ --- -## 非破壊的なRedBlackTree +<!-- 問題提起2 --> + +## ストレージ階層に対応できていない + +- 大量のメモリ +- NVMe +- SSD +- RAID +- テープ -<!-- 解決2 --> +--- + +<!-- 問題提起2 B-treeがよく用いられるがそうでなくて良いの?という感じ --> + +## 実装がブロックベース -![w:1100](figs/nondestructive_tree_modification.png) +- B-Treeによる実装 + - ディスクのブロックアクセスが前提 + - SSDのようなランダムアクセスが前提となっていない +- ランダムアクセスの場合B-Treeを用いる利点は少ない +- 証明しやすいRedBlackTreeを用いることが考えられる --- @@ -209,18 +192,15 @@ - SSD上のコピー - ログ的にコピーしていく - Copying GC + - メモリ上とSSD上のデータ構造を統一 --- -<!-- 補足 B-treeがよく用いられるがそうでなくて良いの?という感じ --> - -## 実装がブロックベース +## 非破壊的なRedBlackTree -- B-Treeによる実装 - - ディスクのブロックアクセスが前提 - - SSDのようなランダムアクセスが前提となっていない -- ランダムアクセスの場合B-Treeを用いる利点は少ない -- 証明しやすいRedBlackTreeを用いることが考えられる +<!-- 解決2 --> + +![w:1100](figs/nondestructive_tree_modification.png) --- @@ -241,20 +221,26 @@ <!-- 問題提起3 スキーマ 最終的にFSのような柔軟性を持ち合わせることで解決 --> -## スキーマ +## スキーマの問題 + +<!-- ファイルシステムにも型は必要 --> - 実は頻繁に変更される - なので動的な属性名を設定されたりする -- DB理論が役に立たない -- 過去のDBとの互換性がない + - DB理論が役に立たない + - 過去のDBとの互換性がない - 扱うデータはjsonなどで,もはや第一正規形でない - ファイルシステムには型が存在しない --- -<!-- 解決3 解決したいが...とone step置く --> +<!-- +スキーマ必要だ. +Gears OSではこのように表現できるね. +でも変更されちゃうのはどうするの +--> -## スキーマ +## Gears OSにおけるスキーマ - DBの各テーブルのレコードの型定義 - Contextに登録されているDataGearの型 @@ -272,7 +258,7 @@ - DBにはリストやキューは入らない - 第一正規系でないから - データ構造を持続的にしたい - - なのでファイルシステムが必要 + - なのでファイルシステムのような柔軟性が必要 --- @@ -293,6 +279,8 @@ ## バックアップとロールバック +<!-- SSD上のコピーという言葉が出てたよね --> + - ロールバックの必要性 - トランザクションの失敗 - システムクラッシュ @@ -319,11 +307,18 @@ - トランザクション統一化 - 持続性 - 柔軟なスキーマ +- バックアップとロールバック +- 権限の表現 --- ## 信頼性の保証 +<!-- +このような正しさを確認していく必要があるし, +他にも問題はある(次のスライド) +--> + - RedBlackTreeの変更の正しさ - トランザクションの正しさ - アクセス権限の正しさ @@ -346,6 +341,12 @@ ## 今後の課題 +<!-- + - 異なる計算機アーキテクチャ + - 異なるエンコード + - 異なる分散ノード +--> + - データクエリ言語 - SQL - SQLより良いものが欲しい @@ -353,12 +354,4 @@ - 時系列データ - データ圧縮 - スタンドアロンなDB - - ポータビリティ - -<!-- - - 異なる計算機アーキテクチャ - - 異なるエンコード - - 異なる分散ノード ---> - -<!-- 今後やりたいことで締めるとなんか締まりがない... --> \ No newline at end of file + - ポータビリティ \ No newline at end of file