Parallel Computing and Scaling of Systems — Juspay Preparation Guide

This guide synthesizes the critical concepts of parallel computing, multithreading, and system scaling required for Juspay's Hackathon Part B and System Interviews.

1. Multithreading & Parallel Computing Fundamentals

Process vs. Thread

Process: An independent program in execution with its own memory space (Code, Data, Heap, Stack). Processes communicate via IPC (Pipes, Shared Memory, Message Queues).
Thread: The smallest unit of execution within a process. Threads share the process's memory (Code, Data, Heap) but have their own Stack and Registers.
Context Switching: The OS saves the state (registers, program counter) of the currently running thread/process and loads the state of the next one. Thread context switching is faster than process context switching due to shared memory space.

Multicore vs. Single Core Processors

Single Core (Concurrency): The CPU rapidly switches between threads (time-slicing), creating the illusion of parallel execution.
Multicore (True Parallelism): Multiple threads execute simultaneously on different physical cores.
Cache Coherence: In multicore systems, each core has its own cache (L1/L2). The MESI Protocol (Modified, Exclusive, Shared, Invalid) ensures all cores see a consistent view of shared memory.
Amdahl's Law: The theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved. It limits maximum speedup based on the strictly sequential portion of the code.

2. Concurrency Problems & Race Conditions

In Juspay's Hackathon Part B, you must manually identify and solve race conditions.

Race Conditions

Occur when two or more threads access shared data and try to change it simultaneously. The final state depends on thread execution timing.

Classic Example (Tree of Space): Two threads trying to lock the same node.
- Thread A reads isLocked = false.
- Thread B reads isLocked = false.
- Thread A sets isLocked = true.
- Thread B sets isLocked = true. (Both succeed incorrectly).
Lost Update: Two threads incrementing a shared ancestor's descendantsLocked counter simultaneously. Both read 0 and write 1, instead of the expected 2.

Deadlocks

A state where threads are blocked forever, waiting for each other to release resources. Four Necessary Conditions:

Mutual Exclusion: At least one resource must be non-shareable.
Hold and Wait: A thread holds a resource while waiting for another.
No Preemption: Resources cannot be forcibly taken from a thread.
Circular Wait: Thread A waits for B, B waits for C, C waits for A.

Prevention in Tree of Space:

Lock Ordering: Always acquire locks in a consistent order (e.g., from leaf to root). This breaks the Circular Wait condition.

Other Issues

Livelock: Threads keep changing states in response to each other without making progress.
Starvation: A thread never gets CPU time or resources due to priority policies.

3. Concurrency Control Mechanisms (Building from Scratch)

Juspay often bans standard std::mutex or synchronized keywords. You must implement locking logically or using hardware primitives.

Why Naive Locking Fails

Coarse-Grained Locking: Wrapping the entire data structure in a single mutex kills parallelism. Siblings (e.g., China and India) should not block each other.
Fine-Grained Locking: Assigning a lock to each node. Requires careful management (Lock Ordering) to avoid deadlocks.

Building Your Own Mutex (Test-And-Set)

Using compiler atomic intrinsics to build a Spin Lock.

class Mutex {
private:
    // volatile ensures reads/writes go to main memory, preventing compiler caching
    volatile int isLocked = 0; 
public:
    void lock() {
        // Atomic Check-and-Set: returns the old value and sets to 1
        while (__sync_lock_test_and_set(&isLocked, 1) == 1) {
            // Spin-wait (busy loop) until lock is released
        }
    }
    void unlock() {
        __sync_lock_release(&isLocked);
    }
};

Advanced Atomic Operations

Compare-And-Swap (CAS): Atomically compares a variable to an expected value, and if they match, sets it to a new value.
Fetch-And-Add: Atomically increments a counter (e.g., __sync_fetch_and_add(&count, 1)). Useful for safely updating descendantsLocked counters without a mutex.

Read-Write (Shared vs. Exclusive) Locks

Shared Lock: Multiple threads can hold it (for reading).
Exclusive Lock: Only one thread can hold it (for writing/modifying). Blocks readers and writers.

4. System Scaling & High-Level Design

Scaling principles required for the System & Cultural Interview:

Idempotency (Critical for Payments)

An operation is idempotent if executing it multiple times yields the same result as executing it once.

Payment Gateway Example: A user clicks "Pay" twice due to lag. The system must use an Idempotency Key to ensure the transaction is processed only once, preventing double charging.

Distributed Session Management

Differentiating tabs on a laptop: Browser uses unique Socket Connections or Tab-specific tokens.
Differentiating laptops on the same Wi-Fi: They share a Public IP (NAT), but the server distinguishes them using unique Source Ports or Session Cookies.
Differentiating separate networks: Distinct Public IPs.
Scaling State: In a multi-node backend, sessions must be stateless (e.g., JWT) or stored in a centralized cache (e.g., Redis).

Database Scaling

ACID Properties: Atomicity, Consistency, Isolation, Durability.
Isolation Levels:
- Read Uncommitted
- Read Committed
- Repeatable Read
- Serializable (Prevents all concurrency anomalies but limits scaling).
Indexing: Speeds up reads (B-Trees) but slows down writes (index must be updated).
SQL vs. NoSQL: Choosing between relational integrity and distributed scale.

Load Balancing & Caching

Load Balancing: Distributing traffic across multiple servers to ensure reliability.
Caching: Using Redis/Memcached to store frequently accessed data, reducing database hits.
Rate Limiting: Algorithms like Token Bucket, Leaky Bucket, and Sliding Window protect the system from DDoS and abuse.

study_guide.md