Time Based Key Value Store

 

Man at work, Cherry St Tavern, Philly

How do you store data identifiable both by a key and a timestamp ?

Write a map implementation with a get function that lets you retrieve the value of a key at a particular time.

It should contain the following methods:

set(key, value, time): sets key to value for t = time.
get(key, time): gets the key at t = time.

The map should work like this. If we set a key at a particular time, it will maintain that value forever or until it gets set at a later time. In other words, when we get a key at a time, it should return the value that was set for that key set at the most recent time.

Understanding the problem

The retrieval part of the question requires us to fetch the value using both the key and the timestamp. The timestamp is not an exact value that would have been stored, rather it would be a value that is within a range of the stored timestamp values

Solving it

We do need a map as our foundation, as that would allow a speedy lookup and storage of values by the key. Storing the temporal nature of the values requires some thought

One way of representing this would be to store a composite value -

• A submap of the values with the timestamp as the key 
• A sorted set containing all the timestamps. This set will be useful for retrieving floor values.

Retrieval of a value by key and timestamp -

• First retrieve the composite value by key
• Determine the floor value of the timestamp in the sorted set. 
• For example a request of 2, would return the greatest value lower than 2 , in this case 0.
• Use the floor value to lookup the return value in the submap

Java

In Java it is possible to use a TreeMap rather than the Map/Set combo. A TreeMap will keep all the keys sorted in a natural order or using a custom sorting order. It also provides methods like floorValue and ceiling to return values within a certain range