Sharding and Leases: Hashing userId → shard, SET NX + TTL + Lua Renewal, Per-User Ordering, Handoff

Interview questions

• Why hash user ids into shards instead of letting the consumer group dispatch freely, and how do you pick the shard count?为什么要对 userId 做哈希分片，而不是让消费组随机派发？分片数应该怎么选？

  Common in ChinaCommon overseasBasic#sharding#consistent-hashing#scalability

  How to reason about it · think before answering

  1. The hinge is 'why not dispatch freely'. Answering 'for load balancing' misses it — a consumer group already balances load, and free dispatch balances better than hashing. Sharding buys something else: affinity.
  2. The chain: a consumer group's unit of assignment is one message, while the business requires one user as the smallest serial unit. When those units disagree, two messages from the same user get processed concurrently by two workers.
  3. Second step: why insert a shard layer instead of taking userId modulo the worker count? Because the worker count changes on scale-up, restart, crash and rolling deploy. Change the divisor and almost every user is remapped, so in-flight sessions migrate wholesale. A fixed shard count pins user-to-shard and lets only shard-to-worker float.
  4. For the count, give criteria rather than a number: it caps parallelism (256 shards means at most 256 useful workers), and changing it is a data migration (every user is remapped, requiring downtime or a dual-write transition). So oversize it up front — 256 across 3 workers is 85/85/86 and costs a few hundred keys of memory, while picking 8 walls you in at the ninth worker. Use a power of two so the modulo degrades to a bit mask and future splits stay clean.
  5. Volunteer the limit of uniformity: it means uniform user counts, not uniform message volume. One enterprise account sending a thousand messages a day can share a shard with a thousand one-message users. The fix is an exception table before the hash that gives that account its own shard, not a larger shard count — that would be the migration above.
  6. Expect the follow-up: why not consistent hashing? It optimizes remap volume, which pays off when shards carry state that is expensive to move. Our workers are stateless executors with state in Postgres and Redis, so nothing needs moving, and shard ownership is already decided dynamically by leases. Fixed sharding optimizes predictability, which is simpler and more reliable here.

  分析过程 · 先想清楚再作答

  1. 题眼在「为什么不随机派发」。只答「为了负载均衡」就掉进坑里了——消费组本来就是负载均衡，随机派发在均衡上比哈希分片更好。分片解决的是另一件事：亲和性。
  2. 推导链是这样的：消费组的分配单位是「一条消息」，而业务要求的最小串行单位是「一个用户」；单位对不上，同一个用户连发的两句话就会被两个进程同时处理。所以要把分配单位从消息抬到用户。
  3. 第二步是「为什么中间要垫一层 shard，而不是 userId 直接取模 worker 数」。因为 worker 数会变——扩容、重启、崩溃、滚动发布；除数一变，几乎所有用户的归属都会变，正在处理的会话被整体搬家。固定的 shard 数把「用户到 shard」钉死，只让「shard 到 worker」随伸缩浮动。
  4. 分片数怎么选，要给出可执行的判据而不是一个数字：它是并行度的上限（256 个 shard 最多让 256 个 worker 有活干），而且改它等于一次数据迁移（所有用户归属重算，必须停机或双写过渡）。所以宁可一开始定得偏大——256 摊在 3 个 worker 上是 85、85、86，多出来的成本只是几百个 key 的内存；定成 8 个的话扩到第 9 个 worker 就撞墙了。要用 2 的幂，取模能退化成位运算，也方便将来对半拆分。
  5. 主动说出哈希均匀的边界：均匀说的是「用户数均匀」，不是「消息量均匀」。一个日发千条的大客户可能和一千个散户落在同一个 shard 上。缓解是给大客户在哈希前加一张小的例外表、单独占一个 shard，而不是把总分片数调大（那就是上面说的数据迁移）。
  6. 可预期的追问：为什么不用一致性哈希？答案是它优化的是「节点变化时的迁移量」，前提是分片承载状态、搬迁很贵。我们的 worker 是无状态执行体，状态在数据库和 Redis 里，没有数据要搬；而且 shard 到 worker 的归属本来就由租约动态决定。固定分片优化的是可预测性，在这个场景里更简单，也更可靠。

  Key points

  • Sharding is about affinity, not balancing: it lifts the unit of assignment from one message to one user so a user always lands on the same worker
  • The fixed shard layer keeps user-to-shard stable across scaling; only shard-to-worker ownership moves
  • The shard count caps parallelism and changing it is a migration, so oversize it and use a power of two (256 in this course)
  • Uniform hashing means uniform user counts, not uniform traffic; hot accounts need an exception table before the hash
  • Consistent hashing optimizes remap volume and only pays off for stateful shards; stateless workers do better with fixed shards

  答题要点

  • 分片解决的是亲和性不是负载均衡：把分配单位从「一条消息」抬到「一个用户」，同一个用户永远落到同一个 worker
  • 中间垫一层固定 shard，是为了让 worker 伸缩时用户到 shard 的映射保持不变，只有 shard 到 worker 的归属浮动
  • 分片数是并行度上限，改它等于一次数据迁移，所以一开始就定偏大、用 2 的幂（本课 256）
  • 哈希均匀保的是用户数均匀，不是消息量均匀；大客户热点要靠哈希前的例外表单独拆 shard
  • 一致性哈希优化迁移量，只在分片带状态时划算；无状态 worker 用固定分片更简单
• Why must a lease carry a TTL, and why renew it with a Lua script instead of GET followed by PEXPIRE?租约为什么必须配合 TTL？续约为什么要用 Lua 脚本，而不是先 GET 再 PEXPIRE？

  Common in ChinaCommon overseasIntermediate#lease#redis#atomicity

  How to reason about it · think before answering

  1. There are two things being tested and the second is the discriminator. The first is really 'do you know a lease is not a lock': a lock means mutual exclusion (I hold, you wait, you get it when I release), while a lease means ownership with an expiry (it lapses even if the holder never releases, because the holder may never come back).
  2. That gives you the necessity of the TTL: holders get kill -9'd, lose the network, lose the whole machine — they never get to hand anything back. Without a TTL you have a lock that is never released and a shard that is permanently orphaned until a human intervenes.
  3. Volunteer the TTL trade-off to show you have tuned this: too short and a GC pause or a network blip costs you the lease, so shards flap and sessions keep migrating; too long and a genuinely dead worker's shards sit idle for a full TTL. A common setting is a 30 second TTL renewed every 10 seconds (one third), which tolerates two consecutive renewal failures.
  4. The second point is atomicity, and you should spell out the failing interleaving: GET says the lease is yours, then within two milliseconds it expires, Redis drops it, another worker wins it with SET NX, and your PEXPIRE succeeds — you have just extended your rival's lease while believing you still hold the shard. If step two is SET rather than PEXPIRE you also overwrite their owner field and both processes start working.
  5. Land on the general principle: check-and-mutate must be indivisible (compare-and-swap). Redis executes commands single-threaded, so one EVAL is a single atomic step to every other client — Lua here is not about performance, it is about fusing GET and PEXPIRE. Redis Functions or WATCH plus a transaction retry are equivalent, but Lua is the most direct.
  6. Expect the follow-up: what should a renewal returning 0 do? Let go immediately — drop the shard from the held set, stop consuming, and refuse to write the in-flight item. Logging a warning and carrying on is the most common source of split brain. Add a self-kill rule too: if the last successful renewal is older than two thirds of the TTL, release everything.

  分析过程 · 先想清楚再作答

  1. 这题有两个考点，第二个才是区分度。第一个考点其实是在问「你知不知道租约和分布式锁不是一回事」——先把这条说清：锁的语义是互斥（我持有、你等待，我主动 release 你才拿得到），租约的语义是带过期时间的所有权（持有者不 release 也会失效，因为它可能永远不会回来了）。
  2. 由此推出 TTL 的必要性：持有者会被 kill -9、会断网、会整台机器掉电，它没有机会归还。没有 TTL 就是一把永不释放的锁，那个 shard 从此永久荒废，只能靠人工介入。TTL 的全部意义是「不需要任何人干预，所有权会自己失效」。
  3. 顺手说出 TTL 的取舍，证明你调过：太短则一次垃圾回收停顿或网络抖动就丢租约，shard 反复易主、用户会话来回搬家；太长则真死了之后要等满一个 TTL 才有人接手。常见口径是 TTL 30 秒、续约间隔取 TTL 的三分之一（10 秒），这样能连续失败两次而不丢租约。
  4. 第二个考点是原子性。两步写法的失败时间线要具体讲出来：GET 返回「是我的」，紧接着的两毫秒里租约恰好到期被 Redis 删除、另一个 worker SET NX 抢到，然后你的 PEXPIRE 执行成功——你续的是对手的租约，而自己还以为持有。如果第二步用的是 SET 而不是 PEXPIRE，你还会把对手的名字覆盖成自己，两个进程一起动手。
  5. 结论要落到通用原理上：检查和改动必须是一个不可分割的动作（compare-and-swap）。Redis 单线程执行命令，一整段 EVAL 对其他客户端就是一个原子步骤，所以 Lua 在这里不是为了性能，是为了把 GET 和 PEXPIRE 粘成一条。等价手段还有 Redis 函数、或用 WATCH 加事务重试，但 Lua 最直接。
  6. 可预期的追问：续约返回 0 应该怎么办？答「立刻放手」——把这个 shard 从持有集合里删掉、停止取消息、手上那条没做完的不许再写。返回 0 只打一行警告日志然后继续跑，是脑裂最常见的来源。再加一条自杀规则：距上次成功续约超过 TTL 的三分之二就主动全部放手。

  Key points

  • A lease is not a lock: locks give mutual exclusion, leases give ownership with an expiry, because the holder may never return
  • Without a TTL you have a never-released lock and a permanently orphaned shard once the holder is killed
  • A 30 second TTL renewed every 10 seconds leaves headroom for two consecutive renewal failures
  • In the two-step window the lease may already have changed hands, so your PEXPIRE extends a rival's term while you still think you hold it
  • Lua fuses the ownership check and the extension into one atomic step; a renewal returning 0 means let go immediately

  答题要点

  • 租约不是锁：锁是互斥，租约是带过期时间的所有权；持有者可能永远不会回来，所以所有权必须能自己失效
  • 没有 TTL 就是永不释放的锁，持有者被 kill 之后那个 shard 永久荒废
  • TTL 30 秒、续约间隔 10 秒（TTL 的三分之一），留出连续两次续约失败的余量
  • 两步续约的窗口里租约可能已易主，你的 PEXPIRE 会替对手延长任期，而自己仍以为持有
  • Lua 的作用是把「比较持有者」和「续期」粘成一个原子步骤，不是为了性能；续约返回 0 必须立刻放手
• What happens when two workers both believe they hold the same shard lease (split brain), and how do you mitigate it?两个 worker 同时认为自己持有同一个 shard 的租约（脑裂）会造成什么后果，怎么规避？

  Common in ChinaCommon overseasDeep dive#split-brain#fencing-token#reliability

  How to reason about it · think before answering

  1. The scoring criterion here is explicit: does your answer contain the sentence 'a Redis lease alone cannot give absolute mutual exclusion'. Anyone who says SET NX plus a TTL makes it safe gets probed until they run out of answers.
  2. Start with how split brain arises, and use the common case: not a crash, but a holder that merely froze for five seconds — a full GC, a noisy neighbour saturating the host CPU, cgroup throttling. It wakes up still believing it holds shard 68, keeps processing the in-flight message and keeps writing, while the lease expired and was taken. Add the second layer: Redis replication is asynchronous, so a failover can lose the last few milliseconds of writes and let two workers both win SET NX.
  3. Then the consequences, expressed in business terms rather than 'inconsistent data': two messages from one user processed concurrently means out-of-order replies, a corrupted context window, and unique(run_id, seq) violations that silently drop a message. Worst is reordered or duplicated side effects — swap 'cancel the order' with 'move the delivery date' and you cancel an order the user wanted to keep.
  4. The key shift: since you cannot rule out that timeline on the Redis side, the goal is not to prevent split brain but to make the second writer's writes fail — push conflict detection and rejection down to the layer that actually causes side effects.
  5. Give three mitigations by value. First, a self-kill rule in the worker: after two consecutive renewal failures, or when the last success is older than two thirds of the TTL, stop processing and clear the held set — cheapest, and it bounds the 'I think I still hold it' window to two renewal periods. Second, fencing tokens: take a monotonically increasing number (Redis INCR) when acquiring, store it in the lease value, attach it to every side-effecting operation, and have the downstream accept only numbers not lower than the highest it has seen — in a database that is one conditional update. The revived predecessor carries a stale number and is rejected. Third, re-validate the lease immediately before each write inside the same script or transaction, which shrinks the window without closing it.
  6. Expect the follow-up: where does fencing break down? It needs downstream cooperation. Databases do conditional updates, but a third-party endpoint (SMS, payments) will not compare your token, so you fall back to idempotency keys that make duplicate execution harmless rather than impossible. True mutual exclusion means moving to a consensus-backed system such as etcd or ZooKeeper session leases, paying in write latency and operational complexity.

  分析过程 · 先想清楚再作答

  1. 这题的判分点非常明确：答案里有没有出现「单靠 Redis 租约做不到绝对互斥」。说「用了 SET NX 加 TTL 就安全了」的人，会被追问到答不上来。
  2. 先讲脑裂是怎么发生的，而且要举那个最常见的场景——不是进程崩溃，是持有者只卡了 5 秒：一次 full GC、宿主机 CPU 被邻居打满、容器被 cgroup 限流。它醒过来时内存里还写着「我持有 shard 68」，继续处理手上那条消息、继续写库，而 Redis 里的租约早已到期并被别人抢走。再补一层：Redis 主从复制是异步的，切主时可能丢掉最后几毫秒的写入，于是两个 worker 都能 SET NX 成功。
  3. 然后讲后果，而且要落到业务上而不是停在「数据不一致」：同一个用户的两条消息被两个进程并发处理，回复乱序、上下文错乱、messages 表的 unique(run_id, seq) 撞约束导致落库失败；最严重的是有副作用的工具被重排或重复执行——「取消订单」和「改配送日期」顺序反了，结果是取消了一个用户本来想留下的订单。
  4. 关键的认知转折：既然无法在 Redis 一侧排除这条时间线，正确的思路就不是「让脑裂不发生」，而是「让第二个人的写入落不了地」——把冲突的检测与拒绝推到真正产生副作用的那一层。
  5. 三条手段按性价比给出。一是 worker 自己的自杀规则：连续两次续约失败、或距上次成功续约超过 TTL 的三分之二，立刻停止处理并清空持有集合——最便宜，把「我以为我还持有」的窗口从无限压到两个续约周期。二是 fencing token：抢租约时从一个单调递增计数器取号（Redis 的 INCR）写进租约值，之后所有有副作用的操作都带上它，下游只接受不比见过的最大号小的写入，落到数据库上就是一句条件更新；醒过来的前任拿的是旧号，写入直接被拒。三是每次写之前重新校验租约，并把校验与写入放进同一段脚本或同一个事务——这只缩小窗口，不消除。
  6. 可预期的追问：fencing 的局限在哪？答「它需要下游配合」。数据库能做条件更新所以好使，但下游是第三方接口（发短信、扣款）时你没法让对方帮你比号，这时只能退回幂等键，把重复执行变成无害，而不是让它不发生。真要绝对互斥就得换到有共识协议的系统（etcd、ZooKeeper 的会话租约），代价是写入延迟和运维复杂度。

  Key points

  • A Redis lease alone cannot guarantee mutual exclusion: a frozen holder that revives, and asynchronous replication losing writes on failover, are both unavoidable
  • State consequences in business terms: out-of-order replies, corrupted context, unique-constraint violations dropping messages, and reordered or duplicated side effects
  • The goal is to make the second writer's writes fail — push conflict detection to the side-effecting layer instead of hoping split brain never happens
  • Three mitigations: a worker self-kill rule on repeated renewal failure, fencing tokens enforced as conditional updates, and re-validating the lease immediately before writing
  • Fencing needs downstream cooperation; against third-party endpoints fall back to idempotency keys, and true mutual exclusion means a consensus system like etcd or ZooKeeper

  答题要点

  • 单靠 Redis 租约做不到绝对互斥：持有者被冻结再醒来、以及主从异步复制丢写，这两条时间线排除不掉
  • 后果要落到业务：同用户回复乱序、上下文错乱、唯一约束冲突丢消息，最严重是有副作用的工具被重排或重复执行
  • 思路是「让第二个人的写入落不了地」，把冲突检测推到产生副作用的那一层，而不是指望脑裂不发生
  • 三条手段：worker 自杀规则（续约连续失败就放手）、fencing token（写入时带单调号做条件更新）、写前重新校验租约
  • fencing 需要下游配合；下游是第三方接口时只能退回幂等键，要绝对互斥就得换 etcd / ZooKeeper 这类有共识协议的系统
• In a multi-worker agent service, how do you guarantee that one user's messages are processed in strict order?在一个多 worker 的 Agent 服务里，怎么保证同一个用户的消息严格按顺序被处理？

  Common in ChinaCommon overseasIntermediate#ordering#sharding#distributed-systems

  How to reason about it · think before answering

  1. This is a small system-design question testing whether you can decompose ordering into layered guarantees rather than naming a middleware. 'Partition by key in Kafka' is not wrong, but it leaves 'and inside the process?' unanswered, which is exactly where they will push.
  2. Decompose it along the path from ingress to side effect, four layers. One, ordered ingress: the gateway assigns consecutive seq numbers per session on write and publishes in seq order; a single stream is append-ordered, so this layer is nearly free. Two, single consumer: only one worker reads a given shard at a time, enforced by the lease — that is the cross-process half.
  3. Three, in-process serialization: no two messages from the same shard may be handled concurrently. This is the layer people break themselves, by dropping a batch into Promise.all or a thread pool to raise throughput. Say it explicitly: the lease preserves order across processes, await preserves it inside one. Four, in-flight first: a killed predecessor may hold a delivered but unacknowledged message, so the successor must claim it back before reading anything new, otherwise a newer message jumps ahead of an older one.
  4. Then name the cost of serialization, which is where they judge whether you have shipped this: a single slow request blocks other users on the same shard, and one 20-second model call can stall every shard that worker owns. The right shape is parallel across shards, serial within a shard — one independent processing chain per held shard. The unit of parallelism is the shard, not the message.
  5. Volunteer the boundary: this only guarantees per-user order, never a global order across users. Global ordering requires parallelism of one, which defeats the point. Ordering and parallelism trade off directly, so sharding exists to shrink the 'must be ordered' scope to the smallest useful unit.
  6. Expect two follow-ups. Could you skip leases? Yes — Kafka key partitioning or sticky routing from the gateway to a fixed worker also gives affinity, at the cost of rigid partition counts or of needing a separate failover mechanism when a worker dies; the lease happens to solve failover at the same time. Could the business simply tolerate reordering? Partly, if appends are idempotent and commutative, but any irreversible side effect such as a refund or a shipment forces you to preserve order.

  分析过程 · 先想清楚再作答

  1. 这题是系统设计小题，考的是你能不能把「顺序」拆成分层的保证，而不是丢一个中间件名字。只答「用 Kafka 按 key 分区」不算错，但没有回答「分区之后进程内怎么办」，会被追着问。
  2. 拆法是从消息进入系统到产生副作用，逐层点出谁在保顺序，一共四层。第一层入队有序：接入层落库时给同一会话的消息发连续 seq，并按 seq 投递，总线对同一条流是追加有序的，这层几乎免费。第二层消费者唯一：同一个分片同一时刻只有一个 worker 在读，靠租约实现——这是跨进程的那一半。
  3. 第三层进程内串行：同一个分片内不能并发处理两条消息。这一层最容易被自己破坏——为了提高吞吐把一批消息丢进 Promise.all 或线程池，顺序就在自己的代码里丢掉了。要明确说出「租约保住跨进程的顺序，await 保住进程内的顺序，缺一不可」。第四层在途优先：前任 worker 挂掉时手上可能有一条已领取但没确认的消息，接管者必须先把它 claim 回来再读新消息，否则新消息会插到旧消息前面。
  4. 紧接着说串行的代价，这是面试官判断你有没有上过线的地方：串行意味着一个用户的慢请求会挡住同一个分片上其他用户的消息，一次 20 秒的模型调用能让这个 worker 名下的几十个分片全部停摆。正确做法是按分片并行、分片内串行——每个持有的分片各起一条独立处理链。并行的单位是分片，不是消息。
  5. 主动划边界：这套机制只保证同一个用户的顺序，不保证跨用户的全局顺序。全局有序需要把并行度压到 1，那就没有分布式可谈了。顺序性和并行度是一对反比，分片的意义就是把「必须有序」的范围缩到刚好够用的最小值。
  6. 可预期的追问一：不用租约行不行？可以，Kafka 按 key 分区、或者让 Gateway 直连固定 worker（粘性路由）都能得到亲和性，但代价分别是分区数难改、以及 worker 挂掉时需要额外的故障转移机制——租约恰好把故障转移也一并解决了。追问二：能不能干脆让业务对乱序免疫？部分可以，比如把「追加消息」设计成幂等且可交换的写入，但只要存在不可逆的副作用（退款、发货），顺序就必须保。

  Key points

  • Decompose ordering into four layers: ordered ingress with consecutive seq, a single consumer per shard via the lease, in-process serialization with await, and claiming the predecessor's in-flight message first
  • The lease preserves order across processes and await preserves it within one — reaching for Promise.all to raise throughput destroys it
  • The unit of parallelism is the shard, not the message: one chain per held shard, or a single slow call stalls every shard that worker owns
  • Only per-user order is guaranteed, never a global order; ordering trades off against parallelism, so sharding shrinks the ordered scope
  • Alternatives are Kafka key partitioning or sticky routing, but neither brings failover; any irreversible side effect makes ordering mandatory

  答题要点

  • 把顺序拆成四层：入队有序（连续 seq）、消费者唯一（租约）、进程内串行（逐条 await）、在途消息优先被接管者 claim 回来
  • 租约保住跨进程的顺序，await 保住进程内的顺序，缺一不可——用 Promise.all 提吞吐会当场毁掉顺序
  • 并行的单位是分片不是消息：每个持有的分片各起一条独立处理链，否则一次慢调用会拖停这个 worker 的全部分片
  • 只保证同一用户的顺序，不保证跨用户全局有序；顺序性和并行度是反比，分片就是把有序范围缩到最小
  • 替代方案是 Kafka 按 key 分区或粘性路由，但它们不自带故障转移；只要存在不可逆副作用，顺序就必须保

Comments

Sign in to join the discussion

No comments yet — be the first.