LoginSignup
24
16

More than 5 years have passed since last update.

@momoiroshikibu

ISUCON6の予選をNode.jsで突破する

Last updated at Posted at 2017-10-10

経緯

去年、ISUCONに参加してみました。少しの爪痕も残すことなく敗退しました。

Node.jsをチョイスしましたが、慣れないasync/awaitとすさまじいhtmlifyの前に、何もできずに終わりました。

で、今年のISUCON7でリベンジすべく、特訓を始めました。
いろいろと調べていると、こんな情報がありました。

ISUCON6 オンライン予選の利用言語比率

あれ、Node.jsで本戦に出場しているチームがない…
と思ったので、少し心に火がつきました。

目標

ISUCON6 本選出場者決定のお知らせを見る限り、90,214点を超えられれば良いらしい。
または、学生になれば良いらしい。でも、社会人学生じゃダメらしい。
ということで、90,214点を超えるのが目標。

参考

このまとめにあるブログエントリをめちゃ参考にさせて頂きました。
みなさまありがとうございます。

【更新終了】ISUCON6 オンライン予選 関連エントリまとめ
http://isucon.net/archives/48465813.html

あと、この環境にお世話になりました。ありがとうございます。
https://github.com/matsuu/vagrant-isucon

結果

まずは結果から。
これらの対応を全てやって、124,721まで到達しました。(ローカルのvagrant-standalone環境)
色々な改善策については予選に参加されたみなさんのブログエントリを参考にするのが良いと思います。
自分で発見したことは特にありません。N番煎じです。

やったこと

明確に分けるのは難しいですが、ざっくりNode.jsに関連する/しないで、こんな変更をしました。

Node.jsに関連するもの

  • Node.jsのバージョンをv8.5.0に。
    効果: ★☆☆☆☆
    難易度: ★☆☆☆☆

  • htmlifyを正規表現からトライ木に。
    効果: ★★★★★
    難易度: ★★★★★

  • Node.js <-> MySQL、Node.js <-> Redis はドメインソケットで。
    効果: ★★☆☆☆
    難易度: ★☆☆☆☆

  • initializeのタイミングでユーザーを全てRedisにキャッシュ。
    効果: ★★★★☆
    難易度: ★★★☆☆

  • 事前にHTMLをRedisにキャッシュしておく。
    効果: ★★★★★
    難易度: ★★★★☆

  • child_processをCPUのコア数(2)に合わせる
    効果: ★★★★★
    難易度: ★☆☆☆☆

  • EJSのテンプレートまわりの処理を改善。
    効果: ★★★★★
    難易度: ★★★★☆

Node.jsに関連しないもの

  • 遅いクエリの改善。特に一覧のアレ。
  • 静的ファイルをNginxで。基本304で。
  • istarを統合。
  • istarのデータ保存先はMySQLではなくRedisで。
  • その他いろいろ

対応とスコアの伸びを示せません。ゴメンナサイ。
なんとなくの感覚値でおすすめ度は★で示してみました。

最初はマメにメモっていたのですが、途中で面倒になってやめました。
そのうちまとめ直すかもしれません。
「行けたら行くわー」みたいなやつです。絶対やらないパターンですので、期待しないでください。

実感として、上記の対応の一つでも不足すると、予選を突破できない、そんな印象です。
少なくとも、効果が★4つ以上は必須っぽい。あとは対応の組み合わせ次第でなんとかなるかも。
検証していませんが、とても高い壁に感じました。
これらの対応を数時間で実現する方たち、すごすぎる。フリースタイルダンジョンすぎる。

ちなみに、いろいろとあって、期間としてはここまで3週間くらいかかっています。
「いろいろあって」は思うようにスコアが伸びなかったことに対する、ただの言い訳だと思ってください。

環境

環境はisucon6-qualifier-standaloneです。

MacBook Proの2017年モデルで、一番安いやつです。
あ、色はスペースグレイです。(スコアに関係ないか)

解説

Node.jsに関連する部分だけ少し補足していきます。少しだけです。
丁寧じゃない言い訳です。拙いレベルでも良いわけです。

Node.jsのバージョンをv8.5.0に

シンプルにただそれだけ、という感じです。
Nodebrewを使っています。いつもお世話になっております。

そんなに効果はありませんでしたが、なんとなく--tarboなどもつけています。
気分的に「あとはアプリを改修するしかない」となれます。言い訳ができなくなります。

あ、忘れていました。一つメリットがありました。
bin/run_iusdaではなく、bin/isudaを直接実行出来るようになります。
Node.jsのバージョンが上がるので、バベる必要が無くなります。

つまり、bin/run_isuda内でrequireされている、runkoaさんが不要になる。
そんなにスコアには影響しない感じがします。気持ちの問題という印象です。
ということで、isuda.js.serviceの内容もbin/isudaとします。

[Service]
WorkingDirectory=/home/isucon/webapp/js
EnvironmentFile=/home/isucon/env.sh
Environment=NODE_ENV=production

# Node.js v8.5.0
ExecStart = /home/isucon/.nodebrew/node/v8.5.0/bin/node /home/isucon/webapp/js/bin/isuda

htmlifyを正規表現からトライ木に。

本選出場者の方々は、トライ木というアルゴリズムで実装をしているようでした。
自分は知らなかったので、余裕で敗退しました。
このアルゴリズムを知らなかったので、"知らない前提"、つまり、トライ木の対応をせずに予選を突破するスコアを出そうとしていましたが、自分の頭では、避けられませんでした。
残念ながら、知らなければ予選敗退決定という感じです。ということで、トライしました。

やりたいことは任意のテキストに対してキーワードをマッチングし、それを置換するなので、
npmでtrieみたいなキーワードで探しました。

すると、keyword-trie-jsというライブラリが見つかりました。
が、使ってみると、ベンチ的にはfailしまくりでした。
あと、キーワードの追加、削除に対応していないようでした。

他にもいろいろと探してみましたが、欲しい機能を持つライブラリはありませんでした。残念。

なので、自分で書くことにしました。トライ木の主要機能はtrie-jsをベースにしました。
キーワードの追加/削除が出来たので、充分でした。
速度などは他のライブラリと比べていないので、不明です。
予選を突破するスコアを出すのが目標です。

Trie.prototypeオブジェクトを拡張し、replace関数を追加しました。
こんな感じの実装になりました。泥くさい感じですが、動いています。

  • 1文字ずつキーワードのプレフィックスにマッチするか確認
  • マッチしなければ置換しない
  • マッチしたら、次の文字を加え(2文字となる)、キーワードのプレフィックスにマッチするか確認
  • これを続け、キーワードの完全マッチがしたら、replacerとなる関数にキーワードを渡し、置換後の文字列を受け取る
  • この文字列をreplace関数の戻り値となる文字列に加える

こういう処理をずっと繰り返します。最長マッチや効率などは考えていません。
きっと、もっと洗練された処理になるのでしょう。

Trie.prototype.replace = function(text, replacer) {
    if (!text) return;
    const chars = text.split('');
    let newText = [];
    let phrase = '';
    for (let i = 0, l = chars.length; i < l; i++) {
        phrase += chars[i];

        if (this.lookup(phrase)) {
            newText.push(replacer(phrase));
            phrase = '';
            continue;
        }

        if (this.isPrefix(phrase)) {
            continue;
        }

        i = i - (phrase.length - 1)
        newText.push(phrase[0]);

        phrase = '';
    }
    return newText.join('');
}

これをこんな感じで呼び出しています。

const res = tree.replace(content, (keyword) => {
    const url = `/keyword/${RFC3986URIComponent(keyword)}`;
    return `<a href=${url}>${ejs.escapeXML(keyword)}</a>`;
});

EJSのテンプレートの対応を除くと、この対応だけで
30,000点から70,000くらいになりました。かなり良い感じです。

Node.js <-> MySQL、Node.js <-> Redis はドメインソケットで。

これだけ。思ったより効果ありという印象。

/etc/redis.conf

unixsocket /var/run/redis/redis.sock
unixsocketperm 700

routes/isuda.js

const cache = redis.createClient('/var/run/redis/redis.sock');

initializeのタイミングでユーザーを全てRedisにキャッシュ。

こんな感じでキャッシュします。シンプルにそれだけ。あとはそれを取り出すだけ。
ユーザーの追加/削除とかもやります。

const cacheCurrentUsers = async (db) => {
    const users = await db.query('SELECT * FROM user');
    for (let user of users) {
        const userJson = JSON.stringify(user);
        await cache.setAsync(`user-${user.id}`, userJson);
        await cache.setAsync(`user-${user.name}`, userJson);
    }
}

clusterモジュールで複数のプロセスを起動するので、何かのオブジェクトに突っ込んでおく、みたいなことは出来ません。(はじめにやって失敗…)
なので、Redisを使いました。予めdumpしておいても良いかもしれません。

ユーザーのidとnameをキーのサフィックスにしました。
ユーザーを取得する処理にはidをキーにする場合とnameをキーにする場合の2パターンがあるので。という単純な理由です。

事前にHTMLをRedisにキャッシュしておく。

手早くこんな感じで。一回このURIに対してリクエストしてRedisのキャッシュに入れておく。で、それをdumpしておきます。

SELECT * FROM entry order by idのSQLは*の部分をもう少し丁寧にしたらスコアが上がるかもしれません。やってません。

これで20000点から60000点くらいになった気がします。

router.get('generate_html_caches', async (ctx, next) => {
    const db = await dbh(ctx);
    const conn = await db.getConnection();

    const keywords = (await conn.query('SELECT keyword FROM entry ORDER BY CHARACTER_LENGTH(keyword) DESC'))
          .map((k) => k.keyword);
    keywords.forEach((keyword) => {tree.add(keyword)});

    const entries = await conn.query('SELECT * FROM entry order by id');
    for (let entry of entries) {
        await htmlify(entry.id, entry.description);
    }
    ctx.body = {
        'caches': entries.length
    }
});

child_processをCPUのコア数(2)に合わせる

こんな感じで。自分の環境だと2個でした。安いモデルなので。
ちなみに、テンプレートから展開したAzureの環境でも2個でした。
環境はわかっているので、整数でも良いかもしれません。

bin/isuda

if (cluster.isMaster) {
  var numChild = os.cpus().length;
  for (var i = 0; i < numChild; i++) {
    cluster.fork();
  }
}

EJSのテンプレートまわりの処理を改善。

これが一番盲点でした。

<%- include('/views/header.ejs') %>だったり、<%- include('/views/footer.ejs') %>のincludeの処理の度にfs.readFileSyncをしている…
つまり、リクエストの度にほぼ3回、テンプレートのファイル(*.ejs)をreadします。
(対象ページのテンプレート、ヘッダ、フッタの3つ)

これをキャッシュする(ファイルの読み込みを無くす)ことで、かなりスコアが上がります。
85,000点から124,721点までなりました。とても効果的です。
下の例のようにプレコンパイルしておいて、その関数をctx.bodyの結果とする感じです。

const ejs = require('ejs');
const ejsOption = {
    source: true,
    compileDebug: false,
    cache: true, // 大事
    root: path.resolve(__dirname, '../')
};

// util
const compileTemplate = (templateFileName) => {
    return ejs.compile(fs.readFileSync(path.resolve(__dirname, `../views/${templateFileName}.ejs`), 'utf-8'), ejsOption);
}

// compile
const indexRenderer = compileTemplate('index');
const authenticateRenderer = compileTemplate('authenticate');
const registerRenderer = compileTemplate('register');
const keywordRenderer = compileTemplate('keyword');

router.get('register', async (ctx, next) => {
    if (!await setName(ctx)) {
        return;
    }
    ctx.state.action = 'register';
    ctx.body = registerRenderer(ctx.state); // render
});

余談

スコアが70,000前後のときに、大人げなくAzure環境にてお金で解決を試みました。
が、1万点くらいしかアップしませんでした。やめたほうが良いと思います。

ちなみに、このときは1インスタンスに"ベンチマーカーとアプリが同居した状態"でした。

なので、ベンチマーカー用インスタンスを分離させて、アプリとベンチで1インスタンスずつとしました。
が、300点くらいしかアップしませんでした。やめたほうが良いと思います。

たいした金額でもないのに、無駄遣い感がすごいです。

感想

とても厳しい戦いだということがわかりました。
なんとか決勝に行きたい。

さいごに

Node.jsで参考実装してくださる方、ありがとうございます。


24
16
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
24
16