Day 1: Compile and Run Java Code via Command Line to Build an Array-Backed Key-Value Store

Modern software development is insulated by layers of build tools, integrated development environments (IDEs), and heavy frameworks. While these abstractions accelerate initial development, they obscure the physical realities of the Java Virtual Machine (JVM) and the underlying operating system. When a high-throughput, low-latency system like a database encounters performance degradation, an engineer who only knows how to click a green play button in an IDE is left defenseless.

To build AstraKV—a high-performance, distributed key-value store—we must start at the bare metal. We begin by stripping away Maven, Gradle, and IntelliJ. We will author, compile, and run our code using only raw JDK command-line tools. We will implement our initial state container using a simple, array-backed sequential layout, exposing the fundamental trade-offs of JVM memory organization, pointer chasing, and $O(N)$ lookup complexity.

The Continuity Contract

Starting Point:</strong> This is Day 1 of the AstraKV series. We begin with zero dependencies, a clean directory structure, and a raw terminal.
<strong style="color: #1e293b; font-weight: 700;">Target State for Day 2: Today we will build a working, memory-bounded, array-backed key-value store. This implementation will suffer from $O(N)$ lookup times and key collision vulnerabilities. On Day 2, we will replace this linear scan engine with a custom-engineered Chained Hash Map to achieve $O(1)$ lookups without relying on Java's built-in java.util.HashMap.

Production Stakes: The Cost of Pointer Chasing

In 2010, early deployments of Apache Cassandra encountered severe performance degradation and unpredictable latency spikes. The primary culprit was the JVM Garbage Collector (GC). Cassandra's memtables—the in-memory write buffers that store incoming mutations before flushing them to SSTables on disk—initially relied on standard Java collection libraries like ConcurrentSkipListMap.

In Java, every object carries a memory overhead known as the Object Header. On a 64-bit JVM, this header typically consumes 12 to 16 bytes (depending on whether Compressed Object Pointers, or Compressed OOPs, are active). When you store millions of small key-value pairs inside a standard Java collection, you do not just store the raw bytes. You store:

1. 1.The collection's internal node objects.

2. 2.The key and value wrapper objects.

3. 3.The actual byte arrays.

This structure creates a highly fragmented heap layout where references point to other references across non-contiguous memory addresses. This phenomenon is known as pointer chasing.

When the Garbage Collector runs, it must traverse this massive web of object references to determine which objects are still reachable. A heap containing 10 million small, independent objects can cause GC pause times to spike into seconds, violating the tight latency budgets of real-time storage engines.

By understanding the exact layout of arrays on the JVM heap, we can design storage engines that minimize reference traversal and maximize CPU cache line efficiency.

The Mechanics of the Array Layout

When we allocate a Java array of objects:

this.store = new Entry[capacity];

The JVM allocates a single, contiguous block of memory to hold capacity number of references (pointers), not the actual Entry objects themselves. Each reference is 4 bytes (with Compressed OOPs enabled) or 8 bytes (with Compressed OOPs disabled).

When we populate the array, we instantiate Entry objects on the heap. The array elements point to these disparate memory locations. To retrieve a value, the CPU must:
1.Fetch the memory address of the array.
2.Calculate the offset to the target element index.
3.Read the memory address of the Entry object stored at that index (Cache Miss Risk #1).
4.Read the key reference stored inside the Entry object.
5.Traverse the key reference to read the actual string characters to perform an equality check (Cache Miss Risk #2).

If the keys do not match, the engine moves to the next index, repeating this pointer-chasing sequence.

Core Implementation Snippets

To write data into our bounded array, we must scan the existing items to prevent duplicate keys. If the key exists, we overwrite its entry. If it is a new key, we append it to the end of the array, provided we have not exceeded our allocated capacity.

Here is the core logic for the state insertion (put) operation:

public boolean put(String key, String value) {
    if (key == null) {
        throw new IllegalArgumentException("Key cannot be null");
    }
    // Scan sequentially to handle updates
    for (int i = 0; i < size; i++) {
        if (store[i].key.equals(key)) {
            store[i] = new Entry(key, value);
            return true;
        }
    }
    // Verify capacity constraints
    if (size >= capacity) {
        return false; 
    }
    store[size++] = new Entry(key, value);
    return true;
}

To retrieve a value, we must perform a linear scan from the beginning of the array to the current active size:

public String get(String key) {
    if (key == null) return null;
    for (int i = 0; i < size; i++) {
        if (store[i].key.equals(key)) {
            return store[i].value;
        }
    }
    return null; 
}

Trade-off Analysis: Parallel Arrays vs. Object Arrays

When designing an array-backed engine, we face a critical structural choice:

1.Array of Objects (Entry[]): Our chosen design.

**Pros:* High conceptual cohesion. Easy to manage and reason about. Overwriting an entry requires updating only a single array reference.
**Cons:* High pointer-chasing overhead. Every entry lookup requires traversing multiple object boundaries.

2.Parallel Arrays (String[] keys and String[] values):

**Pros:* Better spatial locality for key scans. The CPU can stream the contiguous keys array into its L1/L2 caches more efficiently because it does not have to jump through intermediate Entry objects.
**Cons:* High maintenance overhead. Deletions, insertions, and updates require synchronized indexing across separate arrays, increasing the risk of state corruption if index alignment drifts.

For our initial baseline, we prioritize structural safety and conceptual clarity, using the Entry[] design.

The Failure Demo: Linear Search Degradation

As our database grows, our linear scan lookup performance degrades at a rate of $O(N)$. If we store 10 keys, a lookup requires at most 10 comparison operations. If we store 100,000 keys, a lookup for a non-existent key (or the last inserted key) requires 100,000 comparisons.

In our hands-on implementation guide, we will run a micro-benchmark that highlights this architectural bottleneck. We will measure the time required to perform lookups on a small dataset versus a larger dataset. You will witness firsthand how linear scanning scales quadratically ($O(N^2)$) when performing sequential lookups during data ingestion.

Assignment: Dynamic Array Resizing with Allocation Metrics

Your assignment is to modify the baseline ArrayKV engine to support dynamic resizing while tracking the physical allocation cost of this operation.

Requirements:

1.Dynamic Resizing: If a put operation is called when the array is full (size == capacity), do not return false. Instead, double the size of the underlying array, copy all existing references to the new array, and then insert the new item.
2.Allocation Tracking: Track how many times a resize operation has occurred, and print a warning message to standard error (System.err) containing the old capacity, the new capacity, and the time taken in microseconds to perform the array copy.

Success Criteria:

Your engine must successfully complete a benchmark of 50,000 operations without throwing a capacity-exhausted error.
You must be able to compile and run your modified engine using raw command-line tools.
*The terminal output must show the resize warnings, detailing the capacity transitions (e.g., 1000 -> 2000).

Solution Hints

To implement the resize logic, utilize Java's highly optimized System.arraycopy method rather than a manual loop. System.arraycopy compiles down to a direct native memory block transfer (similar to memmove in C), which is significantly faster than copy loops executing inside the JVM interpreter.

Expected Implementation Pattern:

private void resize() {
    long start = System.nanoTime();
    int oldCapacity = this.capacity;
    this.capacity = oldCapacity * 2;
    
    Entry[] newStore = new Entry[this.capacity];
    System.arraycopy(this.store, 0, newStore, 0, this.size);
    this.store = newStore;
    
    long durationUs = (System.nanoTime() - start) / 1000;
    System.err.printf("[AstraKV System Warning] Storage resized: %d -> %d (%d us)n", 
        oldCapacity, this.capacity, durationUs);
}

This dynamic array pattern forms the basis of many resizing buffers in production systems, but as we will see on Day 2, it does not resolve the underlying lookup complexity bottleneck.