Yabu.log

ITなどの雑記

Java読書会「現場で役立つシステム設計の原則」を読む会 第2回に参加

遅れて午後から参加しました。今回は、書かれていることは確かに理想だけど...という切り口の議論が多かったように思います

現場で役立つシステム設計の原則 〜変更を楽で安全にするオブジェクト指向の実践技法

現場で役立つシステム設計の原則 〜変更を楽で安全にするオブジェクト指向の実践技法

かんしんごと vs かんしんじ?

YutakaKatoさんと漢字の読みで張り合っています

www.youtube.com

私は著者が講演で「かんしんごと」と発音しているビデオ(1:28:2~)に影響を受け、これにつられて「かんしんごと」で通しています

なぜ「関心事」だけ「じ」と読むのでしょうか？

「心配事」はいわば和語扱い、「関心事」は漢語扱いだからです。

oshiete.goo.ne.jp

日本語の読み方的には「かんしんじ」が正しいようです😇。DDD界隈読みということもありえるのでしょうか。

まぁ漢字の読み方とかにこだわっているわけではありませんが、この本やたらと「関心事」という単語が出てくるので、どうしても気になってしまうのです。

なんと252回も！出てきますw

とりあえずDRYみたいなのは有害

  • 共通しているからという理由でまとめてはいけない。ドメインの観点から検討して、本当に共通か？ を意識して共通化する必要がある。
  • 共通化というのは結果にすぎない。
  • とにかくDRY原則!というのが有害
  • 日時系のAPIは日付概念はものすごく抽象化されているから便利に使える
    • とりあえずなんとなく共通処理をまとめました、だと誰も使わない

https://qiita.com/tag1216/items/91a471b33f383981bfaa

  • ドメインを考えるのはすごく大変。重複クラスをまとめるだけなら脳みそを使わない。

Accountパターンの出どころは？

関心事のパターン 業務ロジックの内容
口座(Account)パターン 現在の値(現在高)を表現し、妥当性を管理する
期日(DueDate)パターン 約束の期日と判断を表現する
方針(Policy)パターン 様々なルールが複合する、複雑な業務ロジックを表現する
状態(State)パターン 状態と、状態遷移のできる/できないを表現する

業務ルールを記述するドメインオブジェクトの基本パターンより抜粋　

ちょっと議論の内容は失念したが、こういうプログラミングのプラクティスは

エンタープライズ アプリケーションアーキテクチャパターン (Object Oriented SELECTION)

エンタープライズ アプリケーションアーキテクチャパターン (Object Oriented SELECTION)

アナリシスパターン―再利用可能なオブジェクトモデル (Object Technology Series)

アナリシスパターン―再利用可能なオブジェクトモデル (Object Technology Series)

  • 作者: マーチンファウラー,Martin Fowler,堀内一,友野晶夫,児玉公信,大脇文雄
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2002/04
  • メディア: 単行本
  • 購入: 7人 クリック: 89回
  • この商品を含むブログ (70件) を見る

エリック・エヴァンスのドメイン駆動設計 (IT Architects’Archive ソフトウェア開発の実践)

エリック・エヴァンスのドメイン駆動設計 (IT Architects’Archive ソフトウェア開発の実践)

などが元になっていたりするらしい。 読書家な人が集まっているので「このパターンは一般的なやつ、このパターンはXXに乗ってるやつだね」という流れになったが、Accountパターンは何が元になっているか?という結論が出なかった。 エリックエバンスの本は手元にあったので一応中を調べてみたが、それらしいものはなかった

  • PoEAAの訳はひどい
    • とても読めたものではないので捨てた

粒度の小さいクラスを大量に作ることの是非

本書では単位や属性のクラスをかなり細かく作成していくが、クラス数が増えるほど依存関係が増えたり複雑になるので、とりあえずクラスを小さくすれば良いというものではない。

個人的に大事なことは責務が混ざらない程度に小さくすることだと思う

他技術的なトピックなど

適当に議論中に出たトピックをまとめます

  • for文でコレクションを確認しているコードはStream APIのAnyMatchなどを使うべき

  • JavaのStringクラスの方がクラス設計としては良いが、結果的にRubyが文字列をただのバイト列として扱っているやり方のほうが結果的に成功している

    • JavaがStringクラスに採用している設計パターンが結果的に良くなかったという趣旨の話があった

  • JSR-305

  • Kotlin最高

    • Springの開発スピードが早い(Kotlinの開発がついていけてないらしい)

次回は「小さく分けたサービスを組み立てる」から

CC本読み会第12回

勉強会 DB Transaction

Concurrency Control and Recovery in Database Systemsを読む勉強会です。

内容としてはロックのパフォーマンスに関してです。今回のポイントは競合の種類(Resource/Data)と競合を回避する手段(abort/block)がメインだと思います よくわからない箇所があったので自宅で復習しました。

今回はp87から

  • 3.12 LOCKING PERFORMANCE
    • Resource and Data Contention
    • Thrashing
    • Blocking and Restarts
    • Predeclaration
    • A Bound on Workload
    • MPL, Transaction Length, and Granularity
    • Read Locks and Nonuniform Access

を読みました。次回は「3.13 TREE LOCKING」からになります。

Concurrency Control and Recovery in Database Systems

Concurrency Control and Recovery in Database Systems

目次です

競合(Contention)に関して

  • 競合には2種類ある。リソース競合とデータ競合。
    • リソース競合(Resouce Contation):メモリやIO待ちなどのシステム的な部分
    • データ競合(Data Contation):ロックに関連する競合
  • 多かれ少なかれ多くのシステムは(物理上のスペックの上限があるので)リソース競合が発生しうる。
    • リソース競合以外の競合としてデータ競合が定義できることは発展的な議論をするために便利な概念となる。
  • データ競合はリソース競合を緩和する可能性がある

Resource contention also hurts a pure restart policy more than a blocking policy. With the latter, some transactions are blocked in lock queues, so fewer transactions compete for resources. (Thus, data contention alleviates resource contention for a blocking policy.)

  • データ競合が起きてできることが少なくなると、リソースの利用率が下がる。

競合に伴うパフォーマンス低下(Thrashing)について

  • リソース競合,データ競合それぞれに応じてThrashingが発生する恐れがある
    • DC Thrashing:ロックの取り合いによって生じるパフォーマンス劣化のこと(デッドロック含む)
    • RC Thrashing:スタベーション,またはlive lockのこと
  • DCスラッシングに関してはDBMSのリソースが無限にあっても発生する恐れがある
  • DC Thrashing pointを超えてからトランザクションを増やすと、blockされていないトランザクションの数が減少する
    • ブロック(ロック解放待ち)とデッドロックがDC Thrashingを引き起こす。特に後者は致命的。
    • DC Thrashing point(Thrashingが起こり始める臨界点みたいなイメージ)
      • DC Thrashing point以降に1つのトランザクションの追加で複数(2以上)のトランザクションが平均的にブロックされてしまう
      • DC Thrashing pointを超えてロックキューが増加するとシステムの使用率がかなり低下する
    • DC Thrashing point以降にシステムに負荷をかけるとパフォーマンスが大きく下がる

競合の解決方法

  • 競合(Data Contation)の解決方法は2種類ある

    • blocking戦略:ロックが解放されるまで待たせるロックキューを作る(waitさせる)
    • restart戦略:専有しようとしたリソースがすでにロックされていた場合、トランザクションをabortして最初からやり直す

  • 一般的なRDBMSの実装状況

    • blocking戦略をとっているもの
      • MySQLはデフォルトは50秒待ち
      • MySQL Clusterは1.2秒
      • DB2は２分待ち
      • Oracleは永久待ち?
    • restart戦略をとっているもの
      • SQLServerはabortしてredo(デフォルトは無限回試行する)
  • blocking/restartは設定で選べないのか?
    • 中身の処理内容が全く違うので設定で切り替えるような問題ではない

blockingとrestartsのパフォーマンスの比較

  • restartする方が一見コストが高いように見える
    • 再起動のコストを払う必要になるため
    • 中断した箇所までのトランザクション処理の成果は捨てられるため
  • が実際にはblocking戦略の方が早く性能劣化(Thrashing)を引き起こす
  • blockingがrestartsより良いという理屈は次の状況が両方発生する場合に
    • restartに時間がかかりすぎる → 実装によって回避可能
    • リソース競合が頻繁に怒る → CPU数を増やすことによって回避可能

  • restartの方がblockingより応答時間は増える

    • restert時にロック解放する必要があるため*1

  • ロックの取り合いをさせるくらいならアボートさせる方が良いというのが最近のDB界隈のトレンド

  • トランザクションは本来APエンジニアに見せるべきではない

    • 本来ならAPエンジニアにはcheckpointを設定させるだけにするべき

  • ブロックは利己的

  • リスタートは自己犠牲的

  • abortは処理が重そうだけどlockの方が軽いのではというのが一般的だが、実態はabortさせてredoする方がパフォーマンスが良い。

    • この本はrestart派
    • 神林さんはblocking派
      • ただし単純なlockではなく後ろにずらす
        • 先日のsundialの論文の発表でも似たような事を言われていたような?
    • 最近はトランザクションの量が多いので、キャッシュの汚染率が高い
      • 定説としてこの本に書かれている内容から時代が変わっている
        • ただこの本が古いという訳ではなく、lockとrestartのコストはアーキテクチャに依存するので随時計測する必要がある。

2PLの検討(Basic 2PL,Conservative 2PL)

Basic 2PLとConservative 2PLについて地球で一番わかりやすい解説はこちら

qiita.com

※以後Basic 2PLをB2PL,Conservative 2PLをC2PLと略します

  • 理屈上はB2PLの方がC2PLよりロックを保持している時間が短い
  • 一見B2PLの方がパフォーマンス上メリットがありそうである
  • ただしこれはデータ競合の発生が少ない場合のみ。
  • データ競合の発生が激しくなるにつれC2PLの方がロックを保持している時間が短くなる

この節p91の「Predeclaration」ですがなぜデータ競合が多いとC2PLが勝るのか、 根拠がよくわかりませんでした。

結論としてはC2PLを導入することによって - デッドロック回避 - DCスラッシングの阻止(軽減) のメリットある。(後者の方が期待度が高い)

性能限界 ~DC Thrashing ギリギリまでパフォーマンスをあげる~

リソースが無限と考えても、トランザクションを増やしたり、並列化するとスループットは上がるが、どこかで下がるポイント(DC Thrashing)がある。

DC-thrashing thus defines an operating region the combination of parameters that affect the performance.

実はこれは計算で算出可能

  • N:MPL(multiprogramming level)多分トランザクション数
  • k:一つのtransactionが要求する平均lock数
  • D:データ資源

の時DC Waolkoad W = k^{2}N/D \lt 1.5

だから性能限界は

k^{2}N/D \lt 1.5

となる。が、これは

  • DBアクセスが一様的である前提
    • ピークとかない。増減しない平均的な接続が常に発生するイメージ
  • リソース競合を考慮していない

なのでかなり楽観的な数値である。 あくまで1.5というのはこの規模の数字である、という参考を示しているにすぎない。

MPLについて

  • MPL(並列化するプロセス数)は1.5D/k2以上あげるべきではない。
    • N(MPL)をあげるとデッドロックが発生する率も上がる
    • restartのコストが高い場合はさらにNを下げる必要がある

Long Transactionについて

以下の事象はスループットを下げる要因となる

そもそもトランザクションよりもロックが増えることによる影響が大きいので トランザクションを分割することでworkloadをあげることができる

例えば

前述の式

W = k^{2}N/D

に当てはめると

(k/n)^{2}(2N)/D = k^{2}N/2Dとなり、これは分解前のW=k^{2}N/Dより倍よくなっている。

Granularity(粒度)について

Granularityの定義はchapter1のp2に書いてある

The size of the data contained in a data item is called the granularity of the data item.

  • 小さいD(荒い granularity)は大きな範囲にロックがかかる
  • 大きいD(細かい granularity)は小さな範囲にロックがかかる

Granularityが性能に及ぼす要因は3つある

  • 1.ロックオーバーヘッド
    • granularityが細かいほどロックが必要=オーバーヘッドが増える
  • 2.データ競合
    • granularityが荒いほどデータ競合が起こる可能性がある
    • ただし、granularityが細かければ良いという訳ではない
      • 一般的にgranularityが細いほどロックが増える傾向にある
      • ロックが増えるともちろんロックの衝突(Data contation)も起こりやすくなる
  • 3.リソース競合
    • 前述したが、データ競合はリソース競合を改善する可能性がある
      • ranularityが荒いとリソース競合が起きにくい。
      • ranularityが細かいとリソース競合が起きやすい

上記の3要因を踏まえるとGranularityによるスループットの変化は以下のグラフのようになる

f:id:yuyubu:20180928005540p:plain
Granularityとスループットの関連。p95から引用したものに補足説明したもの

  • ただしこのグラフのようなスループット増減を必ずとるわけではない

    • 例1:データベースの大部分にアクセスする長いトランザクションの場合
      • 粒度を細かくしても結局ロックが増えるだけなのでDの増加に対してkが伸び悩まないため①の性能劣化より後のスループット変化が起こらない
    • 例2:短いトランザクションに関してはDの増加に伴うkの伸び悩みが早く起こるので①の性能劣化が現れない
      • いきなり右肩上がりのグラフになる

  • Read Lock

    • 今まではWrite Lockを前提に考えてきたが、lockの何割かがread lockと考えるとパフォーマンスは工場する
  • アクセスの偏り
    • アクセスの偏りが発生しているとworkload(負荷)増加の恐れがある

他雑談

  • MVCCは理解に3年かかる。説明できるようになるのに8年かかる
  • 神林さんのdb tech showcase2018の発表ですが、資料公開/ブログで再整理される予定があるそうです!
  • ANSIのSQL標準の資料は、新しいものは有料だが、ベータ版は公開されていて読めるらしい
  • プログラミング言語のコンペでSQLを使って2位になったチームがあったらしい?
    • ISUCONではない。
  • COBOLで作られたWEBサーバーがあるらしい?(プロジェクト)
    • COBOLerにもなんでもCOBOLで実現する変態的な人がいるらしい

次回は「3.13 TREE LOCKING」から!

*1:ロック解放は時間がかかるような処理なのか?

dbtech showcase Tokyo2018に参加

勉強会 DB

dbtech showcase Tokyo2018に参加

f:id:yuyubu:20180925232952j:plain

このカンファレンスは「プログラマのためのSQL」の参加者から聞いて知りました。 大企業/メガベンチャーのDBの運用ノウハウだったりデータベースベンダーの方から最新の製品テクノロジなどが楽しく聞けた3日間でした。

ストレージ

  • A27:DBエンジニアのためにSSD Q&A集

SSDのセッション。内容は以下の4つ

  • 1.製品寿命
  • 2.TLC
  • 3.enterprise向けssd
  • 4.NVMe仕様SSD

SSDはHDDより爆速で早い、程度の認識しかなく、そこまで興味はなかったのですが、twitterのタイムラインが盛り上がっていたので急遽参加しました。

SSDの仕組みから始まり、寿命やコントローラーの説明、NVMeの展望などが語られました。

SSDはファームウェアは順調に進化しているが、それを利用するOSやFSはまだまだ技術に追いついていない(特にNVMe)という印象を持ちました。

企業システム向けのSSDはまだまだ進化の余地があり、今後ますます注目が集まってくる分野になると思います。

MySQL 8.0

ドキュメントベースのNoSQLデータベースとして利用しつつ、jsonの任意のデータを選択した仮想列を作成してそちらをSQLから参照するというテクニックが披露されました(x dev API)。MySQL8.0では他にもWindow関数が入ったりして大きく標準SQLに近づいたというか、自分の中でMySQL株が上がりまくりです。

トランザクション理論

  • A13・14:今後のDBのトランザクション処理のあり方について徹底討議する ～"InvisibleWriteRule: トランザクションの書込み最適化" を中心に
  • C33:MVCCにおけるw-w/w-r/r-wのあり方とcommit orderのあり方の再検討～Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management Systemを題材に

1日めのA13/14は忘れ物で*1遅れて参加したため、後半部分しか聞けませんでした。最近気になって購読し始めた「ぱと隊長日誌*2」の筆者の方や神林さん、kumagiさん(参加者)などなど、トランザクションに関する情報発信をされてる方々が勢揃いされていたので、面白いディスカッションだったと思う。

C33は事前に前倒しで開始する...との連絡が非公式にありましたが、5分前に到着したところすでに始まっており、前倒ししたのに10分程度延長されていた

発表内容としてはこちらの論文を読みながらMVCCやOCCを分散システムに適応するとどうなるか、という発表内容だった。

http://www.vldb.org/pvldb/vol11/p1289-yu.pdf

個人的に印象に残ったのが、

  • Sundialのアルゴリズムではロックに頼らず、時系列順(Timestamp Ordering)に頼ってデータの整合性を担保する
    • サイト間で物理時間は同期しない。*3同期するのは順序のみで、順序同期なら技術的に可能らしい
  • 実行順序を工夫することで、発生順ではありえない操作が実現できる
r1(x2)w2(x2)c2c1→w2(x2)r1(x2)c2c1
  • 分散システムと普通のRDBMSではcommitの意味が違う
    • 普通のRDBMS:データを保存する(ACID)
    • 分散システム:データを確定させる(他のサイトから見えるようにする)

あとちなみに別セッションですが...

Amazonのマルチマスタなデータベースに関して分散システムの勉強会で話題に登りましたが...

マルチマスターでのデッドロックの検知はそんなに優しくない AWSはマルチマスターをやっているらしい(無謀？超絶技術？)

分散処理本第37回に参加

書き込み競合は先勝ちとなっているようです。ではデッドロック検知は...気になりますねぇ(やっぱりタイムアウトなんでしょうか?)

大企業のDBA

他にもLINEさんのセッションやリクルートさんのセッションが面白かったです。 普段は聞けない大企業のDB運用事例について聞くことができました。

リクルートさんの方は社内事例の紹介という訳ではなく、昨今話題の様々なデータベース関連製品の紹介&整理でした。分量が多すぎて理解しきれていませんが、格DBやその使い分けに関してわかりやすく紹介されていました。

LINEさんは自社でMySQL関連のツールを色々作られているそうです(面白そう) １日目のYahooさんの発表も聞いておけばよかったと後悔。

勉強時間の大半をRDBMSに費やしていましたが、今までDBAの方のお話を聞く機会が今までなかったので刺激的でした。

*1:メガネ...これがないと発表会では何も見れない

*2:https://taityo-diary.hatenablog.jp

*3:やるなら原子時計とか使ってやる。今の技術でも難しいと聞いたことがある

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

勉強会 SQL

余談ですが参加者にdbtech show case tokyo 2018の参加者も多かったので、そちらの話題で雑談などが盛り上がりました。*1

「29.7ビット単位の集約関数」から読みました。

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

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

適切に設計されたOLTPデータベースは正規化されている。通常、DWHはスタースキーマスキーマまたはスノーフレークスキーマを採用しており、これはかなり非正規化されている。

ペタバイト以上のデータを持つ企業

がペタバイト以上のデータを持つ企業だと書かれているが、 このほんの情報は古く、2014年時点では売上10億ドル以上の 企業の56パーセントが 1PB以上のデータを管理している*2

  • 巨大なデータを扱うDB

  • dbtech show caseで話題のMySQL8.0の環境構築がうまくいかなかった

  • MySQL Sandboxで独立した環境を構築できる

    • dbdeployerも検討すべき。

  • MySQLはなぜ5の次が8なのか

  • 11月にpostgreSQLのカンファレンスおすすめ

  • P.562のクエリがおかしい

▼P.562

SELECT B.region_nbr, S.city_id, SUM(S.sales_amt) AS total_sales
  FROM SalesFacts AS S, MarketLookup AS M
 WHERE EXTRACT (YEAR FROM trans_date) = 2011
   AND S.city_id = B.city_id
   AND B.region_nbr = 6
 GROUP BY ROLLUP(B.region_nbr, S.city_id);
  • Bという別名はどこから出て来たのか。(Mではないのか?誤植?)

  • このSQLを実行できるTableが書かれていないのでそちらも欲しい

  • 99年にANSI SQLにRoll up,Cube関数が入った

  • 最新のMySQLにwindow関数に対応した
  • 最新のSQLiteはWindow関数に対応した
  • CUME_DIST()関数
    • 初めて見たので検証予定
  • Window Frame
    • 理解しきれてないので検証予定

前職ではウインドウ関数を多少していたのですが*3、WindowFrameを弄ったりは普段やりません。*4 ので、この辺は技術検証の必要があるかなと思います。

次は「30.6ベンダー拡張」から！

*1:参加されていない方申し訳ない

*2:http://www.jdsf.gr.jp/backup/stm/img/201507/01.pdf

*3:ウインドウ関数簡単なものなら空でかけます

*4:普通はウインドウ関数もあまり利用しないと思いますが、プロダクションのSQLの品質が疑わしい場合かなり使えます

分散処理本第38回に参加

勉強会 Distributed System

Distributed Computing: Principles, Algorithms, and Systemsを読む勉強会です。やはり難しいので少し予習していきました。アルゴリズムの分類までは一応軽く読んで概要をつかんでから臨みました

予習をしてブログの下書きを作っておくと、感想のポストがサクッとかけて良いですね。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

分散システムに置けるデッドロックの検出アルゴリズムの分類

  • path-pushing
  • edge-chasing
  • diffusion computation
  • global state detection.

出典:E. Knapp, Deadlock detection in distributed databases, ACM Computing Surveys, 19(4), 1987, 303–328.

※詳しい方が概要を知っているがその分類名を知らない、ということが発生していたので、一般的な分類ではないのかもしれない。

path-pushing

各サイトがWFGを送り合いグローバルなWFGを構築する。 送信しながらどんどんWFGを更新してデッドロックの発生、検知を明らかにして行く

edge-chasing

グラフのエッジに剃ってprobesと呼ばれる特殊なメッセージを送信して行く。 以前送信したprobeと同じものを送信した場合、それでcycleを検出できる

diffusion computation

deadlockが発生していれば帰ってくるようなエコーメッセージを送る。

よく解らん？という話になった

参考にしてある論文は以下のもの

    1. Chandy, J. Misra, and L. M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems, 1(2), 1983, 144–156.

  2. Herman and K. M. Chandy, A Distributed Procedure to Detect AND/OR Deadlock, Technical Report TR LCS-8301, Department of Computer Sciences, University of Texas, Austin, TX, 1983.

本書記載のアルゴリズム例は2つあり、

  • Chandy–Misra–Haas algorithm for one OR model
  • Chandy–Herman algorithm

前者はWikipediaの記事があった

https://en.wikipedia.org/wiki/Chandy-Misra-Haas_algorithm_resource_model

CMHアルゴリズムとしても有名らしい

global state detection.

分散システムの各スナップショットからデッドロック有無を確認する。しかし以下の条件が必要である

  • (i) a consistent snapshot of a distributed system can be obtained without freezing the underlying computation.

  • (ii) a consistent snapshot may not represent the system state at any moment in time, but if a stable property holds in the system before the snapshot collection is initiated, this property will still hold in the snapshot.

10.6  Mitchell and Merritt’s algorithm for the single-resource model

アルゴリズムとしてはpublic/privateなlabelを使う 文章化するのがちょっと難しいが一言で表すなら

  • 待ち状態に対して２種類(private/public)のラベル作成し値zを与える
    • 下の例はu->v間の待ちを表しているこのzはu+vより大きな値かつユニークでなければならない
    • この操作を待ちの連鎖が終わるところまで続けて行く

f:id:yuyubu:20180918234652j:plain

2週することで図のDetectの状態が発生が把握できる(1週しただけだとDeadlockかどうかわからない)

p360の図は誤植

  • Figure 10.2 The four possible state transitions [22]

という図があるが元ネタが「E. Knapp, Deadlock detection in distributed databases, ACM Computing Surveys, 19(4), 1987, 303–328.」という論文の図であり、引用するときに一部記号が間違っている。

また10.6は本書中の記載のみだと理解が辛く、引用元の論文をよく読み込まないと何を行っているかわからない。

余談:ACM Degital Libaryは高い

500ドルくらいするらしい。。。

次回は「10.7  Chandy–Misra–Haas algorithm for the AND model」から!

a tour of Goをやった

Golang

Goならわかるシステムプログラミングで推奨していたのでとりあえず一周して見た*1

https://go-tour-jp.appspot.com/list

Go言語の文法については、全くのプログラミング初心者でなければ、tour of Goという公式のチュートリアルを一通りこなすだけで、本書の範囲なら十分理解できるでしょう

Goならわかるシステムプログラミングp4より抜粋

と書かれていたのでとりあえずやっておこう、というつもりで進めたのだが。。。 だらだらやったのもあってか1.5日ほどかかった。

とりあえず自分は日頃競プロ的な頭を使うプログラミングをやらないので、 プログラミング能力が劇的に落ちていることを実感した。

時間をかけて競プロを強めようとは思わないが、アルゴリズムとかのエンジニアとしての基礎的な部分を固める必要があると再度認識した。

コードはあまり人に見せられるような綺麗なものではないけど、時間がかかった課題のものを中心に公開しておきます。

フィボナッチ

https://go-tour-jp.appspot.com/moretypes/26

DRYにものすごく反しているような???

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    count := 0
    v1 := 0
    v2 := 0
    value := 0
    return func() int {
        defer func() { count++ }()
        if count == 0 {
            return 0
        } else if count == 1 {
            v1 = 0
            v2 = 1
            return 1
        } else {
            value = v1 + v2
            v1 = v2
            v2 = value
            return value
        }
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 15; i++ {
        fmt.Println(f())
    }
}

ワードカウント？的なやつ。一応テストは全てパスした

https://go-tour-jp.appspot.com/moretypes/23

package main

import (
    "golang.org/x/tour/wc"
    "strings"
)

func WordCount(s string) map[string]int {
    wordlists := strings.Fields(s)
    countMap := make(map[string]int)
    for _, v := range wordlists {
        countMap[v]++
    }
    //return map[string]int{"x": 1}
    return countMap
}

func main() {
    wc.Test(WordCount)
}

なんか画像を作るやつ

https://go-tour-jp.appspot.com/moretypes/18

package main

import "golang.org/x/tour/pic"

func Pic(dx, dy int) [][]uint8 {
    value := make([][]uint8, dy)
    for i := 0; i < dy; i++ {
        value[i] = make([]uint8, dx)
        for j:=0;j<dx;j++{
            value[i][j] = uint8(i^j)
        }
    }
    return value
}

func main() {
    pic.Show(Pic)
}

生成する画像は、好きに選んでください。例えば、面白い関数に、 (x+y)/2 、 x*y 、 xy などがあります。

f:id:yuyubu:20180918023900p:plain
(x+y)/2
f:id:yuyubu:20180918023856p:plain
x * y
f:id:yuyubu:20180918023902p:plain
x ^ y

ASCII文字 'A' の無限ストリームを出力する Reader

package main

import "golang.org/x/tour/reader"

type MyReader struct{}

// TODO: Add a Read([]byte) (int, error) method to MyReader.
func(r MyReader) Read(b []byte) (int ,error){
    b[0] = 'A'
    return 1,nil
}


func main() {
    reader.Validate(MyReader{})
}

io.Readerをラップした暗号復号処理(rot13)

rot13Reader(io.Readerをラップして換字式暗号を標準入出力に変換してだす)

readerが最後にerrorとしてio.EOFを返すのが解らずに、1時間ほど試行錯誤した。

package main

import (
    "fmt"
    "io"
    "os"
    "strings"
)

type rot13Reader struct {
    r io.Reader
}

func (r2 rot13Reader) Read(p []byte) (n int, e error) {
    i := 0
    b := make([]byte, 1)
    for {
        _, err := r2.r.Read(b)
        //fmt.Printf("n = %v err = %v b = %v\n", n, err, b)
        //fmt.Printf("b[:n] = %q(%v)\n", b[0], b[0])
        if err == io.EOF {
            break
        }

        value := b[0]
        //文字の場合のみ暗号置換を実施する
        if 64 < b[0] && b[0] < 91 {
            value = value + 13
            if value > 90 {
                value = value - 26
            }
        }

        if 96 < b[0] && b[0] < 123 {
            value = value + 13

            if value > 122 {
                value = value - 26
            }
        }

        //fmt.Printf("lot13 = %q(%v)\n", value, value)
        p[i] = value
        i++
    }

    return i, io.EOF
}

func main() {
    s := strings.NewReader("Lbh penpxrq gur pbqr!")
    r := rot13Reader{s}
    //b := make([]byte, 100);r.Read(b)
    io.Copy(os.Stdout, &r)
}

解読後は普通の文章になっているので多分あっていると思うが、if文の境界値条件はきちんと検査していないのでバッグっているかもしれない。

conncurenncyを使った二分木探索

https://go-tour-jp.appspot.com/concurrency/8

package main

import (
    "fmt"
    "golang.org/x/tour/tree"
)

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    //fmt.Println(t)
    //左があるときはどんどん左に行っちゃう
    if t.Left != nil {
        Walk(t.Left, ch)
        ch <- t.Value
        if t.Right != nil {
            Walk(t.Right, ch)
        }
        //左がなくなったけど右がある場合はそっちに行く
    } else if t.Right != nil {
        ch <- t.Value
        Walk(t.Right, ch)
    } else {
        //葉
        ch <- t.Value
    }
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1:=make(chan int,10)
    ch2:=make(chan int,10)
    Walk(t1,ch1)
    Walk(t2,ch2)

    for i:=0;i<10;i++{
        v1:= <-ch1
        v2:= <-ch2
        if(v1!=v2){
            return false
        }
    }
    return true

}

func main() {
    fmt.Println("test")
    /*

   ch := make(chan int)
   go Walk(tree.New(2), ch)
   count := 0
   for i := range ch {
       fmt.Println(i*10)
       count++
       if(count == 10){
           //closeするタイミングをどこに入れるか解らなかったので
           //呼び出し側にいれた。こういうプログラミングは良くないと思う
           close(ch)
       }
   }
   */
    b1:= Same(tree.New(1), tree.New(2))
    fmt.Println(b1)
}

mutexを使ったクローラー

https://go-tour-jp.appspot.com/concurrency/10

Crawlメソッドの呼び出しを並列に(goroutine)にしなければ動く。 並列にするとなぜか正しく動かない。これは自分がmutexとか並列プログラミングにまだまだ無知だからだと思う。 とりあえず私が並列プログラミングをやるとdeadlockだらけになることがわかった。

package main

import (
    "fmt"
    "sync"
)

type Fetcher interface {
    // Fetch returns the body of URL and
    // a slice of URLs found on that page.
    Fetch(url string) (body string, urls []string, err error)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher) {
    // TODO: Fetch URLs in parallel.
    // TODO: Don't fetch the same URL twice.
    // This implementation doesn't do either:

    if depth <= 0 {
        return
    }

    mux.Lock()
    if check[url] == 1 {
        mux.Unlock()
        return
    }
    check[url] = 1
    body, urls, err := fetcher.Fetch(url)
    mux.Unlock()


    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        //go Crawl(u, depth-1, fetcher) //並列だと正しく動かない
    Crawl(u, depth-1, fetcher)

    }
    return
}

func main() {
    check = make(map[string]int)
    Crawl("https://golang.org/", 4, fetcher)
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

var mux sync.Mutex
var check map[string]int

func (f fakeFetcher) Fetch(url string) (string, []string, error) {

    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
    "https://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "https://golang.org/pkg/",
            "https://golang.org/cmd/",
        },
    },
    "https://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "https://golang.org/",
            "https://golang.org/cmd/",
            "https://golang.org/pkg/fmt/",
            "https://golang.org/pkg/os/",
        },
    },
    "https://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
    "https://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
}

他：違和感のある翻訳

呼び出す 具体的な メソッドを示す型がインターフェースのタプル内に存在しないため、 nil インターフェースのメソッドを呼び出すと、ランタイムエラーになります。

https://go-tour-jp.appspot.com/methods/13

編集履歴を辿って原文を確認すると以下のようであった

Calling a method on a nil interface is a run-time error because there is no type inside the interface tuple to indicate which concrete method to call.

https://github.com/atotto/go-tour-jp/commit/123f593e8270035b7f59a8d4eaa0e61bbee98239

具象メソッドを含むinterfaceタプルが存在しないのでnilインターフェースの呼び出しはエラーになります。くらいが妥当な気がする?

というかinterfaceタプル、ってなに？っていう感じでgoをそこまでわかっていないので具体的に今どういう役が適切かは提案できない。

https://qiita.com/umisama/items/e215d49138e949d7f805

だたgoのnilはJavaのnullとも違うし、nil自体がnil型のような特性を持っているような振る舞いがあるようなので、 この辺りは今後注意して学習して行きたい。

感想

今までは写経中心だったり、ロジックというよりもAPIのドキュメントを調べて書かれている通りに実装することが中心だったが、Goできちんとプログラミングを書くのは初めてだったのでいい経験になったと思う。

何よりも、tour of Goをやらねばいけない、という憑き物のようなものが落とせてよかった。

*1:と行っても周回するつもりはあいrません

GolangでUDPサーバー&クライアントを作成してWiresharkで検証する

Golang ネットワーク Wireshark

Goならわかるシステムプログラミング第７章 UDPソケットを使ったマルチキャスト通信に書かれている内容をWiresharkを使ったり、デバッグでライブラリ(netパッケージ中心)のソースを読んだりして検証してみました

サーバー側

  • net.ListenPacket()の戻り値のnet.PacketConnインターフェースを使う
    • TCPの時のnet.Listenerインタフェースのようなクライアントを待つインタフェースではない
    • ReadFromメソッドで受信内容を読み取る
      • 引数で渡しているbufferに通信内容を格納している
      • remoteAddressに通信して来たクライアントのアドレスを受け取っている
      • bufferの中身はあくまでudpパケットの中身しか入らない
        • だからIPヘッダの情報などはReadだけでは読み取れず、ReadFromで別途IPアドレスなどを取得する必要がある
package main

import (
    "fmt"
    "net"
)

func main() {
    fmt.Println("Server is runnign at localhost:8888")
    conn, err := net.ListenPacket("udp", "localhost:8888")
    if err != nil {
        panic(err)
    }
    defer conn.Close()

    buffer := make([]byte, 1500)
    for {
        length, remoteAddress, err := conn.ReadFrom(buffer)

    if err != nil {
            panic(err)
        }

        fmt.Printf("Received from %v: %v\n",remoteAddress, string(buffer[:length]))

    _, err = conn.WriteTo([]byte("Hello from Server"), remoteAddress)

        if err != nil {
            panic(err)
        }

    }
}

ReadFrom関数の実装が気になったので確認してみた

//udpsock.go
func (c *UDPConn) ReadFrom(b []byte) (int, Addr, error) {
    if !c.ok() {
        return 0, nil, syscall.EINVAL
    }
    n, addr, err := c.readFrom(b)
    if err != nil {
        err = &OpError{Op: "read", Net: c.fd.net, Source: c.fd.laddr, Addr: c.fd.raddr, Err: err}
    }
    if addr == nil {
        return n, nil, err
    }
    return n, addr, err
}

//udpsock_posix.go
func (c *UDPConn) readFrom(b []byte) (int, *UDPAddr, error) {
    var addr *UDPAddr
    n, sa, err := c.fd.readFrom(b)
    switch sa := sa.(type) {
    case *syscall.SockaddrInet4:
        addr = &UDPAddr{IP: sa.Addr[0:], Port: sa.Port}
    case *syscall.SockaddrInet6:
        addr = &UDPAddr{IP: sa.Addr[0:], Port: sa.Port, Zone: zoneCache.name(int(sa.ZoneId))}
    }
    return n, addr, err
}

//fd_unix.go
func (fd *netFD) readFrom(p []byte) (n int, sa syscall.Sockaddr, err error) {
    n, sa, err = fd.pfd.ReadFrom(p)
    runtime.KeepAlive(fd)
    return n, sa, wrapSyscallError("recvfrom", err)
}

//syscall_unix.go
func Recvfrom(fd int, p []byte, flags int) (n int, from Sockaddr, err error) {
    var rsa RawSockaddrAny
    var len _Socklen = SizeofSockaddrAny
    if n, err = recvfrom(fd, p, flags, &rsa, &len); err != nil {
        return
    }
    if rsa.Addr.Family != AF_UNSPEC {
        from, err = anyToSockaddr(&rsa)
    }
    return
}

//zsyscall_darwin_amd64.go
// THIS FILE IS GENERATED BY THE COMMAND AT THE TOP; DO NOT EDIT

func recvfrom(fd int, p []byte, flags int, from *RawSockaddrAny, fromlen *_Socklen) (n int, err error) {
    var _p0 unsafe.Pointer
    if len(p) > 0 {
        _p0 = unsafe.Pointer(&p[0])
    } else {
        _p0 = unsafe.Pointer(&_zero)
    }
    r0, _, e1 := Syscall6(SYS_RECVFROM, uintptr(fd), uintptr(_p0), uintptr(len(p)), uintptr(flags), uintptr(unsafe.Pointer(from)), uintptr(unsafe.Pointer(fromlen)))
    n = int(r0)
    if e1 != 0 {
        err = errnoErr(e1)
    }
    return
}

このSyscall6の中身は見れなかった。名前的にもこれはネットワーク系のシステムコールなのでしょうか。 という訳で、コールスタックは私の場合は

syscall.recvfrom (/usr/local/go/src/syscall/zsyscall_darwin_amd64.go:146)
syscall.Recvfrom (/usr/local/go/src/syscall/syscall_unix.go:262)
internal/poll.(*FD).ReadFrom (/usr/local/go/src/internal/poll/fd_unix.go:215)
net.(*netFD).readFrom (/usr/local/go/src/net/fd_unix.go:208)
net.(*UDPConn).readFrom (/usr/local/go/src/net/udpsock_posix.go:47)
net.(*UDPConn).ReadFrom (/usr/local/go/src/net/udpsock.go:121)
main.main (/User/Study/go-sys/chap7/udp_server/udpServer.go:18)

となった。

クライアント側

package main

import (
    "fmt"
    "net"
)

func main() {
    conn, err := net.Dial("udp4", "localhost:8888")
    if err != nil {
        panic(err)
    }

    defer conn.Close()
    fmt.Println("Sending to server")
    _, err = conn.Write([]byte("Hello from client"))
    if err != nil {
        panic(err)
    }

    fmt.Println("Receiving from server")
    buffer := make([]byte, 1500)
    length, err := conn.Read(buffer)
    if err != nil {
        panic(err)
    }
    fmt.Printf("Received: %s\n", string(buffer[:length]))
}

net.Dialでnet.Connインターフェース(実装はnet.UDPConn)を取得してそちらにWrite,Readで送受信ができる。 とてもシンプルですね。

キャプチャ結果

この2つのソースで送受信それぞれ1つづつしかパケットが飛んでいない。

f:id:yuyubu:20180917005441p:plain

UDPはとてもシンプルですが、TCPが信頼性を担保するためにいかに頑張ってくれているか、というのが実感できるのではないでしょうか。

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

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