Ride-sharing platforms like Uber and Lyft face significant challenges in dynamically scheduling drivers and passengers in real-time across distributed servers. Your task is to design a distributed scheduling system that ensures:

• Scalability: The system must support millions of concurrent ride requests and driver availability updates.
• Consistency: No two drivers should be allocated the same ride, even under high churn conditions.
• Fault Tolerance: The system should handle network partitions gracefully without losing scheduling information.

The goal is to minimize ride allocation latency while maintaining strict fairness in driver-passenger assignments.

1. Background

Use the following distributed systems concepts to guide your solution:

• CAP Theorem: Trade-offs between consistency, availability, and partition tolerance.
• Time Synchronization: Techniques like Lamport Timestamps and Vector Clocks.
• Key-Value Stores: Distributed hash tables (DHTs), Cassandra’s partitioning strategies, and quorum-based operations.

2. Problem Statement

Design a ride allocation system using a distributed key-value store (e.g., Cassandra) for ride-sharing in a metropolitan area. Ensure the following:

• Unique Ride Assignments: Each ride request must be uniquely assigned to one driver.
• Real-Time Updates: Drivers and passengers update their statuses frequently.
• Eventual Consistency: Allow for eventual synchronization of data after network partitions resolve.
• Fair Load Balancing: Distribute requests across drivers evenly based on geographic proximity.

3. Instructions

Follow these steps:

1. Partitioning: Design a partitioning strategy to assign ride requests and drivers to servers. Use hashing or geographic sharding.
2. Conflict Resolution: Implement a conflict-free replicated data type (CRDT) to resolve conflicts in driver assignments.
3. Time Order: Use Vector Clocks to ensure causality in updates when multiple servers update driver statuses concurrently.
4. Replication: Configure replication strategies to tolerate server failures while ensuring strong eventual consistency.
5. Testing: Simulate network partitions and churn (e.g., drivers frequently entering/exiting the network) and evaluate system performance.

4. Deliverables

Your submission should include:

• Design Document: A detailed explanation of your system architecture, including diagrams.
• Implementation Code: Use Python with libraries like `boto3` for distributed simulation.
• Performance Metrics: Measure latency, throughput, and consistency under simulated conditions.
• Conflict Resolution Demo: Demonstrate how your system resolves conflicting ride assignments in a simulated partition scenario.

5. Evaluation Criteria

Your solution will be evaluated based on:

• Novelty: Use of advanced distributed systems techniques.
• Scalability: Ability to handle large-scale data and churn.
• Efficiency: Minimal latency for ride allocation.
• Fault Tolerance: Recovery from simulated network failures.

1. Architecture Design

The system architecture involves:

• Distributed Key-Value Store: Use Cassandra for storing ride requests and driver availability. Data is partitioned using a geohashing scheme to minimize latency by keeping geographically close data together.
• Replication: Set a replication factor of 3 for fault tolerance. Consistency levels like QUORUM ensure strong eventual consistency while maintaining availability.

2. Partitioning

Partition rides and drivers based on geographic regions:

• Use a geohashing technique to divide the city into regions. Each region is mapped to a Cassandra partition.
• Store each ride request with keys formatted as `:`, and driver availability as `:`.

3. Conflict-Free Assignments

To prevent multiple drivers being assigned to the same ride:

• Use a CRDT (Conflict-Free Replicated Data Type): A grow-only set (G-Set) to track ride-driver assignments.
• When multiple servers propose assignments for the same ride, CRDT ensures convergence by selecting the first proposal based on timestamps.

4. Causal Ordering

Use Vector Clocks to handle concurrency in updates:

• Each server maintains a vector clock for its region. Updates to driver status or ride requests carry the vector timestamp.
• Upon receiving an update, servers merge vector clocks to determine causality.

def merge_vector_clocks(vc1, vc2):
    return {k: max(vc1.get(k, 0), vc2.get(k, 0)) for k in set(vc1) | set(vc2)}

5. Fault Tolerance and Recovery

Implement fault-tolerant features:

• Hinted Handoff: Ensure writes succeed even when replicas are unavailable by buffering them at the coordinator node.
• Read Repair: During reads, resolve inconsistencies across replicas using the latest vector clock.

6. Load Balancing

To balance load among drivers:

• Use a weighted round-robin algorithm within each region to assign rides to drivers based on their distance and availability.

7. Testing and Simulation

Simulate the system with high churn and network partitions:

• Use Python's `concurrent.futures` to simulate driver updates and ride requests across multiple threads representing servers.
• Log latency, throughput, and error rates during partition scenarios.

import concurrent.futures
import time
import random

def simulate_ride_request(region, ride_id):
    time.sleep(random.uniform(0.1, 0.5))
    print(f"Ride {ride_id} requested in region {region}")

with concurrent.futures.ThreadPoolExecutor() as executor:
    regions = ["R1", "R2", "R3"]
    for i in range(10):
        executor.submit(simulate_ride_request, random.choice(regions), i)

Performance Evaluation

Analyze the following metrics:

• Average latency for ride assignments under normal and partitioned conditions.
• Consistency check: Validate correctness of ride-driver assignments across replicas after partitions resolve.
• Load distribution among drivers in each region.