본문은 Makuake Advent Calendar 2020의 13일째 문장이다.
본문은 아래의 문장을 바탕으로 약간의 수정을 진행하였다.

URLルーティング自作入門　エピソード１

URLルーティング自作入門　エピソード２

GolangのHTTPサーバーのコードリーディング

소개하다.

Golang에서 URL 라우터를 만드는 과정을 기록합니다.
논리적 루트에 대해 정규 표현식이 아닌trie 트리 알고리즘을 기초로 한다.
Go에는 다양한 라우터 패키지가 있습니다.
전임

julienschmidt/httprouter

go-chi/chi

git-gonic/gin

fasthttp/router

많은 도서관들이 복잡한 트리 구조 알고리즘을 채택하여 성능을 최적화시켰다.
이번에는 상대적으로 이해하기 쉬운 데이터 구조를 정의함으로써 이를 실현하고 알고리즘의 난이도를 낮추고 싶다.

URL 라우터란?

URL 라우터는 URL 정렬 프로세스를 기반으로 하는 응용 프로그램입니다.
설명할 필요가 없을 수도 있지만, URL과router라는 단어의 정의를 확인하고 싶습니다.

통합 리소스 포지셔닝 주소

URL은 인터넷에 있는 페이지의 주소를 나타내며 URL은 Unified Resource Locator의 약자입니다.
URL 문자열의 형식은 다음과 같습니다.

 <scheme>:<scheme-specific-part>

http, https, ftp 등 프로토콜 이름은 위젯에 사용되지만, 프로토콜 이름 이외의 패턴 이름도 정의됩니다.
참조Uniform Resource Identifier (URI) Schemes<sceme-specific-part> 부분에서 패턴 기반 문자열을 정의했습니다.
예를 들어 http와https 프로젝트에서 규칙은 도메인 이름과 경로 이름(또는 디렉터리 이름)을 정의하는 것이다.
자세한 URL 사양은 RFC1738을 참조하십시오.
참조rfc1738 - Uniform Resource Locators (URL)
RFC1738은 인터넷 표준(std1)으로 지정되었습니다.

라우터

알다시피, 루트는 루트 제어를 의미한다.
예를 들어 네트워크 간에 통신을 중계하는 공유기는 패키지 전송을 조정하기 위해 루트표를 사용하여 루트를 실행한다.
URL 라우터는 브라우저에서 URL이라는 정보를 수신하도록 요청하고 수신된 URL을 기반으로 데이터를 처리할 수 있도록 URL과 처리 사이의 중개 역할을 합니다.
네트워크의 라우터에 라우팅 테이블이라는 데이터 구조가 있는 것처럼 URL 라우터에도 라우팅에 사용되는 데이터 구조가 필요합니다.

요구 사항 정의

각종 다기능 공유기가 있지만 이번에 우리는 다음과 같은 기능을 가진 공유기를 실현할 것이다.

정적 경로 지원

URL/foo/bar/은 정적 라우팅 정의/foo/bar/와 일치하며 프로세스를 반환할 수 있습니다.

동적 라우팅 지원

URL/foo/bar/123은 동적 경로 매개 변수(예: /foo/bar /:id가 있는 경로 정의와 일치하며 경로 매개 변수 데이터로 프로세스를 되돌릴 수 있습니다.

데이터 흐름

나는 이것이 결코 특별히 어렵지 않다고 생각하지만, 나는 데이터 흐름을 확인하고 싶다.

라우터는 URL의 경로 부분을 입력 데이터로 받아 경로와 일치하는 데이터를 확인하고 프로세스를 호출합니다.
경로와 절차를 어떻게 일치시키는가가 실시의 기초이다.

나무구조

일치 경로와 절차의 기본적인 실현은 트리 구조라고 불리는 데이터 구조를 이용하여 알고리즘을 실현한다.

나무 구조는 뿌리, 분지, 노드와 잎(잎 끝의 노드)을 가진 데이터 구조이다.
데이터 저장 방법과 검색 방법의 모델에 따라 다양한 유형의 트리 구조가 있다.
우리는 주로 URL 루트에서 문자열을 처리하기를 원하기 때문에, 문자열 검색에 전문적으로 사용되는 trie 트리라는 데이터 구조를 사용했다.

Trie 트리 구조

trie 트리는 문자열을 처리하는 트리 구조입니다.
접두사 트리라고도 부른다.
모든 노드에는 하나 이상의 문자열이나 숫자가 있는데, 뿌리 노드에서 잎 노드로 값을 검색하고 연결해서 단어를 표현합니다.
각 노드마다 반드시 하나의 값이 있는 것은 아니다.
Trie 트리는 네트워크 계층의 IP 주소 검색, 애플리케이션 계층의 http 라우팅 및 머신 러닝 환경에서의 형태 분석에 사용됩니다.
이 알고리즘의 이미지는 다음과 같은 시각화 도구이다
나는 네가 그것을 겪을 때 쉽게 이해할 수 있다고 생각한다.
Trie（Prefix Tree）
trie 트리의 메모리 효율을 최적화하려면 문자열 접두사를 효과적으로 저장하는 트리 구조, 예를 들어 기수 트리(Patricia trie)를 고려해야 한다.
trie 트리의 계산 복잡도는 검색과 삽입에 동일하며 검색 키의 길이가 m일 때 최악의 계산 복잡도는 O(m)이다.
나는 이미 예시 코드를 준비했으니 한번 보십시오.
trie

트리를 어떻게 처리합니까?

Trie 트리를 URL 라우터와 함께 사용하기 쉽게 사용자 정의합니다.

예를 들어, 위 그림은 GET만 지원하는 라우트를 정의합니다.

/foo/

/baz/

/foo/bar/

/foo/:name[string]/

/foo/bar/:id[int]

루트 디렉토리에 HTTP 메서드의 노드를 직접 생성하고 각 HTTP 메서드의 경로를 저장합니다.:로 시작하는 노드는 경로 매개 변수를 저장하는 노드입니다.
DSL[int]은 정규 표현식을 매개변수에 매핑하는 데 사용됩니다.
검색하고 도착한 노드에 처리 데이터가 있으면 일치에 성공하고, 없으면 일치에 실패합니다.
다음은 이 맞춤형 세 갈래 나무의 실현이다.
[goblin/trie.go(https://github.com/bmf-san/goblin/blob/master/trie.go)

Golang 공유기의 실현

Golang에서 표준 패키지net/http는 라우팅 기능을 제공합니다.
이 기능은 Golang에서 멀티플렉서라고 합니다.
그러나 표준 패키지는 경로 파라미터를 지원하지 않기 때문에 외부 패키지나 확장 표준 다중 복호화기를 준비해야 합니다.
이번에, 나는 자신의 루트를 만들 것이기 때문에, 다중 복용기를 확장해야 한다.
다중 복용기의 확장을 배우기 전에 http 서버 규범을 익히는 것이 가장 좋다.

http 서버 코드 읽기

참조 실현

우리는 아래의 실현을 참고하여 그것을 읽을 것이다.

package main

import (
    "net/http"
)

func main() {
    mux := http.NewServeMux()
    handler := new(HelloHandler)
    mux.Handle("/", handler)

    s := http.Server{
        Addr:    ":3000",
        Handler: mux,
    }
    s.ListenAndServe()
}

type HelloHandler struct{}

func (h *HelloHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("Hello World"))
}

나는 이 쓸데없는 코드를 한 줄 한 줄 읽어서 코드를 간소화할 것이다.

ServeHttp(응답 작성기 포함, r* 요청)

나는 이 쓸데없는 코드를 한 줄 한 줄 읽어서 코드를 간소화할 것이다.

type HelloHandler struct{}

func (h *HelloHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("Hello World"))
}

ServeHTTP (w ResponseWriter, r * Request)는 Handler 인터페이스의 실현이다.

// url: https://golang.org/src/net/http/server.go?s=61586:61646#L1996
func (mux *ServeMux) ServeHTTP(w ResponseWriter, r *Request) {
    if r.RequestURI == "*" {
        if r.ProtoAtLeast(1, 1) {
            w.Header().Set("Connection", "close")
        }
        w.WriteHeader(StatusBadRequest)
        return
    }
    h, _ := mux.Handler(r)
    h.ServeHTTP(w, r)
}

// url: https://golang.org/src/net/http/server.go?s=61586:61646#L79
type Handler interface {
    ServeHTTP(ResponseWriter, *Request)
}

참고 실현 중HelloHandler구조는 ServeHTTP (w ResponseWriter, r * Request)를 위해 준비한 것이고,HandlerFunc 를 사용하여 다시 쓸 수 있습니다.

// url: https://golang.org/src/net/http/server.go?s=61509:61556#L1993
type HandlerFunc func(ResponseWriter, *Request)

func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) {
    f(w, r)
}

다시 쓰는 인용은 다음과 같다.

package main

import (
    "net/http"
)

func main() {
    mux := http.NewServeMux()
    mux.Handle("/", http.HandlerFunc(hello))

    s := http.Server{
        Addr:    ":3000",
        Handler: mux,
    }
    s.ListenAndServe()
}

func hello(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("Hello World"))
}

내가 사용한 부분을 다시 쓸 수 있다ServeHTTP (w ResponseWriter, r * Request).
그나저나 mux.Handle의 내용은 이렇게 이루어졌다.

// url: https://golang.org/src/net/http/server.go?s=75321:75365#L2390
func (mux *ServeMux) Handle(pattern string, handler Handler) {
    mux.mu.Lock()
    defer mux.mu.Unlock()

    if pattern == "" {
        panic("http: invalid pattern")
    }
    if handler == nil {
        panic("http: nil handler")
    }
    if _, exist := mux.m[pattern]; exist {
        panic("http: multiple registrations for " + pattern)
    }

    if mux.m == nil {
        mux.m = make(map[string]muxEntry)
    }
    e := muxEntry{h: handler, pattern: pattern}
    mux.m[pattern] = e
    if pattern[len(pattern)-1] == '/' {
        mux.es = appendSorted(mux.es, e)
    }

    if pattern[0] != '/' {
        mux.hosts = true
    }
}

ServeMux

앞에 있는 코드를 자세히 봅시다.

    mux := http.NewServeMux()
    mux.Handle("/", http.HandlerFunc(hello))

    s := http.Server{
        Addr:    ":3000",
        Handler: mux,
    }

914의 일부분은 914에서 내부적으로 처리할 수 있기 때문이다.

url: https://golang.org/src/net/http/server.go?s=75575:75646#L2448
func HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
    DefaultServeMux.HandleFunc(pattern, handler)
}

url: https://golang.org/src/net/http/server.go?s=75575:75646#L2435
func (mux *ServeMux) HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
    if handler == nil {
        panic("http: nil handler")
    }
    mux.Handle(pattern, HandlerFunc(handler))
}

만약 네가 위의 상황을 고려하여 그것을 다시 쓴다면, 그것은 이렇게 될 것이다.

package main

import (
    "net/http"
)

func main() {
    http.HandleFunc("/", hello)

    s := http.Server{
        Addr:    ":3000",
        Handler: http.DefaultServeMux,
    }
    s.ListenAndServe()
}

func hello(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("Hello World"))
}

mux.Handle ("/", http.HandlerFunc (hello))는 내부 변수로 지향HandleFunc 구조의 지침을 포함한다.DefaultServeMux는 url 모드를 ServeMux 에 일치하게 등록할 수 있는 방법입니다.

url: https://golang.org/src/net/http/server.go?s=75575:75646#L2207
// DefaultServeMux is the default ServeMux used by Serve.
var DefaultServeMux = &defaultServeMux

var defaultServeMux ServeMux

url: https://golang.org/src/net/http/server.go?s=68149:68351#L2182
type ServeMux struct {
    mu    sync.RWMutex
    m     map[string]muxEntry
    es    []muxEntry // slice of entries sorted from longest to shortest.
    hosts bool       // whether any patterns contain hostnames
}

서버

마지막으로 볼 부분은 이 부분이다.

    s := http.Server{
        Addr:    ":3000",
        Handler: http.DefaultServeMux,
    }
    s.ListenAndServe()

다음은 HandleFunc의 실현이다.

url: https://golang.org/src/net/http/server.go?s=68149:68351#L3093
func (srv *Server) ListenAndServe() error {
    if srv.shuttingDown() {
        return ErrServerClosed
    }
    addr := srv.Addr
    if addr == "" {
        addr = ":http"
    }
    ln, err := net.Listen("tcp", addr)
    if err != nil {
        return err
    }
    return srv.Serve(ln)
}

DefaultServeMux에 대한 상세한 설정이 필요하지 않으면 s.ListenAndServe ()로 줄일 수 있다.Server의 설정값은 golang.org --server.go를 참조하십시오.

url: https://golang.org/src/net/http/server.go?s=68149:68351#L3071
func ListenAndServe(addr string, handler Handler) error {
    server := &Server{Addr: addr, Handler: handler}
    return server.ListenAndServe()
}

요컨대 이렇다.

package main

import (
    "net/http"
)

func main() {
    http.HandleFunc("/", hello)

    http.ListenAndServe(":3000", nil)
}

func hello(w http.ResponseWriter, r *http.Request) {
    w.Write([]byte("Hello World"))
}

익명 함수와 함께 사용할 때, 그것은 이렇게 보입니다.

package main

import (
    "net/http"
)

func main() {
    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        w.Write([]byte("Hello World"))
    })

    http.ListenAndServe(":3000", nil)
}

확장 멀티플렉서

다음은 확장 다중 복용기 부분의 코드입니다.
goblin/router.go
Golang은 표준 패키지의 인터페이스가 정확하게 유지보수되었기 때문에 확장하기 쉽다.

결론

이것이 바로 이런 방식으로 개발된 소프트웨어 패키지다.
bmf-san/goblin
코드량이 적으니 읽어 주세요.
물론 기부도 환영합니다D

부록.

임프 첨가awesome-go