Low level design : Inventory Management System of an e-commerce website
Problem Statement: https://codezym.com/question/4
Inventory is number of items of a particular product a seller has in their warehouse for selling to customers. e.g. 100 pieces of Boat stone 650 bluetooth speaker.
An inventory management system manages product listings, sellers and inventory i.e. item count of each product a seller is selling.
Here we are discussing about an e-commerce website like Amazon, Flipkart etc where there are multiple sellers selling the same product and customer can order the product from any seller.
Primary use-case :
Customers create order for a particular product,
createOrder(String orderId, String destinationPincode, String sellerId, String productId, int itemCount)Customers also fetch list of sellers which can deliver a particular product to a particular pincode and have atleast
itemCountpieces of the product, whereitemCountis the number of items customer wishes to order, e.g. two blue t-shirts.getSellers(String productId, int itemCount, String destinationPincode)
The data which is getting changed and fetched simultaneously using multiple threads is
itemCount, when user creates order or seller adds inventory.Our solution will be built around store and access of
itemCount.
Other use-cases:
createSeller(String sellerId, List serviceablePincodes, List paymentModes);createProduct(String productId, String name, double price);String addInventory(String productId, String sellerId, int delta);int getInventory(String productId, String sellerId);
Storing critical data itemCount :
Lets start with a basic data structure:
Map<productId, Map<sellerId, itemCount>> productInventory
Above map keeps list of sellers who are selling a particular product. But we also need the number of items of that product seller has in their warehouse. Hence we used a map Map<sellerId, itemCount> instead of a list.
We need our data structure to be thread safe and efficient at the same time, so the final data structure will be :
ConcurrentHashMap<String, ConcurrentHashMap<String, AtomicInteger>> productInventory
Basically, map changed to ConcurrentHashMap and instead of itemCount we are using a AtomicInteger, we could have done with a integer also.
Above data structure can easily support both of our primary use-cases:
1. createOrder(String orderId, String destinationPincode, String sellerId, String productId, int itemCount)
AtomicInteger items = productInventory.get(productId).get(sellerId);
if(items==null) return false;
while (true) {
int currentValue = items.get();
if (currentValue <delta) break;
// reduce inventory on createOrder
if(items.compareAndSet(currentValue, currentValue - delta)) return true;
}
2. List getSellers(String productId, int itemCount, String destinationPincode, String paymentMode);
ArrayList<String> getSellers(String productId, int itemCount,
String destinationPincode, String paymentType){
ArrayList<String> sellers = new ArrayList<>();
ConcurrentHashMap<String, AtomicInteger> map = productInventory.get(productId);
if(map==null) return sellers;
for(String sellerId: map.keySet()){
Seller seller = sellerManager.getSeller(sellerId);
if(seller==null || !seller.servesPincode(destinationPincode)
|| !seller.supportsPaymentType(paymentType)) continue;
if(map.getOrDefault(sellerId, new AtomicInteger(-1)).get()>=itemCount)
sellers.add(sellerId);
}
sellers.sort(Comparator.naturalOrder());
return sellers;
}
Alternate data structures to store itemCount :
We could have also used a list in place of inner map Map<sellerId, itemCount>
ConcurrentHashMap<String, ArrayList<SellerInventory> productInventory
class SellerInventory{ String sellerId; AtomicInteger itemCount; }
Even this would be thread safe and yet efficient.
If you agree or disagree with either of above data structures then jump into comments and start a discussion.
One could also say why not use a simple hashmap and protect it with synchronized keyword or protect it with ReentrantReadWriteLock i.e. HashMap<String, HashMap<String, AtomicInteger>> productInventory
Above will work but it will be inefficient because at a time out of thousands of products with each product getting sold by 10's or even 100's of sellers only one thread is able to update inventory at a time and rest are locked out.
ConcurrentHashMap inside a ConcurrentHashMap or List with AtomicInteger inside a ConcurrentHashMap gives us two levels of parallelism which increases the number of threads that can update or read at a time. This comes at the cost of extra space but it is more efficient in a multithreaded environment.
Complete Code :
You can run and test below code on CodeZym: https://codezym.com/question/4
Whole functionality is divided into two classes
ProductManagerandSellerManager, which stores details about products and sellers respectively.ProductManagerclass keeps tract of actual inventory, i.e. the data structure we discussed above.Class
Sellerand ClassProducthold the actual data, consider them like rows of a database.
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
* - All the methods of this class will be tested in
* a MULTI-THREADED environment.
* - If you are creating new interfaces, then they have to be declared on the top, even before class Solution, else it will give class not found error
* - use helper.print("") or helper.println("") for printing logs else logs will not be visible.
*/
public class Solution implements Q04EcommerceOrdersInterface {
Helper04 helper;
SellerManager sellerManager = new SellerManager();
ProductManager productManager = new ProductManager();
// constructor must always be public, don't remove the public keyword
public Solution(){}
public void init(Helper04 helper){
this.helper=helper;
// helper.println("Ecommerce orders module initialized");
}
/**
* creates a new seller (who sells products on website).
* - each seller sells many products and multiple sellers can sell the product with same productId
* @param sellerId it will always be a non null, non blank unique string
* @param serviceablePincodes list of pincodes where seller can deliver products
* @param paymentModes it wil be always one of cash, upi, netbanking, debit card and credit card
*/
public void createSeller(String sellerId, List<String> serviceablePincodes,
List<String> paymentModes) {
sellerManager.createSeller(sellerId, serviceablePincodes, paymentModes);
}
/**
* - Creates a product. Multiple sellers can sell the same product.
* - For simplicity lets assume that each item will have same price
* - once a product is created, inventory for the same will be added by differet seller who will be selling that item.
* @param productId it will always be a non null, non blank, unique string
* @param name e.g boAt stone 650 bluetooth speaker
* @param price price of item e.g. 1599
*/
public void createProduct(String productId, String name, double price) {
productManager.createProduct(productId, name, price);
}
/**
* seller adds multiple items of a product for selling. e.g 50 grey pure cotton shirts.
* @param delta number of items seller is adding e.g. 50 . It will always be a positive integer.
* @return returns "inventory added", "product doesn't exist", "seller doesn't exist"
*/
public String addInventory(String productId, String sellerId, int delta) {
if(sellerManager.getSeller(sellerId)==null)
return "seller doesn't exist";
if(productManager.getProduct(productId)==null)
return "product doesn't exist";
return productManager.addInventory(productId, sellerId, delta);
// return "inventory added";
}
/**
* @return returns the number of items left for a product from a given seller,
* if the product or seller doesn't exist then returns 0
*/
public int getInventory(String productId, String sellerId) {
return productManager.getInventory(productId, sellerId);
}
/**
* creates order with order id
* - buyer will choose both product and seller who will deliver the product and create an order.
* - For simplicity lets assume that at this time only one product (1 or more counts) is purchased in a single order.
* @param orderId it will always be a non null, non blank, unique string
* @param productCount it will always be a positive integer
* @param paymentMode it wil always be one of cash, upi, netbanking, debit card and credit card
* @return returns (in that order) : "order placed" or "product doesn't exist" or "buyer doesn't exist" or "seller doesn't exist" or "pincode unserviceable" or "payment mode not supported" or "insufficient product inventory"
*/
public String createOrder(String orderId, String destinationPincode,
String sellerId, String productId,
int productCount, String paymentMode) {
Product product = productManager.getProduct(productId);
if(product==null) return "product doesn't exist";
Seller seller = sellerManager.getSeller(sellerId);
if(seller==null) return "seller doesn't exist";
if(!seller.servesPincode(destinationPincode))
return "pincode unserviceable";
if(!seller.supportsPaymentType(paymentMode))
return "payment mode not supported";
boolean reduced = productManager.reduceInventory(
productId, sellerId, productCount);
return reduced ? "order placed": "insufficient product inventory";
}
/**
* returns list of all sellers sorted by sellerId in ascending order, which have >=itemCount pieces of the product with productId and also deliver to destinationPincode.
* @param productId product which needs to be checked for purchase
* @param itemCount number of items that we wish to check for, always be a positive integer
* @param destinationPincode pincode of buyer where product needs to be delivered.
*/
public List<String> getSellers(String productId, int itemCount, String destinationPincode, String paymentType) {
ArrayList<String> sellers = productManager.getSellers(
productId, itemCount, destinationPincode,
paymentType, sellerManager);
sellers.sort(Comparator.naturalOrder());
return sellers;
}
}
class Seller {
private HashSet<String> serviceablePincodes = new HashSet<>();
private HashSet<String> sellerPaymentModes = new HashSet<>();
Seller(List<String> serviceablePincodes, List<String> sellerPaymentModes){
this.serviceablePincodes.addAll(serviceablePincodes);
this.sellerPaymentModes.addAll(sellerPaymentModes);
}
boolean servesPincode(String pincode){
return pincode!=null && serviceablePincodes.contains(pincode);
}
boolean supportsPaymentType(String paymentType){
return paymentType!=null && sellerPaymentModes.contains(paymentType);
}
}
class SellerManager{
// sellerId vs serviceable pincodes
ConcurrentHashMap<String, Seller> sellers = new ConcurrentHashMap<>();
/**
* creates a new seller (who sells products on website).
* - each seller sells many products and multiple sellers can sell the product with same productId
* @param serviceablePincodes list of pincodes where seller can deliver products
* @param paymentModes it wil be always one of cash, upi, netbanking, debit card and credit card
*/
public void createSeller(String sellerId, List<String> serviceablePincodes, List<String> paymentModes) {
sellers.put(sellerId, new Seller(serviceablePincodes, paymentModes));
}
public Seller getSeller(String sellerId){
return sellers.get(sellerId);
}
}
class Product {
String productId, name;
double price;
Product(String productId, String name, double price){
this.productId=productId;
this.name=name;
this.price=price;
}
public double getPrice() {
return price;
}
}
class ProductManager {
ConcurrentHashMap<String, Product> products = new ConcurrentHashMap<>();
/** productId's vs sellerId of sellers who are selling the product vs productCount
* - high level of concurrent read and write operations on different keys so used nested concurrent hashmaps so that in case of many threads locking is more fine-grained and reduces contention.
* - if search was a major use case then would have used a single map with productId_sellerId as key
*/
ConcurrentHashMap<String, ConcurrentHashMap<String, AtomicInteger>> productInventory = new ConcurrentHashMap<>();
// HashMap<String, ConcurrentHashMap<String, AtomicInteger>> productInventory = new HashMap<>();
public void createProduct(String productId, String name, double price) {
products.put(productId, new Product(productId, name, price));
}
public Product getProduct(String productId){
if(productId==null) return null;
return products.get(productId);
}
/**
* seller adds multiple items of a product for selling. e.g 50 grey pure cotton shirts.
* @param delta number of items seller is adding e.g. 50 . It will always be a positive integer.
* @return returns "inventory added", "product doesn't exist"
*/
public String addInventory(String productId, String sellerId, int delta) {
productInventory.putIfAbsent(productId, new ConcurrentHashMap<>());
ConcurrentHashMap<String, AtomicInteger> inventory =
productInventory.get(productId);
inventory.putIfAbsent(sellerId, new AtomicInteger(0));
inventory.get(sellerId).addAndGet(delta);
return "inventory added";
}
/** adds -delta to inventory, returns true if successful
* false return means either the item doesn't exist
* or existing productCount is less than delta
*/
public Boolean reduceInventory(String productId, String sellerId, int delta) {
AtomicInteger items = getInventoryInternal(productId, sellerId);
if(items==null) return false;
while (true) {
int currentValue = items.get();
if (currentValue <delta) break;
if(items.compareAndSet(currentValue, currentValue - delta))
return true;
}
return false;
}
private AtomicInteger getInventoryInternal(
String productId, String sellerId){
ConcurrentHashMap<String, AtomicInteger> inventory = productInventory.get(productId);
if(inventory==null) return null;
return inventory.get(sellerId);
}
public int getInventory(String productId, String sellerId){
AtomicInteger inventory = getInventoryInternal(productId, sellerId);
return inventory==null?0:inventory.get();
}
// return all sellers who have product with enough inventory to satisfy the order
ArrayList<String> getSellers(String productId, int itemCount,
String destinationPincode, String paymentType,
SellerManager sellerManager){
ArrayList<String> sellers = new ArrayList<>();
ConcurrentHashMap<String, AtomicInteger> map = productInventory.get(productId);
if(map==null) return sellers;
for(String sellerId: map.keySet()){
Seller seller = sellerManager.getSeller(sellerId);
if(seller==null || !seller.servesPincode(destinationPincode)
|| !seller.supportsPaymentType(paymentType)) continue;
if(map.getOrDefault(sellerId, new AtomicInteger(-1)).get()>=itemCount)
sellers.add(sellerId);
}
return sellers;
}
}