Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
GolangでURLルーターをつくった
Search
bmf_san
May 07, 2020
Programming
390
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
GolangでURLルーターをつくった
bmf_san
May 07, 2020
Transcript
32 slides
GolangでHTTP Routerをつくった @bmf_san
https://speakerdeck.com/bmf_san/urlruteinguwotukuruepisodo1
続編にして完結編
⽬次 ・HTTP Routerの仕組み ・データ構造 ・Golangでの実装
Github https://github.com/bmf-san/goblin
1 HTTP Routerの仕組み
HTTP Router is 何? ・リクエストされたURLやHTTP Methodに応じて、 処理の実⾏を制御するアプリケーション ・URLとアプリケーションの処理を結びつける
処理のイメージ
パターン Routerが解釈するルーティングのパターン ・静的なルーティング →/foo/barが/foo/barに⼀致 ・動的なルーティング →/foo/bar/123が/foo/bar/:idに⼀致
2 データ構造
データ構造を考える ・Router≒⽂字列マッチング ・URLの階層構造と相性が良いデータ構造 →⽊構造
⽊構造
トライ⽊(プレフィックス⽊) ・⽂字列の集合を扱う⽊構造の⼀種 ・ざっくりいうと、⽂字列を探索しやすいように⽊に 格納したやつ ・ex. サジェスト、IPアドレス探索、形態素解析とか に応⽤が⾒られる
トライ⽊を知る ・https://www.cs.usfca.edu/~galles/visualization/ Trie.html →アルゴリズムのビジュアライズ ・https://github.com/bmf-san/road-to-algorithm- master/tree/master/data_structures/tree/trie →参照実装かいた
オレオレトライ⽊ ・ルーティングの定義を元にオレオレトライ⽊をつく る(これが結構試⾏錯誤した..) ・トライ⽊の定義に当てはまるのかちょっと⾃信ない けど多分トライ⽊、いやギリトライ⽊だと思う
オレオレトライ⽊ • /foo/ • /baz/ • /foo/bar/ • /foo/:name[string]/ •
/foo/bar/:id[int] ˞ύϥϝʔλͷఆٛͷํ%4-ͳͷͰࣗ༝
ͦΜͳͰେৎ͔ʁ
⼤丈夫だ、問題ない。でも・・ ・時間的計算量(処理時間)、空間的計算量(メモ リ)をより最適化するなら、当然選択肢はある ・Radix Tree https://www.cs.usfca.edu/~galles/ visualization/RadixTree.html
3 Golangでの実装
GolangでのURLパターンマッチの 仕組み、お作法
net/http ・net/httpのインターフェースついて、HTTPServer を⽴てるコードの実装から内部処理を読んでおく →net/httpのmuxを拡張する ・cf. https://bmf-tech.com/posts/GolangのHTTP サーバーのコードリーディング
muxとは ・マルチプレクサ。多重器、多重装置、多重化装置、合波器。 ・2つの⼊⼒から1つの出⼒を得るもの ・雑にいうとURLのパターンマッチするやつ ・net/httpではServeMux構造体(URLパターンマッチやる 君) cf. https://golang.org/pkg/net/http/#ServeMux
net/httpのmuxの拡張 ・http.ListenAndServeから処理をたどる →addressとHandlerインターフェースを満たしたhandlerを引数に 取る。内部的には、handlerの呼び出し=ServeHTTPの呼び出しとな る cf. https://golang.org/src/net/http/server.go?s=96538:96593#L3074 ・ServeMuxはServeHTTPを実装しており、Handlerインターフェー スを満たしている cf.
https://golang.org/pkg/net/http/#ServeMux.ServeHTTP
)BOEMFS*OUFSGBDF 何を拡張すればいい? IUUQ-JTUFO"OE4FSWF "EESFTT )BOEMFS 4FSWF)551 ཁ͢Δʹ͜Εʂ
こんな感じ ・https://github.com/bmf-san/goblin/blob/master/ router.go#L60 ࣗલͷ63-ύλʔϯϚον
⾃前のURLパターンマッチの実装
オレオレトライ⽊の実装 ・オレオレトライ⽊を実装に落とし込む →トライ⽊の応⽤。パラメータ部分の実装がちょっ と⾯倒 ・コアの実装 https://github.com/bmf-san/goblin/blob/master/trie.go
再帰処理との闘い ・つらい ・テストとデバッガで頑張れば 乗り越えられる
Example ・参照実装 https://github.com/bmf-san/goblin/blob/master/_examples/main.go ・トレイリングスラッシュは気にしないで⼤丈夫なは ず ・静的ファイルはhttp.ServeFile使って問題なく返せ るはず
ベンチマーク ɾࢀর https://github.com/bmf-san/goblin#benchmark →ͪΌΜͱੳͰ͖͍ͯͳ͍͚Ͳɺ΅ͪ΅ͪͳײ͢͡Δ ɾgoRouterͷϕϯνϚʔΫੳ https://github.com/julienschmidt/go-http-routing-benchmark
Issue・PR・Star
参考 ・雑まとめ GolangͰgoblinͱ͍͏URLϧʔλʔΛࣗ࡞ͨ͠ URLϧʔςΟϯάࣗ࡞ೖɹΤϐιʔυ̍ URLϧʔςΟϯάࣗ࡞ೖɹΤϐιʔυ̎ GolangͷHTTPαʔόʔͷίʔυϦʔσΟϯά A Trie implementation in
Golang
More Decks by bmf_san
See All by bmf_san
桃太郎で始めるRego入門‐今日から使えるRegoの基本編
bmf_san
0
110
完璧を求めない意思決定-アクセス制御基盤における制約との向き合い方
bmf_san
5
21k
AAPについて調べてみた
bmf_san
0
170
レーダーをつくる
bmf_san
0
100
契約テストとPactについて
bmf_san
0
140
5分でわかるSLO
bmf_san
2
200
権限について考える
bmf_san
2
200
自作HTTPルーターから新しいServeMuxへ
bmf_san
3
1.9k
古くなってしまったPHPフレームワークとPHPのバージョンアップ戦略
bmf_san
1
540
Other Decks in Programming
See All in Programming
Spec-Driven Development - Why Vaadin Is the Perfect Fit
simas
PRO
0
260
Claude Codeのおかげでやりたいことがやれるようになったんだよォー!
sms_tech
0
150
仕様駆動開発入門 (何を作るかを先に決めて渡す) | 目指せ Kiro マスター 05
inariku
PRO
2
190
AI駆動開発4年目の現在地(『あなたはFDEになるべきか?』イベント資料)
kumaiu
0
660
LLM 101
dalinaum
0
510
Zero-Tap Sign-In対応、結局何をすればいいの?
mitohato14
0
2.4k
Claude Code ハーネスDeep Dive – 君はどこまで制御する? -
takateeen_knj
6
6.1k
Augmenting AI with the Power of Jakarta EE
ivargrimstad
0
370
将来の標準フォーマッター?ktfmtを深堀る
t45k
0
220
複数ドメインを一つのアプリに統合するFlutterの設計と運用_FlutterKaigi2026登壇資料(須永高弘)
takahirosunaga
0
200
AIが生成したコードは読むべきか?抽象化設計とコードの品質保証 / abstraction-design-and-quality
minodriven
16
9.4k
はじめてのPLATEAU
nokonoko1203
1
660
Featured
See All Featured
HDC tutorial
michielstock
2
1k
How to Grow Your eCommerce with AI & Automation
katarinadahlin
PRO
2
350
Making Projects Easy
brettharned
120
6.9k
Deep Space Network (abreviated)
tonyrice
0
420
What the history of the web can teach us about the future of AI
inesmontani
PRO
3
810
ラッコキーワード サービス紹介資料
rakko
5
5.9M
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
9
1.7k
Product Roadmaps are Hard
iamctodd
55
13k
Exploring anti-patterns in Rails
aemeredith
4
570
Producing Creativity
orderedlist
PRO
348
41k
Effective software design: The role of men in debugging patriarchy in IT @ Voxxed Days AMS
baasie
1
620
Primal Persuasion: How to Engage the Brain for Learning That Lasts
tmiket
0
520