2018-11-17

プログラマのためのSQL 読書会(31)に参加

SQL 勉強会

今回は普段の会議室が取れなかったとかで和室でした。

本日の勉強会会場です🍵 pic.twitter.com/H9wKWc3Cor
— yuYabu (@yuyabu2) 2018年11月15日

プログラマのためのSQL 第4版

作者: ジョー・セルコ,Joe Celko,ミック
出版社/メーカー: 翔泳社
発売日: 2013/05/24
メディア: 大型本
この商品を含むブログ (16件) を見る

32. 11 オーバーラップする被覆

期間(開始,終了)を扱うようなテーブルで、被覆していて切れ目のない範囲を抽出したいという趣旨のクエリです。

データ

CREATE TABLE Intervals
(x INTEGER NOT NULL,
 y INTEGER NOT NULL,
     CHECK (x <= y),
     PRIMARY KEY (x, y));

---

INSERT INTO Intervals
VALUES (1, 3),(2, 5),(4, 11),
       (10, 12), (20, 21),
       (120, 130), (120, 128), (120, 122),
       (121, 132), (121, 122), (121, 124), (121, 123),
       (126, 127);

実行結果

min_x	max_y
1	12
20	21
120	132

例のごとく、何パターンも紹介されていますが、そのうち1つにpostgreSQLだけ実行結果が違うものがありました。

--パターン1:ディーター・ネース のウィンドウ 関数を使ったクエリ
SELECT min_x, MAX(y)
  FROM (SELECT x, y,
               MAX(CASE WHEN x <= MAX_Y THEN NULL ELSE x END)
                 OVER (ORDER BY x, y
                       ROWS UNBOUNDED PRECEDING) AS min_x
          FROM (SELECT x, y,
                       MAX(y)
                         OVER(ORDER BY x, y
                              ROWS BETWEEN UNBOUNDED PRECEDING
                                       AND 1 PRECEDING) AS max_y
                  FROM Intervals) AS DT) AS DT
 GROUP BY min_x;

---パターン2:自己 結合と3レベルの相関サブクエリを使うクエリ


SELECT I1.x, MAX(I2.y) AS y
  FROM Intervals AS I1
         INNER JOIN
           Intervals AS I2
    ON I2.y > I1.x
 WHERE NOT EXISTS
         (SELECT *
            FROM Intervals AS I3
           WHERE I1.x - 1 BETWEEN I3.x AND I3.y)
             AND NOT EXISTS
         (SELECT *
            FROM Intervals AS I4
           WHERE I4.y > I1.x
             AND I4.y < I2.y
             AND NOT EXISTS
                  (SELECT *
                     FROM Intervals AS I5
                    WHERE I4.y + 1 BETWEEN I5.x AND I5.y))
 GROUP BY I1.x;


--パターン3:サブクエリ の 代わりに左外部半結合を使ったクエリ
SELECT I1.x, MAX(I2.y) AS y
  FROM Intervals AS I1
         INNER JOIN
           Intervals AS I2
             ON I2.y > I1.x
               LEFT OUTER JOIN
                 Intervals AS I3
                   ON I1.x - 1 BETWEEN I3.x AND I3.y
                     LEFT OUTER JOIN
                       (Intervals AS I4
                          LEFT OUTER JOIN
                            Intervals AS I5
                              ON I4.y + 1 BETWEEN I5.x AND I5.y)
                      ON I4.y > I1.x
                     AND I4.y < I2.y
                     AND I5.x IS NULL
 WHERE I3.x IS NULL
   AND I4.x IS NULL
 GROUP BY I1.x;

---パターン4:トニー・アンドリュースのクエリ

SELECT Starts.x, Ends.y
  FROM (SELECT x, ROW_NUMBER() OVER(ORDER BY x) AS rn
          FROM (SELECT x, y,
                       LAG(y) OVER(ORDER BY x) AS prev_y
                  FROM Intervals) AS Foo
                 WHERE prev_y IS NULL
                    OR prev_y < x) AS Starts,
       (SELECT y, ROW_NUMBER() OVER(ORDER BY y) AS rn
          FROM (SELECT x, y,
                       LEAD(x) OVER(ORDER BY y) AS next_x
                  FROM Intervals) AS Boo
         WHERE next_x IS NULL
           OR y < next_x) AS Ends
 WHERE Starts.rn = Ends.rn;

このパターン4のクエリのみ実行結果が違って出ます。

  x  |  y  
-----+-----
   1 |  12
  20 |  21
 120 | 124

ご覧の通り最後の被覆範囲が(120,132)ではなく(120 ,124)と出てしまいました。

2018-11-15

Transactional Information Systems 5章 MVCC勉強会　第一回に参加

今回読んだ内容としてはMVCCでは

xのWrite時にデータを上書きではなく、新しいバージョンのX2を作る
xのread時にどのバージョンを読むかを決定する、バージョン決定関数h()が存在する

が要点ですが、その定義や文言について議論が長く続きました。

MVCCは理論がついてきていない。実装が先行している。→理論の再構築が必要
MVCCは基本的にwriteロックを取らないが、現行のものでwriteロックを取らないものはない

p.188のExample 5.2の手前まで読みました。

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

作者: Gerhard Weikum,Gottfried Vossen
出版社/メーカー: Morgan Kaufmann
発売日: 2001/05/24
メディア: ハードカバー
クリック: 2回
この商品を含むブログ (2件) を見る

感想

参加要件

required

本を持ってること（ebookでももちろん可）

まじめにMVCCを理解しようという気持ち

nice to have

Isolationレベルがわかるレベルの知識

CSRが中身はともかく「何の略語かわかる」ぐらいの知識（本来は4章までの中身と言いたいところですが、それはちょっとハードル高そうなので。別にいいです。）

と書かれていますが、CSR,FSR,VSRなど各シリアライゼーションの意味を把握した上で、本書の内容も理解できているようなレベルの議論がなされています。また@okachimachiorz1さんがすでに全編音読という偉業を成し遂げられているためか、@okachimachiorz1さんが内容に関して批判点(議論したい点)などをまとめたレジュメを配られた状態で始まりました。

5章までの全内容+勉強会中に読む範囲の予習をした上で自分なりの意見を持つくらいのレベルが要求されていると思いました。

次回までにもうちょっとパワーアップして臨みたいです。

okachimachiorz1さんkumagiさんがネット上に書かれたトランザクション関連の情報を読んで自分なりの理解を持つ。
- ぱとさんのブログに書かれているような感じで読んでいきたいです。 taityo-diary.hatenablog.jp
Tx本2,3章の内容を重点的に読む
トランザクションのアノマリーやisolationに関して自分なりに理解してブログを書く

以下ちょっとした内容のまとめです(まとまってない...)

5.1 Goal and Overview

処理中だけmultiversion。未来永劫マルチバージョンではない。

リカバリも重要。処理中のバッファとリカバリのためのバックアップは別。バージョンという言葉が意味するものを正確に定義する必要がある。

commitの意味が変わってきた

この本:リカバリポイント
最近:リカバリの話ではない。
- oneshot request,group commitは前提になっている。
- "実行順序の制御"に使われている。

We will also look at the storage space needed to hold multiple versions.

ディスクベースで書かれている。インメモリのことも考えないといけない。
- バージョンをストレージに保存する必要があるか
- リカバリできるならいらない。
マルチバージョンの時のバージョン数の問題をどう考えているか?
- マルチバージョンの性能をあげるには、バージョンの数を少なくする必要があるという風潮がある
- 古いものはほとんどいらない
  - いると思う。read-onlyで必要。
  - 複数書くのは賛成だが、沢山書くのは反対。
- LOSTアップデートのアノマリーの定義が必要(曖昧)
  - インクリメンタルな操作を行う2つのスレッドだと、片方でロストアップデートが起こる。
    - それはreadがおかしい
バージョンコントロールデータベース、というものもある。それはMVCCと混同すべきではない

The discussion in this chapter continues to consider unaborted transactions only.

重要なことが最後に書かれている...
- アボートはその種類の考慮が必要
  - システムアボート
  - ユーザーアボート
    - ユーザーアボート不要論
    - 半順序宣言をユーザーが終えた、というのがユーザーコミット?(よくわからない)
感想:アボート、コミット、チェックポイントなどなど、システムとユーザーで意味が大きく違う気がする

5.2 Multiversion Schedules

CSRとは
コンフリクトの定義は?
- writeが入ること?
- この本では交換可能性
  - 順番を変えて意味が変わるならコンフリクト、変わらないならコンフリクトフリー

EXAMPLE 5.1
s = r1(x)w1(x)r2(x)w2(y)r1(y)w1(z)c1c2

バージョンという概念を導入するとExample5.1のhistoryの入れ替えができる。

DEFINITION 5.1

installとは何か?？commitと対になって出てきたが...

過去の論文でread,write,commit,abortの定義を調べたが、writeの明確な定義はない。(古い時代の論文のサーベイ結果)

RWCAは個々のデータベースで定義すべき

DEFINITION 5.1の2の意味がわからない。

history と scheduleの違いとは?p66に乗ってる
- scheduleはhistoryの部分集合？

余談

スヌーピー！その発想はなかったです。これからはスヌーピーということにしていきます！
— ゆううき (@y_uuk1) 2018年11月15日

これからはスヌーピーでいきます
— ゆううき (@y_uuk1) 2018年11月15日

2018-11-12

デッドロック検出におけるknotとcycleの違いについて

deadlock Distributed System

分散処理本読書会で度々話題になっているknotについて簡単にまとめました。

分散処理本でknotの出典としている論文「Some Deadlock Properties of Computer Systems」をknotの説明の箇所より少し後まで読み終えたため、knotについてわかったこと、つまりcycleとの違いやなぜ定義する必要があるのかなどを書きたいと思います。

cycleについて
knotについて
違いは何か
なぜ分けて定義する必要があるのか。
- ケース1.and modelではknotを検出する必要はない。cycleだけで十分
- ケース2.or modelではcycleだけだと不十分でありknotを示す必要がある
参考文献

cycleについて

参考にしている論文の定義を借ります。

定義:サイクルは開始ノードと終了ノードが同じになるようなpathのことです*1

例えば下記の図はc→d→cというcycleが存在しています。これを論文の表記を借りて(c,d,c)と書きます。

f:id:yuyubu:20181112010842p:plain — 図の出典:参考文献2のHOLTの論文

knotについて

定義:knotは集合K内の到達可能なノードの厳密な集合のことです。*2

集合Kがknotである場合、Kの要素は以下の特性を持ちます。

集合内の要素は互いにK内のどの要素にも到達可能である
Kに含まれない要素には到達できない

例えば上記に掲載したHOLT論文のFig3の図で言えばcとdはc,d以外への到達を可能にするエッジを持っていません。こちらも論文の表記を借りて{c,d}と書きます。

違いは何か

knotはノードの集合の定義、cycleはエッジの集合(path)の定義です。

knotを構成しているノードの組み合わせから作成できるcycleのパスが必ずあります。
逆にcycleを構成しているエッジのノードの集合は常にknotになっているわけではありません。

Holtの論文ではcとdはcycleを構成し、かつknotになっています。cycleでありながら、knotでは無い図はHoltの論文には掲載されていません。そのような図は分散処理本こと"Distributed Computing: Principles, Algorithms, and Systems"には掲載されています。

f:id:yuyubu:20181112011538p:plain — 図の出典:参考文献1の分散処理本

こちらの図では(P11,P21,P24,P54,P11)のサイクルが存在していますが、サイクルを構成しているノードの集合{P11,P21,P24,P54}はknotではありません。なぜなら(P11,P32)のエッジが存在しており、ノードP11は集合{P11,P21,P24,P54}以外のノードP32へ到達可能だからです。

定義している集合の要素の種類(ノード/エッジ)が違っていますが、あえていうなら、cycleよりknotの方が厳しい条件を備えているというべきでしょう。(cycleの方がゆるい)

なぜ分けて定義する必要があるのか。

ノード(プロセス)が複数のノードに同時に依存している場合、その依存の種類によってデッドロックの判定方法は変わります。あるケースではcycleを検出するだけではデッドロックの検出条件として不十分だからです。

ケース1.and modelではknotを検出する必要はない。cycleだけで十分

and modelは依存している複数のプロセスを 全て完了する必要がある とするモデル。デッドロック検出を行うにはサイクルを示せば良い。分散処理本figure 10.1の図ではP11→P21→P24→P54→P11のサイクルが存在しているためデッドロックが発生している。

具体的に書くと、P11の要素はP32とP21の要素両方の終了を待つ必要があるが、P21はP11とサイクルを構成しているため、P21とP11は永遠の完了しない、これはデッドロックである。

ケース2.or modelではcycleだけだと不十分でありknotを示す必要がある

or modelは依存している複数のプロセスに対して、 どれか1つだけの完了を必要 とするモデル。デッドロック検出を行うにはcycleだけでは不十分でknotを示す必要がある。例えば分散処理本figure 10.1の図では

P11→P21→P24→P54→P11のサイクルが存在しているが、これはknotではないのでこのWait-for-graphではデッドロックは発生していない。

具体的に書くと、P11の要素はP32とP21の要素どちらかの終了を待つ必要があるが、P21はP11とサイクルを構成しているが、P32が完了するればP21の完了を待つ必要がないため、これはデッドロックではない。

f:id:yuyubu:20181112013934p:plain — 分散処理本のWFGに加筆

分散処理本掲載の図のWFGでは赤矢印で示した順P33→P32→P11→P54→P24→P21→P44で処理を完了させることができる。*3

念の為ですが、knotは必ずcycleを構成するのでknotがあればand modelでもデッドロックが発生している事になる。

参考文献

1:Ajay D. Kshemkalyani and Mukesh Singhal(2011)Distributed Computing: Principles, Algorithms, and Systems
2:RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems

Distributed Computing: Principles, Algorithms, and Systems

作者: Ajay D. Kshemkalyani
出版社/メーカー: Cambridge University Press
発売日: 2011/03/03
メディア: ペーパーバック
この商品を含むブログを見る

*1:原文:A cycle is a path whose first and last nodes are the same.

*2:原文:A knot is a nonempty set K of nodes such that the reachable set of each node in K is exactly set K

*3:P21とP44の順番はもちろん逆でも可能

2018-11-10

第22回横浜Go読書会に参加

golang 勉強会

go言語に関する書籍を読む会です。今回から本が新しくなり『Go言語による並行処理』を読んで行きます。

Go言語による並行処理

作者: Katherine Cox-Buday,山口能迪
出版社/メーカー: オライリージャパン
発売日: 2018/10/26
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

初回なので参加者の方が多かったです(初参加の方も)

yokohama-go-reading.connpass.com

誤植など

epub版固有の誤植というのがいくつか見つかりました。

github.com

ちなみに電子版で呼んでる方はpdfが多い気がしますが、私はepub派です。

組み版や翻訳、原著との差分に関して気になる点

柴田さんをはじめ、複数の方から意見が出ました。

「驚異的並列」の元の単語(embarrassingly parallel)を書いて欲しい。
- 対応する原文の単語をよく併記している(by柴田さん)
原著ではソースに行番号が書かれている。
- p5では3行目、５行目と本文中で参照されているので消すべきではないと思うが...

    var data int
    go func() { // ❶
        data++
    }()
    if data == 0 {
        fmt.Printf("the value is %v.\n", data)
    }

ここで、3 行目と 5 行目ではともに dataという変数にアクセスしようとしています。

組み版が気になる。原著ではソースがまたがっている(p5-6)が、これは無理やり改ページした後にソースを掲載するべき
- Effective Javaとプログラミング言語Goはなるべく跨がないように無理やり改行している部分がある

並列性と並行性

Goでは並列処理がかけない。並行処理だけ。並列処理ができる言語はないような気がする。
原著では並行性は Concurrency ,並列性は Parallelism になっているはず
- 確認したところそのようになってた。
アムダールの法則:並列化による性能向上
Spigotアルゴリズム:円周率の計算を並列化する方法
CPUのクロックは長いこと3,4Ghzで止まっている。~~2010年頃は~~10GHzの時代が来る!とか言ってた時代もあった
- 2000年前後だそうです
競合状態(race condition)
- 競合状態の検出は困難。
並列性を実現するのはシステムコールでやる。
- あるプロセスを特定のCPUに割り当てるシステムコールが存在する。
過去にはシングルコアで動かないプログラムをマルチコアCPUで動かすと、想定していなかった競合に関するバグが発生した。
- 対策としてCPUのコアをbiosで無効化していた。
  - 無効化するのはもったいので、CPUコアに特定のプロセスを割り当てるシステムコールがOSに導入された

golangのデッドロック検出機能

golangでは簡単なデッドロックの検出は最初から入ってる。
- 全てのgo routineが止まった(wait)時はデッドロックの可能性がある
  - プロセスはRunnable, run, waitの状態をとる。
- システムコールを呼んでるgo routineがあればデッドロックとしない(システムコールに時間がかかっているだけの可能性があるため)
  - システムコールを呼んでるものが一個あるだけで、デッドロック検出が動かないというのが不便すぎる。
race conditionの検出機能を言語機能として持っているプログラミング言語はほとんどない。

デッドロック検出のプログラミング言語を動かした例。

type value struct {
  mu    sync.Mutex
  value int
}

var wg sync.WaitGroup
printSum := func(v1, v2 *value) {
  defer wg.Done()
  v1.mu.Lock()         // ❶
  defer v1.mu.Unlock() // ❷

  time.Sleep(2 * time.Second) // ❸
  v2.mu.Lock()
  defer v2.mu.Unlock()

  fmt.Printf("sum=%v\n", v1.value+v2.value)
}

var a, b value
wg.Add(2)
go printSum(&a, &b)
go printSum(&b, &a)
wg.Wait()

$ go run sample.go
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [semacquire]:
sync.runtime_Semacquire(0xc000014054)
        /usr/local/go/src/runtime/sema.go:56 +0x39
sync.(*WaitGroup).Wait(0xc000014054)
        /usr/local/go/src/sync/waitgroup.go:130 +0x64
main.main()
        /Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:34 +0x122

goroutine 5 [semacquire]:
sync.runtime_SemacquireMutex(0xc000014074, 0x0)
        /usr/local/go/src/runtime/sema.go:71 +0x3d
sync.(*Mutex).Lock(0xc000014070)
        /usr/local/go/src/sync/mutex.go:134 +0xff
main.main.func1(0xc000014060, 0xc000014070)
        /Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:24 +0xa1
created by main.main
        /Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:32 +0xea

goroutine 6 [semacquire]:
sync.runtime_SemacquireMutex(0xc000014064, 0x0)
        /usr/local/go/src/runtime/sema.go:71 +0x3d
sync.(*Mutex).Lock(0xc000014060)
        /usr/local/go/src/sync/mutex.go:134 +0xff
main.main.func1(0xc000014070, 0xc000014060)
        /Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:24 +0xa1
created by main.main
        /Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:33 +0x114
exit status 2

上記のプログラムはsleep関数を抜くとdeadlockが発生しにくくなる。
- 簡単なスクリプトでなんども実行したところ?50数回目にデッドロック発生。
複数のロックを取るときは、同じ順番で取ることが重要。
Edgar Coffmanのdeadlock検知の論文が挙げられている
- http://bit.ly/CoffmanDeadlocks

golangで1ミリ秒ごとにxxするという書き方

golangでこの構文は何か？という話題になった。

for range time.Tick(1 * time.Millisecond) {
  cadence.Broadcast()
}

1ミリ秒待ってブロードキャスト、という意味になる。
無限ループの先頭にsleep()関数を使うことでもかけるが、チャネルを使ってこのように書くこともできる
上記ソースのtime.Tickのチャネルは閉じなくていいのか?
- 残るけど、mainが死んだ時に全員死ぬのでOK

condとmutexの違い

condは外部からbroadcast,signalで起こすことができる。
broadcastとsignalの違いは全てのcondを起こせるか、どうかの違いがある。

cadence := sync.NewCond(&sync.Mutex{})
go func() {
  for range time.Tick(1 * time.Millisecond) {
    cadence.Broadcast()
    //broadcastは全てが起きる
    //

  }
}()

takeStep := func() {
  cadence.L.Lock()
  cadence.Wait()
  //waitじにはロックを解除する。、waitを抜けたときはlockを獲得している。
  //ブロードキャスト、もしくはシグナルの受診時にロックを獲得した状態でwait()のいちに戻ってくる
  //なお復帰、ロック再獲得はatomicに実行される
  cadence.L.Unlock()
}

他

Juliaは言語仕様にchanelがあるらしい

次回は2.3「これがどう役に立つのか」（p.29）から

yokohama-go-reading.connpass.com

2018-11-09

go言語で数値-文字変換を行う方法

golang

~~基本的にプログラミングをするときは全部Javaだと思って書いているので、他言語の挙動に困惑することがよくあります。~~ Go言語では文字と数値を+演算子で連結した時に、数値が文字コードとして解釈されているような変換がされたので、数値を文字に変換する方法を調べました。

実行環境

jshell

$ jshell -v
|  JShellへようこそ -- バージョン9.0.1

$ go version
go version go1.11 darwin/amd64

謝った文字列変換

fmt.Println("test" + 65)
//出力結果:testA

この通り65がAに変換されました。

※おそらく内部でstring(65)が実行されているものと思われます

JavaだとStringとint型を+で連結すると文字型に型変換された65が連結に利用されています。

jshell> String a = "test" + 65
a ==> "test65"

strconv.Itoaを使う

fmt.Println("test" + strconv.Itoa(65))
//出力結果:test65

内部ではFormatIntを呼び出しているようです。

// FormatInt returns the string representation of i in the given base,
// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
// for digit values >= 10.
func FormatInt(i int64, base int) string {
    if fastSmalls && 0 <= i && i < nSmalls && base == 10 {
        return small(int(i))
    }
    _, s := formatBits(nil, uint64(i), base, i < 0, false)
    return s
}

// Itoa is shorthand for FormatInt(int64(i), 10).
func Itoa(i int) string {
    return FormatInt(int64(i), 10)
}

FormatIntをそのまま利用しても結果は同じになります。

fmt.Println("test" + strconv.FormatInt(int64(65), 10))
//出力結果:test65

参考

https://stackoverflow.com/questions/10105935/how-to-convert-an-int-value-to-string-in-go

https://golang.org/src/strconv/itoa.go?s=783:806#L14

2018-11-08

分散処理本第40回に参加

恒例のDistributed Computingこと分散処理本を読む会になります。

Distributed Computing: Principles, Algorithms, and Systems

作者: Ajay D. Kshemkalyani,Mukesh Singhal
出版社/メーカー: Cambridge University Press
発売日: 2008/04/17
メディア: Kindle版
この商品を含むブログを見る

「10.9 Kshemkalyani–Singhal algorithm for the P-out-of-Q model」の続き(10.9.2 The algorithm)から、10章の最後までを読みきりました。

次回は「CHAPTER 11 Global predicate detection」からになります。*1

学んだこと

P-out-of-Qリソースモデルにおけるデッドロック検出アルゴリズム""Kshemkalyani–Singhal algorithm”について学びました。こちらは個別の記事でブログを書きたいと思います。

分散処理本のKindle版に見つかった落丁について

「Algorithm 10.4 Deadlock detection algorithm」として挙げられている擬似コードの図が「Algorithm 10.3 Kshemkalyani–Singhal algorithm for the P-out-of-Q model.」の図と全く同じものば謝って掲載されています。(しかも同じ擬似コードを2回連続で並べています)