発明のための再発明

内部動作のような、プログラムを書くときの参考になることを書きます

yarnを使ってimportが解決されるまでを追う

yarn add から webpackがimportを解決するまでを追う

Javascriptでは、Yarnとwebpackを使うのが主流なので、それらがどのような動きをしているかを追った。

事前準備

動きを追うために以下を用意した

  1. コード
  2. Verdaccio

コード

コードの配置は以下

.  
├── build  
│   └── bundle.js  
├── node_modules  
│   ├── my-isarray  
│   ├── webpack -> ../../../.config/yarn/link/webpack  
│   ├── webpack-cli  
├── package.json  
├── src  
│   └── app.js  
├── webpack.config.js  
└── yarn.lock  

各ファイルの中身は、

  • my-isarray
console.log("test-isarray");  

export default function(obj) {  
    console.log("my-isarray is called");  
    return Array.isArray(obj);  
}  
  • src/app.js
import a from "my-isarray";  

(function() {  
    console.log("src************");  
})()  

a();  
  • webpack.config.js
module.exports = {  
  mode: "none",  
  entry: "./src/app.js",  
  output: {  
    filename: "bundle.js",  
    path: __dirname + "/build"  
  }  
}  

Verdaccio

プライベートnpm のレポジトリ用にVerdaccioを使った。
dockerが用意されているので、configを弄った後に自作のpackageを登録すれば完了する

Yarnとwebpackのコミットハッシュ

調査に使用したコードのハッシュ値は以下である

Yarn: c58bd58e029ab5a69d75742c6ae82aa96cef0140 (v1.11.0-0)
webpack: 5ade57451073ef0993379d2cc6b80d616e86ef5d (v4.19.0)

動きを追う

大まかな流れは画像の様になる

f:id:mrasu:20180923170303j:plain

yarn add

最初に、yarn addをしてnode_modulesに展開されるまでを追う

  1. npmからメタデータを取得する
    npmのAPIを使用して、hash値やバージョンなどの最新情報を取得する。
  2. npmから~/.cache/yarn/v2に保存
    メタデータと以前にダウンロードしたものが違うものであればtarballをダウンロードして、展開する。
    この時、直接 node_modules にダウンロードするのではなく、~/.cache/yarn/v2のような共通ディレクトリにダウンロードすることで、別プロジェクトが使うときにも使いまわせるようになっている。
  3. 対象のnode_modulesディレクトリへコピー
    ~/.cache/yarn/v2に保存したパッケージ内容を対象ディレクトリにコピーする。

webpackを使って対象パッケージを使用する

次に、webpackが"ビルド"として行っている「ファイルの結合」の流れを追う

  1. Parserを通して各ファイルの依存関係を発見する
    Acornを使用してパースしている。
    Acornの結果を基に、webpack内にあるParser.jsがフックポイントを作って回る。
    このフックポイントの一つがimportを通ったときに発火するようになっているので、発火した場所を見ることで各ファイルが依存したパッケージを知ることが出来る。
  2. Resolverが名前解決する
    enhanced-resolveという、デフォルトのResolverがwebpackから切り出されている。
    これを利用することで、各ファイルが依存しているパッケージをnode_modulesから選び出している。
  3. webpackに登録されたLoader,Pluginsを実行し、各ファイル・全体を変更する
  4. 結果を基にファイルをつなぎ合わせる

以上

以上で、yarnがパッケージをダウンロードしてwebpackがファイルに結合するまでの流れが追えた。

読んでいて思ったこと

Yarn

yarnでは、jestとflowを使用していて、「やはり、Facebook製」といった感じを出している。
やることを絞っているためか、コードは結構シンプルで読みやすい。
上に書いた事以外にも、ネストや重複した依存関係の解決があるのでそこはまた読んでみたい所

webpack

webpackはプラグインの仕組みを使っていて、他の人が勝手にプラグインを書いて好きに公開できるようになっている。
この仕組みはwebpackを下支えしている良い仕組みだと思う。
ただし、コードを見ると、制御できている人が居るのか疑問なレベルの複雑さを持っている。
読み慣れていないせいかもしれないが、コールバック地獄がかなり読みづらかった。
また、hooksという各PluginやLoaderに対するフックポイントをまとめた変数があるのだが、フックポイントが多すぎてどこがいつ影響するのかわかりづらい。
あと、デフォルトのプラグインがまとめてlib直下に送られているのは流石にどうかと思う・・・

Dynamo: Amazon’s Highly Available Key-value Store

はじめに

AmazonがDynamodbを紹介した論文を読んだ。
2007年のもので、NoSQLブームの走りとなったものだったと思う。
コンピュータ・サイエンス関係の「おすすめの論文」のようなもので、よくおすすめされるので読んでみたが、意外と面白かったので、面白かった場所に焦点を当てて書く。
ただし、現在は、AWSのサービスとして提供されていて機能追加も多いのでこの論文とは大きく異なると思われるので注意が必要。

Dynamodbとは

Amazonが開発したNoSQLで、高可用性KVS。
論文上では99.9995%のリクエスト返答成功率と、データロス無しという、数字を出している。

https://aws.amazon.com/jp/dynamodb/
を読むと、概要がわかりやすいだろう。

Dynamo で使われている技術 (4章)

4章では、主要技術を5つ挙げている。

  1. Consistent hasing
    データ分割のアルゴリズムとして、Consistent hashingを採用している。
    また、キーが偏らないように Virtual node を使い単一ホストに対する複数キーの設定を設定している。
    ただ、単純には行かなかったようで、後半で試行錯誤を書いている。

  2. Versioning
    Vector clockを採用し、順序が確定する場合には最新の情報を返す。
    更新要求が成功したからと言って、dynamoが更新された情報を返すわけではなく、古いデータを取得することが有りえる。
    そのため、同一データに対して同時に更新する可能性があり、不整合が発生しうる。その場合は復元を行う(後半に詳細が有る)
    さらに、vectorが大きくなるのを抑えるために、古い情報は捨てている。

  3. Sloppy quorum and hinted handoff
    (W: Writeが成功する時の最低ノード数) + (R: Read時のデータ取得対象ノード数) > (N: レプリケーションノード数)
    になるようにして、Quorumのようになっている。
    書き込み対象が落ちている場合は、別ノードにデータが書き込まれる。復旧したら、データを戻した後にデータを消す(hinted hand off)。
    ちなみに、W, Rのノード数を変えることで、個々のサービスの要求を満たすことが出来るようになっている。
    例えば6章に、商品情報や宣伝のサービスではW=N,R=1にして高速で動作するようにしているとしている。(更新が圧倒的に少ないのでこういう設定が可能)

  4. Anti-entropy using merkle tree
    Merkle tree を使うことによって差分を高速に発見し、そこだけデータ同期を行う

  5. Gossip based membership protocol and failure detection
    GossipでノードやConsistent hashのリング情報などを共有している
    Seedsというリング上の全てのノードを知っているノードがいて、全ノードがそれらに合わせるので、分断は起きない。

バージョン差異が見つかった場合の修復方法 (6章冒頭)

Versioningでバージョンの不整合があるので、それをどのように治すかという問題を解説している。
不整合に対する対応では、サービスの性質に応じて3種類の方法を用いている。

  1. クライアント(アプリ側)が独自のビジネスロジックで治す (例: カート情報)
  2. 最新の更新日付を持つバージョンを使用する (例: セッション情報)
  3. R=1,W=Nにして、そもそもバージョン差異に気づかないようにする。(例: 商品情報や宣伝のサービス)

ちなみに、全リクエスト中に複数バージョンが見つかった割合は

  • 0.00057%で2つのバージョン
  • 0.00047%で3つ
  • 0.00009%で4つ

と、少ない(6.3章)

Consistent hasingのキーの割当に用いた戦略について (6.2章)

Consistent hashは工夫が合ったようで、3種類の戦略を取ったらしい。
下に論文にある図を置く
f:id:mrasu:20180910002502j:plain

戦略1. ノードに対してランダムなtokenを割り当てて、token間のデータを各ノードが持つデータとする

Consistent hasingを素直に実装した初期の戦略。
ただ、この戦略には、以下の問題があった

  1. ノードが増えたときには必ずデータ移動が発生し、移動対象データの全スキャンが走るので重い
    それに対応するために、データ移動を優先度最低のバックグラウンドタスクとして、移動完了後にノードを追加するようにした。そのために、ノード追加の時間が長かった
  2. Merkle tree の再計算が必要
  3. データの存在するノードが変動する可能性が有るので、全体バックアップを取るのに苦労した

これら問題の本質は、

  1. データの分割箇所(partition)(上図の網掛け部分)の決定
  2. データを配置する配置ノード(上図のA,B,C)の決定

という選択を同時に変更してるところから発生している。
例えば、「リクエストが多いからノードを追加しよう」と思ってもデータの分割箇所の変更が発生していた。

戦略2. 事前にpartionを均等なQ個に分割し、partitionを配置するノードは後から割り当てる

バックアップやMerkle treeの問題は、ノードが保持するデータが変わるために発生する問題だったので、保持データが変わらないようにしている。
partition内のデータを保持するノードを決定する際には、リングの位置を表すtokenを各ノードに割り当てて、partitionに最も近いtokenを持つN個のノードへpartitionのデータが配置される。
これによって、

  • (戦略1で問題だった)partitionと配置ノードが同時に変わる問題を解決
  • partitionを動的に変えられる

という利点が有る。

戦略3. Q個の均等なpartionに分割し、各ノードに割り当てるpartitionも確定する

2番めの戦略を進めて、割り当てるpartitionのノードを固定している。
そのために、

  • ノードが無くなる場合には、消えたノードのpartitionを別のノードへ割り当てる
  • ノードを追加する場合には、既存のノードに割り当てられたpartitionを新規ノードに移動させる

となり、2で発生していた、ノードが保持するpartitionが変わる問題が解消された。
ちなみに、3つの戦略における負荷の偏りを測ると、3が最良で2が最悪となった。(2が遅い理由はみつからなかった)

3番目の戦略の良いところはデプロイが簡単になったところ。
簡単になった理由は、

  • partitionの範囲が固定されていてノードが保持するpartitionも固定されるおかげで、ノードのbootstrapや復元が早くなる (partitionの範囲が動的だとランダムアクセスになる)
  • アーカイブが簡単 (partitionの範囲が固定されるので)

ただし、ノード管理の手間は増えるという欠点が有る。

まとめ

以上、Dynamoの古い論文を読んだ。

BeyondCorp - A New Approach to Enterprise Security -

GitHubのを眺めていたら、ORYのoathkeeperを見つた。
これがGoogleが社内で使用している「BeyondCorp」を参考にしているということが書いてあったので、その論文を読んだ。

BeyondCorpとは

GoogleVPNの代わりに使用している、認証・認可のシステム。
人・デバイス・ネットワークなどを基に社内システムへのアクセス制御を行い、ホテルやカフェなどから、Google社内システムへのアクセスができるようになっている。
論文は何個か出されているが、読んだのは、BeyondCorp: A New Approach to Enterprise Security
また、GCPのサービスにもなっていて、Cloud Identity-Aware proxyという名前になっている

BeyondCorpの仕組み

図にすると、↓のような構成らしい f:id:mrasu:20180806003128j:plain

認証

HRのシステムと結びついてシングルサインオンをやっていると書いているが、具体的にはあまり書いていない。
Cloud Identity-Aware proxyでは、セキュリティキーというデバイスを使って二要素認証をしているので、同じようなものがあるはず。 (https://login.corp.google.com/?gnubby=0 を見ても、SecurityKeyの記載がある)

認可

権限制御のシステムは、AccessControlEngineという名前がついていて、

  • ユーザー
  • ユーザーの所属する組織
  • バイス
  • 場所

を基に権限を与えている。
例えば、バグトラッカーを使えるのは、フルタイム開発者が開発マシンから見ている時だけ。財務システムはファイナンスグループのフルタイムかパートタイムだけ。など、分けられている。
権限制御はサービス単位だけでなく、サービスの要素に対しても割り当てられる。バグトラッカーのバグ詳細のページを見る権限と、検索、更新する権限は別にすることが出来るらしい。
また、Googleのビル内からのアクセスかどうかとか、新しい場所からのアクセスかで認証レベルを変えているし、OSのパッチがあたっているかどうかでも変えているらしい。

VPNから、BeyondCorpへ移行するのは大変だったようで、後半はそれについて書いてある。
あと、各社内サービスへの入り口へのFQDNDNSで公開していると書いてある。これは、社外ネットワークを使っている以上、必要だろうという感じ。サービス本体の情報は社内DNSから引けるのかもしれない。