1. fmy

    Posted

    fmy
Changes in title
+Yarn(pkg) はなぜ速いのか気になったのでソースコードを読んでみた
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,199 @@
+
+## そもそもどれくらい速いのか?
+依存が多そうな sails で比較してみます。
+
+```package.json
+{
+ "dependencies": {
+ "sails": "0.12.11"
+ }
+}
+```
+
+実行環境は以下。
+
+```
+$ node -v
+v6.9.1
+$ npm -v
+v4.0.3
+$ yarn -V
+v0.17.9
+
+$ rm -rf ~/.npm ~/.yarn ~/Library/Caches/Yarn # キャッシュなどを削除
+```
+
+実行結果。
+
+```
+$ time npm install
+...
+npm install 34.90s user 10.77s system 103% cpu 44.206 total
+
+$ rm -rf node_modules
+$ time yarn install
+...
+yarn install 12.26s user 7.28s system 71% cpu 27.494 total
+```
+
+およそ **1.6倍速い** という結果になりました。
+キャッシュが存在する2回目以降は更に速くなり、およそ **4.5倍** になります。
+
+```
+$ rm -rf yarn.lock node_modules
+$ time yarn install
+...
+yarn install 4.97s user 1.23s system 100% cpu 6.159 total
+```
+
+今回、yarnはなぜ速いかを探ってみたいと思います。
+
+## 公式の説明
+速度に関する部分だけ抜き出してみます。
+
+- **オフラインモード**
+ - 一度ダウンロードした package はキャッシュされ二度目はダウンロードされない
+- **ネットワークパフォーマンス**
+ - 並列ダウンロード対応
+ - 更にリソースを最適化する様になっている
+
+
+実際にソースコードを読んで、この辺りの処理を追ってみました。
+
+## ソースコードリーディング
+
+Facebook製のyarnはやはりFacebook製のAlt-JSであるFlowにて書かれています。
+
+
+`yarn install` コマンドのワークフローは以下のようになっています。
+https://github.com/yarnpkg/yarn/blob/0.17-stable/src/cli/commands/install.js
+
+- install
+ - fetchRequestFromCwd : cwdのファイルからリクエストする情報を取得
+ - resolver : 依存性を解決
+ - flatten : flattenオプション時に平滑化作業を行う
+ - fetcher : パッケージのダウンロード
+ - compatibility : OSやnodeのバージョンとの互換性をチェック
+ - linker : Cacheディレクトリからnode_modules以下にコピー
+ - script : post-installなどのscriptを実行
+
+一番速度に関係してそうなfetcherについて見てみましょう。
+
+### fetcher
+
+package-fetcher.jsのinitを見てみます。
+パッケージ一覧を取得後、コンソール表示したら、その後の処理はpromise.queueで[覆われて](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/package-fetcher.js#L79-L110)います。
+
+```javascript:package-fetcherのinit関数
+ async init(): Promise<void> {
+ const pkgs = this.resolver.getPackageReferences(); // パッケージ一覧を取得
+ const tick = this.reporter.progress(pkgs.length); // コンソール表示
+
+ await promise.queue(pkgs, async (ref) => {
+ const res = await this.maybeFetch(ref); // 実際の取得
+ ...
+ });
+ }
+```
+
+
+promise.queueは[こちら](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/promise.js#L48-L87)に定義してありますが、promiseをたくさん並べて並列に処理するようにするラッパーです。この実装は他の参考になりそうです。
+
+promise.queueはソースコードのいたるところで使われており、yarnができる限り多く並列化していることがわかります。
+
+#### キャッシュ処理
+
+並列で処理されるfetch関数内では、まず。
+キャッシュはMacだと ~/Library/Caches/Yarn/ 以下に保持されています。[config.generateHardModulePath](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/config.js#L248-L269) によりpackageに対して一意のパスを発行し、この場所を確認しに行きます。ディレクトリ内に`.yarn-metadata.json`があればその情報を取得し処理を終えます。
+
+```javascript:package-fetcherのfetch関数
+ async fetch(ref: PackageReference): Promise<FetchedMetadata> {
+ const dest = this.config.generateHardModulePath(ref); // キャッシュディレクトリ発行
+ ...
+ const fetcher = new Fetcher(dest, remote, this.config);
+
+ if (await this.config.isValidModuleDest(dest)) { // キャッシュの存在を確認
+ return this.fetchCache(dest, fetcher); // キャッシュのメタデータを取得
+ }
+ ...
+ try {
+ return await fetcher.fetch(); // キャッシュがない場合リモートから取得
+ } catch (err) {
+ ...
+ }
+ }
+```
+
+```.yarn-metadata.json
+{
+ "artifacts": [],
+ "remote": {
+ "resolved": "https://registry.yarnpkg.com/async/-/async-2.1.2.tgz#612a4ab45ef42a70cde806bad86ee6db047e8385",
+ "type": "tarball",
+ "reference": "https://registry.yarnpkg.com/async/-/async-2.1.2.tgz",
+ "hash": "612a4ab45ef42a70cde806bad86ee6db047e8385",
+ "registry": "npm"
+ },
+ "registry": "npm",
+ "hash": "612a4ab45ef42a70cde806bad86ee6db047e8385"
+}
+```
+
+もし存在しない場合は、実際に取得しに行きます。
+fetcherはgit, tarballなどタイプごとに実装されており、その各クラスのfetch関数が呼ばれます。tarballの場合、ダウンロードのレスポンスストリームをtgzファイルとして書くWritableStreamと解凍するTransformの[2つにpipeして](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/fetchers/tarball-fetcher.js#L168-L176)います。
+
+```javascript:tarball-fetcherのfetchFromExternal関数
+ req.pipe(validateStream); // 一旦バリデータに流す
+
+ validateStream
+ .pipe(fs.createWriteStream(tarballStorePath)) // tgzのままファイルに書き込む
+ .on('error', reject);
+
+ validateStream
+ .pipe(extractorStream) // 解凍処理のstreamに流す
+ .on('error', reject);
+```
+
+npmではダウンロードし終わってから、再度ファイルを読み込んで解凍しており、それに比べて時間短縮できそうです。
+
+#### リトライ処理
+ダウンロード処理は[request-manager.js](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/request-manager.js)に移譲されています。
+この中で各リクエスト処理はqueueで管理されており、新しいリクエストを受け付けるとまずqueueに[push](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/request-manager.js#L211)します。running数に余裕があれば、queueからshiftした処理を[実行](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/request-manager.js#L416-L425)します。
+
+```javascript:request-fetcherのshiftQueue関数
+ shiftQueue() {
+ if (this.running >= this.max || !this.queue.length) {
+ return; maxを超えているか、queueが空ならreturn
+ }
+
+ const opts = this.queue.shift(); // 先頭を取得
+
+ this.running++;
+ this.execute(opts); // リクエスト実行
+ }
+```
+
+yarnはあちこちで並列処理されていますが、HTTPリクエストは全てここを通して行われているので、全体でのHTTPリスエスト並列処理数が管理できています。
+
+もしネットワークが切れなりなどしてリクエストが失敗した場合、5回以内は再度実行を試みるために[offlineQeueにpush](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/request-manager.js#L324-L340)されます。
+リトライ処理はネットワークの回復を期待して実行するまで[3秒間のtimeout](https://github.com/yarnpkg/yarn/blob/0.17-stable/src/util/request-manager.js#L290-L298)をとります。
+
+
+### npmの実装は?
+今回比較のためにnpmに関してもソースコードを読みましたが、npmにもキャッシュ機構や、並列処理はあります。フロー制御に[slide](https://github.com/npm/slide-flow-control)というライブラリを多用しており、これに依存しすぎているように感じます。関数呼び出しのネストが非常に深く、その辺りも遅さの原因のようです。
+
+お世辞にも読みやすいコードとは言い難く、読むのに時間がかかりました。。npmはそこそこ歴史があるので次第に複雑になっていったのでしょう。Facebookの人たちが一から書きたくなる心情も理解できました。
+
+## 結論
+今回読んだ部分では特に驚くべきような実装があるわけではなく、やるべきことをきちんと綺麗に実装しているという印象を受けました。
+どの部分が効いて1.6倍も速くなっているか定量的に調べるまではいきませんが、高速化のためのポイントがいくつか理解できました。
+また、promise.queueやrequest-managerなどの実装は参考になる部分が多く、他にも活用できそうです。
+
+また思わぬ形でFlowに触れる機会になりました。最初見たときはちょっと気持ち悪さがありましたが、慣れるとソースコードは追いやすいです。
+実際に書いてはないですが、悪くはなさそうです。
+
+### P.S.
+yarnからはFacebookの例のPATENTSファイルは削除されています。
+https://github.com/yarnpkg/yarn/commit/46e8be5a9b5e692ac9307a79342d0c1e03ffc3da
+
+CopyrightもFacebook, Inc.からYarn Contributorsに変更され、より公共性の高いOSSとなっています。