崧云悠揽月

库存锁定算法对比与并发控制

崧云悠揽月
May 25, 2026

1. 背景 ​

用户下单到实际出库之间有一段窗口期，期间库存需要"预占"，防止其他订单超卖：

真实库存 = 可用 (quantity) + 锁定 (lockQuantity) + 在途 (inTransitQuantity)

库存锁定要解决的三大挑战：

挑战表现本文方案
拆仓多一个订单跨多个仓发货§2 分配算法
库存碎片化仓库里堆积无法承接订单的小尾巴§4 工程实践
并发超扣多订单同时锁定同一批库存§3 并发控制

2. 分配算法 ​

核心问题：一个订单需要 N 件商品，从 5 个仓库怎么分配？

2.0 前置：什么是贪心算法 ​

贪心算法（Greedy）：每一步都做"当前看起来最好"的选择，不回溯、不看未来。简单高效，但不保证最优。

用硬币兑换举例：

题目币值贪心策略贪心结果最优解
凑 63 元[1, 5, 10, 25, 50]每次取最大不超过剩余的币值50+10+1+1+1 = 5 枚 ✅5 枚
凑 6 元[1, 3, 4]同上4+1+1 = 3 枚 ❌3+3 = 2 枚

结论：贪心是否最优取决于问题结构。库存锁定属于"贪心不一定最优，但工程上够用"的场景。

2.1 顺序贪心 ​

思路：按库存从小到大（或从大到小）排序，逐个扣减直到满足需求。

python
def sequential_greedy(warehouses, need, ascending=False):
    sorted_whs = sorted(warehouses, key=lambda w: w.quantity, reverse=not ascending)
    locks, remaining = [], need
    for w in sorted_whs:
        if remaining <= 0:
            break
        lock = min(remaining, w.quantity)
        if lock > 0:
            locks.append((w.name, lock))
            w.quantity -= lock
            remaining -= lock
    return locks

示例：仓库 [A=10, B=20, C=30, D=40, E=50]，连续锁定 30 件 × 3 次。

方向R1R2R3总拆仓最终状态
从小到大A 10 + B 20C 30D 30 (留10)4[0,0,0,10,50]
从大到小E 30 (留20)D 30 (留10)C 303[10,20,0,10,20]

优缺点：✅ 极简、性能好；❌ 小→大必然多拆仓；大→小消耗大仓，未来大单无仓可用。

2.2 动态规划 ​

DP 是什么：穷举所有可能的子问题、保留每个子问题最优解的方法。和贪心的区别：贪心一旦选定不回头，DP 把所有路径都算一遍再挑最好的。

思路：把库存锁定建模成 Subset Sum 问题——找一组仓位使总锁定量 ≥ need，最小化拆仓数。

python
def dp_optimal(warehouses, need):
    total = sum(w.quantity for w in warehouses)
    dp = [float('inf')] * (total + 1); dp[0] = 0
    choice = [[] for _ in range(total + 1)]
    for i, w in enumerate(warehouses):
        for j in range(total, -1, -1):
            if dp[j] == float('inf'):
                continue
            for x in range(1, w.quantity + 1):
                if j + x > total:
                    break
                if dp[j] + 1 < dp[j + x]:
                    dp[j + x] = dp[j] + 1
                    choice[j + x] = choice[j] + [(i, x)]
    best = min((j for j in range(need, total + 1) if dp[j] != float('inf')),
               key=lambda j: (dp[j], j))
    return [(warehouses[i].name, x) for i, x in choice[best]]

示例：仓库 [A=25, B=20, C=15, D=10, E=5]，需求 = 30（所有仓都不够，必须拆）。

算法方案拆仓碎片
贪心(大→小)A 25 + B 5215（B 仓剩 15）
DPA 25 + E 5（sum=30）20 ✅
DP 备选B 20 + D 10（sum=30）20 ✅

DP 通过枚举子集精确凑齐 30，零碎片。

优缺点：✅ 理论最优、可零碎片；❌ 复杂度 O(n × N × max_q)，业务规则塞进 DP 状态方程极复杂，不适合实时下单。

2.3 BF + 贪心 ​

思路：分两阶段——

阶段 1（Best Fit）：有单仓够用？→ 选最小够用仓，单仓出完
阶段 2（贪心兜底）：都不够 → 从大到小拆仓
python
def best_fit_with_greedy(warehouses, need):
    sufficient = [w for w in warehouses if w.quantity >= need]
    if sufficient:                                          # 阶段1
        target = min(sufficient, key=lambda w: w.quantity)
        target.quantity -= need
        return [(target.name, need)]
    return sequential_greedy(warehouses, need, ascending=False)  # 阶段2

示例：仓库 [A=60, B=55, C=50, D=20, E=10]，先锁 50 再锁 60。

算法R1 (need=50)R1 后状态R2 (need=60)R2 拆仓
贪心(大→小)A 锁 50（A 被锯）[10,55,50,20,10]A 不够，B 55 + C 52 ❌
BF + 贪心C 锁 50（最小够用）[60,55,0,20,10]A 锁 601 ✅

BF 选了最小够用仓 C，保护大仓 A 完整，使 R2 仍能单仓出完。

优缺点：✅ 简单、性能好、保护大仓、阶段清晰；❌ 不保证全局最优，阶段 1 仍会留小尾巴。

3. 并发控制 ​

核心问题：多个订单同时锁定同一批库存，如何避免超扣？

3.1 悲观锁（SELECT FOR UPDATE） ​

场景：事务内独占行锁，其他事务等待。

typescript
const products = await ctx.model.ProductStorage.findAll({
    where: { id: ids },
    transaction,
    lock: true,                       // SELECT ... FOR UPDATE
});
// 事务内独占，提交/回滚后释放

优缺点：✅ 简单、强一致；❌ 热点行排队，高并发性能差。

3.2 乐观锁（version 字段 / CAS） ​

场景：先读 version，更新时 CAS 校验，失败则重试。

typescript
const result = await ProductStorage.update(
    { quantity: newQty, version: row.version + 1 },
    { where: { id: row.id, version: row.version } },   // CAS
);
if (result[0] === 0) throw new Error('并发冲突，请重试');

优缺点：✅ 无锁等待、性能好；❌ 冲突多时重试代价大。

3.3 分布式锁（Redis） ​

场景：跨服务、跨实例的业务级锁，或锁定粒度比 DB 行更粗的对象。

typescript
const ok = await redis.set(`lock:product:${id}`, val, 'EX', 5, 'NX');
if (!ok) throw new Error('库存锁繁忙');
try {
    // 业务逻辑
} finally {
    await redis.eval(UNLOCK_LUA, 1, key, val);   // Lua 保证原子释放
}

优缺点：✅ 跨服务、解耦数据库；❌ 锁过期、客户端崩溃要兜底，实现细节多。

三种方案对比 ​

方案性能强一致实现复杂度适用场景
悲观锁中✅低单库、低并发、强一致要求
乐观锁高✅中冲突少、读多写少、性能敏感
分布式锁中取决实现高跨服务、跨实例、业务级锁

实战建议：单库场景优先悲观锁（最简单可靠）；冲突少且追求性能用乐观锁；跨服务才上分布式锁。

4. 工程实践 ​

算法只是局部最优，落地还需流程兜底：

机制作用
定时调拨整合周期任务把碎片仓库存调拨到主仓，物理消除碎片
仓管手动调整锁定 ≠ 出库，仓管在拣货现场可基于实际情况换仓/合单
碎片阈值过滤算法侧剔除"小于阈值的碎片仓"，让其等待整合
预占 + 正占两级软预占带 TTL，用户确认后才硬锁，减少死锁碎片

关键认知：把脏活留给流程层，算法保持简单清晰。

5. 总结 ​

维度顺序贪心动态规划BF + 贪心
复杂度O(n log n)O(n × N × max_q)O(n log n)
拆仓数中最少少
碎片量多 / 中最少少
业务扩展✅❌✅
推荐场景Baseline离线批量实时锁定主流程 ⭐

库存锁定 = 分配算法 × 并发控制 × 工程兜底。 算法选 BF + 贪心（简单 + 实用），并发选悲观锁或乐观锁（看场景），碎片化交给定时调拨——三者配合才是完整答案，不要奢求单一算法解决所有问题。

最后更新时间: