Here's an implementation in Python built on top of Redis using sorted sets:

    class TimeStore:
        def __init__(self, redis_client):
            self.redis_client = redis_client

        @staticmethod
        def timestamp(time): return (time-datetime.datetime(1970,1,1)).total_seconds()

        def set_value(self, key, value, time=None):
            if time is None: time = datetime.datetime.utcnow()

            self.redis_client.zadd(key, self.timestamp(time), value)

        def get_value(self, key, time=None):
            if time is None: time = datetime.datetime.utcnow()

            for item in self.redis_client.zrevrangebyscore(key, self.timestamp(time), 0, start=0, num=1):
                return item
            return None

        def cleanup_before(self, key, time):
            self.redis_client.zremrangebyscore(key, 0, self.timestamp(time))