Yabu.log

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

ネットワークの物理層に関する5つの興味深いエピソード

コンピュータネットワークの第2章は物理層についての章でした。読み終えたので感想でも書こうと思います。 この章は難解なので自分が楽しめたのは精々物理層に纏わる様々な歴史上のエピソードのみでした。いくつか紹介してみようと思います。

コンピュータネットワーク 第5版

コンピュータネットワーク 第5版

  • 作者: アンドリュー・S・タネンバウム,デイビッド・J・ウエザロール,水野忠則,相田仁,東野輝夫,太田賢,西垣正勝,渡辺尚
  • 出版社/メーカー: 日経BP
  • 発売日: 2013/09/12
  • メディア: 単行本
  • この商品を含むブログ (4件) を見る

エピソード1:警察無線がキャデラックのABSの誤動作の原因になった

1970年代にGeneralMotorsはすべての新しいキャデラックにコンピュータ制御のアンチロック・ブレーキを装備することにした。 (中略) ある晴れた日に,オハイオ州のハイウェイ警察官が,本署を呼び出すために,新しい自動車無線機を使い始めると,隣にいたキャデラックが突然,暴れ馬のようになりだした。 (中略) キャデラックはときどき凶暴になる。ただしオハイオ州の主なハイウェイ上で,しかもハイウェイ・パトロールが見ているときに限ってである。 (中略) キャデラックの配線がオハイオ州ハイウェイ・パトロールの新しい無線システムが使っている周波数にとって格好のアンテナとなることを発見した。

この本以外のソースが見つからなかったが、本書によると、特定の周波数を使う警察無線がABS回路に影響を与えていたらしい。

少し粘ってネットを検索してみると、車好きのコミュニティっぽいサイトで学生が本書のこの内容を取り上げたスレッドを発見した(が特にこの件に関して結論は出ていない)。周りの人間は懐疑的だが、私も本書のこのストーリに驚かされた。

www.pakwheels.com

日本でも赤外線リモコンが干渉を起こして火事の恐れがある、として電気ストーブの販売規制がかかったことは記憶に新しいと思う

www.nite.go.jp

本書のこのエピソードの驚くべき点は赤外線リモコンのように同じ種類の媒体同士(無線 & 無線)の干渉事故ではなく、有線(ABS) & 無線(警察無線)の干渉である点だと思う。

エピソード2:建物間で照射し合うレーザー光線を利用した通信システムが実現化されていた

筆者の一人(タネンバウム)はかつて欧州の近代的なホテルで,退屈なセッションの間,参加者が電子メールを読むことができるように,会議の主催者たちが端末をいっぱいに設置した部屋を用意した会議に参加したことがある。地元のPTTは3日間だけのために多数の電話回線を設置するのを望まなかったため,主催者は屋根にレーザーを置いて数km先の彼らの大学のコンピュータ科学の建物を狙った。

「2.3.5 光伝送」より抜粋

この話には悲しいオチがあって、昼間の太陽に暖められた対流によってレーザーの軌道が変わって、昼間だけネットが繋がらないという結果に終わったそうだ。

f:id:yuyubu:20181016202341p:plain
レーザー通信で発生した障害

しかしそこまでして会議中にメール読みたいのかよwwwと思ったけど、レーザー光線やLEDを使った2転換通信を行う発送はそこまでぶっ飛んだものでもなく、それ用の道具は普通に売ってるようだ。

www.airlinx.com

また電子工作でレーザー光線を使った通信を電子工作で実現したブログエントリがあった。

Homemade 10 Mbit/s Laser / optical Ethernet transceiver – Linux, Games, Programming and some random science stuff

技術ある人すごい

エピソード3:静止衛星の基礎原理は技術的に実現が難しかった時代にSF作家が考案した。

1945年に,サイエンス・フィクション作家ArthurC.Clarkeは高度3万5800kmの円軌道の衛星は空で動かないように見え,追跡する必要がないことを計算した(Clarke,1945)。彼は,さらにこれらの(人工)静止衛星(geostationary satellites)を使った通信システムの全容を,軌道,太陽電池パネル,無線周波数,打ち上げ手順を含めて記述した。残念ながら彼は,電力を要し,壊れやすい真空管増幅器を軌道に乗せることは非現実的であると結論付け,いくつかのサイエンス・フィクションは書いたものの,それ以上このアイデアを推進しなかった。 トランジスタの発明はすべてを変え,最初の通信衛星であるテルスター(Telstar)が1962年7月に打ち上げられた。

「2.4.1静止衛星」より抜粋

などなど、この辺は読んでてロマンが溢れる節でしたね。

常識っちゃ常識ですが人工衛星に限らずトランジスタ真空管に取って代わってコンピュータの進歩を大きく飛躍させていますね。

エピソード4:低軌道衛星のバブルは携帯電話の普及によって弾けた

1990年にMotorolaFCCに対して77個の低軌道衛星を打ち上げるイリジウムIridium)・プロジェクト(原子番号77の元素はイリジウム)の許可を申請して新天地を開拓した。後になって計画は66個の衛星を用いるように変更され,したがってジスプロシウム(原子番号66)と改名されるべきであったが,病名のように聞こえたのであろう。 7年間,協力者や資金調達をつぎはぎした結果,1998年11月に通信サービスが開始された。しかし不幸なことに1990年以降,携帯電話ネットワークが目覚ましく発達したため,大きくて重い衛星電話に対する商業需要はほとんどなかった。その結果,イリジウムは利益を上げることができず,1999年8月に破産へと追い込まれ,歴史上最も劇的な大失敗企業の一つとなっている。

「2.4.3 低軌道衛星」より抜粋

約200万分の1の価値に暴落したようです。

いる。衛星その他の資産(50億ドルの価値)は,その後,地球大気圏外ガレージセールのようにして投資家に2千5百万ドルで買われた。

衛星電話は携帯電話ほどではありませんが、結構お安く運用することができます。

www.kddi.com

これはインフラ構築が難しい場所(離島、船上、災害地)などで有用という大きなメリットがあります。

エピソード5:通信インフラに使われている銅がAT&Tの資産価値の80%を占めていた時代があった

ある時点では,AT&Tの資産価値の80%はローカル・ループの銅であった。その時点ではAT&Tは事実上,世界最大の銅鉱山であった。幸いなことにこの事実は投機筋にはあまり良く知られていなかった。もし知られていたら,ある企業侵略者がAT&Tを買収して米国のすべての電話サービスを打ち切り,電線を外して銅の精錬業者に売却して投資を回収したかもしれない。

「2.6.1 電話システムの構造」より抜粋

ある時点でAT&Tを買収してインフラの銅を全て売ればお釣りが帰ってきそうな記述ですが、特にソースがないので本当の話なのかは不明。

WEB上での議論を引用すると、

The point is to put the value of that copper (and the cost of replacing it in the event that it is damaged) into perspective.

Highly relevant quote: *At one time, 80% of AT&T's capital value was the copper... | Hacker News

とあるので、インフラを再構築するための費用として計上するなら...という意味なのかもしれない。

2章(物理層)全体の感想

この章は私のようなソフトウェアエンジニア向けの章というより、インフラエンジニアやネットワークハードウェアを研究開発する人が身につける基礎的な知識、という印象を持ちました。*1

技術パートはアナログ - デジタル変換的な話やフーリエ変換と信号処理、物理層の媒体となる素材(ガラス、銅) や電波(長波,短波)や光線(可視光線、赤外線)等の特性などについての解説が延々と続きました。

本章に掲載されている計算などは一応、情報系の学部なのでなんとなく耳にしている概念はありましたが、多くは初見のものであり、理解できないものが多かったです。

自作ネットワークプロトコルの作成などを考えている人がいるならこの辺は理解しておく必要がありそうです。

*1:このタイプのエンジニアもいるので、単なるソフトウェアエンジニアというべき文脈でエンジニアと記述する最近の風潮はあまり好きではありません。

Goの時間フォーマットは他の言語とかなり違っている

多くのプログラミング言語には時間を表示、保存するときに文字型に変換するためのフォーマットが用意されています

例えばJavaではこんな感じでyやMを使って日付フォーマットを指定します。大方他の言語でもこのような方式になっていると思います

 SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
 Date now = new Date(System.currentTimeMillis());
        
String nowStr = format.format(now);
System.out.println(nowStr);
//出力:2018-10-15 13:07:24.872

Goだとどうでしょうか。こんな感じに指定します。

now := time.Now()
nowStr := now.Format("2006-01-02 15:04:05.000")
//出力結果:2018-10-15 22:14:57.1516

あれ?なんで時刻の値を与えているんだ?と最初戸惑いましたが、Goでは2006年1月2日の15時4分という時間をサンプルとして与えてフォーマットとしています。

意味 Java Golang
M 1
d 2
時間 H 3
m 3
s 5
y 06(2006)

なおこの時刻は何か特別な日付ではなく、作者が自然と考えるフォーマットで書いたときに1,2,3...と並ぶように作ったようです。

これはアメリカ式の時刻の順番なのだ。"1月2日午後3時4分5秒2006年"(つまり「自然な順番」で1, 2, 3, 4, 5, 6)を指しているのである。

qiita.com

Goならわかるシステムプログラミングを読み終えました

13章までは一人で読みました。14章以降は横浜Go読書会に参加して読みました。

Goならわかるシステムプログラミング

Goならわかるシステムプログラミング

どんな本だったか?

Go言語の要素

  • io.Writeやio.Readなどのinterface
  • chanelで同期をとる仕組み
  • go routineで並列に処理する仕組み

などを使ってコンピュータやOS,ネットワークの仕組みに迫るという本です。大体以下の要素を学びます

  • OSのシステムコール
  • ネットワーク全般
  • ファイルシステム
  • プロセス、スレッド
  • シグナル
  • 並列処理
  • メモリ管理
  • 時間・時刻の扱い
  • コンテナ、仮想化技術
  • OSのセキュリティ(付録)

どんな人向けか?

この本はGolang × システムプログラミングな本であることは確かだけど、どちらかの理解が浅い人が片方を頼りに理解を補うような本ではないと思う。 文章とか可愛い図が多かったりする点から初心者テイストを感じするが、読後は中級者向けな印象を受けた。入門書ではないかなと。 Golangとシステム双方をある程度理解した人がその接点を探るような読み方が、ベストなのではと思う。

感想

私にとってGolangに関して初めて読んだ本となりました。ネットワークの話題などはいくつかブログに検証する記事をあげました。

yuyubu.hatenablog.com

yuyubu.hatenablog.com

yuyubu.hatenablog.com

またこの本に影響されてTour of Goをやってみた。

yuyubu.hatenablog.com

yuyubu.hatenablog.com

OSについては今年の前半に割と頑張って勉強したから分かる箇所が多かったものの、並列処理などはわからない点が多かった。

yuyubu.hatenablog.com

私自身マルチスレッドなプログラミングはあまりやったことがないので、 他の言語と比較することはできないはgoはかなりカジュアルに並列処理(go routine)ができる点が特徴だと思うので、並列・並行制御に関するベストプラクティスを紹介するような本が相性がいいんじゃないかなと思います(横浜Go読書会の次回の課題本)

今後(個人的な話)

Goもシステムプログラミングも基礎が全然足りていないという感想。まだまだ初心者にすぎないことを思い知らされた一冊でした。ほんの内容と関係ないけど今後どんなことを学んで行きたいか書いてみようと思います。

今後のシステムプログラミング分野の学習

大体は低レイヤーの歩き方に書いてあるトピックに剃って勉強を進めていく感じ。

rkx1209.hatenablog.com

今はパタヘネやコンピュータネットワークを読んでいるけど、インフラエンジニアになる予定は今のところないので、ネットワークは教養目的で勉強を進めています。

コンピュータの構成と設計 第5版 上・下電子合本版

コンピュータの構成と設計 第5版 上・下電子合本版

コンピュータネットワーク 第5版

コンピュータネットワーク 第5版

  • 作者: アンドリュー・S・タネンバウム,デイビッド・J・ウエザロール,水野忠則,相田仁,東野輝夫,太田賢,西垣正勝,渡辺尚
  • 出版社/メーカー: 日経BP
  • 発売日: 2013/09/12
  • メディア: 単行本
  • この商品を含むブログ (4件) を見る

今後のGolangの学習

Goを使うような仕事についてみたいけど、未経験なのでポテンシャル採用になると思うけど、それができる第2新卒ほど若くないし、厳しいだろうなという印象。まずはProgramming言語Goをやって基礎を固めたいと思う。

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

横浜Go読書会の次の課題本は「Go言語による並行処理」。

Go言語による並行処理

Go言語による並行処理

これもプログラミング言語Goの第8章と9章ができていないと難しいのではないかという話。

TREE LOCKをdeadlock-freeに保つ5つの条件

TREE系のindexやODBの継承関係をもつテーブル等、木のデータ構造を持つオブジェクトをロックする方法としてTREE LOCKという方法がある

単純にオブジェクト全体をロックするよりも、このロックを使ったほうがパフォーマンスが良い場合がある。

TREE LOCKのプロトコルは以下のルールに従う必要がある。

TREE LOCKが従うべき5つのルール

  • 1.要素Xにアクセスする前に必ずxをロックすること
  • 2.他のトランザクションがロックしていない時のみXのロックを確認できる
  • 3.ロックしたい要素xが木の根でない場合、必ず親の要素をロックすること(根→葉の方向でロックが進む)
  • 4.あるトランザクションがXを解放できるのはXに関する処理が全て終わったあとのみ
  • 5.あるトランザクションがXを解放後、再びXのロックを確保できない。

f:id:yuyubu:20181012211312p:plain
アクセスしたい要素の親を常に抑える

TREE LOCKではロック順が必ずroot→reafの順番に進む。例えば上記の図で23の要素が欲しい場合は

al(50)
al(17)
al(23)

の順番にロックを獲得し、解放する時はその逆で実施する。※al : acess lock

このルールに従った場合、木の中ではdead-lockが発生しなくなる。*1 なぜなら

T1→T2→...→T1

というサイクルが発生したと仮定すると、前のT1ですでにrootのlockが完了しているので、後ろのT1はlock待ちにならないからである。

TLのメリットは2PLよりもロックを早く解放することができることである。ただしこれはトランザクションマネージャーがロック解放対象のノードが不要になったタイミングを検知、通知できる場合のみである。不要確定時の通知が難しい場合、ロックの解放はトランザクションの終了時になる(=S2PL)

参考

Concurrency Control and Recovery in Database Systems

Concurrency Control and Recovery in Database Systems

*1:木が複数ある場合はdead-lockが発生する可能性がある

*2:これはあくまで私の理解であって議事録や勉強会全体での総意ではありません

IEEE754について。モダンなコンピュータはどのように少数を扱っているのか

IEEE754とは

小数の計算性能と移植性改善のために制定された。おそらく現代のほとんどのコンピュータや言語処理系が採用している少数を扱うときの規格。

値の表現方法について

その表現は符号部(sign)、指数部(exponent)、仮数部(fraction)に分けられる

f:id:yuyubu:20181008234719p:plain

value start end length
sign 31 31 1
exponent 23 30 8
fraction 0 22 23

画像の出典:https://en.wikipedia.org/wiki/IEEE_754-1985

それぞれを組み合わせて以下のように少数を表現している

(-1)sign * (1 + fraction) * 2exponent-127

sign bitを符号の有無に利用している点はシンプルだが、仮数部および指数部は 1を足したり127を引いたりしていてややこしく、初見では理解しがたいため解説を後述する

仮数部はなぜ1を足しているのか。

これは科学的表記法を2進数に適応した場合を考えるとわかりやすい。

7.5025 + 102 = 750.25

これが科学的表記法。凡例は

m * 10n ただし 0 <= m < 1

これを2進数に適応すると

1.01110111001 * 29 = 1011101110.01

となる。

2進で表現した小数は表現する数値が0以外の場合、科学的表記法に直すと仮数部の左端は必ず1になる。以下に適当な例をあげる

10進数 2進数 科学的表記法
0.75 0.11 1.1 * 2^ -2
12.5 1100.1 1.1001 * 2^ -3
33.25 100001.01 1.0000101 * 2^ -5

IEEE754ではこちらを省略するようになっている

IEEE754では,正規化された2進数の先頭の1を仮数フィールドの中で直接持たないようにした.したがって,仮数の実際の長さは,単精度では24ビットであり,倍精度では53ビット(1+52)である.正確を期す場合には,頭に1を付けた24まビットの数値を指して“significand”という用語を使用し,23ビットの数値を指して“fraction”という用語を使用する.0には前に1が付かないので,ハードウエアが1を付加しないようにするために,特定の値が予約されている.

コンピュータの構成と設計 3.5章 浮動小数点演算より抜粋(補足:倍精度小数点に関する記述を省いてある)

※予約されている特定の値は単精度浮動小数点の場合はオール0である

浮動小数点数の表現で省略した1を+1して戻すことで実際の値としている。

指数部はなぜ127を引いているのか

これはゲタばき表現、と呼ばれるものであり数値比較を単純にするために

  • 00000000の状態を最小値に(2^ -127)にしたい
  • 11111111の状態を最大値に(2^ 128)にしたい

という目標がある。ので8進数で0~255の値を計算した後、そこから127を引いてcの値に変換する。 この操作をゲタばき(バイアス)という。

最も小さな負の指数を00...00と表し,最も大きな正の指数を11...11と表すような,表記法を用いることが望ましい.それをゲタばき表現(biasedrepresentation)と呼ぶ.ゲタばき表現をとる際に,実際の値を得るために,通常の符号なしの表現から引く数値をゲタ(bias)という.

コンピュータの構成と設計 3.5章 浮動小数点演算より抜粋

まとめ

  • 最上位ビット(31ビット目)は0で整数、1で負数の符号を表す
  • 仮数部では科学的表記法の2進数表現と同じ考え方だが、最上位ビットになる「1」を省略する
  • 指数部ではゲタばき表現を使って-127~128を表現する

コンピュータの構成と設計 第5版 上・下電子合本版

コンピュータの構成と設計 第5版 上・下電子合本版

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

今回の勉強会では、標準SQLかどうかを判断できる無料の資料の存在を教えてもらったのがデカかったです。

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

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

  • 「30. 6 ベンダー 拡張」から「31.6累積統計」まで読みました。
  • 進捗72% →74%

30. 6 ベンダー 拡張

この節でベンダー拡張のWindow関数として紹介されている以下の関数は、 現在では全て標準SQLに入っているためベンダー拡張では無くなっている。

この節で書かれているベンダ間の差分は無くなっています。 これはつまりどういうことかというと、Window関数に関して、一般的に普及している主要RDBMSはかなり高い水準でSQL標準に準拠しているということです。

そういえばMySQL8にWindow関数が対応したことが大きなニュースになっていましたね。 時代がWindow関数に追いつきましたね。私も障害調査の時にWindow関数をかなりカジュアルに書きますが、まだまだ普及しているとは言い難いので、積極的に使っていきましょう。

標準SQLかどうかはどうやって見分けるか?

  • JISになったものは公開されているのでそちらをみる

  • 昔の99とかは本が出たのでそちらを参考

C.J.Dateの有名なサンプルデータについて

サンプルとして、デイトの有名な部品テーブルを利用しよう(Date,1983,1995a)。

Parts

part_nbr part_name part_color part_wgt city_name
p1 Nut Red 12 London
p2 Bolt Green 17 paris
p3 Cam Blue 12 paris
p4 Screw Red 14 London
p5 Cam Blue 12 paris
p6 Cog Red 19 London

とあるが、有名なのか?と話題を出したところ、誰も特に知らなかった。まだ本書の参考文献は量が多いことに加えて、巻末に纏めて書かれているため参照しにくい。帰宅後調査してみたところ

Dateに関して1983年と1995年の著作は以下のものがあるらしい

  • Relational Database Writings 1991-1994 [FACSIMILE], 1995, Addison Wesley Longman, ISBN 978-0201824599
  • Database : a primer, Addison Wesley, 1983, ISBN 978-0201113587

おそらくこの2冊からの引用ということだろう。

Relational Database Writings 1991-1994

Relational Database Writings 1991-1994

Database: A Primer

Database: A Primer

余談だがカラム名でググってみたところ、

  • この本
  • セルコの投稿
  • この本のmedianの節を参考にしたと思われる発表スライド

のみがヒットした。セルコ以外の人が特に利用している様子が見当たらなかった。

JIS標準がカタカナ名末尾の'ー'をつけない理由

  • コンピュータ(JIS準拠)
  • コンピューター(非準拠)

JISの資料が多すぎて末尾のーを消すだけで規格書が1冊へる、という理由があるらしいが、ソースが不明。Wikipediaにも似たようなことが書かれている

JISの従来の表記規格では、後述のように一定の基準で長音符を省略していた。省略した理由は、当時の活字などの印刷コスト、紙面や画面上の表示スペース、記憶装置などの節約と言われている[要出典]。

次回は「31.6 累積統計」から

分散処理本第39回に参加

恒例の分散本(Distributed Computing: Principles, Algorithms, and Systems)を読む勉強会です。

分散システムでのデッドロック検知はサイト間での検知を如何にとるか、と言うのがポイントだと思います。 今回勉強した2種類のアルゴリズムではサイト間でメッセージを送ってデッドロックを検知します

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

10.7  Chandy–Misra–Haas algorithm for the AND model

Andモデルでのデッドロック検出は単純で、サイクルを検出できれば良い。tripletというメッセージをWFGの依存先の各ノードがサイト外である場合に送る。

  • triple(i,j,k)の形式は以下に示す通り

    • i:デッドロック検出を開始したノード
    • j:kに依存しているノード(かつkとは別サイト)
    • k:jが依存しているノード(かつjとは別サイト)
  • 送信するprobe:triplet(pi, pj, pk)

  • 依存関係の配列:dependent_K(i)

f:id:yuyubu:20181003234144p:plain
引用元:http://www.lnse.org/vol3/205-X0012.pdf

以下がアルゴリズム

Algorithm 10.1 より引用

ポイントは以下の通り

  • サイクルの検出開始地点(Fig1の図で言うとP1がi=kのprobeを受け取った時点でデッドロックの検出が成功する。
    • 上図(fig1)の例でだと(1,5,1)のprobeがi=kに相当する
  • 検出開始ノードから送るprobeの内容とprobeを受け取ったノードが依存先にprobeを送る内容は同一

参考リンク:

10.8  Chandy–Misra–Haas algorithm for the OR model

  • 基本的な考え方
    • ORモデルの場合は一つのサイクルの検出でデッドロック検知とならない。
    • ORモデルの定義として、複数のリソースに依存している場合、依存先のリソース全てでデッドロックが発生して初めてデッドロックとなる
    • このため、WFGの各ノードは依存先のノード件数をローカル変数numでもつ
    • 依存先のデッドロック検出(後述のreply受診時)の度に、numをデクリメントする。
    • num=0のノードはその先で全てデッドロックが起こっていると言うことなのでreply(i,j,k)を自分の依存元に返す

f:id:yuyubu:20181004001029p:plain
A->Aのデッドロックが最初に発生した時

アルゴリズム

Algorithm 10.2 Chandy–Misra–Haas algorithm for the OR model より抜粋

最終的に上図のAはBからreply(A,B,A),つまりi=k=Aを受け取ってデッドロックの検知が完了する。

参考リンク:

読書会では「10.9 Kshemkalyani–Singhal algorithm for the P-out-of-Q model」まで突入したが、予習ができてないので内容がよくわからなかった。 また、10.9をやりきっていないのでそちらは次回の予習で調べます。

次回は「10.9.2 The algorithm」から