Design Instacart

Design Instacart

Requirements

Functional requirements

  • Inventory management like instacart

  • Make sure we don’t overshop

  • Shipment coming in

  • Browse, add to cart, at the same time update availability, no over selling

Non-functional requirements

  • Availability

  • High throughput

  • Service reliability

Out of scope

  • No payment, shipment

High-level overview

API design

  • addToCart(cartId, itemId, timestamp)

  • removeItemFromCart(cartId, itemId)

  • checkout(userId, cartId)

Database Design

  • select relational db

  • inventory table

  • cart table

  • order table

Detailed Design

Ref: 高并发下防止库存超卖的解决方案

Ref: 实战高并发秒杀实现（2）：防止库存超卖问题（超详细）

  • 产生超卖的原因：

    • 在高并发场景下，如果有两个线程 a, b，同时查询到商品库存为 1，他们都认为库存（stockCount）充足，于是开始下单减库存。

    • 如果线程 a 先完成减库存操作，库存为 0；

    • 如果线程 b 也减库存，于是库存就变成了 -1，超卖了！

// 1. 查询出商品库存信息
select stockCount from inventory where itemId = 1;
// 2. 根据商品信息生成订单
insert into order(orderId, itemId) values (null, 1);
// 3 .修改商品库存
update inventory set stockCount = stockCount - 1 where itemId = 1

Pessimistic Concurrency Control (悲观锁 PCC)

  • pessimistic locking model prevents simultaneous updates to records

  • as soon as one user starts to update a record, a lock is placed on it

  • other users must wait until the first user has finished committing their changes, thereby releasing the lock.

  • we use select...for update to add a lock on the record

// 0. 开始事务
begin;/begin work;/start transaction; (三者选一就可以)
// 1. 查询出商品信息，同时加锁
select stockCount from inventory where itemId = 1 for update;
// 2. 根据商品信息生成订单
insert into order(orderId, itemId) values (null, 1);
// 3. 修改商品 stockCount 减一
update inventory set stockCount = stockCount - 1 where itemId = 1;
//4.提交事务
commit;

  • Pro:

    • solve oversell in concurrent scenarios

  • Con:

    • performance issue: all following operation will be blocked

    • may causing dead lock

Optimistic concurrency control (乐观锁 - OCC)

  • doesn't use record locking, allow multiple users to attempt to update the same record without informing other users;

  • the record changes are validated only when the record is committed

  • if one user successfully updates the record, others' updates are informed that a conflict exists.

  • normally, it add a version

    • before update, note down the current version;

    • when commit the change, check if the version is modified.

// 1. 查询出商品信息
select stockCount, version_num from inventory where itemId = 1;
// 2. 根据商品信息生成订单
insert into order (orderId, itemId) values (null, 1);
// 3. 修改商品库存
update inventory set stockCount = stock - 1, version_num = version_num + 1 where itemId = 1, version_num = version_num;

  • 在并发的时候，如果线程 b 尝试修改商品库存的时候，发现 version 已经被线程 a 修改了，那么线程 b 执行 update 语句就不满足了，库存就不会超卖

  • Pro:

    • solve oversell in concurrent scenarios

  • Con:

    • only one thread can succeed, all others will fail -> bad customer experience

  • 优化：减少锁的颗粒度

// 修改商品库存时判断库存是否大于 0
update inventory set stockCount = stockCount - 1 where itemId = 1 and stockCount > 0;

Distributed Lock (分布式锁)

Redis 的 setnx 实现锁机制

  • 除了在数据库层面加锁，还可以通过内存中加锁，实现分布式锁。

  • 在 Redis 中设置一个锁，拿到锁的线程抢购成功，拿不到锁的抢购失败。

    • Redis 的 setnx 方法可以实现锁机制，key 不存在时创建，并设置 value，返回值为 1

    • key 存在时直接返回 0

    • 线程调用 setnx 方法成功返回 1 认为加锁成功，其他线程要等到当前线程业务操作完成释放锁后，才能再次调用 setnx 加锁成功

Long TIMEOUT_SECOUND = 120000L;

Jedis client = jedisPool.getResource();

// 线程设置 lock 锁成功
while(client.setnx("lock", String.valueOf(System.currentTimeMillis())) == 1) {
    Long lockTime = Long.valueOf(client.get("lock"));

    //持有锁超时后自动释放锁
    if (lockTime != null && System.currentTimeMillis() > lockTime+TIMEOUT_SECOUND) {

    client.del("lock");
    }

    Thread.sleep(10000);
}

......

......

client.del("lock");

  • Con:

    • 在高并发情况下，对数据库进行频繁操作，会造成严重的性能问题，所以我们必须在前端对请求进行限制

Redis 原子操作

  • 在 Redis 中食指一个队列， key 为 itemId，队列的长度为商品的 stockCount。

  • 每次请求到达时，pop 出一个元素。这样拿到元素的请求被认为秒杀成功；

  • 后续通过 MQ 发送消息异步完成数据库减库存操作；没有拿到元素的请求即认为秒杀失败；

  • 由于 Redis 是单线程，而 list 的 pop 操作是原子性的，因此并发的请求都被串行化 了，库存就不会超卖了。

// 获取商品库存
String token = redisTemplate.opsForList().leftPop(goodsStock);

if(token == null) {
    log.info(">>>商品已售空");
    return setResultError("亲，该秒杀已经售空，请下次再来!");
}

// 异步发送 MQ 消息，执行数据库操作
sendSecondKillMsg(itemId, userId);

.......

分布式锁的几种实现方式

distribution transaction：2pc

Saga Pattern

Saga distributed transactions pattern

TCC（try-confirm-cancel）

考官点评

  • expire cart：定时清理不付款的 shopping cart。

  • 某些 store 可以 sharding

  • 有大的格局，进行取舍，自己简化难点

  • transaction vs DB：通过计算，可能用 DB 直接就能做

  • Saga pattern： 看现在的 state 在哪儿，决定 roll forward 或者 roll back

    • Saga 是不保证 isolation 的

  • 2PC 是在数据层层面实现 distributed txn；saga 是在 micro service 层面实现 distributed txn

  • 考官举例

PreviousDesign Ads Logging SystemNextDesign a payment system

Last updated