Go to Qiita Advent Calendar 2024 Top
LoginSignup
151
118

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@legokichi

非同期 IO について

Last updated at Posted at 2018-03-02
1 / 63

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

時間切れ

参考資料

151
118
4

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
151
118

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?