使用正则表达式开发一个高性能路由

原文地址：http://nikic.github.io/2014/02/18/Fast-request-routing-using-regular-expressions.html

前一些日子，我发现了一个叫做Pux的路由库，这个路由库声称自己比现有的路由要快很多，为了实现这个特点，该库使用了 C 语言编写了 PHP 扩展。

然而，当我瞅了几眼它的代码后，我非常怀疑这个库在路由过程中做了错误的优化，而且我能够很容易在不适用扩展的情况下做出更高性能的实现。当我在看了 benchmarking 代码后更加确定了我的怀疑，因为我发现这里仅仅只是对及其确定的单个路由做了测试。

为了进一步研究这个问题，我写了一个轻量的路由库：FastRoute。这个库中实现的分发过程接下来我会具体描述。为了给出一些前期印象，这里先给出一个同 Pux 库的 benchmark 结果：

1 placeholder  | Pux (no ext) | Pux (ext) | FastRoute
-----------------------------------------------------
First route    | 0.17 s       | 0.13 s    | 0.14 s
Last route     | 2.51 s       | 1.20 s    | 0.49 s
Unknown route  | 2.34 s       | 1.10 s    | 0.34 s

9 placeholders | Pux (no ext) | Pux (ext) | FastRoute
-----------------------------------------------------
First route    | 0.22 s       | 0.19 s    | 0.20 s
Last route     | 2.65 s       | 1.78 s    | 0.59 s
Unknown route  | 2.50 s       | 1.49 s    | 0.40 s

这个 benchmark 使用了 100 个路由，分别对最好和最坏的情况做了测试。而且分两个方面进行：一个是只包含一个占位符的路由，另一个是包含 9 个占位符的路由。整个过程重复了上千次。

在进入到正式的主题之前，让我再强调最后一点：这篇文章表面上是关于路由的，但是我真正想聊得是一般的基于正则表达式的调度过程。从某种程度上说，这是对我之前写的"lexing performance in PHP“的重复。

关于路由的问题

为了确保我们没有跑题，让我们首先来定义一下“路由”。在大多数实现形式中，它是类似于如下形式的一系列过程：

$r->addRoute('GET', '/usr/{name}/{id:\d+}', 'handler0');
$r->addRoute('GET', '/user/{id:\d+}', 'handler1');
$r->addRoute('GET', '/user/{name}', 'handler2');

接着像下面这样分发 URI:

$d->dispatch('GET', '/user/nikic/42');
// => provides 'handler0' and ['name' => 'nikic', 'id' => '42']

为了达到更高的抽象度，我们会使用 HTTP Method 和一些特定的格式来定义路由，在这篇文章中，我唯一要阐述的是在分发层面上，路由是如何被解析的，而关于分发的数据是如何生成的将不会做深入说明。

那么，在路由过程中，慢的地方在哪呢？在一个大型设计的系统中很可能会生成几十个对象，调用几百个方法。Pux 在减少这种开销上做了很伟大的工作。但是，在更基础的层面上，路由分发过程中导致开销大的因素是一系列几十个或几百个甚至几千个路由正则来跟现有的 URI 做匹配。如何让他变得更快是本文将要讨论的话题。

组合正则

优化的基本思想是避免一个个进行正则匹配，而是将这些正则合并成一个大正则，这样就只需要匹配一次，我们用前面的例子来说，组合正则如下：

Individual regexes:

    ~^/user/([^/]+)/(\d+)$~
    ~^/user/(\d+)$~
    ~^/user/([^/]+)$~

Combined regex:

    ~^(?:
        /user/([^/]+)/(\d+)
      | /user/(\d+)
      | /user/([^/]+)
    )$~x<Paste>

转换起来非常简单，只需要将所有的单个正则用 OR 连接起来。当与该正则匹配的时候，如何确定是哪个路由匹配上了呢？为此，让我们来看看简单的preg_match执行的结果：

preg_match($regex, '/user/nikic', $matches);
=> [
    "/user/nikic",   # full match
    "", "",          # groups from first route (empty)
    "",              # groups from second route (empty)
    "nikic",         # groups from third route (used!)
]

所以，技巧就是在$matches数组中找到第一个不为空的元素。为了能够使用匹配的结果，你还需要一个额外的数据结构来映射$matches索引到匹配的路由

[
    1 => ['handler0', ['name', 'id']],
    3 => ['handler1', ['id']],
    4 => ['handler2', ['name']],
]

下面是一个简单的实现：

public function dispatch($uri) {
    if (!preg_match($this->regex, $uri, $matches)) {
        return [self::NOT_FOUND];
    }

    // find first non-empty match (skipping full match)
    for ($i = 1; '' === $matches[$i]; ++$i);

    list($handler, $varNames) = $this->routeData[$i];

    $vars = [];
    foreach ($varNames as $varName) {
        $vars[$varName] = $matches[$i++];
    }
    return [self::FOUND, $handler, $vars];
}

当我们找到第一个不为空的元素下标$i后，占位符变量就能够通过继续移动$matches数组下标计算出来，并且跟变量名进行关联。

这么简单的方法到底有多好呢？下面是跟 Pux（c 扩展）对比的结果：

1 placeholder  | Pux (ext) | GPB-NC
-----------------------------------
First route    | 0.13 s    | 0.20 s
Last route     | 1.20 s    | 0.70 s
Unknown route  | 1.10 s    | 0.16 s

9 placeholders | Pux (ext) | GPB-NC
-----------------------------------
First route    | 0.19 s    | 0.41 s
Last route     | 1.78 s    | 4.09 s
Unknown route  | 1.49 s    | 0.30 s

GPB-NC 表示的是"Group Position based, non-chunked"分发。接下来你就会明白这个术语的含义。正如你所看到的，这个方法在单个路由的时候表现出很高的性能，当然在第一次路由的情况下它还稍逊色于 C 扩展实现，但是在 last route 和没有匹配路由的情况下，它比 c 扩展要更快一些。

当我们注意到有 9 个占位符的路由时，情况就不那么乐观了：在 last route 的情况下，它要比 c 扩展慢两倍，而另一方面，在没有匹配到路由的情况下依然表现很好的性能。为什么会这样呢？

这背后的原因是（至少我假设是）在编译正则表达式的过程中，包含了大量的捕获组调用：100 个路由，每个路由有 9 个占位符，那么你会得到 900 个组，如果路由没有匹配到，$matches不需要计算，所以调用很快，如果第一个路由匹配上了，PCRE 只计算与该路由相关的匹配（也就是 9 个元素组合一个全匹配）。但是如果是最后一个路由匹配上的话，PCRE 不仅仅要计算最后一个路由，而且还要计算前面所有的路由包含的组。

所以，我们需要做的就是减少正则组的数量。

重置组数量

PCRE 正则语法中有一个比较少见的特性，就是(?|...，不捕获组类型。(?:和(?|的区别就是后者能在正则的每个分支上重置组数量。为了更好的说明它的含义，我们来看下面的例子：

preg_match('~(?:(Sat)ur|(Sun))day~', 'Saturday', $matches)
=> ["Saturday", "Sat", ""]   # The last "" is not actually in the $matches array, but that's just
                             # an implementation detail. I'm writing it here to clarify the concept.

preg_match('~(?:(Sat)ur|(Sun))day~', 'Sunday', $matches)
=> ["Sunday", "", "Sun"]

preg_match('~(?|(Sat)ur|(Sun))day~', 'Saturday', $matches)
=> ["Saturday", "Sat"]

preg_match('~(?|(Sat)ur|(Sun))day~', 'Sunday', $matches)
=> ["Sunday", "Sun"]

当使用(?:的时候，PCRE 会把Sat和Sun两个组分开匹配，每一个组都有一个唯一的下标。(Sat)是 1，(Sun)是 2。

在子组定义的左括号后面紧跟字符串 ”?:” 会使得该子组不被单独捕获，并且不会对其后子组序号的计算产生影响。比如, 如果字符串 “the white queen” 匹配模��the ((?:red|white) (king|queen))，匹配到的子串是 “white queen” 和 “queen”，他们的下标分别是 1 和 2。

有时需要多个匹配可以在一个正则表达式中选用子组。为了让多个子组可以共用一个后向引用数字的问题， (?| 语法允许复制数字。考虑下面的正则表达式匹配 Sunday： (?:(Sat)ur|(Sun))day 这里当后向引用 1 空时 Sun 存储在后向引用 2 中. 当后向引用 2 不存在的时候 Sat 存储在后向引用 1 中。使用(?|修改模式来修复这个问题： (?|(Sat)ur|(Sun))day, 使用这个模式， Sun 和 Sat 都会被存储到后向引用 1 中。

这就给我们提供了解决路由匹配中“太多子组”问题的方法。只需要将(?:替换成(?|:

~^(?|
    /user/([^/]+)/(\d+)
  | /user/(\d+)
  | /user/([^/]+)
)$~x

然而，现在组下标被重置了，我们不能确定到底是哪个路由被匹配上。前面我们是使用第一个不为空的下标，而现在下标被重置后，第一个不为空的元素永远都是$matches[1]。

聪明的你们也许会想到给每一个子组取一个名字，从而通过名字来看到底是哪个路由被匹配上了：

~^(?|
    (?<route1> /user/([^/]+)/(\d+) )
  | (?<route2> /user/(\d+) )
  | (?<route3> /user/([^/]+) )
)$~x

但是，这在 PCRE 中是不被允许的：内部命名组的实现是通过映射子模式名到组下标，然后将其作为一个普通的，无名组。也就是说上述的正则表达式<route1>, <route2>和<route3>都关联了同一个下标 1，这是没有意义的。

一个有效的方法是考虑匹配组的数量。上面给出的三个路由中，第一个路由会产生一个包含 3 个元素的$matches数组，第二个路由会产生 2 个元素。

那么，我们使用$matches的长度来确定匹配的路由是不准确的，但是我们可以很容易通过添加无用的组来调整正则：

~^(?|
    /user/([^/]+)/(\d+)
  | /user/(\d+)()()
  | /user/([^/]+)()()()
)$~x

现在，第一个路由有两个组（产生 3 个元素），第二个路由有三个组（产生 4 个元素），第三个路由有四个组（产生 5 个元素）。如此以来，分发可以被表达成如下格式的一个数组：

[
	3 => ['handler0', ['name', 'id']],
    4 => ['handler1', ['id']],
    5 => ['handler2', ['name']],
]

下面是一个简单的实现：

public function dispatch($uri) {
    if (!preg_match($this->regex, $uri, $matches)) {
        return [self::NOT_FOUND];
    }

    list($handler, $varNames) = $this->routeData[count($matches)];

    $vars = [];
    $i = 0;
    foreach ($varNames as $varName) {
        $vars[$varName] = $matches[++$i];
    }
    return [self::FOUND, $handler, $vars];
}

让我们再来看一下之前的对比：

1 placeholder  | Pux (ext) | GPB-NC | GCB-NC
--------------------------------------------
First route    | 0.13 s    | 0.20 s | 0.60 s
Last route     | 1.20 s    | 0.70 s | 1.06 s
Unknown route  | 1.10 s    | 0.16 s | 0.56 s

9 placeholders | Pux (ext) | GPB-NC | GCB-NC
--------------------------------------------
First route    | 0.19 s    | 0.41 s | 0.65 s
Last route     | 1.78 s    | 4.09 s | 0.96 s
Unknown route  | 1.49 s    | 0.30 s | 0.54 s

GPB 和 GCB(the Geoup Count Based)方法都是 Non-Chunked。很显然的是，GCB 很好的解决了 GPB 中的性能瓶颈，但是在其他情况下的性能却有所降低。

这是为什么呢？我认为这是由于增大的正则表达式和子组数量导致的。我们来具体分析一下：100 个路由我们需要生成$99 * 100 / 2 = 4950$个无用的子组，这会产生 $4950 * 2 = 9900$额外字节，也即是将近 10KB 的开销。

你可以看一下 100 个包含 9 个占位符的正则长啥样：generated regular expression:

|/cv/([^/]+)/([^/]+)/([^/]+)/([^/]+)/([^/]+)/([^/]+)/([^/]+)/([^/]+)/([^/]+)
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()())$~

（这看起来多像 LISP 代码呀！）

分块正则表达式

由于填充的空子组数量随着路由数量呈现指数级增长，这种方法并不能被广泛应用。另一种减少填充空子组数量的方法是将正则表达式分割成两个部分：一部分匹配前 50 个路由，另一部分匹配剩下的 50 个。每一个部分只需要$49 * 50 / 2 = 1225$个填充空子组，也就是总共有 2450 个子组，这样就远远少于 4950 个。如果路由被分割成 10 个部分，那么每个部分只需要$9 * 10 / 2 = 45$个空子组，也就是总共只需要 450 个。

下面是一个简单实现：

public function dispatch($uri) {
    foreach ($this->regexes as $i => $regex) {
        if (!preg_match($regex, $uri, $matches)) {
            continue;
        }

        list($handler, $varNames) = $this->routeData[$i][count($matches)];

        $vars = [];
        $i = 0;
        foreach ($varNames as $varName) {
            $vars[$varName] = $matches[++$i];
        }
        return [self::FOUND, $handler, $vars];
    }

    return [self::NOT_FOUND];
}

下面是 10 个分块的性能测试：

1 placeholder  | GCB-NC | GCB-10C
---------------------------------
First route    | 0.60 s | 0.14 s
Last route     | 1.06 s | 0.49 s
Unknown route  | 0.56 s | 0.34 s

9 placeholders | GCB-NC | GCB-10C
---------------------------------
First route    | 0.65 s | 0.20 s
Last route     | 0.96 s | 0.59 s
Unknown route  | 0.54 s | 0.40 s

显然，使用 10 个分块的方式在每种情况下都战胜了没有分块的情况，甚至有些时候有 2 到 3 倍的性能提升。

使用正则表达式开发一个高性能路由

目录

关于路由的问题

组合正则

重置组数量

分块正则表达式

总结

版权

评论