12.路由树-总结与面试要点

本节课工程结构如下:

(base) yanglei@yuanhong 17-summary % tree ./
./
├── context.go
├── handleFunc.go
├── httpServer.go
├── httpServer_test.go
├── matchNode.go
├── node.go
├── router.go
├── router_test.go
└── serverInterface.go

0 directories, 9 files

PART1. 注册路由的注意事项

已经注册了的路由,无法被覆盖.例如/user/home注册两次,会冲突
path必须以/开始并且结尾不能有/,中间也不允许有连续的/
不能在同一个位置注册不同的参数路由.例如/user/:id和/user/:name冲突
不能在同一个位置同时注册通配符路由和参数路由.例如/user/:id和/user/*冲突
同名路径参数,在路由匹配的时候,值会被覆盖.例如/user/:id/abc/:id,那么/user/123/abc/456,最终id = 456
- TODO:这里是可以实现把2个id都记录下来的,只需要将matchNode.pathParams的类型修改为map[string][]string即可.下去自己试一下
- TODO:这种情况也可以考虑panic掉

把以上内容作为注释放在addRoute()方法上,那么但凡用户发现panic的时候看一眼这个注释,都知道出了什么问题

router.go:

// AddRoute 注册路由到路由森林中的路由树上
// 其中path为路由的路径.该路径:
// 1. 不得为空字符串
// 2. 必须以"/"开头
// 3. 不能以"/"结尾
// 4. 不能包含连续的"/"
// - 已经注册了的路由,无法被覆盖.例如`/user/home`注册两次,会冲突
// - `path`必须以`/`开始并且结尾不能有`/`,中间也不允许有连续的`/`
// - 不能在同一个位置注册不同的参数路由.例如`/user/:id`和`/user/:name`冲突
// - 不能在同一个位置同时注册通配符路由和参数路由.例如`/user/:id`和`/user/*`冲突
// - 同名路径参数,在路由匹配的时候,值会被覆盖.例如`/user/:id/abc/:id`,那么`/user/123/abc/456`,最终`id = 456`
func (r *router) addRoute(method string, path string, handleFunc HandleFunc)

PART2. 为什么在注册路由用`panic`?

可以看到在addRoute()方法中有大量的panic出现.

那么问题来了:

可不可以返回error?
应不应该返回error?

2.1 可不可以返回`error`?

可以返回,但没必要.因为框架的使用者根本不会去处理的.注册路由都失败了,谁还有空去处理注册路由的报错信息呢?

2.2 应不应该返回`error`?

其实不应该.从框架使用者的角度上来看,用户必须完成注册路由的步骤,才能启动HTTPServer.那么在注册路由时,采用panic就是没问题的,因为这时应用还没运行.

注册路由时panic总好过应用启动了再panic.

PART3. 路由树是线程安全的吗?

显然不是线程安全的.我们要求用户必须要注册完路由才能启动HTTPServer.而正常的用法都是在启动之前依次注册路由,不存在并发场景.

换言之,这是一个顺序写并发读的场景.并不会出问题.并发读写才会引入线程安全问题.

至于运行期间动态注册路由,没必要支持.这是典型的为了解决1%的问题,引入99%的代码.

之所以不将路由树做成线程安全的,也是为了性能,因为一旦涉及到加锁/原子操作的情况,性能就下来了.

PART4. 面试要点(一)

4.1 路由树算法的实现?

核心就是前缀树.前缀的意思就是,两个节点共同的前缀,将会被抽取出来作为父节点.在我们的实现中是按照/来切割,每一段作为一个节点.

4.2 路由匹配的优先级?

本质上这是和Web框架相关的.在我们的设计里面是静态匹配 > 路径参数 > 通配符匹配.但实际上这个规则意义不大,因为路径参数和通配符匹配是互斥的

4.3 路由查找会回溯吗?

这也是和Web框架相关的,我们在课程上是不支持的.在这里可以简单描述可回溯和不可回溯之间的区别,可以是用课程中的例子/user/123/home和/user/*/*.课程中不支持是因为这个特性非常鸡肋

4.4 Web框架是怎么组织路由树的?

一个HTTP动词就是一颗路由树.也可以考虑所有HTTP动词共用一颗路由树,每个节点标记自己支持的HTTP方法.前者是比较主流的

TODO:第二种可以尝试去写

PART5. 面试要点(二)

5.1 路由查找的性能受什么影响? 或者说怎么评估路由查找的性能?

核心是看路由树的高度,次要因素是路由树的宽度(想想我们的node.children字段).

但是我们实现的时候node.children字段用的是map来实现的,所以宽度对我们的实现影响不大.但是如果使用slice实现,宽度影响就比较大了.

GIN的最长前缀树,则树会更高;我们的实现中,树会更宽.

如果你不是为了装逼,不要写GIN的那种路由树,因为代码很复杂,且很难读懂.

5.2 路由树是线程安全的吗?

严格来说也是跟Web框架相关的.大多数都不是线程安全的,这是为了性能.所以才要求大家一定要先注册路由,后启动Web服务器.如果你有运行期间动态添加路由的需求,只需要利用装饰器模式,就可以将一个线程不安全的封装为线程安全的路由树.

5.3 具体匹配方式的实现原理?

课程上我们实现了静态匹配、通配符匹配和路径匹配，作业里面要求大家照着实现一个正则匹配.其实核心就是划定优先级,然后一种种匹配方式挨个匹配过去.

Last updated 2 months ago