GolangでgoblinというURLルーターを自作した

アプリケーション

概要

GolangでURLルーターを自作したので実装するまでの過程をメモしておく。

準備

URLルーターを実装する際に行った下準備をまとめる。

データ構造とアルゴリズム

URLをどのようにマッチングさせるか、というロジックについて検討する。

多くのライブラリでは、データ構造として木構造がよく扱われているので、どんな種類の木構造を採用するかを考えてみた。

文字列探索に特化した木の中で、時間的・メモリ的計算量がよりベストなものを選定しようとすると、基数木というのが良さそうに見えるので最初はそれを採用しようとしていたのだが、実装が難し過ぎて挫折をした。

もう少し身近でシンプルなものをということでトライ木を採用することにした。

net/httpのコードリーディング

net/httpが持つマルチプレクサの拡張として実装を行うため、内部の仕組みについてある程度理解しておく必要がある。

GolangのHTTPサーバーのコードリーディングを参照。

色んなrouterの実装を読む

参考>リポジトリ参照。

その他

過去URLルーティングについてまとめた記事。

bmf-tech.com/posts/tags/URLルーティング

実装

github.com - goblinを参照。

基本はトライ木を使いやすい形に変えていくだけではあるのだが、パスパラメータの扱いに何度か格闘した。 正規表現の対応はそれほど面倒ではなく、DSLを用意してあげるだけでどうにかなるので、DSLの扱いにセンスが問われる。

実装過程では、テストを並行して書いたり、ステップ実行のデバッグを繰り返したりして、データ構造が常にどう変化しているかキャッチしながらやっていたので、段々脳内デバッグ力が上がっていたような気がする。

普段あまり書かないようなロジックなので、コーディングの良いトレーニングになったのは間違いなさそう。

今後の課題はリポジトリに起票してあるissueの通りで、暇な時にでもブラッシュアップを重ねようかと思っている。

参考

リポジトリ

設計とか実装の参考にさせてもらったリポジトリ

その他

実装時に参照した記事。