系统设计 24：空间网格的边界与位置新鲜度

在坐标 (1.00, 0.50) 搜索 50 米内的人：两位好友分别位于网格边界左右各 10 米。如果只查请求所在的网格，就会漏掉其中一位；如果不检查位置更新时间，昨天路过的人仍会显示“附近”。商家搜索和附近好友都需要空间候选集，但好友查询还要处理权限与位置时效，不能仅换个表名复用餐馆检索。

本篇用固定二维公里坐标讲解候选筛选，再把真实地理距离、权限变化和动态更新明确列为未验证边界。所有流量与延迟是教学假设。

哪些结果可以出现

商家侧需要按半径查营业且公开的商家；好友侧必须先有双方有效可见关系，才可返回对方的近似位置。读请求不变量：结果必须在请求半径内、查询时尚未过期、用户具备查看权限；空间索引只生成候选，不能替代最后的距离、ACL 和时间过滤。写请求不变量：同一主体只接受版本更高的位置，旧事件不能覆盖新坐标。删除/隐藏位置后，新请求必须在约定传播窗口内停止返回；缓存失效前不能承诺强撤销。

教学 SLO 设为商家查询 p99 不超过 200 ms，好友位置从客户端提交到可查询 p95 不超过 10 s，撤销权限后新请求 5 s 内不再返回。这里未做负载、网络或缓存试验，三个数字都不是实测达标结果。排除实时导航、轨迹回放、反作弊、跨国测地精度保证与“100% GPS 准确”。好友在隐身模式直接拒绝列入候选，即使空间索引中的旧坐标尚存；产品层还需限制频繁查询造成的定位推断。

外部接口 PUT /locations/me {x, y, observed_at, version, visible} 返回接受版本；GET /nearby?x=&y=&radius_m=&kind= 返回匿名 ID、粗粒度距离及位置时间，不返回好友的原始坐标。商家可另有 GET /places/{id} 读取开放资料。权威记录 locations(subject_id PK, x, y, version, expires_at, visibility)；place(id, x, y, open_state)；邻接权限 friend_visibility(viewer_id, subject_id, allowed)。网格倒排键 (cell_x, cell_y, subject_id) 只是从权威位置派生的投影，更新位置时要删除旧格并放入新格，不能只追加。请求方坐标也需要鉴权，半径有上限。

容量：更新通常比地图查询先吃资源

假设 100 万活跃好友每 30 s 上报一次，更新率为 1,000,000 人 / 30 s = 33,333 次/s；一次上报 100 B 有效负载约 3.33 MB/s，峰值系数 3 则约 100,000 次/s 与 10 MB/s，不含索引维护和 TLS。每人当前状态按 96 B 估计，100 万条为 96 MB 逻辑量，三副本 288 MB；如果每次更新都留 64 B 历史记录并保留一天，33,333 次/s × 86,400 s × 64 B ≈ 184.3 GB/天，三副本约 553 GB/天（索引、日志另计）。只保留最新位置与保留轨迹是两种完全不同的成本承诺。

另假设每天 200 万次附近查询，均值 2,000,000 / 86,400 ≈ 23.15 query/s，峰值十倍约 231.5 query/s。固定坐标实验有 1103 个点：边界查询看 167 个候选；密集区域半径 50 m 的查询同样看 167 个候选，返回 101 个点。如果一半用户把上报间隔缩短到 5 s，其每秒上报量从约 16,667 升至 100,000 次，总体从 33,333 升至约 116,667 次/s；瓶颈先落在写入/旧格清理，而不是半径查询。热点并不能靠多加几个空网格消失。

网格负责不漏，距离负责精确

实验使用米为单位、边长 500 m 的网格，把 (x,y) 映射为 (floor(x/500),floor(y/500))。半径查询枚举与包围盒相交的网格，再算欧氏距离。在 (999.99,0) 的 1 m 查询中，(1000.01,0) 跨过格子边界，仍应命中。仅取中心格的反例会漏掉该点；粗筛允许假阳性，随后用精确距离排除。

flowchart LR
    U[商家或好友更新] --> V[鉴权 版本 时间]
    V --> L[(权威最新位置)]
    L --> G[(网格单元到主体 ID)]
    R[查询 半径 权限] --> C[取相交单元的候选]
    G --> C
    C --> F[距离 过期 权限再过滤]
    L --> F
    F --> O[粗粒度附近结果]

二维平面只是合成场景。经纬度跨日期变更线、纬度不同的经度尺度及球面距离不能直接套这一公式。PostGIS ST_DWithin文档区分 geometry 的坐标单位和 geography 的米单位，也描述空间索引友好的先筛候选；这里引用的是工程候选方案，本次没有启动 PostGIS 或测其性能。商家规模不大时单库范围索引加距离全量过滤更便宜；热点密度高或查询半径跨很多网格时，调整单元大小并不能保证降本，考虑分层网格或为热点区域设查询预算。好友 ACL 不适合只放在全局公共缓存；缓存键至少含可见性版本，撤销应优先走权威校验。返回匿名点并不保证隐私，连续查询仍可能反推位置。

更新乱序时的失败路径

sequenceDiagram
    participant P as 手机
    participant W as 位置写服务
    participant G as 网格投影
    participant Q as 附近查询
    P->>W: 版本 8 新坐标 B
    W->>G: 移除 A 放入 B
    P->>W: 延迟到达的版本 7 坐标 A
    W-->>P: 拒绝旧版本
    Q->>G: 获取 B 附近候选
    G-->>Q: 主体 ID
    Q->>W: 校验最新版本 TTL 与权限
    W-->>Q: 若已过期或隐藏则不返回

要给“撤销后五秒不再出现”做端到端承诺，不能只异步更新网格：需要查询时核对权威权限，或确保失效消息有可监测的传播上限；存储故障且无法校验权限时好友查询应拒绝返回，而非放行旧缓存。若只是公开商家，可短暂返回陈旧开放状态并标记刷新；这与好友位置的失败策略不同。恢复时用权威记录的最新版本重建网格，并抽样全量扫描对比候选，检查跨格迁移与孤儿索引；恢复期间限制读取范围或回退有界全量查询。

运行 python3 -B examples/system-design/labs/24/nearby.py，版本、种子和原始输出见 examples/system-design/evidence/24/RUN.md。随机种子 2401 生成 1000 个普通点，另有 100 个密集点和边界、过期、隐藏各一点，共 1103 点。四次查询的候选数为 167、66、166、167，命中数为 77、20、60、101，均与逐点全量扫描完全相同；过期和隐藏点被过滤，单格反例漏边界。这只测固定平面坐标的正确性和候选数量，不测延迟、球面距离、迁格并发或乱序更新。

[PATTERN] “宽进严出”的检索：用便宜且不漏的粗筛产生超集，再用权威版本与权限做精筛。空间网格、倒排检索与预过滤都适用；当候选集接近全集时，应量化实际节省，不能把“建了索引”当成效果。

追问与速查

如果半径从 100 米放大到 100 公里，候选数和查询上界怎么变？如果手机断网一小时才上报旧位置，按设备时间还是服务端版本裁决？如果双方互相关注但只有一方开启可见，查询该怎样拒绝？回答需要分别落在网格枚举、版本授权与查询时权限过滤，不应只说“加缓存”。

问题	模式	反例/代价
格子边界漏人	相交单元粗筛后距离精筛	查询单元变多
显示旧或隐藏好友	权威版本、TTL、权限复核	读放大或拒绝服务
高密区慢	测候选数再调粒度	格子越小未必更快