非同期 IO について

おしながき

C10K 問題について
非同期 IO とは何か
async-await
非同期 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);
  });
}

コールバックスタイル

＿人人人人人人人人人人人＿
＞　突然のCallback Hell　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣

async-await の必要性

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 はモナド
関数型リアクティブプログラミング

時間切れ

非同期 IO について

非同期 IO について

おしながき

1. C10K 問題 について

時は 2002 年

Web 勃興期

牧歌的時代の終わり

HTTP サーバ

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

どう実装するか

当時の Web サーバ

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

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

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

→

C10K 前後史

C10K まとめ

2. 非同期 IO とは何か

IO とは

IO の種類

同期ブロッキング

同期ノンブロッキング

非同期ブロッキング

非同期ノンブロッキング

非同期 IO の実現方法

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

GIL のない言語では

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

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

非同期 IO まとめ

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

イベント駆動とは

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

コールバックスタイル

async-await の必要性

callback hell からの脱出

yield | async-await の実現方法

軽量スレッド

継続

状態マシン

コンパイル前

コンパイル後

マクロ

閑話休題

Fiber, Coroutine, Generator, Goroutine の違い

Fiber とか

Generator とか

Goroutine

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

4. 非同期 IO のこれから

非同期 IO のこれから

参考資料

1. C10K 問題について

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

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

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