基于 ETS 的漏斗限流

Author Avatar
Wincer 7月 08, 2020
  • 在其它设备中阅读本文章

ETS(Erlang Term Storage),是一种运行在 Erlang 虚拟机上基于内存的项式存储系统,在功能上类似于「简化版」的 Redis,但由于集成在 OTP 内部,相比 Redis 来说有两个优点:

  1. 不用像 Redis 必须通过网络端口访问,所以在理论上的存取性能会比 Redis 要高几个数量级;
  2. 存取的数据结构比较灵活,可以是任何的 Erlang/Elixir 项式。

在稍稍查阅了 ETS 的相关文档之后,我便决定将目前 API 项目中的漏斗限流模块使用 Elixir + ETS 重写(稍后会介绍一下我为什么这么做),当然只重写限流部分并不能替换现有的基于 Redis 的限流,在日后我会将整个的 API 系统都用 Elixir 重写一遍。

漏斗限流

漏斗限流是我之前在阅读《Redis 深度历险》了解到的一种限流方法,相比于传统的 Nginx 请求限制(ngx_http_limit_req_module)会更加的灵活。比如:漏斗限流可以接受短期内的多次访问,只需要不超过漏斗的总容量即可,在暂停访问则会一点一点恢复容量——这才应该是比较符合常理的限流方式,毕竟某接口的访问间隔不可能总是恒定的。

漏斗限流的初始化参数包含如下四个:

  1. 漏斗的总容量;
  2. 漏斗的流水速率;
  3. 漏洞当前的剩余容量;
  4. 上一次请求的时间。

其中前两项参数相同类型的漏斗都会保持一致,后两项则是每一个独立的漏斗都不一样。因此我在设计目前的限流模块时,只使用了剩余容量、上一次时间这两个参数,总容量与速率设置成了恒定不变的。

使用 ETS

继使用 Elixir 重写完豆瓣的爬虫之后,总感觉有写不舒服:Elixir 擅长领域不应该是在爬虫,而应该是在服务端应用上。因此我决定继续深入研究 Elixir。只是手中暂时也没有什么新坑,于是就想着使用 Elixir 把 API 系统重构一下,虽然重构完成后我也不一定会将现有的 Golang 版本的 API 替换(毕竟 Golang 的部署实在太香了),但重构应该是会加深我的 Elixir 的理解。

那么为什么我会选择使用 ETS 呢,其实有一个很重要的原因就是 Elixir 的数据是不可变的,因此当使用另外的数据结构(比如:Map)修改或新增键值对的时候,会涉及到比较大的内存和时间开销(复制旧的 Map 数据到新的 Map 上),于是我便把目光转向了 ETS。

其实我最早的打算是使用 Heap 这个数据结构,只是虽然 Heap 在新增键值对的性能很高(O(1)),删除的时候也不错(O(lgn)),但是在更新的操作很麻烦,需要查找出旧的删除,再插入新的。更关键的是 Elixir Heap 的实现方式是配对堆,与二插堆提供的上浮下沉操作不一样,自己实现配对堆的更新操作的话不知道会踩多少坑。。

简单写了一段代码来测试 ETS 的存取性能:

defmodule TestETS do
  defp set(0), do: nil
  defp set(n), do: :ets.insert(:ets_test, {:key}) && set(n - 1)

  defp get(0), do: nil
  defp get(n), do: :ets.lookup(:ets_test, :key) && get(n - 1)
end

简直出乎我的意料,一千万次的插入和查找操作均在 1 秒内完成(硬件水平:i7-9700K,16G 3000MHZ)。

#

惰性删除

在设计好了插入和更新(更新同样可以使用 insert 函数完成)后,还有一个非常重要的功能:「删除」。如果不定期将存储在 ETS 的键值对删除的话,内存的占用就会越来越多,所以得需要实现一个定期删除的策略。我考虑的策略是如果某 IP 五分钟之内没有请求,那么就将 Key 为 IP 的键值对从内存中删除。

为此需要记录每一个 IP 访问的最后时间,且最好按照时间来严格排序(从功能上来说 Redis 的 sorted set 其实是完美契合的,只是这样一来的话又得用 Redis 了,那目前为止的工作就没有意义了),如果不能严格排序的话,用 Heap 也是一个不错的选择。只是同样会因为 Elixir 数据不可变的原因,成为性能的瓶颈。

在 Google 了好一段时间之后,终于在 Stack Overflow 上找到了我想要的方案:使用另一个类型为 ordered-set(类似于 Redis 的 sorted set)的 ETS Process 来存储 IP 访问时间顺序的数据,为了避免数据的冗余,只需要保存 Key(即 IP)和时间即可,在需要删除的时候,先获得 ordered-set 的第一个元素,然后取出时间判断这个时间是不是已经过去五分钟了,如果是的话,就把这个数据删除,同时也需要将另一个 ETS Process 里对应的键值对删除。

对于这个「在需要删除的时候」的检测,我将其设置为每一次访问都会触发。

提高可用性

完成了删除的功能开发之后,限流系统已经可以正常使用,但是为了提高系统的可用性,还需要将当前系统的主要进程使用 Supervisor 监管。目前功能实现分为三个模块:

  1. Ral.Cell:这个模块是对外提供的接口,只有 choke 函数被定义为公开,其余辅助函数均对外隐藏。choke 接受一个参数 Key,不限制类型,但最好为 Atom,返回值是 true 或者 false,代表本次请求通过或者不通过;
  2. Ral.CMD:这个模块是接受 choke 函数被调用时产生的对数据库的操作,将其与 Ral.Cell 拆分是为了让消息能在两个进程之间异步地传输,提升性能;
  3. Ral.ETS:这个模块是专门控制 ETS 的相关进程的,如果和 Ral.CMD 合并成一个模块的话,需要将 ETS 的参数设置为 :public 或将整个 Ral.CMD 注册成 GenServer,但前者有些危险:任何进程都可以写入 ETS 的数据,理想情况应该是最多允许其他进程读取数据而不允许写入;后者与用 Message Queue 传递消息相比将显著的降低(大约 50% 的)性能。

三个模块中,需要被 Supervisor 监管的有 Ral.CMD:需要保证 Message Queue 消息接收方始终可用和 Ral.ETS:需要保证 ETS 的服务始终可用——至于 Ral.Cell,只包含对 ETS 的查询操作和对 Ral.CMD 的调用操作,因此无需对其使用高可用。


功能完善后,简单跑了一下 benchmark,每秒处理数可以达到 27w,而之前使用 Redis 的限流模块QPS 只有 2w,这就将系统的性能瓶颈从限流模块转向了 Web Server,算是一个比较成功的轮子吧~

本文标题: 基于 ETS 的漏斗限流
最后更新:2020 年 07 月 10 日 - 20:07
本文链接:https://blog.itswincer.com/posts/16c559c7/
本文采用:署名-非商业性使用-禁止演绎 4.0 国际 协议进行许可,阅读 相关说明