Plan B: Compare-and-Swap (CAS) for Lock-Free Memory Upgrades

[jlin53882]

🔗 關聯 Issue

跟隨 Issue #632 的後續追蹤

---

📋 Plan B 提案：Compare-and-Swap (CAS)

問題背景

Issue #632 的 Plan A（兩階段處理）已經緩解了主要的 lock contention 問題：

• Plan A：N locks (每個 entry) → 1 lock per batch
• 但仍然需要 lock，在某些邊界條件下可能造成競爭

解決方案

Plan B 使用 Compare-and-Swap (CAS) 實現無鎖（lock-free）並發更新：

┌─────────────────────────────────────────────────────────┐
│                    Plan B: CAS                          │
├─────────────────────────────────────────────────────────┤
│  1. 每次更新讀取當前 version                            │
│  2. 更新時 compare version，匹配才 swap                 │
│  3. 若版本衝突，自動重試直到成功                         │
│  4. 完全不需要 lock                                    │
└─────────────────────────────────────────────────────────┘

實作方式

需要新增 version 欄位到每個 memory entry：

interface MemoryEntry {
  // ... existing fields ...
  version: number;  // 新增：用於 CAS
}

更新流程：

async function atomicUpdate(id, expectedVersion, newData) {
  const record = await store.get(id);
  
  if (record.version !== expectedVersion) {
    // 版本衝突，重試
    return { success: false, conflictVersion: record.version };
  }
  
  // 版本匹配，更新並遞增版本號
  await store.update(id, {
    ...newData,
    version: record.version + 1,
  });
  
  return { success: true };
}

優點

優點	說明
✅ 完全無鎖	可並發執行，無 lock contention
✅ 適合分散式	多 Gateway 實例可同時運行
✅ 自動序列化	版本衝突時自動重試，最終一致
✅ 無 long operation	每個 operation 都是 O(1) lock 時間

缺點

缺點	說明
❌ 需要 schema migration	所有現有 entry 需要加 version 欄位
❌ 需要 store API 改動	需要修改 store.update() 支援 version
❌ 高並發時可能重試多次	conflict → retry → conflict → retry
❌ 複雜度增加	需要處理重試邏輯

適用場景

• 多 Gateway 實例同時運行：每個實例無需協調即可並發更新
• 需要嚴格的最終一致性：CAS 提供更強的一致性保證
• 大規模升級：1000+ entries 的批量升級

---

📊 Plan A vs Plan B 比較

特性	Plan A (已實作)	Plan B (本 issue)
Lock 次數	1 per batch	0 (無鎖)
Schema 改動	無	需要加 version
API 改動	無	修改 store.update()
實作複雜度	中等	較高
適用場景	單一 Gateway	多 Gateway 實例
遷移成本	無	需要 migration script

---

🎯 預期效益

實作 Plan B 後：

1. 完全消除 lock contention：Plugin 和 Upgrade CLI 可真正並發運行
2. 支援多實例：多個 Gateway 可同時執行升級
3. 更好的擴展性：從 O(batch_size) lock time → O(1) lock time

---

🔄 實作步驟建議

1. 新增 version 欄位到 MemoryEntry schema
2. 實作 migration script：為所有現有 entry 加入 version: 1
3. 修改 store.update() 支援 version check
4. 新增 store.atomicUpdate() API
5. 更新 memory-upgrader.ts 使用 atomicUpdate

---

⏰ 優先級

低 — Plan A 已經解決主要問題。Plan B 適合做為未來優化或當需要支援多 Gateway 實例時再實作。

[AliceLJY]

感谢提案。CAS 方向是对的，但当前优先级确实建议压低，理由如下：

Plan A（PR #639）先落稳观察

PR #639 的两阶段处理已经把 lock 次数从 N（每 entry 一次）→ 1（每 batch 一次），对单 Gateway 场景是量级改善。建议：

1. 先合 PR fix: two-phase processing to reduce lock contention (Issue #632) #639
2. 生产跑 2-3 周
3. 看残留 lock contention 是否还明显影响到实际场景
4. 如果"batch 级 lock"仍有问题 → 再决定是否上 CAS

CAS 的成本不只是代码

你列的优缺点很完整，补充几个实施层面的隐性成本：

成本	量级
Schema migration（所有现有 entry 加 version）	需要 upgrade CLI 支持 + 老用户升级流程
store.update() API 签名变更	外部调用方（tools.ts / upgrader / auto-capture）全部要跟进
重试风暴处理	高并发时 conflict → retry → conflict → retry 循环，需要 backoff 策略 + max retry cap，否则 CAS 可能比 lock 更慢
测试复杂度	需要构造 conflict 场景 + 验证 eventual consistency，单元测试成本高于 lock 路径

多 Gateway 场景是关键判断

CAS 的最大 ROI 是 "多 Gateway 实例并发写同一 memory 库"。目前：

• 项目没有官方推荐的多 Gateway 部署模式
• 多 Gateway 需要 shared LanceDB storage（网络文件系统或分布式 blob store），这个架构 @win4r 那边没有明确表态是否支持

如果长期保持"单 Gateway 单机本地 LanceDB"部署模式，CAS 的收益就只剩 "upgrade CLI 和 plugin 并发" 这一个场景，而这个场景 Plan A 已经缓解。

建议动作

• 本 issue 保留为 design discussion，标 low-priority / future-work
• 不立即实施
• Plan A 稳定后 + 有明确的多 Gateway 需求 → 再启动 Plan B

@win4r / @rwmjhb 如果对多 Gateway 路线有别的判断，欢迎推翻上述。