Shopping Lists on the Cloud

A Local-First, Highly Available Distributed System

Project Overview

This project implements a distributed inventory management system designed around Local-First principles. It ensures that user data is always accessible, fully functional offline, and seamlessly synchronized across devices using eventually consistent models.

The system balances local autonomy with global consistency, ensuring that the device remains the primary source of truth while the cloud acts as a coordination layer.

TODO

• Due to the change in the crdt merge at last hour, adding replica id's the delete of an item must be handle other way. The items need to be marked as deleted then when crdt_merging if the other list has that item it will be marked as deleted as well, this way we won't loose the knowledge that item doens't exist. This cloud lead to problems when creating another item so we cloud handle that with timestamps.

Compile Project

bash

git clone --recurse-submodules -j8 https://github.com/CarlosSanchess/ShoppingLists
cd /src
make

Then you can run the broker, the client and how many workers/nodes you want.

Core Requirements & Vision

• Local-First: Full functionality completely offline. All edits happen locally first with zero network dependency for core features.
• High Availability: Always accessible regardless of network status or server availability.
• Eventual Consistency: All devices converge to the same state automatically using Conflict-Free Replicated Data Types (CRDTs).
• Scalability: Supports massive scale (millions of users) via Dynamo-style partitioning.
• Security: End-to-end encryption principles where the cloud coordinates synchronization without accessing content.

Technology Stack

• Language: C (Backend & Frontend)
• Communication: ZeroMQ (CZMQ High-level C Binding)
• Serialization: CJson
• GUI: Raylib (Optional)

System Architecture

1. Communication Layer (ZeroMQ)

The system uses a Client-Broker-Worker topology with specific ZeroMQ socket patterns for distributed coordination:

• Broker:
  • ROUTER Socket: Receives lists from clients and forwards them to the appropriate worker; receives merged lists from workers.
  • PUB Socket: Publishes updated lists to subscribing clients.
• Worker:
  • DEALER Socket: Receives lists for processing and storage logic.
• Client:
  • SUB Socket: Subscribes to specific topics (current list) for real-time updates.
  • REQ Socket: Connects to the broker for remote synchronization.

2. Data Model: CRDTs

To manage concurrent writes and ensure consistency without locks, the system treats shopping lists as State-based CRDTs.

Structure: PN-Counter Pairs Items use Positive-Negative (PN) Counters to track quantities (acquired vs. goal).

• Value Calculation: sum(increments) - sum(decrements)
• Merge Logic: The merge operation is idempotent, commutative, and associative.
  • Merge(A, B) = max(A.inc, B.inc), max(A.dec, B.dec)

Data Structures (C Implementation):

typedef struct {
    char CRDT_PNCounter_ID[64];
    CRDT_PNCounter acquired_quantity;
    CRDT_PNCounter goal_quantity;
} CRDT_PNCounter_Pair;

typedef struct {
    char name[MAX_NAME_SIZE];
    CRDT_PNCounter_Pair **counters_array;
    size_t no_crdt_pairs;
    time_t last_modified;
} Item;

3. Data Partitioning (Dynamo Style)

The system solves the "DHT Challenge" (Mapping, Dynamism, Routing, Distribution) using a Consistent Hashing Ring.

• Ring Hashing: A ring buffer with a fixed number of slots.
• Virtual Nodes: Physical nodes are assigned multiple "virtual nodes" dispersed randomly around the ring to prevent hotspots and ensure even load distribution (e.g., Node A handles slots 0, 10, 20).
• Mapping: Hash(List_ID) % N_Slots determines the target node.

4. Fault Tolerance

To handle node failures without data loss, the system implements a Successor Replication Strategy:

• Data is stored on the primary node responsible for the slot.
• Data is immediately replicated to successor nodes in the ring.
• Failover: If a node fails, the successor node holding the replica immediately serves the request, ensuring high availability and zero reconfiguration downtime.