Papers/2023/matac-sigos: Paper/paper.tex comparison

comparison Paper/paper.tex @ 11:0cf15f862f02

transaction

author	matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date	Sun, 16 Apr 2023 22:01:29 +0900
parents	091510a8cd0a
children	e739be918b0e

comparison

equal deleted inserted replaced

-:091510a8cd0a
+:0cf15f862f02
 その後，コピーしたものはバックアップとしてディスクに書き込む．
 そうすることで，データの増加によるリソースの枯渇を防ぎ，
 かつデータのバックアップを作成することで信頼性の向上が期待できる．
-\section{トランザクション}
+\section{RedBlackTreeのトランザクション}
-ルートノードはデータをリード，ライトする時に増やす．
+トランザクションはDBの重要な機能の一つである．
-それにより，ルートノードは一つのスレッドを表現する．
+データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう
-スレッドがデータのアップデートを行う際は，他のスレッドとの競合を防ぐ必要がある．
+トランザクションの仕組みを考える必要がある．
-スレッドはルートノードからアップデート対象のノードまで辿るようにロックを獲得していく．
+今回，ファイルシステムは全てRedBlackTreeで実装するため，
-その際，子ノードのロックを獲得した後は親ノードのロックを手放して良いことにする．
+RedBlackTreeのノードに対するトランザクションを考える．
-データのアップデートが完了し，ロックを解除後，ルートノードの切り替えを行う．
-このような操作によって，トランザクションを実現する．
+トランザクションをwriteとreadに分けて考える．
-しかし，このままだとアップデートによってデータの一貫性を損なう場合がある．
+writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する．
-常に最新のデータを持ったルートノードを選択する仕組みが必要になる．
+writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える．
+そのため，書き込みの並列度はルートの数と一致する．
-なお，リードする際はその時点で最新のルートノードを元にリード用のルートノードを作成する．
+しかしながら，ルートの置き換えは競合的なので，
-リードは木を変更することがないので，
+複数書き込みを行っても1つしか成功しない．
-作成したリード用ルートノードの数だけ同時にリード可能となる．
+よって，単一のRedBlackTreeに複数の書き込みポイントを作り，
+並行実行可能にする必要がある．
+RedBlackTreeに複数の書き込みポイントを作るために，
+キーごとのルートを作成する．
+ノードはそれぞれがキーとRedBlackTreeを持つ状態になる．
+writeする際は，そのキーのルートを置き換える．
+それによって，RedBlackTreeは複数の書き込みポイントを持つことができ，
+writeを並行実行することが可能となる．
+readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である．
+しかし，常に最新の情報を読み込めるとは限らない．
+最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる．
 \section{スキーマレスな実装}
 従来のSQLのようなスキーマの定義が存在すると，
 個別にバックアップなどを取らない限り

Mercurial > hg > Papers > 2023 > matac-sigos

comparison Paper/paper.tex @ 11:0cf15f862f02