Nginx(ngx_lua) 过滤 10w 个 User ID

今天的工作太刺激了，一天下来正好解决了一个有意思的问题。晚上来记录一下。

上次解决了当有很大的 HTTP body，在 ngx_lua 里面读不到的情况后，还留下一个解决性能问题。上次提到，我们对于用户的每一个请求，都要根据一个 json 形式的规则，来判断怎么样路由这个用户。为了让读者更明白这个问题，举几个例子：

1. 给出一个 10万元素的用户 ID 列表，如果用户的 ID 在这里面，并且请求 URL 是 xx，Cookie 含有 xx，就转发到 Server A
2. 用户 ID 在列表转发出 10% 的用户到 Server B

此模块我是用 ngx_lua 写的，现在有问题的实现是这样的，将这个规则保存在 ngx.shared_dict 里面。每一个请求过来，我就解析成 lua 的 table，然后判断规则。我的测试环境是一台内网的服务器，单进程开 Nginx，wrk 测试是 1800~1900 request/sec。开启这个模块之后，只有 88 requests/sec，由于每一个请求都要经过这个模块，这样的延迟是无法接受的。

规则是发到每台机器的 Nginx 上，要在 Nginx 所有的 work process 共享一个变量，不知道除了 shared_dict 还有啥方法。其实我想过自己基于 shared_dict 实现保存 table，就是我把 table 打扁平，按照 key-value 放到 shared_dict，但是这项工作想想就挺大的，而且要踩坑才能保证正确性。

今天发了一个邮件到 openresty 社区（这个社区非常活跃和友好！），问了这个问题。mrluanma 和 tokers 回复说可以用 mlcache 。其实我之前也看了一下这个项目，但是没有看完文档，不知道靠不靠谱，既然大家可以说这么用，就去试一试了。

这其实是一个缓存，首先 L1 缓存是每一个 Nginx 进程里面的 Lua vm 会有缓存，如果没有命中，那么第二层缓存就是 ngx.shared_dict ，如果再没有命中，就会调用用户的 callback，也就是所谓的 L3. 由于是一个缓存项目，所以有一些缓存方面的问题，比如 dog pile，此模块都处理好了。我的用法比较特殊，只是拿它来做多个 worker/多个 HTTP requests 的共享数据，所以很多地方没有细看。

新建一个 cache 的 Nginx 代码如下，需要写在 http 里面。

这里要注意 3 个地方：

1. 因为要调用 set() 方法，我们是主动更新规则的，而不是等他过期。调用 set() 和 update() 要提供 worker 之间通讯的方式。mlcache 实现了通过 shared_dict 来通讯，所以我只要另外申请一个 shared_dict ，然后将这个 shared_dict 设置给 ipc_shm 就好了。
2. ttl 和 neg_ttl 设置成 0 ，理由同上。
3. 通过 _G 可以执行全局的变量，这样 lua 就可以直接使用 cache 这个名字了。

然后在设置规则的时候，直接通过 cache 来调用即可：

读取规则也是一样：

今天栽在这里很长时间，文档说第二个参数是 optional 的，我以为就可以不填。然后 set() 就填了两个变量。结果调试半天（Lua 奇葩的变量不够 nil 来补）。后来才明白这个 optional 的意思是你可以填一个 nil 进去，因为未定义的变量就是 nil 啊！难怪呢，我还想 lua 怎么实现的，难不成判断函数调用的参数个数？

另外一个点是 get() 方法要提供一个 callback 函数，L2 没有命中的时候提供就执行这个函数。在我这里，如果 L2 是 nil，那么 L3 也返回 nil 好了。

显示调用 set() 的一个非常重要的点是：一定要通知其他 worker 删除 L1 缓存。不然我们调用 set() 只是更新了一个 worker 的 L1 和 L2。在本文的场景下，worker 的数据不一致导致转发规则不一致是有问题的。这里只要在 set() 的之后调用一下 purge() 之后，通知其他 L1 去删除自己的缓存就可以了。 这里之前写的 purge() 函数的使用是有错误的，purge() 是清除缓存，包括用于 worker 交流的 shm 和 lua-resty-lrucache 的缓存，导致所有 L1 和 L2 miss 然后去 L3 更新，所以开销是比较大的（虽然在我这里，整个缓存=我的一个 table）。

正确的用法是这样的，使用 set() 的话，要多加一步，在 get() 前面调用一下 update() 。从源代码和文档得知，它的工作原理是这样的：set() 内置会广播一条消息，然后更新 L1 缓存（仅自己的 worker）和 L2 缓存。get() 之前 update() 这个调用会队列里面的广播事件，如果有事件的话，就先消费掉事件，没有事件的话，就什么也不做。注意所谓的 update 并不是更新 L2 缓存，而是消费所有的事件的意思。这样就做到一个 worker 更新某个值之后保持和其他 worker 一致了。

下图的第一个 worker 先 set 了一个值，然后通过 shared_dict 广播出去这个值的 name，回调函数是从 L1 删除这个值。其他 worker 蓝色的箭头表示 get() 之前 update() 去检查是否有事件需要处理。

修改之后性能从 88 requests/sec 上升到 300+ requests/sec，所有提升，但还是很慢。平均下来一个请求的延迟增加 3ms 多。

然后我又顺着这 10w userid 进行优化，规则里面这个 uid 是一个很大的 List，所以逻辑上是遍历查找一个用户是不是在列表里面的，O(n) 的效率。主要的耗时点就在这里。我想改成用 Set 结构来存，这样只要 O(1) 复杂度就够了。

问题是，Json 只有 Dict 和 List 两种数据结构，这个回答说的很好：

1. 编程实现 List 和 Set 互相转换是很简单的
2. Json 用于数据交换，你不能信任一个数据输入是 Uniq 的

但是我觉得 Json 增加 {"foo", "bar", "banana"} 这种形式好像没有什么不妥。

Anyway，我只能自己实现了，写了一个函数，在 Json 转换成 table 之后，找到我想转换的 Key，将它的 value 从 array 形式的 table（key 是 1 2 3 4 5 …）改成 Set 形式的 table (key 是各个元素，value 为 true），代码如下：

这样，在找的时候，只要看 value 是不是 true 就可以了：

这样改了之后，性能上升到 1800 requests/sec，跟不开启这个模块相比，基本上没有性能损耗了。

 

话说回来，这个问题跟我上一家公司的面试我的时候出的题目很像：给你一个 IP 列表，内存可以随便用，但是查找速度要快，如何看一个 IP 是否在表中？

我当时的方法是，一个 IP 用一个 bit ，bit 位要么是 0 要么是 1，表示此 IP 在或不在。表示世界上所有的 IP（IPv4）需要 2^32 个bit = 536M，将 IP 列表中的 bit 都置为 1，其余为0. 这里的关键是 IP 如何映射成 bit 表，IP 其实是 4 个字节而已，直接用 4 个字节所表示的数字作为 index 就好了。

巧合的是，这个周我正好认识了布隆过滤器。哈，我的想法真先进。

---