5天2亿活跃用户，2017QQ“LBS+AR”天降红包活动后台揭密
前言
刚刚过去不久的QQ“LBS+AR”天降红包玩法在5天内达成了2.57亿用户参与、共计领取卡券和现金红包20.5亿次的成绩，得到用户的一致好评，赢得口碑、数据双丰收。
作为一个全新的项目，后台面临着许多挑战，比如：
1. 海量地图活动数据管理
在全国960万平方公里土地上投放上亿的活动任务点，如何管理海量的的地图/任务数据？
2. 地图查点方案
如何根据用户地理位置快速获取附近可用的任务点？
3、数千个行政区红包余量的实时统计
红包雨活动是在区级行政区开展的，全国有数千个区级行政区，每个行政区都有数十个不同的红包任务及奖品，实时返回数千个地区的红包剩余量是如何做到的？
本文将从总体上介绍LBS+AR红包后台系统架构，并逐步解答上述几个问题。
图一 后台鸟瞰图（及各系统间大致调用方向）
1. 投放系统：活动、商户、奖品等信息的可视化配置页面
2. 静态数据层：CDB提供的MySQL服务，包含多个配置表
3. 配置同步系统：负责构建海量活动数据的缓存及同步，包含2个模块
a) 缓存构建模块：定期轮询式地从CDB中读取活动数据，如果数据发生变化，重新构建AR标准缓存格式的共享内存数据
b) 配置同步服务端：负责接收客户端请求，将共享内存数据下发到各个业务机器
4. 逻辑层：负责接受客户端请求，包含2个系统
a) 主逻辑：负责用户参加地图红包的核心逻辑，包含地图查点、抽奖等流程
b) 采集系统：负责实时获取各个活动及奖品的发放数据，用于主逻辑获取活动状态、客户端显示剩余计数、后台统计活动数据
5. 动态数据层：负责用户、活动动态数据的存储，包含4类数据
a) 发奖计数器：每个任务/奖品发放量
b) 用户历史记录：用户中奖的信息
c) 冷却与限额：用户领取的每种奖品的限制信息
d) 叠放计数器：可重复获取的奖品数量（本次活动是皇室战争卡券数）
6. 辅助模块：完成单个特定任务的模块
a) 频率控制：负责控制奖品发放速度
b) 订单：负责管理财付通现金订单
c) 一致接口：负责一致性路由，将同一个用户的请求路由到同一台机器的指定进程
7. 发奖相关系统：负责奖品发放的外部系统
下面主要为大家介绍海量配置管理、地图打点查点和实时的余量采集系统。
一 海量配置数据管理
LBS+AR红包与以往的红包最大的不同在于多了一重地理位置关联，全国有上千万的地理位置信息，结合活动的任务奖品数据产生了海量的配置数据，而这些数据都需要快速地实时读取（详细数据结构见后文）。这是后台遇到的第一个挑战。
类型 | 量级 |
任务数据 | 十万级 |
奖品数据 | 千级 |
奖池数据 | 十万级 |
全国POI数据 | 千万级 |
任务与POI关联数据 | 亿级 |
总体思路
配置数据有如下特点：
1. 数据量可能很大，数据间有紧密的关联
2. “一次配好，到处使用”，读量远高于写量
根据第一个特性，由于我们有Web投放系统的可视化配置能力，而公司内部的CDB能提供可靠的MySQL服务，有自动容灾和备份的功能，故选择CDB作为静态数据存储。
根据第二个特性，我们需要开发一种缓存，放弃写性能，将读性能优化到极致。
第一代缓存系统——写性能换读性能
缓存系统将数据读取方式从“远端磁盘读取”改为“本地内存读取”，读性能提高好几个数量级，它具有如下特点：
1. 缓存构建模块定时轮询数据库，在共享内存中构建缓存，配置变动可在分钟级时间内完成
2. 每张表使用2块共享内存，一块用于实时读，另一块用于更新，数据更新无感知，对业务零影响
3. 使用二分法查询数据，O(logN)的复杂度，性能较优
第二代缓存系统——O(logN)算法部分变O(1)
由于在地图查点流程中要执行数十至上百次的“任务与POI关联数据”查询，而对亿级数据进行二分查找每次要做将近30次的字符串比较，严重影响了系统性能。
为了解决这个问题，第二代系统针对POI数据离散化的特点，对量大的数据进行了前缀哈希，将一半的O(logN)操作转换成O(1)，进一步用写性能换读性能，性能得到有效提升：字符串比较的最大次数减少了将近一半。
算法流程：
1. 根据经验设置前缀长度
2. 遍历数据构造映射表，映射表存储了前缀及其对应的起始/末尾序号
3. 以前缀为Key，将映射表记在多阶哈希中（指定大小，枚举阶数搜索可行的压缩方案）
下面是一个构造映射表的例子：
对于样例数据
l 如果取3字节前缀，只有2个结果，产生的映射表比较容易构造哈希，但最大单条映射的记录长度是9，二分的次数仍然较多。
l 如果取5字节前缀，最大单条映射的记录长度是4，二分次数较少，但条目较多，哈希构造较难。
总结如下
一些可能的问题：
l 为什么不全部哈希呢？
上亿条数据每次改动都做全部哈希，耗费的时间和空间恐怕是天文数字。虽然我们舍弃写性能换取读性能，但用几个小时（几天）写耗时换几纳秒的读耗时，边际效用已经降到负数了。实践中做一半即可达到不错的读写平衡。
l 如果映射的记录长度十分不均匀怎么办？
这是此项优化的命门所在。幸运的是我们要优化的数据是POI相关的，而实践发现POI数据离散性极好，得出的映射记录数量非常均匀
l 如果哈希一直构造失败怎么办？
此项配置数据改动不多，如果对于某一版本数据构造失败，一般会有足够的时间根据数据特性调整前缀长度、增加哈希表大小、扩大阶数搜索范围来确保成功。如果时间比较紧急，也可以放弃此项优化，程序如果检测到哈希失败，会自动使用全部二分的方式读取。即便没有这项优化，我们还有许多柔性调控策略防止系统过载。
第三代缓存系统——中间层加速同步
上一代系统扩容后的结构如下图：
每台机器构建数据时都要去数据库读一次全量数据并排序，同时要在本地生成，每次大约耗时5分钟。而在这种架构下，所有机器的读数据库操作实际上就是串行的，当逻辑层扩容到100台机器时，完成全部任务将耗费好几个小时，考虑到配置修改的风险，这种架构在实践上是不可行的。
第三代架构图如下（箭头指数据流向）：
在数据层和逻辑层中间添加一个配置同步系统，先让少部分配置中心机器优先完成构建，再去带动数量较多的逻辑层机器，最终达到共同完成。有效解决了上一代平行扩容的问题，效果拔群。
实践效果
1. 极致读性能
2. 海量静态缓存数据的快速构建：完成全部机器近20G不同类型静态数据的构建和同步只需要30分钟
3. 数据同步无感知，实现无缝切换，对业务零影响
二 地图打点与查点
基于LBS的活动离不开地理位置相关的业务交互。在本次活动中，用户打开地图会定期向后台上报坐标，后台需要根据坐标获取周围可用的活动任务点，此节介绍打点与查点相关内容。
专业的地图服务会使用一种树形数据结构来进行空间查询，但LBS+AR红包活动的场景比较简单，故而选用了一种粒度较粗性能更好的打点查点方案，查询附近地理信息只需要进行四则运算，再一次用O(1)的方法解决O(logN)的问题。
地图格子方法介绍
将整个二位平面根据坐标分成一个个边长相等的正方形格子，根据用户的坐标用简单的数学运算即可获取相应的格子ID，时间复杂度O(1)。一个格子是一次查询的最小粒度。
在本次活动中，我们使用约200米边长的格子，每次查询会返回以用户为中心周围共计25个格子的任务点。
格子与任务点示例如下：
打点流程介绍
活动的投放是以任务的维度投放，每个任务关联一个POI集合，每个POI集合中包含几个到上百万不等的POI点，每个POI点都有一个经纬度信息（详细情况见下文数据结构设计）。
打点的责任是将任务为索引的数据重构为以格子ID为索引的数据，通过遍历缓存系统中的POI/POI集合/任务分片来实现。最终的格式如下：
查点流程介绍
1. 客户端上报经纬度
2. 根据经纬度计算中心格子ID
3. 根据中心格子ID及半径配置，获取全部格子列表
4. 在打点系统中获得此片区域全部Poi和Task信息
5. 检查任务状态后返回给客户端
三 采集系统进化之路
采集系统的主要职责是：
1. 实时返回区级行政区红包计数
2. 实时接受主逻辑的查询，返回奖品发放状态。
3. 返回活动预告以及参数配置等辅助信息。
这里面临的主要的挑战是区级行政区的红包余量计数，本文将着重介绍余量计数方案的演化思路。
朴素方案
来一个请求就去读一次！
进程级缓存方案
上一个方案显然不可行，而进程级缓存是最初使用的方案。这时采集功能并未单独成为一个独立模块，而是嵌在主逻辑里的。
主逻辑定期地扫描配置中全部有效任务，读计数器，将计数存储在STLMAP中。
假如每次数据缓存5秒，实际活动中约有8w条数据需要处理，每天活动分8场，100台逻辑层机器，对数据层的压力是400w次每秒，这个级别的读量几乎占满了全部Grocery性能。虽然方案比较成熟，但还是决定优化。
机器级缓存方案
这个方案做了2件事：
1. 将进程级的缓存上升到机器级，节省40倍进程访问开销
2. 将采集流程从主逻辑解耦，单独部署，减轻100台主逻辑机器绑定的访问开销
本方案使用有序的拼接索引+范围二分查找的方式替代STLMAP进行查询，使用sf1框架实现，服务与构造进程一体。由于sf1不支持并发外部调用，构造进程使用简单逐个查询的方法处理。
（sf1是后台较为常用的一种服务框架，性能较好，但不支持天然异步开发）
夹缝求生的最终优化
上一方案功能上确实可行，但性能上仍然存在问题：sf1框架不好做并发外部调用，用串行的方式查询数万条数据，完成一轮更新的时间是分钟级的，影响产品体验。
为了优化此问题，我们做了两级并发：
1. 利用Grocery提供的MultiKeyBatch方法，让Grocery接口机并发（详情请参见Grocery API，调用此接口格外注意业务数据大小及打包数量，轻易不要使用！）。示意图如下：
2. 将构造进程从sf1改为spp，利用mt_task方法并发请求。我们使用了宏定义IMTTask的简便用法。
需要注意的是，理论上可以只用第二种并发方式即可满足“采集模块”的需求，但从整个系统的角度看，防止数据层过载更加重要，第一种并发方式减少了10倍Grocery Intf请求量和一部分Cache请求量，虽然开发量较大，却是不可或缺的。
经过两级并发，分钟级的构建间隔被缩短到了1秒。但是不能发布！因为遇到了夹缝问题。
采集模块夹在客户端和Grocery之间，加速采集会影响Grocery，而减少机器又会影响客户端更新计数的效果，三个条件互相制约，需要想办法突破这个夹缝难题。
解决方法是：将查余量过程的O(logN)流程变成O(1)，性能提升10倍即可。
采集系统的主要业务逻辑是返回地区红包计数，之前的方案1秒内的数万次请求每次都会执行包括二分查找在内的全套逻辑，而事实上只有第一次是有必要的（地区的余量等信息1秒内的变化微乎其微）。那么答案就呼之欲出了，只需要给每个地区的结果做1秒钟的缓存即可。
最终把可以做缓存的流程全都加上了合理的缓存结构，单机性能成功提升10倍。
后记
本次项目总结的后台开发基本法：
1. 架构问题可以通过读写转换、时空转换的方式变成算法问题
2. O(logN)问题总有办法变成O(1)问题
3. 没人能预知未来。开发海量数据/海量请求的系统时，多用上面两个方法，从一开始就要尽力做到最好
另外不能忘了，在海量用户来袭的前夕，对自己的产品承载能力进行一个测试，任何企业都是一样，不能在最后一个环节被击溃，得不偿失···
腾讯提供了一个可以自主进行服务器性能测试的环境，用户只需要填写域名和简单的几个参数就可以获知自己的服务器性能情况，目前在腾讯WeTest平台可以免费使用。
腾讯WeTest服务器性能测试运用了沉淀十多年的内部实践经验总结，通过基于真实业务场景和用户行为进行压力测试，帮助游戏开发者发现服务器端的性能瓶颈，进行针对性的性能调优，降低服务器采购和维护成本，提高用户留存和转化率。
功能目前免费对外开放中，点击链接：http://wetest.qq.com/gaps 可立即体验！
如果对使用当中有任何疑问，欢迎联系腾讯WeTest企业qq：800024531
原文链接：http://wetest.qq.com/lab/view/285.html
