右上➚

プログラミングに関するメモをのこしていきます

ISUCON 7 本戦出場してきました 「都営三田線東急目黒線直通急行日吉行」

ISUCON 7 お疲れ様でした!

僕らのチーム,「都営三田線東急目黒線直通急行日吉行」は学生枠 2 位,全体で 10 位という結果でした.

予選の結果が異常によかったので完全に調子に乗っていたんですが,本戦はやっぱり難しかったですね... 本戦でも社会人上位勢と戦えるくらいのスコアを出すのと学生枠優勝が目標だったのでやっぱりくやしい.

やったこと

結局テンパりすぎてスコア記録を残せていないので,なんとなく記憶を頼りに...

Go 実装でいきました.

  • room 名から ws をつなぎに行くホストが一台に固定されるように
    • 同じルームの action は全部同じホストにいくように
    • これでオンメモリに出来るようにした(結局ほとんどオンメモリにデータは持たなかった)
  • ルーム名から適当なハッシュ値を計算してふるようにしていたけれど,ルームによってアクセス頻度とかがちがうっぽい?ことに気がつく
    • 3 台に振ってるはずなのに,CPU 使用率を見ると 2 台しか使われていないとか
    • 負荷分散が運ゲーになっていて改善の結果が見にくかったので,とりあえず 1 台しか使わないように
  • ホストごとの接続数を redis に入れて,空いていそうなところに振り分けるように
    • 前段のサーバに nginx + app + redis を入れて,そこの redis に room -> host の対応情報を入れた
    • CPU 使用率で振り分けたほうが良かったかもしれない
  • schedule の計算過程を最適化出来る気がしなかったので,結果をキャッシュしようと試みる
    • どうやっても事後検証をパスできなかったので捨てることに...
  • 部屋ごとにロックをとってすべての操作を直列にした
    • トランザクションとかが複雑すぎていじれる気がしなかったので,一旦直列にして考えることを減らそうとした
    • rollback 考えなくて良くなったのでこれ自体は良かった気がする
  • @izumin5210 が adding/buying を redis にいれたり,過去の adding をまとめてくれた
    • ここは完全におまかせしてしまった
    • 最終的にまともに効いたのはこれだけだったのでは
  • 終盤はベンチマーカに弾かれる原因をひたすら探していた
    • 安全側に倒そうということで,色んな所でひたすらロックを取るようにしてなんとかパスした

という感じで,最高スコアが 17000 くらい,最終スコアが 16700 で終了しました.

反省

  • チーム名が長すぎた
    • 名札のチーム名部分のフォントが他のチームより小さかった気がする(ご迷惑おかけしていたらすみません...)
    • 手書きで書くのがつらすぎる
    • 来年は気をつけます
  • テストがせっかく用意されていたのにまったく使わなかった
    • テスト使っていたらもうちょっと計算過程の最適化にも手を出せたかもしれない
  • なにも操作がなくても 500ms ごとに status を計算していたところの最適化を入れきることができなかった
    • この計算は room ごとに一回やれば良いはずなのにコネクション一個につき一回計算していた
    • room ごとにひたすら status を計算し続ける goroutine を起動してそこから返す実装を書いていたが,終盤の fail 祭りにびびっていれられなかった...
    • 意味があったかどうかはよくわからない.
  • CPU profile をみて,bigint の計算がやばいことはわかっていたのに,手が出せなかった
    • この複雑さは結果をキャッシュしろってことだな!って勝手に思い込んでいたけど,結果のキャッシュも複雑で無理だった
    • 他のチームの方の話を聞く限り,そんなに無茶な最適化じゃなくても地道に最適化していたらそれなりにスコアに効いたのかもと思った(これはやってみないとわからないけど)

予選のときも練習のときも,「遅いのはわかっているけど複雑そうでやりたくない」部分を触らないとだめっていう教訓は得ていたはずなんだけど,結局そこでやられてしまったのが一番くやしいですね...

来年は学生枠ではなくなるのですが,社会人枠でも本戦にでて勝ちたいです!

去年に引き続き本戦に出られたのはほんとうに良かったし,またまた勉強になる良い経験でした!運営の皆様お疲れ様でした & ありがとうございました!

ISUCON7予選1日目に「都営三田線」で参加して通過できた話

ISUCON7 予選お疲れ様でした! タイトルどおりですが,「都営三田線東急目黒線直通急行日吉行」という学生チームで参加し,1日目3位枠で通過することができました. チーム編成は,去年2人チームで参加したときの相方である 0gajun と,僕の内定先の同期の izumin の 3 人チームでした.

何をやったかとかスコアの変遷は別で記録したいと思います(僕一人で把握しきれていないので)が,とりあえずリポジトリはここです.

github.com

追記: タイムラインと詳細はこっちに書きました

www.wantedly.com

f:id:agtn:20171023153909p:plain

去年2人で参加した時は学生枠で予選通過はできたものの,一般枠との圧倒的なスコア差にだいぶ打ちひしがれていました. もともと,「0gajun がインフラ,僕がインフラ寄りのアプリ」というチームだったので,アプリ側をがつがついじれる izumin が加わったことで,チームバランスが良くなった + 手数が圧倒的に増えたと思います.

去年とくらべてメンバーも増えたし学生とはいえ一年間で成長している(はず)というのもあったので,夢として「学生枠だけど一般枠と戦えるスコアを出したい」というのがありました. 結果,予選1日目上位3チーム枠で本戦出場を決められて本当にうれしかったです.2日目の上位が圧倒的なスコアだったのでちょっと凹みましたが,全体でも 10 位くらいだったと思うので,目標は達成できたと思います. また,無理やり ISUCON 特化な高速化を入れたりすることなく良いスコアを出せたと思うので,そこも良かったなと思っています. 本戦でも良いスコアが出せるように頑張るぞー!

最後に,ISUCON 運営の皆様,本当にお疲れ様でした & ありがとうございました! 予選から複数台構成で面食らいましたが,複数台は難しい分,楽しさも増すし勉強になることもたくさんありました! 本戦も楽しみにしています!

go generate する時のバイナリのバージョンを固定したい

https://github.com/golang/mockmockgen というコマンドを提供しています. これは,interface から mock を自動生成するコマンドで go generate と合わせて使うと interface に追従する mock がとても簡単に作れます.

他にも yacc とかリソースをバイナリに埋め込むとか,色々便利ツールがあり,go generate でコード生成をするのは golang のアプリケーションではよくあることだと思います.

しかし,golangvendor/ の仕組みは基本的に package として使うことを考えて作られているので,プロジェクトごとに mockgen などの生成コマンドのバージョンを固定するためには使えません.

ここで,go generate で使うバイナリのバージョンが固定されていないと起こりうる問題として

  • 生成されたコードに毎回 diff が出る
    • 気軽に git add . 出来ないし,コミット漏れや無駄コミットにつながる
  • バージョンAのコマンドとバージョンBのコマンドによって生成されたコードが混ざる
  • ライブラリのバージョンと生成コマンドのバージョンが一致しないためバグる
    • github.com/golang/mock/mockgengithub.com/golang/mock/gomock というライブラリとセットで使うので,gomock package と mockgen バイナリのバージョンは揃えたい

などがあります.

これ結構嫌な問題だと思ったのですが,パッとぐぐってみてもあまり困っている声を聞かないので普通どうやって解決しているのか気になっています. (もしかして僕が知らないだけで普通に解決されている問題だったりするのだろうか…)

とりあえず vendor 以下の package をビルドしたり固定されたバージョンのバイナリをぱぱっと実行するために

github.com

を作ってみました.

shell script で書けそうな単純な仕事しかしていませんが,go で実装されています.

bindor build github.com/golang/mock/mockgen./.bindor/mockgen というバイナリが出来ます. bindor exec command args... とやると PATH=./.bindor:$PATH した環境下で command args... を実行します.

$ glide get github.com/golang/mock
$ bindor build github.com/golang/mock/mockgen
$ bindor exec which mockgen
/path/to/current/.bindor/mockgen

という感じです.

//go:generate bindor mockgen としてもいいですが,bindor exec go generate とすればソースコードを書き換えなくても .bindor 以下のバイナリを使うようになるはずです.

bindor 自体にバージョンを固定する仕組みは入れていません.glide とかがやってくれている仕事を分散させても管理が面倒になるだけでメリットがなさそうだし,ライブラリとしても使う package の場合はどうせ glide で管理するので,vendor 以下のディレクトリの奪い合いになってしまいます.

というわけでバイナリを vendoring する bindor を作った話でした.もっといい解決方法があったら教えてください.

Rust で Unix のシグナルを channel 経由でキャッチする

Rust でシグナルハンドリングをする必要があったのですが,あまり自分の用途にあるライブラリがなかったので作りました. 僕が Windows のことをほとんどわからないので,Windows 未対応です.

github.com

docs.rs

https://crates.io/crates/signal-notify

golangsignal.Notify に寄せた API になっていて,標準ライブラリの std::sync::mpsc::{Sender, Receiver} 経由でシグナルを待ち受けることができます.

extern crate signal_notify;
use signal_notify::{notify, Signal};
use std::sync::mpsc::Receiver;

fn main() {
    let rx: Receiver<Signal> = notify(&[Signal::INT, Signal::USR1]);
    for sig in rx.iter() {
        match sig {
            Signal::INT => {
                println!("Interrupted!");
                break;
            }
            Signal::USR1 => println!("Got SIGUSR1!"),
        }
    }
}

Rust で Unix シグナルを取るライブラリとしては GitHub - BurntSushi/chan-signal: Respond to OS signals with channels. というのが有名です. こちらは標準ライブラリの mpsc::channel ではなく,chan クレイトの channel を使っています. chan クレイトはケースによってはかなり便利で,

  1. 複数の consumer を作れる (receiver.clone() ができる)
  2. chan_select! マクロによって golangselect 的なことができる

という利点があります.

一方で複数 consumer にする必要がない & chan_select! が必要ないケースでは,シグナルハンドリングのためだけに chan にも依存するのもなんとなくはばかられるという気持ちがありました. また,自分の目的として「SIGWINCHSIGIO が取りたい」というのがあったのですが,chan-signal の仕組みだとデフォルトで無視されるシグナルをキャッチできない(macOS だけ)という問題もありました. 報告するときに方法を考えていたのですが,あまり自信がなかったのとほとんど完全に仕組みを書きなおす形になりそうだったので,自分の手元で std::sync::mpsc を使って実験してみたという経緯です.

仕組み

  1. 初期化時にパイプを作る
  2. シグナルごとに通知すべき Sender を覚えておく
  3. シグナルごとに sigaction でハンドラをセットする
    • シグナルが来たらそれをパイプに write(2) する
  4. シグナル待受&通知用のスレッドを起動する
    • パイプからシグナル番号を読んで,適切な Sendersend する

という仕組みで動いています. 自信がなかったのは,「シグナルハンドラでやっていいこと一覧」をちゃんと把握していないという点です. 一応 sigaction の man を見ると write は読んでもいい関数一覧にいる気がするし,実際動いてはいるのでセーフだろうと判断しました. (もしアウトだったら教えてください)

ちなみに chan-signal の方は,

  1. シグナルごとに通知すべき Sender を覚えておく
  2. 監視用スレッドを起動し,メインスレッドでは pthread_sigmask を使ってシグナルをブロックする
    • シグナルがすべて監視用スレッドに渡るようにする
  3. 監視用スレッドで sigwait して適切な Sendersend する

という仕組みで動いているようです. sigwait は指定したシグナルが投げられるまでブロックします. ただし,macOSsigwait の man を見ると,

Processes which call sigwait() on ignored signals will wait indefinitely. Ignored signals are dropped immediately by the system, before delivery to a waiting process.

とあって,無視されるシグナルを sigwait で待っても補足できないようです. Linux の man を見るとそんなことは書いていないし,普通に動くっぽいです.

今の実装だと,シグナルを受け取る Receiver がすべて閉じても,監視スレッドは動き続けるしハンドラも残り続けるので,これはなんとかしたいなぁと思っています. アプリケーションの実行時間のうち,ある期間だけシグナルをとってそれ以外はスルーしたいというケースもそんなにないかなというのと,内部的な変更にしかならないので API が変わらないというのがあるので,この状態でとりあえず public にしました.

CLI を書いていると意外と普通に SIGINT は取りたくなることがあると思うので,ぜひ使ってみてください. issue 報告等お待ちしています.

BK-tree を golang で実装した

先日はてぶに 興味深いデータ構造:BK木 | プログラミング | POSTD という翻訳記事 ( 元記事 http://signal-to-noise.xyz/post/bk-tree/) があがっているのをみて初めて BK-tree というものを知ったので,golang で実装してみました.

github.com

BK-tree とは

先程の記事に全部書いてあるのですが… BK-tree は,ある距離空間内で近傍点探索を効率的に行えるデータ構造です.利用例としてはスペルチェックや類似画像検索などがあります.

距離空間とは,なにかしらの距離を計算することができる空間のことで,距離としてハミング距離やマンハッタン距離,レーベンシュタイン距離,ユークリッド距離などなどが挙げられます. 例えば,いわゆる普通の 3 次元の空間は,ユークリッド距離を距離関数に持つ距離空間と考えられます.

近傍点探索は,要するにある点に対して,近くにある点を探すことです.

f:id:agtn:20170513183241p:plain

ものすごく単純に近傍点探索をやろうと思うと,全要素を線形に探索して距離を計算していく必要があります. そこで BK-tree を使うともっと計算量が減らせるというわけなのです.(ちなみに僕は BK-tree を使った場合の計算量がよくわかっていません.実験的に速いことを確認しただけです.正確な計算量は考えてもよくわかりませんでした…)

構造や仕組みは元記事などをご参照ください.

golang での bk-tree 実装は実はいくつかあったのですが,単純にアルゴリズムを理解するために実装したかったのと,レーベンシュタイン距離を距離関数として使うことを前提にしていたりとちょっと自分の用途に合っていない気がしたので,別で作ってみました.

このパッケージでは,スペルチェックそのものや距離関数を提供していません.BK-tree というデータ構造だけを提供しています.

使用例

16 bit 整数を要素,ハミング距離を距離関数とした例です.

要素となる型は bktree.Entry interface を満たす必要があります.これは Distance(Entry) int を要求する interface です.
本当は distance<T: Entry>(x: T) -> int みたいな形にしたいのですが,golang だと出来ないので,実装側で e.(hashValue) のように型アサーションする必要があります.
ここでは uint16 に戻してハミング距離を計算しています.

要素の追加は Add(e Entry) です.
ここでは 0 ~ 0xffff までを突っ込んでいます.

探索は Search(e Entry, tolerance int) []*Result です. 第一引数がキー,第二引数が許容する距離の最大値です.

package main

import (
    "fmt"

    "github.com/agatan/bktree"
)

type hashValue uint16

// Distance calculates hamming distance.
func (h hashValue) Distance(e bktree.Entry) int {
    a := uint16(h)
    b := uint16(e.(hashValue))

    d := 0
    var k uint16 = 1
    for i := 0; i < 16; i++ {
        if a&k != b&k {
            d++
        }
        k <<= 1
    }
    return d
}

func main() {
    var tree bktree.BKTree

    // add 0x0000 to 0xffff to the tree.
    for i := 0; i < 0xffff; i++ {
        tree.Add(hashValue(i))
    }

    // search neighbors of 0x0000 whose distances are less than or equal to 1.
    results := tree.Search(hashValue(0), 1)
    for _, result := range results {
        fmt.Printf("%016b (distance: %d)\n", result.Entry.(hashValue), result.Distance)
    }
}

これを実行すると,

0000000000000000 (distance: 0)
0000000000000001 (distance: 1)
0000000000000010 (distance: 1)
0000000000000100 (distance: 1)
0000000000001000 (distance: 1)
0000000000010000 (distance: 1)
0000000000100000 (distance: 1)
0000000001000000 (distance: 1)
0000000010000000 (distance: 1)
0000000100000000 (distance: 1)
0000001000000000 (distance: 1)
0000010000000000 (distance: 1)
0000100000000000 (distance: 1)
0001000000000000 (distance: 1)
0010000000000000 (distance: 1)
0100000000000000 (distance: 1)
1000000000000000 (distance: 1)

という感じで 0x0000 とのハミング距離が 0 ~ 1 である要素がとれます.

パフォーマンス

単純な線形探索との比較をするベンチマークをおいてあります.
64 bit 整数,距離関数はハミング距離,データ量 1,000,000 件での結果が以下のようになりました.

ベンチマーク 実行時間
BK-tree (完全一致) 1108 ns/op
BK-tree (fuzziness 1) 29468 ns/op
BK-tree (fuzziness 2) 328753 ns/op
BK-tree (fuzziness 4) 5490888 ns/op
BK-tree (fuzziness 8) 68182122 ns/op
BK-tree (fuzziness 32) 353715305 ns/op
Linear Search 4132926 ns/op

fuzziness が小さければ小さいほど ( = tolerance が小さければ小さいほど ) 高速に探索できることが分かります.

また,データ量が増えるほど Linear Search より有利になるので,距離に対してデータが十分に大量にある場合はかなり有効といえそうです.

おまけ

tree の構築にかかるコストがそこそこ大きかったので pprof で見つつチューニングする必要がありました. 学びとして,「map が重い」「interface が重い」というのがありました.

各ノードの部分木は,そのノードからの距離 d を key として,map[int]*Node としていました. tree を構築する際には,allocate + read + write をかなりの回数行うのですが,これがまぁ遅い.
最終的にこの部分はスライスでもっておいて,d を key として部分木をとりたい時は線形探索をするようにしました.
next, ok := n.children[d] としていた部分が

type elem struct
    distance int
    node *node
}

for _, c := range n.children {
    if c.distance == d {
        return c.node
    }
}
return nil

という感じになります.あんまりきれいではないんですが,こっちの方がほとんどのケース倍以上速かったので,こちらを採用しました.
部分木の数が増えてくると,map のほうが速いと思われるのですが,ハミング距離の場合最大でも bit 数までしか部分木が増えないので.
レーベンシュタイン距離を用いたスペルチェックの場合でも,単語の最大文字数以上の距離にはなりません. 2 次元 / 3 次元程度の距離空間なら kd-tree などもっと他に良い方法があるきがするので,レーベンシュタイン距離やハミング距離を使うケースをメインに考えました.

その結果,実行時間のかなりの割合が Entry interface を介した関数呼び出しのオーバヘッドとか,inteface の allocation になってしまいました.
データ構造を golang で提供する以上このオーバヘッドは避けられないです.( もちろん BK-tree そのものを,自分の利用形態に特化して作れば回避できますが… )
ちょっと Rust や C++ で書きたくなりました.十分速いし書きやすいので良いんですが…

Rust でグラフ構造や木構造を作る

プログラムを書いていると何かしら木構造っぽいものやグラフっぽいものを作りたい場面が多々あると思います. Rust は所有権や Size の都合で,これらを作ろうと思うと地味にハマるのでまとめておきます.

Rust で木構造

最も単純な木構造は Rust だと

enum Tree<T> {
    Leaf(T),
    Node(Box<Tree<T>>, Box<Tree<T>>),
}

といった形で表せます. Rust では明示的に boxing してあげないと再帰的なデータ構造は作れないのでちょっと複雑に見えるかもしれませんが,まぁ単純です.

この木構造を書き換えたい場合は,ownership をとって書き換えた値を返すこともできますし,&mut Tree<T> をとって in-place に書き換えることもできます.

fn inc(&mut self) {
    match *self {
        Tree::Leaf(ref mut i) => *i = *i + 1,
        Tree::Node(ref mut left, ref mut right) => {
            left.inc();
            right.inc();
        }
    }
}

fn inc2(self) -> Tree<i32> {
    match self {
        Tree::Leaf(i) => Tree::Leaf(i + 1),
        Tree::Node(left, right) => Tree::Node(Box::new(left.inc2()), Box::new(right.inc2())),
    }
}

Rust で有向非巡回グラフ

有向非巡回グラフ構造は,グラフのエッジに向きがあり,かつ循環がない構造で,これは割りと単純に表現できます.

struct Node<T>(T, Vec<Rc<Node<T>>>);

Node は自身の値 T と,つながっているノードの Vec を持ちます.(対象問題によっては Vec ではなくて HashMap とか HashSet とか)

Rc は参照カウント方式のスマートポインタです. グラフでは,Node は複数の Node から参照される可能性があるので, Box は使えません.

これを変更可能にしたい場合はちょっと面倒ですが RefCell を使う必要があります.

Rust では基本的に mutable borrow は常にひとつしか存在できず,mutable borrow が生きている間は immutable borrow もつくることができません. Rc から mutable な参照を取り出すこともできません.

そこで RefCell を使うことで borrow check をランタイムに行うようにします. RefCell は immutable な参照から mutable な参照を取り出せるようにする働きをしますが, mutable な参照を取っている間に,さらに mutable な参照を作ろうとしたり immutable な参照を作ろうとすると,ランタイムに panic します. コンパイル時検査ではなくランタイム検査になるので,プログラマの責任できちんと管理しないと死にます.

RefCell 版がこちら

struct Node<T>(T, Vec<Rc<RefCell<Node<T>>>>);

impl Node<i32> {
    fn inc(&mut self) {
        self.0 += 1;
        for n in &self.1 {
            n.borrow_mut().inc();
        }
    }
}

Rust で巡回有向グラフ

循環がある場合は厄介です. Rust で参照を共有するための Rc は参照カウントなので,循環参照があるとリークします. したがって循環のある構造を表すために Rc は使えません.

木構造で親を参照するポインタを子に持たせておきたいといったケースでは,親は子を Rc で持ち,子は親を Weak で持つという形で対応できますが, グラフだとそういうわけにもいきません.

そこで出て来るのが Arena という方法です.

オブジェクトの実体は Arena の中に作り,グラフにはその ID を持たせて管理します.

type NodeId = usize;

struct NodeArena<T> {
    arena: Vec<Node<T>>,
}

impl<T> NodeArena {
    fn alloc(&mut self, value: T) -> NodeId {
        let id = self.arena.len();
        let node = Node(id, value, Vec::new());
        self.arena.push(node);
        id
    }
    fn get(&self, id: NodeId) -> &Node<T> {
        &self.arena[id]
    }
    fn get_mut(&mut self, id: NodeId) -> &mut Node<T> {
        &mut self.arena[id]
    }
}

struct Node<T>(NodeId, T, Vec<NodeId>);

こんな感じです.

こうすることでコンパイル時の borrow check を諦めることなくグラフ構造を作ることができます.
(ii+1 番目のノードを同時に mutable に参照したいとかは苦しいですが)

欠点としては単純に間接的な表現でめんどくさいというのもありますが,GC がないので参照されなくなったオブジェクトも Arena 上で生き続けてしまうことです. そのため,動的に要素が生きたり死んだりするケースには使いにくいです.

ノードグラフの構築が終わったら Arena をリフレッシュするみたいなことをすると良いのかもしれません. (構築中は VecArena を表現して,構造が固まったら HashMap を使った Arena に切り替えて参照されているidだけを残すみたいな)
それでも構築中はオブジェクトがあまりまくるので辛いですね...

mio で echo サーバメモ

Rust の非同期 IO ライブラリのなかでももっとも低レベルなレイヤーを担っている mio を使ってecho サーバを書いた。 echo サーバばっかり書いているような気がするけど,echo サーバやっておくと簡単な割にライブラリの使い方とかがちゃんと分かる気がするので好きです。

コード

extern crate mio;

use std::io::prelude::*;
use std::collections::HashMap;

use mio::*;
use mio::tcp::{TcpListener, TcpStream};

#[derive(Debug)]
struct ClientsHolder {
    table: HashMap<Token, TcpStream>,
    free_token: Vec<Token>,
    next_max_token: Token,
}

impl ClientsHolder {
    fn new_from(start_token: Token) -> Self {
        ClientsHolder {
            table: HashMap::new(),
            free_token: Vec::new(),
            next_max_token: start_token,
        }
    }

    fn next_token(&mut self) -> Token {
        if let Some(tok) = self.free_token.pop() {
            return tok;
        }
        let tok = self.next_max_token;
        self.next_max_token = Token(tok.0 + 1);
        tok
    }

    fn register(&mut self, tok: Token, client: TcpStream) {
        self.table.insert(tok, client);
    }

    fn get_mut(&mut self, tok: Token) -> Option<&mut TcpStream> {
        self.table.get_mut(&tok)
    }

    fn remove(&mut self, tok: Token) -> Option<TcpStream> {
        let result = self.table.remove(&tok);
        if result.is_some() {
            self.free_token.push(tok);
        }
        result
    }
}

// Setup some tokens to allow us to identify which event is
// for which socket.
const SERVER: Token = Token(0);

fn main() {

    let addr = "127.0.0.1:13265".parse().unwrap();

    // Setup the server socket
    let server = TcpListener::bind(&addr).unwrap();

    // Create an poll instance
    let poll = Poll::new().unwrap();

    // Start listening for incoming connections
    poll.register(&server, SERVER, Ready::readable(), PollOpt::edge())
        .unwrap();

    // Create storage for events
    let mut events = Events::with_capacity(1024);
    let mut clients = ClientsHolder::new_from(Token(1));

    loop {
        poll.poll(&mut events, None).unwrap();

        for event in events.iter() {
            match event.token() {
                SERVER => {
                    // Accept and drop the socket immediately, this will close
                    // the socket and notify the client of the EOF.
                    let (stream, _) = server.accept().unwrap();
                    let tok = clients.next_token();
                    poll.register(&stream, tok, Ready::readable(), PollOpt::edge()).unwrap();
                    clients.register(tok, stream);
                }
                tok => {
                    let mut close = false;
                    if let Some(mut stream) = clients.get_mut(tok) {
                        let mut buf = [0; 1024];
                        let n = stream.read(&mut buf).unwrap();
                        if n == 0 {
                            poll.deregister(stream).unwrap();
                            close = true;
                        } else {
                            stream.write(&buf[0..n]).unwrap();
                        }
                    }
                    if close {
                        clients.remove(tok);
                    }
                }
            }
        }
    }
}

面倒だったので unwrap まみれですが。

やったこと

mio の全体の流れとしては,Poll 型の値がイベントを監視する役割を担います. Poll に監視対象を登録していき,Poll::poll でイベントの発火を待ちます. 発火したイベント一覧が Events 型の Events::iter で取れるので,対応していけばよいです.

mio では Token という型の値を使って監視対象を識別しています. 監視対象には TcpListenerTcpStreamSender,などなどいろんなものがあるので,統一的に扱うために PollToken だけを保持します. Token と監視対象の紐付けはユーザ側の責任でやってくれという感じみたいです.

echo サーバではクライアントの数は不特定なので,「空いている Token を探す」と「Token に対応するクライアント (TcpStream) を探す」がうまくできる必要があります. そこで,ClientsHolder を定義しました. こいつが,空いている Token を返すのと Token をキーに TcpStream を返す仕事をします. remove されたらその Token は再利用します.

気になるところ

mio はファイルに対する抽象化は提供しない方針のようです. STDIN / STDOUT も同様です.

ファイル IO もノンブロッキングにしたい場合はどうしたらいいんでしょう?よくわかっていない. mio::unix 以下に UNIX 限定の拡張がおいてあって,EventedFd という file descriptor を扱う実装はあるので,UNIX 限定なら力技でなんとかなるのかもしれない.

あと mio は関係ないんですが,実装の部分で,

let mut close = false;
if let Some(mut stream) = clients.get_mut(tok) {
    let mut buf = [0; 1024];
    let n = stream.read(&mut buf).unwrap();
    if n == 0 {
        poll.deregister(stream).unwrap();
        close = true;
    } else {
        stream.write(&buf[0..n]).unwrap();
    }
}
if close {
    clients.remove(tok);
}

というのがあるんですが,これどうやったらスマートなんでしょう. close = true としている部分で clients.remove(tok); をやるのが普通だと思うんですが,if let Some(mut stream) = clients.get_mut(tok) { のところで clients は borrow されているから mutable borrow はこれ以上作れないのです.