Начало работы с Golang Web (2): как реализовать маршрутизацию RESTful

• Начало работы с Golang Web (1): понимание Http-сервера сверху донизу
• Начало работы с Golang Web (2): как реализовать маршрутизацию RESTful
• Начало работы с Golang Web (3): как элегантно спроектировать промежуточное ПО
• Начало работы с Golang Web (4): как разработать API

Резюме

существуетпредыдущий постВ мы говорили о том, как реализовать Http-сервер в Golang. Но в итоге мы можем обнаружить, что хотяDefaultServeMuxОн может выполнять функцию распределения маршрутов, но его функция также несовершенна.

Зависит отDefaultServeMuxНевозможно сделать маршрутную раздачуRESTfulstyle API, у нас нет возможности определить методы, требуемые запросом, и нет способаAPIдобавить в путьqueryпараметр. Во-вторых, мы также надеемся сделать поиск маршрута более эффективным.

Итак, в этой статье мы проанализируемhttprouterЭтот пакет изучает, как он реализует функции, которые мы упомянуты выше, из уровня исходного кода. И, для самых важных в этом пакетеПрефиксное дерево, который будет объяснен в виде комбинации картинок и текстов.

1 использование

Мы также начинаем с того, как его использовать, и исследуем сверху донизуhttprouter. Давайте сначала посмотрим на небольшой пример в официальной документации:

package main

import (
    "fmt"
    "net/http"
    "log"

    "github.com/julienschmidt/httprouter"
)

func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
    fmt.Fprint(w, "Welcome!\n")
}

func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
    fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}

func main() {
    router := httprouter.New()
    router.GET("/", Index)
    router.GET("/hello/:name", Hello)

    log.Fatal(http.ListenAndServe(":8080", router))
}

На самом деле, мы можем обнаружить, что практика здесь и использование собственныхnet/httpПакетный подход аналогичен. Сначала необходимо зарегистрировать соответствующий URI и функцию, другими словами, согласовать маршрут и процессор.

При регистрации используйтеrouter.XXXметод для регистрации соответствующего метода, такого какGET,POSTи Т. Д.

После регистрации используйтеhttp.ListenAndServeНачните слушать.

Что касается причин, мы подробно расскажем об этом в следующих главах, а сейчас нам нужно только сначала понять практику.

2 Создать

Давайте посмотрим на первую строку кода, мы определяем и объявляемRouter. Вот посмотрите на этоRouterСтруктура , другие атрибуты, не относящиеся к этой статье, здесь опущены:

type Router struct {
	//这是前缀树，记录了相应的路由
	trees map[string]*node
	
	//记录了参数的最大数目
	maxParams  uint16

}

после создания этогоRouterПосле структуры мы используемrouter.XXXметод регистрации маршрута. Продолжайте видеть, как регистрируется маршрут:

func (r *Router) GET(path string, handle Handle) {
	r.Handle(http.MethodGet, path, handle)
}

func (r *Router) POST(path string, handle Handle) {
	r.Handle(http.MethodPost, path, handle)
}

...

Здесь тоже длинный список методов, все они одинаковые, вызывающие

r.Handle(http.MethodPost, path, handle)

Сюда. Давайте еще раз посмотрим:

func (r *Router) Handle(method, path string, handle Handle) {
	...
	if r.trees == nil {
		r.trees = make(map[string]*node)
	}

	root := r.trees[method]
	if root == nil {
		root = new(node)
		r.trees[method] = root

		r.globalAllowed = r.allowed("*", "")
	}

	root.addRoute(path, handle)
	...
}

В этом методе также опущены многие детали. Мы остановимся только на том, что имеет отношение к этой статье. Мы видим, что в этом методе, еслиtreeЕсли он не был инициализирован, сначала инициализируйте егопрефиксное дерево.

Затем мы замечаем, что это деревоmapструктура. Другими словами, метод соответствует дереву. Затем, соответствующий этому дереву, вызовитеaddRouteметод, положитьURIи соответствующийHandleСохраните его.

3 Префиксное дерево

3.1 Определения

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。 Типичным приложением является подсчет, сортировка и сохранение большого количества строк (но не только строк), поэтому поисковые системы часто используют его для статистики частотности текстовых слов. Его преимущества: использование общего префикса строк для сокращения времени запроса, минимизация ненужных сравнений строк, эффективность запросов выше, чем у хеш-деревьев.

Проще говоря, это искать что-то, пока вы идете по определенному пути дерева, вы можете это найти.

Например, в поисковой системе вы вводитеКай:

У него будут эти ассоциации, которые тоже можно понимать как префиксное дерево.

Другой пример:

В этомGETПрефиксное дерево метода содержит следующие маршруты:

• /wow/awesome
• /test
• /hello/world
• /hello/china
• /hello/chinese

К этому моменту вы должны понимать, что в процессе построения этого дереваЛюбые два узла, если они имеют одинаковый префикс, одинаковые части будут объединены в один узел..

3.2 Построение диаграммы

сказано вышеaddRouteМетод является методом вставки этого дерева префиксов. Предполагая, что число теперь пусто, здесь я намерен графически проиллюстрировать построение дерева.

Предположим, что три маршрута, которые нам нужно вставить:

• /hello/world
• /hello/china
• /hello/chinese

(1) Вставка/hello/world

Поскольку в этот момент дерево пусто, его можно вставить напрямую:

(2) Вставка/hello/china

В это время было обнаружено/hello/worldи/hello/chinaиметь тот же префикс/hello/.

Затем, оригинал/hello/worldузел, разделите его, а затем вставьте узел, который нужно вставить/hello/china, усекая ту же часть, что и/hello/worldдочерний узел .

(3) Вставка/hello/chinese

В этот момент нам нужно вставить/hello/chinese, но обнаружил, что/hello/chineseи узел/hello/имеет общий префикс/hello/, так что давайте проверим/hello/дочерние узлы этого узла.

Обратите внимание, что в узле есть свойство, называемоеindices. Он записывает первую букву дочерних узлов этого узла, которую нам удобно найти. нравится/hello/Узел, егоindicesзначениеwc. И узел, который мы хотим вставить,/hello/chinese, после удаления общего префикса,chineseПервая буква такжеc, так что мы входимchinaэтот узел.

В это время вы обнаружите, что ситуация вернулась к нашей первоначальной вставке/hello/chinaситуация на тот момент. В то время общий префикс был/hello/, общедоступный префикс теперьchin.

Поэтому мы также ставимchinВырезать, как узел, получитсяaкак дочерний элемент этого узла. А также поставитьeseТакже как дочерний узел.

3.3 Подведение итогов алгоритма построения

На этом сборка закончена. Подведем итог алгоритму.

Конкретный аннотированный код будет приведен в конце этой статьи., если вы хотите узнать больше, вы можете проверить это самостоятельно. Сначала поймите процесс здесь:

(1) Если дерево пусто, вставьте напрямую
(2) В противном случае выяснить, совпадает ли текущий узел с вставляемым.URIимеет общий префикс （3）如果没有公共前缀，则直接插入 （4）如果有公共前缀，则判断是否需要分裂当前的结点
(5) Если требуется разделение, используйте общую часть в качестве родительского узла, а остальные — в качестве дочерних узлов.
(6) Если разделение не требуется, найдите дочерние узлы с одинаковым префиксом или без него.
(7) Если есть тот же префикс, перейдите к (4)
(8) Если нет префикса того же самого, вставьте непосредственно
(9) В последнем узле поставьте соответствующийHandle

Но здесь некоторые студенты хотят спросить:Как тут маршрут без параметров?

На самом деле, если вы понимаете описанный выше процесс, параметры остаются теми же. Логика такова: перед каждой вставкой будет сканировать, есть ли в данный момент путь вставляемого узла с параметрами (то есть сканировать, есть ли какие-либо/или*). Если есть параметры, текущий узелwildChildсвойство установлено наtrue, затем установите раздел параметров наНовый ребенок узел.

4 Монитор

Поговорив о регистрации маршрутизации, давайте поговорим о мониторинге маршрутизации.

существуетпредыдущий постВ содержании мы упомянули об этом:

type serverHandler struct {
	srv *Server
}

func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
	handler := sh.srv.Handler
	if handler == nil {
		handler = DefaultServeMux
	}
	if req.RequestURI == "*" && req.Method == "OPTIONS" {
		handler = globalOptionsHandler{}
	}
	handler.ServeHTTP(rw, req)
}

В то время мы упомянули, что если мы не перейдем ни к одномуHandleМетод, Golang будет использовать метод по умолчаниюDefaultServeMuxспособ обработки запроса. И теперь мы проходим вrouter, поэтому будем использоватьrouterдля обработки запроса.

следовательно,routerтакже понялServeHTTPметод. Давайте посмотрим (опять же опуская некоторые шаги):

func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
	...
	path := req.URL.Path

	if root := r.trees[req.Method]; root != nil {
		if handle, ps, tsr := root.getValue(path, r.getParams); handle != nil {
			if ps != nil {
				handle(w, req, *ps)
				r.putParams(ps)
			} else {
				handle(w, req, nil)
			}
			return
		} 
	}
    ...
    // Handle 404
	if r.NotFound != nil {
		r.NotFound.ServeHTTP(w, req)
	} else {
		http.NotFound(w, req)
	}
}

Здесь мы выбираемметод запросасоответствующийпрефиксное дерево, называетсяgetValueметод.

Кратко объясните этот метод: в этом методе текущий путь и узел в узле будут постоянно сопоставляться.pathдо тех пор, пока вы накоему не найдете маршрут, соответствующий этому маршрутуHandleметод.

Обратите внимание, что в течение этого времени, если маршрут RESTful и содержит параметры в маршруте, он будет сохранен вParamздесьParamСтруктура выглядит следующим образом:

type Param struct {
	Key   string
	Value string
}

Если соответствующий маршрут не найден, вызывается следующий метод 404.

5 обработка

На этом шаге, по сути, содержание почти такое же.

После получения соответствующего маршрутаHandleПосле этого вызовите эту функцию.

только и использовалось раньшеnet/httpв упаковкеHandlerРазница в том, что здесьHandleПараметры, полученные от API, инкапсулируются.

type Handle func(http.ResponseWriter, *http.Request, Params)

6 в конце

Спасибо, что вы здесь~

На этом знакомство с httprouter завершено, и самое главное — построение префиксного дерева. В приведенном выше примере я использовал комбинацию графики и текста для имитации процесса построения префиксного дерева, надеясь помочь вам понять, как развивается префиксное дерево. Конечно, если у вас есть какие-либо вопросы, вы также можете оставить сообщение или связаться со мной в WeChat~

Конечно, если вас это не устраивает, можете посмотретьприложение сзадиЗапись, с префиксным деревомПолный код комментарии.

Конечно, автор только начинает. Так что пропусков может быть много. Если в процессе прочтения какое-либо объяснение окажется не на месте или возникнет отклонение в понимании, пожалуйста, оставьте сообщение, чтобы исправить это.

Еще раз спасибо~

PS: Если у вас есть другие вопросы, вы также можете найти автора на официальном аккаунте. Кроме того, все статьи будут обновлены в общедоступном аккаунте как можно скорее, добро пожаловать, чтобы поиграть с автором~

7 Чтение исходного кода

7.1 Структура дерева

type node struct {
	
	path      string    //当前结点的URI
	indices   string    //子结点的首字母
	wildChild bool      //子节点是否为参数结点
	nType     nodeType  //结点类型
	priority  uint32    //权重
	children  []*node   //子节点
	handle    Handle    //处理器
}

7.2 addRoute

func (n *node) addRoute(path string, handle Handle) {

	fullPath := path
	n.priority++

	// 如果这是个空树，那么直接插入
	if len(n.path) == 0 && len(n.indices) == 0 {

		//这个方法其实是在n这个结点插入path，但是会处理参数
		//详细实现在后文会给出
		n.insertChild(path, fullPath, handle)
		n.nType = root
		return
	}

	//设置一个flag
walk:
	for {
		// 找到当前结点path和要插入的path中最长的前缀
		// i为第一位不相同的下标
		i := longestCommonPrefix(path, n.path)

		// 此时相同的部分比这个结点记录的path短
		// 也就是说需要把当前的结点分裂开
		if i < len(n.path) {
			child := node{

				// 把不相同的部分设置为一个切片，作为子节点
				path:      n.path[i:],
				wildChild: n.wildChild,
				nType:     static,
				indices:   n.indices,
				children:  n.children,
				handle:    n.handle,
				priority:  n.priority - 1,
			}

			// 将新的结点作为这个结点的子节点
			n.children = []*node{&child}
			// 把这个结点的首字母加入indices中
			// 目的是查找更快
			n.indices = string([]byte{n.path[i]})
			n.path = path[:i]
			n.handle = nil
			n.wildChild = false
		}

		// 此时相同的部分只占了新URI的一部分
		// 所以把path后面不相同的部分要设置成一个新的结点
		if i < len(path) {
			path = path[i:]

			// 此时如果n的子节点是带参数的
			if n.wildChild {
				n = n.children[0]
				n.priority++

				// 判断是否会不合法
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
					n.nType != catchAll &&
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
					continue walk
				} else {
					pathSeg := path
					if n.nType != catchAll {
						pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
					}
					prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
					panic("'" + pathSeg +
						"' in new path '" + fullPath +
						"' conflicts with existing wildcard '" + n.path +
						"' in existing prefix '" + prefix +
						"'")
				}
			}

			// 把截取的path的第一位记录下来
			idxc := path[0]

			// 如果此时n的子节点是带参数的
			if n.nType == param && idxc == '/' && len(n.children) == 1 {
				n = n.children[0]
				n.priority++
				continue walk
			}

			// 这一步是检查拆分出的path，是否应该被合并入子节点中
			// 具体例子可看上文中的图解
			// 如果是这样的话，把这个子节点设置为n，然后开始一轮新的循环
			for i, c := range []byte(n.indices) {
				if c == idxc {
					// 这一部分是为了把权重更高的首字符调整到前面
					i = n.incrementChildPrio(i)
					n = n.children[i]
					continue walk
				}
			}

			// 如果这个结点不用被合并
			if idxc != ':' && idxc != '*' {
				// 把这个结点的首字母也加入n的indices中
				n.indices += string([]byte{idxc})
				child := &node{}
				n.children = append(n.children, child)
				n.incrementChildPrio(len(n.indices) - 1)
				// 新建一个结点
				n = child
			}
			// 对这个结点进行插入操作
			n.insertChild(path, fullPath, handle)
			return
		}

		// 直接插入到当前的结点
		if n.handle != nil {
			panic("a handle is already registered for path '" + fullPath + "'")
		}
		n.handle = handle
		return
	}
}

7.3 insertChild

func (n *node) insertChild(path, fullPath string, handle Handle) {
	for {
		// 这个方法是用来找这个path是否含有参数的
		wildcard, i, valid := findWildcard(path)
		// 如果不含参数，直接跳出循环，看最后两行
		if i < 0 {
			break
		}

		// 条件校验
		if !valid {
			panic("only one wildcard per path segment is allowed, has: '" +
				wildcard + "' in path '" + fullPath + "'")
		}

		// 同样判断是否合法
		if len(wildcard) < 2 {
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
		}

		if len(n.children) > 0 {
			panic("wildcard segment '" + wildcard +
				"' conflicts with existing children in path '" + fullPath + "'")
		}

		// 如果参数的第一位是`:`，则说明这是一个参数类型
		if wildcard[0] == ':' {
			if i > 0 {
				// 把当前的path设置为参数之前的那部分
				n.path = path[:i]
				// 准备把参数后面的部分作为一个新的结点
				path = path[i:]
			}

			//然后把参数部分作为新的结点
			n.wildChild = true
			child := &node{
				nType: param,
				path:  wildcard,
			}
			n.children = []*node{child}
			n = child
			n.priority++

			// 这里的意思是，path在参数后面还没有结束
			if len(wildcard) < len(path) {
				// 把参数后面那部分再分出一个结点，continue继续处理
				path = path[len(wildcard):]
				child := &node{
					priority: 1,
				}
				n.children = []*node{child}
				n = child
				continue
			}

			// 把处理器设置进去
			n.handle = handle
			return

		} else { // 另外一种情况
			if i+len(wildcard) != len(path) {
				panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
			}

			if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
				panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
			}

			// 判断在这之前有没有一个/
			i--
			if path[i] != '/' {
				panic("no / before catch-all in path '" + fullPath + "'")
			}

			n.path = path[:i]

			// 设置一个catchAll类型的子节点
			child := &node{
				wildChild: true,
				nType:     catchAll,
			}
			n.children = []*node{child}
			n.indices = string('/')
			n = child
			n.priority++

			// 把后面的参数部分设置为新节点
			child = &node{
				path:     path[i:],
				nType:    catchAll,
				handle:   handle,
				priority: 1,
			}
			n.children = []*node{child}

			return
		}
	}

	// 对应最开头的部分，如果这个path里面没有参数，直接设置
	n.path = path
	n.handle = handle
}

Здесь собраны самые критические методы. Позвольте мне поаплодировать вам, если вы это увидите!

Эту часть будет труднее понять, и, возможно, ее придется прочитать несколько раз.

Если все еще есть что-то непонятное, пожалуйста, оставьте сообщение для обмена или зайдите на официальный аккаунт, чтобы найти меня напрямую ~