Mercurial > hg > Papers > 2023 > matac-sigos
changeset 29:587197c3aa09
transaction
| author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 May 2023 16:32:47 +0900 |
| parents | 30fc12d776f1 |
| children | ce4af0b4df9d |
| files | marp-slide/figs/transaction.svg marp-slide/slide.md |
| diffstat | 2 files changed, 54 insertions(+), 56 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/marp-slide/figs/transaction.svg Fri May 12 16:32:47 2023 +0900 @@ -0,0 +1,1 @@ +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" width="383px" height="565px" viewBox="-0.5 -0.5 383 565" content="<mxfile><diagram id="L_h3FubKQM33HK9nJZH5" name="Page-1">7VvNk5owHP1rPLYDBPw47rrr9tKZzuyh7TEjUZmNhEJctX99AySQQFBQgV3qHlbyS4LhvZeXLxyB+fbwEsJg8524CI8swz2MwNPIshxgsv9x4JgGTGM6SSPr0HN5LA+8en+RKMijO89FkVKQEoKpF6jBJfF9tKRKDIYh2avFVgSr3xrANSoFXpcQl6M/PZdu0ujUmuTxb8hbb8Q3m+NZmrOFojB/kmgDXbKXQuB5BOYhITS92h7mCMfgCVzSeouK3KxhIfJpnQpT3gx6FM+GXPaoPOkTn308bugWs5TJLtHBo7/YtfHV4anfUs5TzLAhEkeR8Gl4lCrFyd9yXl4tSeX13IeYrLwhLLLwMOb5EQ3JW0YAyCJzgkmYPAwwkj+WU8aFQxWRXbjkj25xKcFwjXgpJw3FoEjVOJYviGwRazErECIMqfeu6gNyma2zcjkT7IKToSdmdifmJDHjvojhbXmHeMdvWmYKY+ZEMS77jUfRawCTB9kzM1RJg1GQ2tPKOyC3IXIrBriIcxoqwXxHIUWHk0CJ3Cl3Ju7NNk/uc59zeGgjWZyIXYMsGDayBWCzwawDZMVX3d1E8nTZTUBfbmKad2ZOMjPpixln2G5kAtWOTKs7OxoPG1qrR2gnw4a2ODvpchAV2Da3asmoc9s+Y9WmYtS5b1dY9Yr4lK+TrYJ1LzGMIm+puLeZcAdDWvD3JFZyeB2/ZS3UcnhTM5XvzeJFY5TeMsaU46lwPf6zIyLjS5Qg/cAKWE5wSJ5d5LOrdfz5huImJ1UNKO7KGpTeOC1T0hPrBVTVkEoAZ0nTtyD21n5MNgMfsfhj3Ke8JcQPPGPruS6u6vQh2flu3MUzLTUawhtY49hR+6/GGmdOuf+CW0yCa6wvVCDO+GOxz/VvjwV3BOMyutlgJMObrfKuWr5phppa/iiuG/ljlrjMH+uYXy0PvfEM2LTL/mjObm2QSVX2bPAoFQiI59NIuvOPOCD1XbuoLqcgj/SOuViyptXTz6VbXl3op0TrYjGbAaCVgKQ1oPFTqeZNNHixriy7t4HX/t+s2J7WtOKbjHS6teuN5jWfcC4jC6PFuY19nnG7LcIvXpoMcRdJjJeK1xm9ed39iO0cN2Zv3MzOj0OfebsEFKdsTtmTQEueJHrcULG1ZgW/Bx1iaw4bW9AntpcuYz+OX59fpth1/drSrRt6eylCnNPduankpr/3Imqs6a71pHrgdTOW6ub3rXlSB4eRfWJbHEsdzcZla9h2cBrZq277xHaqwbbhRoRRsRExZ+XiLYZBbkc0OF1rcHhqqIcvQDOrmrSkBKDrZSlzUQD9OkoAVUp4kDSQ3uxDa+DkhnHbm1Tn3+5rywuA7tWEGyng8a6Ai8eDLvcEQPV4cLUG5gPXQDZxaEEDLc5lWTL/NUN6Kpj/JgQ8/wM=</diagram></mxfile>"><defs/><g><path d="M 165 53 L 115 83" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 165 53 L 215 83" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><ellipse cx="165" cy="28" rx="25" ry="25" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><ellipse cx="65" cy="198" rx="25" ry="25" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><path d="M 115 133 L 65 173" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 115 133 L 165 173" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><ellipse cx="115" cy="108" rx="25" ry="25" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><ellipse cx="215" cy="108" rx="25" ry="25" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><ellipse cx="165" cy="198" rx="25" ry="25" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><path d="M 225 198 L 200.1 198" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 193.35 198 L 202.35 193.5 L 200.1 198 L 202.35 202.5 Z" fill="#000000" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="all"/><rect x="225" y="183" width="95" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 93px; height: 1px; padding-top: 198px; margin-left: 226px;"><div data-drawio-colors="color: #000000; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><font style="font-size: 25px;">key = a</font></div></div></div></foreignObject><text x="273" y="202" fill="#000000" font-family="Helvetica" font-size="12px" text-anchor="middle">key = a</text></switch></g><rect x="40" y="323" width="120" height="240" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><path d="M 160 458 L 197.06 337.56 Q 200 328 210 328 L 289.9 328" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 296.65 328 L 287.65 332.5 L 289.9 328 L 287.65 323.5 Z" fill="#000000" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="all"/><path d="M 160 458 L 289.9 458" fill="none" stroke="#ff9933" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 296.65 458 L 287.65 462.5 L 289.9 458 L 287.65 453.5 Z" fill="#ff9933" stroke="#ff9933" stroke-width="3" stroke-miterlimit="10" pointer-events="all"/><rect x="40" y="443" width="120" height="30" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><rect x="0" y="443" width="40" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 38px; height: 1px; padding-top: 458px; margin-left: 1px;"><div data-drawio-colors="color: #000000; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 20px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><font style="font-size: 25px;">a</font></div></div></div></foreignObject><text x="20" y="464" fill="#000000" font-family="Helvetica" font-size="20px" text-anchor="middle">a</text></switch></g><path d="M 315 343 L 265 393" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 315 343 L 365 393" fill="none" stroke="#000000" stroke-width="3" stroke-miterlimit="10" pointer-events="stroke"/><ellipse cx="315" cy="328" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><ellipse cx="265" cy="408" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><ellipse cx="365" cy="408" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#000000" stroke-width="3" pointer-events="all"/><path d="M 315 473 L 265 523" fill="none" stroke="#ff9933" stroke-width="4" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 315 473 L 365 523" fill="none" stroke="#ff9933" stroke-width="4" stroke-miterlimit="10" pointer-events="stroke"/><ellipse cx="315" cy="458" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#ff9933" stroke-width="4" pointer-events="all"/><ellipse cx="265" cy="538" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#ff9933" stroke-width="4" pointer-events="all"/><ellipse cx="365" cy="538" rx="14.999999999999998" ry="14.999999999999998" fill="none" stroke="#ff9933" stroke-width="4" pointer-events="all"/><rect x="65" y="293" width="70" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 68px; height: 1px; padding-top: 308px; margin-left: 66px;"><div data-drawio-colors="color: #000000; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 20px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><font style="font-size: 20px;">Context</font></div></div></div></foreignObject><text x="100" y="314" fill="#000000" font-family="Helvetica" font-size="20px" text-anchor="middle">Context</text></switch></g><rect x="40" y="3" width="30" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 18px; margin-left: 41px;"><div data-drawio-colors="color: #000000; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 20px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><span style="font-size: 30px;">A</span></div></div></div></foreignObject><text x="55" y="24" fill="#000000" font-family="Helvetica" font-size="20px" text-anchor="middle">A</text></switch></g><rect x="350" y="313" width="30" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 328px; margin-left: 351px;"><div data-drawio-colors="color: #000000; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 20px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><span style="font-size: 30px;">B</span></div></div></div></foreignObject><text x="365" y="334" fill="#000000" font-family="Helvetica" font-size="20px" text-anchor="middle">B</text></switch></g><rect x="350" y="443" width="30" height="30" fill="none" stroke="none" pointer-events="all"/><g transform="translate(-0.5 -0.5)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 458px; margin-left: 351px;"><div data-drawio-colors="color: #FF9933; " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 20px; font-family: Helvetica; color: rgb(255, 153, 51); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;"><span style="font-size: 30px;">C</span></div></div></div></foreignObject><text x="365" y="464" fill="#FF9933" font-family="Helvetica" font-size="20px" text-anchor="middle">C</text></switch></g></g><switch><g requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"/><a transform="translate(0,-5)" xlink:href="https://www.diagrams.net/doc/faq/svg-export-text-problems" target="_blank"><text text-anchor="middle" font-size="10px" x="50%" y="100%">Text is not SVG - cannot display</text></a></switch></svg> \ No newline at end of file
--- a/marp-slide/slide.md Fri May 12 13:50:37 2023 +0900 +++ b/marp-slide/slide.md Fri May 12 16:32:47 2023 +0900 @@ -13,7 +13,7 @@ 琉球大学 理工学研究科 知能情報プログラム 河野研究室 -又吉 雄斗, 佐野 巧曜, 河野 真治 +### 又吉 雄斗, 佐野 巧曜, 河野 真治 --- @@ -38,7 +38,7 @@ ## 信頼性の保証を目的としたOS -3種類のGears OS +### 3種類のGears OS - GearsAgda(Agda) - 形式手法による信頼性の向上 @@ -60,7 +60,7 @@ ## CodeGearとmetaCodeGearの関係 -ノーマルレベルとメタレベルの存在 +### ノーマルレベルとメタレベルの存在 - CodeGearがDataGearを受け取り，処理後にDataGearを次のCodeGearに渡すという動作をしているように見える - 実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，それらの計算はMetaCodeGearで行われる @@ -102,16 +102,12 @@ ## ディスク上とメモリ上のデータ構造 - ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する -一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． -なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， -B-Treeのようなノードを複数持つことができる構造が効果的だからである． -その点ではRedBlackTreeはB-Treeに劣る． -しかしながら，SSDはランダムアクセスによってデータにアクセスするため， -RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． -よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． +- ブロックアクセス数の観点ではRedBlackTreeはB-Treeに劣る +- しかしながら，SSDはランダムアクセスによってデータにアクセスするため，RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． +- よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． - そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． ---- +<!-- --- ## データのロールバックとバックアップ @@ -134,60 +130,61 @@ まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する． その後，コピーしたものはバックアップないしログとしてディスクに書き込む． そうすることで，データの増加によるリソースの枯渇を防ぎ， -かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． +かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる． --> + +--- + +## トランザクション + +- トランザクションはDBの重要な機能の一つである +- データの競合を防ぎ信頼性を向上させるために，トランザクションの仕組みを考える必要がある +- ファイルシステムは全てRedBlackTreeで実装するため，RedBlackTreeのノードに対するトランザクションを考える +- トランザクションをwriteとreadに分けて考える + +--- + +## トランザクション + +### writeする場合 + +- トランザクションはRedBlackTreeのルートの置き換えと対応する +- writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える +- ルートの置き換えは競合的なので，複数プロセスから同時に書き込みを行っても1つしか成功しない +- 単一のRedBlackTreeに複数の書き込みポイントを作り，並行実行可能にする必要がある --- ## トランザクション -トランザクションはDBの重要な機能の一つである． -データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう -トランザクションの仕組みを考える必要がある． -今回，ファイルシステムは全てRedBlackTreeで実装するため， -RedBlackTreeのノードに対するトランザクションを考える． - -トランザクションをwriteとreadに分けて考える． -writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する． -writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える． -そのため，書き込みの並列度はルートの数と一致する． -しかしながら，ルートの置き換えは競合的なので， -複数プロセスから同時に書き込みを行っても1つしか成功しない． -よって，単一のRedBlackTreeに複数の書き込みポイントを作り， -並行実行可能にする必要がある． - -% TODO: writeトランザクションの図を入れたい +### 複数の書き込みポイント -RedBlackTreeに複数の書き込みポイントを作るために， -キーごとのルートを作成する． -ノードはそれぞれがキーとRedBlackTreeを持つ状態になる． -writeする際は，そのキーのルートを置き換える． -それによって，RedBlackTreeは複数の書き込みポイントを持つことができ， -writeを並行実行することが可能となる． +- RedBlackTreeに複数の書き込みポイントを作るために，キーごとのルートを作成する +- ノードはそれぞれがキーとRedBlackTreeを持つ状態になる +- writeする際は，そのキーのルートを置き換える -図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す． -Aの木はファイルシステム全体を表すRedBlackTreeである． -ノードNのデータに対して書き込みすることを考えると， -キーがaであるBの木のルートからロックしCの木を作成して， -Bの木からCの木のルートに入れ替えることで書き込みを行う． -この書き込みを行っている際， -Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる． - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=80mm]{figs/transaction.drawio.pdf} - \end{center} - \caption{トランザクショナルなwrite操作} - \label{fig:Transaction} -\end{figure} - -% TODO: read時常に最新の情報が取れないことを説明する図を入れたい - -readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である． -しかし，常に最新の情報を読み込めるとは限らない． -最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる． --- +## トランザクション + +- Aの木はファイルシステム全体を表すRedBlackTreeである +- ノードNのデータに対して書き込みすることを考える +- キーがaであるBの木のルートからロックしCの木を作成して，Bの木からCの木のルートに入れ替えることで書き込みを行う + + + +--- + +## トランザクション + +### readする場合 + +- readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である +- しかし，常に最新の情報を読み込めるとは限らない +- 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる + +<!-- --- + ## ファイルシステムにおけるスキーマ 従来のRDBのようなスキーマが存在すると， @@ -216,7 +213,7 @@ そのことから，GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる． なお，今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す． DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている． -よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． +よって，KernelのContext上にキーを用いたDataGearの参照を書き込む． --> ---