ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

Database Concurrency Control Papadimitriou 読書会 第7回 議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読書会 第7回 - connpass の議論メモです。
※第6回は休講でした。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

2.4 VIEW SERIALIZABILITY

Definition 2.3: Suppose that a transaction A has k read steps, r1, r2, ... , rk. The view of A in a schedule s under interpretation I and initial state X is the k-tuple (r1s(I,X), ... , rks(I,X)) of the values of the variables read by the read steps of A in s. Two schedules s and s' are called view equivalent if
(a) They are final-state equivalent, and
(b) Under any interpretation and initial state, the views of each transaction in both schedules are the same.

(b) は両方のスケジュールの全てのトランザクションでviewが一致していること、としている。

一見すると (b) だけでも view equivalent が成り立ちそうだ。ここであえて (a) を含めているのは final-state equivalent の定義 (Definition 2.1) が含まれていることを言いたいのではないか。

from D(s) we construct the directed graph D1(s) by deleting all nodes of D(s) from which no step of A can be reached.
(中略)
Theorem 2.1: Two schedules s and s' are final-state equivalent if and only if they involve the same transactions, and D1(s) = D1(s').
(中略)
Theorem 2.2: Two schedules s and s' are view equivalent if and only if they involve the same set of transactions and D(s) = D(s').

Theorem 2.1, Theorem 2.2 はほぼ同じ形となっており、D1 と D の違いがある。

Definition 2.5 の "programs with loops, after these loops have been "unwound""とはループ展開(ループ展開 - Wikipedia)を行ってループをなくすということ。

Figure 2.3. A Free Schema のパスの例として以下が挙げられている。
1. R(x)W(y)W(z)
2. R(x)W(y)R(z)W(x)
これ以外にも以下のパスが存在しうる。
3. R(x)W(y)R(z)W(z)

namely that no read step is preceded by a read or write step on the same entity, and likewise no write step is preceded by a write step on the same entity.

これは以前に出てきたトランザクションの定義に沿っている。


[memo]
P6 に該当すると思われる定義の記載があります。

It is quite natural - and, it turns out, simplifying - to make the following assumptions about the structure of the transactions.
(a) In a transaction, an entity is read at most once, and is written at most once.
(b) In a transaction, no entity is read after it is written.



Definition 2.6: Let A be a transaction. A full interpretation I of A consists of
(a) A free schema SA such that A is a path in SA;
(b) For each entity x ∈ E, a domain Dx;
(c) For each write step W(x) appearing in SA, we have in I a function f : ΠiDyi → Dx, where the yi's are the entities read by the read steps preceding W(x) in SA; and
(d) For each predicate P of SA, I contains a subset p of ΠiDyi, where the yi are the entities in the read steps preceding P in SA (this subset contains the combinations of values that make P true).

(c) で write はその前に read した結果で決まるとしている。
(d) で P はそこまでに read した結果で決まるとしている。

We say that s is legal for I and X if for each transaction A of s and each predicate P in SA the following holds: Transaction A corresponds to a path of SA which, for each predicate P of SA, takes the left branch at P if (v1s(I,X), ... , vks(I,X)) ∈ p, and the right branch otherwise, where the vi's are the read steps which precede P in A, and p is the interpretation of P.

スケジュールが "legal" であるとは、そこまでに read した結果に応じて P が正しく動いたということ。つまり、スケジューラに P に反するようなステップが来たときは legal ではない。

トランザクション毎に Free Schema がある。そして、与えられた view によって P が決まる。Free Schema 通りに動くならスケジュールは legal だ。

関連記事

The Theory of Database Concurrency Control - nikezono
中園さんの読書メモ。

papa本第7回メモ - 誰にも見えないブログ
@yuyabu2 さんの読書会ノート。

Database Concurrency Control Papadimitriou 読書会 第5回 議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読書会 第5回 - connpass の議論メモです。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

今回、エルブラン・セマンティクスで検証を行っています。エルブラン・セマンティクスの詳細は過去記事を参照ください。
エルブラン・セマンティクス(Herbrand Semantics)理解メモ - ぱと隊長日誌

2.3 THE CRITIQUE OF FINAL-STATE SERIALIZABILITY

Using Semantics

Final-State serializability is certainly "syntactic," in that it ignores the semantics of the transactions and the integrity constraints of the database.

final-state serializability (FSR) は意味論の観点では考えていないということ。

Commutativity

可換性のこと。


[memo]
交換法則 - Wikipedia

write steps がインクリメント(例:f(x) = x + 1)するだけとする。
A1 : R(x)W(x)
A2 : R(x)W(x)

この時、A1A2 も A2A1 も全体としては結果に変わりがない。だが、この2つのスケジュールは final-state equivalent とは言えない。


[memo]
ここではスケジュールが final-state serializability かではなく、2つのスケジュールが final-state equivalent であるかを確認していることに注意が必要です。

◆ A1A2 ⇒ R1(x)W1(x)R2(x)W2(x)
H(R1(x)) = f0x()
H(W1(x)) = f1x(f0x())
H(R2(x)) = f1x(f0x())
H(W2(x)) = f2x(f1x(f0x()))
----------
H(x) = f2x(f1x(f0x()))

◆ A2A1 ⇒ R2(x)W2(x)R1(x)W1(x)
H(R2(x)) = f0x()
H(W2(x)) = f2x(f0x())
H(R1(x)) = f2x(f0x())
H(W1(x)) = f1x(f2x(f0x()))
----------
H(x) = f1x(f2x(f0x()))

それぞれの H(x) が異なることから final-state equivalent でないとわかります。



Copiers

"f(...,x,...) = x" は恒等写像を意味している。


[memo]
恒等写像 - Wikipedia

恒等写像を考慮すれば、もっと緩い FSR が定義できるかもしれない。


[memo]
この節で例示されているスケジュールをエルブラン・セマンティクスから検証します。

◆ オリジナルのスケジュール
R1(x)R3(x)W3(y)W2(x)R4(y)W4(x)R5(x)W5(z)W1(z)
H(R1(x)) = f0x()
H(R3(x)) = f0x()
H(W3(y)) = f3y(f0x())
H(W2(x)) = f2x()
H(R4(y)) = f3y(f0x())
H(W4(x)) = f4x(f3y(f0x()))
H(R5(x)) = f4x(f3y(f0x()))
H(W5(z)) = f5z(f4x(f3y(f0x())))
H(W1(z)) = f1z(f0x())
----------
H(x) = f4x(f3y(f0x()))
H(y) = f3y(f0x())
H(z) = f1z(f0x())

◆ A5A1A3A2A4 のスケジュール
R5(x)W5(z)R1(x)W1(z)R3(x)W3(y)W2(x)R4(y)W4(x)
H(R5(x)) = f0x()
H(W5(z)) = f5z(f0x())
H(R1(x)) = f0x()
H(W1(z)) = f1z(f0x())
H(R3(x)) = f0x()
H(W3(y)) = f3y(f0x())
H(W2(x)) = f2x()
H(R4(y)) = f3y(f0x())
H(W4(x)) = f4x(f3y(f0x()))
----------
H(x) = f4x(f3y(f0x()))
H(y) = f3y(f0x())
H(z) = f1z(f0x())

この2つのスケジュールで H(x), H(y), H(z) は一致しており、オリジナルのスケジュールが FSR にみえます。ですが、papa本ではオリジナルのスケジュールが FSR ではないとしています。

この疑問を解くヒントになりそうな資料がありました。

Copiers. Suppose we know that t3 and t4 simply copy their arguments via r(X)w(Y) and r(Y)w(X). Then, r1(X)r3(X)w3(Y)w2(X)r4(Y)w4(X)r5(X)w5(Z)w1(Z) is equivalent to t5t1t3t2t4 although it's not final state serializable. key- r5 read X0.

https://webcourse.cs.technion.ac.il/236510/Spring2018/ho/WCFiles/ch3.pdf

"key- r5 read X0" とあります。確かに2つのスケジュールで H(R5(x)) は異なります。

もし A3, A4 が恒等写像であるとすれば、
H(R5(x)) = f4x(f3y(f0x())) = f0x()
となります。これであれば2つのスケジュールで H(R5(x)) が等しくなります。

ただ、最終状態のエルブラン・セマンティクスでなく、途中のエルブラン・セマンティクスが等しくないことで final-state equivalent でないといえるのかが確信を持てないでいます。

今回の記事では最終状態のエルブラン・セマンティクスが等しければ final-state equivalent であるとしました。Weikum本から定義を引用します。

DEFINITION 3.6 Final State Equivalence
Let s and s' be schedules. s and s' are called final state equivalent, denoted s ≈f s', if op(s) = op(s') and H[s] = H[s'], i.e., s and s' comprise the same set of operations and have the same Herbrand semantics.
Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)



Integrity Constraints

この節は FSR の話と言うよりトランザクション (TX) の正しさとは何か、という話に近いのでは。一方で、全部終わった後に上手く行くなら良い(途中は無視!)ということから考えると FSR にもつながる。

Dead Transactions

TX を勝手に除いてはダメ、としているが、不要な制限ではないか?Integrity Constraints を守っていさえすればよいのでは?
だが、これを許すと初期状態=最終状態、つまり「何もしない(全ての TX を取り除く)」ということを許してしまう。なのでそんなわけはない。


[memo]

Schedule s is not final-state serializable, as it can be easily checked. It is, however, final-state equivalent to the serial schedule consisting of the transaction A2 alone!

これをエルブラン・セマンティクスから検証します。

◆ オリジナルのスケジュール
R1(x)R2(y)W1(y)W2(y)
H(R1(x)) = f0x()
H(R2(y)) = f0y()
H(W1(y)) = f1y(f0x())
H(W2(y)) = f2y(f0y())
----------
H(x) = f0x()
H(y) = f2y(f0y())

◆ A1A2 のスケジュール
R1(x)W1(y)R2(y)W2(y)
H(R1(x)) = f0x()
H(W1(y)) = f1y(f0x())
H(R2(y)) = f1y(f0x())
H(W2(y)) = f2y(f1y(f0x()))
----------
H(x) = f0x()
H(y) = f2y(f1y(f0x()))

◆ A2A1 のスケジュール
R2(y)W2(y)R1(x)W1(y)
H(R2(y)) = f0y()
H(W2(y)) = f2y(f0y())
H(R1(x)) = f0x()
H(W1(y)) = f1y(f0x())
----------
H(x) = f0x()
H(y) = f1y(f0x())

◆ A2 のスケジュール
R2(y)W2(y)
H(R2(y)) = f0y()
H(W2(y)) = f2y(f0y())
----------
H(x) = f0x()
H(y) = f2y(f0y())

「オリジナルのスケジュール」と「A2のスケジュール」で H(x), H(y) が一致することを確認できました。


最後の状態に影響するものを live とする。有向グラフ D(s) で A にリーチしていれば live ということ。

(a) A write step is live in s if either it is the last write step on this entity, or it is the last write step for that entity before a live read step for the entity.
(b) A read step is live in s if there is a subsequent live write step in the same transaction.

read only TX はdead TX と言えるのではないか?R に影響を与えないため。

FSR は途中の観測者を考えない。R つまり最後の観測者だけ考える。Read Only Anomaly も考えなくて良い。

We say a transaction is dead in s if all of its steps are dead in s.

全ての step が dead なら TX も dead だ。
一部の step が dead でも TX まで dead とは言えない。w(x)w(y) で w(x) が R につながり、w(y) が dead となるようなケースが考えられる。


[memo]

Yet s' is final-state serializable, and therefore correct from our point of view, since it is equivalent to the serial schedule A1A3A2

これをエルブラン・セマンティクスから検証します。

◆ オリジナルのスケジュール
R3(z)W3(y)R1(x)R2(y)W1(y)W2(y)
H(R3(z)) = f0z()
H(W3(y)) = f3y(f0z())
H(R1(x)) = f0x()
H(R2(y)) = f3y(f0z())
H(W1(y)) = f1y(f0x())
H(W2(y)) = f2y(f3y(f0z()))
----------
H(x) = f0x()
H(y) = f2y(f3y(f0z()))

◆ A1A3A2 のスケジュール
R1(x)W1(y)R3(z)W3(y)R2(y)W2(y)
H(R1(x)) = f0x()
H(W1(y)) = f1y(f0x())
H(R3(z)) = f0z()
H(W3(y)) = f3y(f0z())
H(R2(y)) = f3y(f0z())
H(W2(y)) = f2y(f3y(f0z()))
----------
H(x) = f0x()
H(y) = f2y(f3y(f0z()))

「オリジナルのスケジュール」と「A1A3A2のスケジュール」で H(x), H(y) が一致することを確認できました。


s' は s に A3 を入れたことで FSR になった。A3 を入れたことで A1 を無効にした。

Strict Serializability

s = R1(x)R2(x)W2(x)R3(y)W3(y)W1(y)
このスケジュール s は s' = A3A1A2 と final-state serializable だ。

s で A2 の終了後に A3 が開始している。一方 s' ではこれが逆順になっている。このような "inversion" が発生しないことを strictly serializable という。これはリカバリのコンテキストで議論されることが多い。

This is not a serious problem. The serial schedule s' should be regarded merely as a proof of the correctness of s, and as a proof it is certainly a valid one.

これはシリアスな問題ではない。シリアライザブルの判定に使っているだけだからだ。

Incorrect Views

以下のスケジュールを考える。
s = R1(x)W1(x)R2(x)R2(y)W2(y)W1(y)

It is final-state serializable, because it is equivalent to A2A1.
(中略)
Now A2 reads x after it is updated, and yet reads an unupdated version of y: It saw an "inconsistent view," in which possibly the integrity constraint is violated.

s は FSR だが VSR ではないということだ。

If however we execute the schedule s from the same state

これは s に従ってプログラムを動かした例。


[memo]
s に従ってプログラムを動かした場合の実行順を示します。

s P1 P2 x y z
0 1 0
R1(x) t1:=x 0 1 0
W1(x) x:=t1+1 1 1 0
R2(x) t1:=x 1 1 0
R2(y) t2:=y 1 1 0
W2(y) if t1 < t2 then z:=1 else y:=t2+1 1 2 0
W1(y) y:=t1+2 1 2 0



デブサミ2019夏「【A-2】今後の生き方についてサラリーマンエンジニアが人生半ばにして考えてみた」聴講メモ

はじめに

Developers Summit 2019 Summer (Developers Summit 2019 Summer)
今後の生き方についてサラリーマンエンジニアが人生半ばにして考えてみた
スピーカー:上野 淳 [ディライトワークス]
の聴講メモです。

メモは口頭説明を中心にまとめています。資料を併せてご参照ください。

Twitterのつぶやきがtogetterでまとめられています。併せてご参照ください。
デブサミ2019夏【A-2】今後の生き方についてサラリーマンエンジニアが人生半ばにして考えてみた #devsumiA #devsumi - Togetter

【参考】としている個所は私が挿入しています(補足や参考資料など)。登壇者の講演内容ではありませんので、その旨ご了承ください。

聴講メモ

環境に流されるエンジニアになってはならない。
ただし、本講演は転職のすすめではない。

会場で参加者アンケート。
新卒からずっと同じ会社なのは6割程度。
ゲーム会社所属は5%程度。

デブサミ2019夏の事前アンケートだと参加者の平均年齢は40歳ぐらい。

デブサミ2019夏のサイトトップに『不確実性に向き合えるソフトウェアとエンジニア組織を作っていくための知見が得られる場を目指します。』とある。不確実なことが多いのはゲーム開発でも同様。

組織を作るのはマネジメントの役割だと思われることが多い。だが、我々エンジニアがどう思うかで変わっていくのではないか。

ゲーム端末の高性能化で、今までできなかったことが何でもできてしまう。
エンジニアとしてはやりたいことがやれる反面、やらなければいけないことが増えた。

開発チームの巨大化の実例として、Fate/Grand Order だと開発メンバーが100名を超えている。
スマホでフェイト!|Fate/Grand Order 公式サイト

役割分担の細分化が進んでいる。この流れはデザイナーが先行し、エンジニアもそうなりつつある。グラフィック・ネットワーク・セキュリティ・QA等々。

ノウハウには専門領域がある。共有するのは簡単ではない。
これに対する解決策として、外に転がっているノウハウを拾いに行く。ただググるのではなく、実際に会いに行き、関心を持っている背景も含めて話を聞くと良いのではないか。

昔であればプロジェクトを経験する中でノウハウを覚えた。だが、今は開発期間が長くなり、経験からノウハウを得るための繰り返しがやりにくくなった。
これに対する解決策として、外に転がっている体験談を聞きに行く。ただググるだけでなく、実際に体験した方に自分の疑問をぶつけることがおすすめ。そして、自分の疑問に対する回答をもらう。

ゲームを創るとは面白さを追求すること。理論ではなく試行錯誤が必要になる。この試行錯誤の時間を作るためにゲームエンジンを採用している。

60歳まで働くとして残り13年。マネージャーの引き継ぎに3年かかるとし、開発期間3年とすると、あと3本ほどしかゲームを作れない!

会場の平均年齢からもいえるように、エンジニア35歳限界説は無いと立証できた。だが、このままで60歳までいけるだろうか?(まま60問題)
そこで自分の「やりたいこと」と「やれること」を棚卸ししてみた。

林先生がいっていたように、仕事をするうえでの「やりたいこと」と「やれること」は違う。
やれることを軸に考えることが大切なのでは。


【参考】
林修「大切なのは、やりたいことよりできること」 | 語録.com

変化することはおっくう。でも変わらないことを否定してみる。
このままじゃない60歳を考える。
前提を変えるために環境を変えた。

経験が邪魔をする。
環境が変わったにも関わらず、過去の経験に引きずられてしまうことがある。

不安が邪魔をする。
でも不安で良いのではないか。不安と向き合い、それを解消する姿勢があれば良い。目をそらしてはダメ。不確実な未来に目を向ける。

「覚悟」とは失敗しても自分のせいだと受け入れる覚悟ではないか。

無意識的選択は危険。選択した意識が無いまま時間が過ぎてしまい、気がついたときには取り返しがつかなくなっている。
自分が望んだ環境に自分がいるのか、ということは考えないといけない。

不安でも良い。心理的安全性でいわれるような失敗しても安全な環境があっても、チャレンジしないと何も変わらない。

何事も経験だ。経験は美化されたり環境が変わって通用しないこともある。でも、自分の自信になる面もある。

自分に揺さぶりをかけることで、想定外の結論に達する。これが成長なのではないか。

失敗しても「てへぺろ」ですむさ。

エンジニアは建築家のようなもの。自分で環境を創り、そこに建築物を建てる。
環境もまたエンジニアリングの範疇なのだ。

デブサミ2032夏(注:年にご注意!)では本講演の続きをしたい。今回の講演の参加者には翔泳社から優先パスを発行してもらうので、そこで成果をぜひ伝えたい。
※もちろんこれはジョークです。