Credit Balance Service with Vector-Clock Expiries

You are designing a backend service that maintains per-user promotional credits. Credits are granted as independent buckets, each with an expiry time represented by a vector clock (no wall-clock time exists). Clients issue operations with an attached vector clock.

Implement the service and explain your design.

Operations

1. add(userId, creditId, amount, expiryVc)
   • Adds a credit bucket with a unique creditId, positive amount, and an expiry represented by a vector clock expiryVc.
2. use(userId, amount, atVc)
   • Spends credits at logical time atVc. The service must consume from credits that expire soonest first.
   • A credit is unavailable (expired) for this spend if expiryVc <= atVc under vector-clock partial order. Expired credits cannot be used.

Requirements

• Specify APIs (request/response, idempotency), core data structures, and algorithms to support efficient inserts and spends across many active credits per user.
• Define how you compare vector clocks (<=, <, ==, concurrent) and how you impose a deterministic total order among credits when expiries are partially ordered (concurrent). State tie-break policies.
• Describe safeguards against double-spend, against using expired credits, and how you handle identical expiries.
• Provide complexity analysis.
• Walk through test cases, including edge cases: concurrent expiries, expiry exactly at atVc, identical expiries, zero/negative amounts, insufficient balance.

Assumptions you may make:

• Vector clocks are maps from processId -> integer counter; missing components are treated as 0.
• The service processes operations per user on a single shard/actor (or uses equivalent transactional concurrency control) so that each user's operations are linearizable.