系统设计：附近的人（LBS 服务）

「附近的人」「附近的商家」「附近的骑手」本质是同一个问题：给定一个坐标与半径，快速找出范围内且满足条件的对象。难点不在单次查询，而在千万级用户高频上报位置时，如何既不写爆存储，又能毫秒级响应。

1. 需求分析

功能性需求

• 位置上报：客户端周期性上报经纬度
• 附近查询：按半径（如 1km/5km）返回附近用户或 POI
• 排序：按距离、活跃度、综合评分排序
• 过滤：性别、年龄、在线状态等条件
• 隐私：模糊化位置、隐身模式、黑名单

非功能性需求

• 查询延迟：P99 低于 100ms
• 上报吞吐：日活 5000 万，每人 30 秒上报一次
• 可用性：99.99%，热点城市不降级
• 精度：城市级可到米级，隐私场景可降级到百米级

核心难点

1. 写入放大：每个用户高频更新位置，写量远大于读量
2. 热点倾斜：一线城市与热门商圈的密度远高于郊县
3. 状态管理：如何判断用户是否「在线」，离线用户不应出现在结果里

2. 容量估算

• 日活用户：5000 万
• 上报频率：每 30 秒一次 → 每人 2880 次/天
• 写入 QPS：5000 万 × 2880 / 86400 ≈ 167 万 QPS
• 峰值按 3 倍计：约 500 万 QPS
• 每次位置记录约 100 字节 → 167 万 × 100B ≈ 167 MB/s 写入

结论：写量是读量的数十倍，所以位置数据不能直接写关系型数据库，必须用内存 + 分片方案，且要考虑「只保留最新位置」以压缩存储。

3. 整体架构

客户端(App/小程序)
      │ 位置上报(HTTP/长连接)
      ▼
   接入网关(鉴权、限流、坐标脱敏)
      │
      ▼
 位置写入服务 ──► 内存地理索引(Redis/自研)
      │                  │
      │                  ▼
      │            附近查询服务 ──► 过滤/排序 ──► 结果
      ▼
  持久化(冷备/历史轨迹，Kafka→HBase)
      │
      ▼
  在线状态服务(心跳 + TTL)

写入路径

客户端上报坐标，网关脱敏后写入内存索引（按地理分片），同时异步投递 Kafka 落历史轨迹。

查询路径

查询服务根据坐标与半径计算覆盖的索引格，从内存索引取出候选集，再过滤与排序。

4. 数据模型

内存中的在线位置表

location_online (
    user_id      BIGINT PRIMARY KEY,
    geohash      VARCHAR(12),      -- 用于粗筛
    lat          DOUBLE,
    lng          DOUBLE,
    cell_id      INT,              -- 索引格 ID
    updated_at   BIGINT,           -- 毫秒时间戳
    status       TINYINT,          -- 在线/隐身/勿扰
    profile_hash VARCHAR(32)       -- 画像标签的压缩指纹
)

索引格表：Redis Hash 与 Sorted Set

cell:{cell_id}  ->  ZSET
    member: user_id
    score:  distance_rank 或 updated_at

冷存储中的历史轨迹表

location_history (
    user_id     BIGINT,
    ts          BIGINT,
    lat         DOUBLE,
    lng         DOUBLE,
    PRIMARY KEY (user_id, ts)
)

设计要点

• 在线位置只保留最新一条，避免历史堆积导致查询变慢
• 用 updated_at 做 TTL，超过阈值自动判为离线
• 索引格按地理分片，热点格可拆分为子格

5. 地理空间索引

Geohash

把经纬度递归二分为 Base32 字符串，前缀相同表示空间相邻。长度每加 1，精度提升约 5 位二进制。

优点是实现简单、前缀可做范围查询；缺点是边界问题——两个相邻点可能前缀完全不同（跨格边界），必须查周围 8 个邻格。

Quadtree 四叉树

把二维平面递归四等分，密度高的区域自动细分得更深。适合分布极不均匀的场景（城市密、郊县疏），但树结构维护成本高，动态更新需要加锁。

Google S2

把球面投影到立方体再映射为 Hilbert 曲线的整数单元，无边界突变问题，且单元层级天然支持半径覆盖。工程上最稳健，但实现复杂。

三种方案对比

半径覆盖的做法

以查询半径换算所需的索引层级，取出该点及其邻格的所有候选，再做精确距离过滤。Geohash 需查 3×3 或 5×5 邻域，S2 则用 Region Covering 算法生成覆盖单元。

6. 位置更新与写入放大

写入放大的来源

用户每次上报都要更新索引：从旧格删除、往新格插入。若每次都同步更新，写放大是上报量的 2 到 3 倍。

优化手段

1. 合并写：短时间内多次上报只取最后一次（客户端节流 + 服务端去抖）
2. 惰性更新：只在跨格时才更新索引，格内移动只更新坐标
3. 批量写：同一用户的更新合并成一个批操作
4. 内存优先：热数据全内存，历史异步落盘

跨格判定

def update_location(user_id, lat, lng):
    new_cell = geohash_encode(lat, lng, precision=6)
    old_cell = get_old_cell(user_id)
    if old_cell != new_cell:              # 只有跨格才动索引
        zrem(f"cell:{old_cell}", user_id)
        zadd(f"cell:{new_cell}", {user_id: score})
        set_old_cell(user_id, new_cell)
    hset("location_online", user_id, pack(lat, lng, now_ms()))

热点格处理

热门商圈单格用户数可能上万。做法：格子超过阈值后按用户 ID 再哈希成子格，或对该格建立二级索引。

7. 在线状态与心跳

心跳机制

• 客户端每 30 秒上报一次（既更新位置也续活）
• 服务端为每个用户在 Redis 写带 TTL 的键，TTL 设为 2 到 3 倍上报间隔
• 键过期即视为离线，查询时自动排除

状态判定

秒级在线的挑战

5000 万用户 30 秒心跳 = 167 万 QPS 心跳，Redis 单集群需分片。可用「位图 + 时间槽」压缩存储：把每个用户每分钟的在线状态存为 bitmap，大幅降低内存。

8. 查询与排序

查询流程

1. 根据坐标与半径确定索引格集合
2. 从各格取出候选用户（可能上千）
3. 精确计算球面距离，剔除半径外
4. 应用过滤条件（性别、年龄、在线）
5. 排序并截断返回 Top N

距离计算

import math

def haversine(lat1, lng1, lat2, lng2):
    R = 6371.0  # 地球半径 km
    dlat = math.radians(lat2 - lat1)
    dlng = math.radians(lng2 - lng1)
    a = (math.sin(dlat / 2) ** 2
         + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2))
         * math.sin(dlng / 2) ** 2)
    return 2 * R * math.asin(math.sqrt(a))

排序策略

• 纯距离：简单但结果单调
• 距离 + 活跃度：加权综合，避免返回一堆僵尸号
• 个性化：结合画像做粗排 + 精排，排序思路可参考 推荐系统设计

候选集裁剪

候选过多时先按索引格距离分层，近格优先；再按活跃度预筛，减少精确计算量。

9. 隐私与精度控制

位置模糊化

• 网格对齐：把坐标对齐到固定网格中心，抹掉精确位置
• 随机偏移：在半径内加噪声，防止反推真实坐标
• 分级精度：不同业务返回不同精度（社交百米级、打车米级）

访问控制

• 隐身模式：不进入任何索引，查询侧无感知
• 黑名单：查询结果中过滤掉互相拉黑的用户
• 频次限制：防止被恶意爬取附近用户列表

合规要点

• 位置属敏感个人信息，需明确授权与用途
• 存储加密、访问审计、可删除（用户注销即清除）
• 跨境业务注意数据出境合规

10. 面试常见问题

Q: 为什么不用数据库的经纬度索引？
关系库的空间索引（如 R-Tree）在百万级尚可，但千万级高频写会写爆 B+ 树。LBS 的主流方案是内存索引 + 地理分片。

Q: Geohash 的边界问题怎么解决？
查询时同时覆盖目标格周围的 8 个邻格，把候选集合并后再精确过滤。这会把候选量放大数倍，因此格子大小要与半径匹配。

Q: 如何做到「附近的人」不返回离线用户？
在线状态用带 TTL 的心跳键维护，查询时先按在线集合过滤。离线用户的心跳键过期自动消失，无需额外清理。

Q: 热点城市怎么办？
索引格按密度动态拆分，热点格再哈希成子格；查询与写入都按格路由到不同分片，避免单分片过热。

Q: 位置数据要存多久？
在线位置只存最新（秒级时效），历史轨迹按合规要求保留有限天数后归档或删除。存储量与合规需求共同决定保留策略。

Q: 怎么防止用户伪造位置？
结合 IP 定位、WiFi 指纹、移动轨迹连续性做异常检测，突变坐标可标记可疑或降权。

总结

LBS 服务的答题主线是索引选型 + 写入优化 + 状态管理：用 Geohash/S2 做空间粗筛，用「只存最新 + 跨格才更新」对抗写入放大，用 TTL 心跳维护在线状态。查询侧再叠加距离计算与个性化排序，最后补上隐私模糊化与合规边界。把写入 QPS 的数量级算清楚，并解释清楚跨格与热点两个坑，这道题就很完整了。