Yabu.log

色々勉強するブログです。

Virtual BoxをRetina Displayで動かした時に発生する画面のボヤけの対処

以前retina displayのmacでVirtual Boxを使うとゲスト側OSの画面が滲む、という趣旨のことを書いた

retina displayを使っている限り、1280x800の解像度でボケずに表示することができないらしいので諦めた。 整数倍の解像度を表示するくらい簡単にできそうなもんだが。。。。 ドライバ周りとか色々と大変なのかな。

yuyubu.hatenablog.com

以下の手順で解消することを確認した。

  • 1.Virutual Boxの 設定>ディスプレイ の「スケールしないHiDPI出力を使用」にチェックを入れる
  • 2.ゲスト側のOSの設定でScaleを200%もしくは300%に変更する

f:id:yuyubu:20181210124932p:plain
「スケールしないHiDPIを使用」にチェックを入れる

f:id:yuyubu:20181210125204p:plain
Scaleの200%を選択

もしかしたらGUIディストリビューションによって違いがあるかもしれないが、Ubuntuだとかなり綺麗に表示された。

hatena blogに画像をあげるとドットバイドットにならずボヤけてしまうので、カメラでとった画像でbefore afterを示してみる。

f:id:yuyubu:20181213002545j:plain
before

f:id:yuyubu:20181213002559j:plain
after

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

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

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

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

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)と出てしまいました。

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)

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

感想

参加要件

  • required
    • 本を持ってること(ebookでももちろん可)
    • まじめにMVCCを理解しようという気持ち
  • nice to have
    • Isolationレベルがわかるレベルの知識
    • CSRが中身はともかく「何の略語かわかる」ぐらいの知識 (本来は4章までの中身と言いたいところですが、それはちょっとハードル高そうなので。別にいいです。)

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

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

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

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

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の部分集合?

余談

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

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

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

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

Distributed Computing: Principles, Algorithms, and Systems

*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の順番はもちろん逆でも可能

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

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

Go言語による並行処理

Go言語による並行処理

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

yokohama-go-reading.connpass.com

誤植など

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

github.com

github.com

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

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

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

  • 「驚異的並列」の元の単語(embarrassingly parallel)を書いて欲しい。

    • 対応する原文の単語をよく併記している(by柴田さん)
  • 原著ではソースに行番号が書かれている。

    • p5では3行目、5行目と本文中で参照されているので消すべきではないと思うが...
    var data int
    go func() { // ❶
        data++
    }()
    if data == 0 {
        fmt.Printf("the value is %v.\n", data)
    }

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

  • 組み版が気になる。原著ではソースがまたがっている(p5-6)が、これは無理やり改ページした後にソースを掲載するべき

並列性と並行性

  • Goでは並列処理がかけない。並行処理だけ。並列処理ができる言語はないような気がする。
  • 原著では並行性は Concurrency ,並列性は Parallelism になっているはず

    • 確認したところそのようになってた。
  • アムダールの法則:並列化による性能向上

  • Spigotアルゴリズム:円周率の計算を並列化する方法

  • CPUのクロックは長いこと3,4Ghzで止まっている。2010年頃は10GHzの時代が来る!とか言ってた時代もあった

    • 2000年前後だそうです
  • 競合状態(race condition)

    • 競合状態の検出は困難。
  • 並列性を実現するのはシステムコールでやる。

  • 過去にはシングルコアで動かないプログラムをマルチコアCPUで動かすと、想定していなかった競合に関するバグが発生した。

    • 対策としてCPUのコアをbiosで無効化していた。
      • 無効化するのはもったいので、CPUコアに特定のプロセスを割り当てるシステムコールがOSに導入された

golangデッドロック検出機能

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

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が発生しにくくなる。

  • 複数のロックを取るときは、同じ順番で取ることが重要。

  • Edgar Coffmanのdeadlock検知の論文が挙げられている

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

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

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

実行環境

jshell

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

go

$ 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

分散処理本第40回に参加

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

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

「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回連続で並べています)

f:id:yuyubu:20181108064616j:plain
同じ擬似コードを2連続で表示。しかも文章と意味があっていないので大混乱

f:id:yuyubu:20181108064650p:plain
10.4の画像の欄に表示されている意味不明な画像は10.3のものを謝って2回表示していたようだ

この落丁はKindle本だけであり、紙の本では10.4の擬似コードで適切なアルゴリズムが紹介されていました。

読み手の@okachimachiorz1さんと@Shin1Miyazawaさん以外の3人の参加者はKindleを参照していたので、 読み手の説明しているアルゴリズムと対応しているものが本中になく非常に混乱しました。

ちなみに表示すべき内容は以下の論文から引用されているアルゴリズムの図になります。

f:id:yuyubu:20181108065424p:plain
表示されるべきアルゴリズム

f:id:yuyubu:20181108065442p:plain
表示されるべきアルゴリズム続き

分散システムにおけるデッドロック対処の章を読み終えて

実際の分散システムではデッドロック検知や防止は難しので、タイムアウトでアボートさせる手法が一般的だそうです。 あえて本書に掲載されているような検知、防止を実装するようなシステムは アボートのコストが非常に高く、それを避けたいのでは? という議論になりました。

*1:キリがいいので参加しようと思っている人はチャンスですよ!!!