# Cache Design

## 1. Estimate Cache Memory needed for caching 1 million entries of a Java object

### About

In a typical Spring Boot microservice, suppose we are caching frequently accessed data using an in-memory cache like `ConcurrentHashMap`, `Caffeine`, or Spring’s built-in caching abstraction. Each cached entry consists of:

* **Key**: A unique identifier (e.g., String or UUID)
* **Value**: A Java object with approximately 10–15 fields

Let’s estimate how much **JVM heap memory** will be required to cache **1 million such objects**.

**Breakdown of Memory Usage**

### 1. Object Overhead (JVM Internal Structure)

Every object in the JVM has some built-in memory overhead, regardless of the fields it contains. This includes:

<table data-full-width="true"><thead><tr><th width="159.98046875">Component</th><th>Size (Bytes)</th><th>Description</th></tr></thead><tbody><tr><td>Object Header</td><td><strong>12 bytes</strong> (on 64-bit JVM with compressed oops)</td><td>Stores object metadata like identity hash, GC info, and type pointer.</td></tr><tr><td>Object Padding</td><td><strong>Up to 8 bytes</strong> (to align to 8-byte boundaries)</td><td>JVM aligns object size to 8-byte multiples for efficient memory access.</td></tr><tr><td>Reference Fields</td><td><strong>4 or 8 bytes each</strong></td><td>Depending on whether compressed oops are enabled.</td></tr><tr><td>Internal Pointers</td><td>Adds indirection and slight overhead when objects contain references to other objects.</td><td></td></tr></tbody></table>

{% hint style="info" %}
**Typical overhead per object (excluding fields):** \~12–16 bytes\
If references are involved, field alignment and padding increase usage further.
{% endhint %}

### 2. Estimated Field Composition (Example: 10 Fields)

Let's assume the object being cached looks like this:

```java
public class UserProfile {
    private UUID id;
    private String name;
    private String email;
    private int age;
    private boolean active;
    private long createdAt;
    private String country;
    private String phone;
    private int loginCount;
    private boolean verified;
    // Total: 10 fields
}
```

<table data-full-width="true"><thead><tr><th width="101.87890625">Field Type</th><th width="67.53125">Count</th><th width="253.1953125">Estimated Size</th><th>Notes</th></tr></thead><tbody><tr><td><code>UUID</code></td><td>1</td><td>16 bytes</td><td>Backed by two <code>long</code> values</td></tr><tr><td><code>String</code></td><td>4</td><td>40–80 bytes each</td><td>Depends on string length; average 60 bytes</td></tr><tr><td><code>int</code></td><td>2</td><td>4 bytes each</td><td>Total: 8 bytes</td></tr><tr><td><code>boolean</code></td><td>2</td><td>1 byte each (but rounded up)</td><td>Total padded to 4–8 bytes</td></tr><tr><td><code>long</code></td><td>1</td><td>8 bytes</td><td>64-bit long</td></tr></tbody></table>

**Total estimated size of fields**:

* `UUID` = 16 bytes
* `4 Strings` = \~240 bytes
* `2 int` = 8 bytes
* `2 boolean` (padded) = \~8 bytes
* `1 long` = 8 bytes

**→ Total = \~280–320 bytes for fields**

### 3. Additional Memory Per Entry (Cache-Level Overhead)

When storing these objects in a map or cache (e.g., `ConcurrentHashMap` or `Caffeine`), we also need to account for:

<table><thead><tr><th width="191.87109375">Component</th><th width="150.5078125">Estimated Size</th><th>Description</th></tr></thead><tbody><tr><td><strong>Key Object</strong></td><td>~40–60 bytes</td><td>UUID or String, including its internal character array</td></tr><tr><td><strong>Map Entry Overhead</strong></td><td>~32–48 bytes</td><td>Bucket pointer, hash, references</td></tr><tr><td><strong>Value Object</strong></td><td>~300–350 bytes</td><td>As estimated above</td></tr><tr><td><strong>References</strong></td><td>~8–16 bytes</td><td>Reference to value and key</td></tr></tbody></table>

**Total per cache entry**:\
\&#xNAN;**\~400–500 bytes** conservatively\
In worst cases, may grow up to **550–600 bytes**.

### 4. Total Estimated Memory Usage

To calculate total memory for 1 million entries:

```
Per Entry (average): 500 bytes
Total Entries       : 1,000,000
-------------------------------
Total Memory Needed : 500 * 1,000,000 = 500,000,000 bytes ≈ 476 MB
```

#### Buffering for Safety

Due to GC metadata, alignment, fragmentation, and fluctuations in field size:

* Add 30–40% buffer
* **Recommended Heap Size**: **700–800 MB**

### 5. How to Measure Actual Memory Usage (Empirical Approach) ?

To validate the estimate with real data:

1. **Write a test class** to load 1 million objects into a `Map`:

   ```java
   Map<UUID, UserProfile> cache = new HashMap<>();
   for (int i = 0; i < 1_000_000; i++) {
       cache.put(UUID.randomUUID(), new UserProfile(...));
   }
   ```
2. **Use a Java profiler**:
   * **JVisualVM**: Attach to the JVM and inspect heap usage.
   * **Eclipse MAT** (Memory Analyzer Tool): For analyzing heap dumps.
   * **YourKit** or **JProfiler**: For in-depth memory profiling.
3. **Compare memory usage before and after population.**

## **2.** LRU Cache

Design and build a "least recently used" cache, which evicts the least recently used item. The cache should map from keys to values (allowing us to insert and retrieve a value associated with a particular key) and be initialized with a max size. When it is full, it should evict the least recently used item.

We need to **design a cache** that:

1. Stores key-value pairs.
2. Has a **maximum size** (capacity).
3. When inserting a new item and the cache is **full**, it must **evict the least recently used (LRU)** item.
4. Both `get(key)` and `put(key, value)` operations must be done in **O(1)** time.

To support O(1) operations:

* Use a **HashMap** to store key → node mappings.
* Use a **Doubly Linked List** to track usage order (most recently used at head, least at tail).

Whenever:

* We `get(key)`: Move the node to the front (MRU).
* We `put(key, value)`:
  * If key exists: Update and move to front.
  * If key doesn’t exist and at capacity: Remove tail (LRU), insert new node at head.

```java
import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    
    // Doubly linked list node
    private class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> cache; // Maps keys to nodes
    private final Node head, tail;          // Dummy head and tail for ease of insertion/removal

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        // Initialize dummy head and tail to avoid null checks
        head = new Node(0, 0); 
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // Get the value associated with a key
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1; // Not found
        }

        Node node = cache.get(key);

        // Move the accessed node to the front (most recently used)
        moveToFront(node);
        return node.value;
    }

    // Put a key-value pair into the cache
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // Key exists: update value and move to front
            Node node = cache.get(key);
            node.value = value;
            moveToFront(node);
        } else {
            // New key
            if (cache.size() == capacity) {
                // Remove least recently used (LRU) node from tail
                Node lru = tail.prev;
                removeNode(lru);
                cache.remove(lru.key);
            }

            Node newNode = new Node(key, value);
            addToFront(newNode);
            cache.put(key, newNode);
        }
    }

    // Move an existing node to the front (MRU position)
    private void moveToFront(Node node) {
        removeNode(node);
        addToFront(node);
    }

    // Add a node right after dummy head
    private void addToFront(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    // Remove a node from the list
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
```

```java
public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);

        cache.put(1, 10); // cache = {1=10}
        cache.put(2, 20); // cache = {2=20, 1=10}

        System.out.println(cache.get(1)); // returns 10, cache = {1=10, 2=20}

        cache.put(3, 30); // evicts key 2, cache = {3=30, 1=10}
        System.out.println(cache.get(2)); // returns -1

        cache.put(4, 40); // evicts key 1, cache = {4=40, 3=30}
        System.out.println(cache.get(1)); // returns -1
        System.out.println(cache.get(3)); // returns 30
        System.out.println(cache.get(4)); // returns 40
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.pranaypourkar.co.in/the-programmers-guide/system-design/design-problems/cache-design.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.