kawasin73のブログ

技術記事とかいろんなことをかくブログです

ロバストなプロトコルを設計して実装した

参加記 TCP/IP Go

どうも、ロバストと愉快な仲間たちのロバストこと、かわしんです。そうです、私がロバストです。

さて、8 月 13 日から 8 月 17 日までの 4 泊 5 日で セキュリティネクストキャンプ に参加してきました。

セキュリティネクストキャンプとは、セキュリティ・キャンプ全国大会 と同時期に開催されるネクストな感じのセキュリティキャンプです。 全国大会は 22 才までの一生に一度しか参加できないのですが、もう一度参加したいという卒業生をターゲットに今年から新しく始まったそうです。このネクストキャンプは 25 才までの学生であれば（詳しくは公式の募集要項を確認してください）卒業生でなくても同等の技術スキルがあれば参加することができます。

応募には審査があり、今年は 13 人の応募から 6 人が選ばれたそうです。

僕はセキュリティキャンプの存在を去年知った時にはすでに 24 才になっており参加できないことを残念に思っていたのですが、今年ネクストキャンプの存在を Twitter で知り参加することにしました。

講義としては、暗号化アルゴリズムの AES を FPGA に実装したり、XSS 文字列の検知するエンジンを機械学習で実装したり、複数の CPU アーキテクチャのエミュレータに実装された特殊命令のアルゴリズムを解析してそれをエミュレータに実装し直したりなど、主に手を動かして演習するタイプの講義が多く非常に勉強になりました。

参考 : セキュリティ・ネクストキャンプ2019 プログラム：IPA 独立行政法人 情報処理推進機構

実習講義が多い分、キャンプ開催前の事前学習やキャンプ中の宿題などタスクが多く眠れない充実した楽しい 5 日間を過ごすことができました。

ロバストなプロトコルを考案せよ

さて、その授業の中で一番僕が楽しみにしていたのがこの「ロバストなプロトコルを考案せよ」という講義です。

これは、10BASE-T の LAN ケーブルの 4 対のツイストペアの 1 つにノイズを載せ、そのケーブルを使ってなるべく多くのファイル転送ができるようなプロトコルを考えて実装し、最終日にコンテストを行うものでした。僕はこのコンテストで１位をとり、ロバスト賞をいただきました。なので、僕こそがロバストです。

ファイルとしては事前に用意された 1000 個の 100KB 程度のランダムなバイナリファイルを転送し、チェックサムを確認して内容が正しいファイルのみをカウントします。間違ったファイルによるペナルティはありません。また出力するファイル名は元のファイルと異なっていても問題ないというレギュレーションでした。

ノイズはだいたい ping パケットが 50% 失敗する程度のノイズが発生させられます。

イメージとしてはこんな感じです。ノイズインジェクターはブラックボックスになっており、ピンを接続して利用します。

f:id:kawasin73:20190819220451j:plain

この画像のケーブルは講師の今岡先生が作成してくださったものですが、事前学習で自分でケーブルの被膜を剥ぐのは結構難しかったです。

僕の Robustp

この課題に対して僕は Robustp という独自プロトコルを設計して実装しました。（正確には実装しながら設計を進化させていますが）

github.com

これは、簡単にいうと UDP の上に TCP や QUIC のようなプロトコルを載せている感じです。

設計

f:id:kawasin73:20190819221652p:plain

Robustp は内部で 2 つのレイヤーに別れています。TCP を参考にしたファイル単位でセグメントの位置やファイルの完成などを管理する ファイル層 と、セグメントを TransID という一意で単調増加する ID で管理して再送やウィンドウ制御を行う トランスポート層 です。

ファイル層 は、各ファイルは一意な Fileno が割り当てられた FileContext 構造体で表現され、ファイルデータを分割したセグメントは Offset が割り当てられた FileSegment 構造体で一意に管理されます。これは TCP を参考にしており、TCP のポート番号が Fileno に対応し、TCP のシーケンス番号が Offset に対応しています。

ファイル層は各ファイルのどのデータが送信済み・受信済みであるのかとファイルのデータが揃っているのかを管理します。ファイル層では TCP と同じように Partial ACK を実現し、受信した全てのパケットの位置を ACK メッセージに詰めて応答し、無駄な再送を防ぎます。

トランスポート層 は FileSegment をラップした TransSegment に TransId を紐づけて管理します。それぞれの TransSegment は WindowManager 内のウィンドウバッファで管理され、WindowManager は、ウィンドウサイズ制御、RTTの計測、再送タイマー、欠損したACKの即時再送 などの機能を提供します。TransId は QUIC での Delivery Order Id の考え方を参考にして実装されており、再送が必要な場合は新しい TransId を割り当てて再送することで RTT 計測のロジックがシンプルになります。

最初は TCP を参考にファイル層のみで実装をして Fileno と Offset （実装当時は Seqno だった）でセグメントを一意に管理して再送を行なっていましたが、再送パケットの RTT 計測ができなくなる課題を抱えていて悩んでいました。

その時にちょうど ぺトロン 君に QUIC の論文 1 を教えてもらい、読んでみると QUIC では再送などを管理する Delivery Order Id とデータの位置を管理する Stream Offset を分離しているという考え方を知りました。それを TransID という形でトランスポート層を分離して実装しました。

Add TransId · kawasin73/robustp@c585c66 · GitHub

ちょうどこのコミットで対応していますが、ファイル層の操作をうまく抽象化していたのでそこまで載せ替えるのは大変ではなかったです。

それぞれのメッセージは、Ethernet の 1 フレームに収まるように 起動時にコマンド引数で渡される MTU（1500 バイト）からセグメントのサイズを調整します。複数のフレームに UDP パケットが分割されると 1 つのフレームが落ちただけでパケット全体をロスしてしまうのを防ぐためです。

ファイル層とトランスポート層の間はシンプルな 4 つのインターフェイスだけが定義されています。

ファイル層からトランスポート層へは Sender の sendThread() メソッド内に定義された sendSegment() マクロを呼び出します。このマクロは、WindowManager.Push() メソッドを呼び出してセグメントをウィンドウに追加してパケットを送信します。

トランスポート層からファイル層へは以下の 3 つのインターフェイスが FileSegment に定義されています。

  • TransId 付きのデータメッセージを作成する PackMsg()
  • ACK メッセージを受信した時に呼び出す Ack()
  • セグメントを再送する時に Partial ACK によってファイル層が知っている再送の必要がないかどうかの情報を問い合わせる IsCompleted()

この辺りの機能の分離とインターフェイス設計は綺麗にできたと自分では満足しています。

ヘッダはこんな感じになっています。

f:id:kawasin73:20190820012418p:plain

赤い部分がファイル層のためのヘッダで、青い部分がトランスポート層のためのヘッダです。どちらかというと TransId を先頭の方に持ってきたかったのですが、これは歴史的経緯です。変更するのがめんどくさかったのでこのままにしました。

コンポーネント構成と提供する機能

f:id:kawasin73:20190819225517p:plain

送信側のコンポーネントはこのように設計されて実装されています。

上の FileContext と FileSegment がファイル層、WindowManager と Enqueuer と Receiver がトランスポート層です。FileSegment が WindowManager からのファイル層へのインターフェイスになっています。

WindowManager の導入が一番難しかったです。このコミットで対応していますが、WindowManager にどの機能（タイマーや RTT 収集など）を含めるかを悩みました。

Add WindowManager · kawasin73/robustp@35836c5 · GitHub

CongestionControlAlgorithm による輻輳制御アルゴリズムの抽象化

TCP では様々な輻輳制御アルゴリズムが提案されています。Robustp ではそれを CongestionControlAlgorithm というインターフェイスで抽象化して輻輳制御アルゴリズムを差し替え可能にしています。

それぞれのアルゴリズムは以下の 2 つのメソッドを実装したものであり、最終的には本番では、Vegas という RTT の遅延を元にしたアルゴリズムにデータロスト時のペナルティを加えた独自のアルゴリズムを実装してコンテストに挑みました。

type CongestionControlAlgorithm interface {
    Add(status uint8, sendAt time.Time, rtt time.Duration)
    WindowSize() int
}

RTOCalclater による RTO 計算の抽象化

また、RTT（Round-Trip Time）から再送タイマーの長さ RTO（Retransmission Time Out）を算出するアルゴリズムも TCP では複数提案されています。

これも RTOCalclater というインターフェイスで抽象化して差し替え可能にしています。本番では実験する時間がなくてシンプルに RTT の倍の時間を RTO とする RTOCalclater を設定しました。

type RTOCalclater interface {
    Update(rtt float64, rttTable []float64) time.Duration
}

再送メッセージがウィンドウを溢れた場合の再送バッファ

ウィンドウサイズは RTT やメッセージのロストによって小さくなったり大きくなったりします。そのため、パケットの再送時にはウィンドウサイズが小さくなって再送できない場合があります。その場合は Enqueuer 内の再送バッファに一時的に貯めておいて、ウィンドウサイズを忠実に守るように工夫をしました。

欠損 ACK の即時再送

今回のコンテストの特徴として 1 本のケーブルのみを占有して利用します。送信したメッセージは全て同じ通信路を通るためメッセージの順序の入れ替わりはありえません。

TCP では 3 回同じ ACK を受け取ったらそれ以前のメッセージはロストしたものとして再送する高速再送アルゴリズムが提案されていますが、今回の講義では 1 つでも TransId が飛んだ ACK メッセージが返ってきた場合はそれ以前のメッセージはロストしたものとして即時に再送するナイーブな実装になっています。

もし IP ネットワークの上をメッセージが流れる場合はもうちょっと緩めの判定をする必要があります。

整合性の検査

データペイロードがノイズによって書き換わっていないかの検証は、UDP のチェックサム機能を利用して、Robustp 自体では実装していません。UDP のチェックサムで整合性の検証をサボることができたのは IP ソケットではなく UDP ソケットを選んだ理由の１つです。

ここまでの機能の設計と実装は、DMM でのインターンの時に学んだシンプルな実装を愚直に積み重ねていく経験がなかったらできていなかったと思います。DMM でインターンして身に付けることができたスキルを自分で実感しました。

Go の採用

この Robustp は Go で実装しました。

この一番の理由は クロスプラットフォーム に対応しており OS ごとの違いを抽象化して隠蔽してくれているからです。コンテストは貸与された Windows PC で行うレギュレーションがあったので、開発を macOS で行う僕としてはクロスプラットフォームは必須でした。Go では UDP ソケットは net.UDPConn という構造体で抽象化されています。

クロスプラットフォームでありながら OS に近い機能のインターフェイスを提供してくれているので今回の課題にはぴったりでした。

GC 言語なので ガバガバとメモリを確保できる気楽さ もあります。今回は速さを競い、プログラムのメモリ量などは気にしないので普段のプロダクトよりも気楽にメモリを確保するプログラムを書いていました。

Queue を C などで実現しようとすると、リングバッファや要素のずらしなどをしないといけませんが、Go ではスライスで以下のシンプルな表記で Queue が実装できて新しいバッファの確保などは Go のスライスが行なってくれます。もちろんスライスの拡張時にコピーやメモリの確保・破棄が起こるのでリングバッファほどのパフォーマンスは出ませんが、初期のプロトタイプの実装では素早く Queue を実現できます。

var queue []Item
// push
queue = append(queue, Item{})
// pop
item, queue = queue[0], queue[1:]

コンパイルされるため そこそこ速い ということもあります。もちろん C ほどの速度は出ませんが 10BASE-T を使う以上、極上の速さは求められないと考えて Go にしました。

並列・並行処理が簡単 に行えることも Go の便利な点です。1 プロセスでクライアント側の送信スレッド、受信スレッドと、サーバ側の送受信スレッドの 3 並列のプログラムにする必要があったので便利でした。

結果

60 秒間の間に送信する試行をクライアント側ポートとサーバ側ポートを変えて 2 回行いました。

結果は、1回目が 399 ファイルの転送に成功して全てのファイルの中身が壊れておらず、2 回目は 475 ファイルの転送に成功して全てのファイルが壊れていないという結果になり、堂々の 1 位を受賞しました。

3 位は TCP の上に grpc を載せて転送して 65 ファイルと 36 ファイル、4 ~ 6 位の転送ファイル数は 1 桁だったので圧勝と言えます。

僕が特に面白かったのは 2 位の aso 君で、1 回目は 347 ファイルを転送して 163 ファイルが正常なファイルで、2 回目は 799 ファイルを転送して792 ファイルが正常という驚異のパフォーマンスを見せていました。残念ながら 2 回目の試行は制限時間内に終わらなかったため参考記録ですが、驚異の結果です。

彼は、プロトコルなどなく、各ファイルを 50 KB の 2 つのブロックに分割し UDP パケットにして片っ端から送りつけ続け、全ファイルを送り終わったらまた先頭から送り直し、受け側では連続する2つの UDP パケットを結合して保存するだけでレスポンスはしないというシンプルなものでした。

何も考えないでファイルを片っ端から送り続けてそのうちのいくつかが正常ファイルだったらいいねという大胆なこんなんプロトコルじゃねーだろとも言えるシステムですが、不正ファイルが無視されるというレギュレーションを逆手に取ったスマートな方法だったと思います。これには度肝を抜かれました。

今回のケーブルはツイストペアの 1 対にだけノイズを載せます。全二重通信では、上りか下りのどちらかだけにノイズがのるため、ノイズがのらない方が上りになる 2 回目では圧倒的なパフォーマンスが得られたようです。そりゃそうか。

やり残したこと

事前学習で実質プログラムを書いていたのはキャンプが始まる前日の1日で、キャンプ中も他の講義の宿題で忙しく隙間時間で実装していたので実質 2~3 日分くらいしか実装していません。（最終日の夜は朝の5時半まで徹夜して時間を稼ぎました）

なので、もちろん効率の悪い部分だったり、やりきれなかった機能が残っています。ざっと羅列していきます。

  • writev によるメモリコピーの削減
    • ファイルデータメモリから送信バッファへコピーしているのを writev などによって効率化できれば速くなっていたはず
  • Receiver がセグメントサイズを暗黙知に依存している
    • プロトコルヘッダーはバイト単位なので任意のセグメント分けができるが、実装を簡単にするためにクライアント・サーバの両方に同じ MTU を渡し、MTU を元に共通のセグメントサイズを持つという実装にしていた
    • 実際の世界ではセグメントサイズは一定ではないはずなので任意のセグメントサイズに対応できるように区間木などのデータ構造を導入する
  • window をリングバッファにする
    • Go のスライスを使った簡易な Queue になっているのでリングバッファに書き換える
    • リングバッファによってメモリコピーやメモリアロケーションが減るはず
  • TransId のローテーション
    • 今回は 60 秒程度しか動かさないので TransId はインクリメントさせるだけだった。32 bit 整数なのでローテーションに対応する必要がある。
  • 輻輳制御アルゴリズムをもっと試す
    • Cubic とか試してみたかった
    • 体力の限界で Vegas アルゴリズムを実装するところで諦めてしまった
  • ファイル送信完了の仕組み
    • ファイル送信が完了したらサーバ側の FileContext を削除できるようにするとメモリ効率が上がる。コンテストではメモリリークは関係ないので対応していなかった
    • 実現するためにはファイル転送の開始と終了をクライアントとサーバ側で同期する必要がある。SYN/ACK, FIN/ACK などの TCP でのコネクション管理をファイルごとにする必要がある
  • ファイル名も送る
    • プロトコルの中にファイル名も送る仕組みを入れると実用的になる
  • リンク層を相手にプロトコル構築
    • そもそも IP + UDP の上に乗っかっているので MAC アドレスを直接指定して送信しあう TCP/IP スタックのようなものを実装しても良かった
    • プログラムの規模が大きくなるので実装コスト的に UDP で甘えてしまった
    • UDP ではチェックサムが異常なファイルは全て捨てていたが、データ訂正の仕組みを入れるなどもできる

最後に

疲れました。とっても。でもとても楽しかったです。

来週の月曜（8/26）からは Klab での TCP/IP プロトコルスタック自作のインターンを受講してきます。奇しくも今回の経験がめちゃめちゃ役に立ちそうです。

また、マスタリング TCP / IP を本屋さんに買いに行った時に出会ったこの本がものすごく役に立ったので共有しておきます。

TCP技術入門 ――進化を続ける基本プロトコル (WEB+DB PRESS plusシリーズ)

TCP技術入門 ――進化を続ける基本プロトコル (WEB+DB PRESS plusシリーズ)

それでは。

  1. https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/46403.pdf↩

JWT はユーザに渡すな

アーキテクチャ設計

JWT とかいてジョットと詠む。どうも、かわしんです。タイトルは釣りです。

この記事は、JWT はログアウトが大変 という内容です。以下で挙げるデメリットを許容できるなら JWT をユーザに渡してもいいと思います。

ログアウトとは、管理者による強制ログアウトや、ユーザのパスワードの変更による全トークンの無効化をさします。ログアウトによって全てまたは一部のトークンが無効化されるユースケースです。

JWT におけるログアウト

JWT はログアウトが大変です。なんかいい方法がないものかと調べていましたが、以下の記事に落ち着きました。

javascript - Invalidating JSON Web Tokens - Stack Overflow

この記事の結論としては、いい方法などない というものです。残念でした。

JWT をログアウトに対応させる方法は ブラックリストを用意する か トークンの有効期限を短くする の 2 つだけです。

NOTE : ここではマイクロサービスのことが念頭にあります。

ブラックリスト方式

ブラックリストを用意する方法では、無効化されたトークンをブラックリストに保存します。

ブラックリストのトークンは、そのトークンの一番最後の有効期限まで保存し続けます。そのあとは TTL なりで削除しても大丈夫です。

そして、各サービスは JWT の検証の際にブラックリストにアクセスして JWT が無効化されていないかをチェックします。

これでは、JWT のメリットであるトークンの検証の分散・独立・ステートレス性が失われてしまいます。

一方で、ブラックリストに保存するのは無効化されたトークンだけなので、ブラックリストのストレージサイズは全てのトークンを中央に保存するよりは小さくなります。検索も速くなるでしょう。

有効期限を短く設定する方式

トークンの有効期限を短く設定し、頻繁に JWT の更新をさせることで、JWT の更新時に無効化されたトークンの更新を弾く方法です。

JWT のメリットであるトークンの検証の分散・独立・ステートレス性は保たれます。

一方で有効期限を短くすることでどの程度短くするかによりますが、トークンの更新リクエストが頻繁に発生することになります。

また、最大のデメリットとして 即時無効化ができない という重大な欠点があります。セキュリティ的にまずいです。多分 JWT を使ってるサービスはこれを許容してるんだと思いますが、実装を手抜きするために仕様を捻じ曲げてセキュリティ的なデメリットを容認してしまうのは個人的にはしたくないです。

マイクロサービスにおける JWT

さて、マイクロサービスにおける認証を調べているとクライアントからのアクセストークンを API Gateway で内部のトークンに変換する方法がしばしば紹介されています。（Microservices Authentication and Authorization Solutions や マイクロサービスシステムにおける認証ストラテジ など）

最初はなんでこんな複雑なことをするんだと思っていたのですが、JWT のログアウトの問題を調べているうちに納得しました。

内部のトークンが JWT の場合、Gateway で利用する変換テーブルからアクセストークンを削除すれば JWT はなくなり使われなくなってしまうので、即時ログアウトが実現できます。

JWT は Gateway 内部のプライベートなネットワークの中でのみ利用されるため JWT 自体はログアウトのことを考える必要がありません。

Gateway の中でアクセストークンの変換が高速にできるのかよという疑問はありますが、そこはクラウドプロバイダーの謎テクノロジーが解決しているのでしょう。

マイクロサービスの文脈では複数のサービスを利用することやサービスが別のサービスに連鎖的にリクエストすることがありえます。各サービスが中央の認証テーブルにアクセスするコストが JWT を使うことにより削減されます。これは連携するサービスの数が多いほどこの効果は大きくなるはずです。

JWT をユーザに渡さず、プライベートネットワークの内部だけで使うという方法は一般的なユースケースに適っていて、いい JWT の使い方だと思います。Gateway 周りの実装がじょっとめんどくさそうですが。

55 日かけて OS を作った

作ったもの C

整骨院は保険がきく。どうも、かわしんです。 突発的な不調の場合は整骨院は保険が適用され 3 割負担になります。慢性的なもの（肩こり）には適用されません。

さて、5 月 20 日に以下のように宣言して作り始めた OS が、昨日ようやくひと段落したのでまとめの記事を書くことにしました。

かの有名な「30日でできる! OS自作入門」（通称 : 30日OS本）をただ写経しただけなのですが、すごく勉強になりました。

30日でできる! OS自作入門

30日でできる! OS自作入門

この本は 30 日とうたっていますが、僕は 55 日かかりました。ただ忙しくて毎日はできなかっただけなので実働自体は 30 日なのですが、これも僕の実力です。

毎日 1 日分だけを進めて全て自分の手で打ち込み、サンプルコードからのコピペはしないという縛りで実装しました。もちろん、自分が書いたコードはコピペ可としました。そうしないと辛すぎるので。

だいたい 1 日分は 2 ~ 3 時間くらいかかりました。写経するだけですが、本の中身を読んで理解したり、写し間違えによるバグを直したりすると結構時間がかかります。

いつも、学校から帰ってきて仕事を始める前の息抜きに OS を作っていましたが、結局 OS を作るだけで1日が終わってしまうことが多々ありました。そのくらい重いです。

できたもの

出来上がった OS はこれです。

f:id:kawasin73:20190714140358p:plain

僕のプロフィール JPEG 画像を表示して、インベーダーゲームを表示してるだけですが、この裏で 1 文字 1 文字打ち込んだコードが動いています。

ソースコードはこれです。自分の名前をつけようと kos (kawasinOS) と名付けましたが、めんどくさくなったので途中からは本に書いてある通り Haribote OS の名前で実装しています。

リポジトリ名が kos-sample となっているのはその名残です。-sample とつけているあたり、またもう１つ OS を作る野望が見え隠れしますが疲れてしまったので次があるかは未定です。

github.com

感想

知識だけでない実践

OS の仕組み自体は大学の授業で習っていたので、ページングやスケジューリングアルゴリズム、プロセスの仕組み、ユーザランドとカーネルランド、CPUの保護、ファイルシステムなどの理論は知っていました。しかし、それを具体的にどのように実装するかは曖昧なままでした。

多分、すでに OS のコードベースがあってそれに機能追加やパフォーマンス改善をする OS 開発をすることはできたと思いますが、何もない状態から 0 ベースで作り上げることは無理だったと思います。

この 30 日 OS 本は、本当に 0 から作り上げていく本なので、どのようにコンピュータが動いているのか全てを理解したかった僕にはうってつけでした。

コンピュータと C 言語の本質

普段ソフトウェアを作るときのインターフェースは システムコール であり OS を相手取って操作します。また、システムコールの上に構築されたライブラリの関数呼び出しも利用します。

一方で、OS を作るときのインターフェースは CPU命令 であり、CPU を相手取って操作します。PIC (Programable Interrupt Controller) や PIT (Programable Interval Timer) やマウス・キーボードなどのデバイスなど、全て CPU 経由で操作します。CPU にはそのための命令が全て用意されており、その振る舞いも全て仕様が決まっています。

ソフトウェア開発との違いはインターフェイスがすでに C 言語の関数の形で用意されている点です（もちろんその関数自体はアセンブリで作られていますが）。OS 開発で必要なインターフェイスである CPU 命令は C 言語のインターフェイスを持っていないため、自分でアセンブリを書いて C 言語で扱える関数を用意 します。この辺りは、正月に作った C コンパイラ 1 の知識が役に立ちました。

そして、自分でアセンブリによって作った関数を C 言語から呼び出して OS を構築していきます。ここで C 言語は何も機能を持っておらず、所詮メモリを操作して関数を呼び出しているだけ のことしかできないのだと理解しました。なんでも自由にできる万能な言語だと思っていた C 言語が、メモリ操作 と 関数呼び出し だけしかできない低機能野郎だったと知れたのは意外な発見でした。

この辺りの C 言語の本質、CPU と OS との関わりなどは、大学の授業では知ることができませんがこの 30 日 OS 本を読むことで理解できました。

プログラミングの方法

また、30 日 OS 本では 基本的なプログラミングの方法 が学べます。この方法は DMM でインターンしてる時 2 にメンターさんに教えてもらった方法なのですが、この本でも全く同じ方法でプログラミングされておりプログラミングの基本中の基本とはこのことなのかと思いました。

普段フレームワークありきでアプリケーションなどを作っている場合にはなんとなく作ってもなんとなく動くものができてしまいますが、正しく動くメンテナブルなソフトウェア を 0 から作る場合にはこの基本は重要です。といっても大したことではないのですが。

まず、main 関数に全ての処理を愚直に書き連ね ます（30 日 OS 本では、HariMain ですが）。関数定義などはしません。main 関数一本勝負です（あまりに冗長なところは関数化してもいいですが）。そして、実際に動かしてみて正しく動くことを確認します。実際に 30 日 OS 本では、数百行の HariMain 関数まで育てています。

次に、main 関数の中身を眺めて共通化できそうなところを探して、関数に抽出 します。その時 1 つの関数には 1 つの役割のみを担わせるように注意します。それによって main 関数が読みやすくなります。また、同じ分野の処理は同じファイルにまとめるなどの分割を行うとよりわかりやすくなります。

ここで重要なのはある関数を変更した時に別の分野の関数に影響しないことです。これにより、手戻りが無くなります。正しく役割を分割して関数に抽出できていれば別ファイルの関数群を気にする事なく機能追加を行うことができます。

関数を抽出する時には、カプセル化 して実装の詳細を隠蔽することが重要です。これはよく言われていることですが、Haribote OS のコードを見るとうまく隠蔽されているように思います。一部（ビジュアル系など）は構造体のメンバにアクセスしてしまっているので完全ではないですが、程よく隠蔽されている感じでしょうか。

関数は引数に、コンテキストとなる構造体（コンソール系の処理なら struct CONSOLE など）を 1 つと新しい状態を表すデータを複数受け取ります。コンテキストとなる構造体の中身の操作は関数に隠蔽されます。

また、重要なこととして 最適化は一番最後 に行うということがあります。まず最初は 効率が悪くてもいいのでシンプルで正しく動くコード を実直に実装します。実際、30 日 OS 本では 平気で線形探索 をバンバンします。データ構造とアルゴリズムのへったくれもないです。関数に抽出するなどした後、実際に動かして遅い部分にデータ構造とアルゴリズムを適用して最適化していきます。

ただ写経しているだけでもこれだけのプログラミングの基本を学ぶことができるので、30 日 OS 本はいい本です。

TIPS

あとは、工夫したことや、新しく 30 日 OS 本をやる人へ向けたアドバイスなどを残しておきます。

macOS での開発する時の参考

30 日 OS 本は Windows での開発を前提とされています。完成品となるサンプルコードが本に CD で添付されており、github などでも公開されています。macOS で動かしたリポジトリが以下に公開されており、各チャプターごとのスナップショットがディレクトリわけしてあって、写経に便利なので参考にしていました。

github.com

確か、何かのデータが置かれているアドレスの値が本に書かれている値ではうまく動かなくて、このリポジトリの値を参考にしたらうまくいったということがあったような気がします。どの値だったかは忘れました。

また、専用のコンパイラ（gccベースらしい）やツールなどを揃える必要がありますが、Windows 向けのツールを macOS 向けに移植されたものを利用しているようです。

残念ながらその公開リンクはリンク切れしていましたが、こちらのリポジトリで公開されていました。GitHub - HariboteOS/z_tools_osx

そのソースコードがこちらのリポジトリで公開されていたので、それをコンパイルしてツール群を利用することにしました。GitHub - HariboteOS/tolsrc: Tool set for developing Haribote OS .

しかし、Xcode 10 からは 32 bit 環境向けのコンパイルは Deprecated になっていたため、解決策を調査して報告してプルリクエストを出し、マージしてもらいました。

github.com

30 日 OS 本の最初には 起動イメージバイナリをバイナリエディタでベタ書き するという洗礼があります。これを手打ちするわけですが、バイナリエディタには iHex を利用しました。

CPU が速すぎる

この本が出版された 2006 年当時の CPU で QEMU を動かすことを想定しているため、本の各所で「動かすとカクカクする」といった表現がされています。本の中ではそれを解決するために最適化を行う章が組み込まれています。

しかし、現代の CPU は当時に比べるととても速くなり、また QEMU のソフトウェアとしての品質も上がっているためだと思うのですが、ぶっちゃけカクカクしない という場面がところどころあり、時代の進歩を感じました。

一方で、CPU が速すぎるためにうまくいかなかった ところがあります。途中のタイマーのパフォーマンス計測のあたりだったと思うのですが、for ループの中で何度も io_cli() （割り込み禁止）と io_sti() （割り込み許可）を繰り返し呼び出す部分があります。

この処理の間に別の処理（グラフィックスのメモリ書き込みなど）を行なっている分には問題はないのですが、この 2 つの関数を交互に高速に呼び出すと QEMU が猛烈に遅くなりキーボードやマウスの割り込みをほとんど受け付けなくなります。CPU が速すぎてこの2つの関数呼び出しの数が多くなりすぎたため、逆に QEMU の動作が遅くなってしまうのが意外で面白かったです。

首をいわした

写経は肉体労働です。本を机に広げてその内容をディスプレイを見ながら打ち込んで行くのですが、僕の作業環境はこんな感じでした。

f:id:kawasin73:20190714171935j:plain

本の中身を首を下に向けて読んで、また首をあげてディスプレイをみるということを繰り返していたので、おかげさまで首をいわしました。プログラマの職業病です。

最初から、左の画面にサンプルコードを表示して、正面のディスプレイに写経することをすれば首の移動は左右だったので負担も少なかったのではないかと後悔しています。皆さんも気をつけてください。

  1. macOS で動かす C コンパイラを C で作った - kawasin73のブログ↩

  2. DMM を卒業しました - kawasin73のブログ↩

Twitter をフィルタリングする Twilter を作った

Go 作ったもの

あなたとわたしと Twitter。どうも、かわしんです。

今週の頭の日曜月曜火曜の 3 日間かけて Twilter というコマンド（？）サービス（？）を作ったので、その紹介をしたいと思います。

Github リポジトリはこちらです。star をつけていただけると喜びます。

また、良かったらご自身で運用してみてください。

github.com

なぜ Twilter を作ったのか

僕のツイッターライフ

僕は Twitter を情報収集と娯楽のために利用していますが、僕の性格として全ての情報を把握しておきたいため、フォローしている人の全てのツイートを読んでいます。

残念ながら Twitter の公式アプリは、勝手にツイートの順番を入れ替えたり、勝手にオススメのツイートだけをフィルタリングして上に表示したり、時間が経ってアプリを開くと勝手にスクロール位置を最新のツイートに変えてしまったりします。

余計なお世話にも程があります。僕はタイムラインの全てのツイートを確認したいのに勝手にスクロール位置やツイートの順番を変えられると、どこまで確認していたかがわからなくなってしまいます。

そこで、僕は Tweetbot という iOS アプリを利用してタイムラインの購読をしています。

Tweetbot 5 for Twitter

Tweetbot 5 for Twitter

このアプリは有料アプリですが、タイムラインの順番やスクロール位置を勝手に変えることはしません。また、複数の iOS デバイス間でスクロール位置を同期してくれるので、家で iPad で読んで通学途中で iPhone で読むみたいな場合でもシームレスにタイムラインの確認ができます。さらに、キャッシュなどの最適化を行なっているため通信状況が悪くてもツイートの確認ができるのもいいところです。

僕みたいな異常な完璧主義の方にオススメのアプリです。

さて、全てのツイートの監視をしている僕ですが時間は有限であるため、ツイートが増えるスピードがツイートを読むスピードを超えてしまうと未読のツイートが無限に増えてしまいます。

そのため、ツイート数とその人が垂れ流す情報の有用さのバランスを元にフォローしている人を定期的に整理して、ツイートの流速調整を行っていました。

今は 100 フォロー以下を目安にやっていますが、割ときつくて、70 ~ 80 フォローくらいがちょうどいい流速なのではないかと思っています。

迎える限界

そんなツイッターライフを送っていた僕ですが、ある日僕のルールの限界を感じさせるユーザーに出会います。

重曹 さんです。この方の代表作はこれです。死ぬほど面白い。複数のツイートに分割されているのでリプライを辿っていってください。

「なかのやま」さん「NZK」さん「重曹」さんのセンスの塊の３名で構成される LINE グループのチャット内容を時々ツイートされるのですが、これが死ぬほど面白いのでフォローして LINE チャット画面を楽しみにしていました。

しかし、重曹さんの毎日のツイート数はかなり多く、僕のタイムラインが爆発してしまいました。LINE グループのツイートの数に比べてその他のツイートが多すぎるため僕のルールではフォローを外すしかないのですが、どうしてもこのセンスあふれる LINE グループの画像は見たいという板挟みの状態になってしまいました。

その時の僕の心の叫びがこれです。

ということで、Twilter を作ることにしました。

Twilter とは何か

Twilter は Twi t ter を F ilter してくれるサービスです。安直な名前なのですでに Twilter という名前のアプリは色々あるようです。しかし、それらはブラウザのエクステンションでツイッターのウェブサイトで表示を消す程度のことしかしてくれないようなので、自分で Twilter を作ることにしました。

機能としては以下の通りです。

  • 特定のユーザーのツイートを定期的に確認し、
  • 設定された条件にマッチするツイートをフィルタリングし、
  • そのツイートを連携している Twitterアカウントでリツイートする

というものです。その連携している Twitter アカウントだけを自分の Twitter アカウントからフォローすれば、フィルタリングされたツイートを自分のアカウントのタイムラインで確認することができます。

こんな形で使います。この設定では、重曹さんのリツイートでないオリジナルの画像ツイートのみをフィルタリングします。

$ export TWITTER_CONSUMER_KEY=xxxxxxxxxxxxxxxxxx
$ export TWITTER_CONSUMER_SECRET=xxxxxxxxxxxxxxxxxx
$ export TWITTER_ACCESS_TOKEN=xxxxxxxxxxxxxxxxxx
$ export TWITTER_ACCESS_TOKEN_SECRET=xxxxxxxxxxxxxxxxxx
$ export REDIS_URL=redis://user:password@host_name:6379

$ twilter -target "YTmoyashifes:and(photo,not(rt))"

このコマンド自体はフォアグラウンドで動きますので、デーモン化は docker や systemd などで行なってください。

docker イメージは https://hub.docker.com/r/kawasin73/twilter で公開しています。

注意事項

まず注意事項を記載しておきますが、リツイートを行うアカウントは 鍵アカウント（Private Account）にすることを強く推奨します。

相手ユーザーに多くのリツイートによる通知が表示されて迷惑になってしまうことを防ぐためです。鍵アカウントであれば相手ユーザーはリツイートされたことがわかりません。

また、監視できる対象ユーザーはツイートをリツイート可能なパブリックアカウントのみです。鍵アカウントは対象外ですので注意してください。

オプション一覧

オプションはこんな感じになっています。

$ twilter -h
Usage of /usr/local/bin/twilter:
  -fallback int
        start filtering tweets fallback minutes ago if no checkpoint (minutes) (default 10)
  -interval int
        interval between monitoring (minutes) (default 10)
  -target value
        list of targets. target format = "<screen_name>:<filter>[/<filter>]"  filter format = "<filter_name>[(<attribute>[,<attribute>])]"
  -timeout int
        timeout for each monitoring + retweet loop (minutes) (default 5)

本当は設定ファイルから読み込めたら便利なんですが、Docker で運用する場合に面倒になるのと、ファイルフォーマットの策定など諸々めんどくさかったので対応していません。

フィルターについて

フィルタ設定は、target オプションによって設定します。複数の target を設定することもできます。

target は <twitter_id>:<filter>[/<filter>[/...]] のフォーマットで指定します。フィルターは / によって区切ることで複数設定できます。（本当は | で区切りたかったけど、シェルのパイプと認識されてしまうため / にしました）

これらのフィルターのうち１つでもマッチするものがあればリツイートされます。

フィルターは以下の種類があります。

  • rt : リツイートされているツイート
  • qt : 引用リツイートされているツイート
  • photo : 画像付きツイート
  • video : 動画付きツイート
  • not(<filter>) : 引数のフィルターにマッチしないツイート
  • and(<filter>[,<filter>[,...]]) : 引数のフィルターの全てにマッチするツイート
  • or(<filter>[,<filter>[,...]]) : 引数のフィルターのどれか１つでもマッチするツイート

まだ実装していませんが、特定のキーワードやハッシュタグを含むツイートのフィルターも作る予定です。

ここで特に特徴的なのは、最後の not、 and、 or フィルターの 3 つだと思っています。

この3つのフィルターを組み合わせることで比較的柔軟に色々な種類のフィルターを定義することができます。また、提供するフィルターの種類もプリミティブなものだけで済むので実装コストも抑えられるのもいいところです。

Redis との連携

Twilter はデフォルトでは起動時刻から fallback に設定された分だけ前のツイートからフィルタリングを始めます。これは再起動した場合に停止していた間のツイートを取りこぼさないためです。

Twilter はオプション機能として、Redis を用意して環境変数の REDIS_URL に接続情報を登録するとツイートの確認状況を Redis に保存します。再起動した場合は Redis に保存されているツイートより後のツイートからフィルタリングを始めます。これにより無駄にフィルタリングをせずに済みます。

Redis との連携機能はオプション機能なので、 Redis がなくても Twilter を利用することができます。

Rate Limit

Twitter にはリクエスト数の Rate Limit があり一定時間にできる API リクエストの数が決まっています。

Twilter ではリクエスト数制限に引っかかった場合でも自動で適切な時間待って再送する 再送処理を実装 していますが、これは一時的にバーストした場合のためのものなのであらかじめ適切にリクエスト数の見積もりと設定をする必要があります。

ユーザーごとのツイート一覧を取得する API のリクエスト数制限は 900 requests / 15 minutes の制限と、 2019 年 6 月 19 日からは 100,000 requests / day の制限があります。

GET statuses/user_timeline — Twitter Developers

Twilter では Twitter アカウントを監視する間隔を interval オプションで指定できます。デフォルトは 10 分になっています。単位は minute です。

ユーザーのツイート一覧取得は、1 回のリクエストあたり最大 200 ツイートを取得できるので、各自それに合わせて interval の値を設定してください。

また、リツイート投稿 API のリクエスト数制限は 300 requests / 3 hours です。リツイート投稿が多くならないようにユーザーの選定とフィルターの中身を設定してください。

POST statuses/retweet/:id — Twitter Developers

アクセストークンについて

Twitter のアクセストークンを取得するには開発者アカウントが必要です。

Twitter は気づいたら開発者アカウントを取得するために 200 字の作文を複数箇所行わなければならないようになってしまっていて、ハードルが上がっていて悲しいです。が、背に腹は変えられないので頑張って英語作文しましょう。

多分、インストール手順の中で Twitter の開発者アカウントを作成するのが一番難しいステップ です。本当に悲しい。

取得したアクセストークンは、TWITTER_CONSUMER_KEY TWITTER_CONSUMER_SECRET TWITTER_ACCESS_TOKEN TWITTER_ACCESS_TOKEN_SECRET の環境変数に設定して利用します。

TWITTER_CONSUMER_KEY と TWITTER_CONSUMER_SECRET には開発者アカウントの Consumer Key と Secret を登録してください。

TWITTER_ACCESS_TOKEN と TWITTER_ACCESS_TOKEN_SECRET には、開発者アカウントから発行されたリツイートを行う鍵アカウントの Access Token と Secret を登録してください。

多くの場合は開発者アカウントの Twitter アカウントとリツイートを行う Twitter アカウントは 別のもの を使うと思います。その場合はダッシュボードから TWITTER_ACCESS_TOKEN と TWITTER_ACCESS_TOKEN_SECRET を生成することができません。

twitter-auth というコマンドラインツールがアクセストークンの発行を簡単に行なってくれるため、利用することを推奨します。

github.com

最後に

と、まぁ、こんな感じです。

Twilter は自宅の kubernetes on Mac mini サーバーで運用しています。じわざわリツイートがタイムラインに流れてくるのを「ちゃんと動いているぞ」と思いながら眺めています。

情報をうまくフィルタリングして時間を有効活用できるようになりました。

Twilter では定期的にツイッターを監視するタスクスケジューリングの部分に一年前に 管理上手のうさちゃん を作った時に作ったタスクスケジューラ htask を使っています。

github.com

うまく汎用的なライブラリを再利用できて、ニヤニヤしてます。

では、良い Twitter ライフを !

Go Conference 2019 Spring で登壇しました

Go 参加記

困った時はドキュメント、どうもかわしんです。

去る 2019 年 5 月 18 日に開催された Go Conference 2019 Spring に LT 枠で登壇してきました。

数百人規模のカンファレンスで登壇するのは初めてだったのでいい経験になりました。ありがとうございました。

題名は「俺はビッグエンディアンでテストがしたいんだ！！！」ということで発表してきました。資料はこれです。

このブログの最初の記事である 俺はビッグエンディアンでテストがしたいんだ！！！ - kawasin73のブログ の内容を LT 向けに圧縮しています。

LT は発表時間が 5 分しかないので内容を削ったりしたのですが、実際の発表では早口すぎて 4 分 10 秒で完走してしまいました。

それだったらもうちょっと話すことがあったので反省点です。

Twitter でいろんな反応をいただいて嬉しいです。

最後に僕の自己満ですが、ツイートをたくさん引用して筆を置きたいと思います。

DMM を卒業しました

参加記 ポエム

初春の令月にして、気淑く風和らぎ、梅は鏡前の粉を披き、蘭は珮後の香を薫らす 1。どうもかわしんです。新しい元号、令和の 3 日目です。頑張っていきましょう。

さて、去る平成の 31 年 4 月 25 日にインターンしていた DMM を卒業しました。1 年と 11 ヶ月でした。

簡単にいえばこれはその退職エントリーです。

DMM に行くまでの経緯

2017 年の 3 月に起業していた会社を辞めることにし、休学していた大学に復学するまで半年ほど時間があったので新しいインターン先を探していました。

それまでの 2 年間は、 Web フロントエンドや、Rails を使ったバックエンド、iOS アプリ、Android アプリなど主にアプリケーションレイヤーのエンジニアをしていました。

しかし、プログラミング技術のコモディティ化とプログラミング人口の増加する未来に危機感を覚えて 2 、技術力に特化するためにミドルウェアやライブラリを作成するエンジニアインターンを探していました。

そこで、偶然参加した DMM が主催した勉強会の懇親会で当時人事だった星野さんとこの話をお話ししてインターン先を探していることを伝えると、DMM でできるかもしれないということで話が進み、DMM の CTO 室で 6 月からインターンをすることになりました。

どうやら、当時はパブリックにインターンの募集はしていなかったらしく、僕が DMM のエンジニアインターン第一号だったらしいです。

やってたこと

CTO 室では @mah0x211 さんに僕のメンターになっていただき、2 年弱ほとんどつきっきりで僕のメンタリングをしていただきました。

やったことは大きく以下の 3 つです。2 年もいてそこまで大きな成果が出せていないのが恥ずかしいです。

  • Lua で実装された KVS を Go に移植する

メンターさんが数年前に実装していたハイパフォーマンス KVS を Go に移植することをしました。実装は僕 1 人で行い、レビューや相談をメンターさんにお願いしていました。

ここで、システムコールなど様々な基礎的なプログラミングを学びました。 最後のベンチマークを計測したりするあたりが結構辛かったです。

  • データベースの分散ルータの設計

上で実装した KVS を分散環境で使えるようにするためのルーターの実装と設計を行いました。

途中で設計をやり直して、メンターさんとホワイトボードを使いながら詰めていく形で設計をしていました。 しかし、僕の技術力不足で残念ながら設計を最後まで完成させることができませんでした。

  • ログ転送エージェント

これは、メンターさんがメインで開発しているプロダクトの一部のタスクを僕が調査したり実装したりする形式で進めました。

僕のコードや設計に細かく丁寧にレビューをしていただき、この時が一番成長したと思います。

メンターさんから学んだこと

2年間 @mah0x211 さんにとてもお世話になり、たくさんのことを学びました。

今までの自分のプログラミングはプログラミングではなかった と感じるレベルで成長して変わることができました。

エンジニアリングに対する姿勢

まず、「ないものは自分で作る」という姿勢を学びました。

それまでの僕は、まずライブラリを探してそれを組み合わせてアプリケーションを作るイメージでした。完全に仕様を満たさないものや過多な機能を提供するライブラリであっても、作るアプリの仕様をそのライブラリに合わせて変えるなど工夫して使うようにしていました。仕様がライブラリに依存してしまっていたのです。

そうではなく、もし仕様に合致するライブラリがない場合はそれを自分で作ってプロダクトに組み込む考え方とそれを達成する技術力を学びました。

また、依存ライブラリの増大はその分だけプロダクトの保守性や品質を下げる可能性があります。プロダクトに必要のない機能がライブラリに含まれることで実行環境（実行バイナリや VM の大きさ）の肥大化や低速化に繋がったり、ライブラリのアップデートに追従する労力が発生してしまいます。

そのコストとライブラリを利用することによるメリットのトレードオフを考えてライブラリ利用か自分で実装するかの意思決定をする必要があることを学びました。

次に、「なんとなくで意思決定しない」という当たり前と言えば当たり前な考え方を学びました。

どのライブラリやミドルウェアを採用するかを「周りでよく使われているから」や「今日本で流行っているから」という曖昧な理由で決めるのではなく、ドキュメントを読んだり実際に試したりして調査することの大切さを学びました。

特に、それらの情報は一次情報である公式ドキュメントを当たる必要があり、英語を読む力も（読むのは遅いですが）身につきました。 また、ドキュメントだけで理解できない場合はソースコードを読んで理解することを徹底することも学びました。

この姿勢はプログラミングの中でも必要です。外部ライブラリやシステムコールが何を返すのか、発生しうるエラーは何か全て理解した上で実装する必要があります。

特にミドルウェアの実装では、起動されてから数年単位で稼働し続けることが求められ、多少のエラーで異常終了することは許されません。全てのエラーをハンドリングするためには全てのエラーを理解する必要があります。例えば、システムコールのドキュメントとして man page をよく読むようになりました。

プログラミングの基礎

プログラミングではまず「設計が大切」であることを学びました。

大きなプロダクトを作る上では、全てのコンポーネント同士の関係を絵に描いて説明できるレベルまで設計を詰めておく必要があります。 絵が複雑になったりする場合はその設計は不十分であることが自然と浮き上がってきます。

実装を始める前に設計をしっかり固めてからでないと手戻りが発生しやすくなってしまいます。

設計は「シンプルな実装を積み上げていく」ことが大切です。

設計では神の目になったつもり大雑把な動きを捉え、その流れに対してデータ構造やアルゴリズムを適用します。最初から複雑に考えるのではなく、一番小さな単位から設計を始めて、それに肉付けしていく形で仕様を満たす設計を作り上げていきます。そのためにも極力シンプルな設計を心がけなければなりません。そのほうがあとで肉付けをしやすくなります。

また、「コンポーネントとビジネスロジックを分離する」ことを意識することも大切です。まず、ビジネスロジックに依存しない足回りとなるコンポーネントを実装し、そのコンポーネントのインターフェイスを組み合わせることでビジネスロジックを組み上げていきます。

コンポーネントがビジネスロジックに依存しないことで、ビジネスロジックの修正はコンポーネントの組み合わせ方を変えるだけで対応でき、コンポーネントの修正は必要なくなるため堅牢なソフトウェアになります。また、汎用化されたコンポーネントはライブラリとして切り出すこともできます。

「データ構造とアルゴリズムは筋肉」です。様々なデータ構造とアルゴリズムを知っていることで最適なデータ構造とアルゴリズムを導入することができ、パフォーマンスの良いミドルウェアを作ることができます。AtCoder で競技プログラミングを始めて勉強するきっかけになりました。

コーディングでは、「読みやすくシンプルなコーディング」の大切さを学びました。関数の中でもサブロジックごとにコードをまとめてコメントをつけることで読みやすくなります。例としては、boltdb の作者である Ben Johnson さんのコードは、サブロジックごとに改行で区切られてコメントが付与されており、とても読みやすいです 3 。

ドキュメンテーションの基礎

ドキュメンテーションでは「読者が上から下に引っかかりなく読むことができる」ような書き方をする姿勢を学びました。上から読んですっと読者の中に内容が入るための、前提条件や因果関係を上から順番に書いたり、表記を統一してブレないようにしたり、重複しないようにしたり、読者が疑問に思うようなことはその場で補足したりするなどの書き方を学びました。

また、僕のドキュメントの癖として英語を多用してしまう「ルー語病」がありました。英語をなるべく日本語に翻訳して書くように意識するようになりました。

あと僕のブログなどの書き物で、数字や英単語の前後にスペースが空いているのは読みやすくするメンターさんの書き方の影響です。

まとめと今後

ここまで学んだことを雑多にまとめましたが、本当に DMM で @mah0x211 さんの下で学べてよかったです。多分 DMM に行っていなかったら今の僕はありません。本当に感謝しています。

そして、来年の 4 月からは GAFA の G 社に新卒で就職する予定です。ホワイトボードでの説明やお絵かきの方法や普段の会話の中での知識などDMM で学んだことが入社面接でとても役立ちました。これで気になった人は DMM の夏のインターンもあるみたいなので是非参加してみてください。

今は大学 4 年生なのでこれから 1 年間は大学の研究に専念することになります。趣味のプロジェクトなどもできたらいいなと考えています。今後ともよろしくお願いします。

  1. 新元号は「令和」 出典は「万葉集」｜NHK NEWS WEB↩

  2. 詳しくは、作る人と使う人 - kawasin73のブログ というポエムにまとめています↩

  3. 例: bolt/db.go at fd01fc79c553a8e99d512a07e8e0c63d4a3ccfc5 · boltdb/bolt · GitHub↩

Go 言語でタイムアウト付きのファイルロックを実現する

作ったもの Go

言語の壁をぶっ壊す。どうも、かわしんです。

プロセス間の待ち合わせの手法としてファイルロックがあります。このファイルロックをタイムアウトでキャンセルすることを可能にするために以下のライブラリを作ったのでその解説をしたいと思います。

github.com

対象

今回の対象は以下の環境とします

ファイルロックを実現するシステムコール

Linux では、fcntl と flock というシステムコールでファイルロックができます。

この 2 つで獲得されるロックはカーネル内では別のものとして扱われますが、 FLOCK の 注意 にもある通り、一部のシステムでは flock と fcntl が影響を与える可能性があるため、単一のプログラムの中ではどちらかのロックのみを使うようにした方が良さそうです。（プログラムの複雑性も軽減されます）

今回の話は、fcntl と flock のどちらでも共通の話なので、fcntl を使ってデモを行います。

FCNTL

fcntl は、ファイルディスクリプタを操作するシステムコールです。

Man page of FCNTL

#include <unistd.h>
#include <fcntl.h>

int fcntl(int fd, int cmd, ... /* arg */ );

以下のコマンドを指定して、引数に flock 構造体を渡すとファイルロックができます。

ロックはファイルのバイト単位で範囲を指定してロックします。

基本はアドバイザリーロックで、頑張ると強制ロックも可能です。

これらは POSIX で標準化されています。

  • F_SETLK : ロックの獲得をノンブロッキングで行います。ロックの獲得に失敗した場合は EACCES または EAGAIN エラーが返ります。
  • F_SETLKW : ロックの獲得を行います。ロックの獲得に失敗した場合はロックの獲得ができるまで処理をブロックします。
  • F_GETLK : ロックの情報を取得します。

ロックの種類は F_RDLCK と F_WRLCK があり flock 構造体で指定します。go でいう sync.RWMutex みたいな感じですね。F_UNLCK を指定するとロックを解除します。

FLOCK

次に flock は、名前の通りファイルをロックするシステムコールです。

Man page of FLOCK

flock は BSD 系由来のシステムコールで POSIX には含まれませんが、シンプルなインターフェイスです。

ロックの範囲はファイル全体のみで、fcntl のように特定の範囲のみをロックすることはできません。

ロックはアドバイザリーロックになります。

#include <sys/file.h>

int flock(int fd, int operation);

operation に以下のオペレーションを指定してファイルをロックします。

  • LOCK_SH : 共有ロック。fcntl でいう F_RDLCK みたいな
  • LOCK_EX : 排他ロック。fcntl でいう F_WRLCK みたいな
  • LOCK_UN : ロックの解除

また、operation に論理和で LOCK_NB を指定するとノンブロッキングでロックを獲得し、指定しない場合はロックを獲得できるまで処理をブロックします。

Go 言語におけるファイルロック

Go では syscall パッケージに syscall.FcntlFlock() と syscall.Flock() が用意されています。

// fcntl のインターフェイス
func FcntlFlock(fd uintptr, cmd int, lk *Flock_t) error

// flock のインターフェイス
func Flock(fd int, how int) (err error)

これらはあくまでもシステムコールをラップしただけのものなのでタイムアウトの機能を追加する必要があります。

github で file lock でタイムアウト付きのファイルロックの Go の実装を調べていると以下の2つのライブラリを探すことができました。

github.com/gofrs/flock

GitHub - gofrs/flock: Thread-safe file locking library in Go (originally github.com/theckman/go-flock)

gofrs/flock には、TryLockContext というメソッドがあり context.Context を利用してタイムアウトやロックの中断を実現できます。

func (f *Flock) TryLockContext(ctx context.Context, retryDelay time.Duration) (bool, error)

しかし、その内部実装は syscall.Flock をノンブロッキングモードで呼び出し、成功するまで for 文で retryDelay で設定された間隔で呼び出し続けるものになっています。

これでは、カーネル内部のロックキュー に入らないため、 複数プロセス間のロックの順序が崩れてしまいます 。(参考 : linux - flock locking order? - Stack Overflow)

また、ロックの獲得まで 最大で retryDelay の分の遅延が発生する ことになります。

github.com/jviney/go-filelock

GitHub - jviney/go-filelock

jviney/go-filelock では、Obtain 関数にタイムアウトの時間を渡してタイムアウト付きのファイルロックができます。

func Obtain(path string, timeout time.Duration) (lock *Lock)

しかし、その内部実装は syscall.Flock をブロッキングモードで実行する goroutine を立ち上げて、その終了とタイムアウトを Obtain 関数内で select 文で待つものでした。

タイムアウトするとさらに新しい goroutine を立ち上げ、その goroutine 内でロックが獲得できるまで待って即座にロックを開放するようにしています。

      // We hit the timeout without successfully getting the lock.
      // The goroutine blocked on syscall.Flock() is still running
      // and will eventually return at some point in the future.
      // If the lock is eventually obtained, it needs to be released.
      go func() {
        if err := <- flockChan; err == nil {
          releaseFlock(file)
        }
      }()

https://github.com/jviney/go-filelock/blob/ec38a70cdf163d7c9f50a224f4c422f8a1847d7a/filelock.go#L48-L56

ロックが獲得できなかった場合、 ロック開放用とロックを取得する 2 つの goroutine が残り続けます 。

また、ロックを獲得中のファイルディスクリプタを閉じるとロックが獲得するまでブロックします。 ファイルディスクリプタを解放することができない ためファイルディスクリプタも残り続けます。

これではリソース管理の面からガバガバです。

どうやってファイルロックを中断するか

上の 2 つのライブラリはファイルロックの直接的な中断ができなかったためにこのような課題が残っていました。

この点を解決するために、ここでどうやってブロックしているファイルロックを中断するかを考える必要があります。

答えは シグナル です。

ブロッキングするシステムコールはシグナルを受信することによってブロックが解除され EINTR エラーを返すようになっています。（タイムアウトという文脈では alarm を使うことが多そうです）

Timeouts for system calls are done with signals. Most blocking system calls return with EINTR when a signal happens, so you can use alarm to implement timeouts.

https://stackoverflow.com/questions/5255220/fcntl-flock-how-to-implement-a-timeout#answer-5255473

そのためシグナルを送信してロック獲得処理に EINTR を発生させることでファイルロックのタイムアウトや中断を実現できます。

シグナルによる割り込みを Go でも実現させる

シグナルを自分のプロセスに送れば解決するはずなのですが、Go では以下の 2 つの障壁があります。

  • SA_RESTART によって EINTR がそもそも発生しない
  • シグナルを pthread_kill 使って送信しないといけない

それぞれ順をおって解説します。

SA_RESTART によって EINTR がそもそも発生しない

SA_RESTART は sigaction に設定するフラグで、このフラグが設定されると、ブロッキングしているシステムコールがシグナルによって中断された場合でも EINTR を返さずにブロッキングを続行するようになります。

参考 : シグナルハンドラーによるシステムコールやライブラリ関数への割り込み

Go ではランタイムによって全てのシグナルに対して SA_RESTART が設定されています。これにより標準ライブラリは EINTR のエラーハンドリングをしなくてよくなります。（確かに標準ライブラリを読んでいると EINTR のハンドリングをしていないことに気づきます）

Also, the Go standard library expects that any signal handlers will use the SA_RESTART flag. Failing to do so may cause some library calls to return "interrupted system call" errors.

https://golang.org/pkg/os/signal/#hdr-Go_programs_that_use_cgo_or_SWIG

これは Go のランタイムの問題なのでどうしようもありません。Go 言語のレイヤーでは解決できません。

ここで、「 言語の壁をぶっ壊す 」CGO の出番です。Go 言語を壊していきます。

CGO によって直接 C 言語で sigaction を実行しシグナルハンドラを設定することで Go のランタイムが設定した SA_RESTART を上書きします。

この時点で Windows とかの可搬性は捨ててます。すみません。

void sighandler(int sig){
    // empty handler
}
static struct sigaction oact;

static int setup_signal(int sig) {
    struct sigaction act;
    // setup sigaction
    act.sa_handler = sighandler;
    act.sa_flags = 0;
    sigemptyset(&act.sa_mask);
    // set sigaction and cache old sigaction to oact
    if(sigaction(sig, &act, &oact) != 0){
        return errno;
    }
    return 0;
}

シグナルを pthread_kill 使って送信しないといけない

さて、SA_RESTART を上書きした上で自身のプロセスにシグナルを送るとブロッキングしているファイルロックを中断できる場合とできない場合が出てきます。

それは、事前に signal パッケージの signal.Ignore() や signal.Notify() などを呼び出した時です。

これらのメソッドを呼び出した時に Go のランタイムは signal mask thread を立ち上げそのスレッドが全ての sigaction の登録を行います。(具体的には ensureSigM という関数)

go/signal_unix.go at 2c5363d9c1cf51457d6d2466a63e6576e80327f8 · golang/go · GitHub

これによって プロセススコープに送られたシグナル はランタイムの signal mask thread に送られてしまいます。その場合は別のスレッドでファイルロックをブロックしているためシグナルが届かず EINTR も発生しません。

この解決策は スレッドスコープでシグナルを送る ことです。

残念ながら Go 言語は OS のスレッド意識させないような作りになっており、スレッドに対して直接シグナルを送ることはできません。

そこで、「 言語の壁をぶっ壊す 」CGO の出番です。どんどん Go 言語を壊していきます。

C では、pthread_kill という関数があり特定のスレッドにシグナルを送ることができます。

static pthread_t tid;

static int setup_signal(int sig) {
    ...
    // set self thread id
    tid = pthread_self();
    ...
}

static int kill_thread(int sig) {
    // send signal to thread
    if (pthread_kill(tid, sig) == -1) {
        return errno;
    }
    return 0;
}

これでブロックしているファイルロックを中断させることができるようになりました。

github.com/kawasin73/gointr を作った

これまでの知見を元にブロッキングしている処理を中断させる処理をライブラリ化しました。

github.com

使い方としては

  1. 中断に使うシグナルを指定して gointr.Intruptter を作成する (gointr.New(syscall.SIGUSR1))
  2. ブロッキングする処理を行う goroutine を立ち上げて intr.Setup() を実行してから、ブロッキング処理を行う
  3. ブロッキング処理が終わったら intr.Close() する
  4. もし、中断する場合は intr.Signal() を呼び出す

となります。中断された場合は EINTR がブロッキングするシステムコールから返ってきます。

注意点

注意点としては、以下のことが挙げられます。気をつけてください。

  • グローバル変数を内部で使っているため 複数のブロッキング処理の中断に対応していない
  • signal パッケージの関数を呼び出すと上書きした sigaction が上書きされ直されるので ブロッキング処理中は signal パッケージの関数を呼んではいけない
  • CGO を使っている

Example

package main

import (
    "fmt"
    "io"
    "log"
    "os"
    "os/signal"
    "syscall"
    "time"

    "github.com/kawasin73/gointr"
)

// lock locks file using FCNTL.
func lock(file *os.File) error {
    // write lock whole file
    flock := syscall.Flock_t{
        Start:  0,
        Len:    0,
        Type:   syscall.F_WRLCK,
        Whence: io.SeekStart,
    }

    if err := syscall.FcntlFlock(file.Fd(), syscall.F_SETLKW, &flock); err != nil {
        // FCNTL returns EINTR if interrupted by signal on blocking mode
        if err == syscall.EINTR {
            return fmt.Errorf("file lock timeout for %q", file.Name())
        }
        return &os.PathError{Op: "fcntl", Path: file.Name(), Err: err}
    }
    return nil
}

func main() {
    signal.Ignore()

    file, err := os.Create("./.lock")
    if err != nil {
        log.Panic(err)
    }

    // init pthread
    intr := gointr.New(syscall.SIGUSR1)

    // init error channel
    chErr := make(chan error, 1)

    // setup timer
    timer := time.NewTimer(3 * time.Second)

    go func() {
        // setup the thread signal settings
        if terr := intr.Setup(); terr != nil {
            chErr <- terr
            return
        }
        defer func() {
            // reset signal settings
            if terr := intr.Close(); terr != nil {
                // if failed to reset sigaction, go runtime will be broken.
                // terr occurs on C memory error which does not happen.
                panic(terr)
            }
        }()
        // lock file blocking
        chErr <- lock(file)
    }()

    for {
        select {
        case err = <-chErr:
            timer.Stop()
            if err == nil {
                log.Println("lock success")
            } else {
                log.Println("lock fail err", err)
            }
            // break loop
            return

        case <-timer.C:
            log.Println("timeout")

            // send signal to the thread locking file and unblock the lock with EINTR
            err := intr.Signal()
            log.Println("signal")
            if err != nil {
                log.Panic("failed to kill thread", err)
            }
            // wait for lock result from chErr
        }
    }
}

最後に

以上です。ありがとうございました。

ぶっちゃけ、ここまで厳密にするなら Go を使わなくていいと思うし、多分自分が使うとしたら github.com/gofrs/flock を使う。