ozine's book library

主题

系统设计经典题目：十二种系统，十二组必须守住的约束 ​

短链、秒杀、Feed 和支付系统都可以画成“入口、服务、数据库、缓存、队列”。图相似，不代表难点相同。短链不能因碰撞覆盖旧映射；秒杀不能多卖；聊天要让重连用户找回消息；支付超时后不能擅自认定失败。设计能不能成立，取决于这些约束在并发、重试和故障时是否仍成立。

下面逐题给出需求边界、最小数据与接口、关键路径、失败恢复和选择理由。它们是教学方案，不是某家公司的完整生产架构。文末有十二个有界本地模型和反例测试，帮助观察关键行为；除秒杀模型外，这些状态机按单线程调用，不声称提供通用并发安全。全部模型都只用内存，不模拟真实数据库、消息集群或支付渠道。

1. 短链系统：先保证映射不会被覆盖 ​

先确认短链是否允许修改目标、设置过期、自定义别名，以及点击统计是否影响跳转。这里选择：公开访问、创建要鉴权；别名唯一；支持停用与过期；跳转优先，统计允许异步。公开短链容易被扫描和滥用，不能把“难猜”当作访问控制。

最小数据是 links(code 主键、target、owner、status、expires_at、version)，以及创建幂等记录。POST /links 接受 URL、可选别名和幂等键；GET /{code} 查询映射并重定向；PATCH /links/{code} 只允许所有者修改。URL 先限制协议与长度；如果后台要预览网页，另做 SSRF 防护，不能拿任意 target 直接访问内网。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    C["创建请求"] --> W["校验目标、生成候选码"]
    W -->|"唯一键插入；冲突换码"| D[("权威映射")]
    U["访问短码"] --> R["跳转服务"]
    R --> H["缓存"]
    H -->|"未命中"| D
    R -->|"校验状态与有效期后 3xx"| U
    R -.->|"有界异步点击事件"| A["统计"]
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    C["创建请求"] --> W["校验目标、生成候选码"]
    W -->|"唯一键插入；冲突换码"| D[("权威映射")]
    U["访问短码"] --> R["跳转服务"]
    R --> H["缓存"]
    H -->|"未命中"| D
    R -->|"校验状态与有效期后 3xx"| U
    R -.->|"有界异步点击事件"| A["统计"]

生成码有三种常见选择。自增 ID 转 Base62 简单、无随机碰撞，但容易枚举并暴露大致数量；随机码分散，必须在唯一约束失败后重试；URL 哈希可以稳定生成，但截断后仍有碰撞，而且“相同 URL”是否应该共享链接，涉及所有者、过期与统计语义。长度 L 的 Base62 空间是 62^L；随机选 n 次的碰撞概率近似 n(n−1)/(2×62^L)，这个近似只在概率较小时有用，不能替代唯一约束。

模型把候选码固定为 a、b，a 已占用：

go
links := map[string]string{"a": "old"}
code, err := allocate(links, "new", []string{"a", "b"})
text
shortlink code=b old=old err=<nil>

换码保住了旧映射。生产实现必须把“只有不存在才插入”交给存储的原子约束，不能把模型中的 map 查写直接放到多实例服务。关系数据库的唯一约束可查 PostgreSQL 18 Constraints。

热点短码会集中压垮一个缓存键或分片，可用边缘缓存、进程内短 TTL 缓存和回源合并；不存在的短码也可做短期负缓存，容量必须有上限，防止随机扫描撑满缓存。修改或封禁链接时，长缓存会延迟生效，需要版本化失效或较短缓存期限。

选择优点限制与恢复要求
永久重定向稳定映射可减少后续请求客户端可能长时间记住目标，不适合随时改址或撤销
临时重定向并明确缓存控制更容易控制更新窗口回源更多；“临时”不等于绝不缓存
同步记录每次点击统计较完整统计故障会拖慢跳转
异步统计跳转路径短需要选择丢失、重复和延迟的容忍度

具体状态码语义和缓存规则应分别核对 RFC 9110 与 RFC 9111。缓存丢失后从权威库恢复；权威库不可用时，是否继续使用未过期旧缓存，必须与停用及时性一起决定。

2. 秒杀／抢购：入口挡流量，库存事务守住不超卖 ​

这里假设每用户限购一件、库存固定、成功下单后保留一段支付时间。需要分别定义“抢到资格”“生成订单”“支付成功”，否则返回一个 200 就容易让用户误以为一定买到了。

最小数据为 inventory(sku、available、version)、reservation(id、user、sku、quantity、state、expires_at)、orders(id、reservation_id、state)，并对业务限购键做唯一约束。POST /reservations 带请求键；GET /reservations/{id} 查询结果。重复请求返回同一预留结果，不能重复扣库存。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
stateDiagram-v2
    [*] --> Reserved: 原子扣减可售量并创建预留
    Reserved --> Confirmed: 核验支付成功并转换状态
    Reserved --> Released: 到期或取消且条件更新成功
    Confirmed --> [*]
    Released --> [*]
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
stateDiagram-v2
    [*] --> Reserved: 原子扣减可售量并创建预留
    Reserved --> Confirmed: 核验支付成功并转换状态
    Reserved --> Released: 到期或取消且条件更新成功
    Confirmed --> [*]
    Released --> [*]

关键不变量是 available 不小于零，且可售、已预留、已售出的数量能与初始库存及显式补货对应。数据库方案是在同一事务里执行带 available≥quantity 条件的扣减、创建预留和幂等结果。单行更新条件与并发行为要按目标数据库隔离级别验证，不能笼统地说“用了事务就不会超卖”。PostgreSQL 的并发更新说明可作为一个具体实现依据。

模型用锁把检查和扣减合在一起：

go
if ok, exists := s.Orders[key]; exists { return ok }
ok := s.Stock > 0
if ok { s.Stock-- }
s.Orders[key] = ok
text
sale first=true replay=true other=false stock=0

故意错误的测试不需要制造 data race：先让 A、B 都读到库存 1，再分别写回 0，最终库存仍是 0，却接受了两单。

text
broken schedule: stock=0 accepted=2

因此 race 测试通过不证明业务不超卖。正常模型另跑 100 个并发请求抢 3 件库存，只接受 3 个。

入口应按活动、用户、设备风险和下游容量做有界准入；排队返回排队编号或明确拒绝，队列容量与可接受等待时间匹配。Redis 原子脚本可将检查与预扣放在同一执行边界，但 Redis 成功与数据库落单仍是两处状态，必须定义持久化、故障切换、补偿和对账。脚本执行期间会阻塞其他命令处理，因此脚本应短小有界，见 Redis Lua 执行文档。

支付确认和到期释放会竞速。两者都必须从 Reserved 做条件状态转换，只有一个成功；重复释放不能反复加库存。支付渠道已经成功而本地预留释放后的异常，需要退款或人工处理的业务流程，不能用“重新扣一下”掩盖。

路径适用条件主要代价
数据库直接预留可承载的峰值、正确性优先热 SKU 行锁竞争，需要入口限流
预分库存额度到分区单热点写入已成为瓶颈局部额度闲置、调拨与恢复更复杂
先排队再事务落单可接受等待，峰值远大于库存排队状态、超时取消和积压管理

3. Feed 流：把合并工作放在写时还是读时 ​

先选时间序还是推荐排序。这里做按时间倒序的关注流，要求新内容在可接受延迟内出现，分页不重复展示同一帖子，并在读取时检查最新权限与删除状态。推荐模型与广告混排是另一个系统，不能用一个“排序服务”盒子假装完成。

数据至少有 posts(post_id、author、created_at、visibility、version)、follows(follower、followee)、inbox(user、post_id、排序键)。POST /posts 发布；GET /feed?cursor=... 读取。游标包含稳定排序键，通常需要时间加唯一 ID；若排序会动态变化，还要设计会话快照或接受翻页漂移。

模式发布时做什么读取时做什么适合与代价
推模式把 post_id 写进粉丝收件列表读收件列表并取内容读快；写放大与冷用户存储高
拉模式只写作者列表取关注作者的近期列表并合并发布便宜；关注多时读扇出大
混合普通作者推，高粉作者保留待拉合并预计算列表与高粉作者列表平衡成本；需要去重与切换规则

假设作者发一篇文章，有 F 个粉丝，推模式产生约 F 次列表写入；拉模式成本大致转移到这些用户实际打开 Feed 的时候。阈值应结合发帖频率、活跃粉丝比例、读取频率和延迟目标决定，不能规定“超过某固定粉丝数必用拉”。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    P["发帖提交"] --> E["事件日志"]
    E --> F["普通作者：分批 fanout"]
    F --> I[("用户 inbox：存 post_id")]
    P --> A[("作者时间线")]
    R["读 Feed"] --> I
    R -->|"高粉作者候选"| A
    I --> M["按稳定键合并、去重、权限过滤"]
    A --> M
    M --> O["有界一页结果"]
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    P["发帖提交"] --> E["事件日志"]
    E --> F["普通作者：分批 fanout"]
    F --> I[("用户 inbox：存 post_id")]
    P --> A[("作者时间线")]
    R["读 Feed"] --> I
    R -->|"高粉作者候选"| A
    I --> M["按稳定键合并、去重、权限过滤"]
    A --> M
    M --> O["有界一页结果"]

扇出任务要带 post_id 和批次游标，崩溃后从进度继续；inbox 唯一键 (user_id, post_id) 避免重投重复。模型用唯一整数代替真实排序键，合并推列表 [7,4] 和拉列表 [9,7]：

go
feed([]int{7, 4}, []int{9, 7}, 10, 3)
text
feed=[9 7 4]

它只证明候选合并去重，不证明跨页快照或权限正确。生产读取要在返回前处理拉黑、取消关注、删帖和可见性变更，不能认为“曾推到 inbox”就是永久授权。TAO 原始论文讨论了社交图查询与读取时隐私检查，但不应把它直接当作本文混合 Feed 的完整实现，见 TAO §2。

热点作者的发布会形成扇出洪峰，按粉丝分片、批量写、只预计算活跃用户可减压；代价是新登录冷用户需要补建。重建时从帖子与关注关系恢复候选，再应用当前权限。关注关系在发帖时还是读取时生效，需要产品明确，历史回填会因此不同。

4. IM 即时通讯：连接在线，不代表消息已可靠送达 ​

这里做单聊和有上限的小群，要求同一会话内有稳定顺序、断线能补消息、多设备同步；不承诺所有会话之间的全局顺序。“服务端已接收”“设备已收到”“用户已读”是三种状态，应分别记录。

最小数据包括 conversations、members、messages(conversation_id、seq、message_id、sender、client_msg_id、body)、device_cursor。发送接口可以是 WebSocket 消息帧中的 Send，也可另设 POST /messages；补拉接口按 conversation_id 和 after_seq 分页。服务端先检查成员权限，再用 (会话、发送者、client_msg_id) 去重，同键不同内容应拒绝。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
sequenceDiagram
    participant C as 发送设备
    participant G as 连接网关
    participant S as 会话存储
    participant R as 接收设备
    C->>G: client_msg_id + 内容
    G->>S: 校验成员、分配会话序号、持久化
    S-->>G: seq=42 已提交
    G-->>C: 服务端接收 ACK
    G->>R: 推送 seq=42
    R-->>G: 设备收到 ACK
    R->>G: 重连后请求 after_seq=41
    G->>S: 拉取缺口
    S-->>R: 包含 seq=42 的持久消息
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
sequenceDiagram
    participant C as 发送设备
    participant G as 连接网关
    participant S as 会话存储
    participant R as 接收设备
    C->>G: client_msg_id + 内容
    G->>S: 校验成员、分配会话序号、持久化
    S-->>G: seq=42 已提交
    G-->>C: 服务端接收 ACK
    G->>R: 推送 seq=42
    R-->>G: 设备收到 ACK
    R->>G: 重连后请求 after_seq=41
    G->>S: 拉取缺口
    S-->>R: 包含 seq=42 的持久消息

WebSocket RFC 6455提供双向连接和帧协议，不替应用定义消息持久化、跨重连去重和已读语义。TCP 当前连接里的有序传输也不能消除两次不同连接上的业务重试。

模型同一个客户端消息发送两遍：

go
m1, _ := chat.Send("client-1", "hi")
m2, _ := chat.Send("client-1", "hi")
text
chat seq=1 replay=1 missed=1

第二次复用序号，离线游标 0 仍只补一条。模型以 slice 长度分配 seq，仅适用于这个单线程单会话模型；生产可按会话分区由单个顺序所有者处理，或用数据库序列化分配。序号通常只需单调，不必无缺口；若删除留空号，补拉协议不能无限等待“缺失序号”。

失败或压力处理方式代价
持久化后发送方没收到 ACK相同 client_msg_id 重试需要保留去重记录或唯一约束
网关重启、设备离线持久消息加游标补拉网关内存不是唯一消息存储
慢设备读不动有界发送缓冲，断开后补拉在线推送可能中断，但不无限占内存
大群扇出分批推送或读时拉取单聊方案不能无条件扩成万人群
多设备已读按用户或设备定义游标，再单调推进不能把一个设备收到当作用户已读

消息保留期、附件存储、端到端加密和删除合规要另定边界。端到端加密会改变服务端搜索、审核和多设备密钥同步方式，不能只在图上补一把锁。

5. 限流器：限制哪种资源，决定算法与故障策略 ​

先问限的是每用户操作数、每租户花费、每 IP 请求数，还是下游并发。每秒 100 次请求并不一定保护住内存：若请求持续 30 秒，在途量仍可能很大。因此速率限制与并发限制常常需要一起用。

最小接口是 Allow(key, cost)，返回允许与否、剩余额度或建议等待时间；HTTP 拒绝可使用 429，并按协议选择 Retry-After，见 RFC 6585 §4。key 必须有明确身份来源，不能信任客户端随便填的用户号。

算法保存的状态行为主要限制
固定窗口窗口计数每窗口最多 N 次窗口边界两侧可短时接近 2N
滑动日志每次请求时间精确限制任意滑动窗口状态量随请求数增长
滑动窗口计数相邻窗口计数与权重低成本近似平滑近似误差需接受
令牌桶剩余令牌、上次补充时间长期速率 r，最多突发 b时间与原子更新必须正确
漏桶／有界队列排队任务、出队时刻输出趋于平滑增加等待；队列满时仍要拒绝

令牌桶每次先补充 min(容量, 原令牌 + elapsed×速率)，令牌够才扣。模型容量 2、每秒补 1 个，输入时间由测试直接传入：

go
bucket := &Bucket{Tokens: 2, Capacity: 2, Rate: 1}
text
limit=true true false true

前三次都在 0 ms，第四次在 1000 ms。测试还验证时间倒退时拒绝计算，避免负时间错误扣减。单进程可以用单调时钟；跨机器的全局限流需要共享权威时间或设计可接受的误差，不能假设各节点时钟完全一致。

最小部署是入口中间件调用限流服务，限流服务按 key 路由到状态分片，再原子更新 (tokens, last_refill)；服务端验证身份，业务 handler 只在准入后执行。单实例小系统可以把同一状态放在进程内并用锁保护，但扩为多实例后额度范围就变了。

分布式令牌桶的读、补、扣必须原子完成。Redis 脚本是一种选项；多分片 key 的操作边界仍需另看。将额度预分给多个实例可减少中心调用，但实例故障可能暂时浪费额度，租约过期和重新发额度若重叠又会超发。每台独立限 100 次不等于全局限 100 次。

故障时放行能保护可用性，却可能压垮下游；故障时拒绝能保护稀缺资源，却会误伤正常用户。支付防重复、昂贵导出和普通页面读取应有不同策略。维护 key 的 TTL 和最大数量，限制恶意构造的高基数键；把拒绝率、限流原因和实际下游负载一起观测，避免“限流生效但资源仍满”。

6. 分布式 ID：唯一、排序和不可猜不是同一个要求 ​

需求应逐项确认：是否全局唯一、是否大致按时间排序、是否要离线生成、字段长度、是否暴露给外部。订单号可猜与否是安全边界的一部分；任何 ID 都不代替授权检查。

方案生成与数据好处风险和代价
数据库序列中心顺序分配简单、容易管理中心依赖；缓存与回滚可能留下空号
号段分配中心记录下一个区间，节点本地用降低中心访问频率节点重启会浪费剩余段；不能重用已发区间
UUIDv4随机生成不依赖中心时间顺序概率唯一；随机写入局部性需评估
UUIDv7时间戳加随机／单调相关字段更利于按生成时间聚集不是跨节点严格全序，仍需处理时钟与随机性
Snowflake 类时间差、节点号、序列号定长整数、本地产生节点号唯一、时钟回退、序列耗尽都要管

UUID 的位布局与生成要求见 RFC 9562。Snowflake 的原始实现可查 归档 IdWorker。本文模型选 41 位毫秒时间差、10 位 worker、12 位序列作为教学布局，并不声称逐行复刻原始版本。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    T["相对 epoch 的毫秒数"] --> C["检查回退与时间范围"]
    W["独占 worker_id"] --> C
    C --> S["同毫秒序列加一；耗尽拒绝或等待"]
    S --> I["time 左移 22 位 OR worker 左移 12 位 OR seq"]
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    T["相对 epoch 的毫秒数"] --> C["检查回退与时间范围"]
    W["独占 worker_id"] --> C
    C --> S["同毫秒序列加一；耗尽拒绝或等待"]
    S --> I["time 左移 22 位 OR worker 左移 12 位 OR seq"]

模型同一毫秒调用两次，序列不同；随后时间回退：

go
gen := &IDGen{Worker: 3}
id1, _ := gen.Next(100)
id2, _ := gen.Next(100)
_, err := gen.Next(99)
text
ids distinct=true rollback=clock moved backward

测试在同一毫秒发完 4096 个后，第 4097 个明确失败，到下一毫秒恢复。生产可以短时间等待真实时钟前进，或采用明确的逻辑时间策略，但不能静默把序列绕回零。

即使进程里用了锁，两个节点拿到同一 worker_id 仍会重复。租约分配要避免旧节点在失联后继续发号；重启时重用节点号，也要处理上一次已使用的最高时间戳。时钟位决定使用寿命，41 位毫秒约为 69.7 年，epoch 到期需迁移方案。大整数送到 JavaScript 客户端时通常用字符串避免精度丢失。恢复策略是停止不安全发号并报警，不能为了“高可用”牺牲唯一性。

7. 延迟任务调度：到点、领走、执行成功是三个状态 ​

先定义精度：允许晚 100 ms，还是允许晚一分钟？到点后是至少执行一次，还是宁可漏掉也不要重复？这里选择“到期后尝试执行，允许重复投递，业务副作用必须幂等”，并允许重试、取消和死信人工处理。

数据为 jobs(id、due_at、payload、state、attempt、lease_until、lease_epoch)，另存业务幂等结果。POST /jobs 带幂等键创建；DELETE /jobs/{id} 通过条件状态转换取消；GET 查询状态。取消成功只应承诺尚未执行部分的语义，不能假装撤回已发生的外部副作用。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
stateDiagram-v2
    [*] --> Scheduled
    Scheduled --> Leased: 到期且原子领取
    Leased --> Succeeded: 当前租约确认
    Leased --> Scheduled: 租约超时后重领
    Leased --> RetryWait: 可重试错误
    RetryWait --> Leased: 到重试时间
    Leased --> DeadLetter: 达重试上限或不可恢复错误
    Scheduled --> Cancelled: 条件取消
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
stateDiagram-v2
    [*] --> Scheduled
    Scheduled --> Leased: 到期且原子领取
    Leased --> Succeeded: 当前租约确认
    Leased --> Scheduled: 租约超时后重领
    Leased --> RetryWait: 可重试错误
    RetryWait --> Leased: 到重试时间
    Leased --> DeadLetter: 达重试上限或不可恢复错误
    Scheduled --> Cancelled: 条件取消

小规模可用带 due_at 索引的数据库周期扫描；内存最小堆便于找最近到期项，但重启必须从持久存储重建。时间轮适合大量定时器和固定精度；有序集合便于按分数查到期任务，但“查询到期”和“标记领取”仍需原子协调。分布式周期调度的故障语义见 Google SRE Cron 章节。

模型用递增 epoch 表示每次领取代次：

go
e1, _ := job.Claim(10, 5)
e2, _ := job.Claim(15, 5)
old, current := job.Ack(e1), job.Ack(e2)
text
job old_ack=false current_ack=true

第一个 worker 的租约到期，第二个重新领取；旧确认不能覆盖新状态。这仍没有阻止旧 worker 向外部系统发请求。若副作用支持 fencing token，应让下游拒绝过时代次；否则使用业务幂等键、结果查询和补偿。只给调度表加租约，不能得到“恰好执行一次”。

多个任务同一时刻到期会突发，按分区和优先级限量领取，用有界 worker 池；重试采用退避、抖动和最大尝试期限，不无限重试。监控应包括最老到期任务的延迟和执行耗时，而不仅是队列长度。恢复时扫描过期租约与未完成任务，明确运行中任务的结果可能未知，再决定查结果还是重投。

8. 排行榜：先定义同分怎么排，再考虑 Top K ​

需求包括实时还是定期刷新、全局榜还是分组榜、只读前 100 名还是查询自己的名次、是否有赛季重置和反作弊。这里用每赛季用户积分榜，同分按用户 ID 升序，明确这是“顺序名次”；若产品要 1、2、2、4 或 1、2、2、3，需要另外定义竞争排名或密集排名。

数据至少有 score_events(event_id、season、user、delta) 和 scores(season、user、score、version)。POST /score-events 只接受可信业务事件；GET /leaderboard?season=...&limit=...；GET /rank/{user} 查询个人。不能让客户端直接提交一个想要的最终分数。

结构适用读取主要代价
数据库分组／排序小中规模、复杂筛选大量实时排序和深分页会贵
Redis sorted set有序取区间、改分数、查排名热榜写入集中；持久与恢复需要权威来源
分片本地 Top K 再归并全局 Top K查询任意用户精确名次较难
定期批量快照可接受刷新间隔展示滞后，实时资格判定不能直接使用旧榜

Redis sorted set按 score 排序，同分按成员字节序处理；反向读取也会影响同分方向，不能默认恰好符合产品规则。模型使用显式比较器，先高分、再 ID 升序：

text
ranking=[{b 100} {a 90} {z 90}]

这是输入 z=90、b=100、a=90 的实测结果，不是 Redis 输出。单纯把“分数×系数+时间”塞进浮点 score，可能超过精确整数表示范围或混淆排序规则；应证明取值范围，必要时保留单独排序字段。

最小架构是可信积分事件写入权威日志，再由按用户分区的消费者更新榜单投影，查询服务读取指定赛季榜单；前几页可缓存，日志作为恢复来源。

并发增分需要原子累加，重复事件需要在同一个业务边界去重。消费者崩溃后重放原始积分事件，得到同样最终分数；删除作弊积分应追加修正事件并保留审计来源，而不是直接改缓存且丢失原因。热门榜可缓存前几页，实时分数与展示榜允许滞后时要标更新时间。

分片 Top K 的一个有用边界是：若每个用户只在一片，排序规则完全相同且分片视图在同一逻辑时刻，那么各片取本地 Top K 的并集足以求全局 Top K。实际异步读取不自动满足同一时刻，因此跨片严格实时排名仍需协调或快照协议。

9. 计数系统：浏览量、去重人数和余额不能共用一种计数器 ​

先说明算什么。PV 是事件次数，UV 是一段时间内不同主体数；点赞数是当前有效关系数；账务余额还涉及货币、审计和合法状态。本文讨论浏览／点赞类业务统计，不把一个可丢失的内存计数器用于资金决策。

最小数据为 events(event_id、object、actor、time、kind)、计数投影和去重状态。POST /events 带稳定事件 ID；GET /counts/{object} 返回数值、统计窗口和更新时间。点赞／取消点赞若表达的是当前状态，用 (对象, 用户) 的关系和版本通常比盲目 +1、−1 更容易处理乱序。

需求可选方案它没有自动解决的事
单节点原子递增数据库条件更新、Redis INCR网络超时后的重试去重、跨故障丢失
热点分摊按事件或主体分到多个计数桶，读取求和精确瞬时总数需要一致的读取边界
多副本单调累加G-counter 每副本分量，合并取 max减少计数、重复业务事件、无限副本元数据
近似不同人数HyperLogLog精确成员列表与精确删除
必须精确且可审计唯一业务事实加事务更新，或可回放日志成本、延迟与保留要求更高

INCR 官方文档说明命令行为；命令原子不表示“超时重试只算一次”。模型给同一个 e1 加两遍，只计一次；另一个模型把副本 a=2 与旧 a=1、b=3 按分量最大值合并：

text
counter dedup=1 merged=5

G-counter 的关键是每个副本只能增加自己的单调分量，合并用 max，重复和乱序传播不会把旧值加第二遍。如果两个节点共用同一副本身份并各自从旧值递增，仍可能丢更新。支持增减的 PN-counter 可分别维护增加和减少的 G-counter，再求差；它不自动保证结果非负。CRDT 的收敛条件参见 原作者资料。

Redis HyperLogLog 文档解释的是近似基数统计，不能拿来回答某个用户是否来过。是否接受误差，应按业务用途决定；用于趋势图和用于限额结算的要求不同。

最小异步架构是采集入口持久记录事件，按对象与分桶键分区的消费者执行去重和累加，查询层合并计数桶并返回更新时间；若要求写后立即精确读，应把相应读写留在明确的同步事务边界内。

热点对象可以分桶增量、批量刷写或异步聚合；每种方式都要说明故障时最多丢多少，以及重放如何防重复。去重记录过期后，旧事件重放可能再次累加，因此去重寿命要覆盖消息保留和允许重放窗口。恢复时从事件或关系表重算，抽样比对权威事实与投影差额。

10. 搜索提示：每敲一个字都查询，要控制候选和隐私 ​

搜索提示可能是“前缀补全”“拼写纠错”或“搜索结果预览”，这三种需求不同。这里做公开词库的前缀补全，返回最多 K 条，排序按热度并以词文本打破同分，不把个人历史或敏感查询放进公共候选。

数据包括词条、标准化形式、语言、权重、可见性和版本。GET /suggest?q=...&limit=... 限制输入长度与 K，按用户权限筛候选；日志应避免无期限保存敏感原始输入。前端防抖减少请求，并给每次查询编号，较晚返回的旧查询不能覆盖较新的输入结果。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    L["许可公开的词条与统计"] --> B["离线清洗、规范化、候选构建"]
    B --> V["不可变索引版本 V+1"]
    V --> S["校验后原子切换索引指针"]
    Q["用户前缀"] --> N["规范化、长度与速率限制"]
    N --> I["前缀查找与有界候选"]
    S --> I
    I --> F["权限过滤、稳定排序、Top K"]
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    L["许可公开的词条与统计"] --> B["离线清洗、规范化、候选构建"]
    B --> V["不可变索引版本 V+1"]
    V --> S["校验后原子切换索引指针"]
    Q["用户前缀"] --> N["规范化、长度与速率限制"]
    N --> I["前缀查找与有界候选"]
    S --> I
    I --> F["权限过滤、稳定排序、Top K"]

Trie 用字符边逐步定位前缀，再枚举子树；若子树巨大，只做前缀定位还不够，需要缓存节点 Top K 或有界搜索。FST 可以压缩共享路径，工程实现要权衡构建成本、内存和更新方式。数据库前缀索引适合较小词库；搜索引擎的 completion suggester 提供专门结构，具体配置见 Elasticsearch 8.19 Suggesters。

模型刻意用线性扫描作为排名正确性的参照，输入 Go 规范化为 go：

text
suggest=[go golang]

它没有声称实现 Trie，也没有做中文分词、拼音、Unicode 归一化或完整大小写折叠。生产标准化必须在构建索引与查询时一致，且与语言需求相符；不能简单删除字符导致两个不同词被错误合并。

问题可选处理代价与恢复
热前缀请求集中缓存公开候选，限制候选数量个性化或私有结果不能混用公共缓存
热度高频变化小增量层叠加周期快照查询要合并和去重
索引更新中断新版本完整构建后切换，保留上一版占双份空间，但可快速回退
删除敏感词必须立即生效返回前叠加禁用表，随后重建多一层检查，需定义传播上限

短暂失败可返回较旧但仍合规的候选，或者空列表；提示服务不应把主搜索和输入界面一起拖死。

11. 支付与对账：未知结果不能当失败，平衡分录不能当正确业务 ​

这里讨论的是一个商户如何组织支付状态与核对流程，全部示例都是虚构内存数据，没有真实扣款、转账或支付账号操作，也不是可上线的银行账务实现。真实设计还需要渠道契约、合规、财务与审计人员确认。

需求至少要确认支付方式、币种、授权与扣款是否分开、退款和拒付、支付最终状态、渠道幂等寿命与查询方式。最小数据有 payments(id、order_id、amount_minor、currency、state、provider_id)、payment_attempts、webhook_inbox、ledger_entries(transaction_id、account、currency、signed_amount) 和 reconciliation_runs。金额用明确币种的最小单位整数或合适的定点表达；不能用 float64 累加金额，也不能把所有币种一律当两位小数。

创建接口 POST /payments 带业务幂等键；GET /payments/{id} 用于查状态；渠道 webhook 是另一条输入路径，需要验签、去重，并在持久记录后异步处理。客户端跳转回成功页面不能成为唯一成功依据。Stripe 的状态核验文档是一个具体渠道例子，不等于所有渠道都使用相同状态名。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
stateDiagram-v2
    [*] --> Created
    Created --> Pending: 持久记录请求意图
    Pending --> Unknown: 超时或连接断开，结果不明
    Pending --> Succeeded: 核验渠道成功
    Pending --> Failed: 核验终止失败
    Unknown --> Succeeded: 查询、通知或对账确认成功
    Unknown --> Failed: 渠道确认终止失败
    Succeeded --> RefundPending: 明确发起退款流程
    RefundPending --> Refunded: 核验退款完成
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
stateDiagram-v2
    [*] --> Created
    Created --> Pending: 持久记录请求意图
    Pending --> Unknown: 超时或连接断开，结果不明
    Pending --> Succeeded: 核验渠道成功
    Pending --> Failed: 核验终止失败
    Unknown --> Succeeded: 查询、通知或对账确认成功
    Unknown --> Failed: 渠道确认终止失败
    Succeeded --> RefundPending: 明确发起退款流程
    RefundPending --> Refunded: 核验退款完成

服务端向渠道发出请求后超时，可能是请求没到，也可能是已扣款但响应丢失。此时写 Unknown，保留原业务键，优先按渠道契约重试同一请求或查询；更换键重新扣款可能制造第二笔交易。幂等键要绑定参数、保留时间与结果语义，见 Stripe 幂等请求及低层错误处理。渠道提供的语义、期限与可重试错误必须逐一核对。

webhook 可能重复或乱序，见 Stripe webhook 文档。事件 ID 去重防止重复处理，同一支付的状态转换还要遵守版本与合法迁移。收到旧的失败事件不能覆盖已确认成功；必要时查询渠道权威对象，不能只按事件到达时间决定最终状态。

模型预置 p1 状态 Unknown、金额 100 个虚构 USD 最小单位；把已核验的成功观察提交给本地 Reconcile 两次：

go
_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
text
payment state=succeeded entries=2 balance=0

模型写两条带符号分录，总和为零，并用 payment ID 避免重复入账。它只演示“结果从未知变明确后，再以原子、幂等方式登记”。没有实现真实会计科目、余额约束、手续费、多币种、跨支付的渠道交易号唯一约束、持久化与并发事务。分录和为零仅是必要的局部检查：给错用户记账也能平衡，所以金额、币种、订单、商户和渠道交易号都需要核对。

对账差异先核对的证据处理方向
渠道成功，本地未知渠道交易号、业务键、金额、币种、商户幂等补记状态与分录
本地成功，渠道没有匹配记录查询口径、时间窗口、渠道最终状态建异常单，不自动再扣款或抹账
金额、币种或手续费不一致原订单、渠道明细与结算口径分别定位业务、计费或汇兑差异
重复支付、退款、拒付原交易关联与后续事件链用独立冲正／退款分录修正并留审计

对账不只是比较两边总额。总额相同仍可能一笔多记、一笔漏记；需要逐笔匹配、汇总检查、差异状态、重跑去重和明确的人工处理入口。支付成功、渠道余额变化与银行结算到帐也不是同一时刻。Stripe 余额报告说明了一种结算核对数据来源；实际字段与结算周期以所用渠道为准。

扩容优先按商户或支付 ID 保持单笔状态串行与幂等，而不是把同一笔交易同时丢给多个无协调 worker。渠道故障时限制重试并保留待核验队列；达到处理时限的 Unknown 必须告警，不能悄悄变成 Failed 清掉积压。

12. 通知推送：供应商接受不等于用户已经看到 ​

需求先分事务通知、营销通知和站内消息，再决定优先级、用户偏好、静默时间、语言、渠道和过期时间。本文假设站内是可查询的持久通知，邮件／短信／设备推送只是额外送达路径；营销退订不能被重试机制绕过。

数据至少有 notification_intents(event_id、recipient、type、payload_version)、deliveries(notification_id、channel、state、attempt、provider_id)、preferences 和 devices。POST /notification-intents 由获准业务方调用；GET /notifications 给用户查询。去重键通常由业务事件、接收者和渠道组成，不是只对模板文本做哈希。

正在绘制图示…

可切换适合窗口或原始尺寸
查看图源代码
flowchart LR
    B["业务事务 + outbox"] --> Q["通知意图队列"]
    Q --> P["偏好、静默时间、有效期与去重"]
    P --> I[("站内收件箱")]
    P --> D["按渠道分开的有界队列"]
    D --> S["邮件 / 短信 / 推送适配器"]
    S --> V["外部提供方"]
    V -->|"接受回执与可用的状态事件"| R["投递状态核对"]
    R --> D
放大图示

原始尺寸下可横向或纵向滚动；按 Escape 关闭。

正在绘制图示…

查看图源代码
flowchart LR
    B["业务事务 + outbox"] --> Q["通知意图队列"]
    Q --> P["偏好、静默时间、有效期与去重"]
    P --> I[("站内收件箱")]
    P --> D["按渠道分开的有界队列"]
    D --> S["邮件 / 短信 / 推送适配器"]
    S --> V["外部提供方"]
    V -->|"接受回执与可用的状态事件"| R["投递状态核对"]
    R --> D

状态应区分 queued、sending、provider_accepted、delivered（渠道能证明时）、expired、failed；若渠道支持打开回执，再单独记录 observed/opened。设备离线、token 失效、系统省电、用户关闭权限都可能影响终端收到。FCM 的投递说明可用来核对一种提供方的指标，不能由 API 接受成功推导每个用户看到了内容。

失败推荐动作需要防止的事
提供方限流或短暂不可用按渠道退避、抖动和配额重试一个供应商故障耗尽全部 worker
请求超时，结果未知原幂等键重试或查询状态换键重发造成重复通知
无效 token／永久地址错误标记失效，停止无意义重试每次投递都重复失败
消息已过期或用户退订发送前重新检查老队列绕过新的偏好与时效
模板更新后回放旧事件保留模板版本或兼容渲染规则重放出与原业务不同的内容

本地模型故意丢掉第一次 ACK，再重投同一个通知：

go
_ = n.Deliver("event-1", true)
_ = n.Deliver("event-1", false)
text
notify attempts=2 visible=1

这里的“一次可见”成立，因为模型接收方用 event ID 去重。很多邮件、短信接口并不提供满足你需求的持久去重契约；若接受成功后 ACK 丢了，发送方单独一个状态表无法完全消除重复。必须查提供方能力，再在可能漏发与可能重复之间做业务选择。队列的 exactly-once 宣传也不能自动扩展到外部发信副作用，Kafka 设计文档对投递语义边界有具体说明。

大规模通知按租户、优先级和渠道隔离，控制单收件人频率；批量活动分批展开，避免创建意图时一次占住全部内存。恢复从尚未终止的 delivery 重建工作，先查未知结果，再重试；监控最老消息年龄、端到端时效、永久错误率和退订执行情况，而不只看发送 QPS。

把这些题放在一起看 ​

十二个方案反复遇到的几件事很具体：稳定业务键给重试一个身份；原子边界把检查与状态变化放在一起；日志或权威数据让状态可重建；版本与租约区分新旧执行者；有界队列和明确拒绝防止故障扩散。

它们没有消除业务差异。浏览计数允许近似，库存不允许负数；Feed 可以晚一点出现，权限变更却未必能等同样久；通知可重试，支付重试必须维持同一业务意图。设计时先写不变量和结果未知时的动作，再挑组件，才知道每个组件究竟负责守住什么。

依据与本机验证 ​

本文采用的接口、数据表、阈值选择与状态机是教学设计。链接的官方文档、标准与原始论文用于支持具体语义，不意味着对应产品采用了本文完整架构。

2026-10-13 在 Go 1.27.2、Linux/amd64 实际执行全部模型，十二行输出与断言一致；普通测试、race 和 vet 均通过。并发秒杀、同键异参、时钟倒退、ID 序列耗尽、任务未到期、过期租约确认、支付金额／币种核对、G-counter 重复合并及“先查再写”的受控反例都有测试。没有运行真实集群、数据库事务、分布式分区、支付接口或外部通知请求。模型中的失败是预设状态转换，不是部署级故障注入。

完整模型与测试 ​

下面所有文件放在同一目录。没有外部依赖、监听端口或后台进程，执行结束即释放内存。输入仅为本文固定的小集合；它们不是接受任意用户输入的服务库。

sh
go run .
go test -count=1 -v ./...
go test -race -count=1 ./...
go vet ./...

go.mod ​

go.mod
module example.com/classicmodels

go 1.27.0

models.go ​

代码块 · 350 行 · 点击收起 / 展开
go
package main

import (
	"errors"
	"fmt"
	"slices"
	"strings"
	"sync"
)

// These bounded in-memory models do not provide durable or distributed storage.
func allocate(links map[string]string, target string, candidates []string) (string, error) {
	for _, code := range candidates {
		if _, exists := links[code]; !exists {
			links[code] = target
			return code, nil
		}
	}
	return "", errors.New("collision budget exhausted")
}

type Sale struct {
	mu     sync.Mutex
	Stock  int
	Orders map[string]bool
}

func (s *Sale) Reserve(key string) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	if ok, exists := s.Orders[key]; exists {
		return ok
	}
	ok := s.Stock > 0
	if ok {
		s.Stock--
	}
	s.Orders[key] = ok
	return ok
}

func feed(pushed, pulled []int, before, limit int) []int {
	seen := map[int]bool{}
	out := []int{}
	for _, src := range [][]int{pushed, pulled} {
		for _, id := range src {
			if id < before && !seen[id] {
				seen[id] = true
				out = append(out, id)
			}
		}
	}
	slices.Sort(out)
	slices.Reverse(out)
	if len(out) > limit {
		out = out[:limit]
	}
	return out
}

type Message struct {
	Seq       int
	Key, Text string
}
type Chat struct {
	Messages []Message
	Seen     map[string]Message
}

func (c *Chat) Send(key, text string) (Message, error) {
	if old, ok := c.Seen[key]; ok {
		if old.Text != text {
			return Message{}, errors.New("payload conflict")
		}
		return old, nil
	}
	m := Message{len(c.Messages) + 1, key, text}
	c.Seen[key] = m
	c.Messages = append(c.Messages, m)
	return m, nil
}
func (c *Chat) After(seq int) []Message {
	out := []Message{}
	for _, m := range c.Messages {
		if m.Seq > seq {
			out = append(out, m)
		}
	}
	return out
}

type Bucket struct {
	Tokens, Capacity, Rate float64
	LastMS                 int64
}

func (b *Bucket) Allow(nowMS int64) (bool, error) {
	if nowMS < b.LastMS {
		return false, errors.New("clock moved backward")
	}
	b.Tokens = min(b.Capacity, b.Tokens+float64(nowMS-b.LastMS)/1000*b.Rate)
	b.LastMS = nowMS
	if b.Tokens < 1 {
		return false, nil
	}
	b.Tokens--
	return true, nil
}

type IDGen struct {
	Worker, Last, Seq int64
	Started           bool
}

func (g *IDGen) Next(ms int64) (int64, error) {
	if g.Worker < 0 || g.Worker >= 1024 || ms < 0 || ms >= 1<<41 {
		return 0, errors.New("out of range")
	}
	if g.Started && ms < g.Last {
		return 0, errors.New("clock moved backward")
	}
	seq := int64(0)
	if g.Started && ms == g.Last {
		seq = g.Seq + 1
	}
	if seq >= 4096 {
		return 0, errors.New("sequence exhausted; advance clock")
	}
	g.Last, g.Seq, g.Started = ms, seq, true
	return ms<<22 | g.Worker<<12 | seq, nil
}

type Job struct {
	Due, LeaseUntil int64
	Epoch           int
	Done            bool
}

func (j *Job) Claim(now, lease int64) (int, bool) {
	if lease <= 0 || j.Done || now < j.Due || now < j.LeaseUntil {
		return 0, false
	}
	j.Epoch++
	j.LeaseUntil = now + lease
	return j.Epoch, true
}
func (j *Job) Ack(epoch int) bool {
	if j.Done || epoch != j.Epoch || epoch == 0 {
		return false
	}
	j.Done = true
	return true
}

type Score struct {
	User   string
	Points int
}

func ranking(xs []Score) []Score {
	out := slices.Clone(xs)
	slices.SortFunc(out, func(a, b Score) int {
		if a.Points > b.Points {
			return -1
		}
		if a.Points < b.Points {
			return 1
		}
		return strings.Compare(a.User, b.User)
	})
	return out
}

type Counter struct {
	Value int
	Seen  map[string]bool
}

func (c *Counter) Add(event string, n int) {
	if c.Seen[event] {
		return
	}
	c.Seen[event] = true
	c.Value += n
}
func mergeG(a, b map[string]int) map[string]int {
	out := map[string]int{}
	for k, v := range a {
		out[k] = v
	}
	for k, v := range b {
		out[k] = max(out[k], v)
	}
	return out
}
func sum(m map[string]int) int {
	n := 0
	for _, v := range m {
		n += v
	}
	return n
}

type Suggestion struct {
	Text   string
	Weight int
}

// Linear scan is only a reference for ranking correctness, not a production index.
func suggest(dict []Suggestion, prefix string, k int) []string {
	prefix = strings.ToLower(strings.TrimSpace(prefix))
	xs := []Suggestion{}
	for _, x := range dict {
		if strings.HasPrefix(x.Text, prefix) {
			xs = append(xs, x)
		}
	}
	slices.SortFunc(xs, func(a, b Suggestion) int {
		if a.Weight > b.Weight {
			return -1
		}
		if a.Weight < b.Weight {
			return 1
		}
		return strings.Compare(a.Text, b.Text)
	})
	if len(xs) > k {
		xs = xs[:k]
	}
	out := []string{}
	for _, x := range xs {
		out = append(out, x.Text)
	}
	return out
}

type Entry struct {
	Account string
	Amount  int64
}
type Payment struct {
	State                string
	Amount               int64
	Currency, ProviderID string
}
type Ledger struct {
	Payments map[string]Payment
	Posted   map[string]bool
	Entries  []Entry
}

func (l *Ledger) Reconcile(id, providerID, currency string, amount int64) error {
	p, ok := l.Payments[id]
	if !ok {
		return errors.New("unknown payment")
	}
	if amount <= 0 || amount != p.Amount || currency != p.Currency || providerID == "" {
		return errors.New("reconciliation mismatch")
	}
	if p.ProviderID != "" && p.ProviderID != providerID {
		return errors.New("provider ID conflict")
	}
	if l.Posted[id] {
		return nil
	}
	// One local atomic transition is assumed; this is neither a banking ledger nor a provider call.
	l.Entries = append(l.Entries, Entry{"provider-clearing", amount}, Entry{"merchant-payable", -amount})
	p.State, p.ProviderID = "succeeded", providerID
	l.Payments[id] = p
	l.Posted[id] = true
	return nil
}
func balance(es []Entry) int64 {
	var n int64
	for _, e := range es {
		n += e.Amount
	}
	return n
}

type Notification struct {
	Seen     map[string]bool
	Visible  int
	Attempts int
}

func (n *Notification) Deliver(id string, loseACK bool) error {
	n.Attempts++
	// Models a receiver that supports persistent dedupe; many providers do not.
	if !n.Seen[id] {
		n.Seen[id] = true
		n.Visible++
	}
	if loseACK {
		return errors.New("ack lost: result unknown")
	}
	return nil
}

func demos() []string {
	out := []string{}
	links := map[string]string{"a": "old"}
	code, err := allocate(links, "new", []string{"a", "b"})
	out = append(out, fmt.Sprintf("shortlink code=%s old=%s err=%v", code, links["a"], err))
	sale := &Sale{Stock: 1, Orders: map[string]bool{}}
	a, b, c := sale.Reserve("u1"), sale.Reserve("u1"), sale.Reserve("u2")
	out = append(out, fmt.Sprintf("sale first=%v replay=%v other=%v stock=%d", a, b, c, sale.Stock))
	out = append(out, fmt.Sprintf("feed=%v", feed([]int{7, 4}, []int{9, 7}, 10, 3)))
	chat := &Chat{Seen: map[string]Message{}}
	m1, _ := chat.Send("client-1", "hi")
	m2, _ := chat.Send("client-1", "hi")
	out = append(out, fmt.Sprintf("chat seq=%d replay=%d missed=%d", m1.Seq, m2.Seq, len(chat.After(0))))
	bucket := &Bucket{Tokens: 2, Capacity: 2, Rate: 1}
	r1, _ := bucket.Allow(0)
	r2, _ := bucket.Allow(0)
	r3, _ := bucket.Allow(0)
	r4, _ := bucket.Allow(1000)
	out = append(out, fmt.Sprintf("limit=%v %v %v %v", r1, r2, r3, r4))
	gen := &IDGen{Worker: 3}
	id1, _ := gen.Next(100)
	id2, _ := gen.Next(100)
	_, err = gen.Next(99)
	out = append(out, fmt.Sprintf("ids distinct=%v rollback=%v", id1 != id2, err))
	job := &Job{Due: 10}
	e1, _ := job.Claim(10, 5)
	e2, _ := job.Claim(15, 5)
	old, current := job.Ack(e1), job.Ack(e2)
	out = append(out, fmt.Sprintf("job old_ack=%v current_ack=%v", old, current))
	out = append(out, fmt.Sprintf("ranking=%v", ranking([]Score{{"z", 90}, {"b", 100}, {"a", 90}})))
	counter := &Counter{Seen: map[string]bool{}}
	counter.Add("e1", 1)
	counter.Add("e1", 1)
	merged := mergeG(map[string]int{"a": 2}, map[string]int{"a": 1, "b": 3})
	out = append(out, fmt.Sprintf("counter dedup=%d merged=%d", counter.Value, sum(merged)))
	out = append(out, fmt.Sprintf("suggest=%v", suggest([]Suggestion{{"go", 9}, {"golang", 7}, {"gopher", 5}, {"java", 10}}, "Go", 2)))
	ledger := &Ledger{Payments: map[string]Payment{"p1": {State: "unknown", Amount: 100, Currency: "USD"}}, Posted: map[string]bool{}}
	_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
	_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
	out = append(out, fmt.Sprintf("payment state=%s entries=%d balance=%d", ledger.Payments["p1"].State, len(ledger.Entries), balance(ledger.Entries)))
	n := &Notification{Seen: map[string]bool{}}
	_ = n.Deliver("event-1", true)
	_ = n.Deliver("event-1", false)
	out = append(out, fmt.Sprintf("notify attempts=%d visible=%d", n.Attempts, n.Visible))
	return out
}
func main() {
	for _, line := range demos() {
		fmt.Println(line)
	}
}

models_test.go ​

代码块 · 149 行 · 点击收起 / 展开
go
package main

import (
	"reflect"
	"sync"
	"testing"
)

func TestModels(t *testing.T) {
	want := []string{
		"shortlink code=b old=old err=<nil>",
		"sale first=true replay=true other=false stock=0",
		"feed=[9 7 4]",
		"chat seq=1 replay=1 missed=1",
		"limit=true true false true",
		"ids distinct=true rollback=clock moved backward",
		"job old_ack=false current_ack=true",
		"ranking=[{b 100} {a 90} {z 90}]",
		"counter dedup=1 merged=5",
		"suggest=[go golang]",
		"payment state=succeeded entries=2 balance=0",
		"notify attempts=2 visible=1",
	}
	if got := demos(); !reflect.DeepEqual(got, want) {
		t.Fatalf("got %q\nwant %q", got, want)
	}
}
func TestConcurrentSale(t *testing.T) {
	s := &Sale{Stock: 3, Orders: map[string]bool{}}
	var wg sync.WaitGroup
	for i := range 100 {
		wg.Go(func() { s.Reserve(string(rune(i))) })
	}
	wg.Wait()
	accepted := 0
	for _, ok := range s.Orders {
		if ok {
			accepted++
		}
	}
	if s.Stock != 0 || accepted != 3 {
		t.Fatal(s.Stock, accepted)
	}
}
func TestFailures(t *testing.T) {
	t.Run("shortlink exhaustion preserves data", func(t *testing.T) {
		m := map[string]string{"a": "old"}
		if _, err := allocate(m, "new", []string{"a"}); err == nil || m["a"] != "old" {
			t.Fatal(m, err)
		}
	})
	t.Run("chat same key different body", func(t *testing.T) {
		c := &Chat{Seen: map[string]Message{}}
		_, _ = c.Send("k", "one")
		if _, err := c.Send("k", "two"); err == nil {
			t.Fatal("accepted changed payload")
		}
	})
	t.Run("bucket clock rollback", func(t *testing.T) {
		b := &Bucket{Tokens: 1, Capacity: 1, Rate: 1, LastMS: 10}
		if _, err := b.Allow(9); err == nil {
			t.Fatal("clock rollback")
		}
	})
	t.Run("ID exhaustion", func(t *testing.T) {
		g := &IDGen{}
		for range 4096 {
			if _, err := g.Next(10); err != nil {
				t.Fatal(err)
			}
		}
		if _, err := g.Next(10); err == nil {
			t.Fatal("wrapped sequence")
		}
		if _, err := g.Next(11); err != nil {
			t.Fatal(err)
		}
	})
	t.Run("job not due", func(t *testing.T) {
		j := &Job{Due: 10}
		if _, ok := j.Claim(9, 5); ok {
			t.Fatal("early")
		}
		if _, ok := j.Claim(10, 5); !ok {
			t.Fatal("not claimed")
		}
		if _, ok := j.Claim(11, 5); ok {
			t.Fatal("duplicate lease")
		}
	})
	t.Run("payment mismatch", func(t *testing.T) {
		l := &Ledger{Payments: map[string]Payment{"p": {Amount: 100, Currency: "USD"}}, Posted: map[string]bool{}}
		if err := l.Reconcile("p", "fake", "EUR", 100); err == nil || len(l.Entries) > 0 {
			t.Fatal("posted mismatch")
		}
	})
	t.Run("payment wrong amount leaves state unchanged", func(t *testing.T) {
		original := Payment{State: "unknown", Amount: 100, Currency: "USD"}
		l := &Ledger{Payments: map[string]Payment{"p": original}, Posted: map[string]bool{}}
		if err := l.Reconcile("p", "fake", "USD", 101); err == nil {
			t.Fatal("accepted wrong amount")
		}
		if l.Payments["p"] != original || len(l.Entries) != 0 || len(l.Posted) != 0 {
			t.Fatal("rejected observation mutated state")
		}
	})
	t.Run("payment provider conflict after success", func(t *testing.T) {
		l := &Ledger{Payments: map[string]Payment{"p": {State: "unknown", Amount: 100, Currency: "USD"}}, Posted: map[string]bool{}}
		if err := l.Reconcile("p", "fake-1", "USD", 100); err != nil {
			t.Fatal(err)
		}
		original := l.Payments["p"]
		if err := l.Reconcile("p", "fake-2", "USD", 100); err == nil {
			t.Fatal("accepted another provider ID")
		}
		if l.Payments["p"] != original || len(l.Entries) != 2 || balance(l.Entries) != 0 {
			t.Fatal("provider conflict mutated state")
		}
		if err := l.Reconcile("p", "fake-1", "USD", 100); err != nil || len(l.Entries) != 2 {
			t.Fatal("duplicate posted", err)
		}
	})
	t.Run("G-counter merge repeat", func(t *testing.T) {
		a, b := map[string]int{"a": 2}, map[string]int{"b": 3}
		m := mergeG(a, b)
		if sum(mergeG(m, b)) != 5 {
			t.Fatal("non-idempotent merge")
		}
	})
}

// Controlled counterexample: no data race, yet a read-check-write schedule oversells.
func TestCheckThenWriteCounterexample(t *testing.T) {
	stock := 1
	aSaw, bSaw := stock, stock
	accepted := 0
	if aSaw > 0 {
		stock = aSaw - 1
		accepted++
	}
	if bSaw > 0 {
		stock = bSaw - 1
		accepted++
	}
	if stock != 0 || accepted != 2 {
		t.Fatal(stock, accepted)
	}
	t.Logf("broken schedule: stock=%d accepted=%d", stock, accepted)
}

保留各书来源与许可 · 示例运行条件以正文为准