Build a Distributed Shopping Cart with CRDTs - The Counter

                      TASK
                    

Implementation

A distributed shopping cart demonstrates CRDTs solving a real-world problem. Using an OR-Set, items can be added and removed from the cart across partitioned nodes, and the cart always converges after healing.

Cart operations:

add_item(item_id, qty): add an item with a quantity (uses OR-Set add with unique tag)
remove_item(item_id): remove all observed entries for the item
view_cart(): return all items in the cart with quantities

Partition scenario:

Nodes A and B are partitioned
User on A adds "milk" to cart
User on B removes "bread" from cart
Partition heals, nodes merge
Result: cart has milk (added on A), no bread (removed on B), plus any pre-existing items

Request:  {"type": "cart_add", "msg_id": 1, "item": "milk", "qty": 2}
Response: {"type": "cart_add_ok", "in_reply_to": 1, "cart_size": 1}

Request:  {"type": "cart_view", "msg_id": 2}
Response: {"type": "cart_view_ok", "in_reply_to": 2, "items": [{"item": "milk", "qty": 2}, {"item": "bread", "qty": 1}], "total_items": 2}

Sample Test Cases

Add items to cartTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"cart_add","msg_id":2,"item":"milk","qty":2}}
{"src":"c1","dest":"n1","body":{"type":"cart_add","msg_id":3,"item":"bread","qty":1}}
{"src":"c1","dest":"n1","body":{"type":"cart_view","msg_id":4}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Remove item from cartTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"cart_add","msg_id":2,"item":"eggs","qty":12}}
{"src":"c1","dest":"n1","body":{"type":"cart_remove","msg_id":3,"item":"eggs"}}
{"src":"c1","dest":"n1","body":{"type":"cart_view","msg_id":4}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Model the cart as an OR-Set of (item_id, quantity) pairs

Hint 2▾

Add item: or_set.add((item_id, quantity))

Hint 3▾

Remove item: or_set.remove(item_id) removes all observed entries for that item

Hint 4▾

Under partition, both sides can add/remove independently — cart stays available

Hint 5▾

After partition heals, merge: add-wins semantics resolve conflicts

Resources

Dynamo Shopping Cart

Amazon Dynamo paper - shopping cart as a motivating use case for CRDTs

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

shopping cartOR-Set applicationpartition toleranceadd-remove conflictconvergence

main.py

python