摇一摇匹配架构设计

摇一摇功能分2种：

• 单纯的触发机制：拼多多摇一摇更换推荐商品、今日头条摇一摇得红包
• 需要进行匹配：微信摇一摇匹配附近的人，陌陌摇一摇匹配附近的朋友

在接到摇一摇需求的时候需要仔细分析业务需求。如果是第1种，只是单纯的触发机制，要是前端的工作，无论是什么形式，最后都只是一个单纯的请求而已。如果是第2种，就较复杂，需要详细设计匹配算法。

和摇一摇匹配类似的场景还有：滴滴司机乘客匹配、饿了么顾客骑手匹配、王者荣耀游戏匹配。

核心问题

我们来分析一下，摇一摇的核心问题有哪些：

• 匹配的目标是什么？
• 摇一摇后，我们能拿到什么数据？什么格式？
• 每个人都可以在任意时刻、任意地点进行摇动，如何建立一个稳定的模型来固化数据集？因为匹配只有对稳定的数据集才能执行，如果数据集能动态扩缩，就无法执行匹配。
• 匹配时，如何执行两两匹配？也就是，如果A匹配到B，那么B一定匹配的是A而不是C。
• 匹配时，如果要求多人一起匹配呢？（拼多多就可以多人匹配）
• 一线城市人口集中，十八线乡村人口稀少，如何解决热点区域请求太多和冷门区域摇不到人的问题？进一步地，请求太多可以做降级，但是如果摇不到人；应该如何设计业务逻辑？

解决方案

确定匹配目标

无论是摇一摇、滴滴司机乘客匹配、饿了么顾客骑手匹配、王者荣耀游戏匹配，即使同时存在其他目标，最核心的指标仍然是时空最近优先。所以，我们可以假设产品需求为：2秒内，100米内，多人匹配。

摇一摇数据格式

摇一摇的核心是用户、时间、空间。

用户：用户基本信息

一般是userld，略。

空间1：经纬度信息LBS（Location Based Service，基于位置的服务）

• 经度（longitude）的取值范围是［-180°，180°］，东经为正，西经为负。例如深圳是在东经113°
• 维度（latitude）的取值范围是［-90°，90°］，北纬为正，南纬为负。例如深圳是在北纬22°

数据项	数据类型	取值范围	是否可以为空	示例
longitude	Double	［-180°，180°］	否	120.280282
latitude	Double	［-90°, 90°］	否	-2.2802282

经纬度用double存，十进制精度15~16位。小数点后位数和定位精度如下：

小数点后	个位	1位	2位	3位	4位	5位	6位
经度	85390m	8539m	853.9m	85.39m	8.539m	0.8539m	-
纬度	111000m	11100m	11100m	1110m	111m	11.1m	1.11m

对于部分APP如果开发了“行政区域”的功能,可以拿到省、区、城市、道路的code,从而更好地进行定位。

空间2：蓝牙信号强度RSSI(Received Signal Strength Indication,接受信号强度指示)

如果用户打开蓝牙进行摇一摇，APP会通过蓝牙把自身的userld进行广播(需要APP同学开发这个功能)，同时也会接收附近的蓝牙数据。如果其他用户也在摇动，那么我们就可以得到{userld,蓝牙信号强度}这样的键值对。蓝牙信号强度RSSI越强，说明地理位置距离越近。
RSSI的取值范围通常是[-∞, 0]:

• 数值越大，蓝牙信号越好，距离越近，0表示发射的信号被完全接收了(实际上不可能)
• 一般-60~-80表示信号较好。
• 一般下限值不会超过-200

数据项	数据类型	取值范围	是否可以为空	示例
rssi	Integer	≤0	否	-51

时间:摇动时间

shake_time_ms，必须使用Long，去掉时区信息便于匹配。

完整的示例数据

{
    "user_id": 11111111,
    "latitude": -2.280282,
    "longitude": 120.280282,
    "nearby_bluetooth_users": [
        {
            "rssi": -51,
            "user_id": 11111111
        },
        {
            "rssi": -21,
            "user_id": 22222222
        }
    ],
    "shake_time_ms": 1630662526751
}

数据压缩

用户量一般在亿级，为了节省存储，可以对其中的数据进行压缩:

• userld如果太长，用lz4无损压缩
• 蓝牙信息，rssi的数值并没有用，有用的是“谁近谁远”的关系，因此按强度排序后保存userld列表就可以了

{
    "user_id": 11111111,
    "latitude": -2.280282,
    "longitude": 120.280282,
    "nearby_bluetooth_users": [
        22222222,
        11111111
    ],
    "shake_time_ms": 1630662526751
}

进一步地，这些key没有用，完全可以做个映射，减少字符：

// 稍微保留一点可读性
{
    "u": 11111111,
    "lat": -2.280282,
    "lon": 120.280282,
    "bt": [
        22222222,
        11111111
    ],
    "t": 1630662526751
}
// 完全靠文档或代码
{
    "0": 11111111,
    "1": -2.280282,
    "2": 120.280282,
    "3": [
        22222222,
        11111111
    ],
    "4": 1630662526751
}

固化数据集

现在，我们已经有了上传数据。但是匹配时，要求用户数据集要固定，不能一直有人加入和退出,因此要固化数据集。

考虑一下摇一摇的场景:

• 摇动期间、一个人只会加入一场匹配
• 在0点摇动的用户，一定不会被1点摇动的用户匹配到(2秒限制)
• 在漠河摇动的用户，一定不会被在曾母暗沙摇动的用户匹配到-(100米限制)

抽象一下就是:

• 构造一个场次ID,保证摇动期间,一个人只会加入一场匹配
• 场次中,相互之间时间差必须在2秒内
• 场次中,相互之间地理位置必须在100米内

一个自然的想法就是“场次ID=活动ID_时间_地理位置”，这样就可以把相同时间、相同地理位置的用户圈在一起。细化一下这个想法。

时间窗口

首先，用户几乎不可能在同一毫秒进行摇动，那就不得不把“时间点”扩大为“时间窗口”。

比如“2023-03-01 10:30:31”代表31~32的1秒窗口，可以容纳“2023-03-01 10:30:31.030-A用户”、“2023-03-01 10:30:31.100-B用户”….

但是，我们的摇动时间是2秒，也就是A用户如果在“2023-03-01 10:30:31.030摇动时，既可以被前1秒“2023-03-01 10:30:30”的全部玩家匹配上，又可以主动匹配到后1秒“2023-03-01.10:30:32”的全部玩家。A用户必须在3个窗口“30”、“31”、“32”做出选择。

因此，强行拟定一个规则：先依次查询“30”、“31”、“32”3个窗口，如果存在，立刻加入；如果都不存在，则创建自己的“31”这个窗口，等待其他人加入。只要遵循这个规则，A用户就有机会加入摇动时间前后的全部游戏场次。

这里可能有疑惑，A用户是31秒的，如果所有用户都遵循这个规则，怎么可能31秒的窗口还没创建，32秒的窗口就创建了？原因是窗口的存储可能是按可用区划分的，如果A用户跨可用区查，B用户直接访问本地可用区，就可能会出现B的32秒窗口先于A的31秒请求创建。

那假设摇动时间是3秒、5秒呢？我们把这个规则一般化：

【时间窗口机制】 用户依次查询前面若干个窗口、自己所在时间窗口、后面1个窗口，如果存在，立刻加入该数据集；如果不存在，则创建自己的时间窗口。其中，向前查找的窗口数量为摇动时间/时间窗口间隔-1

• 如果摇动时间2秒，时间窗口间隔为1秒，那么往前查找2/1-1=1
• 如果摇动时间3秒，时间窗口间隔为1秒，那么往前查找3/1-1=2
• ·······

这个公式是这么来的：用户摇动时间=等待其他用户加入游戏时间=窗口宽度，那么必须有如下关系，才能保证用户等待的时间内有其他玩家可以加入：(往前查找数+1)*时间窗口间隔=摇动时间。

地理位置网格

现在拥有的数据是经纬度和蓝牙。蓝牙已经表明了100米内(按蓝牙特性其实会更精确，10米内)的用户数据了，无需再处理。但是对于经纬度，目前只有所有用户的经纬度数据，并不知道哪些用户是在100米内的，不可能对所有用户用O(N^2)的时间去计算相互之间的经纬度距离。

抽象一下，问题就是需要用经纬度反向索引用户，很容易想到空间索引——网格索引。常用手段有3个：

• GeoHash：用Z阶曲线描述二维平面
• Google S2：用希尔伯特曲线描述二维平面，投影成正方形展开
• Uber H3：类似S2，投影成六边形展开

我们用最简单的GeoHash来实现,对GeoHash深入一下。

空间索引Geohash思路

经纬度本身就是一个空间索引，但这个粒度太精确了。为了快速判断临近点，我们可以把地球划分成一个个类似正方形的小区域，如果拥有小方块端点的经纬度数据库，就能用小方块反向索引所有点，从而把临近点聚合起来。

这个经纬度数据库太难维护，如果能直接用某个代号比如A、B、C、D表示好所有小方块，然后经纬度直接能hash到这个代号上就好了。

我们把经纬度表示的地球展开成正方形，如果纬度范围[-90°, 0)用二进制0代表，(0°, 90°]用二进制1代表，经度范围[-180°, 0)用二进制0代表，(0°, 180]用二进制1代表，那么地球可以分成如下4个部分：00、01、10、11

进一步地，我们对小方格递归地做划分，可以得到更多小方格，并以纬度在奇数位，经度在偶数位的顺序单字节交叉配对，每个小方格的代号就是确定的：

这就是Z形曲线的GeoHash。网格越多，误差越小。

• geohash 转换网站：http://geohash.co/
• geohash 地图：http://geohash.gofreerange.com/
• geohash开源java库(apache 2.0)：https://github.com/kungfoo/geohash-java
• geohash精度表：

  geohash length	lat bits	lng bits	lat error	lng error	km error
  1	2	3	±23	±23	±2500
  2	5	5	±2.8	±5.6	±630
  3	7	8	±0.70	±0.70	±78
  4	10	10	±0.087	±0.18	±20
  5	12	13	±0.022	±0.022	±2.4
  6	15	15	±0.0027	±0.0055	±0.61
  7	17	18	±0.00068	±0.00068	±0.076
  8	20	20	±0.000085	0.00017	±0.019

GeoHash应用于摇一摇

我们可以把GeoHash的字符串，拼接到场次ID上。问题变为，我们初始化时用多少精度的GeoHash串呢？这取决于如何解决GeoHash的副作用——网格隔离。

GeoHash在搜索临近点的时候有个严重的问题，就是网格隔离。如图，user1最近的点应该是user2，但由于不再同一个网格，被场次隔离开，只能匹配稍远一些的user4。即使user1和user2是面对面地摇，也会神奇地发现竟然摇不到对方!
考虑到实际中，手机GPS精度也不高，面对面的用户通常经纬度都是一样的。所以不用考虑这种极端情况，取一个经验值一一默认7位。

开发思路

至此我们有了一个场次ID：活动ID_时间窗口_GEOHASH，需要创建时间窗口、聚合用户数据。
（1）存储选型：Redis
（2）相关命令:

• 尝试加入一个已经存在的窗口：jedis.rpushx(如果存在则push)
• 创建当前窗口：jedis.rpush(如果不存在则创建,然后push)、jedis.expire
• 获取指定窗口的所有用户：jedis.lrange(key,0,-1)

匹配

什么时候触发匹配?

• 将“场次D”、“时间窗口剩余时间”返回给客户端
• 客户端等待“时间窗口剩余时间”，如果提前发起请求，直接拒绝
• 客户端发起查询请求，触发匹配；如果已经有其他用户触发过匹配，存在匹配结果缓存，则直接返回结果

匹配要求

（1）完成匹配：匹配看似有点像“二分图的最大匹配”模型，但实际上并不是，因为一个节点可以有多条边，不一定能二分。所以，最快的方式就是按照“距离最近”做贪心。
（2）匹配结果一致性：因为任何用户可能在任何时间触发匹配，所以无论何时、无论哪个用户，计算出的匹配结果必须完全一致。

全局匹配算法

核心：请求一次，计算出全部匹配结果。

蓝牙匹配

蓝牙匹配具有如下特性:

• 单向匹配：user1的蓝牙列表有user2，user2没有搜索到user1，但是他们一定符合“距离很近,且都在摇一摇”的条件，因此仍然可以匹配。此时距离为蓝牙搜索距离x1。
• 传递性:
  • 父节点和父节点：user3和user4都和user1存在蓝牙关系，那么即使user3和user4没有直接蓝牙关系，也可以匹配。此时距离为蓝牙搜索距离x2。
  • 父节点和子节点：user5和user6也可以匹配。
• 单次匹配：一个用户只允许存在于1个匹配关系中。user1和user2匹配之后，就不能再和其他玩家匹配了。

因此:

FOR 场次内所有用户
  FOR 当前用户的蓝牙关联用户列表(按强度排好)
    IF 当前用户未匹配&蓝牙搜索用户也未匹配 THEN 匹配成功
    IF 当前用户已匹配&蓝牙搜索用户未匹配 THEN 蓝牙搜索用户加入落单池（当前用户 -> 蓝牙用户）
    IF 当前用户未匹配&蓝牙搜索用户已匹配 THEN 当前用户加入落单池（蓝牙用户 -> 当前用户）

加入落单池:(已匹配 -> 未匹配)
  IF 落单池中已经有等待的用户 THEN 匹配成功
  ELSE 放入落单池:已匹配 -> 未匹配

例如:

• 扫描user1：
  • user1未匹配，user2未匹配 -> 匹配(user1, user2)
  • user1已匹配，user3、user4未匹配 -> 匹配(user3, user4)
  • user6等待匹配
• 扫描user2：没有蓝牙关联，跳过
• 扫描user3：没有蓝牙关联，跳过
• 扫描user4：没有蓝牙关联，跳过
• 扫描user5：user5未匹配，user1已匹配 -> 查询user1关联列表，发现user6等待匹配 -> 匹配(user5, user6)
• 扫描user6：user7等待匹配
• 扫描user7:没有蓝牙关联,跳过
• user7在蓝牙匹配中落单

经纬度匹配

本来，我们应该对剩余的全部用户，两两之间计算距离，来找到最近的用户进行匹配。这样还是太慢了，可以用同样的方式一一先计算更精确的geohash缩小范围，然后再执行距离计算。
由于geohash范围缩小，网格隔离的副作用增大，为了避免副作用影响，搜索附近的点时，除了当前网格，再多搜索附近8个网格。假设搜索半径为r，geohash方格的误差为Δ，那么方格的边长为2Δ。考虑极端情况，用户正好在方格的角点上，为了保证搜索半径被geohash方格覆盖，那么至少有：r<=2Δ。按照geohash精度表，可以很容易计算出如下结论：

geohash字符位数	实际精度Δ	匹配半径r要求
8	±19米	≤38米（如20米）
7	±76米	≤152米（如100米）
6	±610米	≤1220米（如1000米）

计算所有用户的geohash
IF 用户已经匹配 THEN 跳过
找出周围含自身共9个geohash方格，计算地理球面距离，找出距离最近的用户，执行匹配
仍未匹配的用户，则本场游戏无法匹配

实现上，一定注意计算的是球面距离，VincentyGeodesy.distancelnMeters(point1, point2);

加锁匹配算法

核心：用户先来先匹配，只计算自己的匹配结果，不计算全局结果。

圈出附近用户

• 使用当前用户的经纬度信息，计算其所在的geohash分片，同时根据geohash算法找到其周围的9个方格，同时获取到9个方格内参与游戏的所有用户数据
• 以当前用户的位置为圆心，以最大匹配距离为半径，在地图上画一个圆，这个圆就是我们的搜索范围
• 得到该圆的外接正方形，通过经纬度范围对获取的数据做一遍初筛，以减少后续计算距离的运算量

加锁匹配

待匹配用户A、B:
  原子性地同时获取匹配锁A、匹配锁B -- redis的msetnx命令
  IF 获取锁失败
    放弃锁
  ELSE
    IF A和B都未被匹配
      匹配(A,B)
   ELSE
      放弃锁

为什么要原子性地同时获取两个锁？因为如果依次获取锁，场景就和哲学家就餐问题一样，可能产生循环等待和相互等待的加锁问题：

（1）循环等待：一次获取锁，3获取4，2获取3，1获取2，4获取1，由于匹配是不会等待的，造成匹配立刻失败。

（2）相互等待：2获取3，3获取2；1获取4，4获取1。通常情况下，距离相近的用户会首先相互搜索到，因此这种情况出现概率很高。

所以，类似哲学家就餐的解法，我们同时原子地获取多个锁。假设1、4的锁被1获取到，只让1做匹配决策，4匹配失败被动接受匹配结果即可。

蓝牙匹配和经纬度匹配

IF 已经被其他节点算出结果 THEN 直接返回匹配结果

蓝牙正向匹配：搜索当前用户的蓝牙列表(已按信号强度排序)，逐个尝试加锁匹配，匹配成功则返回

蓝牙逆向匹配：根据蓝牙的技术特点，可能存在A能搜索到B，但是B无法搜索到A的情况，因此需要再进行逆向的匹配。在数据集查找当前用户被蓝牙搜索到的用户，按信号强度排序(如果rssi被压缩，此步做不到)，逐个尝试加锁匹配，匹配成功则返回

蓝牙传递匹配：使用蓝牙还可能存在A与B无法互相搜索，但却同时被C搜索到的情况，因此需要再进行间接匹配。获取搜索到了当前用户的所有用户列表，按信号强度排序，逐个尝试匹配；针对每个目标用户，获取他们搜索到的所有间接用户，排除掉当前用户和未圈选中的人群之后，按信号强度排序，逐个尝试匹配，匹配成功则返回

经纬度匹配：对每个用户，进行球面距离匹配，如果匹配成功则返回

IF 匹配成功 THEN记录匹配结果因为可能跨geohash分片匹配，所以缓存结果key不能使用shakeId，用窗口开始时间就可以了，“窗口时间_userId”

IF 抢锁失败 THEN 自旋几次，让其他节点先做决策

IF 匹配失败 THEN 轮空。

多人匹配

多人匹配，思路类似。

摇不到人如何处理?

方案1 直接轮空

• 直接说没匹配到，请重试。
• 如果不需要进行后续步骤(不需要后续聊天、组队等)，直接匹配一个机器人，用户无感知，不知道是匹配到真人还是机器人

方案2 动态匹配

类似LOL、王者荣耀一类的游戏，一旦第一次没有匹配到，就升级搜索范围，扩大搜索。

动态匹配实际上不好实现,和用户的分布关系太大。最好还是直接轮空，多跟PD battle一下。

热点区域和冷门区域法

一个时间窗口如果超过64KB数据，会产生频繁GC。因此如果1km内超过300个用户同时在摇，我们称为热点区域。热点区域需要执行动态降级，如果一个区域连续5次用户数量大于300，我们就将该区域geohash精度调高一级。相反，如果一个区域连续5次用户数量小于2，我们就将该区域geohash精度降低一级。

多级队列法

相当于我们构造多个虚拟地球，如果在第一层世界中没有匹配到，我们标记这些用户，将他们放入第2层、第3层世界，然后调整geohash，比如第1层要求是100米内，那第2层就调高到1000米去搜索(不过搜索完后,最终还是只匹配100米)。

实战经验

1、沿海城市、一线城市，聚集的人非常多。
2、单场匹配人数，不应超过300人。
3、某活动，蓝牙匹配用户：经纬度匹配用户=1:5，经纬度平均匹配距离20m。