The Question

Thread-Safe Versioned Key-Value Store

Design and implement a thread-safe, timestamp-based key-value store. The data structure should support two main operations: 1. set(key, value, timestamp): Stores the value associated with key at the given timestamp. 2. get(key, timestamp): Returns the value associated with the given key such that the stored timestamp is the largest value less than or equal to the requested timestamp. If no such value exists, return null or an empty string. Constraints: - The implementation must be thread-safe and handle concurrent reads and writes. - The get operation should be optimized for performance, ideally $O(\log N)$ where $N$ is the number of versions for a specific key. - Multiple values can be stored for the same key at different timestamps.

Java

ConcurrentHashMap

ConcurrentSkipListMap

Binary Search

Questions & Insights

Clarifying Questions

Are timestamps strictly increasing? In a real-world system, timestamps might arrive slightly out of order due to network latency, but for this puzzle, we usually assume set operations for a specific key provide increasing timestamps, or the data structure must handle insertions at any point in the timeline.

How should concurrency be handled? Should we prioritize high-throughput writes (lock-free structures) or strictly serializable consistency?

What is the scale of data? If the number of versions per key is massive, we need an efficient search (

O(\log N)

) rather than a linear scan.

What should be returned if no value exists? We will assume returning null or an empty string is appropriate if the timestamp is earlier than the first recorded version.

Assumptions

Timestamps are represented as integers or longs.

The get operation must return the value associated with the largest timestamp_prev <= timestamp_query.

The system must be thread-safe for concurrent readers and writers.

Thinking Process

Data Structure Choice: We need a two-level mapping. The first level maps a key to its history. The second level maps timestamps to values. Since we need to find the "largest timestamp less than or equal to

X

", a sorted map or a skip list is ideal to support floor operations.

Concurrency Strategy: A ConcurrentHashMap is the standard for the top-level key lookup. For the version history, using a ConcurrentSkipListMap provides a thread-safe, lock-free way to maintain sorted timestamps and perform floor lookups in

O(\log N)

time.

Binary Search vs. Built-in Methods: While we could use an ArrayList with Collections.binarySearch, ConcurrentSkipListMap is more robust for multi-threaded environments where writes and reads happen simultaneously, avoiding ConcurrentModificationException.

Atomic Operations: We use computeIfAbsent to ensure that the creation of the history map for a new key is atomic and thread-safe.

Implementation Breakdown

Problem Set

Functional Requirements:

set(String key, String value, int timestamp): Stores the value with the given timestamp.

get(String key, int timestamp): Returns the value such that timestamp_prev <= timestamp.

Constraints:

Must be thread-safe.

get must be

O(\log N)

where

N

is the number of versions for that key.

set must be

O(\log N)

for sorted insertion.

Approach

Algorithm: Binary Search (via Skip List navigation).

Data Structure: ConcurrentHashMap and ConcurrentSkipListMap.

Complexity:

Time: set

O(\log N)

, get

O(\log N)

Space:

O(K \times V)

where

K

is unique keys and

V

is versions per key.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: Using ConcurrentSkipListMap is highly readable and idiomatic in Java. However, if writes are strictly sequential per key, a simple ArrayList with synchronized blocks and binarySearch might have a smaller memory footprint.

Memory Management: In a production system, versioned stores can grow indefinitely. One might implement a TTL (Time To Live) for older versions or a "max versions per key" limit to prune the ConcurrentSkipListMap.

Garbage Collection: Frequent writes create many Entry objects. For extremely high-performance systems, using primitive-specialized data structures (like those in fastutil or Koloboke) could reduce pressure on the JVM GC.

Snapshot Isolation: This structure naturally supports a form of snapshot isolation, useful in building distributed databases where "Read at Timestamp T" is a core primitive.