参加饿了么编程马拉松感

饿了么在今年十一月的时候举办了一个黑客马拉松，官方主页在这里，看了简介以后我认为有两点比较吸引人。

首先，比赛形式比较新颖，之前也参加过类似的马拉松以及听闻过很多XX编程马拉松，形式都是差不多的：接受组队报名，然后花上两天时间大家待在一个地方通宵编程实现一个和主办方做的事完全没有关系的创意，一般会在第二天下午开始做presentation，最后会根据评委打分决出获胜队伍。这种类型的比赛，根据我的观察，presentation是最重要的，其次是idea，最后才是技术。而这次的饿了么举办的马拉松分初赛和决赛，初赛前10名进入决赛，初赛需要实现一个功能，最后评测完全靠的是实力和技术，分数公开透明。虽然还不知道决赛题目是什么，但也令人期待。

其次，如果真的进了前10名，能去参加决赛，大家可能都是非常强的高手，想想也令人激动不是么。

于是和另外两位小伙伴一起参加了这次初赛。

题目描述

初赛的题目是使用Python, Java, Go三种语言（任选其一）实现一个“限时抢购”功能。具体来说，就是实现一个web服务，对外提供一个restful接口，让模拟用户可以通过接口来抢购数据库中的食物。评分使用功能测试、性能测试的结果做为指标。功能测试就是看有没有超售，错误处理之类的，通过了功能测试才能进入性能测试这个打分的环节。

性能测试

  1. 给定 100 个食物，每个库存 1000
  2. 脚本模拟 1000 个并发用户同时进行抢单。（登录 -> 查看食物列表 -> 随机选择 1-3 个食物购买 -> 下单）
  3. 将按照“成功下单数/秒”的峰值进行排名

测试环境

  1. 2CPU-4GB 服务器 * 3，运行应用。（请求会随机分布到 3 台服务器上）
  2. 2CPU-4GB 服务器 * 1，提供 redis
  3. 25GB 1000qps 腾讯云数据库，提供 mysql
  4. 12CPU-12GB 服务器 * 1，运行性能测试脚本

一个能跑的程序还是很容易实现的。其中有一个难点是，因为是分布式服务，所以我们必须保证下单并减库存的操作是原子的，传统的读-改-写在高并发情况下不适用，好在redis支持lua脚本是原子的，于是这个问题就解决了。

数据库设计

因为提供了redis，又是性能的比赛，所以我们决定放弃mysql，完全用redis来做。

因为负载均衡的存在用户请求可能被分发到任何一台应用服务器上，redis中需要存储一些共享的数据，如用户登录后的token，用户的购物车，用户的订单，以及最重要的食物库存，如下图所示：

KEY                             VALUE
---------------------------------------------------------
token:user                      hashmap: {<tokenid>: <userid>}  // 检测token的合法性
user:order                      hashmap: {<userid>: <orderid>}  // 获取某个user的订单，系统只允许一个用户下一单，所以这个hashmap能检测是否重复下单
cart:user                       hashmap: {<cartid>: <userid>}   // 获取购物车是哪个user的
cart:<cartid>                   hashmap: {<foodid>: <cnt> }     // 该购物车的食物及数量
order:user                      hashmap: {<orderid>: <userid>}  // 这个order对应哪个user
order:<orderid>                 hashmap: {<foodid>: <cnt> }     // 每一个订单包含的食物及数量
food:stock                      hashmap: {<foodid>: <stock>}    // 食物的库存

框架的选择

一开始我们用python写了个能跑过测试的版本，能异步的地方都用了协程，但是分数还是比前十的队伍差了很多，于是我们怀疑是不是语言层面的问题导致了分数差那么多，于是我们队伍的小伙伴对python和go做了一个性能比较，其中每一次访问/都会使redis调用一个脚本，这个脚本和我们下单的操作运算量差不多，结果如下：

LANG    WEB         REDIS             METHOD      TIME
---------------------------------------------------------
python  tornado     redis-py          coroutine   1.406ms
python  tornado     redis-py          sync        1.022ms
python  aiohttp     asyncio-redis     coroutine   0.879ms
python  falcon      redis-py          gunicorn    0.669ms
node    express.js  node-redis        event       0.301ms
golang  net/http    gopkg.in/redis.v3 coroutine   0.245ms

我们发现在相同的环境下，go的性能是最好，虽然很不情愿，但不得不放弃python用go重写。事实证明，用go以后分数有明显上升。

实现

食物的库存存在redis的hashmap中(foodid映射到stock)，下单用lua脚本来做，查询库存就返回所有食物列表和相应库存。后来我们发现这个方法效率太低，每次查询库存都要返回所有的食物，即使很多食物库存都没有变化过，太浪费I/O。于是我们小伙伴提出了一个基于timestamp的方法，结果就是每次查询库存值传输某个时间之后变化的食物，大大减少了流量。

具体方法是这样做的：本地存储一个当前timestamp，并且redis端存储一个foodid到该食物最后更新时间，然后把(更新时间|foodid|foodstock)这个长整型存储在redis中的ordered set里，key就是更新时间，于是我们在查询库存的时候，只需查询从app的timestamp到正无穷的时间里有哪些元素就可以了，复杂度是log(N)的，然后根据这些元素的值就可以还原出id和stock值。

这是个非常精妙的思想，当时在腾讯实习的时候看过微信内部的一篇文章，说微信为了同步不同设备上的消息记录，用的就是这个时间戳的思想，差分传输而非全部。

下单操作就麻烦一些了，先根据id找到这个食物的最后更新时间，然后根据这个值从ordered set里拿到(更新时间|foodid|foodstock)这个长整型，分解出id和stock，减完库存还得删除原来的元素插入新的元素，这些都是log(N)的操作。

突破

随着比赛的进行，我们发现自己的分数卡在一个瓶颈了。某一天晚上我突然发现，我们实现了系统的强一致性，而题目里根本没有要求我们这么做！我们用timestamp的目的是为了让查询库存节省流量，但是带来的tradeoff是每次下单的时候都有好几次log(N)操作（需要根据查询食物最后更新时间来找到这个食物的库存，而后者存在redis的ordered set里）。但是在测试的时候根本就没有测获得库存的强一致性，题目要求的是最终一致性，所以我们没必要实现地那么老实，只要一个goroutine隔个两秒去redis拉一下数据就可以了，然后我们的下单操作变得异常简单，把stock存成hashmap，只是几个简单的O(1)操作。

我们为了库存显示的强一致而牺牲了下单的效率，这明显是不值得的，我们宁愿下单快，但库存会有一些误差。这在实际工程也是合理的，网站显示库存还剩一个，但是你下单的时候发现库存为0，这是用户可以理解的，手慢了就被别人买掉了。但是这个妥协大大带来了下单峰值的上升。

优化

整个比赛后期就是在不断优化的过程中，其中一个比较难的地方在于如何确定瓶颈，在redis？在I/O？还是在APP服务器的处理速度？最后几天就是在不断地对程序做profile然后性能优化然后再做profile。一个印象比较深的例子是有一个操作我在不断纠结要不要放到redis的lua脚本去做，如果放了会增加redis的负载，但是会减少网络I/O的时间，线上测出来的结果又是差不多的，那这个做还是不做？在比如reids线程池到底搞多少个才是合适的？

另外，把能缓存的数据全部缓存起来，性能会提高不少。

TradeOff

做这个项目中遇到了太多需要tradeoff的地方：

  1. 代码的可读性和性能，为了提高性能我们牺牲了很多可读性
  2. 不要用第三方库，虽然手写一些功能会比较累、易出错，但有些第三方库为了通用性，使得效率大大下降。我们把使用的一些第三方库都删掉以后，效率又提高了不少
  3. 下单一定要快，这样每秒的单数就增加了，而实时显示库存就显得不那么重要
  4. 用户注册返回的token如何生成得高效且具有随机性
  5. 将Go程序设置为多核后，对共享变量的读取用乐观锁还是悲观锁

代码

放在了github上。

我们的代码峰值是4600多单每秒，而饿了么大学（好像是内部员工组成的队伍）的实现是5000多单每秒，还是有400的差距。

感想

  • 队友很重要，两个小伙伴很给力（乐群和骆神）
  • Go好简洁，很好用
  • 做系统考虑好TradeOff很重要
  • redis好强大，单线程事件驱动网络I/O的典范
  • 这是一个优化比赛，看谁能优化到极致

彩蛋

在看了饿了么5000分的标准实现后，发现这400分的差距还是有原因的，为了性能redis里面存的越少越少，这样I/O次数就少，罗列一些我们组没有注意到的点：

  • token其实是不需要存redis的，token如果是userinfo的一个函数映射，那么每台机器都可以根据这个函数事先为每个user生成一个token，而不是随机字符串。比如md5(userId)作为token，然后在起服务器的时候就把token生成好，并且维护一个token到userinfo的映射（为了之后带token的请求找到该user），就完全不需要redis了。这样做虽然好，但token好像无法过期了？于是我问了一下主办方，给我发了一篇文章，思路非常好，把client当做database，这样本地就根本不用存一个用户相关的数据，比如token。虽然这篇文章表明了token可以不用存储，但没有回答token的生成和userinfo相关到底是不是一个好的选择？在我们的实现里，用了随机字符串来作为token，每次都是on-the-fly生成，效率明显会差一点

  • 为了判断user是否只下了一单，在我们实现里用了user:order这个hashmap。官方没有这个数据结构，只维护了order存了哪些food和count（也是个hashmap），然后每个user的order被命名为o_<userId>，所以只要用EXIST命令看一下这个key存不存在就知道用户有没有重复下单了

  • 把userId嵌到购物车Id里面，那么reids就不用存购物车Id到userId的映射了（值得吐槽的是判定购物车Id是不是有效的方法是传来的string是否满足他事先规定的pattern，这在现实中完全不能用啊）

  • 我们的实现里下单时把购物车这个hashmap完整地复制到了订单这个hashmap，而官方只用了一条redis命令RENAME

  • 官方实现里，每个用户下单的orderId竟然是事先生成好的，其值就等于userId，难道这个不应该是on-the-fly生成的么，这样的好处是下单返回成功和上述的RENAME可以异步执行，这样的设计使得我们设计中的order:user成为累赘了，因为userId本身就是orderId，根本就不用这个查找

  • 在官方实现里是怎么查询所有订单的呢？因为订单都是以o_开头的，所以用redis的命令KEYS o_*就可以获取所有以o_开头的key，那么所有订单也自然就拿到了，这里需要(1+n)次（1次查询所有订单名字+根据返回的名字查询n个订单的详细内容）redis访问，但查询订单不在benchmark里，所以实现得耗时一些没有影响

  • 官方用了go-reuseport这个库，即多进程端口复用，据说比单进程端口要性能好一些

  • 官方把go的GC关掉了，据说效果不大，在我们的profile结果里GC也只占了很小一部分

结论就是，虽然官方实现有几点值得吐槽的地方（比如判定作弊的标准不太明确，导致可能有些选手即使想到了优化方法，然后觉得这个实际中不能用，就放弃了），为了性能牺牲掉了很多实用性（比如官方Go的实现没有可拓展性，假如来了一个需求说一个用户可以下多个订单，就要大改了），毕竟是个性能比赛。但确实有很多地方值得学习，根据这个特定的场景，redis数据库设计得非常简洁，大大减少了I/O次数（瓶颈），而且用了许多redis技巧和Go技巧，特别是发出异步redis请求的goroutine和channel的使用，对于初学Go的我帮助很大。