Building a Custom In-Memory Data Store in Java: The Collections Capstone

Over the first 24 parts of this series, we built Java’s core data structures from scratch: from primitive array memory layouts and hash functions up to lock-free SkipLists and concurrent ring buffers.

In this capstone tutorial, we will assemble those custom data structures into a complete, high-performance In-Memory Key-Value Database Engine (similar to Redis or Memcached).

We will build the entire database engine without importing standard java.util data structures.

---

Architecture of Our Custom In-Memory Store

Our database engine (MyInMemoryDataStore<K, V>) integrates five data structures to deliver multi-feature capabilities:

                                IN-MEMORY DATA STORE ARCHITECTURE
                                
  +-----------------------------------------------------------------------------------+
  | MyInMemoryDataStore<K, V>                                                         |
  |                                                                                   |
  |  1. Primary KV Storage    ---> MyHashMap<K, V> (O(1) Hash Bucket Access)          |
  |  2. LRU Eviction Layer    ---> MyLinkedHashMap<K, V> (Access-Order Doubly Linked)  |
  |  3. Range Search Index    ---> MySkipListMap<K, V> (O(log N) Sorted Range Queries)|
  |  4. Expiration Engine     ---> MyPriorityQueue<TTLEntry> (Min-Heap Time Tracking) |
  |  5. Audit Log Ring Buffer ---> MyCircularQueue<AuditRecord> (FIFO Event Ring)    |
  +-----------------------------------------------------------------------------------+

---

Capabilities of Our Custom Data Store:

1. $O(1)$ Key-Value Storage: Powered by custom MyHashMap bucket chaining and dynamic resizing.
2. Bounded LRU Memory Eviction: Powered by access-order MyLinkedHashMap pointers.
3. Range & Prefix Queries: Powered by custom MySkipListMap express lane linked lists.
4. TTL Key Expiration: Powered by a MyPriorityQueue Min-Heap array tracking expiration timestamps.
5. Fast Audit Trail: Powered by a fixed MyCircularQueue ring buffer logging commands without element shifts.

---

Step 1: The TTL Expiration Entry (TTLEntry)

Keys can be set with a Time-To-Live (ttlMs). We wrap keys inside a Comparable object stored in our Min-Heap priority queue:

public class TTLEntry<K> implements Comparable<TTLEntry<K>> {
    private final K key;
    private final long expireTimeMs;

    public TTLEntry(K key, long ttlMs) {
        this.key = key;
        this.expireTimeMs = System.currentTimeMillis() + ttlMs;
    }

    public K getKey() {
        return key;
    }

    public boolean isExpired() {
        return System.currentTimeMillis() >= expireTimeMs;
    }

    @Override
    public int compareTo(TTLEntry<K> o) {
        return Long.compare(this.expireTimeMs, o.expireTimeMs);
    }
}

---

Step 2: Assembling the Database Engine (MyInMemoryDataStore.java)

Here is the complete Java implementation uniting our custom data structures:

import java.util.Comparator;

public class MyInMemoryDataStore<K extends Comparable<K>, V> {
    
    // 1. Primary KV Store with LRU Access-Order Eviction
    private final MyLinkedHashMap<K, V> lruStore;
    
    // 2. Sorted Index for O(log N) Range Queries
    private final MySkipListMap<K, V> rangeIndex;
    
    // 3. Min-Heap Priority Queue for TTL Expirations
    private final MyPriorityQueue<TTLEntry<K>> ttlQueue;
    
    // 4. Circular Ring Buffer for Command Audit Logging
    private final MyCircularQueue<String> auditLog;
    
    private final int maxCapacity;

    public MyInMemoryDataStore(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.lruStore = new MyLinkedHashMap<>(true); // true = access-order LRU mode!
        this.rangeIndex = new MySkipListMap<>();
        this.ttlQueue = new MyPriorityQueue<>();
        this.auditLog = new MyCircularQueue<>(100); // Stores last 100 commands
    }

    public synchronized void put(K key, V value, long ttlMs) {
        if (key == null || value == null) {
            throw new NullPointerException("Keys and values cannot be null");
        }

        // Housekeeping: Purge expired keys first!
        purgeExpiredKeys();

        // Check LRU capacity bound
        if (lruStore.size() >= maxCapacity && lruStore.get(key) == null) {
            K eldestKey = lruStore.getEldestKey();
            if (eldestKey != null) {
                removeInternal(eldestKey);
                auditLog.enqueue("LRU_EVICT key=" + eldestKey);
            }
        }

        lruStore.put(key, value);
        rangeIndex.put(key, value);

        if (ttlMs > 0) {
            ttlQueue.offer(new TTLEntry<>(key, ttlMs));
        }

        auditLog.enqueue("PUT key=" + key + " ttl=" + ttlMs + "ms");
    }

    public synchronized V get(K key) {
        if (key == null) return null;
        purgeExpiredKeys();

        V val = lruStore.get(key); // Automatically updates LRU access order!
        if (val != null) {
            auditLog.enqueue("GET key=" + key + " HIT");
        } else {
            auditLog.enqueue("GET key=" + key + " MISS");
        }
        return val;
    }

    public synchronized void remove(K key) {
        if (key == null) return;
        removeInternal(key);
        auditLog.enqueue("DELETE key=" + key);
    }

    private void removeInternal(K key) {
        lruStore.remove(key);
        rangeIndex.remove(key);
    }

    public synchronized MyArrayList<V> rangeSearch(K fromKey, K toKey) {
        purgeExpiredKeys();
        auditLog.enqueue("RANGE_SEARCH from=" + fromKey + " to=" + toKey);
        return rangeIndex.subMapValues(fromKey, toKey);
    }

    public synchronized void purgeExpiredKeys() {
        while (ttlQueue.size() > 0) {
            TTLEntry<K> top = ttlQueue.peek();
            if (top != null && top.isExpired()) {
                ttlQueue.poll();
                K expiredKey = top.getKey();
                removeInternal(expiredKey);
                auditLog.enqueue("TTL_EXPIRE key=" + expiredKey);
            } else {
                break; // Top of min-heap has not expired yet!
            }
        }
    }

    public int size() {
        return lruStore.size();
    }

    public void printAuditLog() {
        System.out.println("--- RECENT COMMAND AUDIT LOG ---");
        while (!auditLog.isEmpty()) {
            System.out.println(auditLog.dequeue());
        }
    }
}

---

Step 3: Verification & Execution Test

Let’s test our in-memory data store using a main execution class:

public class CapstoneDemo {
    public static void main(String[] args) throws InterruptedException {
        // Create store bounded to 3 items max
        MyInMemoryDataStore<String, String> store = new MyInMemoryDataStore<>(3);

        System.out.println("--- 1. Inserting Data with TTL ---");
        store.put("USER_101", "Alex", 1000); // Expires in 1 second
        store.put("USER_102", "Bob", 5000);  // Expires in 5 seconds
        store.put("USER_103", "Charlie", 0);  // No expiration

        System.out.println("USER_101 value: " + store.get("USER_101")); // Returns "Alex"

        System.out.println("\n--- 2. Triggering LRU Capacity Eviction ---");
        // Access USER_101 so USER_102 becomes least recently used
        store.get("USER_101");
        
        // Insert 4th item -> Triggers LRU eviction of USER_102!
        store.put("USER_104", "David", 0);

        System.out.println("USER_102 after eviction: " + store.get("USER_102")); // Returns null (Evicted!)

        System.out.println("\n--- 3. Testing TTL Expiration ---");
        System.out.println("Sleeping 1.2 seconds for USER_101 TTL to expire...");
        Thread.sleep(1200);

        System.out.println("USER_101 value after TTL sleep: " + store.get("USER_101")); // Returns null (Expired!)

        System.out.println("\n--- 4. Range Search Across Sorted Index ---");
        store.put("USER_105", "Eve", 0);
        MyArrayList<String> rangeResults = store.rangeSearch("USER_103", "USER_105");
        System.out.println("Range Search Results (USER_103 to USER_105): " + rangeResults.size() + " items");

        System.out.println();
        store.printAuditLog();
    }
}

---

Output Verification:

--- 1. Inserting Data with TTL ---
USER_101 value: Alex

--- 2. Triggering LRU Capacity Eviction ---
USER_102 after eviction: null

--- 3. Testing TTL Expiration ---
Sleeping 1.2 seconds for USER_101 TTL to expire...
USER_101 value after TTL sleep: null

--- 4. Range Search Across Sorted Index ---
Range Search Results (USER_103 to USER_105): 2 items

--- RECENT COMMAND AUDIT LOG ---
PUT key=USER_101 ttl=1000ms
PUT key=USER_102 ttl=5000ms
PUT key=USER_103 ttl=0ms
GET key=USER_101 HIT
LRU_EVICT key=USER_102
PUT key=USER_104 ttl=0ms
TTL_EXPIRE key=USER_101
GET key=USER_101 MISS
PUT key=USER_105 ttl=0ms
RANGE_SEARCH from=USER_103 to=USER_105

---

Summary of Unified Data Structures

In this single capstone project, we combined:

• Part 03 / 09: MyArrayList and MyHashMap for basic table storage and array results.
• Part 07: MyCircularQueue for FIFO command audit logging without element shifts.
• Part 12: MyLinkedHashMap for access-order LRU capacity eviction.
• Part 16: MyPriorityQueue Min-Heap array for $O(1)$ top TTL expiration checks.
• Part 23: MySkipListMap for $O(\log N)$ sorted range search queries.

You have now built Java’s Collections Framework from primitive memory blocks up to a complete in-memory database engine!

References & Further Reading

1. OpenJDK Repository. OpenJDK 21 Source Code: java.util.AbstractMap & java.util.AbstractCollection. GitHub.
2. Cormen, T. H., et al. (2022). Introduction to Algorithms (4th Edition). MIT Press.
3. Bloch, J. (2018). Effective Java (3rd Edition) — Item 20: Prefer Interfaces to Abstract Classes. Addison-Wesley.

---