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:

Component	Size (Bytes)	Description
Object Header	12 bytes (on 64-bit JVM with compressed oops)	Stores object metadata like identity hash, GC info, and type pointer.
Object Padding	Up to 8 bytes (to align to 8-byte boundaries)	JVM aligns object size to 8-byte multiples for efficient memory access.
Reference Fields	4 or 8 bytes each	Depending on whether compressed oops are enabled.
Internal Pointers	Adds indirection and slight overhead when objects contain references to other objects.

Typical overhead per object (excluding fields): ~12–16 bytes If references are involved, field alignment and padding increase usage further.

2. Estimated Field Composition (Example: 10 Fields)

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

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
}

Field Type	Count	Estimated Size	Notes
UUID	1	16 bytes	Backed by two long values
String	4	40–80 bytes each	Depends on string length; average 60 bytes
int	2	4 bytes each	Total: 8 bytes
boolean	2	1 byte each (but rounded up)	Total padded to 4–8 bytes
long	1	8 bytes	64-bit long

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:

Component	Estimated Size	Description
Key Object	~40–60 bytes	UUID or String, including its internal character array
Map Entry Overhead	~32–48 bytes	Bucket pointer, hash, references
Value Object	~300–350 bytes	As estimated above
References	~8–16 bytes	Reference to value and key

Total per cache entry: ~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:

   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.

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;
    }
}

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
    }
}