面经策

如何在附近 100w 的商户中，快速找到离你最近的 5 家商户？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

"百万人次中找最近 5 家商户"是 LBS 的经典问题（美团/大众点评的核心链路），我会先讲标准方案，再讲业务量级与体验的权衡。

标准方案：GeoHash 前缀粗筛 + 精确距离精排

  • GeoHash 编码：经纬度二分交替编码成 base32 字符串，前缀相同 = 区域相邻，长度决定精度：6 位约 1.2km×0.6km，7 位约 150m
  • 查询流程：对用户位置编码 → 前缀匹配召回同区域商户 → 边界问题用周围 9 宫格（自身 + 8 邻域）覆盖 → 候选集算精确哈弗辛距离排序 → 取 Top5
  • Redis 原生支持：GEOADD key lng lat member + GEOSEARCH key FROMLONLAT ... BYRADIUS 1km COUNT 5，内置 geo 编码和距离排序，中小规模直接用它，别自研

量级分档

  • 十万~百万商户：Redis GEO 单集群足够（内存百 MB 级），QPS 5 万+ 无压力
  • 亿级 POI / 多维度筛选（品类+评分+距离混合排序）：Geohash 召回 → ES/向量检索做业务排序，LBS 召回和业务排序分层

业务架构视角（差异点）

  1. 精度是成本/体验权衡：召回半径先按商户密度自适应——市中心 500m 够 5 家，郊区要 5km；固定半径会出现"城区返回一堆、郊区返回零"，郊区空结果直接等于用户流失
  2. 这是流量入口型功能：响应从 100ms 涨到 1s，进店转化肉眼可见地掉，值得用内存换
  3. 商户变更频率低（一天几百次），数据全量驻内存毫无压力，预计算 + 缓存命中率接近 100%
  4. 扩展业务点：最近距离只是排序因子之一，营业状态、营业时间、配送范围（外卖场景用多边形而非圆）都要能叠加

🏗 系统架构师 ​

附近商户检索我用GeoHash / Google S2 编码把二维降成一维，这是架构上的关键一步。

方案演进按量级分档：

1. 中小规模（百万级商户，万级 QPS）——GeoHash + Redis 写入时把每个商户的经纬度编码成 GeoHash 字符串存入 Redis 的 GEO 结构（底层 zset）：

  • 查询：GEOSEARCH key FROMLONLAT lon lat BYRADIUS 5 km ASC COUNT 5，一步拿到最近 5 家，Redis 单节点数万 QPS 无压力
  • 原理：GeoHash 把经纬度交替二分编码成 base32 字符串，前缀相同 = 区域相近，一维前缀匹配即可用有序结构索引；Redis GEO 用 52 bit geohash 做 score 存 zset
  • 边界问题：GeoHash 的 Z 阶曲线有突变，跨格子相邻的点编码可能差很远，所以搜索时要同时查周围 9 宫格的格子（Redis GEOSEARCH 内部已处理）

2. 大规模/多条件过滤——ES geo_point 或 S2 如果还要叠加"营业中、评分、品类"等过滤条件，Redis 拿回的 ID 再回查 DB 就绕了，直接 ES：geo_point 字段 + geo_distance 排序，filter 条件下推，性能同样优秀；Google S2 的 cell 覆盖（Covering）适合做地理围栏和多边形场景。

3. 超大规模：商户数据按地理分片（单元化），流量按城市路由到就近集群。

核心要点：不能对 100 万商户逐个算 Haversine 距离（暴力 O(n) 在高 QPS 下不可接受），空间索引（GeoHash R树思想）把候选集缩到几十个，再精算距离排序取 top5。

💻 全栈开发专家 ​

直接上 Redis GEO，底层是 geohash + zset，为"附近的人/店"场景而生。

实现

bash
# 商户入驻时写入（key 建议按城市分：shop:geo:310000）
GEOADD shop:geo:310000 121.4737 31.2304 "shop:10001"

# 查附近 5 家，按距离升序
GEOSEARCH shop:geo:310000 FROMLONLAT 121.47 31.23 BYRADIUS 3 km ASC COUNT 5
java
List<GeoResult<RedisGeoCommands.GeoLocation<String>>> results =
    stringRedisTemplate.opsForGeo()
        .search("shop:geo:310000",
            GeoReference.fromCoordinate(121.47, 31.23),
            new Distance(3, Metrics.KILOMETERS),
            RedisGeoCommands.GeoSearchCommandArgs.newGeoSearchArgs()
                .sortAscending().limit(5))
        .getContent();

拿到 shopId 后再查详情（详情放普通缓存，避免大 member）。

原理一句话 geohash 把二维经纬度编码成一维字符串，前缀相同 = 位置相邻，所以"附近"查询变成 zset 的范围检索，O(logN)。

100 万量级的工程处理

  • 按城市拆 key：单 key 百万 member 没问题，但拆开更利于淘汰和运维。
  • 多级半径放大：先搜 500m，不足 5 家放大到 2km、5km，避免直接大范围扫描。
  • Redis GEO 的距离排序是近似的（球面距离），精度要求高的（计费场景）取出后应用层精算 Haversine 再排。

踩过的坑 写入时经纬度顺序是 经度 纬度，反了查出来全是空，这个坑我见同事踩过两次。