转载

当我们谈优化，到底在谈什么

副标题：参加饿了么编程马拉松感

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

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

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

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

题目描述

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

性能测试

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

测试环境

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

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

数据库设计

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

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

框架的选择

一开始我们用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到正无穷的时间里有哪些元素就可以了，然后根据这些元素的值就可以还原出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线程池到底搞多少个才是合适的？

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