Yabu.log

ITなどの雑記

NP問題における決定問題とはなにか

アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というものの解説をします。学習には以下の本を使っています。

組合せ最適化 第2版 (理論とアルゴリズム)

組合せ最適化 第2版 (理論とアルゴリズム)

まずは決定問題が扱う「言語」という概念から説明します。

言語

計算量理論は大部分が決定問題に基づいている。実際、任意の言語L⊆{0,1}*は、決定問題,すなわち,与えられた0-1文字列がLに属するか(どうかを)決定する問題,と解釈できるからである。(p419)

言語とあるが、これは一般的な自然言語でもプログラミング言語の意味でもない。何らかのデータを符号化したものと考えられる。言語{0,1}*は何らかの011001011...と続く01の羅列、即ちバイナリであることを前提としている。 決定問題は上記の文通り、あるバイナリが言語Lに属するかどうかを決定する問題のこと。

決定問題の定義

決定問題(decision problem)は多項式時間で決定できる言語Xとその部分集合Y⊆Xの対P=(X,Y)として定義される。

注意)このP=(X,Y)のPは複雑性クラスのP,NPのPではありません。本中では斜体にして区別している。

ここで{0,1}* ⊇ X ⊇ Yという言語間の包含関係が成り立つ集合X,Yを定義。なお任意のバイナリが{0,1}* ⊇ Xであるかはどうかは多項式時間で決定できる必要がある*1。この事を組合せ最適化の本ではハミルトン閉路問題を例に説明している

全ての2新文字列がハミルトン閉路問題のインスタンスというわけではなく、無効グラフを表すものだけがそのインスタンスである。本書で扱うほとんどの興味深い決定問題において、インスタンスは0-1文字列集合の真部分集合である。任意の文字列が正しいインスタンスであるかどうかを多項式時間で決定できることが必要である。(p420)

インスタンス

言語Xの任意の元をインスタンスと呼ぶ。

Xの要素をPのインスタンスという

インスタンスは以下の2つのものに分類できる

Yの要素がyes-インスタンス

X/Yの要素がNo-インスタンス(p420)

補足:X/Yは集合XからYを引いた差集合のこと。

決定問題(X,Y)に対するアルゴリズム

x∈Yならばf(x)=1, x∈ X/Y ならばf(x)=0となる関数f:X→{0,1}を計算する(p420)

Xの任意の元がYに属しているかを判定するアルゴリズムのこと。

を変えてして問題の任意のインスタンスを判定できる必要がある。

証明検証アルゴリズム

P=(X,Y)に対してP'=(X',Y')という多項式時間で処理できる決定問題(証明検証アルゴリズム)を定義する。X'とY'は以下のように示される

X':={x#c: x∈X, c∈{0,1}[p(size(x))]}

Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}

シンボル#,文字列cをこの順に連結した文字列を表す。(p421)

[p(size(x))]というシンタックスはxのサイズにしたがって多項式サイズで増えるという意味。[value]は床関数のシンタックスです

ja.wikipedia.org

決定アルゴリズムに対して、証明検証アルゴリズムは扱える問題のインスタンスはyes-インスタンスの処理のみで十分でありNo-インスタンスの検証を要求されないが、処理速度は多項式時間を要求される。決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。

決定問題P=(X,Y)とPの証明検証問題P'=(X',Y')には以下の関係がある

  • X'は言語Xのインスタンスに何らかの文字列#cを追加したものを元にする集合
  • XとX'は濃度は一致するが、集合間には特に部分集合であるとかそういう関係はない。(YとY'間も同様)
  • Xの任意の元はX'の部分文字列になっている。x'=x + "#c" ただし(x'∈X,x∈X)
  • 証明検証アルゴリズムでxが、連結されている#cによってYに属しているかどうかを判定する。
  • cは証明(certificate)と呼ばれる

y#c∈Y'となるような文字列cは、(cによってy∈Yであることが証明されるので)yに対する証明(certificate)とも呼ばれる

  • 証明検証アルゴリズムではX'がY'に含まれるかを計算する。この時の計算量が多項式時間で表せるものがクラスNPに属する(詳細は別エントリで)

決定問題まとめ

で、上記適当に箇条書きにしたものを整理すると、以下のことがわかる。

  • 問題、とは日曜に使う数学の問題という意味ではなく、バイナリの集合と部分集合のペア(P=(X,Y))が定義できれば問題となる
  • 部分集合のペアと言語の閉包関係は以下のようになる。{0,1}* ⊇ X ⊇ Y
  • 決定問題では任意のバイナリが問題のインスタンスであるかは多項式時間で決定できる必要がある。
  • 言語Xとその部分集合Yを定義する。アルゴリズム(関数)を使ってXの元がYに属するかの判定を{1,0}への写像で表現する。
  • 言語の包含関係{0,1}* ⊇ X ⊇ Yで後半のX ⊇ Yの決定に必要な計算量でP,NPの分類を行う。

続く。

*1:なぜ多項式時間で決定できる必要があるのかは自分が当たった本には書かれていおらず、私自身も理解できていないのでもし知っていれば教えてください

別パーティションのWindowsで使ってぃるディスクをubuntuにmount

ubuntuwindowsパーティションを分けたディスクで運用しているのでその知見でも書きたいと思います。

ubuntuからwindows側のパーティションにあるファイルを見たい場合はdiskをマウントして閲覧することができます。

f:id:yuyubu:20190614150234p:plain
windowsubuntuが乘っているnvme

windowsが完全に終了していないからマウント出来ない?というエラーが出ましたが、これでとりあえず閲覧(read-only)できるようになりました。

まずはマウントポイントを作ります。

$ sudo mkdir /media/winf

mountコマンドでマウントします。

$ sudo mount -t ntfs-3g /dev/nvme0n1p4 /media/winf

以下の警告が出ました。

Windows is hibernated, refused to mount.
Falling back to read-only mount because the NTFS partition is in an
unsafe state. Please resume and shutdown Windows fully (no hibernation
or fast restarting.)

f:id:yuyubu:20190614151333p:plain
エクスプローラで認識できるようになった

参考

dacelo.space

本記事方法でマントした情報はrebootすると消えますので、半永久的にOSに認識させたい場合は以下の記事を参照して/etc/fstabを編集してください。

pocke.hatenablog.com

CMU 15-445/645 (FALL 2018)Database Systems - 01 Relational Data Modelノート

TLの詳しい方が勧めていたのでちょっと見てみました。

15445.courses.cs.cmu.edu

スケジュールを見るとかなり本格的でLogging,Concurrency Control,MVCC,はたまた分散OLTP/OLAPと続き、Course informationの所に

The course is appropriate for students with strong systems programming skills.

とあるのでついていけるか不明だが、とりあえず取り組んでみようと思います。 最終的には制作課題?的な感じでC++11でstrage managerを作るらしい。

  • 動機
    • ちょっとだけ入門したC++を活かす機会
    • 英語のリスニングの良い機会
    • DBの基礎力向上
      • CC本読書会がなくなった事による穴埋め

Concurrency Control and Recovery in Database Systems

Concurrency Control and Recovery in Database Systems

  • papa本はDBの基礎というには特殊な知識に偏りすぎている気がする*1

Theory of Database Concurrency Control

Theory of Database Concurrency Control

などをモチベーションに、お昼ご飯とか洗い物とか手が塞がってる時など隙間時間にちょくちょく進めてみます。

早速第一回を見た。第一回はRDBMSの歴史、リレーションとは何か、という話とリレーショナル代数の説明で終わった。

relational model

A Relational Model of Data for Large Shared Data Banks

  • tuple

    • 粒度的には行に相当
    • set of attribute
  • relation

    • 粒度的には表に相当(この例えはたまに怒られますが、分かりやすく 例えると。)
    • ただしunordered set
    • 厳密な意味を知りたければcoddの論文を読む必要がある
      • 1個以上のtupeの集合(つまりテーブル)のn項関係関係(つまりjoin)を意図しているように見える。(joinしていないテーブルも含んでいると思われる)

The term relation is used here in its accepted mathematical sense. Given sets S1 , S2, , . . . , Sn, (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S1, its second element from S2 , and so on.(1.3. A RELATIONAL VIEW OF DATA より抜粋)

  • attribute

    • 列に相当するもの
    • 通常atomic/scalarな値をとる
      • json型やArray型の登場により、現代のDBではこの制限はゆるくなりつつある。 
  • この論文はRDBMSの源流を探る意味で読む価値はありそうだが、今回ここは掘り下げない。

リレーショナル代数

Syntax 意味 SQL
σ Select WHERE句
Π Projection SELECT句
Union UNION演算子
Intersection INTERSECTION演算子
- Difference EXCEPTまたはMINUS演算子
× Product CROSS JOIN
Join Natural JOIN(オリジナルはこれらしい)

Select(σ)

  • Relationからtupleを述語を使って選択する。Where句に相当
  • Syntax:σ predicate(R)

Projection(Π )

  • 特定のattributesを使ったrelationを作成する。
  • attributesの順の並び替えも可能
  • 値の操作も可能。(select a-100 from t_table的な)
  • SQLではSelect句に相当。
  • Syntax:ΠA1,A2,…,An(R)

Union(∪)

  • binary operator.(2つのテーブルをinputにとる演算子)
  • どちらかのrelationまたは両方のrelationに出現するentityを表示
  • Syntax:(R ∪ S)

Intersection(∩)

  • binary operator
  • 2つのinputのrelation双方に共通するtupleから成るrelationを生成する
  • Syntax:(R ∩ S)

Difference(-)

  • binary operator
  • 最初のinputのrelationに存在し、かつ2つめのinputに存在しないtupleから成るrelationを作成する
  • Syntax:(R - S)

Product(×)

  • 2つのrelationの組み合わせから成るrelationを作成する
  • Syntax:(R × S)
  • 一見使えなさそうに見えるが何に役立つだろうか?という設問が投げられた 
    • 全組み合わせを試したいテストの時に役立つだろうという話になった。

Join(⋈)

  • Syntax:(R ⋈ S)
  • 最初にnatural joinを定義したらしい
    • equal join, straight joinという呼び名もある
  • 2つのrelationの1組み以上の共通のattributeで同じ値をもつtupleの組み合わせから成るrelationを作成する
    • 要約すると、同じカラム名の列に関して同じ値を持っているtuple同士を結合させる
    • 授業では以下の例で説明された

R

a_id b_id
a1 101
a2 102
a3 103

S

a_id b_id
a3 103
a4 104
a5 105

(R ⋈ S)

a_id b_id
a3 103
  • intersectionも同じテーブルの例を使っており、結果が全く同じになってしまっていた(授業で使う例としては分かりにくい)
    • 違いは何か?という質問が学生から挙げられた
      • intersectionでは全てのattributeの順、値が一致するtupleのみから成るrelationを作成する
      • natural joinでは共通する名前のattributeが一致すれば良い。

Extra Operator

originalのrelational operatorで表現できなかったものが後年に追加された

  • 対応しているSQLは以下のスライドなどを参考に書き足している。

https://courses.cs.washington.edu/courses/cse444/10sp/lectures/lecture16.pdf

name operator SQL
Rename ρ ASに相当。DDL(ALTER)ではない
Assignment R←S INSERT
Duplicate Elimination δ distinct。UNIONなどにつけるALLではない
Aggregation γ Group by
Sorting τ Order by
Division R÷S 構文としてはない

自分の知っている範囲では関係除算(Division)は構文としてはないのでSQL上で結合とかEXISTSとかを駆使して表現する。

感想

relation

RDBMSの文脈でRelationという言葉がよく出てくるが、正直今日までよく意味がわからなかった。

  • 実装(実際のRDBMSSQL)⇨モデル(relationa model)の順番で勉強しているのがそもそも誤解を招いている原因だと思いますが。
  • テーブルのこと、や結合のこと、写像のことなど、出現する時々に様々なコンテキストを持って出てくるのでますます混乱する。
  • とりあえず今回はCoddのオリジナルの定義に当たれたのと、今回のビデオコースでの文脈である程度意味を絞り込りこむことができた。

  • 関係代数はrelationを操作するためのもの。relationから値を取り出したり、新たにrelationを作るのに使う。

    • この時のrelationという意味に限定して使うのがより厳密。
  • SQLでは<Query Expression>がもっとも近いと思う*2

*1:スケジューラーの本な のでindexなどの話はあまり出てこない

*2:SELECT句の結果、UNION演算子の結果、UNION演算子の引数に取れるもの等

Theory of Database Concurrency Control Papadimitriou 読書会 第2回ノート

人身事故の影響で開始時間が遅れたため、あまり進んでいません(まだ1章を読み切っていない) P8 SchedulesからP12 Proposition 1.1まで読みました。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

connpass.com

Schedules

トランザクション中のdatabase step(read|write)を並び替えたシーケンスのこと。

An interleaved execution of several transactions is termed a schedule.(p8) (略) Formally, a schedule of the transaciotns A1,A2,...,Ak is a sequence of steps in the shuffle A1 * A2 * ... * Ak of the transactions

shuffleされた順列の中にはinterleaveされていないスケジュールも含まれる。特にこれは Serial Schedule と呼ばれる特別なものになる。

A Serial Schedule is a schedule consisting of a succession of transactions, without any interleaving.(p9)

1つのtransactionはcorrectなので、それが直列に並んだSerial Scheduleもcorrectになる。 Serial Scheduleと同じ性質をもつScheduleもまたcorrectになる...という点を次章(2章)で踏み込む。

2章ではSerializabilityをFSR,VSR,CSRの観点から論じる。 必要な道具(エルブランセマンティクス/interpretation)の準備は終わっていると思うので、2章冒頭のFSRが待ち遠しい。

読書会中には

  • transactionはcorrectなのか?
  • transactionがdatabase step以外の(アプリ側から見た)依存関係を持っていた場合は?
  • Nested Transactionはどうなのか?

と言った議論が起こった。この本では

  • transactionはconsistencyの単位とする
  • hidden restrictionがある場合はマージして1つのトランザクションにする

と言った前提をTransactionの節で引いているので、私個人はシンプルに文面を信じて読み進めています。

interpretationの拡張

p6で定義したinterpretationの定義を拡大して一般的にトランザクション界隈でエルブランセマンティクスと同等のものにまで広げている。*1

※interpretation(エルブランセマンティクス)はFSRを定義する際に重要になってくるので、 本書やWeikum本、kumagiさんのAdvent Calendarなどと比較しつつ単独で記事を書こうと思っています。 今回はざっくりした内容にしておきます。

  • あるentity Xに対するreadはXに直前にwriteで書き込んだ値になる。
    • ただしreadの前にwrite stepがない場合は初期値を読む
  • あるentity Xに対するwriteはそれまでにreadした値を引数にとる関数(ドメインの値に写像)の結果を書き込む

という風な規則を付け加えることでscheduleとinterpretationで計算処理を初期状態と関数の組み合わせで表現することができる。

Schedulers

スケジューラーはDB内で同時実行制御の責務を持つ。

The scheduler is the part of the database system which is responsible for concurrency control.

  • 入力:ユーザーが実行したdatabase stepのstream
  • 出力:適当な順に並び替えたstream

streamは厳密な(一般的な)定義がないという議論になった。本書ではarriving requestsなどと書かれている点から、 non deterministicでアプリサイドから次々と到着してくるdatabase stepのrequestの流れ程度の理解で問題ないと思う。

  • streamは毎度コンテキストに合った定義を用意する必要がある。
  • micro batchの塊はstreamではない
  • 最初から最後まで切れないものがstream(windowが作れない)
    • 例:映像
  • データ工学では最初にあるのがデータではなくクエリ、というのがstreamという定義がある
  • ストリームとデータのJoinができるシステムの例:PSoup

Sirish Chandrasekaran, Michael J. Franklin: PSoup: a system for streaming queries over streaming data. VLDB J. 12(2): 140-156 (2003)

スケジューラーは一貫性の保護と高い並列性の実現を目標に設計される。

The goal of the scheduler is to safeguard the consistency of the database by outputting only correct schedules.(p9)

The goal of the scheduler is to preserve consistency while maintaining a high level of parallelism or performance.(p10)

スケジューラーの優劣がわかる指標のようなものをChapter5で定義している。 現在のデータベースのベンチ周りではこの指標の定式化ができていないので、 deterministic*2という前提を引いているため、ワークロードが変わると優劣が大きく変わったりするらしい。

余談ですが、Calvinというシリアル実行していると解釈もあるシステムもある。

abstractとconclusionsしか読めてないが、

  • 分散ストレージでpaxos-baseのconsistencyを持つ
  • トランザクションをサポート
  • TPCCの結果が結構良い

というものらしい。

Calvin: Fast Distributed Transactions for Partitioned Database Systems

graph

第一章末にはAppendixとして本書で必要となる数学的な知識、グラフ理論や複雑姓クラスのちょっとしたまとめがある。 今回はグラフ理論を半分くらい読んだ。

  • vertex:グラフの頂点(ノードのこと)
  • edge:2つのvertexから構成される辺のこと

グラフはvertexの集合Vとedgeの集合Eのペア。

A graph is a pair G = (V,E), where V is a finite set of nodes or vertices, and E is a set of subsets of V of cardinality two, (p11)

f:id:yuyubu:20190519010908p:plain:w500
graphの例 p11から抜粋

上記グラフは以下のようになる

G = (V,E)
V = {v1,v2,v3,v4,v5,v6}
E = {[v1,v2],[v1,v4],[v1,v3],[v2,v4],[v3,v4],[v3,v5],[v3,v6],[v4,v6],[v5,v6]}
  • walk

隣接している頂点を繋いだ経路のことをwalkという。本書では私の要約より厳密に定義されている。

A walk in a graph G = (V,E) is a sequence [v1,...,vn] of vertices in V, such that for i = 1,..., n-1,[vi,vi+1]∈E (p11)

  • walkの中でnodeの繰り返しがないものをpathという
  • walkの中で第一nodeと最終nodeが一致しているものをcycleという

A walk in which there is no repetition of nodes is a path; if only the first and last nodes coincide, whe have a cycle.(p11)

  • degree

ノードから何本edgeが生えているかをdegreeという。

directed graph

上記の無向グラフの定義を拡張して有向グラフ(directed graph)を定義する。各要素に以下の変更点が加わる

  • edge → 呼称をarcに変える。矢印の根本をtail,矢印の先をheadと呼ぶ。
  • degree → ノードがarcのtail側、head側それぞれを区別したdegreeを新たに定義する。
    • ノードから生えているtailの数:out-degree
    • ノードに刺さっているheadの数:in-degree

orderdとcycleの関係

本書では以下が同値と見なされている

  • DAGであること
  • グラフの頂点が順序付けが可能であること(can be ordered)
Proposition 1.1: A directed graph is acyclic if and only if its vertices can be ordered so that for all arcs the tail comes before the head.(p12)

対偶として以下が成り立ってしまう点で長い議論が発生した。

  • 順序付け不可能である ↔︎ Cycleが存在する

様々なCycle

f:id:yuyubu:20190519010841p:plain:w300
Cycle?の例

  • Cycleを個別に定義せずに、順序付けできない(トポロジカルソートができない)ことからCycleの定義を導いてしまう書籍、論文だと(2)もCycleと見なしているケースがある
  • (2)のようなグラフは以下の論文に乗っているこのstep graphが該当している(勉強会後に神林さんに聞きました)

Making Snapshot Isolation Serializable

f:id:yuyubu:20190519010412p:plain
Making Snapshot Isolation Serializableのp504から抜粋

okachimachiorz.hatenablog.com

ちなみに以下の本ではCycleは3ノード以上で成り立たないとしているので、(1),(2)双方ともCycleではない。

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

knot

  • Cycleを定義している本は少ない。的な話からknotの話になった。
  • 安易にデッドロックやAnomalyの定義をサイクルに頼るのではなく、検出に必要な性質を整理した上でknotのようなcycleより厳密なグラフ構造を定義している本や論文もある。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

  • RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems

  • あるリソースモデルではWFGに存在するcycleを検査するだけでは不十分なのでより厳密なknotというものの有無を検査する

  • knotはpathのクロス(結び目っぽく見える)とは関係ない
  • knotとCycleは単純に比較できないが、あえて言及するならcycle ⊃ knot
    • kontが存在する場合はknotを構成しているvertexからなるcycleが存在している。
    • cycleがあるからといってknotがあるとは限らない

yuyubu.hatenablog.com

今回はp12のProposition 1.1まで読みました。次回は1.1のProofからです。Complexity(NP,NP complete)の話がが長くなるような予感がしています。

関連:

同回他参加者のブログなどのリンクを貼っておきます

  • ぱと隊長のブログ

taityo-diary.hatenablog.jp

scrapbox.io

*1:ちなみにですが、私の身の回りではinterpretationよりエルブランセマンティクスという名称の方が一般的

*2:database stepが開始時に決まり途中で変化しないというのが現時点の私のdeterministicの理解。分岐処理や対話的な処理をトランザクションで表現できない

Theory of Database Concurrency Control Papadimitriou 読書会 第1回ノート

難しいけどなんとか付いていく感じです

Theory of Database Concurrency Control

Theory of Database Concurrency Control

前提

  • MVCCはPhil BernsteinとPapadimitriouの2者の貢献が大きい。Weikum本のMVCCもこの本の引用が多く含まれる
  • 特にMVCCを理解するにはPapadimitriouの本書を避けて通れない(多分)
  • 今回は本書全体で使う概念の定義などがメイン
  • 最初から~p8のSchedulesの手前まで読みました。
  • 本は価格が高騰していますが、入手できなくても来ると何らかの手当がある!?

用語の定義等

entity

本書ではデータベースが扱うデータの定義をページでもオブジェクトでもなく、entityを採用する。

A database represents a part of the world, and this representation is done in terms of a complex data structure. This data structure cnsists of elementary parts called entities in this book ( any subdivision of the data structure into entities is relevant). (p2 The Problem of Concurrencyより抜粋)

一般的なDB用語でいうところのentityと若干違うので注意。

  • 加算無限な集合
    • ただしある瞬間においては有限の集合になる
  • 不可分かつ重複がない
  • 単一の操作でアクセス(read,write)される
  • entityの更新には副作用がない(更新対象外のentityに影響を与えない)

read

アプリ側の変数にentityの現在の値を割り当てること

assign the currenct value of the entitiy to a program variable.

write

アプリ側で計算した値にentityの値を変えること

change the current value of the entity to a value previously computed by the program.(p5)

transaction

プログラムの実行の結果から作成される一連のreadとwriteのシーケンスのこと。

A transaction is a sequence of database steps resulting from the execution of a program.(p5)

  • transactionは制御構文(if,for)を持たない
  • database step間での計算の整合性なども気にしない。
    • セマンティックスを扱わない。

state

entitiyへの値の割当のこと

A state is an assignment of values to the entities.(p2 The Problem of Concurrency)

integrity constraint

実世界のデータ整合性のこと。 本書では預金額がマイナス以下になったり、飛行機の乗客席以上の予約を受け入れているような状態をDBに保持しないことを例に上げて説明されている。

Not all possible combinations fo value of entities represent a legal state of the world.For example...(略) Such real-world restriction are called the integrity constraints of the database.

consistent

  • データベースのstateは各entityに割当可能な値の集合D(domain)の直積の内どれかにになる。
  • integrity constraint C はドメインの直積の部分集合になる。
  • データベースのstateがC内の要素と一致する時、consistentであるという

interpretation(Herbrand Semantics)

An interpretation of A is a pair I = (D,F)

F= {fa: a is a step of A and ACTION(a) W}

以前に読んだentityのドメインの直積から、write対象のエンティティのドメインへの写像をInterpretationと定義している。

これがWriteのセマンティックスであり、Herbrand Semanticsの厳密な定義であるらしい。

In other words, it fills in the missing semantics of the transaction.(p6)

classicalなconncurrency controlとの違い

classicalなconncurency controlは以下の目標があった

  • リソース利用や並列性を高める
  • p同士の連携(interaction)の調停
  • resouce(printer,memory,processors)にrobustnessがある

databaseのconncurency control(transaction)

  • isolateして動く(interactionはない)
  • robustnessがない。よりdelicateにする必要がある
    • 失敗時は不整合データの伝搬などが起こる可能性がある。

議論

  • DBのほうがOSより難しい的な感じの論調になっている
  • FS(ファイルシステム)はDB寄り
  • FSはメタデータが壊れると致命的
  • 最近のFSはWALなどを持っている

enumerable setとcounterble setの違いは?

<要加筆>

hidden restrictions と Transaction chopping

  • T1とT2に"hidden restrictions"な前後関係があった場合、まとめて一つのトランザクションとしなければならない。

A transaction is a unit of consistency, a grouping together of several database steps, the combined execution of which is known to preserve the integrity constraints. A consequence is that threre can be no "hidden restrictions" on inter-transaction behavior.for example , if correctness requires that steps from "two transactions are executed in some predefined order, then these "two transactions" are in fact a single transaction.

  • 最悪のケースとして1トランザクションになる恐れがあるのではないか?という議論があった。

  • トランザクションはコミットのアボートや単位だが、その粒度が混ざるのはどうなのか?

  • トランザクションになってしまうようなrestrictionがある場合は、1トランザクションにならざるを得ない、と思う。

  • 今回はスケジューラの話が難しくなることを防止するためにこのような定義をしているだけなのではないか。

  • トランザクションを細かくできる話もある。(このとき、hidden restrictionが許されるのかは私にはわからない。)Transaction choppingという

Transaction Chopping Weikum本に書かれているTransaction Chopping

Assume that there are n transaction program that can execute within some give interval, leading to n possibly concurrent transaction executions. if a program can gbe invoked multiple times within the considered interval, we treat it as if there were two differenct programs. we futher assume that each program consists of a straight-line sequence of SQL statements with parameterless where clauses.Decomposing , or Chopping , atransaction programamounts to changing the program as follows:

Definition 8.8 Transaction Chopping

Let ti be a transaction program. A chopping of ti is a decomposition of ti into ordered pieces ti1 ... tik(k >= 1, most often k >=2) such that every database operation invoked by ti is contained in exactly one piece, and the order of operation invocations is preseved.

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

  • (個人的にhidden restrictionの議論はLinearizabilityに近いものを感じた。)

https://scrapbox.io/nikezono/Linearizability

Mono versionから理論を出発させるのではなく、Multiversionから理論を出発させるべき。

Mono Versionの枠組みの拡張としてMultiversionを議論するべきではない、 Multiversionの枠組みで、Mono Versionをその中の一つの特殊系として理論を構築すべき、的な議論があったが、 ここは理解度が低いのでメモ程度にブログに残しておく。

この話はここに限った話ではなく、色んな所で見聞きします。

おそらくMono Versionの枠組みの拡張で何か無理が起こるものだと思うけど、多分もう少し登ると見えてくる光景なのかなと思います。

Interpretationの定義は好評でした

Conflictの判定や依存などの表現にHerbrand Semanticsはよく使われている道具だと思いますが、 本書の定義(Interpretationですが)は概ね好評な感じでした。 ただこの本が書かれた時点ではHerbrand Semanticsという名前は出てきていない。

「ふつうのLinuxプログラミング 第2版」を読んだ

本書はシステムコールとlibcのAPIなどを使ったLinuxで動作するコマンドを作るを通して、 Linuxについて深く知ろうという趣旨の本です。

読んだきっかけ

本書を読んだきっかけは自分のlinux力があまりにも低すぎると感じたため。 具体的に言うと、cmakeに-CMAKE-INSTALL_PREFIXをつけずにビルドして、/usr/localに実行バイナリをおいてしまった。 この件に関して「これじゃぁ他のユーザーに影響でちゃうよ。」と怒られたが、

  • Linuxのフォルダ構成について何も理解していない。
  • -CMAKE-INSTALL_PREFIXをつけるのはかなり基本的なことっぽい。

の2点からググってネット上のコマンドをコピペするしか能のない自分のLinux力を猛省したところ、本書を見つけた。

  • TLの強めのエンジニアがリコメンドしている
  • 最近改版された。
  • 自分が分からなかったフォルダ構成について書かれている
  • 会社に1版に大量の付箋がついているものが存在している(おそらくこれで猛勉強した同僚がいる(いた?))

の4点から、本書を学習してみることにした。

雑感

include<stdio.h>を呪文とすることなく順序立てて初心者にも理解できるように解説している。

  • 1.システムコールやそのAPIのmanコマンド読み方
  • 2.実際にシステムコールなどを使ってみる小さなコードを作る
  • 3.システムコールだけで実現できない動作をバッファなどを実装して自前で作る
  • 4.3で作った相当のものがライブラリとして用意されていることをmanコマンドで説明する

という流れでstdioのprintfの解説を試みている。本や大学の授業などでこの部分の解説を受けたことがなかったので、 ここの流れは見事だなと思った。

manコマンドのセクションについて

manコマンドで実行コマンドまたはライブラリの関数等の使い方を調べることができます。

調べる対象のコマンド名のほかにもセクション番号を引数で渡すことができます。 引数としてなにがあり、どの数字に対応しているかはman manで調べることができます。

$man man
・・・(略)
       1   Executable programs or shell commands
       2   System calls (functions provided by the kernel)
       3   Library calls (functions within program libraries)
       4   Special files (usually found in /dev)
       5   File formats and conventions eg /etc/passwd
       6   Games
       7   Miscellaneous (including macro packages and conventions), e.g. man(7), groff(7)
       8   System administration commands (usually only for root)
       9   Kernel routines [Non standard]
・・・(略)

名前がかぶっているもの、例えばprintfなどはstdioで定義されている関数以外にもユーザーコマンドとして存在しているため、manコマンドで調べると、ライブラリの関数よりも先にユーザーコマンドのセクションがヒットして表示されてしまいます。

$man printf

PRINTF(1)  User Commands  PRINTF(1)

NAME
       printf - format and print data

ライブラリの関数を調べたいときはman 3 prinftと引数にセクション番号を渡すことで表示できます。

$man 3 printf

PRINTF(3)  Linux Programmer's Manual  PRINTF(3)

NAME
       printf, fprintf, dprintf, sprintf, snprintf, vprintf, vfprintf, vdprintf, vsprintf, vsnprintf - formatted output conversion

SYNOPSIS
       #include <stdio.h>

       int printf(const char *format, ...);
・・・(略)

本書ではライブラリ関数やユーザーコマンドを見分けるため、printf(1)やprintf(3)といった書き方に統一しています。 これは分かりやすく、ほかの本でも見かける*1ので、知らない人は覚えておくとよいと思います。

本書を読むまではmanはコマンドの意味を調べるもの、という理解でしたが、実際は更に協力なものでした。 ちょっとTIPS的な要素ですが、man asciiと打つとアスキーコード表が出てきます。

Linux世界を構成する3つの概念とは

Linux世界はこの3つの概念によって成立しています。つまりLinuxプログラミングを理解するためにはこの3つの概念をよく理解しなければならないということです。そしてそれことが本書の目的です。*2

ストリームとは

ファイルディスクリプタで表現され、read()またはwrite()で操作できるもののこと(p82)

  • STDIO,STDOUT
  • ネットワーク
  • ファイル

などを抽象化したインターフェースのことです。

ファイルディスクリプタとは

OSがストリームに対して割り当てる番号(int)のこと。 この割り当てられたファイルディスクリプタに対して、read(2),wreite(2)を使って入出力を制御します。 read(2)やwrite(2)は引数として操作対象としてフアィルディスクリプタを引数に取ります。

       #include <unistd.h>

       ssize_t read(int fd, void *buf, size_t count);
       ssize_t write(int fd, const void *buf, size_t count);

open(2)でストリームを作成し、ディスクリプタを得る。close(2)でストリームを破棄する。

stdioとFILE型

C言語にはファイルディスクリプタをラップし、内部でバッファ管理している標準ライブラリがあります。 それがstdioです。

       #include <stdio.h>

       size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);

       size_t fwrite(const void *ptr, size_t size, size_t nmemb,
                     FILE *stream);

unistd.hのread(2),write(2)等はUNIXシステムコールであり、なるべく移植性が高いstdioの関数を使うように本書に記されています。

read()やwrite()は基本的にはUNIXシステムコールであり、ほかのOSでも存在するとは限りません。しかし、fread()やfwrite()はC言語の標準関数ですから、より多くの環境で使えることが期待できるのです。(p121)

stdioではファイルディスクリプタではなく、それをラップしたFile型を使います。

File型からファイルディスクリプタを得るにはfileno(3)を使います。逆にファイルディスクリプタからFile型を作るにはfdopen型を使います。

以下のプログラムではSTDOUTにはファイルディスクリプタ=1がデフォルトで割り当てられていますが、こちらをラップしたFILE型を作ってfwriteで書き込みを行っています。

#include<stdio.h>
#include<unistd.h>
#include<string.h>

int main(){
                 FILE *stdout_file = fdopen(STDOUT_FILENO,"r+");
                 char *hello = "hello world\n";
                 fwrite(hello,strlen(hello),1,stdout_file);
}

ヘッダファイルは必要になったときに書けば良い。無理して関数とヘッダファイルの対応は覚えなくてOK

大学時代はstdlibはとりあえず書いとけ、みたいな雑な教え方をされた覚えがある。 プログラムを写経して覚えるスタイルだと、そんなかんじで最初に書くことになるのがヘッダファイルのインクルードになるが、 これから各プログラムに何が必要で、それを予め書いておくというプログラミングスタイルに固執する必要はなさそうだと思いました。

manを見れば必要なヘッダファイルはかいてありますから、コードを書いていて新しいAPIが必要になった時点でmanを参照すればいいのです。関数とヘッダファイルの対応をう躍起になって覚える必要はありません。記憶力はもっと有意義なところに使いましょう(p93)

Linuxやlibcに足りないものが沢山見えてくる。

printf()が濫用される理由

これはちょっとした雑学ですが。

printf()はフォーマット付きの出力用のAPIなのですから、 HelloWorldプログラムのようにフォーマット機能が必要ないときに、printf()を使う必然性はないはずです。それでも何かとprintf()が使われています。このようにprintf()が乱用されるのは「標準出力に文字列をそのまま出力するAPIがstdioにないことが原因でしょう。fputs()だと標準入出力を明示的に指定しないといけませんし、puts()だけだと改行が内化されるのが邪魔です。(p118より)

コマンドライン引数のフォーマットに統一性がない。

古いunixのコマンドなどは前述のgetopt(3)を使わずに自前で引数をパースしているものも多いようです。 そのようなツールでは一般的なコマンドライン引数の扱いとは違ったルールで動作している可能性があります。 本書では今linuxツールを作るならgetoptを利用することを推奨しています。

例外処理の仕組み

これは本書に書かれていることではありませんが、自分の感触です。

erronoを使った例外処理なんかはAPI自体がグローバル変数を強要してくる作りになっていて、あまり綺麗なAPIになっていないと思いました。*3

ディレクトリツリーの標準規格FHS(The FilesystemHierarchy Standard)

読む動機となった/usr/localなどのフォルダ役割についてのまとめ。 ディレクトリツリーの標準規格から、主要なディレクトリとその用途。主に9章の内容をまとめたもの

/                   # ルートディレクトリ。bin,etc,dev,proc,sysあたりがまともな動作に必須
├── bin           # ブートするときに必要なコマンド
├── boot          # カーネルのプログラム
├── dev           # デバイスファイル
├── etc           # マシンごとの設定ファイル
├── lib           # ライブラリ置き場(ディストリビューションが管理)
├── proc          # プロセスファイル
├── sbin          # (ブート時も必要となる)管理者用コマンド
├── sys           # デバイスやデバイスドライバの情報 
├── tmp           # 一時ファイルやリカバリファイル
├── usr           # NFSで共有する前提のものを置く。(単ノード利用前提は/var配下に)
│   ├── bin      # コマンド(ディストリビューションが管理)
│   ├── include  # システムのヘッダファイル    
│   ├── local    # ユーザーが管理しても良い。(/usr直下はディストリビューション管理)
│   │   └── bin # コマンド(ユーザーが管理)
│   ├── sbin     # 管理者用コマンド
│   ├── share    # ドキュメント。(manやinfo)
│   │   └── man # manページ。roff形式
│   └── src      # linuxカーネルのソースなどのシステムが使うコード置き場
└── var           # 頻繁に書き換えるファイル・複数マシンで共有しないファイル等
    ├── log       # サーバープロセスのログ
    ├── spool     # メールやプリンタの入力
    └── run       # 起動中のサーバープロセスのPIDファイル
    └── tmp       # 一時ファイルやリカバリファイル

感想

本書はC言語文法の解説などはほとんど書かれておらず、全くの初心者向け、というわけではありませんし、 ライブラリの中の実装などを詳しく説明するなどもないため、上級者向けというわけでもありません。 自分のようにOSやC言語の本を適当に読み漁り、中途半端に知識はついているが基礎が出来ていない人にちょうどいいのかなと思います。 本書は割と細かく丁寧に書かれており、printfに辿り着くまでに100ページ以上あるので、それが我慢できない人にはおすすめしません。

あたりにおすすめです。

というわけで全く新しく知ること、はあまり書かれていませんでしたが、過去の経験の蓄積からなんとなく、そうなんだ、こういうふうになっているんだ、と思い込んでいた事象について、はっきりと仕組みの解説などが書かれていて、いい加減な知識を補強する土台のようなものが出来、安心することができました。個人的にはmanコマンドを引く癖がついたのが一番でかい収穫だと思います。

Linuxのユーザーとしてはまだまだ知識が足りない気がする。LPICの勉強でもすればいいのかな。

次に読む本

シェルスクリプト書けないとやっていけないよ、とのことなので

入門UNIXシェルプログラミング―シェルの基礎から学ぶUNIXの世界

入門UNIXシェルプログラミング―シェルの基礎から学ぶUNIXの世界

*1:紹介システムパフォーマンスとか

*2:p5の1.1本書の概要より引用

*3:この仕組みはマルチスレッド化した際に利用できなくなるケースがあるらしい

time(2)を使って手軽に実行時間、メモリ最大使用量、CPU利用率を知りたい

time(2)コマンドには2種類あります。

  • bash組み込みのtimeコマンド
  • gnuのtime

gnuのtimeコマンドはcpu使用率や平均メモリ利用量、最大メモリ使用量などを計測することができます。 デフォルトの出力フォーマットが見にくいですが、利用者が独自フォーマットを定義して必要な情報のみを選択する事ができます。

FORMATTING THE OUTPUT

% A literal `%'.
C Name and command line arguments of the command being timed.
D Average size of the process's unshared data area, in Kilobytes.
E Elapsed real (wall clock) time used by the process, in [hours:]minutes:seconds.
F Number of major, or I/O-requiring, page faults that occurred while the process was running. These are faults where the page has actually migrated out of primary memory.
I Number of file system inputs by the process.
K Average total (data+stack+text) memory use of the process, in Kilobytes.
M Maximum resident set size of the process during its lifetime, in Kilobytes.
O Number of file system outputs by the process.
P Percentage of the CPU that this job got. This is just user + system times divided by the total running time. It also prints a percentage sign.
R Number of minor, or recoverable, page faults. These are pages that are not valid (so they fault) but which have not yet been claimed by other virtual pages. Thus the data in the page is still valid but the system tables must be updated.
S Total number of CPU-seconds used by the system on behalf of the process (in kernel mode), in seconds.
U Total number of CPU-seconds that the process used directly (in user mode), in seconds.
W Number of times the process was swapped out of main memory.
X Average amount of shared text in the process, in Kilobytes.
Z System's page size, in bytes. This is a per-system constant, but varies between systems.
c Number of times the process was context-switched involuntarily (because the time slice expired).
e Elapsed real (wall clock) time used by the process, in seconds.
k Number of signals delivered to the process.
p Average unshared stack size of the process, in Kilobytes.
r Number of socket messages received by the process.
s Number of socket messages sent by the process.
t Average resident set size of the process, in Kilobytes.
w Number of times that the program was context-switched voluntarily, for instance while waiting for an I/O operation to complete.
x Exit status of the command.

(man 2 timeから抜粋)

環境変数の$TIMEにフォーマットを登録するか-f optionでフォーマットを指定することができます。

export TIME="time result\ncmd:%C\nreal %es\nuser %Us \nsys  %Ss \nmemory:%MKB \ncpu %P"

もしくは

time -f "time result\ncmd:%C\nreal %es\nuser %Us \nsys  %Ss \nmemory:%MKB \ncpu %P" <command>

実行結果(sleep コマンドを実行しています)

$ /usr/bin/time sleep 1
time result
cmd:sleep 1
real 1.00s
user 0.00s 
sys  0.00s 
memory:2128KB 
cpu 0%