EFI system partition を拡張する

EFI system partition(ESP) の容量が足りなくて、ファームウェアアップデートが失敗したので拡張した。

今回は、ESP の後ろに別のパーティションが存在し、そのままではパーティションのサイズ変更ができなかった。 そのため、ESP を空き領域に作り直して内容をコピーする作戦を取った。

UEFI は GUID の特定のフラグを持つパーティションを ESP として使うらしい。 ファームウェアがまともなら今回の作戦でもうまく行くはず。 幸いなことに手元の XPS 13 9380 はまともなファームウェアだったらしくうまく行った。

方法としては、linux 上から ESP に保存されているファイルを保存しておく。 次に parted で既存の ESP を削除し、別の場所に esp と boot フラグを立てたパーティションを作る。 あとは、fat32 でフォーマットして保存しておいたファイルを書き戻す。

linux の fstab を書き換えるのを忘れていたので systemd がレスキューモードに落ちたが、 fstab を書き換えて復旧できた。

もとから入っている windows も BitLocker を有効にしていたので若干不安だったが正しくブートした。

CMU 15-445 Two-Phase Locking Concurrency Control

  • dependency graph はスケジュールを与えられたときにserializeかどうかを判定する方法
  • クエリをserializeに実行するにはどうするか?
    • lock を使う
  • 2 Phase Locking
    • grow phaseとshrink phaseがある
    • 前者ではロックを取ること、後者は開放することしかできない
  • 2PL ではコミットあるいはロールバックの前にロックを開放できる
  • Strict 2 PL
  • 2PLはデッドロックを起こす
    • 解決には2種類ある
    • deadlock detection
    • deadlock prevention
  • deadlock detection
    • dependency graphを作成してループがあればアボートさせる
    • バックグラウンドでDGを作れば即応性はなくなるが、計算コストが下げられる
    • これはトレードオフなのでDBMSはチューニングパラメータを持っている
  • deadlock prevention
    • ロックまちが取れないときに、どちらかを殺す
    • DGを作る必要がない
    • 先に開始したほうを高プライオリティにする
    • ロック順序を一方後にするためのプロトコル
    • wait-die
      • 高プライオリティ側はロックを待てる
      • 低プライオリティは死ぬ
    • wound-wait
      • 高プライオリティはロックを持っている方を殺す
      • 低プライオリティはロックを待つ
  • ロック粒度
    • タプルだけでロックを扱うとたくさんのタプルを扱うとたくさんのロックを取らないといけない
    • ロックを階層化して低階層でのロックの数を減らす
    • Intention-Shared(IS), Intention-Exclusive(IX), Shared+Intention-Exclusive(SIX)を導入する
      • ISは下層で読むときに使う
      • IXは下層で書くときに使う
      • SIXは下層で良い書きするときに使う

CMU 15-445 Concurrency Control Theory

  • トランザクションの性質としてACIDがある
  • 一番簡単な方法はシングルスレッドで実行して、データベースファイルをコピーして、書き換えてスワップすること
  • Aを守る方法としては shadow paging と logging がある
  • schedule について
  • serial schedule とはトランザクションを一つずつ実行するスケジュール
  • equivalent schedules とは実行結果が同じになるスケジュール達のこと
  • serializable schedule とは serial schedule と同じ結果になるスケジュールのこと
  • conflict とは R-W, R-W, W-W を起こすようなオペレーションの組
    • これが起こると anomaly が置きてうれしくない
    • R-W だと2回読むと異なるデータが読めちゃう
  • conflict serializable とは conflict の順を保ったまま serial schedule に並び治せるスケジュール
    • dependency graph を作って循環がないかみれば効率的に判定できる
  • view serializable とは conflict serializable に加えて blind write を許すスケジュール
    • dependency graph が循環しても許される場合がある
    • 効率よく判定することができないので使われていないらしい

The Ubiquitous B-Treeを読んだ

B+-Treeのデリート時のロジックがいまいちわからなかったので、B+-Treeに最初にフォーマルに言及したというこの論文を読んだ。 この論文自体はサーベイみたいな感じで、B-Treeのアルゴリズムやそのバリエーションなどを記載している。 複数ユーザーが平行に利用するロッキングについても記述しているがちゃんと読み込めなかった。 この辺は参照している論文をちゃんと読んだほうが良さそう。

もともとB-Treeはファイルシステムの実装のために考案されたらしい。 古い時代の話なので、ディスクのアームがなんちゃらとかシリンダがなんちゃらとか書いてあって面白い。

IBMファイルシステムとしてB-Treeをインデックスとして使うVSAMというのを作ったということが書いてあった。

CMU 15-445 Query Optimization

  • query rewrite
    • rule based optimizer
    • 一般に可能なクエリの書き換えを行う
    • selection は可能な限り先に行うと上で扱うデータ量が減る
  • cost based optimizer
    • 実データをもとにクエリプランを考える
    • データの分布を一様分布として扱うと楽だけど実際はそんなことない
    • 統計情報はヒストグラムを使ったりする
    • この頃のシステムだとサンプリングする
    • 一部のページからサマリーテーブルを作っておいて、コストを見積もる

CMU 15-445 Joins

  • 特にequal joinを扱う
  • N =num of outer table blocks, M = inner
  • nested loop join
    • simple nested loop join
      • outer table のタプルごとにinterのblockを舐める
    • block nested loop join
      • outer tableのblockごとにinterのblockを舐める
      • 仮にouterを保持しておくバッファがあるなら、ioコストはN+Mになる
    • index nested loop join
      • innerがindexを持っているとすると、probeにインデックスが使えるのでioコストが減る
  • sort merge join
    • 2-phaseでやる
    • phase1は2つのテーブルをソートする
    • pahse2で2つのテーブルの突合を行う
    • コストはN+M+sort
  • hash join
    • basic hash join
      • outerのハッシュテーブルを作る
      • コストはN+M
    • grace hash join
      • basicだとouterのハッシュテーブルがメモリに収まらないといけない
      • 東大のgraceというシステムで開発されたやつ
      • outer, innerのハッシュテーブルを作り、それをバケットに分割してディスクに書く
      • コストは3(N+M)

CMU 15-445 Sorting + Aggregationsのメモ

  • データがメモリに収まらない場合を想定する
  • Sorting

    • 結果セットをページ内でソートしてディスクに書く
    • 2つのソート済みページを取り出して比較してページを埋めて、溢れたらディスクに書く
    • 利用するページは入力2つ、出力1つで3ページしか使わない
  • Aggregation

    • ナイーブにやるならsortを使って結果を並び替えて、最後にシーケンシャルスキャンする
    • ソートが重いので、hashテーブルを使ってgroup byするキーごとに結果を作る
    • 結果がメモリに収まらないなら、ハッシュ関数h1を使ってタプルをバケットに分割してディスクに書く
    • 次にバケットごとにハッシュ関数h2を使って結果を作る