2014年5月21日 星期三

R3 - 極致效能的 URL Router Library

其實幾年前就有想用 DFA 做 URL router 的想法,只是為了有趣,所以當時用 PHP 寫了一個簡單的 RE parser,但是用 PHP 寫成的 parser 實在太醜了,而且在動態語言裡面這樣實作也不會快到哪裡去,於是後來就作罷。

當時也另外看了 Journey 的原始碼,發現 Rails/Journey 在處理 Regular Expression 的路徑比對也只是把一整個 Regular Expression 路徑放到另外一個 array 裡面去循序比對罷了,並不會塞到 DFA 裡面.... 看到這邊其實就想丟鍵盤了,如果你只有 字串拿來做 DFA,那倒不如就直接用 Ruby 內建的 Hash Table 查表算了。

後來一直沒有動機繼續把這個想法做完,一方面,用 C parsing regular expression 實在太累人,且就算實作了,考量到開發時間有限,也不可能完整支援所有的 RE features,所以就折衷先寫了一個非常 Tiny 的 library - Pux 來解決 PHP + Nginx/Apache routing overhead 的問題。

再後來,有次跟 Cindy 討論發現其實可以用 prefix/suffix tree 來做比對。而 prefix tree 很適合這個問題。但 RE 還是沒有辦法很完美的整合進來。

睡了一晚,想到 RE 其實可以拆成個別的 node 做 partial match 即可,這樣就可以用很簡單的資料結構的解決掉問題,不用自己做 Regular Expression 的引擎,只要把部分字串交給 PCRE 接手即可,而且還可以得到非常不錯的效能。

後來用了一些零零碎碎的時間總算把雛形寫完了,接著就拿 stevegraham/rails 的 PR 裡的測試資料簡單評測了一下。發現新引擎處理比對的速度,每秒約可以處理一千兩百萬到一千三百萬個路徑 (12M~13M) 比對 ( http://c9s.github.io/r3/bench.html ) ,而 Journey 約處理九千個路徑左右 (約一千多倍的差異)。

現在,只要是 3P 語言都可以透過跟 R3 binding 得到相當不錯的效能!歡迎大家來實作 R3  binding:

專案網址: http://github.com/c9s/r3


目前 Cindy 寫的 Perl 版本的 R3 CPAN module 已經放上 CPAN :https://metacpan.org/pod/Router::R3

當 Rails/Journey 還在 9326 i/s 繞,Perl 版的 R3 跑起來就有 1,662,383 i/s。

當然你可能會說,Router 有需要這麼快嗎?Well 其實這個專案基本上只是為了實驗加興趣而實作的,雖是實驗,但所有的 Feature 都透過 C 的 Check Unit Testing 做測試,使用 autotools 做 feature testing, project building。

R3 後續在 Hacker News 以及 Twitter 上引起討論。 如:



日本的 mattn san 也做了一份 Perl Router 的 Benchmark,與號稱最快的 Perl Router Module 比較: