Yarn(pkg) はなぜ速いのか気になったのでソースコードを読んでみた

そもそもどれくらい速いのか？

依存が多そうな sails で比較してみます。

{
  "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製の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で覆われています。

  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はこちらに定義してありますが、promiseをたくさん並べて並列に処理するようにするラッパーです。この実装は他の参考になりそうです。

promise.queueはソースコードのいたるところで使われており、yarnができる限り多く並列化していることがわかります。

キャッシュ処理

並列で処理されるfetch関数内では、まずキャッシュの確認に行きます。
キャッシュはMacだと ~/Library/Caches/Yarn/ 以下に保持されています。config.generateHardModulePath によりpackage, versionに対して一意のパスを発行し、この場所を確認しに行きます。ディレクトリ内に.yarn-metadata.jsonがあればその情報を取得し処理を終えます。

  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) {
      ...
    }
  }

{
  "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しています。

        req.pipe(validateStream); // 一旦バリデータに流す

        validateStream
          .pipe(fs.createWriteStream(tarballStorePath)) // tgzのままファイルに書き込む
          .on('error', reject);

        validateStream
          .pipe(extractorStream) // 解凍処理のstreamに流す
          .on('error', reject);

npmではダウンロードし終わってから、再度ファイルを読み込んで解凍しており、それに比べて時間短縮できそうです。

リトライ処理

ダウンロード処理はrequest-manager.jsに移譲されています。
この中で各リクエスト処理はqueueで管理されており、新しいリクエストを受け付けるとまずqueueにpushします。running数に余裕があれば、queueからshiftした処理を実行します。

  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されます。
リトライ処理はネットワークの回復を期待して、3秒間のtimeoutの後に実行されます。

npmの実装は？

今回比較のためにnpmに関してもソースコードを読みましたが、npmにもキャッシュ機構や、並列処理はあります。フロー制御にslideというライブラリを多用しており、これに依存しすぎているように感じます。関数呼び出しのネストが非常に深く、その辺りも遅さの原因のようです。

お世辞にも読みやすいコードとは言い難く、読むのに時間がかかりました。。npmはそこそこ歴史があるので次第に複雑になっていったのでしょう。Facebookの人たちが一から書きたくなる心情も理解できました。

結論

今回読んだ部分では特に驚くべきような実装があるわけではなく、やるべきことをきちんと綺麗に実装しているという印象を受けました。
Yarnが速いというよりもnpmが遅いというべきかもしれません。
どの部分が効いて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となっています。