JavaScript
Go
Node.js
怪文書

非同期 IO について

非同期 IO について


おしながき

  1. C10K 問題 について
  2. 非同期 IO とは何か
  3. async-await
  4. 非同期 IO のこれから

1. C10K 問題 について


時は 2002 年


Web 勃興期


牧歌的時代の終わり


HTTP サーバ


10000 クライアントからの同時接続


どう実装するか


当時の Web サーバ

  • Apache
  • クライアント毎に 1 プロセス
  • クライアント毎に 1 スレッド

クライアント毎に 1 プロセス

  • 10000 プロセス も起動したら OS が死ぬ
  • CPU|メモリ が足りない
  • PID の上限
  • etc...

クライアント毎に 1 スレッド

  • 10000 thread も起動したら OS が死ぬ
  • CPU|memoryが足りない
  • thread数の上限
  • virtual memory の上限
  • etc...

これからの時代(2002年当時)

  • nginx
  • 複数の thread で複数の client を受け持つ
  • 非同期 並列 イベント駆動
    • 非同期: 非同期イベント駆動
    • 並列: 軽量スレッド


C10K 前後史


  • 1973: Actor(Scala, Erlang の起源)
  • 1977: future-promise
  • 1978: CSP(Go の起源)
  • 1983: C++
  • 1986: Erlang
  • 1990: Haskell 1.0
  • 1991: Concurrent ML

  • 1994: PHP, Java, python1, Perl5, Common Lisp
  • 1995: Apache, JavaScript, Ruby, Haskell 1.3(monad)
  • 1996: Shockwave Flash, Concurrent Haskell
  • 1997: IE4

  • 2000: libevent(poll|select)
  • 2001: POSIX AIO(POSIX 1003.1b), IE6
  • 2002: C10K 問題提議
  • 2003: libaio(Linux AIO, Linux2.6), Scala
  • 2004: nginx(AIO), Rails, Firefox1

  • 2005: gevent(eventlet), GoogleMap, F#
  • 2006: Firefox 2.0, jQuery1.0
  • 2007: libev, Clojure(STM), LINQ(C#3.0)
  • 2008: epoll (Linux 2.6.28), boost(1.35) asio , Task(C#4.0), node.js(libuv), Google Chrome
  • 2009: go, CoffeeScript, iPhone3GS, ReactiveX(C#5.0)

  • 2010: C#5.0(async)
  • 2011: java nio(jdk1.7), Kotlin, React, Deferred(jQuery1.5)
  • 2012: Elixir, TypeScript
  • 2013: Promise
  • 2014: Swift, Flux, asyncio(Python3.4)

C10K まとめ

  • 10000 コネクションさばきたい
  • 非同期や並列アーキテクチャが模索された時代があった

2. 非同期 IO とは何か


IO とは

  • Disk IO
  • Network IO
  • IO は CPU の時間に比べてとても遅い

IO の種類

  • 同期ブロッキング
  • 同期ノンブロッキング
  • 非同期ブロッキング
  • 非同期ノンブロッキング

同期ブロッキング

  • プロセスがカーネルにシステムコールする
  • プロセスはカーネルの返事を 待つ
  • プロセスのスレッドのプログラムカウンタは止まる
  • 例: read, write システムコール

同期ノンブロッキング

  • プロセスがカーネルにシステムコールする
  • プロセスはカーネルの返事を 待たない
  • プロセスは任意のタイミングで IO の状態をカーネルに問い合わせる(polling)
  • 例: O_NONBLOCK を指定した read, write, poll, select システムコール

非同期ブロッキング

  • プロセスはカーネルにシステムコールでIO処理をたくさん登録して返事を 待つ
  • カーネルは どれかが終わったら 返事する
  • 同期ブロッキングに比べてたくさんの IO 処理を同時に待てる (多重 IO)
  • ex. epoll システムコール

非同期ノンブロッキング

  • プロセスはカーネルにシステムコールをたくさん投げる
  • プロセスはカーネルからのシグナルが発生するまで他のことをする
  • シグナル処理は高コストという問題も
  • ex. POSIX AIO, Linux AIO

非同期 IO の実現方法

  • 1スレッドで複数の IO 呼び出しを処理を しない
  • 1スレッドで複数の IO 呼び出しを処理を する

単一スレッドで複数の IO 呼び出しを処理を しない

  • 同期ブロッキングを使い、複数スレッドで並列化
  • Python や Ruby のスレッドに GIL (Global Interpreter Lock) がついているのは IO 待ちのためのスレッドだから

GIL のない言語では

  • go は GIL がない代わりに channel と mutex がある
  • Clojure は GIL の代わりに STM がある

単一スレッドで複数の IO 呼び出しを処理を する

  • 同期ノンブロッキング(O_NONBLOCK)して、カーネルに次回のイベントを poll(libevent)
  • POSIX AIO で非同期ノンブロッキングして、シグナルでカーネルからの通知を受け取る(nginx aio)
  • epoll で複数のIOをまとめて取り扱う(nodejs)

非同期 ファイル IO について

  • epoll はファイル IO を非同期で扱えない
  • linux でのファイル IO はスレッドプールで実現されている
  • Linux AIO はパフォーマンスの問題や開発が止まっているから使われていない

非同期 IO まとめ

  • 同期ブロッキング - 普通のIO
  • 同期ノンブロッキング - 古い非同期(O_NONBLOCK)
  • 非同期ブロッキング - モダンな非同期(epoll)
  • 非同期ノンブロッキング - 開発停滞(Linux AIO)

3. イベント駆動と async-await


イベント駆動とは

  • イベントループで次に発火するイベントを決める
  • コールバックスタイルのイベントリスナにイベントを通知する
  • シングルスレッドで多重 IO が扱える
  • イベントループのスレッドでの処理時間を抑えないとパフォーマンスが出ない

イベントループ擬似コード

const waitingEvents = [];
const callbacks = {
  "main": ()=>{
    waitingEvents.push("foo");
    callbacks["foo"] = (event)=>{
      console.log("foo", event);
    };
  }
};

// event loop
while(true){
  const currentEvent = epollLike(waitingEvents);
  currentEvent.forEach(([eventName, event])=>{
    callbacks[eventName](event);
  });
}

コールバックスタイル


plhe5cqmsz7ss4mrwqix.jpg


_人人人人人人人人人人人_
> 突然のCallback Hell <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄


async-await の必要性

js-callbacks-promises-asyncawait.gif


callback hell からの脱出

  • 継続渡し形式(コールバック)から
  • 直接形式(yield|async-await)へ

yield | async-await の実現方法

  • 軽量スレッド
  • 継続
  • ステートマシン
  • マクロ

軽量スレッド

  • スレッド生成のコストはでかい
  • そもそもスタックフレームはでかい
  • IO イベントを待つために省メモリな軽量スレッドを使う
  • goroutine, C# Task, Java Green thread, GHC Haskell, Elixir, Boost Fiber

int read_chunk( NonblockingAPI & api, std::string & data, std::size_t desired) {
    int error;
    while ( EWOULDBLOCK == ( error = api.read( data, desired) ) ) {
        // ここで他のファイバーに処理を譲る
        boost::this_fiber::yield();
    }
    return error;
}

継続

  • Generator, Coroutine
  • スタックポインタとプログラム・カウンタを実行時に書き換える ことでシングルスレッドで擬似マルチスレッドできる
  • JavaScript, Python, Rust, Ruby, Boost Context, scheme call/cc

context ctx;
asio::io_service io_service;

void f(){
  socket_.async_connect(
    ip::tcp::endpoint(ip::address::from_string("127.0.0.1"), 31400),
    [](auto ec){ ctx.resume(); });
  ctx.suspend();
  // next...
}

int main(){
  auto ctx = context{f};
  ctx.start();
  io_service.run();
}

状態マシン

  • Coroutine エミュレータ
  • Boost Coroutine, C# の async-await, Babel|TS の generator の ES5 向けコンパイル

コンパイル前

async function a() {
    const a = await new Promise((resolve, reject)=>
      setTimeout(()=>{ resolve(0); }, 1000) );
}

コンパイル後

var __awaiter = (this && this.__awaiter) || function (thisArg, _arguments, P, generator) {
    return new (P || (P = Promise))(function (resolve, reject) {
        function fulfilled(value) { try { step(generator.next(value)); } catch (e) { reject(e); } }
        function rejected(value) { try { step(generator["throw"](value)); } catch (e) { reject(e); } }
        function step(result) { result.done ? resolve(result.value) : new P(function (resolve) { resolve(result.value); }).then(fulfilled, rejected); }
        step((generator = generator.apply(thisArg, _arguments || [])).next());
    });
};
var __generator = (this && this.__generator) || function (thisArg, body) {
    var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g;
    return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g;
    function verb(n) { return function (v) { return step([n, v]); }; }
    function step(op) {
        if (f) throw new TypeError("Generator is already executing.");
        while (_) try {
            if (f = 1, y && (t = y[op[0] & 2 ? "return" : op[0] ? "throw" : "next"]) && !(t = t.call(y, op[1])).done) return t;
            if (y = 0, t) op = [0, t.value];
            switch (op[0]) {
                case 0: case 1: t = op; break;
                case 4: _.label++; return { value: op[1], done: false };
                case 5: _.label++; y = op[1]; op = [0]; continue;
                case 7: op = _.ops.pop(); _.trys.pop(); continue;
                default:
                    if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; }
                    if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; }
                    if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; }
                    if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; }
                    if (t[2]) _.ops.pop();
                    _.trys.pop(); continue;
            }
            op = body.call(thisArg, _);
        } catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; }
        if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true };
    }
};
function a() {
    return __awaiter(this, void 0, void 0, function () {
        var a;
        return __generator(this, function (_a) {
            switch (_a.label) {
                case 0: return [4 /*yield*/, new Promise(function (resolve, reject) {
                        return setTimeout(function () { resolve(0); }, 1000);
                    })];
                case 1:
                    a = _a.sent();
                    return [2 /*return*/];
            }
        });
    });
}

マクロ

  • コンパイル前にコールバックネストに変換される
  • haskell, purescript, clojure

閑話休題


Fiber, Coroutine, Generator, Goroutine の違い


Fiber とか

  • User Land Thread
  • Light Weight Thread
  • Green Thread
  • OS thread の代替物。スケジューラ がある。
  • スレッドプールで処理されることもある

Generator とか

  • Generator
    • Iterator を生成するもの
  • Iterator
    • next() で次の値が取り出せるもの
  • Coroutine
    • Generator で実現できるもの。スケジューラは含まれていない

Goroutine

  • go のランタイムにある非同期並列 Fiber の scheduler
  • 他の言語の軽量スレッドと違い IO イベントループに依存しないことで IO bound と CPU bound な処理の使い分けを scheduler でがんばる

イベント駆動と async-await まとめ

  • イベント駆動はコールバックスタイルになる
  • コールバックスタイルはコールバック地獄を生み出す
  • コールバック地獄は async-await で解決できる

4. 非同期 IO のこれから


非同期 IO のこれから

  • 非同期例外とタスクキャンセル
  • promise-future, async-await はモナド
  • Stream は promise-future の一般化
  • Stream はモナド
  • 関数型リアクティブプログラミング

時間切れ


参考資料