队列、重试与幂等 · 系统设计

为什么需要它

直觉理解

定义

消息队列

A buffer where producers put work and workers take it, so the two can run at different speeds.

生产者放入工作、工作者取出工作的缓冲区，让两边可以按不同的速度运行。

背压

Pushing back on producers (for example by rejecting work) when consumers can't keep up.

当消费者跟不上时，反过来对生产者施压（比如拒绝新工作）。

指数退避

Waiting twice as long after each failed attempt, up to a cap.

每次失败后等待的时间翻倍，直到一个上限。

幂等键

A unique id sent with a request so the server can recognise a retry and not do the work twice.

随请求发送的唯一 id，让服务器能认出重试，不把工作做两遍。

示例

1
2
3
4
5
6
7

arrivals = [5, 12, 12, 12, 3, 0, 0]
per_second = 8
backlog = 0
for second, n in enumerate(arrivals):
    backlog += n
    backlog -= min(backlog, per_second)
    print(second, backlog)

0 0
1 4
2 8
3 12
4 7
5 0
6 0

1
2
3
4

base, cap = 0.5, 8.0
for attempt in range(7):
    delay = min(cap, base * 2 ** attempt)
    print(attempt + 1, delay)

1 0.5
2 1.0
3 2.0
4 4.0
5 8.0
6 8.0
7 8.0

1
2
3
4
5
6
7
8
9
10
11

charged = {}

def pay(key, amount):
    if key in charged:
        return "already done"
    charged[key] = amount
    return "charged"

print(pay("order-17", 30))
print(pay("order-17", 30))
print(sum(charged.values()))

charged
already done
30

常见错误

小测验

1
2
3
4
5

backlog = 0
for n in [10, 10, 10]:
    backlog += n
    backlog -= min(backlog, 6)
print(backlog)

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

1. 预测输出退避时间表

   准确写出它打印的内容。

2. 改需求给队列设上限

   simulate 忽略了 limit。每一秒加上新到的请求之后，把积压限制在 limit 以内（多出来的请求被拒绝），然后再让工作者处理。

3. 从零写只扣一次

   写一个 process(requests)。每个请求是 (幂等键, 金额)。为每个请求返回一项，组成列表：某个键第一次出现时是 "charged"，之后同一个键的请求都是 "duplicate"。

   process([("a", 10), ("b", 5), ("a", 10)])   # ['charged', 'charged', 'duplicate']

本课术语