Beyond the Basics: A Deep Dive into the CAP Theorem with Java Threads

Beyond the Basics: A Deep Dive into the CAP Theorem with Java Threads
Play this article

I have Discussed this a lot of people during design discussions, taking Interviews and have often seen lot of confusion related to CAP Theorem, So thought of explaining the CAP theorem using Code, as a legend once said 'Talk is Cheap, show me the Code'

CAP Theorem or Brewer Theorem Statement

In a distributed data store, you can only have two out of the following three guarantees across a write and read:

  • Consistency: A read is guaranteed to return the most recent write for a given client.

  • Availability: A non-failing node will return a reasonable response within a reasonable amount of time, without guarantee that it’s the most recent write.

  • Partition Tolerance: The system will continue to function when network partitions occur


Now let me first clear some terms or confusions which I generally encounter

Consistency has different definitions in ACID properties and CAP Theorem :

Consistency in ACID :

Ensures that a database transaction brings the database from one valid state to another, maintaining database invariants, meaning that certain data conditions (like unique keys, foreign keys, and check constraints) are maintained before and after the transaction. Consistency in this context is more about maintaining the integrity and correctness of the data following the execution of an operation or transaction.
Example: Consider a database for a school where students can enroll in courses. There's a rule that a course can only have up to 30 students.

BEGIN TRANSACTION;

-- Check available slots in the course
IF (SELECT COUNT(*) FROM Enrollments WHERE CourseID = 202) < 30 THEN
    INSERT INTO Enrollments (StudentID, CourseID) VALUES (1001, 202);
ELSE
    PRINT 'Course is full';
END IF;

COMMIT;

Consistency in CAP Theorem:

Consistency in the context of the CAP theorem ensures that all nodes in a distributed database system appear to be synchronized at all times. Every read request received by the system returns the value of the most recent write, making sure that there is no discrepancy in data regardless of which node is accessed.

Explanation with a Theoretical Scenario:

  • Assume a distributed database with multiple nodes (Node A, Node B, Node C).

  • A write operation occurs, modifying the data in Node A.

  • In a system that maintains consistency as per CAP theorem, this write operation is not considered "completed" until the data modification is successfully replicated to Nodes B and C.

  • If any read operation is made during this update from any node, the system ensures that it returns the value of the most recent completed write operation.

  • The goal is to make sure all nodes provide the same data output for read operations.


Now let me reframe the CAP Theorem in a more intutive manner

When Dealing with Distributed Databases, we can't avoid network failures, thus when a Partition happens and a Node is unable to communicate with other nodes, then we can either choose Consistency or Availability.


Now let me simulate this by Code

Build a Simpsons Quote-Bot withTwilio & Python | Pluralsight | Pluralsight

Intution : Threads as individual Node

First, let's create a Class which has attributes of a Node and perform the Operations which we would expect a DB Node to do

DatabaseNode Class

Attributes:

  • dataStore: A ConcurrentHashMap that acts as the local database for each node.

  • nodeId: A unique identifier for each node.

  • allNodes: A list containing references to all nodes in the system.

  • isActive: A boolean flag to indicate whether a node is active or not (simulating network partition).

Methods:

  • write(String key, String value): Performs a write operation on the node's local data store if the node is active.

  • read(String key): Performs a read operation from the node's local data store if the node is active and prints the read value.

  • deactivate(): Deactivates a node, simulating a node going offline or a network partition.

  • activate(): Activates a node, bringing it back online after a network partition is resolved.

  • run(): The method that will be executed when the thread is started. Custom behavior for each node can be added here.


import java.util.concurrent.*;

public class DistributedDatabaseDemo {

    static class DatabaseNode implements Runnable {
        private final ConcurrentHashMap<String, String> dataStore;
        private final String nodeId;
        private final CopyOnWriteArrayList<DatabaseNode> allNodes;
        private boolean isActive = true;

        public DatabaseNode(String nodeId, ConcurrentHashMap<String, String> dataStore, CopyOnWriteArrayList<DatabaseNode> allNodes) {
            this.nodeId = nodeId;
            this.dataStore = dataStore;
            this.allNodes = allNodes;
        }

        public void write(String key, String value) {
            if (isActive) {
                dataStore.put(key, value);
                System.out.println("Node " + nodeId + " wrote: " + key + " -> " + value + "\n");
            } else {
            System.out.println("Node isn't active");
            }
        }

        public void read(String key) {
            if (isActive) {
                String value = dataStore.get(key);
                System.out.println("Node " + nodeId + " read: " + key + " -> " + value + "\n");
            } else {
            System.out.println("Node isn't active");
            }
        }

        public void deactivate() {
            isActive = false;
            System.out.println("Node " + nodeId + " is now inactive.");
        }

        public void activate() {
            isActive = true;
            System.out.println("Node " + nodeId + " is now active.");
        }

        public boolean isActive() {
            return isActive;
        }

        @Override
        public void run() {
            // Custom behavior for each node can be added here.
        }

    }
}

Coordinator Class

  • Attributes

    • allNodes: A list containing references to all nodes in the system.

    • roundRobinIndex: An AtomicInteger to maintain the index for round-robin reads.

  • Methods

    • globalWrite(String key, String value)

      • Initiates a global write, making each node in the system write the data to its store.
    • roundRobinRead(String key)

      • Performs a read in a round-robin fashion from the nodes. It selects a node based on the roundRobinIndex, executes a read, and then increments the index.
    • areAllNodesActive()

      • Checks whether all nodes in the system are active and returns a boolean value.

static class Coordinator {
        private final CopyOnWriteArrayList<DatabaseNode> allNodes;
        private final AtomicInteger roundRobinIndex = new AtomicInteger(0);

        public Coordinator(CopyOnWriteArrayList<DatabaseNode> allNodes) {
            this.allNodes = allNodes;
        }

        public void globalWrite(String key, String value) {
            System.out.println("Coordinator initiating global write.");
            for (DatabaseNode node : allNodes) {
                node.write(key, value);
            }
        }

        public void roundRobinRead(String key) {
            int index = roundRobinIndex.getAndIncrement() % allNodes.size();
            DatabaseNode node = allNodes.get(index);
            node.read(key);
        }

        public boolean areAllNodesActive() {
            for (DatabaseNode node : allNodes) {
                if (!node.isActive()) {
                    return false;
                }
            }
            return true;
        }
    }

Let's simulate it in Main method now

public static void main(String[] args) throws InterruptedException {
    ConcurrentHashMap<String, String> dataStore = new ConcurrentHashMap<>();
    CopyOnWriteArrayList<DatabaseNode> allNodes = new CopyOnWriteArrayList<>();

    DatabaseNode node1 = new DatabaseNode("1", dataStore, allNodes);
    DatabaseNode node2 = new DatabaseNode("2", dataStore, allNodes);
    DatabaseNode node3 = new DatabaseNode("3", dataStore, allNodes);

    allNodes.add(node1);
    allNodes.add(node2);
    allNodes.add(node3);

    ExecutorService executorService = Executors.newFixedThreadPool(3);
    executorService.submit(node1);
    executorService.submit(node2);
    executorService.submit(node3);

    Coordinator coordinator = new Coordinator(allNodes);

    // Coordinator performs a global write
    coordinator.globalWrite("key1", "value1");

    //Performing Reads
    coordinator.roundRobinRead("key1");
    coordinator.roundRobinRead("key1");

    // Introducting Network Partition
    TimeUnit.SECONDS.sleep(2);
    System.out.println("Introducing network partition, making Node 3 inactive.");
    node3.deactivate();

    //////////////////////////////////////
    ////// Choosing Availability /////////
    //////////////////////////////////////
    coordinator.globalWrite("key2", "value2");
    coordinator.roundRobinRead("key2");

    TimeUnit.SECONDS.sleep(2);
    System.out.println("Resolving network partition, making Node 3 active again.");
    node3.activate();

    // Once we try to read the value from Node 3, we won't get it
    // as we Node 3 hasn't received the value yet
    coordinator.roundRobinRead("key2");
    coordinator.roundRobinRead("key2");
    coordinator.roundRobinRead("key2");    

    //////////////////////////////////////
    ////// Choosing Consistency //////////
    //////////////////////////////////////
    System.out.println("Introducing network partition, making Node 3 inactive.");
    node3.deactivate();

    if(!coordinator.areAllNodesActive()){
        System.out.println("DB facing Down Time");
    }
    // If we Chose Consistency then whenever we detect 
    // an unreachable node, we won't accept any write/read

    executorService.shutdown();
}

Output :


Now we've successfully Simulated the CAP Theorem using Threads :)

Family Guy GIF - Family Guy Stewie - Discover & Share GIFs