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

itemID	sku	price	count	ttl
13844	AXD-356	98.99	10000	135464

• cart table

cartId	userId	orderId
123	218	45435843

• order table

orderId	itemId	count
218	456468	2
218	456469	3
-----------

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

• 考官举例