embryo

エンジニアの備忘録

再帰下降構文解析で電卓プログラムを実装する

Typescript アルゴリズム

パーサ入門として式解析の一つである再帰下降構文解析をTypescriptで実装してみたのでまとめました。

構文解析の基礎

構文解析入門にあたって基本的な語句を整理します。

構文図

構文の規則を図式化したもの。構文の構成要素とその関係性を図式で表します。 例えばある言語のルールとして「英字で始まりで英字と数字で構成されるもの」が識別子とされている場合、その識別子は下記のような構文図で表されます。下記の例だとab0, b01aなどが該当します。

f:id:sue71:20180201023554p:plain

BNF記法

構文図を文字列で表現したもの。例えば前述の例を表す場合

<識別子> ::= <英字> (<数字> | <英字>)
<英字> ::= a | b | c| ... | z 
<数字> ::= 0 | 1 | 2 | ... | 9

のようになります。<>で囲まれているものは非終端記号、それ以外を終端記号といいます。

  • 非終端記号: 他の文字列で代替されるもの
  • 終端記号: 他の文字列で代替されないもの

字句解析

構文解析する前に、文字列を構文規則に従って意味を持つ集合(トークン)に分割する必要があります。トークンは例えば以下のようなものが該当します。

  • if
  • else
  • (
  • )

ここで取得されたトークンを元に構文解析を行います。構文解析の手法は色々ありますが今回はよく使用されている再帰下降構文解析を実装します。

再帰下降構文解析

BNFに出現した非終端記号に対応する関数を用意し、末端から値を決定していく方法です。

再帰下降構文で四則演算

四則演算を実装する場合、演算子の優先度を考慮する必要がありますが再帰下降構文を用いた場合は構文規則そのものに演算子優先度が含まれます。 式をexpression, 項をterm, 因子をfactorとした場合、四則演算の構文規則は

<expression> ::= <term> [ ('+'|'-') <term> ]*
<term>   ::= <factor> [ ('*'|'/') <factor> ]*
<factor> ::= <number> | '(' <expression> ')'

のようになります。expressionを根としたツリー構造を考えるとexpressionから下向きに処理が実行されてていき、factorは必要に応じてexpressionを呼び出すので再帰的な性質も持っています。

Node.jsによる実装

下記仕様で簡易電卓プログラムを実装しました。

  • 変数には[a-z]が使用可能
  • 四則演算が使用可能
  • ?はPrint文として扱う

gist.github.com

  1. 入力を受け付け
  2. statement関数で1文(1行)ずつ処理
  3. expression, term, factorで式を解析、stackに値を詰める
  4. Print文が呼び出された場合はstackから値を取り出して出力する

といった流れで実装しています。

識別子の扱いについて

今回は代入される値が数値であることが決まっているのでシンプルに配列を定義していますが実際は型情報などを保持する必要があります。これを記号表と呼ぶのですがこちらに関しては別記事で紹介します。

実行結果

a = 10 + 5
b = a + 10
? b
25

参考

SketchPlugin開発の効率化

Javascript Sketch フロントエンド

この記事はSketch Adevent Calendar の 17日目の記事になります。

今日はデザインツールSketchのPlugin開発を効率的に行う手法についてまとめていきます。開発者向けの記事となりますのでご留意ください。

SketchPlugin開発の基本

SketchPluginは以下のディレクトリ構造で構成されています。下記の場合、pluginame.sketchpluginをダブルクリックすることでSketchにインストールされます。各要素の意味は下記のとおりです。

  • Sketch: SketchPluginの本体が配置されます
  • Resources: 画像などの静的リソースが配置されます。こちらに配置されたリソースはスクリプトからアクセスすることが出来ます
  • manifest.json: 名前などの情報や、スクリプトのパスなどが記述されます
pluginname.sketchplugin
└── Contents
    ├── Resources
    │   └── logo.png
    └── Sketch
        ├── command.js
        └── manifest.json

詳細は公式のドキュメントを参照するのが一番分かりやすいです。最近更新されたようで更にわかりやすくなっています。

developer.sketchapp.com

SketchPlugin開発のつらみ

一度でもSketchPluginを開発したことがある方なら以下のようなつらみに悩まされたことがあるかと思います。

  • cocoascriptによる開発
  • UIの実装が高コスト
  • 貧弱なデバッグ機能
  • UndocumentedなAPI

今回はこれらの問題点をできるだけ解消して開発を効率的に行う方法についてまとめたいと思います。

ES6で開発するための環境を整える

cocoascriptによる開発

cocoascriptはJavascriptの記法でネイティブの機能を操作できるというもので、基本的にSketchPluginはcocoascriptで記述されます。 文法はJavascriptCoreに準拠するため、新しいバージョンのSketchであればES6文法もサポートされていますが、import/exportは当然ES6のように書くことはできないため、以下のような特殊な文法で記述する必要があります。

@import "someUtils.js";

someUtils();

webpackでバンドルする

文法自体はES6に対応しているため、webpackなどでBundleしたファイルをSketchフォルダ以下に移してあげれば良さそうです。これでimport/exportの問題は解消され、npmモジュールなどの使用も簡単に行えるようになります。また後述しますが、WebView上のJavascriptとcocoascriptでコードを共有することも出来るようになります。

skpmを使う

実際にwebpackを使用するには、いくつか特殊な設定が必要になります。例えばエントリポイントとなる関数をグローバルに定義する必要があるのですが、それらのSkechPluginに必要なwebpackの設定を内包したビルドツールがskpm-buildです。

他にも本来SketchPlugin上では使用できないconsoleなどを使用できるようにするpolyfillなども自動で追加されるのでSketchPluginの開発においてはこちらのツールを使用するのが良いかと思います。公式でも紹介されていますがドキュメントがまだ整備されていないので近々別の記事で紹介できればと思います。

UIをWebViewで実装する

AppKitを用いた場合

基本的にUIはAppKitで実装することになるので下記のようにコードで直接矩形情報を指定する必要があります。iOS開発者やFlash開発者には馴染みがあるかもしれませんが、SketchPluginの開発ではUI確認のためのツールなどが提供されているわけではないので、複雑なUIを実装するのには不向きです。

let view = NSView.alloc().initWithFrame(NSMakeRect(0, 0, 200, 180));

WebViewを利用する

WebViewを用いることでHTMLでUIを作成することができます。cocoascript とWebView Scriptのイベントのやり取りは下図のように行うことができます。

f:id:sue71:20171218022839p:plain

cocoascript -> webView

WebViewのAPI経由でWebView上のJavascriptを実行することができます。予めWebView上にSketchから呼ばれる関数をグローバルに登録しておくことで特定の関数を呼び出すことが出来ます。

webView -> cocoascript

WebViewはURLの変更イベントをハンドリングすることが出来るので、WebView内のJavascriptでURLにハッシュを付与することでイベントを通知することができます。

sketch-module-web-view

sketch-module-web-viewは前項のやり取りを抽象化してくれるライブラリです。こちらを利用した場合下記のように処理をやり取りすることが出来ます。

  • cocoascriptからwebviewの処理を実行
const webUI = new WebUI(context, "index.html", options);
webUI.eval(`callJavascript()`);
  • webviewからcocoascriptの処理を実行
import { pluginCall } from "sketch-module-web-view/client";
pluginCall("callNative", "args")

デバッグ環境を整える

下記ログファイルにSketchPlugin内でlogを用いてロギングされた内容や、エラー内容が出力されています。

tail -f ~/Library/Logs/com.bohemiancoding.sketch3/Plugin\ Output.log

上記のようにtailで参照することも可能ですが、sketch-dev-toolsを利用することでSketch上でログを確認することができます。またsketch-dev-tool上でドキュメントツリーの状態やSketchのアクションも確認できるので大変便利になりました。(下図)

  • Output Log f:id:sue71:20171218030808p:plain

  • Tree f:id:sue71:20171218030810p:plain

  • Action Log f:id:sue71:20171218030804p:plain

また、manifest.jsonに不備がある場合、エラー出力は下記のようにして確認できます。実行時のログと出力箇所が違うことに注意してください。

tail -f ~/Library/Logs/com.bohemiancoding.sketch3/Plugin\ Developer.log

class-dumpでクラスヘッダを確認する

公式サイトにていくつかのAPIドキュメントが公開されていますが、これらはほんの一部です。実際にレイヤーなどがどういった構造を持っているかは実行時にログで確認するしかありません。そこでclass-dumpを用いてヘッダファイルを出力しインターフェースを確認します。

class-dumpはこちらからダウンロードしてください。下記のように実行することで使用しているクラスのヘッダファイルを取得できます。

$ class-dump /Applications/Sketch.app

例えばSketchのレイヤーを司るクラスのインターフェースは下記のように出力されます。

@interface _MSLayer : MSModelObject
{
    BOOL _isFlippedHorizontal;
    BOOL _isFlippedVertical;
    BOOL _isLocked;
    BOOL _isVisible;
    long long _layerListExpandedType;
    NSString *_name;
    BOOL _nameIsFixed;
    NSString *_originalObjectID;
    unsigned long long _resizingType;
    double _rotation;
    BOOL _shouldBreakMaskChain;
    NSDictionary *_userInfo;
    MSExportOptions *_exportOptions;
    MSRect *_frame;
}

まとめ

SketchPuginを開発する上で困るポイントとその問題に対する対処法を説明しました。本記事を書き始めた頃からもplugin開発事情に変化が起きているようです。(例えばsketch-dev-toolは10月末頃リリースされました。) 情報が古い可能性もあるため、もっと良い方法などありましたらコメント頂けるとうれしいです。

最後に今回説明した実装のサンプルです。

github.com

PWAを支える技術とPRPLパターンの実装

Architecture Javascript React フロントエンド

この記事はトレタ Advent Calendar 2017の11日目の記事です。

dev.toで最近話題になったPWA実装ですが、今日はそのPWA設計パターンの１つであるPRPLを実践するために必要な技術スタックとその実装方法についてまとめました。

PRPLパターンとは

Googleが提唱するPWAの設計パターンの１つです。

PRPL パターン  |  Web  |  Google Developers

  • (P)ush: HTTP/2 Pushを用いて初期表示に必要なリソースを配信します
  • (R)ender: 最小限の初期描画を行い、インタラクティブな状態にします
  • (P)re-cache: ServiceWorkerを用いて事前に他のルートのリソースをキャッシュします
  • (L)azy-load: ユーザー操作に合わせてオンデマンドにリソースの配信と生成を行います

これらの頭文字をとってPRPLと呼んでいるようです。

PRPLを支える技術

PRPLを実現するための重要な技術としてHTTP/2 Server PushとServiceWorkerがあります。

HTTP/2 Server Push

従来のHTTP/1.1のリクエストでは

  • htmlファイルをリクエストする
  • htmlファイルを解析する
  • Javscript, cssなどのリソースが見つかったら読み込む

というステップで初期表示が行われていましたが、HTTP/2 Server Pushを用いることで１つのリクエストに対して複数のレスポンスを送信することが可能になります、つまり要求されたリソースに加えて、リソースを追加して送信することができるので一度のリクエストで初期の表示に必要なリソースを返却することが出来ます。

実装方法として後述する2つの方法があげられます。

ストリームを直接操作する方法

下記の例はnodejs+expressの実装例です。streamを操作し、レスポンスにリソースを追加しています。

gist.github.com

Linkヘッダを利用する方法

下記のようなLinkヘッダををレスポンスに追加することでServerPushのトリガーとなります。 厳密にはリソースヒントと呼ばれる仕様でH2O, nghttp2などではServerPushのトリガーとして扱っているようです。

link: <[url]>; rel=preload; as=[file type]

[url]にはリソースへのURLが、[file type]にはstyle, scriptなどのファイルタイプが入ります。

ServiceWorker

Service Workerはページ上で実行されるスクリプトとは別のスレッドでで別のスクリプトを実行することができる機能です。ネットワークプロキシとしてリクエストをコントロールしたりデータをキャッシュすることが可能です。

ライフサイクル

ServiceWorkerは登録→インストール→アクティベートの順に状態が遷移します。

登録

Service Workerスクリプトを登録します。<scope>を渡すことで特定のルート以下をコントロールすることを明示できます。

if ('serviceWorker' in navigator) {
  navigator.serviceWorker.register(‘/sw.js’, {scope: <scope>)
  .then(function(registration) {
    console.log(’Success registration’);
  })
  ;
}
インストール

登録が完了するとinstall状態へ移行します。install時に処理を登録した場合は下記のようにハンドリングできます。

self.addEventListener('install', function(event) {
  console.log(“Service worker is installed")
});
アクティベート

Workerに登録したjsの更新時、ServiceWorkerがすでにインストールされている場合はデータの不整合を防ぐために、Workerが更新可能な状態まで待つことになります(ページを閉じるなどした場合に更新可能になります)。そのため、コントロール可能な状態をハンドリングしたい場合はactivateイベントに処理を登録する必要があります。

不整合が起きないことが予めわかっている場合に、すぐにactivateな状態に移したい場合は

self.addEventListener(‘activate', function(event) {
     event.waitUntil(self.skipWaiting());
});

また、workerがコントロールするのは登録後に開かれたページなので、すぐさまページをコントロールしたい場合は

self.addEventListener(‘activate', function(event) {
    event.waitUntil(self.clients.claim());
});

のようにすることですぐにページのコントロールを開始することが出来ます。

キャッシュ戦略

Service Workerをキャシュに用いる場合、２つの方法があります。

  • Install時にキャッシュを更新する
  • オンデマンドにキャッシュを更新する
Install時にキャッシュを更新する

予めキャッシュするリソースを指定し、installイベント時にキャッシュを更新します。PreCacheを実現するためにはこの方法を用いるのが良さそうです。

var CACHE_NAME = 'cache-v1';
var urlsToCache = [
  '/',
  '/styles/main.css',
  '/script/main.js'
];

self.addEventListener('install', function(event) {
  event.waitUntil(
    caches.open(CACHE_NAME)
      .then(function(cache) {
        console.log('Opened cache');
        return cache.addAll(urlsToCache);
      })
  );
});
オンデマンドにキャッシュを更新する

fetchイベントを通してファイル単位でキャッシュを更新します。リクエストを逐次キャッシュすることが出来るため2回目のアクセスを高速化できます。streamは用途に応じて複製する必要があるため扱いに注意してください。

self.addEventListener('fetch', function(event) {
  event.respondWith(
    caches.match(event.request)

      .then(function(response) {
        if (response) {
          return response;

        }

          // キャッシュ用とリクエスト用が必要なのでclone
        var fetchRequest = event.request.clone();

        return fetch(fetchRequest).then(

          function(response) {
            // リクエストが成功しており、なおかつoriginからの要求であること
            if(!response || response.status !== 200 || response.type !== 'basic') {
              return response;

            }
            // キャッシュ用とブラウザに返却する用が必要なのでclone
            var responseToCache = response.clone();

            caches.open(CACHE_NAME)
              .then(function(cache) {
                cache.put(event.request, responseToCache);
              });

            return response;
          }
        );
      }
    )
  );
});

PRPLをReactで実装する

以下の一般的なフロントエンド技術スタックでPRPLを実装する方法を考えます。

  • react
  • react-router
  • webpack

Push

HTTP/2 Server Pushに対応した配信サーバーを構築します。

webpackを使用する場合はpreact-cliの実装を参考にするのが良さそうです。 preact-cliの実装ではビルド時にこちらのフォーマットでファイルを出力し、配信時にLinkヘッダを付加することでServerPushを実現しているようです。

https://github.com/GoogleChromeLabs/simplehttp2server#http2-push

PreCache

初期表示完了後に残りのルートに必要なファイルをServiceWorkerのinstall時にキャッシュします。Install時のキャッシュ方法に関しては前項で説明しましたが、

sw-precache-webpack-pluginを使用することでServiceWorker用のスクリプトをwebpackビルド時に自動で生成することが出来ます。キャッシュ対象としてwebpackでビルドしたリソースが自動で追加されますが、設定項目でカスタマイズが可能です。

生成されたservice-worker.jsをエントリポイントで登録します。

Lazy-Load

オンデマンドロードを実現するために、リソースの分割とロード方法について考えます。

webpackによるリソース分割

リソースを取得する際、極端な例として2つの方針が考えられます。

  • 1リクエストに対して1モジュールを返す方法
  • 1リクエストに対してバンドルされた1ファイルを返す方法

前者は必要なリソースのみを取得できますが、リクエストが多くなってしまうためリクエストのオーバーヘッドが大きくなります。 後者は1度のリクエストで済むためオーバーヘッドは小さくなりますが不要なファイルも読み込むことになります。

これに対してwebpackでは、その折衷案としてある程度のまとまり(chunk)にファイルを分割する機能が提供されています。Push, PreCacheを有効に使うためにアプリケーションのバンドルを適切に分割する必要があるため、アプリケーションのコア(AppShell)と各ルートのchunkに分割するのが良さそうです。

リソース読み込み時にrequire.ensureを呼び出すことでchunkの分割対象と見なしてくれるようになります。(webpack2以降ではDymanic Importもサポートされているようです)

ルーティング

遷移時に各ルートのリソースを取得するためにreact-routerのgetComponentを呼び出します。webpackの設定ファイルにてchunkFilenameを指定しておくことで、require.ensure で指定した名前でファイルが作成されます。

  • react-routerの設定
<Route
     path=“/list"
     getComponent={(location, callback) => {
         (require as any).ensure([], () => {
             callback(null, require("./List"))
          }, "List")
      }}
/>
  • wepackの設定
output: {
     path: outputPath,
     filename: "[name].js”,
     chunkFilename: "[name].js"
}

対応状況

ServiceWorkerに関してはまだ非対応ブラウザも多いですが、フォールバックが可能な設計になっているため、現段階で使用可能な技術です。あまりにキャッシュに頼った設計にしてしまうと、非対応ブラウザとのパフォーマンス差が大きくなってしまうため注意が必要です。

まとめ

PRPLパターンを実装する上で必要な技術スタックと設計についてまとめました。dev.toはPRPLライクな実装に加えてレンダリングのチューニングやInstantClick+SSRを利用した静的コンテンツキャッシュにより高速な遷移を実現しています。Instantly Fastを実現するためにはサービスの設計段階からパフォーマンスを考慮しておく必要がありそうです。

参考

PRPLパターン

HTTP/2

ServiceWorker

Golangの環境をつくった(goenv+ghq+peco)

goの開発環境を整えた際のメモです。

goenvでgoをインストール

golangのバージョンを管理するためにgoenvを導入しました。direnvと併用してプロジェクトごとに環境を分けることも可能ですが今回はgoenvのみをセットアップします。

GOPATHを設定する

goのワークスペースとなるGOPATHを設定します。デフォルトでは$HOME/goが設定されているようですが、go以外の作業もこちらで行う場合は他の名前にしておいた方が良さそうです。なぜgo以外の作業を考慮するかですが、後述するリポジトリ管理方法はgo開発に限らず有用であるためです。

ghq

goではgo getで依存ライブラリなどを取得するのが主流となっていますが、その場合GOPATH以下にgitのリポジトリがどんどん増えていくことになります。そこでリポジトリの管理を簡単にするためにghqを導入します。ghqはgo製のツールでgo getした時と同じ形でリポジトリを管理できます。デフォルトでは.ghq/以下で管理されているため管理するパスをGOPATHに合わせましょう。ghqの管理するパスを変更するには.gitconfigに以下のように設定を追加します。

[ghq]
     root = /Users/username/go/src

peco

ci上でテキストをインタラクティブにフィルタリングすることができます。前述のghqと連携させることで快適にリポジトリ間を行き来することができます。ghq listの結果をpecoに渡し、pecoで選択したリポジトリにcdするようにaliasを設定します。

alias g='cd $(ghq root)/$(ghq list | peco)'

エディタ

JetBrain製のGoLandを使用しています。IDE自体は割りと新しいのですがIntelliJプラットフォーム向けのPluginが使用できるため使用できるPluginの品質が高いのが魅力です。

余談ですが元々の名前はGogLandなので情報を検索する場合はGogLandで検索すると多少マシになるかもしれません。

GoLand: Capable and Ergonomic Go IDE by JetBrains

参考文献

DNSの仕組みと調査方法について

ネットワーク インフラ

仕事で外部のエンジニアに依頼したドメイン移行が正しく動作していなかったため、良い機会と思いDNSについて調べました。

名前解決の方法

そもそも名前解決とは何かというと、ドメインとIPアドレスを紐付けることです。手法として以下の2つが上げられます。

  • /etc/hostsに直接対応を記述する方法
  • /etc/resolve.confにDNSサーバーのIPアドレスを記述し、問い合わせる方法

今回はDNSサーバーによる名前解決について説明していきます。

DNSによる名前解決

ドメインツリーによる負荷分散

全世界に無数に存在するドメインの解決を一台のネームサーバーで担当するのは不可能です。そこでDNSでは下記のように、各階層に意味を持たせ、下位のドメインを管理させることで分散型の構造を構築しています。

f:id:sue71:20171121143038p:plain
ドメインツリー

キャッシュサーバーによる高速化

クライアントからDNSサーバーに対してドメインを問い合わせる場合、実際には直接情報(レコード)を保存しているサーバー(=コンテンツサーバー)に問い合わせるのではなく、それぞれのコンテンツサーバーとのやり取りを仲介するサーバー(=キャッシュサーバー)を介して行われます。

f:id:sue71:20171121152115p:plain
DNS解決の流れ

  1. クライアントからキャッシュサーバーへ問い合わせを開始する
  2. キャッシュサーバーがルートサーバーへ問い合わせる
  3. ルートサーバーからjpを管理するネームサーバーのアドレスが返却される
  4. jpを管理するネームサーバーに問い合わせる
  5. example.jpを管理するネームサーバーのアドレスが返却される
  6. example.jpを管理するネームサーバーへ問い合わせる
  7. example.jpのIPアドレス(Aレコード)が返却される

上図のようにルートサーバーから順に問い合わせていくのが基本的な流れですが、毎回この手順を踏むのでは速度面のロスがあるので、キャッシュサーバーは一度取得したレコードを一定期間保存し、キャッシュが存在している場合にはすぐさまクライアントに応答します。

f:id:sue71:20171121143044p:plain
キャッシュが存在している場合

キャッシュの生存期間としてTTLが用いられ、時間を超過すると再度権威サーバーへと問い合わせます。

プライマリ/セカンダリDNSによる冗長化

コンテンツサーバーは普通複数台存在します。プライマリ/セカンダリDNSと呼ばれ、プライマリDNSがなんらかの理由で応答しない場合にセカンダリDNSを参照します。セカンダリDNSはプライマリDNSのレコードをコピーして保持するため常に同期された状態になりますが、プライマリDNSのレコードを更新する際にシリアルナンバーを更新してセカンダリDNSに更新されていることを伝える必要があります。(異なった仕様のものもあるようです)

f:id:sue71:20171121143047p:plain
プライマリDNSとセカンダリDNS

digで名前解決してみる

digコマンドを使用して実際に名前解決してみます。nslookupコマンドでもIPアドレスを引くことは出来ますがdigコマンドの方がより詳細に情報を取得できます。 (他にもいくつか挙動が異なる点がありますが割愛します)

>>dig google.com

; <<>> DiG 9.8.3-P1 <<>> google.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 19537
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

;; QUESTION SECTION:
;google.com.               IN         A

;; ANSWER SECTION:
google.com.            186        IN         A          172.217.26.46

;; AUTHORITY SECTION:
google.com.            55214      IN         NS         ns3.google.com.
google.com.            55214      IN         NS         ns4.google.com.
google.com.            55214      IN         NS         ns2.google.com.
google.com.            55214      IN         NS         ns1.google.com.

;; ADDITIONAL SECTION:
ns1.google.com.        39695      IN         A          216.239.32.10
ns2.google.com.        39695      IN         A          216.239.34.10
ns3.google.com.        39695      IN         A          216.239.36.10
ns4.google.com.        39695      IN         A          216.239.38.10

;; Query time: 3 msec
;; SERVER: 192.168.2.1#53(192.168.2.1)
;; WHEN: Mon Nov  6 14:52:59 2017
;; MSG SIZE  rcvd: 180

各出力項目について

重要な出力について説明していきます。

status

名前解決の状態に関する項目です。上記出力ではNOERRORとなっているため、正常に名前解決が行われたことを意味します。 他にはNXDOMAINなどが表示されることがありますが、この場合は指定したドメインが存在しないことになります。

flags

応答の意味が表示されています。それぞれ下記の意味を示しています。上記応答はqr rd raとなっているため、サーバーからの応答で、なおかつキャッシュサーバーによる応答であり、キャッシュサーバーは再帰的問い合わせに対応している、ということがわかります。

  • aa: コンテンツサーバーからの応答であることを示します
  • qr: サーバーからの応答であることを示します。DNSでの名前解決では必ずこのフラグが付いています。
  • rd: 再帰的問い合わせの結果であることを示します
  • ra: 再帰的問い合わせが可能であることを示します

ANSWER SECTION

問い合わせに対するレスポンスになります。google.comのIPアドレスが得られている事がわかります。二列目の値が残りのTTLになります。このTTLが切れた場合に再度コンテンツサーバーに問い合わせることになります。

google.com.            186        IN         A          172.217.26.46

AUTHORITY SECTION

コンテンツサーバー(権威サーバー)のドメイン情報が表示されています。この中から１つが選択され、再帰的に問い合わせが行われます。

google.com.            55214      IN         NS         ns3.google.com.
google.com.            55214      IN         NS         ns4.google.com.
google.com.            55214      IN         NS         ns2.google.com.
google.com.            55214      IN         NS         ns1.google.com.

ADDITIONAL SECTION

付加情報が表示される項目です。ネームサーバーが返却された場合、ネームサーバーのIPアドレスなどが付加情報として返却されます。

ns1.google.com.        39695      IN         A          216.239.32.10
ns2.google.com.        39695      IN         A          216.239.34.10
ns3.google.com.        39695      IN         A          216.239.36.10
ns4.google.com.        39695      IN         A          216.239.38.10

digの使い方いろいろ

実際にどのような使い方があるのかを、今回調査に使用したものを中心に紹介します。

非再帰的問い合わせ

通常digコマンドでは再帰的に問い合わせが行われていますが、+norecオプションを付加することで、たらい回す先のDNSサーバーを返すようになります。

>> dig google.com +norec

; <<>> DiG 9.8.3-P1 <<>> google.com +norec
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 42047
;; flags: qr ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

...

flagsからrdの項目が消えていることがわかります。

問い合わせるネームサーバーを指定する

@DNSサーバーアドレスを使用することで、ネームサーバーを直接指定して名前解決を行うことができます。またキャッシュサーバーではなくコンテンツサーバーを指定した場合、再帰的問い合わせを行うことはできないので、自身が管理するレコードのみを返すことになります。

>> dig google.com @ns1.google.com

; <<>> DiG 9.8.3-P1 <<>> google.com +norec @ns1.google.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 14958
;; flags: qr aa; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;google.com.               IN         A

;; ANSWER SECTION:
google.com.            300        IN         A          172.217.26.46

;; Query time: 75 msec
;; SERVER: 216.239.32.10#53(216.239.32.10)
;; WHEN: Mon Nov 20 19:50:46 2017
;; MSG SIZE  rcvd: 44

flagsにaaと表示されているのがわかります。

再帰的問い合わせの状況を確認する

+traceオプションを付加することで、再帰的問い合わせの状況を追うことができます。浸透状況を疑う場合はこのコマンドを実行すると良さそうです。 下記出力ではルートサーバーから順に問い合わせている状態が確認できます。

>> dig google.com +trace

; <<>> DiG 9.8.3-P1 <<>> google.com +trace
;; global options: +cmd
.                  152273     IN         NS         f.root-servers.net.
.                  152273     IN         NS         l.root-servers.net.
.                  152273     IN         NS         e.root-servers.net.
.                  152273     IN         NS         j.root-servers.net.
.                  152273     IN         NS         d.root-servers.net.
.                  152273     IN         NS         b.root-servers.net.
.                  152273     IN         NS         g.root-servers.net.
.                  152273     IN         NS         i.root-servers.net.
.                  152273     IN         NS         h.root-servers.net.
.                  152273     IN         NS         c.root-servers.net.
.                  152273     IN         NS         a.root-servers.net.
.                  152273     IN         NS         k.root-servers.net.
.                  152273     IN         NS         m.root-servers.net.
;; Received 492 bytes from 192.168.2.1#53(192.168.2.1) in 10 ms

;; Truncated, retrying in TCP mode.
com.               172800     IN         NS         l.gtld-servers.net.
com.               172800     IN         NS         b.gtld-servers.net.
com.               172800     IN         NS         c.gtld-servers.net.
com.               172800     IN         NS         d.gtld-servers.net.
com.               172800     IN         NS         e.gtld-servers.net.
com.               172800     IN         NS         f.gtld-servers.net.
com.               172800     IN         NS         g.gtld-servers.net.
com.               172800     IN         NS         a.gtld-servers.net.
com.               172800     IN         NS         h.gtld-servers.net.
com.               172800     IN         NS         i.gtld-servers.net.
com.               172800     IN         NS         j.gtld-servers.net.
com.               172800     IN         NS         k.gtld-servers.net.
com.               172800     IN         NS         m.gtld-servers.net.
;; Received 824 bytes from 192.5.5.241#53(192.5.5.241) in 13 ms

google.com.            172800     IN         NS         ns2.google.com.
google.com.            172800     IN         NS         ns1.google.com.
google.com.            172800     IN         NS         ns3.google.com.
google.com.            172800     IN         NS         ns4.google.com.
;; Received 164 bytes from 192.54.112.30#53(192.54.112.30) in 152 ms

google.com.            300        IN         A          172.217.27.78
;; Received 44 bytes from 216.239.34.10#53(216.239.34.10) in 38 ms

ルートサーバーから順に問い合わせている様子がわかります。

プライマリDNSサーバーを確認する

soaをオプションとして付加することで、プライマリDNSサーバーを調べることができます。

>> dig google.com soa

; <<>> DiG 9.8.3-P1 <<>> google.com soa
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 47193
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 4, ADDITIONAL: 4

;; QUESTION SECTION:
;google.com.               IN         SOA

;; ANSWER SECTION:
google.com.            60         IN         SOA        ns1.google.com. dns-admin.google.com. 176366135 900 900 1800 60

;; AUTHORITY SECTION:
google.com.            151698     IN         NS         ns3.google.com.
google.com.            151698     IN         NS         ns4.google.com.
google.com.            151698     IN         NS         ns1.google.com.
google.com.            151698     IN         NS         ns2.google.com.

;; ADDITIONAL SECTION:
ns1.google.com.        324498     IN         A          216.239.32.10
ns2.google.com.        324498     IN         A          216.239.34.10
ns3.google.com.        324498     IN         A          216.239.36.10
ns4.google.com.        324498     IN         A          216.239.38.10

;; Query time: 37 msec
;; SERVER: 192.168.2.1#53(192.168.2.1)
;; WHEN: Tue Nov 21 11:48:38 2017
;; MSG SIZE  rcvd: 210

ns1.google.comがプライマリDNSサーバーであることがわかります。

TTLと浸透時間について

ドメインの移行が上手く行っていない際に「浸透時間が〜」という話を良く耳にしますが、基本的にはTTLを正しく設定していれば問題ないようです。 具体的には下記のような手順で移行することで、短時間でドメインの移行を完了することができます。

  1. 現在のTTLを確認する。例えば86400(24時間)と設定されていると仮定します。
  2. 移行前にTTLを300(5分)に設定します。
  3. 現在のTTLが86400となっているため、24時間以上の時間を置きます。
  4. キャッシュサーバーに保存されるTTLが300になっているはずなのでレコードの更新を行います。(TTLは長い時間を設定しても問題ありませんが、ミスが起きたときのために短い時間を設定しておくのが良いです)

今回の件で調査したこと

最後に今回問題を調査するにあたって、どのように問題解決に至ったかをメモしました。

キャッシュの確認

まず、キャッシュサーバーが古いドメインを返しているのではと思い、+traceオプションを使用して経路を確認しました。レコードが登録されているであろうネームサーバーまでは到達していましたが、最終的に到達するドメインが古いものになっている状態でした。しかしTTLには十分短い時間が設定されていたため、TTL設定の不備では無さそうです。

プライマリDNSの確認

次にsoaオプションを使用して到達している複数のネームサーバーの中からプライマリDNSを確認します。プライマリDNSがわかったので直接指定して確認したところ、そちらの方では新しいドメインに向いていました。そこでプライマリDNSとセカンダリDNSの同期が上手くなされていないのではと思い、担当者に調査をお願いした所、プライマリDNSのシリアルナンバーを更新していなかったことがわかりました。

まとめ

DNSの仕組みと問題が起きた際の調査方法について説明しました。DNSの仕組みを理解していればある程度問題が予測できそうです。

参考

LU分解を実装してみた

線形代数 アルゴリズム Javascript

今日は連立方程式の解法などに用いられるLU分解についてです。

LU分解とは

とある正方行列Aに対して以下のような等式が成り立つ場合を考えます。

 Ax = B

このとき A を L(下三角行列)とU(上三角行列)に分解すると三角化された行列の計算を2回行えば 解を得られることになるので計算が簡単になるというもの。

 A = LU

{ 
L = \begin{bmatrix} 
    1 & 0 & 0 & 0 \\\
    \vdots & 1 & 0 & 0 \\\ 
    \vdots & \vdots & 1 & 0 \\\ 
    l_{n1} & l_{n2} & \ldots & 1
\end{bmatrix}
}

{ 
U = \begin{bmatrix} 
    u_{11} & u_{12} & \ldots & u_{1n} \\\
    0 & u_{22} & \ldots & u_{2n} \\\ 
    0 & 0 & \ddots & \vdots \\\ 
    0 & 0 & 0 & u_{nn}
\end{bmatrix}
}

LU分解のメリット

では一体どう簡単になるかという話ですが

 Ax = B
 LUx = B
 Ly = B
 Ux = y

と変形すると結局三角行列の方程式を２つ計算すればxが求められることになります。例えば二元連立方程式の場合



\begin{bmatrix} 
    1 &  0 \\\ 
    l_{21} & 1 
\end{bmatrix}
\begin{bmatrix} 
    y_1 \\\ 
    y_2
\end{bmatrix}
=
\begin{bmatrix} 
    b_1 \\\ 
    b_2
\end{bmatrix}


 
\begin{bmatrix} 
    u_{11} & u_{12} \\\ 
    0 & u_{22}
\end{bmatrix}
\begin{bmatrix} 
    x_1 \\\ 
    x_2
\end{bmatrix}
=
\begin{bmatrix} 
    y_1 \\\ 
    y_2
\end{bmatrix}

となるため、自明なものから順に計算すれば簡単に求めることができます。

LU分解の過程について

 A = LU



\left(
    \begin{array}
      a_{11} & a_{12} & \ldots & a_{1n} \\
      a_{21} & a_{22} & \ldots & a_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      a_{n1} & a_{n2} & \ldots & a_{nn}
    \end{array}
\right)

=

\left(
    \begin{array}
      l_{11} & l_{12} & \ldots & l_{1n} \\
      l_{21} & l_{22} & \ldots & l_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      l_{n1} & l_{n2} & \ldots & l_{nn}
    \end{array}
\right)
\left(
    \begin{array}
      u_{11} & u_{12} & \ldots & u_{1n} \\
      u_{21} & u_{22} & \ldots & u_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      u_{n1} & u_{n2} & \ldots & u_{nn}
    \end{array}
\right)




\left(
    \begin{array}{c|ccc}
      a_{11} & a_{12} & \ldots & a_{1n} \\
\hline
      a_{21} & a_{22} & \ldots & a_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      a_{n1} & a_{n2} & \ldots & a_{nn}
    \end{array}
\right)
=
\left(
    \begin{array}{c|ccc}
      l_{11} & l_{12} & \ldots & l_{1n} \\
\hline
      l_{21} & l_{22} & \ldots & l_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      l_{n1} & l_{n2} & \ldots & l_{nn}
    \end{array}
\right)
\left(
    \begin{array}{c|ccc}
      u_{11} & u_{12} & \ldots & u_{1n} \\
\hline
      u_{21} & u_{22} & \ldots & u_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      u_{n1} & u_{n2} & \ldots & u_{nn}
    \end{array}
\right)


 
\begin{eqnarray}

\left( \begin{array}{c|c}
   a_{11} & a_1^T \\
   \hline
   a_1 & A_1 \\
\end{array}\right)

&=&

\left( \begin{array}{c|c}
   1 & 0 \\
   \hline
   l_{1} & L_1 \\
\end{array}\right)

\left( \begin{array}{c|c}
   u_{11} & u_1^T \\
   \hline
   0 & U_1 \\
\end{array}\right)
\\
&=&

\left( \begin{array}{c|c}
   u_{11} & u_1^T \\
   \hline
   l_1u_{11} & l_{1}u_1^T + L_1U_1 \\
\end{array}\right)

\end{eqnarray}

のように分解して計算すると、恒等式の関係より

 u_{11} = a_{11}
 u_1^T = a_1^T
 l_1 = a_1 / u_{11}
 A_1 = l_1u_1^T + L_1U_1

が成り立ちます。ここで A_1 - l_{1}u_1^T を新たに Aとすることで、同様の操作を繰り返すことができます。つまりn次正方行列を仮定するとn回繰り返すことで全てLU成分が分かることになります。

gist.github.com

計算量について

LU分解までの処理はO(n3)になるため、一度だけ方程式を解く場合はガウスの消去法などと変わりありません。 ガウスの消去法は右辺も処理する必要がありますが、LU分解は一度分解した結果を使いまわせるのがメリットです。 右辺の値を変更して何度もLUを再利用する場合に利点がありそうです。

まとめ

LU分解を自前で実装する方法とメリットについて説明しました。 次回は単体法について説明したいと思います。

参考

Generatorと非同期処理

今日はes6の仕様であるGeneratorについてです。

es6でカスタムイテレータを作る (Iterator, Iterable, Generator) - embryo

で簡単に紹介しましたが、今回はGeneratorで非同期処理を扱ってみたいと思います。

co で非同期処理

GitHub - tj/co: The ultimate generator based flow-control goodness for nodejs (supports thunks, promises, etc)

coとはGeneratorを利用して非同期処理を同期的に記述することを目的としたライブラリです。 下記のように一連の非同期処理を同期的に実行できるため、処理をシンプルに記述できる他、同一スコープ内で非同期処理の結果を共有することも可能になります。

function asyncTask(value) {
     return new Promise(resolve => {
         setTimeout(() => {
              resolve(value);
         }, 1000)
     });
}

co(function *() {
     let result = yield asyncTask(100)
     console.log(result);
})

今回はこの実装を参考にしつつ、簡易な方法で実装していきます。

普通にGeneratorを使う

まずGeneratorを素直に使用する方法です。Generatorはnextを持っているため、このnextを非同期処理の完了時に呼び出すことで 非同期処理を順次実行することができそうです。

gist.github.com

この場合Generatorを処理の外で実行する必要がある他、Generatorを仕様側が知っている必要があります。そこで次の実装ではGeneratorを意識せずとも実行できるように書いてみます。

Generatorを内部で実行する

gist.github.com

Generatorを内部で実行する方法です。Generatorの引数にcallbackを引数として渡しており、実行側では任意のタイミングでcallbackを実行すればよいため、generatorを意識せずに使用できます。しかしこの場合仕様側はコールバックを順次呼びだす必要があるため、本質的には非同期処理的な書き方と言えます。

Promiseを使用する

gist.github.com

iteratorのresult.doneがtrueを返すまで、PromiseのonFullfilledが呼ばれる度にgenerator#nextを再帰的に呼び出します。仕様側はGeneratorやコールバックを意識すること無く、かつ同期的に非同期処理を実行することが出来るようになりました。 前述したcoも仕組みとしては大体同じです。(coではエラーハンドリングなども考慮されていますが今回は説明のため簡易の実装にとどめています)

おまけ

ちなみに現在仕様策定中の async, await を用いれば coのようなライブラリに頼らずとも標準で上記のような処理を書くことが出来ます。

https://tc39.github.io/ecmascript-asyncawait/

async function () {
     console.log(await new Promise().resolve(100));
     console.log(await new Promise().resolve(200));
     console.log(“complete”);
}

/*
100
200
complete
*/

参考