右上➚

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

個人のメモ・ノートを保存するサービス選び

Dropbox Paper と Google Keep を併用してメモとかを取っていた. 長期的な記録とか人に見せうるもの,長めの文章は Dropbox Paper に, 一時的なメモとかリマインダ的なものは Keep に, と使い分けていた.

Dropbox Paper すごく好きだったんだけど,

  • なんか重い気がする
  • WYSIWYG なので markdown で書いているつもりでもちょこちょこ変なことが起きる
    • バッククオートをおした時の挙動とか
  • ブラウザでしか開けない

というのが使いにくく感じてしまった. 基本的にグループで使うものだと思うので,僕は使わない機能がいっぱいあるなぁという感じもした.

Keep は Keep で好きだし,使い分ければそんなに嫌なこともなかったので続投したい. その上で,長期的に残しておきたいメモやノートを書くサービスを探してみた.

ほしい要件

  • markdown で書ける
  • 端末間同期
  • 画像を D&D で貼れる & 保存できる
  • グループ分け.ディレクトリを切るくらいの機能で十分
  • Archive
  • 検索
  • ブラウザ以外のアプリケーションとして閲覧できる
    • 別に Electron でもなんでも良いけど,ブラウザとは独立したアプリケーションとして動いて欲しい
  • mobile app
  • 細かい一時的なメモを取るのは keep.google.com でやる
  • ToDo もいらない

比較

Dropbox Paper

Pros

  • サービスの大きさ・信頼性
  • markdown + WYSIWYG なエディタであること
  • 人にパッと見せられるくらいキレイにメモがとれる
  • presentation mode(個人で使ってたらあんまりいらないかも)

Cons

  • 重い...
  • WYSIWYG であること
  • ブラウザでしか開けない
  • markdown で書いているのに markdown として export すると微妙に modify されている...

Google Keep

Pros

  • さくさく
  • シンプル
  • リマインダとの連携とか

Cons

  • 長期的に残しておきたいドキュメントとかノートを書くためのものではない
  • markdown で書けない

evernote

お金は払う前提で考える

Pros

  • 圧倒的コミュニティ.連携の広さとか tips が転がりまくっている.
  • web clip とかちょっとした pdf や画像をポンポンぶち込んでおける
  • 短いメモみたいなものも躊躇なくいれておけそう

Cons

  • markdown が使えない問題がでかい
  • 長めの文章を書く感じじゃなさそう
  • 機能が多すぎてごちゃつきそうというイメージもある

Boostnote

OSS になっているエディタで,dropbox みたいな外部クラウドストレージを使って同期をはかるやつ.

Pros

  • UI
  • 要件はほぼ満たしている
  • 外部ストレージを使っているので,サービス停止のリスクは外部ストレージに依存する
    • dropbox / google drive / one drive とか代替も結構あるのでサービス停止を気にする必要がなさそう

Cons

  • Dropbox などのストレージを圧迫する
  • Boostnote 独自のフォーマット(フォーマットとしては cson だけど)で保存されるので,別に外部ストレージにそのまま md が吐かれるとかではない
    • markdown として export はできる

Inkdrop

Pros

  • UI
  • 要件は満たしている
  • status と tag 機能は便利そう.
  • 一番普通に整理が出来る構造になっている気がする
  • Data Access API が使える

Cons

  • 個人開発なのでサービス停止がこわい
    • とはいえ markdown なので移行は容易い

結論

要件を満たしているといえるのは Inkdrop と Boostnote くらいだろうか. Boostnote よりも Inkdrop のほうが first impression では好みだった. とりあえず 60 日 free なので Inkdrop を使ってみる. 今この文章も Inkdrop 上で書いている.普通に markdown を書けばいいのでまあ書くのは楽.

golang でテストのために時間を操作するライブラリ timejump

現在時刻に依存するコードをテストするとき,golangtime.Now を普通に使っているとモックできずうまくテストが書けないという問題があります. 時間の操作は time パッケージをそのまま使えば良いのですが,time.Now だけはモックできるようにしたいところです.

解決方法としては,グローバル変数var NowFunc func() time.Time を置いておいて,テスト時に入れ替えるという方法があり,ORM である gorm などが実際にこれを行っています.

gorm/utils.go at 2a1463811ee1dc85d168fd639a2d4251d030e6e5 · jinzhu/gorm · GitHub

例:

var NowFunc = time.Now

func Do() string {
    return NowFunc().String()
}

func TestDo(t *testing.T) {
    now := time.Date(2009, time.November, 10, 23, 0, 0, 0, time.UTC)
    NowFunc = func() time.Time {
        return now
    }
    got := Do()
    if got != now.String() {
        t.Fail()
    }
}

golang の使用上,Ruby の timecop のようなことは出来ないので,こういう工夫をするしかありません.

なんとなくグローバル変数をテストのために置いて書き換えるのが嫌なのと,なんにも考えずに t.Parallel() を置けなくなるのがちょっと嫌だなと思っていました. また,時間経過をシミュレーションしたい場合は,そういう NowFunc を毎回書く必要があり,結構面倒です. あとパッケージをまたぐと厄介だし毎回書くのも嫌.

そこで,Ruby の timecop のように現在時刻をいじくり回せるようにするライブラリを作ってみました.

github.com

godoc.org

使用する際は time.Now をすべて timejump.Now に置き換える必要があります.( Ruby と違って time.Now を直接上書きできないので...) 普段は timejump.Nowtime.Nowif !active { ... } が一段挟まるだけなのでパフォーマンスに影響はほとんどないはずです.

テスト時は,timejump.Now の挙動を変えたいテストの頭で

func TestDo(t *testing.T) {
    timejump.Activate()
    defer timejump.Deactivate()
    ...
}

とします.

timejump.Activate区間はロックをとっているので,テストを並列で走らせても並列に走らなくなります.

timejump.Stop() で時間停止,timejump.Jump で時間移動,timejump.Moveタイムゾーンの移動,timejump.Scale で時間の経過速度をいじれます.

時間を止めたいだけの場合はグローバル変数NowFunc を持っておいて t.Parallel を間違って置かないように気をつけるほうが正直楽だとは思いますが,時間経過をテストしたい場合にはちょっと楽になるはずです.

もともとあるパッケージのテストをするために書いたパッケージだったのですが,目的だったテストを書く前にテストしたいパッケージが御役御免になってしまったので,timejump も御役御免になってしまいました. いつか使う日が来る気がするので,ここに寝かせておきます.

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++ で書きたくなりました.十分速いし書きやすいので良いんですが…