大廠技術(shù) 堅(jiān)持周更精選好文

背景

本人自己曾經(jīng)造輪子搞過(guò)一個(gè) Node.js 端的應(yīng)用層 Web 框架，里面涉及到一個(gè)路由系統(tǒng)的實(shí)現(xiàn)，當(dāng)時(shí)是通過(guò)一個(gè)叫前綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)便捷的路由查找與匹配機(jī)制，這里跟大家分享一下。

前綴樹(shù)介紹

前綴樹(shù)，即字典樹(shù)，又稱(chēng) Trie 樹(shù)。這種數(shù)據(jù)結(jié)構(gòu)通常用來(lái)儲(chǔ)存字符串，并且是以路徑字符節(jié)點(diǎn)的形式來(lái)儲(chǔ)存。擁有公共前綴的字符串，會(huì)共享同樣的父節(jié)點(diǎn)路徑。前綴樹(shù)是通過(guò)利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。

前綴樹(shù)的 3 個(gè)基本性質(zhì)：

根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

路由匹配的場(chǎng)景

這個(gè)問(wèn)題是在做 Web 框架的路由時(shí)碰見(jiàn)的，所以這里的請(qǐng)求路徑的形式可以當(dāng)做就是一個(gè)個(gè) URL 刨去協(xié)議名、域名、端口號(hào)（有的話）之后的部分，一般是通過(guò)斜杠 ("/") 來(lái)鏈接一個(gè)個(gè)元素，形如：

/api/user/nameList
/api/user/addressList

而且在大部分時(shí)候，路由的路徑是根據(jù)模塊的層級(jí)來(lái)劃分功能，以達(dá)到顧名思義的目的，因此路由的路徑其實(shí)是會(huì)有很多公共的前綴。比如，上述例子中同屬于一個(gè)二級(jí)模塊 User 的接口：

/api/user/list 和 /api/user/create ，它們便有共同的前綴 /api/user ，聯(lián)系到上述前綴樹(shù)的性質(zhì)，我們便可以通過(guò)前綴樹(shù)來(lái)儲(chǔ)存和搜索這些路由信息。

應(yīng)用到路由匹配中

根據(jù)上面的一個(gè)結(jié)論，可以得到一個(gè)基本思路：

把路由路徑當(dāng)做是用斜杠連接起來(lái)的 Component 的組合，因此前綴樹(shù)當(dāng)中的節(jié)點(diǎn)，儲(chǔ)存的就不再是單個(gè)字符，而是一個(gè)個(gè) Component，但這不會(huì)影響我們?nèi)ナ褂眠@種數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行搜索。

按照上面的描述，將這兩串路徑用 / 分割，形成一組 Component，同時(shí)它們擁有兩層的公共路徑，那么將會(huì)形成這樣的樹(shù)結(jié)構(gòu)：（葉子節(jié)點(diǎn)儲(chǔ)存的是對(duì)應(yīng)的 handler）

將路由聲明添加到 Trie 樹(shù)中

下面是將路由聲明的 Component 添加到 Trie 樹(shù)中的代碼：

router.get( '/api/user/nameList', xxx);

addToTree(urlPattern: string, handler: any) {
    let p = this.root;
    // Padding an element to the rear of the array to make the leaf node.
    const urlPatternComponents = [...urlPattern.split('/').filter(Boolean), LEAF_SIGN];

    urlPatternComponents.forEach(component => {
      const { quickMap } = p;

      // If quickMap has this component, it means the route has the same namespace
      // with existed route, so get to the next level directly. If the node is a leaf
      // node, just return cause it means redundant route is adding to the tree, we dont need it.
      if (p.quickMap.has(component as string)) {
        const node = p.quickMap.get(component as string)!;
        if (isLeafNode(node)) {
          return;
        }
        p = node;
        return;
      }

      if (component === LEAF_SIGN) {
        const newNode = new RouterTreeLeafNode(handler);
        quickMap.set(LEAF_SIGN, newNode);
        return;
      }

      const newNode = new NTreeNode(component as string);
      p.quickMap.set(component as string, newNode);
      // When the expression like ':id' shows in the route, it should
      // treat it as a parameter node.One tree node can only have one parameter node.
      if ((component as string).indexOf(':') > -1) {
        p.paramNode = newNode;
      }
      p = newNode;
    });
  }

router.get(' /api/hi/:name'

這里用一個(gè) quickMap 來(lái)儲(chǔ)存子節(jié)點(diǎn)，key 為 Component，value 為節(jié)點(diǎn)，用于在匹配過(guò)程中快速查找到與 Component 值相匹配的節(jié)點(diǎn)。注意在 urlComponents 數(shù)組末尾填充了一個(gè)叫 LEAF_SIGN 的 Symbol，看上面的樹(shù)結(jié)構(gòu)圖就知道，實(shí)際路由聲明的 Component 遍歷完之后，葉子節(jié)點(diǎn)的值儲(chǔ)存的是最后一個(gè) Component，因此我們需要給它添加一個(gè)子節(jié)點(diǎn)，用來(lái)儲(chǔ)存實(shí)際匹配的結(jié)果，也就是路由的 Handler。paramNode 放到動(dòng)態(tài)路由匹配一節(jié)再解析，這里可以先不管。

靜態(tài)路由匹配

在匹配時(shí)，也實(shí)際的請(qǐng)求路徑同樣按照上面的分割方式切分成一組 Component，從 Trie 的根節(jié)點(diǎn)開(kāi)始，它的子節(jié)點(diǎn)必定只有一個(gè)，將指針指向它的唯一子節(jié)點(diǎn)，并將遍歷 Component 的指針往后挪，根據(jù)遍歷到的新的 Component 去匹配下一層的子節(jié)點(diǎn)。直到 Component 被遍歷完，若最后可以找到相匹配的子節(jié)點(diǎn)，則該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，將其值取出作為結(jié)果返回。若未能匹配，在靜態(tài)路由匹配的情況中就是 Route not found 的情況了，但是實(shí)際場(chǎng)景肯定沒(méi)有這么簡(jiǎn)單粗暴，這里先留個(gè)坑，后面會(huì)講到。

代碼如下：

getHandlerFromTree(url: string): any{
    const [urlWithParams, _] = url.split('?');
    const urlComponents = urlWithParams.split('/').filter(Boolean);
    let p = this.root;
    let i = 0;
    let res;
    let path = '';
    while (p) {
      const component = urlComponents[i ++];

      // If the quickMap has the component, return it if it's also a leaf node.
      // Or just move to the next level and store the path.
      if (p.quickMap.has(component)) {
        const node = p.quickMap.get(component)!;
        if (isLeafNode(node)) {
          res = node.value;
          break;
        }
        path += '/' + node.value;
        p = node;
        continue;
      }

      const leafNode = p.quickMap.get(LEAF_SIGN);

      if (leafNode == null) {
        // If quickMap has other node, it means static route cannot be matched.
        if (p.quickMap.size > 0) {
          const err = { message: 'Route not defined', statusCode: 404, statusMessage: 'Not found' };
          throw err;
        }
        
        // Else it means no handler was defined.
        const err = { message: 'Handler not defined', statusCode: 500, statusMessage: 'Not found' };
        throw err;
      }

      res = leafNode.value;
      break;
    }

    return {
      handler: res,
      path
    };
  }

動(dòng)態(tài)路由匹配

我們?cè)谑褂?Express 或是 Koa.js 時(shí)，會(huì)用到形如 /api/user/:id 這樣的動(dòng)態(tài)路由聲明，這是一個(gè)實(shí)用的功能，來(lái)看下如何在基于 Trie 樹(shù)的路由系統(tǒng)中實(shí)現(xiàn)動(dòng)態(tài)路由。

還是剛才的兩條路由聲明，現(xiàn)在我們加上一條新的:

/api/user/nameList

/api/user/addressList

/api/user/:id

得到這樣的結(jié)構(gòu):

對(duì)這樣的動(dòng)態(tài)參數(shù)路由聲明，將其作為一個(gè)特殊節(jié)點(diǎn)，用一個(gè)單獨(dú)的指針 paramNode 保存，我們限制一種路由聲明只能有一個(gè)動(dòng)態(tài)參數(shù)，就是不能既有 /api/user/:id 又有 /api/user/:name，這樣的話在實(shí)際匹配時(shí)無(wú)法得知，路徑中對(duì)應(yīng)位置的 Component 代表的是什么含義。

接上面的坑，實(shí)際匹配時(shí)，當(dāng)碰見(jiàn)無(wú)法匹配的 Component 時(shí)，那么代表這個(gè) Component 是一個(gè)動(dòng)態(tài)參數(shù)的實(shí)際值，所以無(wú)法跟任何靜態(tài)聲明匹配，這時(shí)就直接去找該節(jié)點(diǎn)的 paramNode 指針指向的節(jié)點(diǎn)，也就是說(shuō)當(dāng)碰到這種情況時(shí)，我們直接把它歸類(lèi)為動(dòng)態(tài)參數(shù)匹配的場(chǎng)景。

看一下加入動(dòng)態(tài)參數(shù)匹配的代碼，省略共同部分：

getHandlerFromTree(url: string): any {
    // ...
    if (p.quickMap.has(component)) {
        const node = p.quickMap.get(component)!;
        if (isLeafNode(node)) {
          res = node.value;
          break;
        }
        path += '/' + node.value;
        p = node;
        continue;
    }
    if (component) {
        path += '/' + p.paramNode.value;
        p = p.paramNode;
        continue;
    }

    const leafNode = p.quickMap.get(LEAF_SIGN);
    // ...
}

那么這時(shí)又有一個(gè)坑，如果 paramNode 不存在，該怎么辦？下面來(lái)說(shuō)下一種場(chǎng)景：正則表達(dá)式匹配。

正則表達(dá)式匹配

router.get( /hi/all/ , xxx)

因?yàn)檎齽t表達(dá)式是可以直接進(jìn)行字符串匹配的，所以這種路由聲明將會(huì)脫離 Trie 樹(shù)的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)而存在，我們選擇將這種節(jié)點(diǎn)全部?jī)?chǔ)存在根結(jié)點(diǎn)下方，避免不必要的查找。上面說(shuō)到，如果一個(gè)節(jié)點(diǎn)的 paramNode 指針不存在，那么我們只好做最后一種選擇，將整個(gè)路徑進(jìn)行正則表達(dá)式匹配，如果仍然無(wú)法匹配，就只好拋出路由未找到的異常，由依賴(lài)路由的代碼去處理這個(gè)異常。

getHandlerFromTree(url: string) {
    // ...
    if (component) {
        // If no parameter node found, try regular expression matching.
        if (!p. paramNode ) {
 const { handler, matched } = this . getHandlerFromRegExpNode (url);
res = handler
path = matched;
 break ;
}
        path += '/' + p.paramNode.value;
        p = p.paramNode;
        continue;
    }

    const leafNode = p.quickMap.get(LEAF_SIGN);
    // ...
}

添加正則表達(dá)式節(jié)點(diǎn)到樹(shù)中：

addRegExpToTree(urlPattern: RegExp, handler: Function) {
    const root = this.root;

    root.children.push(new RouterRegExpLeafNode(urlPattern, handler));
}

得到的結(jié)構(gòu)是這樣的：

這樣就實(shí)現(xiàn)了一個(gè)支持靜態(tài)、動(dòng)態(tài)、正則表達(dá)式三種匹配方式的路由機(jī)制。

簡(jiǎn)單分析

使用 Trie 樹(shù)來(lái)做路由匹配就是比較折中的方案，通常來(lái)說(shuō)路由聲明都會(huì)按照模塊來(lái)做分類(lèi)，在同一個(gè)一級(jí)模塊下面的多個(gè)二級(jí)模塊路由，然后每個(gè)二級(jí)模塊下面會(huì)有多個(gè)三級(jí)模塊路由，就會(huì)產(chǎn)生公共前綴，就給了 Trie 樹(shù)節(jié)省空間的機(jī)會(huì)，并且重復(fù)率越高節(jié)省的空間越多（聽(tīng)起來(lái)怎么像 gzip 壓縮），Trie 樹(shù)的最壞查找效率取決于所儲(chǔ)存的序列的最長(zhǎng)長(zhǎng)度，也就是樹(shù)的最大深度，是一個(gè)線性級(jí)別的時(shí)間復(fù)雜度。這里會(huì)有另一個(gè)問(wèn)題，如果所有路由聲明都是分散的，沒(méi)有公共前綴，假設(shè)有 m 條長(zhǎng)度為 n 的記錄，在彼此沒(méi)有公共前綴時(shí)，Trie 樹(shù)的空間復(fù)雜度會(huì)達(dá)到 O(mn)，故在使用時(shí)應(yīng)盡量收斂路由聲明的 namespace 數(shù)量。

總結(jié)

一開(kāi)始內(nèi)心有個(gè)問(wèn)題，為什么不直接用哈希表儲(chǔ)存靜態(tài)路由，然后動(dòng)態(tài)路由就使用遍歷查找的方式？后面對(duì)這個(gè)問(wèn)題有了一些自己的理解：

使用哈希表儲(chǔ)存靜態(tài)路由，查找速度是常數(shù)級(jí)別的，非常快，但是需要線性空間來(lái)儲(chǔ)存，而且每一條靜態(tài)路由都需要完整儲(chǔ)存，那么就浪費(fèi)了公共前綴這個(gè)特性。其次，對(duì)動(dòng)態(tài)路由使用遍歷匹配的方式太過(guò)暴力，動(dòng)態(tài)路由沒(méi)有辦法去很好地做緩存，而路由匹配是個(gè)高頻的動(dòng)作，這種方式的性能開(kāi)銷(xiāo)相對(duì)來(lái)說(shuō)比較大，也是不夠合適的。