Time Based Key-Value Store

Updated on 27 June, 2025
Time Based Key-Value Store header image

Problem Statement

The task is to design a data structure named TimeMap that functions like a key-value store, but with the ability to handle multiple values for the same key at different timestamps. This data structure has two main functionalities:

  • Storing Values: Through the method set, it can store a specific key with its corresponding value at a given timestamp. This function respects the temporal sequence of input as each new timestamp for the same key is guaranteed to be strictly increasing according to the problem constraints.

  • Retrieving Values: Through the method get, this data structure should be able to return a value corresponding to the key, considering the nearest past timestamp or the exact timestamp if matched directly. If an exact timestamp match or a suitable past timestamp isn't found, it returns an empty string. This function utilizes the given property that timestamp inputs are strictly increasing, thus simplifying the search process for the nearest relevant timestamp.

The TimeMap class is initialized with no arguments, preparing it to handle the subsequent set and get requests.

Examples

Example 1

Input:

["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output:

[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation:

TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1); // return "bar"
timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, the only value is at timestamp 1.
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" at timestamp = 4.
timeMap.get("foo", 4); // return "bar2"
timeMap.get("foo", 5); // return "bar2"

Constraints

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 10^7
  • All the timestamps timestamp of set are strictly increasing.
  • At most 2 * 10^5 calls will be made to set and get.

Approach and Intuition

The implementation of the TimeMap revolves around efficient data retrieval and storage mechanisms, considering the key, value, and timestamps. Given the constraints and operations, here is an intuitive logic breakdown:

  1. Choosing the Right Data Structure:

    • A hash table (or dictionary in Python) is ideal for key to value mappings due to average constant time complexity for insertions and lookups.
    • For handling each key's multiple timestamps, we can map each key to another dictionary or a sorted list which will itself store pairs of timestamp and value.
  2. Handling the set Method:

    • Inserting a new value for a given key and timestamp into the data structure involves appending or creating a new entry. Since the timestamps are strictly increasing, appending the new (timestamp, value) pair to a list associated with the key is simple and efficient.
  3. Handling the get Method:

    • For retrieval, the method should return the value where timestamp_prev <= timestamp. Utilizing the property of sorted timestamps, a binary search can be performed to find the largest timestamp_prev which is an optimal strategy for this method. It minimizes the lookup time from linear to logarithmic.
  4. Edge Case Handling:

    • If a get query is requested with a timestamp earlier than the first stored timestamp for that key, it promptly returns an empty string.
    • If a set operation tries inserting a timestamp out of order (which contradicts the input assumption), proper error handling or restructuring might be needed, but considering constraints, this scenario is invalid.

This approach ensures that the operations are done in a time-efficient manner, respecting the increasing sequence of timestamps and utilizing modern data structure capabilities like hash tables and binary search. The constraints establish that the size and frequency of operations are well within the manageable range for these structures.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp
class KeyValueStore {
public:
    unordered_map<string, vector<pair<int, string>>> store;
    KeyValueStore() {
    }
    
    void storeValue(string key, string value, int timestamp) {
        store[key].push_back({ timestamp, value });
    }
    
    string retrieve(string key, int timestamp) {
        if (store.find(key) == store.end()) {
            return "";
        }
        
        if (timestamp < store[key].front().first) {
            return "";
        }
        
        int low = 0;
        int high = store[key].size();
        
        while (low < high) {
            int mid = (low + high) / 2;
            if (store[key][mid].first <= timestamp) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        if (high == 0) {
            return "";
        }
                
        return store[key][high - 1].second;
    }
};

The provided C++ code defines a class KeyValueStore which implements a time-based key-value store. This store allows you to save multiple values for the same key with unique timestamps and retrieve a value for a key at a specific point in time. Here's a breakdown of its functionality and usage:

  • Data Structure:

    • The class uses an unordered_map named store where each key is a string and its corresponding value is a vector of pairs. Each pair consists of an integer timestamp and a string value.
  • Constructor:

    • KeyValueStore(): Initializes the key-value store.
  • Methods to Manipulate Data:

    • storeValue(string key, string value, int timestamp): This method stores the value along with its timestamp into the vector corresponding to the given key.
    • retrieve(string key, int timestamp): Retrieves the value for the passed key at the specified timestamp, or closest previous timestamp if the exact timestamp is not present.
  • Functionality Details of retrieve:

    • First, the method checks if the key exists in the map. If it does not, it returns an empty string.
    • It then checks if the requested timestamp is earlier than the first timestamp in the vector; if so, it also returns an empty string.
    • The method uses a binary search algorithm to find the closest lower or equal timestamp. This section divides to check midpoints and adjust low and high values, effectively finding the highest index where the timestamp is less than or equal to the requested timestamp.
    • If there’s no valid high index due to boundary condition, it again returns an empty string. Otherwise, it returns the value from the vector at index high - 1.

This structure provides an efficient way to retrieve values based on time and makes the KeyValueStore practical for situations where time-based versioning of data is crucial, such as caching systems, databases, and logging systems.

java
class KeyValueStore {
    HashMap<String, ArrayList<Pair<Integer, String>>> store;

    public KeyValueStore() {
        store = new HashMap<>();
    }

    public void put(String key, String value, int timestamp) {
        if (!store.containsKey(key)) {
            store.put(key, new ArrayList<>());
        }

        store.get(key).add(new Pair<>(timestamp, value));
    }

    public String retrieve(String key, int timestamp) {
        if (!store.containsKey(key)) {
            return "";
        }

        if (timestamp < store.get(key).get(0).getKey()) {
            return "";
        }

        int start = 0;
        int end = store.get(key).size();
        
        while (start < end) {
            int mid = (start + end) / 2;
            if (store.get(key).get(mid).getKey() <= timestamp) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (end == 0) {
            return "";
        }

        return store.get(key).get(end - 1).getValue();
    }
}

The provided Java code outlines a class KeyValueStore that implements a time-based key-value store, enabling not only storing key-value pairs but also retrieving the value associated with a key at a particular timestamp.

Summary of the Class and Methods:

  • The KeyValueStore class utilizes a HashMap where each key maps to a list of pairs. Each pair consists of a timestamp and the corresponding value set at that timestamp.
  • The constructor initializes the store as an empty HashMap.
  • The put method adds a new key-value pair with the given timestamp. If the key does not already exist in the map, it first creates a new entry in the map with an empty list.
  • The retrieve method returns the value associated with a given key at the specified timestamp or the closest earlier timestamp. If no suitable entry is found, it returns an empty string.

Detailed Behavior of Methods:

  1. put(String key, String value, int timestamp):

    • Checks if the key exists. If not, it initializes an empty list for this key.
    • Adds the new timestamp-value pair to the list associated with the key.
  2. retrieve(String key, int timestamp):

    • Performs an early return of an empty string if the key does not exist or the first timestamp is already higher than the requested timestamp.
    • Executes a binary search to find the largest timestamp that is less than or equal to the requested timestamp.
    • Returns the paired value if such a timestamp exists, otherwise returns an empty string.

This implementation uses an ArrayList to store pairs per key, which ensures efficient append operations for the put method and allows binary search for the retrieve method, striking a balance between complexity and performance. However, one should account for potential performance implications when the list grows, as the binary search time complexity is O(log n)).

js
let keyValueStore = {};
var KeyValueTimeMap = function() { 
    keyValueStore = {};
};

KeyValueTimeMap.prototype.setKeyValue = function(key, value, timestamp) {
    if (!(key in keyValueStore)) {
        keyValueStore[key] = [];
    }

    keyValueStore[key].push([timestamp, value]);
};

KeyValueTimeMap.prototype.getKeyValue = function(key, timestamp) {
    if (!(key in keyValueStore)) {
        return "";
    }

    if (timestamp < keyValueStore[key][0][0]) {
        return "";
    }

    let start = 0;
    let end = keyValueStore[key].length;

    while (start < end) {
        let middle = Math.floor((start + end) / 2);
        if (keyValueStore[key][middle][0] <= timestamp) {
            start = middle + 1;
        } else {
            end = middle;
        }
    }

    if (end == 0) {
        return "";
    }

    return keyValueStore[key][end - 1][1];
};

The provided JavaScript solution implements a time-based key-value store using an object keyValueStore to map keys to arrays of timestamp-value pairs. The solution consists of a KeyValueTimeMap constructor and two methods: setKeyValue and getKeyValue.

In the KeyValueTimeMap constructor:

  • Initialize keyValueStore as an empty object. This is used to store the keys along with their corresponding values and timestamps.

In the setKeyValue method:

  • Check if the key does not exist in keyValueStore and initialize it with an empty array if so.
  • Push the [timestamp, value] pair into the array of the given key in keyValueStore.

In the getKeyValue method:

  • Return an empty string if the key is not present in the store.
  • If the provided timestamp is less than the first timestamp in the array for the key, return an empty string, indicating no value is set before the given timestamp.
  • Use binary search to find the highest index where the timestamp is less than or equal to the provided timestamp.
  • Return the corresponding value if found; if not, return an empty string if the search query goes out of bounds of array indices.

This implementation ensures efficient retrieval of values associated with specific timestamps, achieving better performance for search operations compared to a linear scan.

python
class TimeDictionary:
    def __init__(self):
        self.storage = {}

    def store(self, identifier: str, content: str, time: int) -> None:
        if identifier not in self.storage:
            self.storage[identifier] = []
        self.storage[identifier].append([time, content])

    def retrieve(self, identifier: str, time: int) -> str:
        if identifier not in self.storage:
            return ""

        if time < self.storage[identifier][0][0]:
            return ""

        start = 0
        end = len(self.storage[identifier])

        while start < end:
            middle = (start + end) // 2
            if self.storage[identifier][middle][0] <= time:
                start = middle + 1
            else:
                end = middle

        return "" if end == 0 else self.storage[identifier][end - 1][1]

The TimeDictionary class in Python3 is designed to implement a time-based key-value store, where keys can have different values associated with specific points in time. This allows for retrieving the most recent value for a key at any given time.

  • Initialize the TimeDictionary class with no arguments. A private dictionary named storage is set up to hold the key-value pairs.

  • The store method takes three arguments: identifier (a string representing the key), content (the value to store), and time (the timestamp associated with the value). This method stores the value along with its timestamp in the storage dictionary under the specified key. If the key does not exist, a new entry is created.

  • The retrieve method requires the identifier and time as arguments and returns the value associated with the key for the most recent time up to the specified time. If the key does not exist or no values are timestamped at or before the provided time, it returns an empty string. It uses binary search to efficiently find the closest timestamp, ensuring optimal performance even with large amounts of data.

This structure is particularly useful for systems where data values are tracked and updated over time, and past states need to be accessed quickly. The class provides an efficient solution for storing and querying data based on time, making it a suitable choice for scenarios like versioned data or change tracking.

Comments

No comments yet.